Title: A distributed algorithm for computing Connected Dominating Set in ad hoc networks

Authors: Chuanhe Huang, Chuan Qin, Yi Xian

Addresses: Computer School, Wuhan University, China. ' Computer Science and Engineering Department, University of South Carolina, USA. ' Computer Science and Engineering Department, University of South Carolina, USA

Abstract: CDS (Connected Dominating Set) can be used as a backbone for efficient communications in ad hoc and wireless sensor networks. It is an NP-hard problem to find a Minimum Connected Dominating Set (MCDS) for a given graph. This paper proposes a distributed approximation algorithm to compute MCDS. The algorithm consists of three phases, and there is no strict boundary between any two consecutive phases. The algorithm has a constant approximation factor of 12, and message complexity O(max (n, opt × log opt)). The simulation result proves the effectiveness and reveals that this algorithm can perform even better as the density of network increases.

Keywords: ad hoc networks; routing algorithms; virtual backbone; connected dominating set; CDS; wireless sensor networks; wireless networks; simulation; distributed algorithms.

DOI: 10.1504/IJWMC.2006.012474

International Journal of Wireless and Mobile Computing, 2006 Vol.1 No.2, pp.148 - 155

Published online: 16 Feb 2007 *

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