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 |
Step6
