home search a-z help
University of Cambridge Computer Laboratory
Thursday November 3rd, 2005 - 4pm
Computer Laboratory > Research > Systems Research Group > NetOS > Seminars > Thursday November 3rd, 2005 - 4pm

Landmark Guided Forwarding

Meng-How Lim

Wireless Ad Hoc network routing presents some extremely challenging research problems, trying to optimise parameters such as energy conservation vs connectivity and global optimisation vs routing overhead scalability. In this thesis, we focus on the problems of maintaining network connectivity in the presence of node mobility whilst providing globally efficient and robust routing. The common approach among existing wireless Ad Hoc routing solutions is to establish a global optimal topological path between a source and a destination. We argue that establishing of an end to end globally optimal path is both unreliable and unsustainable as the network diameter, traffic volume, number of nodes all increase in the presence of moderate node mobility.

Apart from the topological based routing approach, some researchers propose to use geographic proximity as a basis for forwarding. In position based forwarding, besides knowing about its own geographic location, every node also acquires geographic position of its surrounding one hop neighbours. Packet delivery in general is achieved by first acquiring the destination position from a location service. This follows by encoding the packet with destination position before passing on the packet to a neighbour that, amongst all other neighbours, has the closest distance to the destination. It is clear that in the Ad Hoc scenario, forwarding by geodesic proximity could result in situations that prevent the packet from advancing further. To resolve this, some researchers propose guaranteed delivery by routing the packet along a constructed planar graph. This approach however has been proven unworkable when inaccurate position or inconsistent neighbourhood state is being considered, such as in a mobile Ad Hoc environment.

We propose Landmark Guided Forwarding (LGF), a hybrid solution that harnesses the strengths of both topological and geographical routing algorithms. LGF leverages on the scaling property of geographic approach while using local topology knowledge to mitigate location uncertainty. We demonstrate that LGF is adaptive to both unstable connectivity and position inaccuracy. Compared with existing solutions, our results indicate that Landmark Guided Forwarding converges much faster, scales much better and more adaptive in mobile Ad Hoc environment.