Algorithmic Aspects for Total Connected Dominating Sets in Mobile Ad Hoc Wireless Networks

A Total connected dominating set (TCDS) for a graph G(V,E) is a subset V'of V , such that each node in V−V' is adjacent to some node in V' and V' induces a connected subgraph. A TCDS 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 TCDS 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 TCDS in the case of mobility and topology changes. Investigating the algorithmic complexity of total domination for wireless ad hoc network as relevant open question .An O(n^2) algorithm has been proposed for this problem by Bertossi [1].Keil [10] proposed an O(n+m) In this paper, we propose the first distributed approximation algorithm to construct a MCDS for the unit-disk-graph with a constant approximation ratio O(n), and linear time and linear message complexity. This algorithm is fully localized, and does not depend on the spanning tree. Thus, the maintenance of the TCDS 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.