Geometric Ad-Hoc Routing for Unit Disk Graphs and General Cost Models
Fabian Kühn, Roger P. Wattenhofer, Aaron Zollinger · Repository for Publications and Research Data (ETH Zurich) · 2002
What is the influence of the chosen cost metric on the performance of a mobile ad-hoc routing algo rithm? In this paper we define the notion of a gen eral cost metric and observe that all cost metrics fall into two classes, linearly bounded and super linear. Distinguished by a natural argument, the two classes yet show a dramatic difference: On a network with linearly bounded cost metric a geo metric routing algorithm will find a route whose cost at most quadratic in the cost of the optimal route, which at the same time is asymptotically op timal. On the other hand there is no such bound on a graph with super-linear cost functions for any geometric routing algorithm. We introduce, how ever, the class of bounded degree unit disk graphs, on which all cost metrics are equivalent. We finally propose an asymptotically optimal distributed geo metric routing algorithm based on node clustering and network backbone construction.