From: Chandrika Jayant (cjayant@cs.washington.edu)
Date: Mon Nov 22 2004 - 01:34:38 PST
“GPSR: Greedy Perimeter Stateless Routing for
Wireless
Networks”
Written by Brad Karp and H.T. Kung
Reviewed by Chandrika Jayant
By the year 2000, a variety of routing algorithms had been implemented that worked fairly well on static, wired networks. In mobile, wireless networks, topology often changes much more rapidly. In the past few years wireless technologies have come to the forefront of new application research, and begged for better routing methods. Hierarchy and caching do not provide large improvements for this kind of network. The authors present Greedy Perimeter Stateless Routing (GPSR), which uses geography and graph theory to achieve scalability in the wireless routing protocol provided. Each node must only know its neighbors’ positions, while in traditional algorithms like distance vector and link state the state is proportional to the number of reachable destinations at each router.
This algorithm switches back and forth between greedy and perimeter forwarding. A node will go to the neighbor that is the closest to the destination node; if no neighbors are closer to the destination than the current node, perimeter forwarding (and the right-hand rule) is used to solve the problem until greedy forwarding can be used again.
The authors’ measures of successful scalability are satisfied in the results presented. There is a high application packet delivery success rate, the per-node state is very low, and there is a small routing protocol message complexity. GPSR seems to hold up very well with increasing network diameter, and the routing traffic generated is independent of the lengths of the routes in the network. Compared to Dynamic Source Routing (DSR), GPSR seems to easily win out. I am curious why DSR was the only protocol tested against, I would have liked to see 1 or 2 more current successful protocols evaluated. Also reading about the simulation environment, I wanted to know how accurate the network they set up reflects current wireless networks that are used day to day.
A main issue I had with the paper is that it only works with planar nodes. Could this be easily translated to 3D? How often is it realistic to only work in 2D? They should have explained the importance of this distinction more. The authors also seem to skim over the importance of the required location database. They use a “highly idealized” database, which is not realistic when considering actual deployment. We know a database would add more overhead- but how much more? How hard will it be for this to ever be created? Will people want this? Will the information stay reliably up to date?
Apart from the issue of creating an efficient distributed location database, other future plans should include first comparing RNG and GG planarizations, and then seeing how to translate 2D faces to 3D volumes. One of the big contributions of this paper is showing how geographic information can benefit various location-aware apps, a field which is definitely very relevant and exciting today.
This archive was generated by hypermail 2.1.6 : Mon Nov 22 2004 - 01:34:43 PST