A constant-factor approximation for d-hop connected dominating sets in unit disk graph
Xiaofeng Gao, Weili Wu, Xuefei Zhang, Xianyue Li · International Journal of Sensor Networks · 2012
This paper presents a new distributed constant–factor approximation to compute d–CDS in Unit Disk Graph with low time complexity. We firstly propose an algorithm for a special case of d=2, namely Two–Hop Connected Dominating Set (TCDS or 2–CDS) with three phases: collecting information for each node; computing a Two–hop Maximal Independent Set (2–MIS); and connecting the selected set. The whole algorithm has approximation ratio 17.421opt + 51.456, where opt is the number of nodes in an optimal 2–CDS set. Next we generalise this algorithm for d–CDS with arbitrary integer d. The generalisation also has a constant–factor approximation ratio (0.335 r³ + 1.337 r² + 0.585 r)opt + (3.338 r³ + 0.5 r² - 0.585 r), where r = d + 0.5. We then compare our algorithm (d = 2) with two classical distributed routing protocols by numerical experiments, proving the efficiency of our design.