## 2 Safe and Efficient UAV Route Construction Method over Wireless Multi-Hop Network
### Method for Constructing Optimal Routes in Terms of Distance and Safety Based on OLSR
#### 2.2.3 Method for Constructing Optimal Routes Based on OLSR  
In our protocol, all the nodes are given information about whether they are located in sparsely populated regions or population-dense regions. The OLSR-based method adds several parameters to the HELLO message header. One is the region information of the HELLO message sending node, the others are the region information and the inter-node distances corresponding to each adjacent node: \"Neighbor Interface Address\".  
In order to search for the optimal route considering the distance and safety, the distance and region information obtained from the HELLO message must be advertised to the entire network. Therefore, the region information of the sending node and the distances between the nodes and the region information corresponding to the \"Advertised Neighbor Main Address\" are added to the TC message header. When a node receives a HELLO and TC message, it updates the routing table for each node using the Dijkstra method, using the link cost as the danger-weighted distance for each link. Figure 3 shows the method based on OLSR for constructing optimal route. The link where the UAV moves toward the population-dense region is weighted by multiplying the distance by 3.0 to increase the cost because it is dangerous. The link where the UAV moves toward the sparsely populated region is weighted by multiplying the distance by 0.6 to decrease the cost because it is safe.  
We define our proposed algorithm in graph-theoretic terms based on [PERSON]'s algorithm [41]. Imagine that a node constructs a graphical representation of the network: here, \(N\) denotes the set of nodes in the graph; \(d(i,j)\) denotes the distance between nodes \(i\) and \(j\) in \(N;l(i,j)\) denotes the non-negative cost (weight) associated with the link between nodes \(i\) and \(j\) in \(N;l(i,j)=\infty\) if no link connects \(i\) and \(j\). In the following description, we let \(s\) in \(N\) denote this node; that is, the node executes the algorithm to find the shortest path to all the other nodes in \(N\). Furthermore, the algorithm maintains the following two variables: \(M\) denotes the set of nodes incorporated so far by the algorithm, and \(C(n)\) denotes the cost of the path from \(s\) to each node \(n\). Given these definitions, the algorithm is defined in Algorithm 1.  
```
1:\(M=\{s\}\)
2:for each \(n\) in \(N-\{s\}\)do
3:if no link connects between node \(i\) and \(j\)then
4:\(l(s,n)=\infty\)
5:elseifUAV moves toward the population dense regionthen
6:\(l(s,n)=3.0\times d(s,n)\) {Proposed method original weighting of population-dense region}
7:elseifUAV moves toward the sparsely populated regionthen
8:\(l(s,n)=0.6\times d(s,n)\) {Proposed method original weighting of sparsely populated region}
9:endif
10:\(C(n)=l(s,n)\)
11:endfor
12:while\((N!=M)\)do
13:\(M=M+\{w\}\) such that \(C(w)\) is the minimum for all \(w\) in \((N-M)\)
14:for each \(n\) in \((N-M)\)do
15:\(C(n)=MIN(C(n),C(w)+l(w,n))\)
16:endfor
17:endwhile
```  
**Algorithm 1** Algorithm for constructing optimal UAV routes based on OLSR.  
Basically, the algorithm works as follows. It starts with \(M\) containing this node \(s\) and then initialize the table of costs (the array \(C(n)\)) to other nodes using the known costs to directly connected nodes. We then look for the node that is reachable at the lowest cost \((w)\)  
Figure 3: Method for constructing optimal routes based on OLSR.  
and add it to \(M\). Finally, we update the table of costs by considering the cost of reaching nodes through \(w\). The last line of the algorithm chooses a new route to node \(n\) that goes through node \(w\) if the total cost of going from the source to \(w\) and then following the link from \(w\) to \(n\) is less than the old route we had to \(n\). This procedure is repeated until all nodes are incorporated in \(M\).