Constructing Minimum Connected Dominating Set in Mobile Ad Hoc Networks

One of the most important challenges of a Mobile Ad Hoc Network (MANET) is to ensure efficient routing among its nodes. A Connected Dominating Set (CDS) is a widely used concept by many protocols for broadcasting and routing in MANETs. Those existing protocols require significant message overhead in construction of CDS. In this paper, we propose a simple, inexpensive and novel algorithm of computing a minimum CDS. The proposed algorithm saves time and message overhead in forming a CDS while supporting node mobility efficiently. Simulation results show that the proposed algorithm is efficient in terms of both message complexity and the size of the CDS.