Greedy Perimeter Stateless Routing in Wireless Networks
Greedy Perimeter Stateless Routing in Wireless Networks (English " Greedy perimeter routing in wireless networks ", abbreviation GPSR ) is a routing protocol for mobile ad -hoc networks, ie, a method by which data packets in spontaneously structured computer networks at their destination should be piloted.
The protocol was developed by B. Karp and owes its name to its functioning as it alternately determined proceeding as a greedy algorithm and the target point circles on the perimeter.
Coordinates instead Recipient Name
GPSR is a geographic routing methods, ie data packets are not sent to specific recipient but to coordinate; the packets are to be delivered to that network node that is geographically closest to these coordinates. Prerequisite for this course is that each network node knows its own position coordinates.
Neighborhood
In the following, the term is "neighborhood " is used. First, two nodes are adjacent if at least one of the two can directly reach the other via the communication medium. In an ad -hoc network this neighborhood relations are not obvious, because by the use of communication media with a limited range - eg radio - can not usually each node each other, contact. Later, it may be necessary that some node " be deleted from the memory," some of their neighbors, see section Planar graphs are required.
The protocol
Each node in the network performs the following steps when it receives a data packet:
The process is explained here very human. The actual implementation of the final step determines the angle between the vector "current node - target " and all vectors "current node - node neighbor " and sends the packet to those neighbors to which the smallest deviation angle was calculated. The direction of rotation counter-clockwise, of course, arbitrarily chosen because it is the usual in mathematics direction of rotation; could equally well be turned clockwise - only condition is that all nodes use the same direction of rotation.
Planar graphs are a prerequisite
Is a prerequisite for the correct functioning of the protocol that the network is represented as a planar graph: one draws all the nodes into a coordinate grid and connects all neighboring nodes, so this connection lines may intersect anywhere. Do they do it but, it must be " cleared " before the GPSR protocol can function correctly the network - to some nodes have to "forget" some of their neighbors. As such an algorithm looks for planarization, in the article A planar graph is discussed in more detail.
If the GPSR protocol used in a non - planar network, cycles can occur, ie, a data packet is repeatedly sent around in circles without ever reaching its goal. This is of course undesirable, because packets are lost in a cycle and the network is claimed unnötigt.