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

北京大学学报（自然科学版）

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

凤旺森,陈萍,张蓓,马皓

北京大学计算中心，网络与软件安全保障教育部重点实验室，北京100871；

收稿日期:2008-05-12 出版日期:2009-05-20 发布日期:2009-05-20

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

FENG Wangsen, CHEN Ping, ZHANG Bei, MA Hao

Key Laboratory of Network and Software Security Assurance, Ministry of Education, Computing Center, Peking University, Beijing 100871;

Received:2008-05-12 Online:2009-05-20 Published:2009-05-20

摘要/Abstract

摘要： 由于无线网络存在节点失效、链路断裂等特性，虚拟主干网需要具备一定的容错性。利用2-连通k-支配集作为容错虚拟主干网的模型。通过分析单位圆盘图中极大独立集的性质和连通图的块-割点树结构，首次设计出在无线自组织网络中构造2-连通k-支配虚拟主干网的近似算法。从理论上分析了该算法的时间复杂度，并证明了该算法的近似比为常数。

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

Abstract: 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.

Key words: 2-connected k-dominating set, approximation algorithm, wireless ad-hoc network, virtual backbone

中图分类号:

TP391

凤旺森,陈萍,张蓓,马皓. 近似2-连通k-支配容错虚拟主干网[J]. 北京大学学报（自然科学版）.

FENG Wangsen,CHEN Ping,ZHANG Bei,MA Hao. Approximating 2-Connected k-Dominating Fault-Tolerant Virtual Backbone[J]. Acta Scientiarum Naturalium Universitatis Pekinensis.

导出引用管理器 EndNote|Ris|BibTeX

链接本文: https://xbna.pku.edu.cn/CN/

https://xbna.pku.edu.cn/CN/Y2009/V45/I3/421