Greedy Perimeter Stateless Routing in Wireless Networks

from Wikipedia, the free encyclopedia

Greedy perimeter stateless routing in wireless networks ( Engl. "Greedy perimeter routing in wireless networks", abbreviation GPSR ) is a routing protocol for mobile ad-hoc networks , ie a process by which data packets in spontaneously built computer networks at their destination should be piloted.

The protocol was developed by B. Karp and owes its name to the way it works, since it alternately works purposefully like a greedy algorithm and circles the target point on the perimeter .

Coordinates instead of recipient name

GPSR is a geo-routing method, i. H. Data packets are not sent to specific recipients, but to coordinates; the packets should then be delivered to the network node that is geographically closest to these coordinates. The prerequisite for this, of course, is that each network node knows its own position in coordinates.

neighborhood

The term “neighborhood” is used in the following. Initially, two nodes are adjacent if at least one of the two can reach the other directly via the communication medium. In an ad hoc network, these neighborhood relationships are not obvious because the use of communication media with limited range - e.g. B. radio - usually not every node can contact each other directly. Later it may be necessary for some nodes to “delete some of their neighbors from memory”, see section Planar graphs are required .

The protocol

Each node in the network performs the following steps when it receives a data packet:

  1. End condition. If your name is in the packet header , you are the node that is closest to the destination. Process the package and do not send it on. Otherwise continue with 2.
  2. Greedy mode. Select the one of your neighbors who is closest to the package's destination coordinates. If this neighbor is closer to the destination than you, send him the package. Otherwise continue with 3.
  3. Perimeter mode . Write your name in the packet header. Look towards the target point and turn counterclockwise until you see the first of your neighbors. Send them the package.

The procedure is explained very humanely here . The actual implementation of the last step determines the angle between the vector “current node - target point” and all vectors “current node - neighboring node” and forwards the packet to the neighbor for whom the smallest deviation angle was calculated. The counter- clockwise direction of rotation is of course chosen arbitrarily, because it is the direction of rotation common in mathematics ; just as well could in be rotated clockwise - only condition is that all nodes use the same direction of rotation.

Planar graphs are a prerequisite

The prerequisite for the correct functioning of the protocol is that the network can be represented as a planar graph : If all nodes are drawn in a coordinate network and all neighboring nodes are connected, these connecting lines must not cross anywhere. If they do, the network must be "leveled" before the GPSR protocol can function correctly - for this some nodes have to "forget" some of their neighbors. What such an algorithm for planarization looks like is discussed in more detail in the article Planar Graph .

If the GPSR protocol is used in a non-planar network, cycles can occur, i. H. a data packet is sent around in a circle over and over again without ever reaching its destination. This is of course undesirable because packets are lost in one cycle and the network is unnecessarily stressed.

literature

  • B. Karp: Challenges in Geographic Routing: Sparse Networks, Obstacles, and Traffic Provisioning. In DIMACS Workshop on Pervasive Networking, Piscataway, NJ, May, 2001
  • B. Karp: Geographic Routing for Wireless Networks. Ph.D. Dissertation, Harvard University, Cambridge, MA, October, 2000
  • B. Karp, HTKung: 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