## 3 FANET Routing Algorithms
### Heuristic-Based Routing Algorithms  
The heuristic algorithms are search algorithms based on experience and illuminating knowledge [78]. Heuristic algorithms can be used to find optimal or sub-optimal solutions in large-scale, complex environments such as SAGINs. Unlike exact algorithms, heuristics can be used in converting NP-hard problems into problems where a solution is found close enough to the optimal solution in an acceptable amount of time [79; 80]. Moreover, as the exact algorithm sets more constraints, it is limited by the size of the network. The trend will be toward large-scale UAV clustering efforts in the future. Routing algorithms for UAVs can be abstracted as a path search problem. Heuristic algorithms are usually based on a search strategy that continuously approaches the optimal routing path through iterative optimization based on the characteristics and constraints of the problem, without searching the entire solution space. As a result, researchers in recent years have used heuristic algorithms as a means of routing optimization. The time and difficulty of solving routing for UAVs with navigation, steering, and uncertain constraints spikes. [PERSON] et al. [81] used a modal algorithm to minimize UAV routing algorithms for three-dimensional flight distances. The algorithm uses a hierarchical architecture combining a meta-heuristic algorithm and a genetic algorithm (GA). Experimental results show that the algorithm proposed by [PERSON] et al. has good stability, but the algorithm is poorly optimized. [PERSON] et al. [82] proposed a routing optimization algorithm combining GA with a simulated annealing algorithm (SA), where GA is used to search for the global optimal position of nodes and SA uses local search operators to avoid trapped local optimal solutions. [PERSON] et al. [83] proposed an improved artificial bee colony algorithm that introduces a cooperative strategy based on the traditional artificial bee colony algorithm (ABC), determines a multi-UAV routing path that satisfies the cooperative requirements by calculating the routing spacing, and uses the routing penalty degree for evaluation. In addition, to avoid the algorithm falling into local optimality, the algorithm uses a slow communication method and replaces the fully connected topology with a ring topology. The algorithm is optimized mainly for energy utilization and routing efficiency. However, the algorithm is limited in terms of the size of the UAV and the number of missions. Particle swarm optimization (PSO) [84] is a widely researched optimization algorithm due to its simplicity, ease of use, global search capability, fast convergence, and parallelizability. These advantages make PSO a relatively mature algorithm with a well-established research base, which is why it continues to attract the interest of many researchers. [PERSON] et al. [85] improve the traditional particle swarm algorithm by introducing an adaptive weight factor and an inertial weight factor to implement a clustered routing algorithm. The study addresses the problem that traditional PSO tends to fall into local optimum solutions by using variable neighborhood search. The algorithm first determines the best clustering head node by using an improved PSO. Other UAVs are then selected to connect to the best clustering head node by comparing distance and energy parameters. Ultimately, data transmission is carried out via the path with the lowest number of hops. This study used energy consumption and network lifetime as optimization objectives, but the study did not explore the performance of this algorithm under large-scale FANET. Similarly, [PERSON] et al. [86] designed a contingent FANET task-driven routing algorithm using a binary particle swarm algorithm and used a weighted time-expansion graph to accommodate dynamic network changes. This study focused the optimization objectives on latency performance and network resource utilization and achieved good results.