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 routingamong its nodes. A Connected Dominating Set (CDS) is a widely used concept by many protocols forbroadcasting and routing in MANETs. Those existing protocols require significant message overhead inconstruction of CDS. In this paper, we propose a simple, inexpensive and novel algorithm of computing aminimum CDS. The proposed algorithm saves time and message overhead in forming a CDS whilesupporting node mobility efficiently. Simulation results show that the proposed algorithm is efficient interms of both message complexity and the size of the CDS.