Asymptotically optimal geometric mobile ad-hoc routing
Fabian Kühn, Rogert Wattenhofer, Aaron Zollinger · 2002
In this paper we present AFR, a new geometric mobile ad-hoc routing algorithm. The algorithm is completely distributed; nodes only need to communicate with direct neighbors in their transmission range. We show that if a best route has cost c, AFR finds a route and terminates with cost O(c^2) in the worst case. AFR is the first algorithm with cost bounded by a function of the optimal route. We also give a tight lower bound by showing that any geometric routing algorithm has worst-case cost Omega(c^2). Thus AFR is asymptotically optimal. We give a non-geometric algorithm that also matches the lower bound, but needs some memory at each node. This establishes an intriguing trade-off between geometry and memory.