In wireless networks comprised of numerous mobile stations, the routing problem of finding paths from a traffic source to a traffic destination through a series of intermediate forwarding nodes is particularly challenging. When nodes move, the topology of the network can change rapidly. Such networks require a responsive routing algorithm that finds valid routes quickly as the topology changes and old routes break. Yet the limited capacity of the network channel demands efficient routing algorithms and protocols, that do not drive the network into a congested state as they learn new routes. The tension between these two goals, responsiveness and bandwidth efficiency, is the essence of the mobile routing problem.
Greedy Perimeter Stateless Routing, GPSR, is a responsive and efficient routing protocol for mobile, wireless networks. Unlike established routing algorithms before it, which use graph-theoretic notions of shortest paths and transitive reachability to find routes, GPSR exploits the correspondence between geographic position and connectivity in a wireless network, by using the positions of nodes to make packet forwarding decisions. GPSR uses greedy forwarding to forward packets to nodes that are always progressively closer to the destination. In regions of the network where such a greedy path does not exist (i.e., the only path requires that one move temporarily farther away from the destination), GPSR recovers by forwarding in perimeter mode, in which a packet traverses successively closer faces of a planar subgraph of the full radio network connectivity graph, until reaching a node closer to the destination, where greedy forwarding resumes.
GPSR will allow the building of networks that cannot scale using prior routing algorithms for wired and wireless networks. Such classes of networks include:
Sensor networks: potentially mobile, potentially great density, vast numbers of nodes, impoverished per-node resources Rooftop networks: fixed, dense deployment of vast numbers of nodes Vehicular networks: mobile, non-power-constrained, widely varying density Ad-hoc networks: mobile, varying density, no fixed infrastructure
We are extending GPSR:
Obstacles and localization errors: We have investigated GPSR's behavior in the presence of obstacles to radio propagation and node localization errors, which introduce the risk that the planar subgraph used by GPSR's perimeter mode may not be connected. We initially investigated the "mutual witness" proposal, a heuristic for preserving the connectivity of the planar subgraph, mentioned in the thesis and DIMACS talk below. More recently (2004), we've developed the Crossing Link Detection Protocol (CLDP), which allows provably correct geographic routing on any connected network, i.e., even on networks where obstacles, irregularly shaped radio ranges, and localization errors occur. CLDP is described in the NSDI 2005 paper below. Geographic provisioning: We use geographic forwarding via a waypoint not on the path found by naive GPSR to distribute load on the network. This approach is promising because on a wireless network, position and capacity are correlated; distributing load geographically leverages spatial reuse, and cuts the average load in regions where traffic is concentrated.
Young-Jin Kim of Ramesh Govindan's Embedded Networks Laboratory at USC has released a full implementation of GPSR (complete with a Mutual Witness protocol) for TinyOS. This implementation runs on Mica sensor motes. Find the code on the ENL software page!
(NEW! 15th January, 2005)
Kim, Y.-J., Govindan, R., Karp, B., and Shenker, S., Geographic Routing
Made Practical, to appear in the Proceedings of the Second USENIX/ACM
Symposium on Networked System Design and Implementation (NSDI 2005),
Boston, MA, May, 2005.
Karp, B., Challenges in Geographic Routing: Sparse Networks, Obstacles, and Traffic Provisioning, in the DIMACS Workshop on Pervasive Networking, Piscataway, NJ, May, 2001. .pdf
Karp, B., Geographic Routing for Wireless Networks, Ph.D. Dissertation, Harvard University, Cambridge, MA, October, 2000. .ps.gz
Karp, B. and Kung, H.T., Greedy Perimeter Stateless Routing for Wireless
Networks, in Proceedings of the Sixth Annual ACM/IEEE International
Conference on Mobile Computing and Networking (MobiCom 2000), Boston, MA,
August, 2000, pp. 243-254. .ps.gz
GPSR Simulation Code
ns-2 simulation code for GPSR, used
in preparation of our MobiCom 2000 paper.
N.B. that you must build this ns distribution with tclcl-1.0b8 and otcl-1.0a4; these are the releases of the ns companion libraries that were current when the ns-2.1b6 snapshot in the tarball above was current.
A rough list of what's GPSR-specific in this ns-2 tarball:
| File(s) | Description |
|---|---|
| gpsr/{gpsr.cc,h} | C++ code for the GPSR routing agent. |
| gpsr/paper-cmu.tcl | TCL script for simulations used in 50-node cases in MobiCom 2000 paper. GPSR parameters set in this script. |
| gpsr/paper-cmu.pl | Perl script for iterating over several simulations, all 50-node cases from the MobiCom 2000 paper. |
| tcl/mobility/gpsr.tcl | TCL library code for GPSR. |
| locdbase.{cc,h} | C++ code for the idealized (omniscient) location database. |
There are also minor modifications to ip.h, cmu-trace.h, and packet.h, for underlying support required by GPSR.
A table of the TCL variables used to configure the behavior of the ns-2 GPSR implementation follows. The values used in the MobiCom 2000 paper are given below, for reference.
N.B. that you should set all these parameters in your simulation script; the defaults may not be appropriate for the simulation you want to run!
| TCL Configuration Variable | MobiCom 2000 Value | Function |
|---|---|---|
| bint_ | {1.0, 1.5, 3.0} | Beaconing interval (seconds) |
| bdesync_ | 0.5 | Random component magnitude (percentage) in beaconing interval, to avoid synchronized beaconing by neighbors |
| bexp_ | 3 * (bint_ + bdesync_ * bint_) | Beacon expiration interval (seconds) before timing out neighbor from neighbor list |
| use_implicit_beacon_ | 1 | When set to 1, treat data packets as beacons; receive promiscuously and reset neighbor expiration timer for every received unicast packet from a neighbor, and reset the beacon transmission timer whenever transmitting a unicast packet |
| use_mac_ | 1 | When set to 1, use link breakage detection from failed MAC retransmit to remove neighbors from neighbor list |
| use_peri_ | 1 | When set to 1, forward packets in perimeter mode when greedy forwarding impossible |
| use_planar_ | 1 | When set to 1, enables planarization in perimeter mode |
| use_timed_plnrz_ | 0 | When set to 1, enables periodic replanarization, on the basis of a timer |