无线自组织网络中构造2-连通k-支配虚拟主干网的近似算法  

An Approximation Algorithm for Constructing a 2-Connected k-Dominating Virtual Backbone in Wireless Ad Hoc Networks

作　　者：凤旺森[1,2] 屈婉玲[1,2] 王捍贫[1,2] 张立昂[1,2] 

机构地区：[1]北京大学信息科学技术学院软件研究所,北京100871 [2]高可信软件技术教育部重点实验室,北京100871

出　　处：《计算机工程与科学》2008年第10期21-23,26,共4页Computer Engineering & Science

基　　金：国家863计划资助项目(2006AA01Z160)

摘　　要：在无线自组织网络中,经常选取一些节点形成虚拟主干网,用以支持路由和区域监视等任务。由于无线网络自身存在误码率高、易受干扰等弱点,虚拟主干网需要具有一定的容错性。已经有研究者提出使用k-连通k-支配集合在无线自组织网络中构造容错虚拟主干网,并通过模拟实验评估了算法的性能。近年来,WangFeng等人设计了常数近似算法用来构造2-连通虚拟主干网。本文将设计一个常数近似算法用以在无线自组织网络中构造一个2-连通k-支配虚拟主干网。Some nodes are often chosen to form a virtual backbone in wireless ad hoc networks in order to support routing and other tasks such as area monitoring. Because of the inherent node （link） failures in wireless networks, virtual backbones should be fault-tolerant. Recently,researchers have suggested to construct a fault-tolerant virtual backbone with a kconnected k-dominating set, and evaluated the performance of their algorithms via simulations. Feng Wang et al. have designed an approximation algorithm to construct a 2-connected fault-tolerant virtual backbone in wireless ad hoe networks. In this paper,a constant ratio approximation algorithm is designed to find a 2-connected k-dominating virtual backbone.

关 键 词：2-连通是一支配集 近似算法 无线自组织网络 虚拟主干网 

分 类 号：TP393.03[自动化与计算机技术—计算机应用技术]