Efficient algorithm for finding minimum connected dominating set in wireless sensor networks
传感器网络中高效的最小连通支配集求解算法

The Connected Dominating Set (CDS) has been widely used for efficient routing in wireless sensor networks. Although finding the Minimum Connected Dominating Set (MCDS) in an arbitrary graph is a NP-hard problem, many approximation algorithms have been proposed to construct a serviceable CDS. To address the weaknesses of these existing algorithms, we proposed a new distributed approximation algorithm, CDS-HG, to construct the CDS for wireless sensor networks. This algorithm models a wireless sensor network as a hierarchical graph, in which a competition-based greedy strategy is used to select nodes at a certain level to route messages to the next level. Formal analysis and simulation studies show that our proposed CDS-HG algorithm generates the smallest CDS while requiring the least message complexity.