Routing on overlay graphs in mobile ad hoc networks

Geometric routing using source-destination locations has been widely suggested as a scalable alternative to conventional routing approaches in mobile ad hoc networks. Recently, there has been considerable attention on face routing in planar graphs constructed from overlay graphs in wireless networks. Given a plane tiled into an infinite mesh of polygons, an overlay graph is defined as one in which a graph edge is defined between two adjacent polygons if a radio link exists between any two nodes located in these polygons. We consider the problem of constructing a connected planar graph from the overlay graph, and geometric routing in such graphs. We prove a specific property of such graphs known as the redundancy property and propose a distributed routing algorithm called Grid Traversal Algorithm (GTA) based on the redundancy property of overlay graphs. The algorithm is both localized and energy efficient, but may not guarantee connectivity in pathological cases. Simulations show that such disconnections are rare in practise and that GTA performs very well in terms of percentage of data delivered, data delay and overhead compared to GPSR, a geometric routing protocol that routes on a planar graph extracted from the unit disk graph.