Title: An enhanced approach to determine connected dominating sets for routing in mobile ad hoc networks

Authors: Chunchun Ni, Hui Liu, Anu G. Bourgeois, Yi Pan

Addresses: Department of Computer Science, Georgia State University, Atlanta, GA 30303, USA. ' Department of Computer Science, Georgia State University, Atlanta, GA 30303, USA. ' Department of Computer Science, Georgia State University, Atlanta, GA 30303, USA. ' Department of Computer Science, Georgia State University, Atlanta, GA 30303, USA

Abstract: A mobile ad hoc network is a collection of wireless mobile nodes forming a temporary network without the support of any established infrastructure or centralised administration. Mobile ad hoc networks face a lot of challenges for designing a scalable routing protocol due to their natural characteristics. The idea of virtual backbone routing has been proposed for efficient routing in mobile ad hoc networks because virtual backbone routing can reduce communication overhead and speed up the routing process compared with many existing routing protocols. Up to now, Minimum Connected Dominating Set (MCDS) is the main method used to form a virtual backbone. However, finding an MCDS is an NP-hard problem. A distributed protocol for calculating the connected dominating set was proposed by Wu and Li. In this paper, we propose a further extension to reduce the size of the dominating set as compared to their method. We conduct extensive simulations on these two related algorithms. These simulation results show that our approach can consistently outperform Wu and Li|s method, particularly for a medium-density network. We discuss the tradeoff between cost and performance through theoretical analysis.

Keywords: mobile ad hoc networks; connected dominating set; routing protocol; mobile communications; wireless networks; virtual backbone routing; cost; performance.

DOI: 10.1504/IJMC.2005.006585

International Journal of Mobile Communications, 2005 Vol.3 No.3, pp.287 - 302

Published online: 22 Mar 2005 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article