Face Tracing Based Geographic Routing in Nonplanar Wireless Networks

Abstract — 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 effec-tively 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