From: Susumu Harada (harada@cs.washington.edu)
Date: Mon Nov 22 2004 - 00:59:34 PST
"GPSR: Greedy Perimeter Stateless Routing for Wireless Networks"
B. Karp and H.T. Kung
In this paper, the authors present a routing solution for dynamic wireless
networks where each router can possibly be mobile, providing a scalable
method for determining the path between a sending node and a receiving
node. Their method, called Greedy Perimeter Stateless Routing (GPSR),
assumes that each router in a wireless network posses knowledge of their
position as they roam about the physical space and bases their decision of
where to route a packet on the relative location of their neighboring
nodes to the destination. The algorithm operates in two phases where the
first phase attempts to route the packet as geographically close to the
destination as possible, and when that gets stuck, switches to a perimeter
routing scheme whereby an attempt is made to route around a geographic
"void" where there are no routers closer to the destination.
I thought the way in which they encapsulated the routing decision by
adopting a geography based policy in which each router tries to perform an
intelligent hill climbing was very attractive. Since the routers only
have to maintain information about their neighbors, it is significantly
more efficient and flexible than link state and distance vector protocols.
Their ability to piggyback the location data on top of data packets as
well as their proactive beaconing also reduces the routing protocol
traffic overhead significantly.
There were several issues that stuck out as I read the paper. First is
their series of assumptions about the nature of the wireless network.
They assume that each wireless router can be characterized as having equal
and uniform coverage radius. In reality, this will not be the case as
buildings may obstruct certain paths and also each router will have
varying coverage areas. How will their perimeter algorithm work under
these conditions? Also, they seem to assume a model under which all the
wireless routers are mobile. In reality, it seems more to be the case
that the wireless routers are mostly stationary, and the mobile clients
(not participating in routing) are the ones that are highly mobile. Given
this scenario, I wonder how relevant their approach is in addressing such
situations. Finally, it is not clear how realistic it is to require all
mobile routers to be aware of their physical location. As power is a
scarce resource for mobile systems, it is not clear how feasible it is to
require them to equip themselves with GPS devices. Also, how well such
methods translate to indoor settings or other places where accurate
location information is unavailable is also unclear.
This archive was generated by hypermail 2.1.6 : Mon Nov 22 2004 - 00:59:34 PST