A constant–factor approximation for d–hop connected dominating sets in unit disk graph. (27th November 2012)

• Record Type: Journal Article
• Authors: Gao, Xiaofeng; Wu, Weili; Zhang, Xuefei; Li, Xianyue
• Is Part Of: International journal of sensor networks. Volume 12:Number 3(2012)
• Page Start: 125
• Page End: 136
• Publication Date: 2012-11-27
• Subjects: WSNs -- wireless sensor networks -- d–hop -- CDS -- connected dominating set -- unit disk graph -- wireless networks -- distributed routing protocols; Sensor networks -- Periodicals; 681.2
• Languages: English
• ISSNs: 1748-1279

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.