Open Access Open Access  Restricted Access Subscription Access

GRAB: Greedy Forwarding with Routing Along Boundaries in Wireless Sensor Networks

Rajesh Sharma, Lalit Kumar Awasthi, Naveen Chauhan


Geographic routing has emerged as one of the most suitable strategies for routing in Wireless Sensor Networks (WSNs). Greedy forwarding is a simpler and efficient form of geographic routing in which a packet is successively forwarded to a neighboring node that makes maximum positive progress towards the destination. However, in the presence of communication voids, greedy forwarding may fail at some dead-end – a node that does not have any optimal neighbor for greedy forwarding. Geographic routing methods proposed in literature mainly differ in the criteria adopted for the notion of progress, and the method used to handle dead-ends. The dead-end situation is usually handled by switching to some other supplementary routing methods like flooding, backtracking, perimeter routing, or face routing. Various schemes for handling void regions are either too inefficient or make unrealistic assumptions like Unit Disk Graph (UDG) model of connectivity. We present a novel routing algorithm “Greedy forwarding with Routing Along Boundaries” (GRAB) that combines greedy forwarding with a robust recovery scheme called rolling circle algorithm (RCA) for routing packets along the boundary of a dead-end region until a greedily routable region (GRR) is encountered, where the greedy forwarding resumes. The proposed technique is based on the actual connectivity graph and geographic locations of the nodes. The scheme does not assume UDG model for node transmission ranges, and does not require graph planarization.

Full Text: