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

4.5 GUARANTEED DELIVERY WITHOUT MEMORIZATION

4.5.1 Face Routing in Planar Geometric Graphs

A planar graph is a graph that can be drawn on the plane in such a way that edges intersect only at their end points. Figure 4.6 shows a planar graph. In geometric graphs, each node is aware of its position and those of its neighbors, and therefore angles toward them. Examples of planar and geometric graphs include street maps, or rooms on the same floor in a building. Planar geometric graphs divide graph into faces. In the example in Figure 4.6, face F₁ is polygon SABC and face F₂ is polygon BEFGHC. Kranakis et al. (1999) described the first localized memoryless routing algorithm for planar geometric graphs, which guarantees delivery whenever the source and destination are connected.

The face routing in Bose et al. (1999) is an improvement on the routing algorithm in Kranakis et al. (1999). The main idea of the face routing (Bose et al., 1999) is to advance (toward destination D) intersections of faces with a straight line segment that connects the last intersection X (initially it is the source S) and the destination D. A packet is routed along the interiors of the faces until an edge on the route intersects XD between X and D. In Figure 4.6, the line intersects the planar graph with faces F₁, F₂, …, F₇. The boundary of any face can be traversed by applying the right-hand rule (counterclockwise traversal) or the left-hand rule (clockwise traversal). In the right-hand rule, the face is traversed ...