The cell structure has two advantages for applying position-based routing: It helps to determine local minima for greedy forwarding and improves recovery from such minima, because for recovery all edges can be used in contrast to other topology-based rules that can be appliedonly on a planar subgraph.

For the analysis of position-based routing algorithms the measures time and traffic are based on the cell structure. The difficulty of exploring the network is expressed by the size of the barriers (i.e. the number of cells in the perimeters). Exploration can be done in parallel, but with increasing traffic. We propose a comparative measure to assess both time and traffic, the combined comparative ratio, which is the maximum of the ratio of routing time and optimal time and the ratio of the traffic and the minimum exploration costs.

While flooding and common single-path strategies have a linear ratio, we present a simple algorithm that has a sub-linear

combined comparative ratio of O(sqrt(h)), where h is the minimal hop distance between source and target. AU - RÃ¼hrup, Stefan AU - Schindelhauer, Christian ID - 19834 SN - 0769523129 T2 - 19th IEEE International Parallel and Distributed Processing Symposium TI - Competitive Time and Traffic Analysis of Position-Based Routing using a Cell Structure ER -