# A Relative Coordinate-Based Topology Shaping Method for UAV Swarm with Low Computational Complexity
## 5 Numerical Results
### Computational Complexity  
In this subsection, the computational complexity of the proposed topology shaping method is analyzed and compared. For a UAV swarm system consisting of \(N\) nodes, from Algorithm 2 we can see that the computational complexity of the column reduction process (from line 3 to line 11) is \(O(5N^{2})\). The computational complexity of the reduction transfer process (from line 13 to line 16) is \(O(mN)\), in which \(m\) is the assigned row after column reduction. The computational complexity of the augmenting row reduction process is \(O(RN^{2})\), in which \(R\) is the range of the cost coefficients [42]. From Algorithm 3, we can find that the computational complexity of the augmentation phase is \(O(N^{3})\)[42]. The computational complexity of the Auction algorithm, the KM algorithm, and the improved KM algorithm is shown in Table 3.  
The computation time of the algorithm is a direct indicator of computational complexity. In order to compare the computational complexity of the LAPJV algorithm with the Auction algorithm, the KM algorithm, and the improved KM algorithm, we have conducted 100 sets of simulations for nodes varying from 10 to 1000. An extended comparison of the computation time is shown in Figure 9, in which (a), (b), (c), (d) are the curves of the average computation time of the LAPJV algorithm, the Auction algorithm, the KM algorithm, and the improved KM algorithm as the number of UAVs vary, respectively. As  
Figure 8: Global energy consumption comparison between the proposed method(LAPJV), the Auction algorithm, the KM algorithm, the improved KM algorithm and random mapping. \begin{table}
\begin{tabular}{c c} \hline \hline
**Algorithm** & **Worst-Case Computation Complexity** \\ \hline Auction & \(O(N^{2}log\)\(N)\)[46] \\ \hline KM & \(O(N^{4})\)[41] \\ \hline improved KM & \(O(N^{3})\)[45] \\ \hline \hline \end{tabular}
\end{table} 
Table 3: Comparison of computation complexity. shown in Figure 9e, the LAPJV algorithm always achieves an extremely low computation time compared with the other three algorithms when the number of nodes varies from 10 to 1000. The average computation time of the LAPJV algorithm increases with the number of UAVs but is consistently below 0.5\(s\) for the case of no more than 1000 nodes. More specifically, the average computation time of the Auction algorithm has exceeded 1\(s\) in the case of 90 UAVs, the KM algorithm exceeds 1\(s\) in the case of 390 UAVs, and the improved KM algorithm exceeds 1\(s\) in the case of 640 UAVs. In the case of 1000 nodes, 100 sets of simulations have been implemented to further investigate the proposed method, and the simulation results are shown in Figure 10. The average computation time of the LAPJV algorithm is 0.19 s, while the KM algorithm takes 30.32 s, the improved KM algorithm takes 3.20 s, and the Auction algorithm takes  
Figure 9: Computation time comparison between LAPJV, Auction, KM and improved KM as nodes varies from 10 to 1000. (**a**) Average computation time of the LAPJV algorithm; (**b**) Average computation time of the KM algorithm; (**c**) Average computation time of the improved KM algorithm; (**d**) Average computation time of the Auction algorithm; (**e**) Average computation time comparison of the four algorithms in the same scale. 71.99 s, which means that the LAPJV algorithm reduces the computation time by 99.37% over the KM algorithm, 94.01% over the improved KM algorithm, and 99.73% over the Auction algorithm. From the simulation results, we can see that the computation time of the LAPJV algorithm is much lower than that of the improved KM algorithm, the Auction algorithm, and the KM algorithm, which is due to the fact that the only a small percentage of nodes will perform the augmentation phases (computational complexity \(O(N^{3})\)) after the initialization phase (computational complexity \(O(N^{2})\)). For better illustration, \(10^{4}\) simulations have been conducted trying to identify the reason for the low computational complexity of the LAPJV algorithm.