From: Kevin Wampler (wampler@cs.washington.edu)
Date: Sun Nov 21 2004 - 23:24:10 PST
Wireless networks present a very different set of demands upon routing
protocols than in a traditional network. The links between nodes are
highly dynamic, making algorithms which rely on having a complete picture
of the network topology highly inefficient. An algorithm for efficiently
routing in such a wireless network is given in "GPSR: Greedy Perimeter
Stateless Routing for Wireless Networks".
Motivated by the prohibitive number of update messages that would have to
be sent in a routing protocol which requires global information about a
network (such as distance vector or link state), GPSR requires only that
each node maintain information about its neighbors. The primary insight
that allows this algorithm to work is that the position of a node provides
a good heuristic for estimating shortest paths. GPSR takes advantage of
this by greedily routing to the neighbor with the smallest Euclidean
distance for a destination. To avoid being trapped in a local minimum,
packets can be switched between two modes, one which greedily minimizes
distance and the other which routes around faces.
In the networks tested, GPSR performs relatively well. Most of the
packets followed the shortest-hops routes, and few packets failed to be
transfered. The efficiency in these cases depends on the networks being
dense, so that Euclidean distance is a good estimate of hop-wise distance.
It may be possible to do slightly better by having nodes give modified
values for their position depending on their neighbors, but I see no way
that we could do too much better with this general approach.
One thing of not, however, is that since each node is required to keep
information on the state of its neighbors, there will be many update
messages sent as the networks grow very dense, in particular as might
happen in new technology drastically increased the transmission range of
the nodes. This case could still probably be handled efficiently however,
by using a distributed dynamic proximity detection algorithm (like the
strips algorithm in the 2003 infocom buddy tracking paper) to minimize the
number of these update messages that are sent.
This archive was generated by hypermail 2.1.6 : Sun Nov 21 2004 - 23:24:10 PST