TY - GEN
T1 - Minimum-latency broadcast scheduling in wireless ad hoc networks
AU - Huang, Scott C.-H.
AU - Wan, Peng-Jun
AU - Jia, Xiaohua
AU - Du, Hongwei
AU - Shang, Weiping
PY - 2007
Y1 - 2007
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=34548322734&partnerID=8YFLogxK
UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-34548322734&origin=recordpage
U2 - 10.1109/INFCOM.2007.91
DO - 10.1109/INFCOM.2007.91
M3 - RGC 32 - Refereed conference paper (with host publication)
SN - 1424410479
SN - 9781424410477
SP - 733
EP - 739
BT - Proceedings - IEEE INFOCOM
T2 - IEEE INFOCOM 2007: 26th IEEE International Conference on Computer Communications
Y2 - 6 May 2007 through 12 May 2007
ER -