Data Broadcasting Approximation Algorithms for Wireless Networks
B.Sujatha, S.Nagaprasad, G.Srinivasa Rao?
Journal Title:International Journal of Computer Science and Mobile Computing - IJCSMC
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.