A probabilistic algorithm for efficient and robust data propagation in wireless sensor networks

We study the problem of data propagation in sensor networks, comprised of a large number of very small and low-cost nodes, capable of sensing, communicating and computing. The distributed co-operation of such nodes may lead to the accomplishment of large sensing tasks, having useful applications in practice. We present a new protocol for data propagation towards a control center ("sink") that avoids flooding by probabilistically favoring certain ("close to optimal") data transmissions. Motivated by certain applications (see [I.F. Akyildiz, W. Su, Y. Sankarasubramaniam, E. Cayirci, Wireless sensor networks: a survey, Journal of Computer Networks 38 (2002) 393-422], [C. Intanagonwiwat, R. Govindan, D. Estrin, Directed diffusion: a scalable and robust communication paradigm for sensor networks, in: 6th ACM/IEEE Annual International Conference on Mobile Computing (MOBICOM 2000), 2000, pp. 56-67]) and also as a starting point for a rigorous analysis, we study here lattice-shaped sensor networks. We however show that this lattice shape emerges even in randomly deployed sensor networks of sufficient sensor density. Our work is inspired and builds upon the directed diffusion paradigm of [C. Intanagonwiwat, R. Govindan, D. Estrin, Directed diffusion: a scalable and robust communication paradigm for sensor networks, in: 6th ACM/IEEE Annual International Conference on Mobile Computing (MOBICOM 2000), 2000, pp. 56-67]. This protocol is very simple to implement in sensor devices, uses only local information and operates under total absence of co-ordination between sensors. We consider a network model of randomly deployed sensors of sufficient density. As shown by a geometry analysis, the protocol is correct, since it always propagates data to the sink, under ideal network conditions (no failures). Using stochastic processes, we show that the protocol is very energy efficient. Also, when part of the network is inoperative, the protocol manages to propagate data very close to the sink, thus in this sense it is robust. We finally present and discuss large-scale simulation findings validating the analytical results. © 2005.