A Low-Cost Flooding Algorithm for Wireless Sensor Networks

Flooding methods have been widely used by routing protocols to disseminate route information and control messages in wireless ad hoc and sensor networks both. However, most of the efficient flooding approaches proposed in the research literature are designed for ad hoc networks only, and they might not be suitable for wireless sensor networks due to their higher node densities, constrained energy and memory resources in sensor nodes. In this paper, we present a distributed low-cost flooding algorithm that is designed particularly for wireless sensor networks. We prove that our new algorithm has O(n + Delta) time and O(n) signaling message complexity, where n is the total number of nodes in a network and Delta is the maximum node degree. Moreover, we show that our low-cost algorithm has a constant approximation ratio, and its signaling message size is also bounded by a constant. Our simulation study demonstrates that our new algorithm not only generates fewer forwarding nodes, but it also uses much less number of signaling messages and has significantly smaller signaling message size than other algorithms published in the literature.