Reducing Broadcast Redundancy in Wireless Ad Hoc Networks

Reducing the number of redundant transmissions is one of the main objectives of efficient broadcast algorithms for wireless ad hoc networks. There are many localized broadcast algorithms proposed to reduce the number of transmissions. However, they do not guarantee a reasonable bound on the number of transmissions in the worst case. In fact, the common belief is that localized broadcast algorithms are not able to guarantee both full delivery and a good bound on the number of transmissions. In this paper, we propose the first localized broadcast algorithm that guarantees full delivery and a constant approximation ratio to the minimum number of required transmissions in the worst case. The proposed broadcast algorithm is a self-pruning algorithm based on 1-hop neighbor information. Our experimental results confirm the analytical analysis of the algorithm and show a significant reduction in the number of transmissions and end-to-end latency compared to one of the best broadcast algorithms based on 1-hop neighbor information.