On Delivery Guarantees and Worst-Case Forwarding Bounds of Elementary Face Routing Components in Ad Hoc and Sensor Networks

Download Now Date Added: Sep 2010
Format: PDF

In this paper, the authors provide a thorough theoretical study on delivery guarantees, loop-free operation, and worst-case behavior of face and combined greedy-face routing. They show that under specific planar topology control schemes, recovery from a greedy routing failure is always possible without changing between any adjacent faces. Guaranteed delivery then follows from guaranteed recovery while traversing the very first face. In arbitrary planar graphs, however, a proper face selection mechanism is of importance since recovery from a greedy routing failure may require visiting a sequence of faces before greedy routing can be restarted again. They provide complete and formal proofs that several proposed face routing and combined greedy-face routing schemes guarantee message delivery in specific planar graph classes or even in arbitrary planar graphs.