Concurrent face traversal for efficient geometric routing

We present a concurrent face routing CFR algorithm. We formally prove that the worst case latency of our algorithm is asymptotically optimal. Our simulation results demonstrate that, on average, the path stretch, i.e., the speed of message delivery, achieved by CFR is significantly better than by other known geometric routing algorithms. In fact, it approaches the shortest possible path. CFR maintains its advantage over the other algorithms in pure form as well as in combination with greedy routing. CFR displays this performance superiority both on planar and non-planar graphs.

► Efficient geometric routing algorithm.
► Concurrent face traversal.
► Theoretically optimal message latency for geometric routing.