Worst-Case optimal and average-case efficient geometric ad-hoc routing

Abstract

In this paper we present GOAFR, a new geometric ad-hoc routing algorithm combining greedy and face routing. We evaluate this algorithm by both rigorous analysis and comprehensive simulation. GOAFR is the first ad-hoc algorithm to be both asymptotically optimal and average-case efficient. For our simulations we identify a network density range critical for any routing algorithm. We study a dozen of routing algorithms and show that GOAFR outperforms other prominent algorithms, such as GPSR or AFR.