Research Article
Connected D-Hop Dominating Sets in Mobile Ad Hoc Networks
@INPROCEEDINGS{10.1109/WIOPT.2006.1666454, author={Trac N. Nguyen and Dung T. Huynh}, title={Connected D-Hop Dominating Sets in Mobile Ad Hoc Networks}, proceedings={4th International ICST Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks}, publisher={IEEE}, proceedings_a={WIOPT}, year={2006}, month={8}, keywords={cluster mobile ad hoc network dominating set NP-completeness I}, doi={10.1109/WIOPT.2006.1666454} }- Trac N. Nguyen
Dung T. Huynh
Year: 2006
Connected D-Hop Dominating Sets in Mobile Ad Hoc Networks
WIOPT
IEEE
DOI: 10.1109/WIOPT.2006.1666454
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.