Approximation Algorithms for Data Broadcast in Wireless Networks

Broadcasting is a fundamental operation in wireless networks and plays an important role in the communication protocol design. In multihop wireless networks, however, interference at a node due to simultaneous transmissions from its neighbors makes it non-trivial to design a minimum-latency broadcast algorithm, which is known to be NP-complete. This paper presents a simple 12-approximation algorithm for the one-to-all broadcast problem that improves all previously known guarantees for this problem.