Wireless Sensor and Actuator Networks: Algorithms and Protocols for Scalable Coordination and Data Communication

4.4 MEMORIZATION-BASED GEOROUTING WITH GUARANTEED DELIVERY

Greedy based routing stops if a current node cannot find any neighbor that is making an advance with respect to the selected advance mechanism, such as reducing the distance to the destination. However, a route from source to destination may still exist. We consider only localized methods to find the route when the selected greedy technique fails. They are generally divided into two classes, depending on whether or not any information about the route has been left at visited nodes, for possible later consultation. This is not allowed in memoryless routing, where all needed information is included in the packet. We will first cover some techniques that do allow memorization. In some cases, memorization can be justified. One example is the creation of a path between two nodes that will be used for an ongoing traffic between them (e.g., for QoS-based applications), where nodes on the path need to memorize the next hop. The alternative is, obviously, to record the whole path in the message; but, with increased path lengths this method does not scale well, as increased message size increases collisions and reduces bandwidth. We will describe several recovery mechanisms based on memorization.

Stojmenovic and Lin (2001a) proposed flooding-based methods, called f-greedy and f-MFR, which apply greedy routing and MFR at intermediate nodes and run a recovery mechanism at concave nodes. Each concave node memorizes message IDs and rejects ...