Open AccessOn greedy construction of connected dominating sets in wireless networks
Author(s) -
Li Yingshu,
Thai My T.,
Wang Feng,
Yi ChihWei,
Wan PengJun,
Du DingZhu
Publication year - 2005
Publication title -
wireless communications and mobile computing
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.42
H-Index - 64
eISSN - 1530-8677
pISSN - 1530-8669
DOI - 10.1002/wcm.356
Subject(s) - computer science , connected dominating set , greedy algorithm , construct (python library) , steiner tree problem , graph , wireless network , set (abstract data type) , computer network , dominating set , distributed computing , wireless , tree (set theory) , algorithm , theoretical computer science , mathematical optimization , telecommunications , mathematics , combinatorics , vertex (graph theory) , programming language
Since no fixed infrastructure and no centralized management present in wireless networks, a connected dominating set (CDS) of the graph representing the network is widely used as a virtual backbone . Constructing a minimum CDS is NP‐hard. In this paper, we propose a new greedy algorithm, called S‐MIS, with the help of Steiner tree that can construct a CDS within a factor of 4.8 + ln5 from the optimal solution. We also introduce the distributed version of this algorithm. We prove that the proposed algorithm is better than the current best performance ratio which is 6.8. A simulation is conducted to compare S‐MIS with its variation which is rS‐MIS. The simulation shows that the sizes of the CDSs generated by S‐MIS and rS‐MIS are almost the same. Copyright © 2005 John Wiley & Sons, Ltd.