Lukewarm Potato Forwarding: A Biased Random Walk Routing Protocol for Wireless Sensor Networks

Low latency data delivery is an important requirement for achieving effective monitoring through wireless sensor networks. When sensor nodes employ duty cycling, sending a message along the shortest path, however, does not necessarily result in minimum delay. In this paper we firstly study the lowest latency path problem, i.e., the characteristics of path with minim delay that connect a source node to the sink under random duty cycling nodes. Then, we propose a forwarding protocol based on biased random walks, where nodes only use local information about neighbors and their next active period to make forwarding decisions. We refer to this as lukewarm potato forwarding. Our analytical model and simulation experiments show that it is possible to reduce path latency without significantly increasing the number of transmissions (energy efficiency) needed to deliver the message to the destination. Additionally, the proposed solution is tunable. By changing the value of just one threshold parameter it can be tuned to operate anywhere in the continuum from hot potato/random walk forwarding protocol to a deterministic shortest path forwarding protocol. © 2009 IEEE.