From: Andrew Putnam (aputnam@cs.washington.edu)
Date: Mon Nov 22 2004 - 01:34:39 PST
GPSR: Greedy Perimeter Stateless Routing for Wireless Networks
Brad Karp and H.T. Kung
Summary: GPSR is introduced as a geographically based routing protocol
for rapidly changing wireless networks. The protocol does not introduce
many new and novel concepts, but does show one method for effectively
utilizing geographical information to make routing decisions without
global routing information.
GPSR has a few primary advantages. First, the protocol scales well
since there is no need for global information to make routing
decisions. Second, it minimizes traffic on the wireless network by
going with the shortest geographic route. (Unfortunately this does
nothing for load balancing). Third, it is effective in delivering
packets to rapidly changing wireless topologies. Fourth, it requires
very little state information, so there is no need for heavy-duty
calculation or much available storage.
GPSR claims to have lower overhead than DSR, but this claim is
absurd given the fact that DSR determines routes dynamically via a
route discovery protocol while GPSR assumes that it has geographical
location information via GPS. The overhead of receiving and processing
GPS data, and planarizing the topology seems like it should be included
in the overhead. Of course your overhead is lower when you assume the
route discovery and route naming work is done for you.
The fact that GPSR utilizes geographical information is the most
novel part of the protocol, and is the reason the protocol is
relatively effective. Primarily, this allows the network to scale well
by not requiring end-to-end information. All the sending node needs to
know it its own location and its destination node's location. From
there, it can simply try to send the message directly or forward the
message to a geographically closer node. There is always the assumption
that packets forwarded to closer nodes will be forwarded in turn. There
is no attempt to deal with security or fairness in this routing
algorithm.
One problem I have with GPSR is that proximity to another node may or
may not be the best way to determine if that node is a better choice
for routing to the destination node. This is particularly true in
sensor network environments where line-of-site transmission tends to
work far better. This is particularly true in urban environments.
Wireless nodes that have no objects blocking their paths to each other
tend to have a much stronger signal than nodes that are close but have
their path obstructed by walls, floors, etc. It is also the case in
outdoor environments due to hills, trees, rocks, etc.
It is interesting that the authors are concerned with wireless
networks that have rapid topology changes, yet require very little
state, and scale effectively. I struggle to find which application
requires all three of these factors. Sensor networks require little
state, but do not tend to have rapid topology changes. They also have a
small amount of state because they don't want to spend power on
computation. Since these nodes must have constant geographical update
information, this does not seem to lend itself to low-power sensor
networks. Most ad-hoc networks consisting of 802.11 radios certainly
have enough storage and computational power to afford routing
algorithms that require more than minimal state. The authors listed
these two networks as their target markets, but I do not see these
networks as benefiting from GPSR.
The authors make a curious comment that made their simulation results
somewhat questionable. The authors say that they do not simulate pause
times of 300, 600, and 900 as did the DSR authors, yet that is where
DSR did the best. It is apparent from the performance curves that DSR
is improving as the pause time increases, and is increasing at a more
rapid pace than GPSR. In fact, GPSR seems to be on a downward trend as
the pause time increases. Whether or not it truly is, this seems to
deliberately hide the fact that DSR may be superior in longer pause
environments. It is certainly worthy of some explanation as to why the
longer pauses were not investigated or reported.
This archive was generated by hypermail 2.1.6 : Mon Nov 22 2004 - 01:34:47 PST