A Distributed Algorithm for the Dead End Problem of Location Based Routing in Sensor Networks

The dead end problem in greedy forwarding is an important issue of location based routing in sensor networks. It occurs when a message falls into a local minimum using greedy forwarding. Current solutions to this problem are insufficient in either eliminating traffic/path memorization or finding satisfactory short paths. In this paper, we propose a novel algorithm, called partial-partition avoiding geographic routing (PAGER), to solve the problem. The basic idea of PAGER is to divide a sensor network graph into functional subgraphs and provide each sensor node with message forwarding directions based on these subgraphs. PAGER results in loop free short paths without memorization of traffics/paths in sensor nodes. It does not require planarization of the underlying network graph. Further, the mobility adaptability of PAGER makes it suitable for use in mobile sensor networks with frequent topology changes. We implement the PAGER algorithm in two protocols and evaluate them in sensor networks with different parameters. Experimental results show the advantage of PAGER in the context of sensor networks.