近似2-连通k-支配容错虚拟主干网  

Approximating 2-Connected k-Dominating Fault-Tolerant Virtual Backbone

作　　者：凤旺森[1] 陈萍[1] 张蓓[1] 马皓[1] 

机构地区：[1]北京大学计算中心,网络与软件安全保障教育部重点实验室,北京100871

出　　处：《北京大学学报（自然科学版）》2009年第3期421-425,共5页Acta Scientiarum Naturalium Universitatis Pekinensis

基　　金：国家高技术研究发展计划专项经费(2006AA01Z456);国家重点基础研究发展计划项目(2009CB320505)资助

摘　　要：由于无线网络存在节点失效、链路断裂等特性,虚拟主干网需要具备一定的容错性。利用2-连通k-支配集作为容错虚拟主干网的模型。通过分析单位圆盘图中极大独立集的性质和连通图的块-割点树结构,首次设计出在无线自组织网络中构造2-连通k-支配虚拟主干网的近似算法。从理论上分析了该算法的时间复杂度,并证明了该算法的近似比为常数。Because of the inherent node （link） failures in wireless networks, virtual backbones should be fault-tolerant. Fault- tolerant virtual backbones were modeled as 2-connected k-dominating sets. An approximation algorithm was designed to find a 2- connected k-dominating virtual backbone in wireless ad-hoc networks by analyzing the properties of maximal independent sets in unit disk graphs and the block-cutvertex tree structure of connected graphs. The time complexity and the performance ratio of the algorithm were analyzed and proved to be a constant, respectively.

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

分 类 号：TN929.5[电子电信—通信与信息系统]