## 4 Proposed Routing Protocol
### Routing Decision Learning Phase  
#### 4.2.1 Markov Decision Process  
In this section, the use of deep reinforcement learning (DRL) to learn how to make routing decisions for UANETs is presented. The Markov Decision Process (MDP) is used to simplify the modeling of reinforcement learning. Hence, we should first model the routing problem as an MDP. As we all know, an MDP consists of the following four tuples \(\langle S,A,P,R\rangle\) where \(S\) is a state space, \(A\) is an action space, \(P\) is the probability of transition from one state to another state, and \(R\) is an immediate reward after a state transition. Consider the following scenario: when the node \(i\) receives a packet, the decision target is to select a neighbor node to forward the packet, while the state is transferred from the current node to the next node, and the process is repeated until the packet delivery fails or succeeds. Based on the above scenario, the MDP can be created as follows. (1) State space: \(S=\{s_{1},s_{2},\ldots,s_{N}\}\) where \(N\) is the total number of nodes in a UANET. the optimal decision of node \(i\) is decided by the information of its neighbors. Therefore, the features of the node can be extracted as follows  
\[s_{i}=\{\left(\left(LS_{i,x},E_{x}^{pre},D_{i,d},D_{x,d},D_{i_{2},d},C_{i,x \to x,d},D_{sum}\right)\mid x\in N_{nbr}(i)\right\} \tag{6}\]  
where \(D_{i,d}\) is the distance between node \(i\) and the destination node \(d\); \(D_{x,d}\) is the distance between the neighbor node \(x\) of node \(i\) and the destination node \(d\); \(D_{i_{2},d}\) is the minimum distance between the two-hop node \(i_{2}\) of nodes \(i\) and \(d\). \(C_{ix\to xd}\) is the cosine similarity of the vector from the last hop node \(i\) to node \(x\) and the vector from node \(x\) to the neighboring node \(D_{sum}=\sum_{i=1}^{8}\min(|L_{i}L_{d}|-|L_{i_{2}}(x,h)L_{d}|,0)\) in [37]; the smaller the \(D_{sum}\), the greater  
Figure 2: DSEGR protocol architecture. the probability the two-hop neighbors of the node can reach the destination node and avoid the void area. (2) Action space: \(\mathbf{A}=\{a_{1},a_{2},\ldots,a_{N}\}\). When the node \(i\) receives a packet, it needs to select a neighbor as the next hop to forward the packet. Thus, optional action of node \(i\) is expressed as \(a_{i}\in\{x\mid x\in N_{\textit{nbr}}(i)\}\), where \(x\) is the the neighbor node \(x\) of node \(i\). (3) Transition probability: The probability of transition between the node \(i\) and its neighbor node is determined by the environment, and it is random and unknown. (4) Reward function: The aim of design reward function R is to make nodes learn how to take a action and achieve faster convergence performance. The reward function of node \(i\) selecting its neighbor node \(x\) is described as  
\[R_{i,x}=\left\{ \begin{array}{ll}100,&\text{if $x$ is destination}\\ -w_{1}D_{x,d}+w_{2}E_{x}^{\textit{pre}}-w_{3}LS_{i,x},&\text{otherwise}\end{array} \right. \tag{7}\]  
where \(w_{1},w_{2}\), and \(w_{3}\) are the weights of the distance between node \(x\) and the destination \(d\), the predicted residual energy of node \(x\), and the link stability between node \(i\) and its neighbor node \(x\), respectively. \(w_{1}+w_{2}+w_{3}=1\). If the neighbor node of node \(i\) is the destination, the reward is 100. If not, the reward value is calculated by weighting the factors considered above. In order to acquire appropriate weights \(w_{1},w_{2}\), and \(w_{3}\), The analytic hierarchy process (AHP) method is used. The AHP structure of the reward function is shown in Figure 3. In our scenario, the target layer of the AHP model is the reward of a selected next hop node. The criteria layer is our above-considered factors. The index layer is the reward of different neighbor nodes. First of all, we need to build the judgment matrix \(A\), which is established by comparing each factor of the criteria layer in pairs. \[A=\left( \begin{array}{ccc}1&2&2\\ \frac{1}{2}&1&1\\ \frac{1}{2}&1&1\end{array}