# An Energy-Balanced Geographic Routing Algorithm for Mobile Ad Hoc Networks
## 2 Gpsr  
The GPSR protocol is a geographic routing protocol that takes into account nodes energy and speed of mobility. In the GPSR protocol, nodes are uniformly distributed and know their geographical positions. Firstly, the greedy algorithm is used to forward the data along a straight line, and the nodes forward the data to the nearest neighbor node (using the Euclidean distance). However, if the node is too far from the destination node, the data can not be transferred through a single hop. In this case, there appears a routing void, with the result that the data can not be transmitted. Under this situation, the protocol uses the boundary forwarding algorithm to forward data to the nodes on the void's region boundary. The routing algorithm mainly uses two modes: The greedy algorithm mode and the perimeter forwarding mode. The principles of these two patterns are described as follows.  
GPSR uses a greedy algorithm to establish routing, tag packet with positional information, forward packets according to the position of the destination node, and greedily select the next-hop node. When the source node forwards the data packet to the destination node, the node with the shortest distance to the destination node is selected as the next hop from the neighbor nodes within the communication range of the source node. The process is iterated until there is no node closer to the destination node than the current node (there is a routing void).  
The perimeter forwarding mode mainly uses the right-hand rule for perimeter traversal. However, the right-hand rule cannot be used on non-planar graphs, so the prerequisite for perimeter forwarding is the construction of a planar graph within the communication range, in which any two edges do not intersect [33]. In GPSR, two algorithms, Relative Neighborhood Graph (RNG) and Gabriel Graph (GG), are used to remove the intersecting edges [34; 35]. In the RNG algorithm, the condition for the existence of a link between nodes \(u\) and \(v\) is that the distance between \(u\) and \(v\) is not greater than the maximum distance between \(u\) and \(w\) or \(v\) to \(w\) for any node \(w\). In the GG algorithm, the condition for the existence of edges between nodes \(u\) and \(v\) is that there are no other nodes in the circle where the diameter is \(d(u,v)\).  
If the next-hop node can not be found within the range of the communication radius \(R\) when using the greedy forwarding mode, the routing will be automatically switched to planar perimeter forwarding. When the source node \(S\) has data to transmit to the destination node \(D\), it uses the right-hand rule to find the next-hop node \(a\), as shown in Figure 1. Then, the node position of the switching mode is recorded. If the distance between the next-hop node \(a\) and the destination node is still larger than the distance between \(S\) and \(D\), then the planar perimeter forwarding is continued, otherwise, the greedy forwarding is applied. As shown in Figure 2, when a routing void appears at \(S\), the planar peripheral forwarding is applied. When the node with the plane peripheral forwarding is closer to the destination node than the node with the routing void, it will turn to the greedy forwarding mode, according to the data forwarding rules of the GPSR algorithm. Then, the final path is \(S\to a\to b\to c\to e\to f\to D\).