# Cooperative Multi-UAV Collision Avoidance Based on a Complex Network
## 3 Core Algorithm Analysis
### Key Node Selection  
The first problem to solve in an encounter is choosing a key UAV to amend its trajectory to avoid collision. The method proposed herein decides the priority of the UAVs via the analysis of the network formed in the collision space. The most threatened one is chosen as the key node. Obviously, the UAV with the higher priority performs collision avoidance operations first. To clarify, it is necessary to define the collision space. When the system detects a pair of UAVs exhibiting a collision risk, the system obtains all the possible UAV numbers to be hit in the future through global data analysis, and then it obtains the status of the corresponding UAV. The airspace formed by these UAVs is called the collision space. Among them, a connection exists between UAVs that are at the risk of collision, and a network is formed for analysis. An adjacency matrix is applied to record the status between the UAVs. The node represents the UAV, and the edge represents the  
Figure 1: Traffic alert and CA (collision avoidance) system (TCAS) coordination for multi-unmanned aerial vehicles (UAVs). relationship between the UAVs. A set is defined to contain the nodes that satisfy the condition. As shown in Figure 2, the nodes represent the corresponding UAVs. After the network is completed, a network description is established to describe the internal characteristics of the multi-UAV system. The nodes in the network exhibit different properties, because the position and velocity are different and the degree of threat is different. Thus, the key node can be chosen according to its properties. First, the easiest method to measure the degree of threat of the UAVs is by examining the situation of the connected edges in the network; this is called the key node selecting method based on degree. To render the network closer to the real scene, it is insufficient to only use the number of edges. The degree approach requires more detailed information, and the edge is a good choice. The edges should contain extra properties to monitor the true relationship of the UAVs. The relationship includes the distance and relative speed between UAVs. The closer a pair of UAVs is to each other, the more dangerous they are. Therefore, the weight of each side depends on the relative distance and relative speed between the UAVs, which is defined as the edge weight between the UAVs:  
\[\omega_{ij}=\frac{\vvet{v_{ij}}\cdot\vvet{d_{ij}}}{\left|\vvet{d_{ij}}\right| \cdot\vvet{d_{ij}}} \tag{10}\]  
where \(\vvet{v_{ij}}\) is the relative speed of the vector direction, and \(\vvet{d_{ij}}\) represent the distance between the UAVs. This implies that the faster the two UAVs approach each other, the greater is the weight of the edge between the two UAVs. The degree of importance of each node can be based on the weight of all edges. The summed value represents the degree of importance of the node. There are many other methods to rank the importance of nodes [34; 37]. Another improved method based on node contraction [38] proposed herein aims to excavate the deeper threat of the UAV networks. There are three reasons for using the node contraction method in selecting the key node: First, the principle of key node selection is to fully exploit the importance of the node, for which the network cohesion is a good measure. The choice of key nodes is not only related to the current degree, it is also to the location of the node. If the node is in the fortress position, shrinking the node will result in a much smaller average path length of the network, resulting in greater network cohesion. This method to obtain key nodes is consistent with the key node selection requirements of the UAV group in performing CA operations, i.e., to determine the current and potential threats of the drone to perform CA. Second, the node contraction method has a shorter calculation time than the node deletion method and the median method, and it does not exponentially increase when the number of nodes is small.