Khaled M. Alzoubi
ABSTRACT
A connected dominating set (CDS) for a graph G(V,E) is a subset V1 of V, such that each node in V--V1 is adjacent to some node in V1, and V1 induces a connected subgraph. A CDS has been proposed as a virtual backbone for routing in wireless ad hoc networks. However, it is NP-hard to find a minimum connected dominating set (MCDS). Approximation algorithms for MCDS have been proposed in the literature. Most of these algorithms suffer from a very poor approximation ratio, and from high time complexity and message complexity. Recently, new distributed heuristics for constructing a CDS were developed, with constant approximation ratio of 8. These new heuristics are based on a construction of a spanning tree, which makes it very costly in terms of communication overhead to maintain the CDS in the case of mobility and topology changes.In this paper, we propose the first distributed approximation algorithm to construct a MCDS for the unit-disk-graph with a emph constant approximation ratio, and emph linear time and emph linear message complexity. This algorithm is fully localized, and does not depend on the spanning tree. Thus, the maintenance of the CDS after changes of topology guarantees the maintenance of the same approximation ratio. In this algorithm each node requires knowledge of its single-hop neighbors, and only a constant number of two-hop and three-hop neighbors. The message length is O( log n) bits.
- K. M. Alzoubi, P.-J. Wan, O. Frieder, "Distributed Heuristics for Connected Dominating Set in Wireless Ad Hoc Networks", to appear in Journal on Communication Networks, 2002.Google Scholar
- V. Bharghavan and B. Das, "Routing in Ad Hoc Networks Using Minimum Connected Dominating Sets", International Conference on Communications'97, Montreal, Canada. June 1997.Google Scholar
- B. N. Clark, C. J. Colbourn, and D. S. Johnson, "Unit Disk Graphs", Discrete Mathematics, 86:165--177, 1990. Google ScholarDigital Library
- B. Das, R. Sivakumar, and V. Bhargavan, "Routing in Ad-Hoc Networks Using a Spine", International Conference on Computers and Communications Networks '97, Las Vegas, NV. September 1997. Google ScholarDigital Library
- R. Sivakumar, B. Das, and V. Bharghavan, "An Improved Spine-based Infrastructure for Routing in Ad Hoc Networks", IEEE Symposium on Computers and Communications '98, Athens, Greece. June 1998.Google Scholar
- I. Stojmenovic, M. Seddigh, J. Zunic, "Dominating sets and neighbor elimination based broadcasting algorithms in wireless networks", Proc. IEEE Hawaii Int. Conf. on System Sciences, January 2001. Google ScholarDigital Library
- P.-J. Wan, K. M. Alzoubi, O. Frieder, "Distributed Construction of Connected Dominating Set in Wireless Ad Hoc Networks", to appear in IEEE INFOCOM 2002.Google Scholar
- J. Wu and H. L. Li, "On calculating connected dominating set for efficient routing in ad hoc wireless networks", Proceedings of the 3rd ACM international workshop on discrete algorithms and methods for mobile computing and communications, 1999, Pages 7--14. Google ScholarDigital Library
Index Terms
- Message-optimal connected dominating sets in mobile ad hoc networks
Recommendations
An enhanced approach to determine connected dominating sets for routing in mobile ad hoc networks
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 ...
Connected Dominating Sets in Wireless Networks with Different Transmission Ranges
Since there is no fixed infrastructure or centralized management in wireless ad hoc networks, a Connected Dominating Set (CDS) has been proposed to serve as a virtual backbone. The CDS of a graph representing a network has a significant impact on the ...
Topology and mobility considerations in mobile ad hoc networks
A highly dynamic topology is a distinguishing feature and challenge of a mobile ad hoc network. Links between nodes are created and broken, as the nodes move within the network. This node mobility affects not only the source and/or destination, as in a ...
Comments