# 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
Consider row 3 of Figure 1(b), we perform an inverse column reduction, which is to add the minimum element of row 3, i.e., 4 to column 3, the result of reduction transfer of row 3 is depicted in Figure 1(c). Apply row reduction to row 3, and the result is illustrated as Figure 1(d). The third step of the initialization phase is augmenting row reduction. Starting from unassigned row 1, the minimum element in row 1 is 2 (column 2) as depicted in Figure 1(d), and the second minimum element is 2 (column 4). All the elements in row 1 are reduced by 2, and the result is depicted in Figure 1(e). Perform inverse column reduction on column 2 and assign row 1 to column 2 and we obtain Figure 1(f). Then the unassigned row is row 4. Perform the same augmenting row reduction procedure on row 4, and we obtain the result as shown in Figure 1(g). The current unassigned row is row 2. Perform augmenting row reduction on row 2, and we obtain the result as depicted as Figure 1(h). Then, the assignment is row 1 assigned to column 2, row 2 is assigned to column 4, row 3 is assigned to column 3, and row 4 is assigned to column 1. All rows are assigned after augmenting row reduction. ```
1//Augmentation
2 forallunassigned\(i^{*}\)do
3 for\(j=1\) to ndo
4\(d_{j}=c_{i^{*}j}-v_{j}\);
5\(pred_{j}=i^{*}\);
6\(READY=\{\}\); \(SCAN=\{\}\); \(TODO=\{1,2,3..n\}\);
7 whiletruedo
8 if\(SCAN=\{\}\)then
9\(\mu=min\{d_{j},j\in TODO\}\);
10\(SCAN=j\), \(d_{j}=\mu\);
11\(TODO=TODO-SCAN\);
12
13 forall\(j\in SCAN\)do
14 if\(y_{j}=0\)then
15 go to augment;
16\(SCAN=SCAN-\{j^{*}\}\); \(READY=READY+\{j^{*}\}\);
17 forall\(j\in TODO\)do
18 if\(\mu+cred_{ij}<d\)then
19\(d_{j}=\mu+cred_{ij}\); \(pred_{j}=i\);
20 if\(d_{j}=\mu\)then
21 if\(y_{j}=0\)then
22 go to augment;
23 else
24\(SCAN=SCAN+\{j\}\);
25\(TODO=TODO-\{j\}\);
26
27
28
29\(augment\) :
30 forall\(k\in READY\)do
31\(v_{k}=v_{k}+d_{k}-\mu\);
32 while\(i\
eq i^{*}\)do
33\(i=pred_{j}\); \(y_{j}=i\); \(k=j\); \(j=x_{i}\); \(x_{i}=k\);
34
35 return\(\mathbf{M}_{o}\), \(c\)
```  
**Algorithm 3**Augmentation Process of LAPJV  
Then, according to the mapping relationships derived by Algorithms 2 and 3, the target position of each UAV can be obtained with minimum global energy consumption. The LAPJV algorithm is a clever shortest augmenting path implementation of Hungarian which preprocesses the cost matrix by column reduction, reduction transfer, and reduction in unassigned rows, therefor the LAPJV algorithm does not need to perform the augmentation phase (Algorithm 3) too many times. From the examples given above, it is possible that the LAPJV algorithm has already completed the assignment in the initialization phase. Although the worst-case computational complexity of the LAPJV algorithm and the improved KM algorithm is \(O(N^{3})\)[45], in practice, the LAPJV algorithm takes less computation time in deriving the optimal mapping, thus the LAPJV algorithm is employed to solve the problem of optimal topology shaping. \[ \begin{bmatrix}14&5&8&7\\ 2&12&6&5\\ 7&8&3&9\\ 2&4&6&10\end{bmatrix} \quad \begin{bmatrix}12&1&5&2\\ 0&8&3&0\\ 5&4&0&4\\ 0&0&3&5\end{bmatrix} \quad \begin{bmatrix}12&1&9&2\\ 0&8&7&0\\ 5&4&4&4\\ 0&0&7&5\end{bmatrix} \quad \begin{bmatrix}12&1&9&2\\ 0&8&7&0\\ 1&0&0&0\\ 0&0&7&5\end{bmatrix} \]  
(a) (b) (c) (d)  
The proposed topology shaping method is shown in Figure 3, and the specific process is as follows:  
1. Obtain the initial and target coordinates matrices \(\mathbf{X}\) and \(\mathbf{Z}\) by Algorithm 1. 2. Obtain the optimal coordinate mapping relationship \(\mathbf{M}_{o}\) by Algorithms 2 and 3. 3. Achieve the topology shaping based on the optimal coordinate mapping relationship \(\mathbf{M}_{o}\).