Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/11966
Title: An improved distributed algorithm for connected dominating sets in wireless ad hoc networks
Authors: Liu, H
Pan, Y
Cao, J 
Issue Date: 2004
Publisher: Springer
Source: Lecture notes in computer science (including subseries Lecture notes in artificial intelligence and lecture notes in bioinformatics), 2004, v. 3358, p. 340-351 How to cite?
Journal: Lecture notes in computer science (including subseries Lecture notes in artificial intelligence and lecture notes in bioinformatics) 
Abstract: The idea of virtual backbone routing has been proposed for efficient routing among a set of mobile nodes in wireless ad hoc networks. Virtual backbone routing can reduce communication overhead and speedup the routing process compared with many existing on-demand routing protocols for routing detection. In many studies, Minimum Connected Dominating Set (MCDS) is used to approximate virtual backbones in a unit-disk graph. However finding a MCDS is a NP-hard problem. We propose a distributed, 3-phase protocol for calculating the CDS in this paper. Our new protocol largely reduces the number of nodes in CDS compared with Wu and Li's method, while message and time complexities of our approach remain almost the same as those of Wu and Li's method. We conduct extensive simulations and show our protocol can consistently outperform Wu and Li's method. The correctness of our protocol is proved through theoretical analysis.
URI: http://hdl.handle.net/10397/11966
ISSN: 0302-9743
EISSN: 1611-3349
Appears in Collections:Conference Paper

Access
View full-text via PolyU eLinks SFX Query
Show full item record

SCOPUSTM   
Citations

2
Citations as of May 16, 2017

WEB OF SCIENCETM
Citations

5
Last Week
0
Last month
0
Citations as of Aug 14, 2017

Page view(s)

41
Last Week
3
Last month
Checked on Aug 13, 2017

Google ScholarTM

Check



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.