A New Greedy Algorithm for Constructing the Minimum Size Connected Dominating Sets in Wireless Networks

摘要

Finding the Minimum-size Connected Dominating Set (MCDS), i.e., the communication backbone with the minimum number of nodes is a key problem in wireless networks, which is crucial for designing efficient routing algorithms and for network energy efficiency etc. This paper proposes a new greedy algorithm to approach the MCDS problem. The key idea is to separate nodes in CDS into core nodes and supporting nodes. The core nodes dominate the supporting nodes in CDS, while the supporting nodes dominate other nodes that are not in CDS. The proposed algorithm is verified by simulation, the simulation results show that the CDS constructed by our algorithm has smaller size than the state of the art algorithms in [10].