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

Virtual Backbone Network Construction Algorithm Based on Connected Dominating Set

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

Aiming at the problem of the lack of a backbone network in Wireless Sensor Network（WSN）, this paper proposes a virtual backbone network construction algorithm based on connected dominating set. The algorithm uses the maximal independent set and the connected dominating set of graph theory to construct a virtual backbone network, and uses the pruning rule to remove redundant nodes. The algorithm preferably selects more energy and closer nodes, which makes the network life longer and the delay smaller. Experimental result shows that in unit disk graphs the connected dominating set generated by the algorithm is at most 7.6opt＋1.4, and the message complexity and time complexity are O（n）.