## 2 Related work
The open void case is illustrated in Figure 4. After the packet encounters a void, GPSR switches to perimeter mode (node 4) and travels back to the source node. It continues perimeter routing until it reaches node 11 that is closer to the destination than the stuck node (node 4). Once back at node 11, it switches to greedy forwarding. The right hand rule is inefficiently aggregates data from the sensor to BS. Our algorithm avoids voids without the use of the right-hand rule. The Distance Upgrading Algorithm (DUA) [20] is a void handling technique that exploits a cost-based idea to handle voids. Similar to the Partial-partition Avoiding Geographic Routing-Mobile (PAGER-M) [21], a packet flows from a node with a higher cost to one with a lower cost. To avoid voids, DUA virtually increases the distance of stuck nodes to the BS such that it can avoid communication voids beforehand. Figure 5: DUA fails in some scenarios. A cost, which may be equal to its Euclidean distance to the destination, is assigned to each node in the network. The stuck node increases its cost to a value greater than its Euclidian distance to the destination, so that the packet can finally be directed by the high-cost-to-low-cost rule [22] along efficient paths to evade the void. DUA proves that, after upgrading the distance, all the routing link directions reverse towards BS. The design parameter defined in DUA is greater than the cost of the farthest node from BS. If the source node upgrades distance by twice the design parameter, it reverses all the links. However, this is true if only one or two concave type stuck nodes are considered. If there are more than two concave type stuck nodes, DUA cannot perform well. A concave node is defined in Section 3. Figure 5 illustrates where DUA breaks down. In Figures 5(h) and 5(j), nodes become a stuck node after upgrading the distance by twice the constant. Distance upgrading by the design parameter in DUA upgrades and downgrades the distance for all nodes along the route from the stuck node to the source node whenever any node becomes a stuck node. This is inefficient for small and many other topological voids. Further, it may select an inefficient route after upgrading the distance, because it increases the cost extensively, such that the packet has to piggyback the location information. Distance downgrading is also required to adjust the distance. This increases the routing overheads in two ways. First, packets carry the node information where it upgraded the distance. Second, BS has to broadcast the control message to downgrade the distance. It is intuitive that cost-based techniques guarantee packet delivery in connected graphs. Inspired from that, we propose the Void Avoidance Algorithm (VAA) that is better than DUA. In VAA, the stuck node only upgrades the distance and downgrading is not required. There is no need to piggyback the coordinate where the virtual distance upgrade is initialized. The primary focus of our proposed algorithm is to virtually increase the distance to the BS by stuck nodes to turn themselves into non-stuck nodes, to eliminate communication voids. Finally, it forwards packets from sensors to BS along efficient routes using greedy routing. After implementing VAA, no node remains a stuck node in the network, if there is at least one route to the destination. Thus, it is completely distributed, immediately responds to node failure or topology changes, does not require planarizing the network, and incurs substantially less overhead.