From: Jonas Lindberg (jonaslin@cs.washington.edu)
Date: Sun Nov 21 2004 - 15:31:54 PST
B. Karp and H. T. Kung, "GPSR: Greedy Perimeter Stateless Routing for
Wireless Networks"
Reviewed by: Jonas Lindberg
In this paper Karp et al. present a routing protocol for wireless networks
with nodes that knows their geographical location. The idea of this protocol
is to use the nodes' position knowledge for greedy forwarding, which means
that a node forwards a packet to the one of its neighboring nodes that is
physically closest to the packet's destination. When greedy forwarding is
not possible (i.e. all of the nodes neighbors are further away from the
destination than itself) the protocol tries to route around the perimeter of
the node-free region between itself and the destination.
The GPSR routing protocol has a couple of neat properties: First, it does
not require much state information, only the position of itself and its
neighbors, which makes it scaleable. Second, it needs only little overhead
routing traffic. Third, it can quickly adapt to topology changes. Forth, the
packet delivery is relatively reliable, at least in densely deployed
networks. One limitation is that all nodes need to know their own position,
either by using a GPS device or trough other means. This might be ok in some
networks, but I can not help wondering what those networks would be and how
this requirement might decimate the number of situations in which GPSR is
suitable.
Karp et al. does a good job explaining how GPSR works and they also discuss
interesting challenges (like the planarization). One small detail that could
be improved in this part is to explain the heuristics behind the numeric
values used in the discussion of the beacon transmissions. The simulation
part presents relevant and interesting results. It shows that GPSR have,
compared to Dynamic Source Routing, good performance in dense wireless
networks.
This archive was generated by hypermail 2.1.6 : Mon Nov 22 2004 - 00:32:33 PST