ITGR: Intermediate Target Based Geographic Routing

Geographic routing is an effective approach for finding a path to forward packets from a source to a destination in wireless ad hoc networks when nodes have location information. The basic strategy is to let each node select one of its neighbors that is closest to the destination as the next hop to forward the packet greedily. However, when there are void areas (holes), greedy routing does not work due to the local minimum problem. Existing geographic routing algorithms use perimeter routing strategies to find a long detour path when such a situation occurs. In this paper, we propose a new approach called Intermediate Target Based Geographic Routing (ITGR) to avoid such long detour paths. The source determines destination areas which are shaded by the holes based on previous forwarding experience. The novelty of the approach is that a single forwarding path can be used to determine a shaded area that may cover many destination nodes. We design an efficient method for the source to find out whether a destination node belongs to a shaded area. The source then selects an intermediate node as the tentative target and greedily forwards packets to it, which in turn forwards the packet to the final destination by greedy routing. ITGR can be recursively called, if necessary, to generate a detour-free path with multiple tentative targets. Simulation results show that ITGR significantly reduces the routing path length, compared with existing geographic routing protocols.