基于连通支配集的虚拟骨干网构造算法

摘要：

针对无线传感器网络中缺少骨干网络的问题,提出一种基于连通支配集的虚拟骨干网构造算法.该算法利用图论中的极大独立集和连通支配集构造一个虚拟骨干网络,运用修剪规则去除冗余节点,通过优先选择能量多、距离近的节点使网络寿命更长、延迟更小.实验结果表明,该算法在单位圆图中产生的连通支配集至多为7.6opt+1.4,消息复杂度和时间复杂度为O(n).

关键词：无线传感器网络、虚拟骨干网、极大独立集、连通支配集

所属期刊栏目：37

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

资助基金：国家自然科学基金资助项目60803122,60903130

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

页数：共3页

页码：116-118