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 primi-tives: planarization and face traversal. The former computes a pla-nar 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 demon-strate the consequences of these pathologies on reachability be-tween 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.