Greedy Perimeter Stateless Routing (GPSR)

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

      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.

ns-2 simulation code    for GPSR


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