On the efficiency of routing in sensor networks

Numerous routing algorithms for sensor networks have been proposed and their efficiencies have been evaluated through extensive simulations. It comes out that the length of paths used to route messages are close to the length l between the source and the destination but most of the time, no theoretical results explain this efficiency. In this paper, we prove a generic result that can be used for this purpose. We then provide an algorithm which finds paths of constant stretch with high probability