## 2 Related work  
Routing protocols for position-based wireless sensor networks are presented in the literature. One-hop flooding [7], partial hop-by-hop routing in Geographic Routing Algorithm (GRA) [8], and Partial Source Routing (PSR) in On-demand Geographic Forwarding (OGF) [9] protocols are based on flooding techniques. These flooding-based geographic routing algorithms exploit the simplest communications techniques in a network, i.e. flooding, to locate a stuck data packet and get around a void. Most of these protocols guarantee packet delivery for connected graphs [7]. Some of these protocols execute full flooding, a technique to send a stuck packet to all network nodes. Flooding is inefficient in terms of resource utilization. Some efficient full flooding algorithms [10] and some restricted flooding mechanisms have been proposed in the literature to minimize the occurrence of void nodes by controlling the range of flooding [27]. However, they still cost too much to handle voids. Graph-based routing algorithms exploit the properties of planar graphs. Some examples are convex face routing [11], original face routing [12], the Face-2 algorithm [13], Other Face Routing (OFR) and Other Adaptive Face Routing (OAFR) in GOAFR [14], and GOAFR\({}^{+}\)[15, 28]. Some complete void handling techniques in geographic routing protocols include perimeter routing in Greedy Perimeter Stateless Routing (GPSR) [16], Request-Response (RR) in Beacon-Less Routing (BLR) [17], and bypass in Priority-based Stateless Geo-Routing (PSGR) [18]. Theoretically, it has been shown that a planar-graph-based technique guarantees packet delivery [19], because planar graph traversal ensures the discovery of a path if a topologically valid path exists. Perimeter routing is the complete void handling technique in GPSR [16]. Perimeter routing consists of a planar traversal algorithm, a distributed planarization algorithm and some other protocol optimizations. In GPSR, a planar sub-graph of the original graph is computed during a preprocessing phase using the Relative Neighborhood Graph (RNG) planarization technique or the Gabriel Graph (GG) planarization technique. When a packet becomes stuck at a void node in greedy forwarding, perimeter routing is enabled and the planar traversal algorithm, similar to Face-2 routing [13], is used to walk the stuck packet around the void. The right hand rule is used to walk around the perimeter. The header of a stuck packet carries information, such as the position of the void node, the position of the last intersection that caused a face change, and the first edge traversed on the current face. Such information helps each node make routing decisions locally. Although GPSR is an accepted stateless location-based routing protocol that guarantees packet delivery if there is a topologically valid path, the detours along the perimeter of its perimeter mode may produce long paths. Planarization in GPSR requires more computational complexity. In GPSR, nodes on the face of the holes may overcrowd due to traffic concentration that may lead to drastic throughput degradation. Excessive energy consumption of void boundary nodes may enlarge the void. Further, GPSR works well in the closed void, but it cannot perform well in an open void. Closed and open are two types of communication void. The closed void is surrounded by sensors, whereas there is an open space to one side in the open void. Figures 3 and 4 illustrate the perimeter mode routing path followed by GPSR in the closed void and open void cases. As shown in Figure 3, a packet travels up to the stuck node (node 4) using greedy forwarding and switches to perimeter mode and travels along the destination using the right hand rule. When it reaches a node that is closer to the destination (i.e. node 11) than the stuck node, it switches back to greedy forwarding. Straight arrows indicate greedy forwarding and curved arrows indicate perimeter mode routing.