Data Broadcasting Approximation Algorithms for Wireless Networks

In this paper, an algorithm for efficient network-wide broadcast (NWB) in mobile ad hoc networks (MANETs) is proposed. The algorithm is performed in an asynchronous and distributed manner by each network node. The algorithm requires only limited topology knowledge, and therefore, is suitable for reactive MANET routing protocols. Simulations show that the proposed algorithm is on average 3-4 times as efficient as brute force flooding. Further, simulations show that the proposed algorithm compares favorably over a wide range of network sizes, with a greedy algorithm using global topology knowledge, in terms of minimizing packet transmissions. The application of the algorithm to route discovery in on-demand routing protocols is discussed in detail. Proofs of the algorithm's reliability and of the intractability of solving for a minimum sized transmitter set to perform NWB are also given.