Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/15900
Title: Extended multipoint relays to determine connected dominating sets in MANETs
Authors: Wu, J
Lou, W 
Dai, F
Keywords: Approximation ratio
Broadcasting
Connected dominating set (CDS)
Heuristic solutions
Mobile ad hoc networks (MANETS)
Multipoint relays (MPR)
Issue Date: 2006
Publisher: IEEE Computer Soc
Source: IEEE transactions on computers, 2006, v. 55, no. 3, p. 334-347 How to cite?
Journal: IEEE Transactions on Computers 
Abstract: Multipoint relays (MPR) [18] provide a localized and optimized way of broadcasting messages in a mobile ad hoc network (MANET). Using partial 2-hop information, each node chooses a small set of forward neighbors to relay messages and this set covers the node's 2-hop neighbor set. These selected forward nodes form a connected dominating set (CDS) to ensure full coverage. Adjih et al. [1] later proposed a novel extension of MPR to construct a small CDS and it is source-independent. In this paper, we provide several extensions to generate a smaller CDS using complete 2-hop information to cover each node's 2-hop neighbor set. We extend the notion of coverage in the original MPR. We prove that the extended MPR has a constant local approximation ratio compared with a logarithmic local ratio in the original MPR. In addition, we show that the extended MPR has a constant global probabilistic approximation ratio, while no such ratio exists in the original MPR and its existing extensions. The effectiveness of our approach is confirmed through a simulation study.
URI: http://hdl.handle.net/10397/15900
ISSN: 0018-9340
DOI: 10.1109/TC.2006.40
Appears in Collections:Journal/Magazine Article

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

SCOPUSTM   
Citations

85
Last Week
0
Last month
0
Citations as of Jan 14, 2017

WEB OF SCIENCETM
Citations

52
Last Week
0
Last month
0
Citations as of Jan 15, 2017

Page view(s)

16
Last Week
0
Last month
Checked on Jan 15, 2017

Google ScholarTM

Check

Altmetric



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