论文部分内容阅读
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.
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. previously previously 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.