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
Author(s)
Related Research Unit(s)
Detail(s)
| Original language | English |
|---|---|
| Title of host publication | Proceedings - IEEE INFOCOM |
| Pages | 733-739 |
| Publication status | Published - 2007 |
Publication series
| Name | |
|---|---|
| ISSN (Print) | 0743-166X |
Conference
| Title | IEEE INFOCOM 2007: 26th IEEE International Conference on Computer Communications |
|---|---|
| Place | United States |
| City | Anchorage, AK |
| Period | 6 - 12 May 2007 |
Link(s)
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 et al.
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
