## 4 Dueling DQN-Based Routing Protocol
### Markov Decision Process  
In order to use the RL algorithm to solve the routing problem, the packet-forwarding process should be modeled as a Markov decision process (MDP). An MDP consists of four tuples \(\{S,A,R,P\}\), where \(S\) is the state space, \(A\) the is the action space, \(R\) is the reward function, and \(P\) is the state transfer probability. According to our UAV-routing scenario, the specific definitions of these tuples were the following:  
(1) State space: \(S=\{s_{1},s_{2},\ldots,s_{N}\}\), where \(s_{i}=\left\{d_{i,j},d_{j,d},d_{i\overline{s},d},d_{\text{sum}}\,LQ_{i,j},DIR_{i,d},T_{j}^{\text{wait}}\right.\)\(\left.\right|\left.j\in Nbr(i)\right\}\), and \(d_{ij,j}\) is the distance between current forwarding node \(i\) and its candidate forwarding node \(j\). In addition, \(d_{j,d}\) is the distance between candidate forwarding node \(j\) and destination node \(d\). We used the expression of neighboring topology information \(NF_{x}=(d_{1},d_{2},\cdots,d_{8})\) to predict the location of the two-hop neighboring nodes of the current forwarding node in different regions [19]. The predicted location of the two-hop neighboring nodes was expressed as the following: \(L_{2}(n,i)=l_{i}+d_{j}\left(\cos\frac{(1+2)\pi}{8},\sin\frac{(1+2)\pi}{8}\right)\), where \(d_{j}\) indicates the farthest distance between the current forwarding node and its neighboring node in the \(j\)th region, and \(l_{i}\) is the location of node \(i\). The feature \(d_{i\overline{s},d}\) is the minimum distance between the predicted two-hop neighboring nodes and the destination node in the \(n\) regions. Then, \(d_{\text{sum}}=\sum_{i=1}^{8}\min\left(\left|l_{i}d_{j}\right|-\left|l_{j}(x, n)l_{d}\right|,0\right)\), if \(d_{\text{sum}}\) was smaller, which indicated a larger probability of mitigating the routing void, where \(l_{d}\) and \(l_{d}\) are the location of destination node \(d\) and node \(j\), respectively, \(LQ_{i,j}\) is the link quality of the link \(L_{i,j}\), and \(T_{j}^{\text{wait}}\) is the total waiting time of packets in node \(j\) at the current time. The feature \(DIR_{i,d}\) was used to learn to avoid selecting a candidate forwarding node that was traveling far away from the destination node, which decreased the probability of packet transmission success. The specific expressions of \(DIR_{i,d}\) were expressed as follows:  
\[\text{DIR}_{i,d}=\frac{\overrightarrow{V_{j}}\cdot\overrightarrow{l_{i}l_{d}} }{\left\|\overrightarrow{V_{j}}\right\|\left\|\overrightarrow{l_{i}l_{d}} \right\|} \tag{10}\]  
where \(\overrightarrow{V_{j}}\) is the velocity vector of candidate forwarding node \(j\), \(l_{i}\) is the location of last-hop forwarding node \(l\), and \(\overrightarrow{l_{i}l_{d}}\) is the vector of node \(i\) to destination node \(d\). If \(0<\text{DIR}_{i,d}<1\), then candidate forwarding node \(j\) was traveling closer to node \(d\). If \(-1<\text{DIR}_{i,d}<0\), then \(j\) was traveling farther away from node \(d\). All these features were designed so the agents could quickly learn the optimal policy. Additionally, different features had different units and scales. We normalized these dimensional features into dimensionless features for data processing convenience and accelerating the Q-network convergence. In our study, we adopted the min-max normalization method. (2) Action space: where \(A_{i}=\{a_{1},a_{2},\ldots,a_{n}\}\) is the set of neighboring nodes within the communication range of current forwarding node \(i\), and \(n\) is the total number of neighbor agents. The action was selected when the current forwarding node needed to forward a packet. (3) Transition probability: \(P:S_{i}\times a_{i}\times S_{j}\rightarrow[0,1]\) defined the probability that the current state would transition to the next state after taking an action. (4) Reward function: \(S_{i}\times A_{i}\to R\) was a critical component. A well-designed reward function could ensure the algorithm would converge faster while also improving network performance.