Geographic routing

Geographic routing (also called georouting or position-based routing) is a routing principle that relies on geographic position information. It is mainly proposed for wireless networks and based on the idea that the source sends a message to the geographic location of the destination instead of using the network address. The idea of using position information for routing was first proposed in the 1980s in the area of packet radio networks [cite journal
last = Takagi |first = H.
coauthors = Kleinrock, L.
title = Optimal transmission ranges for randomly distributed packet radio terminals
journal = IEEE Transactions on Communications
volume = 32
issue = 3
pages = 246–257
month = March
year = 1984
doi = 10.1109/TCOM.1984.1096061] and interconnection networks [Citation
last = Finn |first = Gregory G.
title = Routing and Addressing Problems in Large Metropolitan-Scale Internetworks
publisher = University of Southern California, ISI/RR-87-180
month = March
year = 1987
url = http://www.isi.edu/div7/people/finn.home/routing_and_addressing_problems_in_large_metropolitan-scale_internetworks.BW.pdf
format = PDF ] . Geographic routing requires that each node can determine its own location and that the source is aware of the location of the destination. With this information a message can be routed to the destination without knowledge of the network topology or a prior route discovery.

There are various approaches, such as single-path, multi-path and flooding-based strategies (see [cite journal
last = Stojmenovic |first = Ivan
title = Position based routing in ad hoc networks
journal = IEEE Communications Magazine
volume = 40
issue = 7
pages = 128–134
doi = 10.1109/MCOM.2002.1018018
year = 2002] for a survey).Most single-path strategies rely on two techniques: "greedy forwarding" and "face routing". Greedy forwarding tries to bring the message closer to the destination in each step using only local information. Thus, each node forwards the message to the neighbor that is most suitable from a local point of view. The most suitable neighbor can be the one who minimizes the distance to the destination in each step (Greedy). Alternatively, one can consider another notion of progress, namely the projected distance on the source-destination-line (MFR, NFP), or the minimum angle between neighbor and destination (Compass Routing). Not all of these strategies are loop-free, i.e. a message can circulate among nodes in a certain constellation. It is known that the basic greedy strategy and MFR are loop free, while NFP and Compass Routing are not [cite journal
last = Stojmenovic |first = Ivan
coauthors = Lin, Xu
title = Loop-free hybrid single-path/flooding routing algorithms with guaranteed delivery for wireless networks
journal = IEEE Transactions on Parallel and Distributed Systems
volume = 12
issue = 10
pages = 023–1032
doi = 10.1109/71.963415
year = 2001] .

Greedy forwarding can lead into a dead end, where there is no neighbor closer to the destination. Then, face routing helps to recover from that situation and find a path to another node, where greedy forwarding can be resumed. A recovery strategy such as face routing is necessary to assure that a message can be delivered to the destination. The combination of greedy forwarding and face routing was first proposed in 1999 under the name GFG (Greedy-Face-Greedy) [cite conference
last = Bose | first = P.
coauthors = Morin, P.; Stojmenovic, I.; Urrutia, J.
title = Routing with guaranteed delivery in ad hoc wireless networks
booktitle = Proc. of the 3rd international workshop on discrete algorithms and methods for mobile computing and communications (DIALM '99)
year = 1999
pages = 48-55
doi = 10.1145/313239.313282 ] .

References

ee also

*List of ad-hoc routing protocols