# A Relative Coordinate-Based Topology Shaping Method for UAV Swarm with Low Computational Complexity
## 4 The Optimal Coordinate Mapping from Initial Topology to Target Topology  
The coordinates of initial and target topology have been derived based on Section 3, and the next step is to determine the target coordinates for each UAV. The optimization model can be expressed by Equations (22)-(25). \[\min C_{g}=\sum_{i=1}^{N}\sum_{l=1}^{N}c_{i,l}M_{i,l},\] (22) s.t. \[\sum_{i=1}^{N}M_{i,l}=1,l=1,2,3,\cdots,N, \tag{23}\] \[\sum_{l=1}^{N}M_{i,l}=1,i=1,2,3,\cdots,N,\] (24) \[M_{i,l}=0\text{ or }1\text{ for all }i,l=1,2,3,\cdots,N. \tag{25}\]  
Equation (22) is the objective function, which reflects the mapping relationship \(M_{i,l}\) with the minimum sum of energy consumption \(c_{i,l}\). Equations (23)-(25) are the constraint conditions of the mapping relationship, which mean only one position in \(\mathbf{Z}\) can be selected for mapping with a node in \(\mathbf{X}\). In this way, the topology shaping problem is transformed into a problem of determining the optimal mapping relationship between \(\mathbf{X}\) and \(\mathbf{Z}\) with minimal global energy consumption. The goal here is to find a mapping relation that minimizes global energy consumption, which has traditionally been formulated as a weighted bipartite graph problem and solved by employing the KM algorithm [24,26,27], the improved KM algorithm [41] or the Auction algorithm [20], even though the computational complexities of these algorithms are relatively high. From the objective function Equation (22) and constraint conditions Equations (23)-(25), we can find that the optimal coordinate mapping can be formulated into a linear assignment problem (LAP), which is also known as a weighted bipartite matching problem. In this paper, in order to obtain a topology shaping with minimal global energy consumption while reducing the computation time, the LAPJV algorithm [41; 42; 43; 44] is adopted to solve the linear assignment problem (LAP). The LAPJV algorithm, which is developed based on some common concepts with the KM algorithm, can significantly reduce the computation time of the whole algorithm by pre-processing the cost matrix and finding the shortest augmentation path. The computational complexity of the algorithm will be analyzed in Section 5.3. The basic idea of the LAPJV algorithm is as follows:  
1. Select an unassigned node in the initial topology **X**. 2. Construct the residual (auxiliary, incremental) graph, \(\mathcal{G}^{\prime}\) with costs \(r_{ij}\). 3. Find the shortest augmenting path via a modified Dijkstra algorithm (recall \(r_{ij}\geq 0\)). 4. Augment the solution to improve the match, construct the auxiliary network and determine from unassigned row \(i\) to unassigned column \(j\) an alternating path of minimal total reduced cost. 5. Update the dual variables so that CS conditions, i.e., \(r_{ij}=u_{i}+v_{j}-c_{ij}=0\), hold. The specific process of deriving optimal coordinate mapping through the LAPJV algorithm consists of two main steps, initialization and augmentation [44]. The input of the LAPJV algorithm is the cost matrix **C**, the rows in **C** corresponding to the nodes in the initial topology, and the columns in **C** corresponding to the positions in the target topology. The element \(c_{ij}\) in matrix **C** is the energy cost from node \(i\) to target position \(j\). The process of the LAPJV algorithm is summarized in Algorithms 2 and 3, and the details are as follows. 1. The initialization phase including three sub-phases: column reduction, reduction transfer, augmenting row reduction. 1. Column reduction. Each element of a column subtracts a positive value. For the input cost matrix **C**, from right to left, subtract the smallest value in the current column from each element in each column of the input matrix, as shown in Algorithm 2 (from line 3 to line 11). In this process, each column is assigned to a minimal row element, and some rows may not be assigned. 2. Reduction transfer, further reducing the unassigned rows.