Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/16532
Title: Minimum-transmission broadcast in uncoordinated duty-cycled wireless Ad Hoc networks
Authors: Hong, J
Cao, J 
Li, W
Lu, S
Chen, D
Keywords: Approximation algorithm
Duty cycle
Minimum-transmission broadcast (MTB)
NP hard
Wireless ad hoc network (WANET)
Issue Date: 2010
Publisher: Institute of Electrical and Electronics Engineers
Source: IEEE transactions on vehicular technology, 2010, v. 59, no. 1, 5204235, p. 307-318 How to cite?
Journal: IEEE transactions on vehicular technology 
Abstract: Broadcast is a fundamental operation of wireless ad hoc networks (WANETs) and has widely been studied over the past few decades. However, most existing broadcasting strategies assume nonsleeping wireless nodes and thus are not suitable for uncoordinated duty-cycled WANETs, in which each node periodically switches on and off to save energy. In this paper, we study the minimum-transmission broadcast problem in uncoordinated duty-cycled WANETs (MTB-UD problem) and prove its NP-hardness. We show that modifications of existing broadcast approaches can only provide a linear approximation ratio of O(n) (where n is the number of nodes in the network). We propose a novel set-cover-based approximation (SCA) scheme with both centralized and distributed approximation algorithms. The centralized SCA (CSCA) algorithm has a logarithmic approximation ratio of 3(ln Δ + 1) and time complexity of O(n3) (Δ is the maximum degree of the network). The distributed SCA (DSCA) algorithm has a constant approximation ratio of at most 20 while keeping both linear time and message complexities. We have conducted both theoretical analysis and simulations to evaluate the performance of the proposed algorithms. Results show that both the CSCA and DSCA algorithms outperform the modified versions of existing broadcast approaches by at least 50%.
URI: http://hdl.handle.net/10397/16532
ISSN: 0018-9545
EISSN: 1939-9359
DOI: 10.1109/TVT.2009.2030203
Appears in Collections:Journal/Magazine Article

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

SCOPUSTM   
Citations

28
Last Week
0
Last month
1
Citations as of Aug 13, 2017

WEB OF SCIENCETM
Citations

18
Last Week
0
Last month
3
Citations as of Aug 14, 2017

Page view(s)

29
Last Week
1
Last month
Checked on Aug 13, 2017

Google ScholarTM

Check

Altmetric



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