Duty-cycle-aware minimum latency broadcast scheduling in multi-hop wireless networks

Xianlong Jiao, Wei Lou, Junchao Ma, Jiannong Cao, Xiaodong Wang, Xingming Zhou

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

26 Citations (Scopus)

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 languageEnglish
Title of host publicationICDCS 2010 - 2010 International Conference on Distributed Computing Systems
Pages754-763
Number of pages10
DOIs
Publication statusPublished - 27 Aug 2010
Event30th IEEE International Conference on Distributed Computing Systems, ICDCS 2010 - Genova, Italy
Duration: 21 Jun 201025 Jun 2010

Conference

Conference30th IEEE International Conference on Distributed Computing Systems, ICDCS 2010
Country/TerritoryItaly
CityGenova
Period21/06/1025/06/10

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications

Cite this