## 4 Gs-Eera
### Algorithm Procedure  
Step 1 (initialization): Each node broadcasts an initial packet with its location information, and then calculates the distance to the other nodes. Step 2 (updating node information): At the beginning of each time slot, each node exchanges the state information with its neighbor nodes and updates the information in the Neighbor Table. Step 3 (determining the next hop): When the destination is within the communication range of current node, the destination would be selected as the next hop directly;  
When the current node is not a void node, and the \(RFlag\) of the packet to be processed at this time is 1, the \(RFlag\) would be adjusted to 0, and the optimal next hop would be selected from the candidate nodes set according to Formula (27);  
When the current node is a void node, the \(VFlag\) would be adjusted to 0 if it is 1 (i.e., this node cannot become a candidate node of others) and adjusts the \(RFlag\) of the packet to be processed at this time to 1. Then, takes the perimeter forwarding strategy to select the optimal next hop from its neighbor nodes which \(Flag=1\). Step 4: Packet is sent to the next hop. Step 5: Steps 2, 3 and 4 are repeated until the packet is received by destination node. The procedure of main algorithms of GS-EERA is presented in Figure 9, and the pseudocode of GS-EERA is shown in Algorithm 2. Figure 8: Routing hole problem. ```
0: The current node \(i\); The destination node \(D\); The neighbor nodes set of i \(NE(i)\); \(CN=\phi\)
1:for all\(j\in NE(i)\)do
2: Execute Alg.1
3:if\(Flag=1\)then
4:\(CN(i)=CN(i)\cup j\)
5:endif
6:endfor
7:if\(D\in NE(i)\)then
8:\(Relay=D\)
9:else
10:if\(CN(i)\
otin\phi\)then
11: Set the RFlag of current packet to 0. 12:for all\(j\in CN(i)\)do
13: Calculate \(M_{ij}\)
14: find the node with maximum \(M_{ij}\). \(Relay=j\)
15:endfor
16:else
17:\(VFlag=1\)  Set the RFlag of current packet to 1. Select next hop from neighbor nodes with \(Flag=1\) by perimeter forwarding strategy
18:endif
19:endif
20: RETURN Relay

Figure 9: The procedure of GS-EERA main algorithm. ### Algorithm Analysis

#### 4.3.1 Correctness Analysis

According to our algorithm, GS-EERA, it selects next hop with the maximum \(M\) from the candidate nodes set (Formula (27)). Let the average weight of the nodes in a path be \(\bar{M}_{S,D}=\sqrt[k]{\prod_{i=1}^{n}M_{i}}\), where \(m\) is the number of hops from source node \(S\) to destination node \(D\). A routing selection strategy is the optimal if it can select the route with the largest \(\bar{M}_{S,D}\) among all routes from \(S\) to \(D\). If the first \(k-1\) hops of the selected nodes are already the optimal route, i.e., \(\bar{M}_{S,P}=\sqrt[k]{\prod_{i=1}^{k-1}M_{i}}\) (where \(P\) is the \(k-1 st\) node) is the maximum among all routes from \(S\) to \(P\). Assume that \(R\) is the node with maximum \(M\) in the candidate nodes set of \(P\). In the \(kth\) hop route selection, if using GS-EERA, \(P\) selects \(R\) as the next hop and \(\bar{M}_{S,R}=\sqrt[k]{\prod_{i=1}^{k}M_{i}}\). Suppose another superior strategy exists which selects \(R^{\prime}\) as relay node (i.e., \(\bar{M}_{S,R^{\prime}}\) is larger than \(\bar{M}_{S,R}\)),

\[\bar{M}_{S,R^{\prime}}>\bar{M}_{S,R}\Rightarrow\sqrt[k]{\prod_{i=1}^{k}M^{{}^{ \prime}}_{i}}>\sqrt[k]{\prod_{i=1}^{k}M_{i}}\Rightarrow M^{{}^{\prime}}_{k}>M_ {k} \tag{30}\]

that is, the \(M\) of node \(R^{\prime}\) is greater than \(R\). It contradicts our earlier assertion that \(R\) is the node with maximum \(M\) among the candidate nodes set of \(P\). Hence, there is no better strategy than GS-EERA. In fact, we can also see from the above derivation that if a superior strategy exists, that strategy selects the node with the largest \(M\) at every next-hop selection, which is exactly the same as the solution of GS-EERA. As a consequence, we conclude that GS-EERA is the optimal strategy. #### 4.3.2 Complexity Analysis

The given approach, GS-EERA, has different time complexity.