Face Tracing Based Geographic Routing in Nonplanar Wireless Networks

Scalable and efficient routing is a main challenge in the deployment of large ad hoc wireless networks. An essential element of practical routing protocols is their accommodation of realistic network topologies. In this paper, we study geographic routing in general large wireless networks. Geographic routing is a celebrated idea that uses the locations of nodes to effectively support routing. However, to guarantee delivery, recent geographic routing algorithms usually resort to perimeter routing, which requires the removal of communication links to get a planar sub-network on which perimeter routing is performed. Localized network planarization requires the wireless network to be a unit-disk graph (UDG) or its close approximation. For networks that significantly deviate from the UDG model, a common case in practice, substantially more expensive and non-localized network planarization methods have to be used. How to make such methods efficiently adaptable to network dynamics, and how to avoid the removal of an excessive number of links that leads to lowered routing performance, are still open problems. To enable efficient geographic routing in general wireless networks, we present face-tracing based routing, a novel approach that routes the message in the faces of the network that are virtually embedded in a topological surface. Such faces are easily recognizable and constructible, and adaptively capture the important geometric features in wireless networks - in particular, holes, -thus leading to very efficient routing. We show by both analysis and si mulations that the face-tracing based routing is a highly scalable routing protocol that generates short routes, incurs low overhead, adapts quickly to network dynamics, and is very robust to variations in network models.