Technical reports

Landmark Guided Forwarding

Meng How Lim

October 2006, 109 pages

This technical report is based on a dissertation submitted September 2006 by the author for the degree of Doctor of Philosophy to the University of Cambridge, St Catharine’s College.

DOI: 10.48456/tr-674

Abstract

Wireless mobile ad hoc network routing presents some extremely challenging research problems. While primarily trying to provide connectivity, algorithms may also be designed to minimise resource consumption such as power, or to trade off global optimisation against the routing protocol overheads. In this thesis, we focus on the problems of maintaining network connectivity in the presence of node mobility whilst providing a balance between global efficiency and robustness. The common design goal among existing wireless ad hoc routing solutions is to search for an optimal topological path between a source and a destination for some shortest path metric. We argue that the goal of establishing an end to end globally optimal path is unsustainable as the network diameter, traffic volume and number of nodes all increase in the presence of moderate node mobility.

Some researchers have proposed using geographic position-based forwarding, rather than a topological-based approach. In position-based forwarding, besides knowing about its own geographic location, every node also acquires the geographic position of its surrounding neighbours. Packet delivery in general is achieved by first learning the destination position from a location service. This is followed by addressing the packet with the destination position before forwarding the packet on to a neighbour that, amongst all other neighbours, is geographically nearest to the destination. It is clear that in the ad hoc scenario, forwarding only by geodesic position could result in situations that prevent the packet from advancing further. To resolve this, some researchers propose improving delivery guarantees by routing the packet along a planar graph constructed from a Gabriel (GG) or a Relative Neighbour Graph (RNG). This approach however has been shown to fail frequently when position information is inherently inaccurate, or neighbourhood state is stale, such as is the case in many plausible deployment scenarios, e.g. due to relative mobility rates being higher than location service update frequency.

We propose Landmark Guided Forwarding (LGF), an algorithm that harnesses the strengths of both topological and geographical routing algorithms. LGF is a hybrid scheme that leverages the scaling property of the geographic approach while using local topology knowledge to mitigate location uncertainty. We demonstrate through extensive simulations that LGF is suited both to situations where there are high mobility rates, and deployment when there is inherently less accurate position data. Our results show that Landmark Guided Forwarding converges faster, scales better and is more flexible in a range of plausible mobility scenarios than representative protocols from the leading classes of existing solutions, namely GPSR, AODV and DSDV.

Full text

PDF (0.9 MB)

BibTeX record

@TechReport{UCAM-CL-TR-674,
  author =	 {Lim, Meng How},
  title = 	 {{Landmark Guided Forwarding}},
  year = 	 2006,
  month = 	 oct,
  url = 	 {https://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-674.pdf},
  institution =  {University of Cambridge, Computer Laboratory},
  doi = 	 {10.48456/tr-674},
  number = 	 {UCAM-CL-TR-674}
}