GPSR: Greedy forwarding and peripheral forwarding

This is a final assignment for wireless Sensor Networks, which stands for “Greedy Perimeter Stateless Routing”.

This is a stateless routing and forwarding protocol, which can effectively reduce the storage information of each physical node by means of “greedy forwarding” and “peripheral forwarding”.

In addition, it can quickly cope with the frequent changes of node distribution caused by external conditions, node energy consumption and other factors in reality.

So, in particular, to revisit it as a share.

Blog address: godbmw.com/passages/20…

Blog Theme recommended: Theme Art Design, “notes + build knowledge system” weapon.

0. In this paper,

With the increase of routing nodes and the change rate of topology structure, the traditional routing and forwarding protocol algorithm has low efficiency and poor robustness. Greedy perimeter stateless routing protocol (GPSR) only uses neighboring information nodes in the topology to make greedy forwarding decisions. When a packet enters a “routing hole”, the algorithm first constructs a GG or RNG plan and then uses “perimeter forwarding” to bypass this area. In this process, the algorithm will automatically switch between “greedy forward” and “peripheral forward” modes. In topologies with frequent changes or a large number of nodes, and with less information stored on each node, GPSR can quickly respond to changes and query the correct routing path at a low cost.

Keywords: GPSR, greedy forwarding, peripheral forwarding, routing void, planar graph

1. Research background and significance

1.1 Research background and motivation

Present some routing has the characteristics of nodes, the topology changes more quickly, for example: the Ad hoc network (no infrastructure, supports military users, post-disaster relief workers and temporary collaboration), sensor network (consists of small sensor nodes resources), “roof” network (not mobile, but concentrated in metropolitan areas, number of hundreds of thousands of nodes).

The high node cost and message cost of traditional routing algorithm results in low adaptability in high mobility and dense node topology. Therefore, a new routing algorithm with low node cost and high robustness is needed.

1.2 Research Significance

The GPSR algorithm proposed in this paper makes reasonable use of geographic information to achieve high robustness. Improve the robustness and mobility in the case of increasing number of network nodes, reduce the routing protocol message sending cost, the success rate of each routing node message delivery and make each node store the least amount of information.

2. Research status at home and abroad

The DV and LS algorithms proposed in this paper require the mapping of the entire network topology to all routing nodes. In the description of DV algorithm, each routing node records the distance to all network destinations in the latest cycle; In the description of LS algorithm, each routing node will receive the information state related to link change.

When the change rate of topology structure increases, or the number of routing nodes in the routing area increases, the complexity of DV algorithm and LS algorithm will increase, as well as the information reserve of each node and the communication cost between nodes.

Although “caching” technology can reduce node load, existing algorithms still cannot guarantee high robustness and low node overhead when the number of nodes is too large or the rate of topology change is too large.

3. Research content

3.1 Main challenges and innovations

In this way, nodes can store the least amount of information and quickly respond to topology changes. The idea of greedy method needs to be used to make each step the optimal solution. This forwarding process is called greedy forwarding.

However, sometimes the condition of “greedy forwarding” cannot be met, which is called “routing void”. An important technique to solve “routing void” is the “right hand rule”, which is called “peripheral forwarding”. Before peripheral forwarding, the graph needs to be processed into a planar graph, and there are GG and RNG planar graphs for selection.

In the forwarding process, the “greedy forwarding” mode and “peripheral forwarding” mode are switched according to node conditions until the final destination node is reached.

3.2 Introduction to related technologies

In the realization of GPSR algorithm, it is necessary to cooperate with “beacon algorithm” to determine the location information of neighbor nodes.

In the “beacon algorithm”, each node periodically broadcasts a beacon containing the node’s own position information, which is encoded into two 4-byte floating point values that mark the node’s X and Y coordinates. The data format is (IP, (x, y)).

In order to avoid conflicts between beacons sent by neighbor nodes, B is used to represent the time interval between beacons, and the time for nodes to send beacons is uniformly distributed between [0.5B and 1.5b]. Set the maximum time for a node to retain location information as T. If the node still does not receive the beacon sent by the neighbor node after the interval of T, the neighbor node is considered invalid or beyond the coverage range and the corresponding location information is deleted.

With the help of these geographic information, GPSR algorithm can avoid blind flooding of detection packets, so as to carry out effective route forwarding and effective route maintenance for node changes. Even achieve stateless distributed non-end – to – end data forwarding.

3.3 Greedy Forwarding

The greedy forwarding process refers to:

The source node marks the location of the destination node or target region to send the packet.
Each intermediate forwarding node knows the location of its neighbor node, and the forwarding node uses the greedy forwarding strategy when selecting the next hop node of packets, that is, selecting the node closest to the target node as the next hop node.
In this way, each forwarding will get closer to the target node until it reaches the target node.

The principle of greedy forwarding is to use the “greedy” idea to let each node choose the current optimal choice (under the condition that conditions are met) until the end of the algorithm.

As shown in the figure below, according to the greedy forwarding principle, the next hop node of node X is node Y. There is no doubt that greedy forwarding only needs to ensure a neighbor information of the node.

3.3 Greedy forwarding dilemma · Routing void

Routing void means that the current node is closer to the destination node than all other one-hop neighbor nodes. In this case, according to greedy forwarding rules, the current node will not forward data to the one-hop neighbor node. If such a network topology exists, it is called a “routing void”.

As shown in the figure below, the void region is the region that does not meet the “greedy forwarding” condition. Because the coverage of node X and the intersection region of the circle with the radius of line xD have no neighbor nodes.

3.4 Peripheral Forwarding

To solve the problem of “routing void” mentioned above, the algorithm will switch Mode from greedy forwarding to peripheral forwarding, thus bypassing “routing void”.

“Peripheral forwarding” is to judge the next jump node according to the “right hand rule” : connect the current node and the destination node to form a straight line, hold the line with the right hand and rotate it counterclockwise, and the first edge reached (edge means that the two points on it can reach each other) is the direction of the next hop.

3.5 Peripheral forwarding dilemma

Although peripheral forwarding can bypass the “routing hole”, in some cases, simply carrying out peripheral forwarding may fall into an infinite loop and only return to the current node, unable to reach the destination node.

Here is an example to introduce. The figure below is a graph composed of X, W, U, Z and destination node D. The lines between the nodes indicate that the nodes at both ends are adjacent (mutually reachable). So let’s say we start at node X.

Starting from X node, follow the “right hand rule” to arrive at U node, Z node and W node. At this point, the “right hand rule” is applied to the W node again, and the algorithm jumps back to the U node again. Finally, the “right hand rule” is applied to node U, jumping back to the starting node X.

Obviously, at this time the peripheral forwarding into trouble. This is mainly because the map is not a “plan”. To get out of this dilemma, you need to delete some edges to make it a GG or RNG plan.

3.6 RNG plan and GG Plan

If the distance between vertices U, V and any other vertex W is greater than or equal to the distance d(U, V) between vertices U and V, then there exists an RNG edge (U, V) between vertices U and V. It is expressed in the equation as follows:

As shown in the figure below, if (u, v) is an edge in RNG, then the shaded half-moon region between nodes U and V cannot contain any proof node W. At this point, because d(u, v) > Max (d(u,w), d(w,v)), in order to construct RNG plane graph, edges (u, v) must be omitted.

The pseudo-code for the RNG flat implementation is as follows. Where, N is the list of adjacent nodes for any node u, and v is any node in set N.

GG plane graph is defined as: if no other vertex W exists in the circle with diameter UV between nodes U and v, then nodes U and V have GG edges (u, v). It is expressed in the equation as follows:

As shown in the figure below, if (u, v) is an edge in GG, the circular shaded area between nodes U and v cannot contain any proof node W.

The pseudo-code for GG plane implementation is as follows. Where, N is the list of adjacent nodes for any node u, and v is any node in set N.

For both GG and RNG plane plans, RNG plane plans are subsets of GG plane plans. The direct relationship between them can be shown as follows:

3.7 Peripheral forwarding dilemma ·RNG planar graph solved

The construction of the above RNG plane graph or GG plane graph can solve the dilemma that “peripheral forwarding” cannot reach the destination node. Here is an example of constructing an RNG plan, again using the previous figure. For the sake of illustration, the length of xu is 12, the length of Xw is 11, and the length of Uw is 10.

By RNG’s definition, D(U, X) > MAX(D(W, U), D(X, W)), so remove the UX edge. At this point, peripheral forwarding is no longer in trouble.

4. Performance evaluation

To test the performance of the algorithm, the paper uses test data from Carnegie Mellon (Cameron) University. On the unimpeded plane, the nodes of the wireless simulation model move. The node randomly selects a target in the specified area and then randomly selects a speed in the specified area to reach the target and stay there for a period of time. This process simulates the high mobility of the topology and its nodes.

The figure below shows the different B (time interval) cases in which GPSR delivers successful packets. Lowering from B=3s to B= 1.5s did not result in much improvement in success rate, and the success rate remained above 97%.

The figure below compares the node consumption of DSR algorithm and GPSR algorithm. The node consumption of GPSR is much lower than that of DSR, and the node consumption of GPSR is more stable as time goes by.

Therefore, the GPSR algorithm achieves what it was designed for: it can maintain high robustness in a topology with high mobility, and the resource consumption of each node is improved. The paper also compares the node state, path length and other dimensions, which only explains the advantages of GPSR algorithm. The main performance test is the packet transfer success rate and node consumption mentioned above, other tests are not redundant here.

5. Reading experience

In the learning process of this paper, I have mastered “greedy forwarding”, “peripheral forwarding”, “RNG and GG plane graph”, and the most important thing is to understand how to schedule state transformation in GPSR algorithm (greedy => peripheral/peripheral => greedy), and how to solve “routing void” and “peripheral forwarding dilemma”. In addition to the core part of the algorithm, we also understand the realization mechanism of “beacon algorithm” and conflict resolution methods.

In my opinion, compared with the traditional algorithm mentioned in the paper, GPSR algorithm has realized the minimization of node storage data (saving node resources), and can reasonably deal with the topology with high variability by using state switching.

The fly in the wall is the overhead of beacons, which is negligible compared to each node storing information for all nodes.

6. Reference

In the process of reading the paper, I found a lot of Chinese and English materials, which is very helpful to understand the GPSR algorithm described in this paper. This system records the relevant information.

Thesis: GPSR: Greedy Perimeter Stateless Routing for Wireless Networks
Youtube Videos(Hindi)

https://www.youtube.com/watch?v=pC9wNLnWIMc
https://www.youtube.com/watch?v=GisJUKkaHQQ&t=16s&app=desktop
https://www.youtube.com/watch?v=8l7M9lY8y4A&app=desktop

Baidu library lectures (beginning on page 43) : https://wenku.baidu.com/view/c23bcb7bc950ad02de80d4d8d15abe23482f039d.html