Jul 3, 2007

Greedy Perimeter Stateless Routing (GPSR)



GPSR: Greedy Perimeter Stateless Routing code for version 2.26 or later (till 2.29 now). Download my implementation tarball
You can obtain its original implementation through GPSR official link which is just for old version of ns2.

  • Since this implementation is original based on ns2 version 2.26, you need to be careful to deal with it when you use a later vesion. Especially the ns-packet.tcl file, you need to do the change by yourself. The one in my tarball may not be suitable for you to use.
  • This implementation consists of 2 parts exactly the same as proposed by the original GPSR paper, and is a little bit different from the orginial ns2 implementation (see through the link above).
  • This implementation is a pure Stateless implementation, where the routing decision of each packet on any node is made purely only on the local information (one-hop neighborhood)
  • Both GG and RNG planarization methods are provided by this implementation.

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

  • tags :

    3 comments:

    Anonymous said...

    I tried to use this version of GPSR code to do simulation in NS2.
    However, I wondered if this version is defined well, since the simulation result is different from the expected. I used the simulation scenario as the original paper said. For example, packet delivery ratio is very low in 50 nodes, (1500m*300m), pause time 30s, and movement speed is 10m/s, 20m/s.

    vamshi said...

    Hi,
    I tried to use your code to implement GPSR and made some modification which I got under http://mailman.isi.edu/pipermail/ns-users/2005-April/049131.html. But still I got errors. Can you help me out.Am using ns-2.34

    Anonymous said...

    I cannot see the nam simulation how can i add it?