An Efficient Heuristic for the Minimum Connected Dominating Set Problem on Ad Hoc Wireless Networks

Connected Dominating Set (CDS) problem in unit disk graph has significant impact on an efficient design of routing protocols in wireless sensor networks, where the searching space for a route is reduced to nodes in the set. A set is dominating if all the nodes in the system are either in the set or neighbors of nodes in the set. In this paper, a simple and efficient heuristic method is proposed for finding a Minimum Connected Dominating Set (MCDS) in ad hoc wireless networks based on the new parameter support of vertices. With this parameter the proposed heuristic approach effectively finds the MCDS of a graph. Extensive computational experiments show that the proposed approach outperforms the recently proposed heuristics found in the literature for the MCDS.