Title :
Connected D-Hop Dominating Sets in Mobile Ad Hoc Networks
Author :
Nguyen, Trac N. ; Huynh, Dung T.
Author_Institution :
Department of Computer Science, University of Texas at Dallas, Richardson, Texas 75083-0688, E-mail: nguyentn@utdallas.edu
Abstract :
A mobile ad hoc network may be logically represented as a set of clusters, and the clusterheads form what is known as a dominating set in graph theory. The clusterheads can be used to perform a variety of functions for nodes in their cluster such as channel access, routing, data collection, broadcasting, etc. There have been several heuristics proposed for forming 1-hop as well as d-hop clusters. In d-hop clustering, the value of d, a constant representing the number of wireless hops in ad hoc networks, is a parameter of the heuristic and controls the size of the clusters. The problem of finding a minimum d-hop connected dominating set was shown to be NP-complete in [9], where the authors raised the question of whether the problem is still NP-complete for the restricted model of unit disk graphs. In this paper, we provide an affirmative answer to this open question. In fact, we show that the minimum d-hop connected dominating set problem is NP-complete for planar unit disk graphs with maximum degree 4. We also review some known 1-hop heuristics that we generalize to the d-hop case and compare their performance. The experimental results show that the algorithm proposed in [9] is the most efficient one.
Keywords :
NP-completeness; cluster; dominating set; mobile ad hoc network; Ad hoc networks; Clustering algorithms; Computer science; Electronic mail; Graph theory; Intelligent networks; Mobile ad hoc networks; Nominations and elections; Routing; Spine; NP-completeness; cluster; dominating set; mobile ad hoc network;
Conference_Titel :
Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks, 2006 4th International Symposium on
Print_ISBN :
0-7803-9549-2
DOI :
10.1109/WIOPT.2006.1666454