基于拓扑特性的分布式虚拟骨干网算法

摘要：

由于在任意连通网络中搜索最小连通支配集(minimum connected domination set,简称MCDS)是NP完全问题,提出了一种拓扑感知的MCDS启发式算法--TACDS(topology-aware connected domination set),并证明了其正确性.通过利用节点的拓扑特性,减小了支配节点选择的盲目性.该算法能够根据2跳内的局部拓扑信息构造出较小的CDS(connected domination set),从而得到基于该支配集的虚拟骨干网.仿真结果表明,该算法优于其他分布式CDS算法,可以更好地近似MCDS.

关键词：无线网络、虚拟骨干网、连通支配集、分布式算法、拓扑特性

所属期刊栏目：21

分类号：TP393(计算技术、计算机技术)

在线出版日期：2010-08-30（万方平台首次上网日期，不代表论文的发表时间）

页数：共10页

页码：1416-1425