On Greedy Construction of Connected Dominating Sets in Wireless Networks

Abstract

Since no fixed infrastructure and no centralized management present in wireless networks, a Connected Dominating Set (CDS) of the graph representing the network is widely used as the virtual backbone and plays an important role in the network. Constructing a minimum CDS is NP-hard. Many CDS construction algorithms have been designed. In this paper, we propose a new greedy algorithm, called S-MIS, with the help of Steiner tree that can construct a CDS within a factor of 4.8+ln5 from the optimal solution. We also introduce the distributed version of this algorithm. The theoretical proof shows that our algorithm is better than the current best performance ratio which is 6.8. A simulation is conducted to compare S-MIS with its variation which is rS-MIS. The simulation shows that the sizes of the CDSs generated by S-MIS and rS-MIS are almost the same.