Generating Minimum Connected Dominating Set in Mobile Ad Hoc Networks

摘要

It is very important to find an efficient routing scheme among the nodes in a Mobile Ad Hoc Network (MANET). We propose a simple and efficient algorithm for computing a minimum Connected Dominating Set (CDS) with no neighbor information at each node to begin with. As a result, the proposed algorithm saves time and message overhead in forming a CDS. Simulation results show that the proposed algorithm is efficient in terms of both message complexity and the size of the CDS.