An Efficient Distributed Flooding Scheme Using One-Hop Information in Heterogeneous Ad Hoc Networks

Flooding is one of the most fundamental operations in wireless ad hoc networks. In this paper, we study the sufficient and necessary condition of efficient flooding schemes based on only one-hop out-neighbors' information in heterogeneous ad hoc networks. We further propose an efficient flooding algorithm using one-hop out-neighbors' information that achieves the local optimality: (1) the number of forwarding nodes in each step is minimal; (2) the time complexity of computing forwarding nodes is the lowest, which is, where n is the number of out-neighbors of a node. Extensive simulations have shown the good performance of our algorithm.