GOAL: A parsimonious geographic routing protocol for large scale sensor networks

Geographic routing is well suited for large scale sensor networks, because its per node state is independent of the network size. However, the local minimum caused by holes/obstacles results in the worst-case path stretch of Ω(c2), where c is the path length of the optimal route. Recently, a geographic routing protocol based on the visibility graph (VIGOR) showed that a path stretch of Θ(c) can be achieved. This path stretch, however, is achieved at the cost of communication and storage overhead, which makes the practical deployment of VIGOR in large scale sensor networks challenging. To this end, we propose GOAL (Geometric Routing using Abstracted Holes), a routing protocol that provably achieves a path stretch of Θ(c), with lower communication and storage overhead. To compactly describe holes, we develop a novel distributed convex hull algorithm, which improves the message complexity O(n log2 n) of state of art distributed convex hull algorithm to O(n log n). The concise representation of a hole is used by nodes to make locally optimal routing decisions. Our theoretical analysis proves the correctness of the proposed algorithms and the path stretch of Θ(c). Through extensive simulations and experiments on a testbed with 42 EPIC motes, we demonstrate the effectiveness of GOAL and its feasibility for resource constrained wireless sensor networks; specifically, we show that GOAL eliminates part of communication overhead of VIGOR and reduces the memory overhead of VIGOR by up to 51%.