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.
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