A Better Heuristic for the Minimum Connected Dominating Set in Ad Hoc Networks

Since no fixed infrastructure and no centralized management present in Wireless Ad Hoc Networks (WANETs), a Connected Dominating Set (CDS) representing the network is widely used as a virtual backbone. Given a graph, a CDS is a subset of vertices such that every vertex in the graph is either in the subset or adjacent to a vertex in the subset and the subgraph induced by the subset is connected. A smaller virtual backbone (a smaller size CDS) incurs less communication overhead. However, finding a minimum size CDS is NP-hard. Thus, it is important to design effective algorithms for the minimum CDS (MCDS) problem. In this article, a new efficient heuristic name as 2-Lenght Betweenness Heuristic for the MCDS problem is proposed. Comprehensive simulation results demonstrate that the proposed heuristic algorithm finds better solutions than the existing approach.