Title: On greedy construction of connected dominating sets in wireless networks
Authors: Li, YS
Thai, MT
Wang, F
Yi, CW
Wan, PJ
Du, DZ
資訊工程學系
Department of Computer Science
Keywords: wireless network;connected dominating set;maximal independent set;greedy algorithm
Issue Date: 1-Dec-2005
Abstract: 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 (c) 2005 John Wiley & Sons, Ltd.
URI: http://dx.doi.org/10.1002/wcm.356
http://hdl.handle.net/11536/12991
ISSN: 1530-8669
DOI: 10.1002/wcm.356
Journal: WIRELESS COMMUNICATIONS & MOBILE COMPUTING
Volume: 5
Issue: 8
Begin Page: 927
End Page: 932
Appears in Collections:Articles


Files in This Item:

  1. 000233999000006.pdf

If it is a zip file, please download the file and unzip it, then open index.html in a browser to view the full text content.