Improved algorithm for broadcast scheduling of minimal latency in wireless ad hoc networks |
| |
Authors: | Wei-ping Shang Peng-jun Wan Xiao-dong Hu |
| |
Institution: | [1]Department of Mathematics, Zhengzhou University, Zhengzhou 450052, China [2]Department of Computer Science, Illinois Institute of Technology, Chicago, IL 60616, USA [3]Institute of Applied Mathematics, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100190, China |
| |
Abstract: | A wide range of applications for wireless ad hoc networks are time-critical and impose stringent requirement on the communication
latency. One of the key communication operations is to broadcast a message from a source node. This paper studies the minimum
latency broadcast scheduling problem in wireless ad hoc networks under collision-free transmission model. The previously best
known algorithm for this NP-hard problem produces a broadcast schedule whose latency is at least 648(r
max/r
min)2 times that of the optimal schedule, where r
max and r
min are the maximum and minimum transmission ranges of nodes in a network, respectively. We significantly improve this result
by proposing a new scheduling algorithm whose approximation performance ratio is at most (1 + 2r
max/r
min)2 + 32. Moreover, under the proposed scheduling each node just needs to forward a message at most once. |
| |
Keywords: | Broadcast latency wireless ad hoc networks approximation algorithm |
本文献已被 维普 SpringerLink 等数据库收录! |
|