An Efficient Heuristic for the Minimum Connected Dominating Set Problem on Ad Hoc Wireless Networks
Source: SASTRA UNIVERSITY
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.