## 2 Modeling of UAV-Assisted Communication
### Optimization Mathematical Model  
In the UAV-assisted emergency communication discussed above, we propose the air-to-ground communication model and simulation of the user evacuation trajectory. The optimization mathematical functions are defined in this section, followed by complexity analysis.  
The main task is to recover the interrupted service and enhance communication quality; thus, we set the total throughput as the objective function in optimization, as shown in Equation (8). In the planning model with \(K\) users and \(N\) time slots, user location, bandwidth division, and transmission power are considered decision variables. Both uplink and downlink communication happens, regarding the UAV as the aerial base station.  
\[R_{i,n}=\frac{1}{2}\cdot B_{n}\cdot[log_{2}(1+SINR_{ug})+log_{2}(1+SINR_{gu})]. \tag{8}\]  
Subscript \(i\) represents the current moving user and subscript \(n\) represents the current time slot. Moreover, design for constraint functions is also necessary. In the above discussions, it can be seen that the objective function consists of the bi-directional arriving rate \(R_{i,n}\) at each resource block. On one side, as UAVs have real physical characteristics, the energy, velocity, and power are limited. On the other, the communication resource is also limited, involving maximum bandwidth.  
Therefore, the constraint variables are divided into 3 sets, which are \(U=[v_{n},a_{n}]\), \(B=[B_{n}]\), and \(P=[E_{n}^{C},E_{n}^{F},P_{n}]\), referring to variables of UAV's location and velocity, variables of bandwidth resource, and variables of energy and power consumption. \(E_{n}^{C}\) represents communication energy cost at time slot \(n\), and \(E_{n}^{F}\) refers to flight consumption. To ensure data communication, the lower bound of \(R_{i}\) is also specified. The total optimization functions are shown in Equation (9),  
\[\max_{UBP} \sum_{n}^{N}\sum_{i}^{K}R_{i,n} \tag{9}\] \[s.t. \left\{\begin{array}{l}0\leq P_{u}\leq P_{max}\\ \sum_{i}^{C}E_{i,n}+E_{n}^{F}\leq E_{max}\\ \sum B_{i,n}\leq B_{i}\\ v_{n}\leq v_{max}\\ R_{min}\leq R_{i}\end{array}\right.\]  
Figure 4: Grid map of valid evacuation area. The area includes obstacles, one exit, and 10 ground users in the simulation. Each grid equals a square area of \(1\) m \(\times\) 1 m in actual simulation.  
The complexity of the discussed problem is proved to be NP-hard (non-deterministic polynomial-time hard) in this section, which can reveal the significance and effectiveness of our algorithm.  
NP means a problem can not be resolved in polynomial time, and all the NP problems can reduced to the NP-hard problem. Reduction is a reversible process, which means that the solvers of both problems can be transformed into one. Therefore, any certain problem can be proved NP-hard if it can be reduced to other typical NP-hard problems.  
According to the list of proven NPH problems, the bounded knapsack problem (BKP) is a NPH model with a basic optimization model:  
\[\begin{split}\max&\sum_{i=1}^{n}v_{i}x_{i}\\ s.t.&\big{\{}\ \sum_{i=1}^{n}w_{i}x_{i}\leq W, \quad x_{i}\in 0,1,2,\ldots,c\end{split} \tag{10}\]  
\(x_{i}\) refers to decision sequence, while \(w_{i}\) stands for weight cost and \(v_{i}\) represents value. Similarly, in our problem, the decision sequence for UAV aims to maximize total throughput with certain \(v_{i}\) factors, and weight constraints are controlled in the communication energy aspect. Thus, our problem can be reduced to a bounded knapsack problem, which indicates the NPH characteristic of our model. Therefore, the joint optimization problem discussed can only achieve an approximate solution, necessitating highly accurate algorithms.