Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/12333
Title: Duty-cycle-aware minimum latency broadcast scheduling in multi-hop wireless networks
Authors: Jiao, X
Lou, W 
Ma, J
Cao, J 
Wang, X
Zhou, X
Issue Date: 2010
Source: Proceedings - International Conference on Distributed Computing Systems, 2010, 5541626, p. 754-763 How to cite?
Abstract: Broadcast is an essential and widely-used operation in multi-hop wireless networks. Minimum latency broadcast scheduling (MLBS) aims to provide 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-cycle-aware scenarios. In this paper, we investigate the duty-cycle-aware minimum latency broadcast scheduling (DCA-MLBS) problem in multi-hop wireless networks. We prove both the one-to-all and the all-to-all DCA-MLBS problems to be NP-hard. We propose a novel approximation algorithm called OTAB for the one-to-all DCA-MLBS problem, and two approximation algorithms called UTB and UNB for the all-to-all DCA-MLBS problem under the unit-size and the unbounded-size message models respectively. The OTAB algorithm achieves a constant approximation ratio of 17|T|, where |T| denotes the number of time-slots in a scheduling period. The UTB and UNB algorithms achieve the approximation ratios of 17|T|+20 and (Δ+22)|T| respectively, where Δ denotes the maximum node degree of the network. Extensive simulations are conducted to evaluate the performance of our algorithms.
Description: 30th IEEE International Conference on Distributed Computing Systems, ICDCS 2010, Genova, 21-25 June 2010
URI: http://hdl.handle.net/10397/12333
ISBN: 9780769540597
DOI: 10.1109/ICDCS.2010.20
Appears in Collections:Conference Paper

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

SCOPUSTM   
Citations

18
Last Week
1
Last month
0
Citations as of Jan 22, 2018

Page view(s)

66
Last Week
1
Last month
Citations as of Jan 21, 2018

Google ScholarTM

Check

Altmetric


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