%0 Journal Article
%T Constructing Minimum Connected Dominating Set in Mobile Ad Hoc Networks
%A Mallikarjun Avula
%A Seong-Moo Yoo
%A Seungjin Park
%J International Journal on Applications of Graph Theory in Wireless ad hoc Networks and Sensor Networks
%D 2012
%I Academy & Industry Research Collaboration Center (AIRCC)
%X 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.
%K Connected dominating set
%K mobile ad hoc network
%K message overhead
%K node mobility
%U http://airccse.org/journal/graphhoc/papers/4312jgraph02.pdf