Please use this identifier to cite or link to this item:
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
ISBN: 9780769540597
DOI: 10.1109/ICDCS.2010.20
Appears in Collections:Conference Paper

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


Last Week
Last month
Citations as of Jun 5, 2018

Page view(s)

Last Week
Last month
Citations as of Jun 18, 2018

Google ScholarTM



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