## 1 Introduction  
Geographic routing, also called position-based routing, geo-routing, location-based routing, or directional routing, was originally proposed for packet radio networks in the 1980s [1-2]. Geographic routing exploits position information instead of topological connectivity information to move data packets to gradually approach and eventually reach the intended destination. Geographic routing eliminates some of the limitations of topology-based routing by using the physical position of the participating nodes as additional information. Each node determines its own position through low energy consumable and low cost GPS or similar positioning services [3-5]. Geographic routing does not require the establishment or maintenance of routes. The localized operation and the state-less feature of geographic routing make it simple and scalable. A new paradigm of geographic routing called geocasting [6], which supports delivery of packets to all the nodes in a given geographic region, made this field more interesting. Geographic routing for WSNs has been attracting research interest. Most of the existing geographic routing protocols use greedy routing to forward packets from source to destination. Greedy routing is a simple, efficient and scalable strategy for geographic WSNs. Since greedy routing makes pure local decisions, it requires only a simple beaconing protocol. Thus, it consumes considerably less bandwidth than protocols that distribute state globally throughout the network. It is robust under topological changes, because a node can make correct forwarding decisions without requiring up-to-date state of nodes beyond a single hop. Due to their low processing and memory cost, greedy routing is efficient in resource constrained WSNs. In greedy routing, a source node selects a neighboring node that is closest (with respect to Euclidian distance) to the destination as the next hop, until the destination is reached. Similarly, each intermediate node selects a next hop node closest to the destination until the packet reaches the destination. The position of the packet destination is carried in the header of the packet so that intermediate nodes can learn the packet's destination. In Figure 1, the arrow shows the radius of the radio range of sensor S. Whenever S has a packet for the base station (BS), it forwards the packet to n, as its next hop node, because the distance between n and BS is less than any other of neighbor of S to BS. This greedy forwarding process repeats until the packet reaches BS. Greedy forwarding performs well in dense networks, whereas in sparse networks it does not perform well due to communication voids. A communication void is a state where all neighbor nodes are further away from the destination than the node holding the current packet. The node where the  
Figure 1: Greedy forwarding. packet gets stuck is called a stuck node, or void node. The packet tarries at the stuck node that has no neighbor closer to the destination than itself. In this situation, packets have to be discarded by the stuck node, when only a greedy forwarding strategy is used, even though a topologically valid path to the destination node may still exist. A communication void is often called a routing hole, dead end or void. In Figure 2, node \(\mathrm{n_{i}}\) is a node holding the current packet and BS is the destination. Node \(\mathrm{n_{i}}\) does not have a node, within its forwarding area (a), closer to the BS than \(\mathrm{n_{i}}\) itself. Let R be the maximum transmission range of BS and \(\mathrm{L_{i}}\) be the distance to the BS from node \(\mathrm{n_{i}}\). Assuming that all the sensors are homogeneous with the transmission range r, the forwarding area for node \(\mathrm{n_{i}}\) depends on the distance to the BS (\(\mathrm{L_{i}}\)) from node \(\mathrm{n_{i}}\). When \(\mathrm{L}\) is extremely larger then r, the forwarding area (\(\mathrm{a_{i}}\)) \(\approx\) 1/2\(\pi\)r\({}^{2}\). On the other hand, if the BS is very close to the node i.e.