Minimum-latency broadcast scheduling in wireless ad hoc networks

Research output: Chapters, Conference Papers, Creative and Literary Works (RGC: 12, 32, 41, 45)32_Refereed conference paper (with ISBN/ISSN)peer-review

101 Scopus Citations
View graph of relations

Author(s)

  • Scott C.-H. Huang
  • Peng-Jun Wan
  • Xiaohua Jia
  • Hongwei Du
  • Weiping Shang

Related Research Unit(s)

Detail(s)

Original languageEnglish
Title of host publicationProceedings - IEEE INFOCOM
Pages733-739
Publication statusPublished - 2007

Publication series

Name
ISSN (Print)0743-166X

Conference

TitleIEEE INFOCOM 2007: 26th IEEE International Conference on Computer Communications
PlaceUnited States
CityAnchorage, AK
Period6 - 12 May 2007

Abstract

A wide range of applications for wireless ad hoc networks are time-critical and impose stringent requirement on the communication latency. This paper studies the problem Minimum-Latency Broadcast Scheduling (MLBS) in wireless ad hoc networks represented by unit-disk graphs. This problem is NP-hard. A trivial lower bound on the minimum broadcast latency is the radius R of the network with respect to the source of the broadcast, which is the maximum distance of all the nodes from the source of the broadcast. The previously best-known approximation algorithm for MLBS produces a broadcast schedule with latency at most 648R. In this paper, we present three progressively improved approximation algorithms for MLBS. They produce broadcast schedules with latency at most 24R - 23, 16R - 15, and R +O (log R) respectively. © 2007 IEEE.

Citation Format(s)

Minimum-latency broadcast scheduling in wireless ad hoc networks. / Huang, Scott C.-H.; Wan, Peng-Jun; Jia, Xiaohua; Du, Hongwei; Shang, Weiping.

Proceedings - IEEE INFOCOM. 2007. p. 733-739 4215673.

Research output: Chapters, Conference Papers, Creative and Literary Works (RGC: 12, 32, 41, 45)32_Refereed conference paper (with ISBN/ISSN)peer-review