Self-selecting reliable paths for wireless sensor network routing

Abstract

Routing protocols for wireless sensor networks face two challenges. One is an efficient bandwidth usage which requires minimum delay between transfers of packets. Establishing permanent routes from the source to destination addresses this challenge since the received packet can be immediately transmitted to the next node. However, any disruption on the established path either causes packet loss, lowering the delivery rate, or invokes a costly process of creating an alternative path. The second challenge is the ability to tolerate permanent and transient failures of nodes and links, especially since such failures are frequent in sensor networks. Protocols that chose the forwarding node at each hop of a packet are resilient to such failures, but incur the delay caused by selection of the forwarding node at each hop of the multi-hop path. This paper presents a novel wireless sensor routing protocol, self-selecting reliable path routing (SRP) for wireless sensor network (WSN) routing, that addresses both challenges at once. This protocol evolved from the self-selecting routing (SSR) protocol which is essentially memory-less. In the first generation of SSR protocols each packet selects the forwarding node at each hop on its path from the source to destination. The protocol takes advantage of broadcast communication commonly used in WSNs as a communication primitive. It also uses a prioritized transmission back-off delay to uniquely identify the neighbor of the forwarder that will forward the packet. As a result, the protocol is resistant to node or link failures as long as an alternative path exists from the current forwarder to the destination. The second generation of SSR protocols, called self-healing routing (SHR) added the route repair procedure, invoked when no neighbor of the forwarder closer to the destination is alive. In a series of transmissions, a packet trapped at the current forwarder by failures of its neighbors is capable of backing-off towards the source to find an alternative route, if such exists, to the destination. The main contribution of this paper is the third generation of SSR protocols, termed self-selecting reliable path routing, SRP. It preserves SHRs dynamic path selection in face of failure. Yet it also enables packets to follow established paths without selection delay if failures do not occur. The important change in the protocol is to make it memorize the successfully traversed path and attempt to reuse it for subsequent packets flowing to the same destination. The interesting behavior of SRP arising from this property is that if a path from the source to destination exists on which no transient failures occur, SRP would converge its routing to such a reliable path. In the paper, we describe novel elements of the SRP protocol that resulted in the desired properties. Using simulation, we compare SRP protocol with the representatives of the two other approaches: AODV as the route-based protocol, and GRAB and SHR as the hop-selection protocols. © 2008 Elsevier B.V.