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

Authors: Xiaofeng Gao; Weili Wu; Xuefei Zhang; Xianyue Li

Addresses: Department of Computer Science and Engineering, Shanghai Jiao Tong University, Shanghai 200240, China. ' Department of Computer Science, University of Texas at Dallas, Richardson, TX 75080, USA. ' Department of Computer Science, University of Texas at Dallas, Richardson, TX 75080, USA. ' School of Mathematics and Statistics, Lanzhou University, Lanzhou 730000, China

Abstract: 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.

Keywords: WSNs; wireless sensor networks; d-hop; CDS; connected dominating set; unit disk graph; wireless networks; distributed routing protocols.

DOI: 10.1504/IJSNET.2012.050447

International Journal of Sensor Networks, 2012 Vol.12 No.3, pp.125 - 136

Received: 02 Dec 2011
Accepted: 23 Apr 2012
Published online: 23 Nov 2012 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article