Abstract: Connected dominating set is very important in Wireless Sensor Networks(WSN) as a virtual backbone for communication and routing between nodes. This paper proposes a nodes’ neighborhood based algorithm to construct a Minimum Connected Dominating Set(MCDS) in WSN. The complexities of time and message are O(nlogn) and O(n), respectively. Regarding to the topological changes due to power constraint, it presents a repair algorithm to reconstruct the MCDS. Theoretical analysis and simulations both demonstrate the correctness and performance of the algorithm.

Key words: Wireless Sensor Network(WSN), Minimum Connected Dominating Set(MCDS), Steiner tree, closed neighborhood

摘要：

针对连通控制集在无线传感器网络中的重要作用，提出一种基于节点邻居关系的最小连通控制集(MCDS)的构造算法，该算法时间和信息复杂度分别为O(nlogn)和O(n)，且针对由于节点电池的耗尽等原因造成的网络拓扑改变的情况，提出一种局部的修复算法以得到新网络的一个MCDS。理论分析和仿真实验都表明了算法的正确性以及执行性能。

关键词: 无线传感器网络, 最小连通控制集, Steiner树, 闭邻居

CLC Number: 

• TP393