# A Low Complexity Persistent Reconnaissance Algorithm for FANET
## 3 Algorithm Description
### Total Edit Distance  
Inspired by the graph edit distance [31; 35], we innovate the Total Edit Distance concept to measure the changes in the FANET and the extent of changes in the threat PDF. Our basic philosophy is to avoid frequent routing updates and iterations to reduce computational overhead and preserve overall efficiency to the greatest extent possible. To do this, we will judge whether to execute overall coordination by sending control instructions through ACP or let each node perform distributed adaptive adjustment according to the range of the TED. Prior to introducing the TED, we briefly describe the graph edit distance [35] here to aid. In graph theory, the graph edit distance measures the dissimilarity between graph \(\Omega_{1}\) and graph \(\Omega_{2}\). Many graph editing operations, such as node and edge additions and deletions, can change one graph into another. With each graph edit operation's cost, the cost of each operation is summed to obtain the total cost of converting the graph \(\Omega_{1}\) to \(\Omega_{2}\), and the smallest cost in this process is defined as the graph edit distance from \(\Omega_{1}\) to \(\Omega_{2}\). Note that different operations usually have various cost functions. Thus, two different sets of operations, with the same outcomes in altering the graph \(\Omega_{1}\) to \(\Omega_{2}\), may be of relatively large distinction regarding the total cost. We first establish the FANET edit distance to measure the change in the FANET. Then, the threat edit distance is defined to record the fluctuation of threat PDF in associated areas, both of which are based on the graph edit distance principle. As a result, the FANET edit distance and the threat edit distance are added to form the TED. Unlike normal graph edit operations, our system does not consider the addition or damage of UAV nodes. So, the node sets are the same at different times. That is to say, the FANET edit operations only contain edge changes, such as edge insertion, edge deletion, and edge length change. We symbolize the FANET as a graph \(\theta(t)\). The graph consists of the set of nodes \(N\), the set of edges \(\sigma(t)\) and their corresponding positions set \(P_{N}(t)\). To transform \(\theta(t)\) to \(\theta(\tau)\), where \(t\) and \(\tau\) are adjacent time with \(t<\tau\), the minimum edge insertions and deletions can be expressed as  
\[d_{1}(t,\tau) =\sigma(\tau)-\sigma(t), \tag{14}\] \[d_{2}(t,\tau) =\sigma(t)-\sigma(\tau), \tag{15}\]  
where \(d_{1}(t,\tau)\) is the edge insert operation between time \(t\) and \(\tau\), the \(d_{2}(t,\tau)\) is the edge delete operation between time \(t\) and \(\tau\), respectively. More importantly, we must pay special attention to the changes in edge lengths since the drones in the FANET move vigorously and frequently. Because the edge length between two nodes is closely related to their communication performance, the optimal routing path may differ from time \(t\) to time \(\tau\). Hence, the total amount of edge length changes between time steps \(t\) and \(\tau\) is how we define the edge length change operation; that is,  
\[d_{3}(t,\tau)=\sum_{i,j\in N}\left|\left\|p_{i}(t)-p_{j}(t)\right\|_{2}-\left\| p_{i}(\tau)-p_{j}(\tau)\right\|_{2}\right| \tag{16}\]  
where \(p_{i}(t)\) stands for the position of node \(i\) in time step \(t\). Note that TED is applicable to simulations of different dimensions. Depending on the simulated scene's dimensionality, the node \(i\)'s position \(p_{i}\) can be equivalent to a two-dimensional \((x_{i},y_{i})\) vector, a three-dimensional \((x_{i},y_{i},z_{i})\) vector, or even a higher-dimensional space vector. We lastly define the threat edit distance to measure the changes in the scenario's threat density distribution at different times. In the duration of a reconnaissance mission,obtaining global information is laborious and impractical. Moreover, each drone in the FANET is threatened by a limited area in our model.