## 2 Safe and Efficient UAV Route Construction Method over Wireless Multi-Hop Network
### UAV Navigation Network Topology  
Mobile ad hoc networks (MANETs) [32] are typical network topology construction techniques for relaying multiple radio terminals. MANET routing protocols can construct the shortest route between source and destination nodes, as shown on the left side of Figure 2. Among them, Optimized Link State Routing Protocol (OLSR) [33] is known as a  
Figure 1: UAV navigation route construction by wireless multi-hop network. typical proactive type, and Ad hoc On-Demand Distance Vector (AODV) Routing [34] is a typical reactive type. Any route for the UAV navigation must be safe and efficient. Thus, the route requires bypass nodes in population-dense regions as much as possible to ensure safety [31]. For this purpose, we consider two levels for the network configuration. The higher level composes the transmission network with nodes in sparsely populated regions. This level is used as the preferred route because it is safe. The lower level is the access network with nodes in population-dense regions that connect to the transmission network via the shortest route. The right side of Figure 2 shows an example of the network configuration suitable for UAV routing. The optimal route is a safe route with a short \"population-dense regions distance\". In order to avoid the risk of running out of battery power, it is also desirable that the \"total distance\", which is the distance from the source node to the destination node, is not too long in terms of efficiency. [PERSON], et al. propose a method to reliably determine the location of waypoints that construct the routes of UAVs [35]. [PERSON], et al. proposed a hybrid differential evolution (HDE) algorithm to generate a high-quality and feasible route for fixed-wing UAVs in complex three-dimensional environments [36]. A multi-objective function is designed, and both the route length and risk are optimized. We have studied two protocols for UAV navigation. One protocol is based on OLSR, which constructs routes using the Dijkstra method [37]. The link cost is a danger-weighted distance. The other is based on AODV, in which each relay node evaluates the received route request (RREQ) messages in terms of the route safety and the flight time. The relay node selects and forwards the better RREQ message to construct an optimal route [38]. The node which receives \(i\)-th RREQ adds the distance in the passage area counter of the RREQ. The node evaluates the \(i\)-th received RREQ message with \(i\) as the decision variable equivalent of the optimization problem, using the objective function equivalent of Equation (1); then, the node records and sends the best \(i\)-th RREQ. The destination node transmits a route reply (RREP) through the best route. By weighting the travel time of each node and taking the minimum value, both the safety and the time perspectives are comprehensively determined. \(\alpha(0\leqq\alpha\leqq 1)\) is a balanced value for time and safety perspectives, i.e., a factor to avoid population-dense regions from the viewpoint of safety; \((1-\alpha)\) is a factor to shorten the total travel time. In the route from the source node to the node that receives \(i\)-th RREQ, \(D_{i}\) is the sum of the distances between the nodes in the population-dense region and half the sum of the distances between the nodes in the sparsely populated region and the nodes in the population-dense region. \(S_{i}\) is the sum of the distances between nodes in the sparsely populated region and half the sum of the distances between the nodes in the sparsely populated region and the nodes in the population-dense  
Figure 2: Network configuration suitable for UAV routing. region. \(v1\) is the speed of the UAV heading to the node in the population-dense region, and \(v2\) is the speed heading to the node in the sparsely populated region. \(v1\) and \(v2\) are set in all nodes.