# Topology Duration Optimization for UAV Swarm Network under the System Performance Constraint
## 4 The Proposed GTSC Method
### Optimal Clustering Algorithm  
In order to maximum the topology duration of a UAV swarm network, both current status and dynamic trend of the swarm need to be considered. In the step of clustering, we need to simultaneously take the initial position and group similarity of movement trend into account. That is to say, the topology duration can be prolonged only when nodes with adjacent physical locations and similar mobility are assigned to the same cluster.  
Here, we define a Similarity Map (SIMMAP) for evaluation of both instantaneous and dynamic relation between UAV nodes. Let \(\Delta v_{ij}\) be the velocity difference between node \(i\) and \(j\), respectively. Then we have  
\[\Delta v_{ij}=\left\|\mathbf{v}_{i}-\mathbf{v}_{j}\right\|_{2} \tag{20}\]  
where \(\mathbf{v}_{i}\) and \(\mathbf{v}_{j}\) are the velocity vectors of node \(i\) and \(j\), respectively.  
Let \(\text{sim}_{-}\)\(p_{ij}\) be the position similarity factor, \(\text{sim}_{-}\)\(v_{ij}\) be the mobility similarity factor. Both similarity factors should satisfy following conditions: (i) when \(d_{ij}=0\) and \(\Delta v_{ij}=0\), \(\text{sim}_{-}\)\(p_{ij}=1\) and \(\text{sim}_{-}\)\(v_{ij}=1\); (ii) when \(d_{ij}\rightarrow+\infty\) and \(\Delta v_{ij}\rightarrow+\infty\), \(\text{sim}_{-}\)\(p_{ij}=0\) and \(\text{sim}_{-}\)\(v_{ij}=0\); (iii) \(\text{sim}_{-}\)\(p_{ij}\) and \(\text{sim}_{-}\)\(v_{ij}\) should be monotone decreasing functions of \(d_{ij}\) and \(\Delta v_{ij}\), respectively. Choose the exponential function of \(e\) to fit \(\text{sim}_{-}\)\(p_{ij}\) and \(\text{sim}_{-}\)\(v_{ij}\), then  
\[\text{sim}_{-}\)\(p_{ij}=\left\{\begin{array}{cc}1&d_{ij}\leq R\\ e^{-k\left(d_{ij}-R\right)}&d_{ij}>R\end{array}\right. \tag{21}\]  
and  
\[\text{sim}_{-}\)\(v_{ij}=e^{-\left(\frac{\Delta v_{ij}(i)}{\beta}\right)^{2}} \tag{22}\]  
Figure 3: Flow chart of the proposed GTSC method.  
where \(k\) and \(\beta\) are similarity sensitivity factors. The similarity of node \(i\) and \(j\) (combining instantaneous and dynamic relation) is then calculated by weighted summation of sim\({}_{-}\)\(p_{ij}\) and sim\({}_{-}\)\(v_{ij}\) as  
\[\text{SIMMAP}_{ij}=\omega_{1}*\text{sim}_{-}\)\(p_{ij}+\omega_{2}*\text{sim}\)\(v_{-ij} \tag{23}\]  
where \(\omega_{1}\) and \(\omega_{2}\) are experience factors, and \(\omega_{1}+\omega_{2}=1\). In fact, the similarity of any two nodes can be obtained based on this equation.  
After the evaluation of similarity of swarm nodes, we employ Agglomerative Nesting (AGNES) algorithm to achieve UAV swarm clustering. AGNES algorithm is a down-top hierarchical clustering algorithm with low-complexity [36; 37]. In UAV swarm scenario, the AGNES algorithm is performed under the following three steps: (i) treat each UAV node as an initial cluster; (ii) keep merging two clusters according to the SIMMAP, where the similarity among nodes is used as the evaluation value for merging clusters; (iii) terminate iteration when pre-defined condition is satisfied.  
The Optimal Clustering Algorithm is presented in Algorithm 1.  
```
0:\(\mathbf{U}=\left[\mathbf{u}_{1},\mathbf{u}_{2},\mathbf{u}_{3},\ldots,\mathbf{u }_{N}\right]^{T}\), \(\mathbf{V}=\left\{\mathbf{v}_{1},\mathbf{v}_{2},\mathbf{v}_{3},\ldots,\mathbf{ v}_{N}\right\}\)
0:Cluster set \(\left\{Cluster_{1},Cluster_{2},\ldots,Cluster_{K}\right\}\)
1:for\(i=1\) to \(N\), \(N\) is the number of UAV nodes do
2:for\(j=1\) to \(N\), \(j\
eq i\)do
3: calculate \(SIMMAP_{ij}\)
4:endfor
5:endfor
6:while (the number of nodes of any one clusters less than 5) do
7:if the cluster \(a\) has a minimum average distance value with cluster \(b\)then
8: merge cluster \(a\) and \(b\) into a same cluster
9:endif
10:endwhile
11:return\(\left\{Cluster_{1},Cluster_{2},\ldots,Cluster_{K}\right\}\)
```  
**Algorithm 1** The Optimal Clustering Algorithm