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.
Original language | English |
---|---|
Title of host publication | ICDCS 2010 - 2010 International Conference on Distributed Computing Systems |
Pages | 754-763 |
Number of pages | 10 |
DOIs | |
Publication status | Published - 27 Aug 2010 |
Event | 30th IEEE International Conference on Distributed Computing Systems, ICDCS 2010 - Genova, Italy Duration: 21 Jun 2010 → 25 Jun 2010 |
Conference
Conference | 30th IEEE International Conference on Distributed Computing Systems, ICDCS 2010 |
---|---|
Country/Territory | Italy |
City | Genova |
Period | 21/06/10 → 25/06/10 |
ASJC Scopus subject areas
- Software
- Hardware and Architecture
- Computer Networks and Communications