Minimizing recovery overhead in geographic ad hoc routing

Geographic routing has been studied as an attractive approach due to its simplicity and scalability properties in routing for wireless ad hoc networks. Greedy routing is an important component of many geographic routing protocols which use a combined routing approach; a kind of recovery routing is used in case that greedy routing is impossible. In this paper, we propose the stateless extension of greedy routing called GR(k)GR(k) that implements a k-bound forwarding algorithm where the parameter k controls the routing success rate and the corresponding overhead. We design three k-bound forwarding algorithms and evaluate which one is best via extensive simulation. The proposed approach improves the success rate of greedy routing by 20–40% at low node densities but in low overhead. These improvements mitigate the adverse effect of recovery routing (e.g. face routing) because the use of recovery routing is minimized; In particular, using GR(k) instead of greedy routing can reduce the number of packet transmissions up to 50%. We show that GR(k) is effective in reducing the average hop stretch in geographic routing by at most 30%.