From: Ethan Phelps-Goodman (ethanpg@cs.washington.edu)
Date: Sun Nov 21 2004 - 21:21:40 PST
Greedy Perimeter Stateless Routing
Karp and Kung
This paper presents an ad hoc routing protocol that routes based on
geography. Most previously researched ad hoc protocols, such as DSR and
AODV, were based on flooding. When a route is needed, the protocol floods a
request for a route to the destination. Extensive caching is used to make
the scheme practical. GPSR works off the assumption that every node knows
its own position, through GPS or some other means. Routing obviously becomes
much easier at this point.
The obvious greedy forwarding works in most cases, and requires only
knowledge of immediate neighbors. No additional state or background traffic
is needed. The protocol is complicated by the fact that the shortest
Euclidean path may not contain reachable nodes. In this case the protocol
falls back on perimeter routing. This requires some slightly complicated
graph algorithms to route around a hole in reachability. The algorithm
involves computing a planar graph from the connectivity graph and proceeding
around the void via the right-hand rule.
Simulations show their system to be superior to DSR. Paths are slightly
shorter and delivery is moderately more reliable. The real win is in control
traffic, which remains a low constant for GPSR, but scales linearly with
network size in DSR. This isn't surprising--the DSR authors are clear that
the protocol is not designed for networks over around 10 hops in diameter,
and geographic information is clearly very useful. In the particular case of
a large diameter network where each node knows its position and has access
to a reliable location server for its destinations, GPSR is the clear
winner. More interesting to me though would be work on improving more
general purpose protocols like DSR.
Ethan
This archive was generated by hypermail 2.1.6 : Sun Nov 21 2004 - 21:21:46 PST