Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/19225
Title: Minimum latency broadcast scheduling in duty-cycled multihop wireless networks
Authors: Jiao, X
Lou, W 
Ma, J
Cao, J 
Wang, X
Zhou, X
Keywords: Approximation algorithms
Broadcast scheduling
Duty cycle
Multihop wireless networks
Issue Date: 2012
Publisher: Institute of Electrical and Electronics Engineers
Source: IEEE transactions on parallel and distributed systems, 2012, v. 23, no. 1, 5740867, p. 110-117 How to cite?
Journal: IEEE transactions on parallel and distributed systems 
Abstract: Broadcast is an essential and widely used operation in multihop wireless networks. Minimum latency broadcast scheduling (MLBS) aims to find a collision-free scheduling for broadcast with the minimum latency. Previous work on MLBS mostly assumes that nodes are always active, and, thus, is not suitable for duty-cycled scenarios. In this paper, we investigate the MLBS problem in duty-cycled multihop wireless networks (MLBSDC problem). We prove both the one-to-all and the all-to-all MLBSDC problems to be NP-hard. We propose a novel approximation algorithm called OTAB for the one-to-all MLBSDC problem, and two approximation algorithms called UTB and UNB for the all-to-all MLBSDC problem under the unit-size and the unbounded-size message models, respectively. The approximation ratios of the OTAB, UTB, and UNB algorithms are at most 17|T|, 17|T|+20, and (Δ +22)|T|, respectively, where |T| denotes the number of time slots in a scheduling period, and Δ denotes the maximum node degree of the network. The overhead of our algorithms is at most constant times as large as the minimum overhead in terms of the total number of transmissions. We also devise a method called Prune to further reduce the overhead of our algorithms. Extensive simulations are conducted to evaluate the performance of our algorithms.
URI: http://hdl.handle.net/10397/19225
ISSN: 1045-9219
EISSN: 1558-2183
DOI: 10.1109/TPDS.2011.106
Appears in Collections:Journal/Magazine Article

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

SCOPUSTM   
Citations

41
Last Week
2
Last month
2
Citations as of Sep 25, 2017

WEB OF SCIENCETM
Citations

30
Last Week
0
Last month
0
Citations as of Sep 22, 2017

Page view(s)

30
Last Week
1
Last month
Checked on Sep 24, 2017

Google ScholarTM

Check

Altmetric



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