A constant-factor approximation for d-hop connected dominating sets in unit disk graph

摘要

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.421 opt + 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~3 + 1.337 r~2 +0.585 r)opt+ (3.338 r~3 + 0.5 r~2 - 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.