| Geographic routing is a scalable any-to-any routing algorithm in which node state scales as the number of neighbors. It uses greedy routing when possible, and uses face routing to recover when greedy progress reaches a local minimum node that has no neighbor closer to the destination. Face routing is guaranteed to work correctly only on planar graphs that have no cross-link.;All currently proposed techniques for face routing and for constructing planar graphs (planarization) have relied on common underlying assumptions: circular radio range and precise localization. However, our experimental evaluations demonstrate that these assumptions are violated by real radios and that these violations can result in persistent routing failures. Motivated by this, we have investigated how well geographic face routing works under general conditions such as irregular radio range and imprecise location information.;In this thesis, we first have extensively examined the correctness of geographic routing algorithms in real wireless graphs. Our initial research identified and classified failures in planarization and face routing. To fix these failures, we have proposed the Cross-Link Detection Protocol (CLDP) and enhanced face routing algorithms. CLDP is the first distributed planarization technique that enables provably correct geographic face routing on arbitrary connectivity graphs.;Next, we have examined the performance of geographic routing algorithms in arbitrary graphs. Existing algorithms have high message cost and high stretch. To improve performance, we have devised Lazy Cross-Link Removal (LCR) and Intelligent Face Routing (IFR): LCR correctly and reactively planarizes graphs with extremely low message cost; IFR is a new approach for face routing which exhibits the best average stretch performance among existing face routing families. |
