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

4.2 GREEDY, PROJECTION, AND DIRECTION-BASED ROUTING

The simplest form of geographic routing is greedy routing which was first described by Finn (1987). In the greedy routing algorithm, each node in the route forwards packets to the neighbor that is the closest to the destination among its neighbors. Only the neighbors that are closer to the destination than the current node are considered. The algorithm is illustrated in Figure 4.1. Suppose node S is the current node in the route and node D is the destination. All neighbors of S are within the circle centered at S. Suppose node B is the closest to destination D among all S's neighbors and d is the distance between B and D. According to the greedy routing algorithm, node S selects node B as the next hop forwarding node. Greedy routing is suitable for large-scale networks with high density and frequent topology changes because it is simple and localized. The distance to the destination is minimized in each hop of the routing. The GEDIR (Stojmenovic and Lin, 2001a) algorithm is a variant of greedy routing. It considers all neighbors (even in backward direction) and selects the node that is the closest to the destination. A message is dropped if it would be sent back to the node where it was previously received from. Another variant is to select the nearest neighbor among those that are closer to the destination than the current node [nearest closer (NC) method, proposed in Stojmenovic and Lin (2001b).

Figure 4.1 Greedy, projection, ...