Geographic Routing with Cross Links

Geographic routing is promising in wireless sensor network because its efficiency and scalability. However, none of the proposed geographic routing algorithms has been implemented in real sensor network application yet. The standard model for geographic routing represents sensor network by an textit{Unit Disk Graph} (UDG), where each sensor node is assumed with the same communication radius. Then, a planar graph is extracted from UDG to perform geographic routing. In practice, however, the standard model may not hold true due to radio disturbance caused by environmental factors. Violating this assumption may result in an incomplete planarization. Delivery on an incomplete planarized graph is not guaranteed. In this paper, we explore how exactly incomplete planarization leads to delivery failure and introduce an algorithm to solve this problem. Experimental results confirm the correctness of our algorithm.