On the pitfalls of geographic face routing

Geographic face routing algorithms have been widely studied in the literature [1, 8, 13]. All face routing algorithms rely on two primitives: planarization and face traversal. The former computes a planar subgraph of the underlying wireless connectivity graph, while the latter defines a consistent forwarding mechanism for routing around "voids." These primitives are known to be provably correct under the idealized unit-disk graph assumption, where nodes are assumed to be connected if and only if they are within a certain distance from each other.In this paper we classify the ways in which existing planarization techniques fail with realistic, non-ideal radios. We also demonstrate the consequences of these pathologies on reachability between node pairs in a real wireless testbed. We then examine the various face traversal rules described in the literature, and identify those [12, 16] that are robust to violations of the unit-disk graph assumption.