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 : GPSR Greedy Perimeter Stateless Routing code ns2 network simulator