 |
 |
 |
 |
| |
|
|
|
|
SECAN-Lab Home News Projects SECAN-LAB Mesh Sequencer U-2010 NARTUS EFIPSANS IRMA SECRICOM The Group Members Publications Theses Teaching Presentations Topics Mobile Computing Ad-Hoc Networks Ad-Hoc Protocols Mesh Computing Trust Related Stuff L-101 Laboratory Systems AS28 Systems 802.11 Network Simulator Internships Conferences Publications Standards Projects Links Partners OSTN Miscellaneous Contact About Job Opportunities Search |
Greedy Perimeter Stateless Routing
The Greedy Perimeter Stateless Routing (GPSR) Protocol is a novel routing protocol for wireless datagram networks. GPSR is based on Greedy Packet forwarding.
Greedy Packet forwarding The basic of this Method is, that the source (S) knows the geographic position of the destination (D). This position will be integrated in the route request! The node who has to trade the route request looks in his local table, where the positions of all node in range are listed, which node is the nearest to the destination (like in figure 1). A node between source and destination receives the route request. It looks in his table which node is now the nearest to the D and so on until the data packet arrived on the destination.  Now we come to the Greedy Perimeter Stateless Routing Protocol, who is treating different problems and their solution by the transfer of the data packets. GPSR is an algorithm who combines two different methods of routing. The first method is the Greedy Packet Forwarding method! This method will be used as long as possible, in some case till the Destination. But when the packet arrives on a node, where the node can't find with the Greedy Packet Forwarding a next node, nearer to the destination, and then will be used the second algorithm, the Perimeter Forwarding. On the GPSR Protocol, all node of the network has a local table, in which all neighbour of the node is listed by name (ID) and postion. A proactive Broadcast refreshes this table of each node in a regular time interval. The source node gives the packet a destination address. This address will not be changed by any node who forwards the packet. In the header of the GPSR Packets are many more data, like we see in the following table:
Now, when an node arrives on a point, where with the Greedy Packet Forwarding algorithm could not be found an node nearer to the destination, the Packet mode will be changed into Perimeter Mode an the second algorithm will be active. This mode first tries to send the packet along this empty region to a node nearer to the Destination, like we see on figure 2.  figure 2After this forwarding on the edge of this empty plane, the packet arrives on the node nearer to the destination. First the node will look if one of his edge lies on the vector xD (like in figure 2). When this is the case, the position of this intersection will be stored in the Header on position Lf. With this information, the algorithm tries to find a new edge and new plane, where the packet can be send. To prevent that a packet will pass endless on the edge of a plane, the Headerflag will be set by arriving on the plane. When now the packet arrives on a node nearer to the destination as the Perimeter Modus Position, stored in the Header, the Packet will change back in the Greedy Mode. Now the packet can use again the Greedy Packet Forwarding Algorithm to arrive to the destination. All the pictures and references: Karp2000 & Busche2003 "Greedy Perimeter Stateless Routing" is mentioned on: Ad-Hoc Protocols (Classification) | Ad-Hoc Workshop Winter 04/05 (Termine) |