| 近似2-连通k-支配容错虚拟主干网 |
| |
| 引用本文： | 凤旺森,陈萍,张蓓,马皓. 近似2-连通k-支配容错虚拟主干网[J]. 北京大学学报(自然科学版), 2009, 45(3): 421 |
| |
| 作者姓名： | 凤旺森 陈萍 张蓓 马皓 |
| |
| 作者单位： | 北京大学计算中心，网络与软件安全保障教育部重点实验室，北京100871； |
| |
| 基金项目： | 国家高技术研究发展计划(863计划)，国家重点基础研究发展规划(973计划) |
| |
| 摘 要： | 由于无线网络存在节点失效、链路断裂等特性，虚拟主干网需要具备一定的容错性。利用2-连通k-支配集作为容错虚拟主干网的模型。通过分析单位圆盘图中极大独立集的性质和连通图的块-割点树结构，首次设计出在无线自组织网络中构造2-连通k-支配虚拟主干网的近似算法。从理论上分析了该算法的时间复杂度，并证明了该算法的近似比为常数。
|
| 关 键 词： | 2-连通k-支配集 近似算法 无线自组织网络 虚拟主干网 |
| 收稿时间： | 2008-05-12 |
Approximating 2-Connected k-Dominating Fault-Tolerant Virtual Backbone |
| |
| FENG Wangsen,CHEN Ping,ZHANG Bei,MA Hao. Approximating 2-Connected k-Dominating Fault-Tolerant Virtual Backbone[J]. Acta Scientiarum Naturalium Universitatis Pekinensis, 2009, 45(3): 421 |
| |
| Authors: | FENG Wangsen CHEN Ping ZHANG Bei MA Hao |
| |
| Affiliation: | Key Laboratory of Network and Software Security Assurance, Ministry of Education, Computing Center, Peking University, Beijing 100871; |
| |
| 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 an... |
| |
| Keywords: | 2-connected k-dominating set approximation algorithm wireless ad-hoc network virtual backbone |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
| 点击此处可从《北京大学学报(自然科学版)》浏览原始摘要信息 |
|
点击此处可从《北京大学学报(自然科学版)》下载全文 |
