Conflict Resolution Strategy Based on Flight Conflict Network Optimal Dominating Set

Abstract

Aiming at the problem that the air traffic flow is increasing year by year and the flight conflicts are difficult to be deployed, we take aircraft as the node and established a flight conflict network based on the flight conflict relationship between aircrafts. After that, we define the concept of an optimal dominating set. By removing the optimal dominating set nodes of the flight conflict network, the conflicts in the network can be quickly resolved and the complexity of the network is reduced. In the process of solving the optimal dominating set of the network, we introduce the immune mechanism based on the particle swarm algorithm (PSO) and ensure the priority deployment of a critical aircraft and high-risk conflicts by setting two types of antigens, nodes and connected edges. Compared with the traditional method, the conflict resolution strategy presented in this paper is able to quickly identify key aircraft nodes in the network and has better sensitivity to high-risk conflict edges, which can provide controllers and the control system with a more accurate and reliable suggestion to resolve the flight conflicts macroscopically.

This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

1. Introduction

In recent years, the world’s air traffic industry has achieved unprecedented development. By the end of 2019, China has built 992 air routes, with a total mileage of 234,509 km, and 527 waypoints exceeding the intersection of three or more air routes. With the development of aviation industry, China’s air traffic system has become more and more complex, resulting in increasing risk of flight conflicts and huge pressure on air traffic control. Taking effective measures to manage the flight conflicts between aircrafts will alleviate this pressure and ensure the safety and smoothness of air traffic operation. Therefore, providing a fast and reliable solution to the conflict has become an urgent problem to be solved.

The research on flight conflict resolution can be generally divided into two kinds, one is the macroconflict resolution, and the other is the specific one. Macroconflict resolution focuses on the overall operation of the airspace. Based on the current air situation, this kind of resolution method can provide controllers with reasonable and feasible suggestions for flight conflict resolution. In contrast, specific conflict resolution provides reasonable maneuvering opinions for aircraft through geometry, probability, control, game, and other theoretical analysis for a given type of conflict event [1–8]. We focus on conflict resolution at the macrolevel. Huang et al. proposed a compact structure of aircraft flows at airway intersections to solve the conflict problem at the intersection of aircraft flows. This method can ensure that more aircraft pass through the fixed area safely and improve the airspace capacity at airway intersections [9]. Hong et al. described conflict resolution as a mixed integer linear programming problem under the constraints of aircraft maneuverability. A two-layer structure was adopted to solve conflicts between aircrafts, avoiding conflicts between aircrafts and ensuring smooth transition to adjacent airspace [10]. Valenzuela et al. proposed a conflict detection and resolution method based on aircraft intention parameterization, which expressed the conflict resolution problem as a constrained parameter optimization problem and deployed them accordingly [11, 12]. Cafieri and Rey adopted mixed integer nonlinear programming for modeling to minimize the number of conflicts or to ensure the maximum number of conflict-free aircraft. The deployment of two-aircraft conflict detection unit reduces the size of the conflict model and improves the computational efficiency [13].

The conflict relationship between aircrafts is nonlinear and complex, and the complex network is an important tool to research this kind of system [14]. In recent years, complex network has been applied in the field of transportation [15–17], and some scholars have analyzed and resolved the conflict between aircrafts through the complex network theory. Wang et al. determined the intrinsic complexity of aircraft set according to the proximity effect between aircrafts and built a complex network model [18]. Jiang et al. took the aircraft as the network node and the ACAS communication between aircrafts as the edge to establish the aircraft state network. By analyzing the indexes of the network, they found the key aircraft nodes in the airspace and provided the flight conflict resolution plan for controllers [19]. Huang et al. applied complex network to conflict resolution of UAV swarm, identifying key UAV by edge weights and resolving them in the direction of reduced network robustness. [20]. However, these methods only consider the position information of the aircraft to build network edges, which cannot accurately reflect the conflict relationship between aircrafts. The velocity obstacle method can combine the speed, direction, and protection area information of the aircraft and predict flight conflicts in advance through geometric method [21, 22]. In this paper, the velocity obstacle method is used to judge the conflict relationship between aircrafts and construct the conflict network. In this paper, the velocity obstacle method is extended to three dimensions, which is used to judge the conflict relationship between aircrafts, and the network is constructed. After improvement, the model can adapt to the complex situation of multiple flight levels and aircraft passing through the flight levels.

In the flight conflict network, the deletion of the aircraft nodes will affect the structure and performance of the network. By analyzing the network, the key aircraft that can quickly reduce the complexity of the system after deletion will be found to provide controllers with a macroresolution strategy. The problem of macroconflict resolution can be transformed into the identification of the conflict network key nodes. Commonly used methods for identifying key nodes in complex networks include degree sorting, betweenness centrality or closeness centrality sorting, $k$-shell decomposition, and PageRank method [23–25], which have good accuracy in identifying key nodes in the network. However, in the process of flight conflict resolution, the simple node identification method may ignore the urgent flight conflict edges, thus affecting flight safety. Therefore, it is necessary to identify the key nodes and edges of the network at the same time. The community method allows dividing the network into several sets of nodes and edges. [26–28], but it is difficult to judge the importance of each community. Li et al. applied the concept of minimum connected dominating set (MCDS) to complex networks. This method can simultaneously identify key nodes and edges in the network, which is of practical significance for the study of network destruction resistance and the construction of backbone networks [29]. However, in the actual conflict resolution process, for the conflict between two aircrafts, controllers usually only need to deploy one of them to resolve the conflict, so the value of connectivity in the conflict resolution problem is limited.

To sum up, this paper proposes a conflict resolution strategy based on the optimal dominating set of the complex network and optimizes the structure of the dominating set through the optimal performance index, so as to provide reasonable suggestions for controllers to resolve flight conflict. The content of each section is arranged as follows.

In Section 1, we develop a flight conflict network model with the aircraft as network nodes and potential conflict relationships as edges. In Section 2, we introduce the concept of dominating set, propose the optimal dominating set, and analyze its practical significance in conflict resolution. In Section 3, we introduce the particle swarm optimization algorithm and immune mechanism and analyze its advantages in solving the optimal dominating set problem. In Section 4, we describe the conflict resolution strategy based on the optimal dominating set of complex networks and detail the deployment process. In Section 5, we demonstrate the feasibility and advantages of the proposed approach in conflict resolution through simulation experiments.

2. Flight Conflict Network

The flight conflict network is a complex network composed of aircraft (nodes) and conflict relations (edges), expressed as $G=V,E,W$. Among them, $V=v_1,v_2,v_3,\cdots ,v_n$ is a set of nodes in the network, corresponding to each aircraft in the airspace; $E=e_1,e_2,e_3,\cdots ,e_n$ is the set of edges, which reflect the conflict relationship between aircraft; $W=w_1,w_2,w_3,\cdots ,w_n$ is the set of network weights, and the weights of edges reflect the urgency of potential conflicts in the flight conflict network.

We divide the judgment of the potential conflict relationship between aircraft (that is, the edge of the flight conflict network) into two steps. Firstly, we determine the positional relationship between the nodes, that is, the corresponding aircraft of the nodes need to be close at the position. As shown in Figure 1, the aircraft’s position detection area is defined as a cylindrical area with radius of $D_1$ and height of $2D_v$. In this paper, the value of $D_1$ is taken as the TCAS communication response distance of 26 km, and the value of $D_v$ is taken as the height of an altitude layer of 300 m.

[figure(s) omitted; refer to PDF]

If the aircraft enters the detection area, it is necessary to further judge whether there will be a conflict between them. Here, we introduce the velocity obstacle model. According to the geometric rules, the velocity obstacle model limits the relative velocity range of potential conflict in two dimensions. When the velocity of the target relative to the obstacle is within this range, the potential conflict is judged. As shown in Figure 2, the spaces between target $A$ and obstacles $B$ is $\mid AB\mid$. The safe protection area of aircraft $B$ is a circle with $B$ as the center and $d_l$ as the radius. The velocity of $A$ is $v_A$, the velocity of $B$ is $v_B$, and the velocity of $A$ relative to $B$ is $v_r=v_A-v_B$. Crossing point $A$ makes tangent lines to both sides of $eB$, and the region formed is called velocity obstacle cone. When the direction of relative velocity $v_r$ is inside the velocity obstacle cone, it will be judged that there is a potential conflict between $A$ and $B$.

[figure(s) omitted; refer to PDF]

In previous studies, the velocity obstacle model is mainly used for robot obstacle avoidance, and it only needs to satisfy the two-dimensional velocity obstacle relationship. In the judgment of flight conflict, the altitude information needs to be considered, so the model is extended into three dimensions. As shown in Figure 3, aircrafts are required to maintain a certain vertical or horizontal interval between each other in flight. This paper establishes an ellipsoidal flight protection zone for aircraft, whose equatorial radius $a=b=d_l$ and polar radius $c=d_l$.

[figure(s) omitted; refer to PDF]

If the coordinate of aircraft $B$ is $X_B,Y_B,Z_B$, then the expression of the ellipsoidal flight protection zone is $$\begin{array}{}\text{(1)}& \frac{{x-X_B}^2}{{d_l}^2}+\frac{{y-Y_B}^2}{{d_l}^2}+\frac{{z-Z_B}^2}{{d_v}^2}=1.\end{array}$$

We assume that a certain error is allowed between the aircraft and the altitude layer in flight, so $d_l=10$ km and $d_v=290$ m are set in this paper.

As shown in Figure 4, when the direction of $v_r$ is within the angle range of the three-dimensional velocity obstacle cone, it means that if no deployment were made according to the current motion state, aircraft $A$ will enter the flight protection area of $B$ and flight conflict will occur.

[figure(s) omitted; refer to PDF]

Let the coordinate of aircraft $A$ be $X_A,Y_A,Z_A$. Point $C$ is the intersection of $eB$ and the line of point $A$ in the $v_r$ direction. The direction vector of $v_r$ is $v_x,v_y,v_z$. Then, according to the point-direction expression of the three-dimensional line, $AC$ can be expressed as $$\begin{array}{}\text{(2)}& \frac{x-X_A}{v_x}=\frac{y-Y_A}{v_y}=\frac{z-Z_A}{v_z}.\end{array}$$

Equations (1) and (2) are established together. If the system has two solutions at the same time, the line and surface have two points of intersection, $C_1$ and $C_2$, whose coordinates are $x_1,y_1,z_1$ and $x_2,y_2,z_2$, respectively. Let $\gamma$ be the included angle between $v_r$ and the position vector $AB$. If two aircrafts satisfy $\gamma <{90}^{°}$, that is, $\cos \gamma >0$, then the direction of $v_r$ is within the obstacle cone, and there is a potential flight conflict between the two aircraft, and an edge is formed in the node pairs. $$\begin{array}{}\text{(3)}& \cos \gamma =\cos <v_r,AB>=\frac{v_r\cdot AB}{v_{r}AB}.\end{array}$$

In this paper, the negative exponential function of the estimated collision time $t_c$ is used as the weight of the edges between nodes in the network. We define the estimated conflict time: if the aircraft keeps its original flight state, the time at which the conflict is predicted to occur, which is expressed by parameters in the model as $$\begin{array}{c}\text{(4)}& t_c=\frac{AC}{v_r},w_{ij}=\exp -t_c,\end{array}$$where $w_{ij}$ represents the weight of the edge between node $i$ and node $j$ and $v_r$ is the relative velocity of aircraft $A$ relative to aircraft $B$. $\mid AC\mid$ represents the distance between aircraft $A$ and $C$. $$\begin{array}{}\text{(5)}& AC=\min {AC}_1,{AC}_2.\end{array}$$

Selecting the negative exponential function of the $t_c$ as the weight has the following advantages: (1) The negative exponential function is a decreasing function in its definition domain, and the larger the value of $t_c$, the smaller the weight, reflecting the weaker conflict intensity. (2) When building an edge, the value of $t_c$ is greater than 0, so the range of the negative exponential function is $0,1$, which can play a role in unifying the weight. (3) The absolute value of the slope of the negative exponential function increases gradually with the decrease of the independent variable that can reflect the urgency of potential flight conflict changes sharply in the process of decreasing $t_c$, which is consistent with the actual conflict situation.

In Figure 5, there are six aircraft operating at two flight levels. The yellow aircraft represents the aircraft in the upper flight level, and its altitude is 0.3 km; the orange aircraft represents the aircraft in the low flight level, and the blue aircraft represents the aircraft climbing or descending between the flight levels. From Figure 5, we can see that there are 2 potential conflicts for aircrafts 1 and 3, and there is 1 potential conflict for aircrafts 2, 4, 5, and 6. The conflict relation of the aircraft pair in the airspace is abstracted as an edge between nodes, and we can obtain the corresponding flight conflict network. For the convenience of expression and calculation, we use the weight matrix to reflect the relationship between nodes and edges in the network. The weight matrix corresponding to the network in Figure 5 is $$\begin{array}{}\text{(6)}& W=\begin{array}{cccccc}0& 0.285& 0.571& 0& 0& 0\\ 0.285& 0& 0& 0& 0& 0\\ 0.571& 0& 0& 0& 0.745& 0\\ 0& 0& 0& 0& 0& 0.726\\ 0& 0& 0.745& 0& 0& 0\\ 0& 0& 0& 0.726& 0& 0\end{array}.\end{array}$$

[figure(s) omitted; refer to PDF]

3. Optimal Dominating Set

3.1. Dominating Sets

Dominating set is a concept in the graph theory. Points in the dominating set are connected to all the other points in the graph. For the conflict network, the aircraft node in the dominating set is in conflict with others in the network, that is, it connects all the aircraft in conflict. Therefore, the dominating set has value and practical significance for macroconflict resolution; we introduce the concept of dominating set in the flight conflict network.

Let there exist an undirected graph $G=V,E$, where $V$ represents the set of nodes and $E$ represents the set of edges. Dominating set (DS) refers to that in an undirected graph $G$, $S\subseteq V$ and $S\ne \varnothing$ exist, and for $\forall x\in V-S$, $x$ is directly connected to at least one node in $S$. In this case, $S$ is called the dominating set of graph $G$.

If any true subset of $S$ is not the dominating set of $G$, $S$ is the minimal dominating set. If $S$ is the dominating set of $G$ and there is no other dominating set $S^{\prime }$ for $S^{\prime }<S$ to be true, then $S$ is the minimum dominating set (MDS) of $G$ and $S$ is the minimum dominating number [30].

As shown in Figure 6(a), $v_3,v_4,v_8,v_{11}$ is a dominating set of $G$, but it is not the MDS. In Figure 6(b), the set $S=v_3,v_5,v_6$ is also the dominating set of $G$, and there is no other dominating set $S^{\prime }$ for $S^{\prime }<S$ to be true, so $v_3,v_5,v_6$ is the MDS of $G$. We know that the dominating set of the graph is not unique.

[figure(s) omitted; refer to PDF]

Since the graph $G$ is an unweighted and symmetric graph, it is easy to know that the set $v_4,v_5,v_6$ is also a MDS of $G$, and $v_5,v_6,v_7$ is also a MDS of $G$. Thus, for a given graph or network, its MDS is not unique.

To get the MDS of the network, in fact, is to find the node set that minimizes the number of nodes in the DS. We use the optimization idea, and the objective function is $$\begin{array}{}\text{(7)}& \min J=S.\end{array}$$

This index takes into account the number of nodes to ensure the minimum size of the control set, that is, the load capacity of controllers and equipment is mainly considered to ensure the minimum number of aircraft to be deployed. This index does not consider the nature of the network’s edges and cannot reflect the urgency of flight conflicts, so controllers cannot deploy aircraft in an orderly manner according to the intensity of conflicts. In this paper, the connotation of the MDS is expanded, the optimal dominating set is defined, and the specific index are determined in the deployment of flight conflicts according to the practical significance.

3.2. Optimal Dominating Set

Assume that $S$ is the dominating sets of network $G$ on the basis of dominating set, the optimal dominating set introduce the optimal performance index function $J$. When $S_j$ optimizes the index $J$, node set $O=S_j$ is the optimal dominating set of the network (optimal dominating set (ODS)). $$\begin{array}{}\text{(8)}& J=\sum _i{k}_i{C}_i,\end{array}$$

where $C_i$ represents the $i$th characteristic quantity of $S$ in the network, and $k_i$ is its corresponding weight in the index. We operate on each column of the adjacency matrix $B$ by bit to obtain the vector $Q$. $$\begin{array}{}\text{(9)}& Q=B_1{B}_{2}L{B}_n.\end{array}$$

$Q$ is an $n$dimensional row vector composed of elements 0 and 1. To make the subset $Z_i$ the dominating set of the network, it needs to satisfy the following requirement: $$\begin{array}{}\text{(10)}& Q_{x_i=0}\subseteq Z_i,\end{array}$$

where $Z$ represents the node set corresponding to the position vector of the particle and $Q_{x_i=0}$ represents the node set corresponding to the position of element 0 in $Q$. When only the elements in $Q$ corresponding to nodes in $Z$ can be 0, and all other elements are 1, $S=Z_i$ is the dominating set of the network.

Therefore, the index of the network’s ODS is expressed as $$\begin{array}{}\text{(11)}& J=\sum _i{k}_i{C}_i,\text{s}.\text{t}.Q_{x_i=0}\subseteq Z_i.\end{array}$$

As shown in Figure 7, the weight of the edge between nodes $v_3$ and $v_5$ is 2, and the weight of the remaining unmarked edges is 1. When the index $J$ considers the point strength of nodes, the network’s ODS should contain nodes with larger point strengths. Then, $v_3,v_5,v_6$ constitutes the ODS of the network. According to the definition of performance indexes, $v_4,v_5,v_6$ is the dominating set of the network, but it is not the optimal dominating set of the network.

[figure(s) omitted; refer to PDF]

Take the optimal performance index of flight conflict network ODS as follows: $$\begin{array}{}\text{(12)}& \min J=\frac{k_{1}n+k_2}{s+k_{3}e}.\end{array}$$

(1) In the first term, $n$ represents the number of nodes in the dominating set. The fewer nodes there are, the less difficult it is for controllers to deploy aircraft. (2) In the second item, $s$ represents the average node strength of the nodes in dominating set. The larger $s$ is, the stronger ability of the dominating set to resolve network conflicts will be. (3) $e$ represents the number of edges in the dominating set. Due to working pressure, when controllers deploy conflicts of two aircraft, they usually only deploy a single aircraft. The smaller $e$ is, the less work controllers have to do and the less workload for the controller

ODS contains the nature and content of MDS, so it has more significance and application value for actual complex network. In the flight conflict resolution, ODS represents a feasible optimal resolution strategy of key aircraft nodes in a conflict network.

4. Immune Particle Swarm Algorithm

In this paper, we combine the particle swarm optimization (PSO) to solve the ODS of the flight conflict network [31, 32] and introduce the immune mechanism to optimize the initial position of particle population, which can accelerate the convergence speed of PSO.

4.1. Binary Particle Swarm Optimization

In PSO, the position of different particles in the solution space represents a feasible solution of NP-hard problem. Suppose there are $n$ nodes in the conflict network, and $n$ corresponds to the dimension of the solution space. The position of particle swarm individuals is the point coordinates in the vector space, expressed by $x_i$, and its dimension is $n$. Since solving ODS is a selection relationship of nodes, binary encoding is used to represent $x_i$, 1 means selection, and 0 means not selected. The computational complexity of binary particle swarm optimization is far less than that of traditional particle swarm optimization.

In the search process, the position of the particle must satisfy the dominating constraint, that is, the node set $Z$ corresponding to the particle is the dominating set of the network. Based on this, we iteratively search for the best fitness function value. According to the optimization objective, we use the best performance metric of the flight conflict network ODS as the fitness function of the particle swarm optimization algorithm: $$\begin{array}{}\text{(13)}& \min J=\frac{k_{1}n+k_2}{s+k_{3}e},\text{s}.\text{t}.Q_{x_i=0}\subseteq Z_i.\end{array}$$

According to the vector $x_i$, the fitness function value at the current position of the particle can be calculated. By comparing with the historical optimal fitness value of the particle, the current optimal position $p_{\text{best}}$ of the individual can be obtained. After the updating of individual optimal position is completed, the global optimal position $g_{\text{best}}$ of the particle population is calculated according to the fitness value of all particles.

The following is the velocity formula of particle swarm: $$\begin{array}{}\text{(14)}& v_i={wv}_i+c_1\mathrm{rand}{p}_i-x_i+c_2\mathrm{rand}{p}_g-x_i,\end{array}$$

where $v_i$ represents the particle velocity, $w$ represents the inertia weight, $c_1$ and $c_2$ represent the learning factor, $\mathrm{rand}$ represents the random number between 0 and 1, $x_i$ represents the current position of the particle, $p_i$ represents the current individual optimal position of the particle, and $p_g$ represents the global optimal position of the contemporary population. Based on the velocity of the particle, its position update formula is $$\begin{array}{}\text{(15)}& s{v}_{i,j}=\frac{1}{1+\exp -v_{i,j}},\text{(16)}& x_{i,j}=\begin{array}{c}1,\hspace{1em}r<s{v}_{i,j},\hfill \\ 0,\hspace{1em}\text{Other}\text{situations},\hfill \end{array}\end{array}$$

where $s{v}_{i,j}$ is the Sigmoid function value of the velocity component. Through the sigmoid function, the velocity component $v_{i,j}$ in the $j$th dimension can be mapped between 0 and 1. $r$ is a random variable, and $r~U0,1$. When $r<s{v}_{i,j}$, the value of $x_{i,j}$ is 1, otherwise it is 0.

4.2. Immune Mechanism

As shown in Figure 8, immunity in biology means that when the body is stimulated by an antigen, it will produce matching antibodies. If the body is invaded by similar antigens again, the antibodies will specifically combine with the antigen to produce immunity.

[figure(s) omitted; refer to PDF]

The immune mechanism of optimization algorithms is to simulate this process. By injecting antigens into the initial population to produce antibodies, the initial position of the population is optimized, so that the algorithm can converge to the position with high fitness more easily in the process of iterative search. And experiments have proved that mechanism can improve the convergence speed of particle swarm optimization algorithm and the ability to calculate high-dimensional data.

5. Deployment Strategy and Steps

5.1. Pretreatment

In this paper, the velocity obstacle method is used to optimize the topology structure of the conflict network, and the flight conflict network model is constructed. The nonconflict edges in the network are filtered, so it is easy to meet the situation of the nonconnected graph, and it is necessary to preprocess when search for the dominating set. We first deals with the isolated nodes in the network.

As shown in Figure 9(a), according to the definition, the isolated nodes in the network will be identified into the dominating set. In most real networks, the isolated nodes mean that they have weak or no connection with other units in the system, so they have no significance to be dominating set nodes. In the flight conflict network, isolated nodes represent that their corresponding aircraft does not have conflicts, so these isolated nodes should be filtered out before searching the dominating set. Figure 9(b) shows the network after filtering the isolated nodes.

[figure(s) omitted; refer to PDF]

Experiments show that filtering the isolated nodes before the algorithm runs can reduce the dimension of the solution space, accelerate the convergence speed of the particle swarm optimization algorithm, and improve the solution quality of the algorithm.

5.2. Antigen Injection

When resolving flight conflicts, controllers will prioritize the deployment of aircraft with serious conflicts and urgent flight conflicts. This is due to unsafe factors can endanger the safety of the flight and the lives of passengers. Therefore, in the flight conflict network, we need to prioritize the key aircraft nodes and the high-risk flight conflict edges. Based on this, we divide the antigens in the immune mechanism into two categories:

(1) Node antigen: we select specific indexes, such as degree, node strength, clustering coefficient, or betweenness to sort, and screen out the top nodes as antigens. We can also select antigens by weighted ranking of multiple metrics. In order to simplify the calculation and highlight the characteristics of immune particle swarm optimization (IPSO), we select node strength as the index of antigen selection. When the node strength is higher than the threshold $s_t$, the node will be injected into the initial population of the PSO algorithm as antigen. If there are aircraft in the network that fails or not easy to adjust, we can also reverse the antigen injection, i.e., circumvent the node in the process of population generation and search

(2) Edge antigen: there is a kind of urgent conflict in the network that the aircraft causing the conflict do not belong to the node antigen. If such conflict is not properly resolved, it will also lead to unsafe factors. Let the weight threshold of edge be $w_t$. If the weight of the connected edge in the flight conflict network is greater than $w_t$ and the nodes at its two ends are not selected as antigens, we inject the node with higher midpoint strength as an antigen into the initial population, which indicates that the flight conflict corresponding to this connected edge has exceeded the predefined safety limit and needs to be focused on and implemented for deployment

5.3. Steps of Implementation

Figure 10 illustrates the steps of IPSO algorithm implementation, and the specific steps are as follows:

(i) Step 1: collect the direction, position and speed information of aircraft in the airspace to build the flight conflict network $GV,E,W$

(ii) Step 2: read the weight matrix $W$ of the network, perform data preprocessing, and filter the isolated nodes in the flight conflict network

(iii) Step 3: initialization parameters: the number of particle population individuals $N$, the dimension of solution space $D$, the maximum number of iterations $T$, learning factors $c_1$ and $c_2$, inertia weight $g$, etc.

(iv) Step 4: immune operation: take the nodes which point strength is higher than the threshold $s_t$ and the edges which weight is higher than the threshold $w_t$ as antigens and inject them into the initial population to produce antibodies in the population and optimize their initial positions

(v) Step 5: initialize the position $x_i$ and velocity $v_i$ of the particle, calculate the fitness value according to the fitness function (Equation (13)), and obtain the initial individual optimal value $p_{\text{best}}$ and the global optimal value $g_{\text{best}}$ of the particle swarm

(vi) Step 6: combine the velocity formula (Equation (15)) and position formula (Equation (16)) to update the velocity $v$ and position $x$ of the particle, respectively, calculate the fitness value, and update the particle individual optimal $p_{\text{best}}$ and the particle swarm global optimal $g_{\text{best}}$

(vii) Step 7: execute the algorithm until the termination condition is met. And the output particle optimal position is the optimal dominating set of this flight conflict network

[figure(s) omitted; refer to PDF]

6. Experiment and Simulation

In order to verify the effectiveness of the method in this paper, we simulate the flight conflict scenario in MATLAB environment and verify it by simulation. First, in the airspace of $100\text{km}\times 100\text{km}\times 0.3\text{km}$, we randomly generate 15 aircrafts on each of the two altitude levels and between the altitude levels, respectively, totaling 45 aircraft. The speed of the aircraft is taken as a random value in the range of $\mathrm{700,850}$ km/h, the horizontal heading is taken as a random value in the range of $\mathrm{700,850}$ degrees, and the aircraft between the altitude layers are equipped with a 30° climb/descent angle.

According to the velocity obstacle relationship between aircraft, we build edges in the network, the estimated conflict time $t_c$ of aircraft pairs is calculated and the edge weight is determined, and the flight conflict network model is obtained, as shown in Figure 11. The topological characteristics of a complex network are only related to the adjacency relationship of nodes and have nothing to do with the shape of the network. To be more intuitive, the flight conflict network is projected onto a two-dimensional plane in the following analysis and research.

[figure(s) omitted; refer to PDF]

6.1. Network Performance Analysis

First, we analyze the properties of nodes in the flight conflict network.

Figure 12(a) shows that the flight conflict network projected on a two-dimensional plane, and Figure 12(b) shows that the aircraft state network constructed through position relationship in the same simulation scene. From these two figures, we can visually see that the number of edges in flight conflict network is significantly reduced and the complexity is lower for the same detection region.

[figure(s) omitted; refer to PDF]

Node degree reflects the number of potential conflicts of aircraft, which determines the structure and performance of network to a certain extent. Figure 13 shows the node degrees corresponding to each aircraft in both networks, and the comparison of each node degree value is shown in Table 1: (1) There are many edges in the aircraft state network, and the nodes are closely related. Controllers need to devote energy to related aircraft pairs, which leads to unreasonable allocation of control resources and greater control pressure. Nodes 20, 27, 31, and 40 in the flight conflict network are isolated nodes, and controllers can appropriately allocate energy to other aircraft nodes, which slows down the load of controllers. (2) The five nodes with the highest degree in aircraft state network are 32, 7, 26, 10, and 44. Node 44 and 7 are still nodes with high degree in the flight conflict network. Node 32 has the highest node degree value in the aircraft state network, but after determination by the velocity obstacle model, the number of its potential conflicts is only two, which is deviated from the judgment intuitively obtained through the proximity relationship.

[figure(s) omitted; refer to PDF]

Table 1

Node degrees in different networks.

Sequence	Flight status network	Flight conflict network	Sequence	Flight status network	Flight conflict network	Sequence	Flight status network	Flight conflict network
1	12	4	16	9	4	31	5	0
2	7	2	17	6	1	32	18	2
3	6	1	18	4	2	33	5	1
4	3	1	19	11	2	34	12	1
5	7	1	20	1	0	35	9	3
6	7	3	21	11	2	36	8	2
7	14	4	22	11	2	37	12	5
8	3	2	23	6	1	38	7	2
9	10	5	24	7	2	39	6	1
10	13	3	25	11	3	40	7	0
11	5	1	26	14	3	41	4	2
12	5	4	27	5	0	42	10	1
13	12	3	28	8	2	43	11	3
14	11	4	29	7	1	44	13	5
15	7	2	30	4	1	45	12	4

Compared to the aircraft state network, the average number of false alarms per node in the flight conflict network decreases by 3.09. The number of edges in the flight conflict network is 49; compared with 188 in the aircraft state network, the false alarm rate is reduced by 73.9%. Therefore, the flight conflict network is simpler in topological structure. It can filter out the redundant information in the network, make the conflict relationship between aircraft clearer, improve the information value of the network, and provide more accurate data for the control work.

6.2. Resolution Strategy

6.2.1. IPSO Solution for ODS

The IPSO and the PSO algorithms are, respectively, used to solve the ODS of the flight conflict network.

As shown in Figure 14, the initial fitness value of the IPSO algorithm is smaller than that of the PSO, which proves that the immune mechanism can make the initial position of particles better. The IPSO algorithm converges to the 45th generation, and the PSO algorithm converges to the 117th generation. The IPSO algorithm converges faster than the PSO algorithm. From the fitness point of view, the fitness value of IPSO algorithm is lower when convergence occurs, so the IPSO algorithm is better to solve ODS.

[figure(s) omitted; refer to PDF]

Through experiments, the IPSO algorithm mostly converges within 100 generations, and the running time is about 0.71 s. As shown in Figure 15(a), the ODS of the flight conflict network identified by the immune particle swarm optimization algorithm is $v_7,v_8,v_{12},v_{14},v_{15},v_{16},v_{17},v_{18},v_{19},v_{26},v_{37},v_{38},v_{41},v_{43}$.

[figure(s) omitted; refer to PDF]

The network with ODS removed is shown in Figure 15(b). The network is decomposed into simple subgraphs, the number of potential conflicts is significantly reduced, and the complexity of the network is reduced.

6.2.2. Evaluation Indexes

Combining the characteristics of flight conflict networks, we select network robustness, giant component, number of conflicting nodes, and network efficiency as indexes to evaluate the network performance after deleting nodes.

(1) Robustness

Robustness reflects the ability of the system to keep the original state unchanged after being attacked. The robustness of flight conflict network is defined as $$\begin{array}{}\text{(17)}& R=\frac{1}{N-I}\sum _{i=1}^n\sum _{j=1}^n\frac{w_{ij}}{2},\end{array}$$

where $I$ is the number of nodes removed from the network and $w_{ij}$ is the element in row $i$, column $j$, of the weight matrix. In the flight conflict network, the decline of network robustness indicates that the integrity of the network has been damaged and is being disintegrated. After the removal of aircraft nodes, the more robustness of the network decreases, the more damaging deployment will be to the conflict network. Therefore, it is necessary to reduce the network robustness as much as possible to resolve the conflicts. Among the four indexes, robustness is relatively the most important.

(2) Number of conflicting nodes

An important index to measure the overall operation situation in the airspace is the number of aircraft without conflict in the airspace. Since this index is positively correlated with the number of deleted nodes, we take the number of nodes with conflicts in the network as the index. $$\begin{array}{}\text{(18)}& \text{NN}=\sum _{i=1}^n{q}_i,\end{array}$$

where $q_i$ is the $i$th component of the vector $Q$. The number of conflicting nodes has an impact on the complexity of the network and the load degree of controllers, so it is a secondary important index.

(3) Giant component

A component is a set of mutually reachable nodes in a network and their edges. The nodes have at least one edge with another node in the set. The component with the largest number of nodes is the giant component of the network, which is measured as $$\begin{array}{}\text{(19)}& \text{GC}=S_l,\end{array}$$

where $S_l$ is the size of the giant component. The more nodes in the giant component, the better the connectivity of the network. In the flight conflict network, the larger the giant component is, the more difficult conflicts are to be deployed, and the greater the controller pressure is. Its importance is equivalent to the number of conflicting nodes.

(4) Network efficiency

Network efficiency is an index to measure the ability of information exchange in a network. The efficiency of transmission is negatively correlated with the consumption of information exchange. In the similarity weight network, the greater the weight of the network’s connecting edges, the closer the connection between the nodes. Network efficiency is defined as $$\begin{array}{}\text{(20)}& \text{NE}=\frac{1}{nn+1}\sum _{i\ne j}\frac{p_{ij}}{d_{ij}},\end{array}$$

where $d_{ij}$ represents the length of the geodesic between node $v_i$ and node $v_j$ in the unweighted network and $p_{ij}$ represents the sum of the weights of all the edges on the shortest path. Network efficiency can reflect the complexity of the network to some extent. The higher NE is, the closer overall connection among network nodes will be, and the network will be relatively more complex. Compared with the first three indexes, the importance of it is relatively low.

Construct the judgment matrix. Through the analytic hierarchy process (AHP) calculation, the weight vector of network robustness, number of conflicting nodes, giant component and network efficiency is $0.5222,0.1998,0.1998,0.0781$, and $\text{CI}=0.0145$, $\text{CR}=\text{CI}/\text{RI}=0.0161$, which passes the consistency test. The comprehensive indexes obtained through AHP are as follows: $$\begin{array}{}\text{(21)}& \text{AHP}=0.5222R+0.1998\text{NN}+0.1998\text{GC}+0.0781\text{NE}.\end{array}$$

6.2.3. Deployment Sequence of ODS

The above experiments show that removing the nodes of ODS can quickly resolve the network conflicts and reduce its complexity. At the same time, if the nodes of ODS are removed in different order, the speed of network performance degradation is different. Figure 16 shows the impact of different ODS removal sequences on network performance degradation rate.

[figure(s) omitted; refer to PDF]

In Figure 16, nodes in the flight conflict network ODS are deleted, respectively, in the order of node degree, random, node strength, and PageRank. After comparison, the effect of deploying ODS according to the order of node degree is better than the node strength and PageRank value. The effect of random deleting is the worst. This is because in ODS, the higher the node degree value, the more conflicts that aircraft node will have with other aircraft. The deployment of these aircraft will cause a large number of edges to fail, so as to reduce the number of conflicts and the robustness of the network at the same time, and the conflict network will be resolved faster.

The optimal deployment sequence of aircraft nodes is 37 ⟶ 9 ⟶ 7 ⟶ 12 ⟶ 16 ⟶ 43 ⟶ 26 ⟶ 13 ⟶ 2 ⟶ 19 ⟶ 8 ⟶ 38 ⟶ 41 ⟶ 28 ⟶ 3.

Deploy according to the degree of ODS nodes in the flight conflict network in descending order. When the degree values are the same, the order is arranged according to the node strength. This characteristic is consistent with the deployment habits of actual controllers. After determining the ODS nodes of the flight conflict network, controllers only need to deploy these aircraft in accordance with the control practice. According to the order of conflict number and conflict intensity, excellent deployment effect can be achieved.

6.3. Comparison with Other Methods

In this section, we first introduce four other network node deletion methods to deploy flight conflicts. Then, we compared the network performance changes of the above four methods during deployment with a conflict resolution strategy based on in-flight conflict network ODS.

(1) In the first method, nodes are randomly deleted in the global flight conflict network. (2) In the second method, aircrafts are deployed according to the number of conflict alarms of the secondary radar, that is, the number of neighboring aircraft within the ACAS distance. (3) The third method is deployed in order of the node strength in the global flight conflict network from large to small. (4) The fourth is the PageRank method. The number of iterations of the algorithm is set to 100 generations, and the damping factor is 0.85. The PageRank value of all nodes is calculated, and nodes are deleted according to the PageRank value from large to small

In the following, we compare the conflict resolution strategy based on the ODS of the flight conflict network with these methods in terms of the changes of network robustness, number of conflicting nodes, giant component, network efficiency, and comprehensive indexes of network performance (normalization processing was conducted before the synthesis of all indexes). Figure 17 shows the results of the experiment, the blue broken line represents the conflict resolution strategy based on ODS, the orange broken line represents random deletions in the global network, the yellow broken line is deployed according to the number of neighbors of the aircraft, the purple broken line is the conflict deployment based on node strength throughout the network, and the green broken line represents the deployment of nodes sorted by the PageRank method.

[figure(s) omitted; refer to PDF]

From the experimental results, it can be concluded that the conflict resolution strategy based on the flight conflict network ODS can make the individual and comprehensive indexes of the network decline faster, so the conflict resolution speed is also faster. Among these methods, due to considering more factors of flight conflict, ODS method is the best, and PageRank method and node strength method are the second best. Due to the small amount of information considered by random deletion and deletion based on the number of neighbors, the deployment effect is general.

In the random deletion, the index of the network appears to rise, because the deletion of isolated or weakly connected nodes in the network will contribute to the improvement of network robustness and network efficiency. It also shows that if the conflict resolution strategy is not appropriate, the overall conflict situation of the network may be more serious. It can also be seen from the Figure 17 that when the deployment is based on the number of neighbors, only judging by radar warning and personal experience, the effect of controllers’ deployment of flight conflicts is limited. As the need for simultaneous deployment of aircraft increases, the relief effect is gradually weakened. In the strategy based on node strength, its broken line overlaps with the ODS method in the early stage, which reflects the role of immune mechanism. With the increase of the number of deployment nodes, the deployment effect of the method is weakened, which is caused to some extent by the scale-free characteristics of the flight conflict network.

7. Conclusion

In this paper, we propose a flight conflict resolution strategy based on the ODS of complex networks. Based on the flight conflict network model, the strategy uses IPSO algorithm to solve ODS, and the conflict resolution strategy is given according to the degree and strength of the ODS nodes. Through theoretical analysis and simulation experiments, we can draw the following conclusions:

(1) The flight conflict network can directly and accurately reflect the conflict relationship and intensity between aircraft, and the network information value is high, which can provide assistance and convenience for controllers to grasp the conflict situation in the airspace

(2) ODS enriches the meaning of dominating set in complex network theory and has more application potential in real network. In this paper, ODS is used to explain and resolve flight conflicts

(3) The immune mechanism has a good application prospect and practical significance in the resolution of flight conflict. At the same time, the IPSO algorithm can improve the solution speed of ODS and quickly identify the key aircraft nodes and conflict edges in the flight conflict network

(4) Compared with traditional methods, the conflict resolution strategy based on the flight conflict network ODS can adapt to different control scenarios, accurately identify the key nodes of flight conflicts in complex situation, and provide macrodeployment suggestions for controllers. This strategy is helpful to reduce the operating pressure of the ATC system, enhance the airspace capacity, and guarantee the flight safety of aircraft

Acknowledgments

The authors gratefully acknowledge the financial support for this project from the National Natural Science Foundation of China (No. 71801221).

References

[1] Q. Q. Zhang, Z. Y. Wang, H. H. Zhang, C. P. Jiang, M. H. Hu, "SMILO-VTAC model based multi-aircraft conflict resolution method in complex low-altitude airspace," Journal of Traffic and Transportation Engineering, vol. 19 no. 6, pp. 125-136, 2019.

[2] Z. Wang, M. Wu, X. Wen, X. Jiang, Y. Gao, "Flight collision resolution and recovery strategy based on velocity obstacle method," Journal of Beijing University of Aeronautics and Astronautics, vol. 45 no. 7, pp. 1294-1302, 2019.

[3] X. R. Jiang, M. G. Wu, X. X. Wen, C. L. Tu, D. M. Nie, "Conflict resolution of multi-aircraft based on the cooperative game," Systems Engineering and Electronics, vol. 40 no. 11, pp. 2482-2489, 2018.

[4] W. F. Chen, Z. J. Shao, "Direct disjunction transcription based conflict resolution approach," Acta Aeronautica et Astronautica Sinica, vol. 35 no. 4, pp. 1122-1133, 2014.

[5] X. Chen, Y. Wan, S. Y. Lao, "Graphical modeling and simulation for a multi-aircraft collision avoidance algorithm based on collaborative decisions," Symmetry, vol. 12 no. 6, pp. 985-1007, DOI: 10.3390/sym12060985, 2020.

[6] W. Y. Liu, I. Hwang, "Probabilistic aircraft midair conflict resolution using stochastic optimal control," IEEE Transactions on Intelligent Transportation Systems, vol. 15 no. 1, pp. 37-46, DOI: 10.1109/TITS.2013.2274999, 2014.

[7] Y. Matsuno, T. Tsuchiya, N. Matayoshi, "Near-optimal control for aircraft conflict resolution in the presence of uncertainty," Journal of Guidance Control and Dynamics, vol. 39 no. 2, pp. 326-338, DOI: 10.2514/1.G001227, 2016.

[8] D. Sislak, P. Volf, M. Pechoucek, "Agent-based cooperative decentralized airplane-collision avoidance," IEEE Transactions on Intelligent Transportation Systems, vol. 12 no. 1, pp. 36-46, DOI: 10.1109/TITS.2010.2057246, 2011.

[9] S. M. Huang, E. Feron, G. Reed, Z. H. Mao, "Compact configuration of aircraft flows at intersections," IEEE Transactions on Intelligent Transportation Systems, vol. 15 no. 2, pp. 771-783, DOI: 10.1109/TITS.2013.2287205, 2014.

[10] Y. Hong, B. Choi, K. Lee, "Conflict management considering a smooth transition of aircraft into adjacent airspace," IEEE Transactions on Intelligent Transportation Systems, vol. 9 no. 17, pp. 2490-2501, 2016.

[11] A. Valenzuela, D. Rivas, "Conflict resolution in converging air traffic using trajectory patterns," Journal of Guidance Control and Dynamics, vol. 4 no. 34, pp. 1172-1189, 2011.

[12] H. R. Eulalia, A. Valenzuela, D. Rivas, "Probabilistic multi-aircraft conflict detection and resolution considering wind forecast uncertainty," Aerospace Science and Technology, vol. 105,DOI: 10.1016/j.ast.2020.105973, 2020.

[13] S. Cafieri, D. Rey, "Maximizing the number of conflict-free aircraft using mixed-integer nonlinear programming," Computers & Operations Research, vol. 80, pp. 147-158, DOI: 10.1016/j.cor.2016.12.002, 2017.

[14] J. J. Tang, Y. H. Wang, F. Liu, "Characterizing traffic time series based on complex network theory," Physica A Statistical Mechanics & Its Applications, vol. 392 no. 18, pp. 4192-4201, DOI: 10.1016/j.physa.2013.05.012, 2013.

[15] J. J. Tang, F. Liu, W. B. Zhang, S. Zhang, Y. Wang, "Exploring dynamic property of traffic flow time series in multi-states based on complex networks: phase space reconstruction versus visibility graph," Physica A Statistical Mechanics & Its Applications, vol. 450, pp. 635-648, DOI: 10.1016/j.physa.2016.01.012, 2016.

[16] J. J. Tang, S. Zhang, W. H. Zhang, F. Liu, W. Zhang, Y. Wang, "Statistical properties of urban mobility from location-based travel networks," Physica A Statistical Mechanics & Its Applications, vol. 461, pp. 694-707, DOI: 10.1016/j.physa.2016.06.031, 2016.

[17] Z. Y. Du, J. J. Tang, Y. Qi, "Identifying critical nodes in metro network considering topological potential: a case study in Shenzhen city--China," Physica A Statistical Mechanics & Its Applications, vol. 539,DOI: 10.1016/j.physa.2019.122926, 2020.

[18] H. Y. Wang, X. H. Xu, Y. F. Zhao, "Empirical analysis of aircraft clusters in air traffic situation networks," Proceedings of the Institution of Mechanical, vol. 231 no. 9, pp. 1718-1731, DOI: 10.1177/0954410016660870, 2017.

[19] X. R. Jiang, X. X. Wen, M. G. Wu, M. Song, C. Tu, "A complex network analysis approach for identifying air traffic congestion based on independent component analysis," Physica A Statistical Mechanics & Its Applications, vol. 523, pp. 364-381, DOI: 10.1016/j.physa.2019.01.129, 2019.

[20] Y. Huang, J. Tang, S. Y. Lao, "Cooperative multi-UAV collision avoidance based on a complex network," Applied Sciences, vol. 9 no. 19,DOI: 10.3390/app9193943, 2019.

[21] Y. I. Jenie, E. J. Kampen, C. C. Visser, "Three-dimensional velocity obstacle method for uncoordinated avoidance maneuvers of unmanned aerial vehicles," Journal of Guidance Control and Dynamics, vol. 39 no. 10, pp. 2312-2323, DOI: 10.2514/1.G001715, 2016.

[22] X. X. Yang, Y. Zhang, W. W. Zhou, "Obstacle avoidance method of three-dimensional obstacle spherical cap," Journal of Systems Engineering and Electronics, vol. 29 no. 5, pp. 1058-1068, 2018.

[23] K. L. Wang, C. X. Wu, J. Ai, Z. Su, School of Optical-Electrical and Computer Engineering, University of Shanghai for Science and Technology, Shanghai 200093, China, "Complex network centrality method based on multi-order K-shell vector," Acta Physica Sinica, vol. 68 no. 19,DOI: 10.7498/aps.68.20190662, 2019.

[24] M. He, Y. Y. Xu, J. T. Liu, "Multi-agent pinning control algorithm based on K-shell decomposition," Control and Decision, vol. 35 no. 10, pp. 2556-2560, 2020.

[25] J. P. Wang, Q. Guo, J. G. Liu, "Credit allocation for each author in a multi-author paper based on PageRank," Journal of University of Electronic Science and Technology of China, vol. 49 no. 6, pp. 918-923, 2020.

[26] X. Y. Wang, Y. Wang, X. M. Qin, R. Li, J. Eustace, "Detecting overlapping communities based on vital nodes in complex networks," Chinese Physics B, vol. 27 no. 10,DOI: 10.1088/1674-1056/27/10/100504, 2018.

[27] X. Y. Wang, X. M. Qin, "Asymmetric intimacy and algorithm for detecting communities in bipartite networks," Physica A Statistical Mechanics & Its Applications, vol. 462, pp. 569-578, DOI: 10.1016/j.physa.2016.06.096, 2016.

[28] X. Y. Wang, X. M. Qin, "Detecting communities by asymmetric intimacy in directed-weighted network," International Journal of Modern Physics C, vol. 28 no. 1,DOI: 10.1142/S0129183117500061, 2017.

[29] J. W. Li, X. X. Wen, M. G. Wu, F. Liu, S. Li, "Identification of key nodes and vital edges in aviation network based on minimum connected dominating set," Physica A Statistical Mechanics & Its Applications, vol. 541,DOI: 10.1016/j.physa.2019.123340, 2020.

[30] J. H. Yin, K. Y. Wu, Graph Theory and Its Algorithm, 2003.

[31] X. Y. Wang, D. D. Zhang, N. Wei, "Fractal image coding algorithm using particle swarm optimisation and hybrid quadtree partition scheme," IET Image Processing, vol. 9 no. 2, pp. 153-161, 2015.

[32] X. Y. Wang, Y. P. Li, "Chaotic image encryption algorithm based on hybrid multi-objective particle swarm optimization and DNA sequence," Optics and Lasers in Engineering, vol. 137, article 106393,DOI: 10.1016/j.optlaseng.2020.106393, 2021.