Fault-tolerant communication topology management based on minimum cost arborescence for leader–follower UAV formation under communication faults

Abstract

A novel fault-tolerant communication topology management method for the leader–follower unmanned aerial vehicle (UAV) formation is proposed to minimize the formation communication cost while keeping the formation shape, even in the case of communication faults during the formation flight. This method is based on Edmonds’ algorithm for the minimum cost arborescence problem in graph theory. When a formation shape is given before the formation flight, this method can get the optimal initial communication topology with the minimum formation communication cost for keeping the formation shape. When some communication faults occur during the formation flight, which will cause the formation shape cannot be kept, this method can reconfigure the communication topology in time to guarantee the safety of all UAVs and recover the formation shape, and then it can reoptimize the communication topology by UAV position reconfiguration in the formation shape to minimize the formation communication cost for continuously keeping the formation shape. The effectiveness of this method is demonstrated through several simulation experiments.

Keywords

Leader–follower UAV formation formation keeping communication fault minimum cost arborescence fault-tolerant communication topology management

Introduction

The cooperative decision and control of multiple unmanned aerial vehicles (UAVs) have drawn considerable attention from the scientific and engineering communities in recent years due to their wide potential applications in many fields, such as joint search and track,¹ persistent surveillance,² localization and navigation,³ environmental monitoring,⁴ ground target attack,⁵ and so on. In order to get a better task performance, multiple UAVs usually need to form and keep a certain formation shape (geometric configuration) by information exchange through partial communication links among them,⁶ where the set of communication links being used is called the communication topology,^7,8 information exchange topology,⁹ or connection topology¹⁰ of the UAV formation. Due to different communication distances and other reasons, communication links in the communication topology usually have different communication costs, that is, they will consume a different amount of battery power or fuel.^11
–13 Meanwhile, the available battery power or fuel of each UAV is usually limited. Furthermore, some communication faults may occur during the formation flight, which will cause that some communication links in the communication topology become unusable and the formation shape cannot be kept. Therefore, an efficient fault-tolerant communication topology management method is beneficial and necessary for a UAV formation to minimize the total cost of the communication links in the communication topology (called the “formation communication cost”) while keeping the formation shape even when some communication faults occur during the formation flight.

To form and keep a formation shape, UAVs usually use one of the following four main formation control approaches: leader–follower-based approach,^14

–18 virtual structure-based approach,^19
–21 behavior-based approach,^22
–24 and consensus-based approach.^25

–28 Different communication topologies are needed for these different formation control approaches. For example, the communication topology for leader–follower-based approach is a (directed) spanning tree, the communication topology for virtual structure-based approach and behavior-based approach is a bidirectional ring, and the communication topology for consensus-based approach must have a subset that is a (directed) spanning tree.⁹ This article focuses on the research of fault-tolerant communication topology management under communication faults for the leader–follower UAV formation, where all UAVs use the leader–follower-based approach to form and keep the formation shape. In this formation, only one UAV (referred to as the formation leader) will track the predefined formation reference trajectory. Other UAVs (referred to as the following UAVs) will directly or indirectly follow the formation leader. For example, one UAV may directly follow the formation leader or follow another UAV that may directly or indirectly follow the formation leader. To the best of our knowledge, only a few results have been reported about the fault-tolerant communication topology management under communication faults for the leader–follower UAV formation.

In the studies of Giulietti et al. and Pollini et al., all available communication links in a leader–follower UAV formation with n UAVs are described by a weighted directed graph. First, an algorithm with a computation complexity of O(n²) based on Dijkstra’s algorithm for the shortest path problem in graph theory is proposed to get the optimal initial communication topology for a given formation shape before the formation flight, where each following UAV has a shortest communication path from the formation leader. This path is composed of one or more communication links. However, the whole communication path for all the following UAVs may not be the shortest, which means that the formation communication cost may not be minimal. Second, when some communication faults occur during the formation flight, an alternative broadcast communication channel (BC) is used to inform all UAVs of these communication faults, and then each UAV runs Dijkstra’s algorithm again to get a suboptimal reconfigured communication topology to guarantee the safety of all UAVs and recover the formation shape. This method can deal with four types of communication faults, including transmitter failure, receiver failure, transceiver failure (UAV loss), and link interrupt (link loss), but other possible types of communication faults, including BC transmitter failure and BC receiver failure, have not been taken into account. Third, after the communication topology reconfiguration following some communication faults, a UAV position reconfiguration in the formation shape is performed based on some predefined reconfiguration maps (RMs) and heuristic laws to reoptimize the communication topology. However, the design of RMs lacks adequate theoretical basis and only adapts to some fixed formation shapes.

In Yang et al.’s study, all available communication links in a leader–follower UAV formation with n UAVs are also described by a weighted directed graph. First, an algorithm with a computation complexity of $O (\frac{{(n - 1)}^{3}}{2} + n - 1)$ is proposed to get the optimal initial communication topology for a given formation shape before the formation flight. This method can guarantee that the whole communication path for all of the following UAVs is the shortest compared to the method in the studies of Giulietti et al. and Pollini et al. However, the computation complexity of the algorithm is relatively high, and it needs to artificially specify the formation leader in advance. Second, when some communication faults occur during the formation flight, another algorithm with a computation complexity of $O (\frac{{(n - 1)}^{3}}{2} + (2 μ + m + 1) (n - 1))$ , where m denotes the number of UAVs with transmitter failure and μ denotes the number of communication faults, is proposed to get a suboptimal reconfigured communication topology to guarantee the safety of all UAVs and recover the formation shape. However, it can only deal with two types of communication faults, including link interrupt and transmitter failure of the following UAVs, and its computation complexity is also relatively high. Moreover, the reconfigured formation communication topology may not be optimal because there is no communication topology reoptimization by UAV position reconfiguration in the formation shape as in the studies of Giulietti et al. and Pollini et al.

Therefore, to overcome the shortcomings in the existing research literatures, this article proposes a novel fault-tolerant communication topology management method under communication faults for the leader–follower UAV formation, which is based on Edmonds’ algorithm for the minimum cost arborescence (MCA) problem in graph theory. The main contributions of our method can be summarized as follows:

Initial communication topology optimization: A novel initial communication topology optimization algorithm is proposed, which has a lower computation complexity and can get a better initial communication topology, where each UAV is assigned the most suitable position in the formation shape, and the most suitable UAV is selected to be the formation leader.

Communication topology reconfiguration under communication faults: A novel communication topology reconfiguration algorithm is proposed, which has a lower computation complexity, can deal with more types of communication faults, and can get a better reconfigured communication topology.

Communication topology reoptimization under communication faults: A novel communication topology reoptimization algorithm is proposed, which can get a better reoptimized communication topology, where each UAV is assigned the most suitable new position in the formation shape.

The remainder of this article is organized as follows. In section 2, the related background and preliminaries are provided. In section 3, the proposed method is presented in detail. In section 4, the effectiveness of the proposed method is validated by simulation results. In section 5, concluding remarks are offered.

Background and preliminaries

Formation controller of each UAV in the leader–follower UAV formation

Let UAV_i and UAV_j denote the ith and the jth UAV in the leader–follower UAV formation. If UAV_i directly follows UAV_j during flight, UAV_i is called the follower of UAV_j and UAV_j is called the leader of UAV_i. UAV_j will send its own position, speed, and direction information to UAV_i through a point-to-point communication link every T_control seconds. When UAV_i receives this information, it will use a formation controller to adjust its speed and direction to keep a desired relative position from UAV_j . In this article, we assume that each UAV has a formation controller as proposed in the studies of Yang et al. and Xu et al.,²⁹ which is described as follows.

First, assume that all UAVs fly at the same height, and then the kinematic model of UAV_i can be simplified as

{\begin{matrix} {\dot{x}}_{i} = v_{i} \cos θ_{i} \\ {\dot{y}}_{i} = v_{i} sin θ_{i} \\ {\dot{θ}}_{i} = ω_{i} \end{matrix}

where (x_i , y_i ) denotes the position of UAV_i, v_i denotes the speed of UAV_i, θ_i denotes the heading angle of UAV_i, and ω_i denotes the angular velocity of UAV_i.

Second, assume that the leader of UAV_i is UAV_j, and then the formation error of UAV_i can be denoted by the forward error ${\tilde{f}}_{i j}$ and the lateral error ${\tilde{l}}_{i j}$ as follows

{\tilde{f}}_{i j} = f_{i j} - f_{i j}^{d} = (x_{i} - x_{j}) \cos θ_{j} + (y_{i} - y_{j}) sin θ_{j} + d \cos (θ_{i} - θ_{j}) - f_{i j}^{d}

{\tilde{l}}_{i j} = l_{i j} - l_{i j}^{d} = (x_{i} - x_{j}) sin θ_{j} - (y_{i} - y_{j}) \cos θ_{j} - d sin (θ_{i} - θ_{j}) - l_{i j}^{d}

where f_ij and l_ij denote the actual forward and lateral distances between UAV_i and UAV_j, respectively, as shown in Figure 1, $f_{i j}^{d} and l_{i j}^{d}$ denote the desired forward and lateral distances between UAV_i and UAV_j, respectively, and d is a small constant ( $0 < d ≪ | f_{i j}^{d} |, | l_{i j}^{d} |$ ).

Figure 1.

The actual forward and lateral distances between UAV_i and UAV_j. UAV: unmanned aerial vehicle.

Finally, based on the above assumptions and descriptions, the formation controller of UAV_i can be designed as

[\begin{matrix} v_{i} \\ ω_{i} \end{matrix}] = [\begin{matrix} \cos {\tilde{θ}}_{i j} - sin {\tilde{θ}}_{i j} \\ - \frac{1}{d} sin {\tilde{θ}}_{i j} - \frac{1}{d} \cos {\tilde{θ}}_{i j} \end{matrix}] . [\begin{matrix} - k_{1} {\tilde{f}}_{i j} + v_{j} + l_{i j} ω_{j} \\ - k_{2} {\tilde{l}}_{i j} - f_{i j} ω_{j} \end{matrix}]

where ${\tilde{θ}}_{i j} = θ_{i} - θ_{j} and k_{1}, k_{2} > 0$ are two constants that denote the feedback gain.

Communication topology of the leader–follower UAV formation

Assume that n UAVs use the leader–follower formation controller described above to form and keep a given formation shape S with n positions that are at the same height h₀ and are numbered by ${1, 2, \dots, n}$ . Therefore, all available communication links in the leader–follower UAV formation can be described by a weighted directed graph as in the studies of Giulietti et al., Pollini et al., and Yang et al.. In this article, we further assume that each UAV can occupy any position in S. Therefore, we use an extended weighted directed graph $G = (V, E, W, P)$ , called the communication link graph in our paper or the network topology in Bekmezcia et al.’s study,³⁰ to describe all available communication links in the leader–follower UAV formation

$V = {v_{i}}, 1 \leq i \leq n$ is the set of nodes, where v_i denotes UAV_i.

$E = {e_{i j}} \subset V \times V, 1 \leq i, j \leq n$ is the set of arcs, where e_ij denotes an available point-to-point communication link from UAV_i to UAV_j so that UAV_i can send information to UAV_j. Namely, UAV_i can be the leader of UAV_j.

$W = {w (e_{i j})}, e_{i j} \in E$ is the set of weights of arcs, where $w (e_{i j})$ denotes the communication cost of e_ij, which is evaluated by its communication distance.

$P = {p_{i}}, 1 \leq i \leq n$ is the set of UAV positions in the formation shape called the UAV position configuration, where p_i denotes the position of UAV_i in the formation shape.

In the leader–follower UAV formation, each UAV only needs to receive information from its leader and send information to its followers, which means that not all available communication links must be used at all times for forming and keeping the formation shape. Therefore, the set of communication links being used in a leader–follower UAV formation is called its communication topology,^7,8 which is a special subgraph of its communication link graph and has the following feature:

Theorem 1

The communication topology of a leader–follower UAV formation must be a spanning tree of its communication link graph, but a spanning tree of its communication link graph is not necessarily a communication topology of the leader–follower UAV formation.

Proof

In a leader–follower UAV formation, except for the formation leader, each UAV must directly or indirectly follow the formation leader. Namely, the formation leader must have a unidirectional communication path, composed of one or more communication links, to each following UAV. Therefore, all communication links being used in the formation will form a spanning tree of its communication link graph, and the root node of this spanning tree denotes a UAV that can be the formation leader. However, not all UAVs can be the formation leader. Therefore, given a spanning tree of the communication link graph, if its root node denotes a UAV that cannot be the formation leader, then this spanning tree cannot be a communication topology of the leader–follower UAV formation. Based on the above analysis, we can naturally conclude theorem 2.

Theorem 2

The communication topology of a leader–follower UAV formation must be a spanning tree of its communication link graph whose root node denotes a UAV that can be the formation leader, and vice versa.

Fault-tolerant communication topology management based on MCA

As we can see from theorems 1 and 2, the communication link graph of a leader–follower UAV formation may have multiple spanning trees that can be a communication topology of this formation, and these spanning trees may have different communication costs because they are composed of different communication links. Therefore, we can select the optimal one from these spanning trees to be the initial communication topology before the formation flight to minimize the formation communication cost. Meanwhile, except for the communication links being used in the communication topology, the other communication links are not used (these are referred to as redundant communication links). Therefore, we can also use the redundant communication links to deal with the communication faults during the formation flight by using them to replace the faulty communication links. Based on the above analysis, this article proposes a novel fault-tolerant communication topology management method under communication faults for the leader–follower UAV formation (based on Edmonds’ algorithm for the MCA problem in graph theory), and it is presented as follows.

Initial communication topology optimization before the formation flight

Before the formation flight, all UAVs need to get an initial communication topology for forming and keeping a given formation shape based on the following assumptions: Each UAV can occupy any position in the formation shape. Several UAVs, but not all UAVs, can be the formation leader. Each UAV can communication with all other UAVs through different point-to-point communication links. The communication cost of a communication link is evaluated by its communication distance.

Under these assumptions and the above description of the communication topology, the objective of the initial communication topology optimization problem before the formation flight is to determine the optimal spanning tree of the corresponding communication link graph $G = (V, E, W, P)$ , which has the minimal communication cost and roots at a node denoting a UAV that can be the formation leader. Therefore, this problem can be modeled as the MCA problem in graph theory, whose objective is to find a spanning arborescence of minimum weight in a weighted directed graph (namely, the minimum spanning tree of a weighted directed graph). The first algorithm for solving the MCA problem, Edmonds’ algorithm, was proposed independently first by Chu and Liu³¹ and then by Edmonds.³² The computation complexity of Edmonds’ algorithm is $O (| E | \times | V |)$ . Tarjan proposed a faster implementation of Edmonds’ algorithm whose computation complexity is $O ({| V |}^{2})$ for dense graphs and $O (| E | \times log | V |)$ for sparse graphs.³³ Gabow et al. proposed a faster implementation of Edmonds’ algorithm whose computation complexity is $O (| E | + | V | \times log | V |)$ .³⁴

When using Edmonds’ algorithm to solve this problem, the first step is to construct the communication link graph $G = (V, E, W, P)$ . Because the position of each UAV in the formation shape is undetermined before the formation flight, we first assume that UAV_i occupies the ith position in the formation shape (the initial value of P is ${1, 2, \dots, n}$ ). Then, we can get the value of W by calculating the communication distances based on the given formation shape and the initial value of P .

After determining G , we can calculate its MCA denoted by $A = (V, E^{*}, W^{*}, P)$ , where $E^{*} \subset E and W^{*} \subset W$ . Let w(A) denote the cost of A, which satisfies

w (A) = \sum_{e_{i j} \in E^{*}} w (e_{i j})

According to the properties of MCA, if A exists, then A has n nodes and n − 1 arcs, and the total weight of its arcs is minimal. However, A cannot be a communication topology if its root node v_i denotes a UAV that cannot be the formation leader. Fortunately, all UAVs are almost exactly the same before the formation flight, except that part of UAVs cannot be the formation leader. Therefore, in this case, we just need to find another node v_j denoting a UAV that can be the formation leader, and then exchange the position of v_i and v_j in G and A to make A become a communication topology. Moreover, this position exchange does not change the total weight of all arcs in A, so A must be the optimal initial communication topology.

Based on the above analysis, this article proposes an initial communication topology optimization algorithm based on MCA, which is shown in Table 1.

Table 1.

Algorithm 1: Initial communication topology optimization.

Algorithm 1: Initial communication topology optimization
Input: A given formation shape S with n positions that are at the same height h₀ and are numbered by ${1, 2, \dots, n}$ ; n UAVs denoted by ${{UAV}_{1}, {UAV}_{2}, \dots, {UAV}_{n}}$ , where several UAVs can be the formation leader.
Output: The optimal initial communication topology $A = (V, E^{}, W^{}, P)$ .
Step 1. Construct the communication link graph $G = (V, E, W, P)$ , where the initial value of P is ${1, 2, \dots, n}$ .
Step 2. Calculate the MCA of $G = (V, E, W, P)$ , which is denoted by $A = (V, E^{}, W^{}, P)$ .
Step 3. If the root node v_i of A denotes a UAV that can be the formation leader, go to step 5.
Step 4. Find another node v_j denoting a UAV that can be the formation leader, and exchange the positions of v_j and v_i in G and A.
Step 5. A is the optimal initial communication topology, where P is the most appropriate UAV position configuration.

UAV: unmanned aerial vehicle; MAC: minimum cost arborescence.

The computation complexity of algorithm 1 mainly depends on the computation complexity of step 2, in which the faster implementation of Edmonds’ algorithm in the study of Gabow et al. is used.³¹ Therefore, the computation complexity of algorithm 1 is $O (| E | + | V | \times log | V |)$ . Compared to the initial communication topology optimization algorithms in the studies of Giulietti et al., Pollini et al., and Yang et al., algorithm 1 has the following advantages:

It has a lower computation complexity than the algorithm with a computation complexity of $O ({| V |}^{2})$ in the studies by Giulietti et al. and Pollini et al. and the algorithm with a computation complexity of $O (\frac{{(| V | - 1)}^{3}}{2} + | V | - 1)$ in Yang et al.’s study.

It does not need to artificially specify the position of each UAV in the formation shape, and can automatically select the most appropriate position for each UAV.

It does not need to artificially specify the formation leader, and can automatically select the most appropriate UAV to be the formation leader.

Algorithm 1 can be used in a centralized scheme or a decentralized scheme. In the former case, the ground control center runs algorithm 1 and informs all UAVs of the result. In the latter case, each UAV runs algorithm 1 and also gets the same result. Once knowing the optimal initial communication topology, the formation leader begins to track the predefined formation reference trajectory and other UAVs begin to follow its leader. Soon all UAVs form the corresponding formation shape, and then will keep the formation shape.

Communication topology reconfiguration under communication faults

During the formation flight, if some communication faults occur in one or more UAVs, UAVs may not continue to keep the formation shape, and may even collide with one another. Therefore, all UAVs should reconfigure the communication topology quickly to avoid the UAV collision and recover the formation shape. At the same time, in order to reduce the cost of communication, the communication cost of the reconfigured communication topology should be as small as possible.

The communication topology reconfiguration must be decentralized for faster execution time, and the reconfiguration algorithm must get the same result in all UAVs (i.e. all UAVs must be informed of the same communication fault information in time). To this end, this article assumes that each UAV can use a broadcast communication channel (BC) to get the same communication fault information as in the studies of Giulietti et al., Pollini et al., and Yang et al.: Each UAV has a unicast transmitter and a unicast receiver for point-to-point communication, and a broadcast transmitter and a broadcast receiver for broadcast communication through the BC. Each UAV will report its status through the BC every T _active seconds. When a UAV detects a communication fault, it will immediately notify all other UAVs through the BC.

Beside the four types of communication faults considered in the studies of Giulietti et al., and Pollini et al., and Yang et al., this article also deals with two additional types of communication faults: broadcast transmitter failure and broadcast receiver failure. All six types of communication faults are listed in Table 2.

Table 2.

Different types of communication faults.

Communication fault type	Description
Link interrupt	When a link interrupt occurs in the communication link e_ij, UAV_j cannot receive any information from UAV_i via point-to-point communication. However, both the unicast transmitter of UAV_i and the unicast receiver of UAV_j work well.
Unicast transmitter failure	When a unicast transmitter failure occurs in UAV_i, UAV_i cannot transmit any information to other UAVs via point-to-point communication.
Unicast receiver failure	When a unicast receiver failure occurs in UAV_i, UAV_i cannot receive any information from other UAVs via point-to-point communication.
Unicast transceiver failure	When a unicast transceiver failure occurs in UAV_i, UAV_i neither can transmit information to other UAVs via point-to-point communication nor can receive information from other UAVs via point-to-point communication.
Broadcast transmitter failure	When a broadcast transmitter failure occurs in UAV_i, UAV_i cannot transmit its status or any communication fault information to other UAVs through the BC.
Broadcast receiver failure	When a broadcast receiver failure occurs in UAV_i, UAV_i cannot receive any status or communication fault information from other UAVs through the BC.

UAV: unmanned aerial vehicle.

For the six types of communication faults, we assume that all UAVs have the same fault detection and isolation (FDI) strategy as follows:

When a unicast transmitter failure, a unicast receiver failure, a unicast transceiver failure, or a broadcast receiver failure occurs in UAV_i, UAV_i itself can detect this fault. Then, UAV_i will record the time stamp of this fault and notify other UAVs of this information through the BC.

When a broadcast transmitter failure occurs in UAV_i, UAV_i itself can detect this fault, but cannot notify other UAVs through the BC. Because other UAVs will never receive the status of UAV_i, after T_active seconds they can conclude that UAV_i has encountered a broadcast transmitter failure and will record the time stamp of this fault.

When a link interrupt occurs in the communication link e_ij and UAV_i is the leader of UAV_j, UAV_j cannot receive the position, speed, and direction information from UAV_i again. After T_active seconds, if UAV_j does not detect its own unicast receiver failure, and does not receive the unicast transmitter failure information of UAV_i, UAV_j will conclude that e_ij is interrupted. Then, UAV_j will record the time stamp of this fault and notify other UAVs of this information through the BC.

When a UAV receives information about a communication, it processes the communication fault immediately, which includes first updating the communication link graph according to the communication fault information and then optimizing the communication topology. If information about a new communication fault is received during the process flow, the UAV interrupts the current process flow immediately, and then processes the new and old communication faults together, which includes first updating the communication link graph according to the new communication fault information and then optimizing the communication topology again.

Based on the above FDI strategy, each UAV will quickly receive the same communication fault information if some communication faults occur, and then can get the reconfigured communication link graph $G_{r} = (V_{r}, E_{r}, W_{r}, P_{r})$ by deleting the corresponding faulty arcs or nodes from the current communication link graph $G = (V, E, W, P)$ :

If a unicast transmitter failure occurs in UAV_j, delete all the outgoing arcs of v_j.

If a unicast receiver failure occurs in UAV_j, delete all the incoming arcs of v_j.

If a unicast transceiver failure or a broadcast transmitter failure or a broadcast receiver failure occurs in UAV_j, delete all the arcs of v_j.

If a link interrupt occurs in the communication link from UAV_j to UAV_k, delete e_jk.

If all the arcs of v_j are deleted, then delete v_j and let $p_{j} = 0 (p_{j} \in P_{r}$ ), which means that UAV_j should leave the formation.

Then, each UAV should get the optimal spanning tree of G_r to be the optimal reconfigured communication topology, which has the minimal communication cost and roots at a node denoting a UAV that can be the formation leader. Therefore, this problem can also be modeled as the MCA problem in graph theory. When using Edmonds’ algorithm to get the MCA of G_r (which is denoted by A_r), the results can be divided into two kinds as follows:

The root node v_i of A_r denotes a UAV that can be the formation leader, and then A_r can be the optimal reconfigured communication topology (i.e. each UAV can reconfigure its communication topology into A_r to recover the formation shape).

The root node v_i of A_r denotes a UAV that cannot be the formation leader, and then A_r cannot be a reconfigured communication topology (i.e. each UAV cannot reconfigure its communication topology into A_r to recover the formation shape). However, this doesn’t mean that there must be no other reconfigured communication topologies.

Therefore, in order to find the optimal reconfigured communication topology in the above two cases, this article proposes a new method based on MCA. First, a special node called virtual leader (VL) and its corresponding outgoing arcs are added into $G_{r} = (V_{r}, E_{r}, W_{r}, P_{r})$ to form an extended reconfigured communication link graph ${G'}_{r} = ({V'}_{r}, {E'}_{r}, {W'}_{r}, P_{r})$ as follows:

${V'}_{r} = {v_{0}} \cup V_{r}$ is the set of nodes, where v₀ is the virtual leader (VL) that denotes an imaginary point in the predefined formation reference trajectory.

${E'}_{r} = {e_{0 k}} \cup E_{r}, 1 \leq k \leq | V_{r} |$ is the set of arcs, where e_0k denotes that UAV_k knows the predefined formation reference trajectory (i.e., UAV_k can be the formation leader).

${W'}_{r} = {w (e_{0 k})} \cup W_{r}, e_{0 k} \in {E'}_{r}$ is the set of weights of arcs, where all outgoing arcs of v₀ have the same weight, which is $w (e_{0 k}) = (\sum_{i = 1}^{| V |} \sum_{j = 1}^{| V |} w (e_{i j}) + 1, e_{i j} \in E)$ (i.e., $w (e_{0 k})$ is larger than the sum of weights of all arcs in G).

Second, the MCA of ${G'}_{r}$ denoted by A′_r is calculated. Finally, based on theorem 3, the optimal reconfigured communication topology A_r can be achieved by deleting v₀ and its outgoing arcs from A′_r.

Theorem 3

If the MCA of G′_r denoted by A′_r exists and v₀ has only one outgoing arc in A′_r, then the optimal reconfigured communication topology A_r exists and it can be achieved by deleting v₀ and its outgoing arcs from A′_r.

Proof

First, if A′_r exists, A′_r must be a spanning tree of G′_r, which means that A′_r must contain all nodes in G′_r, and each node in A′_r must have an incoming arc except for the root node. Moreover, v₀ does not have any incoming arc based on the definition of G′_r, so v₀ must be the root node of A′_r and have at least an outgoing arc. Second, because G′_r has $| V_{r} | + 1$ nodes, A′_r only has $| V_{r} |$ arcs. If v₀ has m ≥ 2 outgoing arcs in A′_r, then after deleting v₀ and its outgoing arcs from A′_r, only $| V_{r} | - m \leq | V_{r} | - 2$ arcs and $| V_{r} |$ nodes remain in A′_r, which cannot form a communication topology because $| V_{r} |$ nodes need at least $| V_{r} | - 1$ arcs to form a communication topology. Therefore, only when v ₀ has one outgoing arc in A′_r, the optimal reconfigured communication topology A_r exists. Third, if A_r exists, it must be a spanning tree of G_r and roots at a node v_k which denotes a UAV that can be the formation leader (i.e. v_k must have an incoming arc e_0k in G′_r). Therefore, v₀, e_0k, and A_r can form a spanning tree of G′_r denoted by B′_r, where $w ({B'}_{r}) = w (A_{r}) + w (e_{0 k}) and w (e_{0 k}) = (\sum_{i = 1}^{| V |} \sum_{j = 1}^{| V |} w (e_{i j})) + 1 \geq w (A_{r}) + 1$ . Let B″_r denote any spanning tree of G′_r. If v₀ has only one outgoing arc e_0k in B″_r, it will form a spanning tree of G_r denoted by B_r after deleting v₀ and e_0k from B″_r. Then, $w ({B ″}_{r}) = w (B_{r}) + w (e_{0 k}) \geq w (A_{r}) + w (e_{0 k})$ , which means $w ({B ″}_{r}) \geq w ({B'}_{r})$ . If v₀ has two or more outgoing arcs in B″_r, then $w ({B ″}_{r}) \geq 2 \times w (e_{0 k}) \geq w (A_{r}) + 1 + w (e_{0 k})$ , which also means $w ({B ″}_{r}) \geq w ({B'}_{r})$ . Therefore, B′_r must be the MCA of G′_r (i.e. ${B'}_{r} = {A'}_{r} and w ({B'}_{r}) = w ({A'}_{r}) = w (A_{r}) + w (e_{0 k})$ ), and A_r can be achieved by deleting v₀ and its outgoing arcs from B′_r (A′_r).

Based on the above analysis, this article proposes a decentralized communication topology reconfiguration algorithm under communication faults based on MCA, which is executed in each UAV when a communication fault occurs. Taking UAV_i as an example, if it receives a communication fault notification from other UAV through the BC or detects its own communication fault, it will run the algorithm as shown in Table 3.

Table 3.

Algorithm 2: Communication topology reconfiguration under communication faults.

Algorithm 2: Communication topology reconfiguration under communication faults
Input: Current communication link graph $G = (V, E, W, P)$ and current communication topology $A = (V, E^{}, W^{}, P)$ .
Output: The reconfigured communication link graph $G_{r} = (V_{r}, E_{r}, W_{r}, P_{r})$ and the optimal reconfigured communication topology $A_{r} = (V_{r}, E_{r}^{}, W_{r}^{}, P_{r})$ .
Step 1. Let $G_{r} = G and A_{r} = NULL$ .
Step 2. According to the type of communication faults, delete the faulty arcs or nodes of G_r and A.
Step 3. If no arcs in A are deleted by step 2, which means that the communication topology reconfiguration is not needed, then let $A_{r} = A$ and return.
Step 4. If v_i is deleted by step 2 and UAV_i cannot be the formation leader, which means that UAV_i should first fly up to another height $h_{i} = h_{0} + 200 \times i$ as soon as possible to avoid collision with other UAVs and then fly back to its own UAV base alone (i.e. UAV_i does not belong to the formation from now on), then return.
Step 5. If v_i is deleted by step 2 and UAV_i can be the formation leader, which means that UAV_i should first fly up to another height $h_{i} = h_{0} + 200 \times i$ as soon as possible to avoid collision with other UAVs and then track the predefined formation reference trajectory alone at the different height h_i from other UAVs (i.e. UAV_i does not belong to the formation from now on), then return.
Step 6. Establish the extended reconfigured communication link graph G′_r by adding VL (v₀) and its corresponding outgoing arcs into G_r.
Step 7. Calculate the MCA of G′_r, which is denoted by A′_r.
Step 8. If v₀ has only an outgoing arc e_0j in A′_r, delete v₀ and e_0j from A′_r to get the optimal reconfigured communication topology A_r (i.e. UAV_j is the new formation leader). Otherwise, A_r doesn’t exist (i.e. the formation shape cannot be kept and the formation should be separated into two or more subformations, where for each e_0j in A′_r, UAV_j is selected to be the formation leader of a subformation).

UAV: unmanned aerial vehicle; MAC: minimum cost arborescence.

After running algorithm 2, all remaining UAVs in the formation switch to the optimal reconfigured communication topology to quickly recover the formation shape. The computation complexity of algorithm 2 mainly depends on the computation complexity of step 7 in which the faster implementation of Edmonds’ algorithm in the study of Gabow et al.is used. Therefore, the computation complexity of algorithm 2 is $O (| {E'}_{r} | + | {V'}_{r} | \times log | {V'}_{r} |)$ , where $| {E'}_{r} | \leq | E_{r} | + | V_{r} | \leq | E | + | V | and | {V'}_{r} | = | V_{r} | + 1 \leq | V | + 1$ . Compared to the communication topology reconfiguration algorithms in the studies of Giulietti et al., Pollini et al., and Yang et al., algorithm 2 has the following advantages:

It has a lower computation complexity than the algorithm with a computation complexity of $O ({| V |}^{2})$ in the studies of Giulietti et al. and Pollini et al. and the algorithm with a computation complexity of $O (\frac{{(| V | - 1)}^{3}}{2} + (2 μ + m + 1) (| V | - 1))$ in Yang et al.’s study, where m denotes the number of UAVs with transmitter failure and μ denotes the number of communication faults.

It can achieve a better reconfigured communication topology, which has less formation communication cost.

It can deal with more types of communication faults.

Communication topology reoptimization under communication faults

After the communication topology reconfiguration following some communication faults, all UAVs are kept safe, some UAV may leave the formation to track the predefined formation reference trajectory alone at a different height or fly back to its own UAV base alone, and the remaining UAVs will continue keeping the formation shape. However, the formation communication cost may not be optimal (minimal). It may be necessary to reoptimize the communication topology by a UAV position reconfiguration in the formation shape, which includes exchanging UAV positions in the formation shape or moving a UAV to fill an empty position in the formation shape left by a UAV that has left the formation.

Because there are many possible UAV position reconfigurations and under each UAV position reconfiguration, there are also many possible communication topologies, the objective of the communication topology reoptimization problem under communication faults is to determine the optimal UAV position configuration, under which the communication topology with the minimal formation communication cost exists. Therefore, this problem can also be modeled as the MCA problem in graph theory. First, for each possible UAV position configuration P_n, we can construct its corresponding extended communication link graph G′_n. Then, we can use Edmonds’ algorithm to calculate the MCA of G′_n to get a candidate optimal communication topology A_n for P_n. Finally, all candidate optimal communication topologies for each UAV position configuration are compared to find the reoptimized communication topology A_o with the minimal formation communication cost and its corresponding reoptimized UAV position configuration P_o.

Based on the above analysis, this article proposes a decentralized communication topology reoptimization algorithm based on MCA, which is executed in each remaining UAV in the formation. Taking UAV_i as an example, the steps of this algorithm are shown in Table 4.

Table 4.

Algorithm 3: Communication topology reoptimization under communication faults.

Algorithm 3: Communication topology reoptimization under communication faults
Input: The formation communication cost w(A) of the communication topology A before the communication faults, the reconfigured communication link graph $G_{r} = (V_{r}, E_{r}, W_{r}, P_{r})$ , and the reconfigured communication topology $A_{r} = (V_{r}, E_{r}^{}, W_{r}^{}, P_{r}), where V_{r} \subseteq V$ because some UAVs may have left the formation.
Output: The reoptimized communication topology $A_{o} = (V_{r}, E_{o}^{}, W_{o}^{}, P_{o})$ , where P_o is the reoptimized UAV position configuration.
Step 1. Let n = 1, $A_{o} = A_{r}$ .
Step 2. If the current communication faults cause some UAV to leave the formation, then go to step 4.
Step 3. If $w (A_{o}) = w (A)$ , the communication topology reoptimization is not needed and go to step 11.
Step 4. Let n = n + 1. If n $\geq \frac{\| V \|!}{(\| V \| - \| V_{r} \|)!}$ , go to step 11.
Step 5. Get another unused UAV position configuration P_n, and establish the corresponding communication link graph $G_{n} = (V_{r}, E_{n}, W_{n}, P_{n})$ based on $G_{r} = (V_{r}, E_{r}, W_{r}, P_{r})$ .
Step 6. Establish the extended communication link graph ${G'}_{n} = ({V'}_{r}, {E'}_{n}, {W'}_{n}, P_{n})$ by adding VL (v₀) and its corresponding outgoing arcs into $G_{n} = (V_{r}, E_{n}, W_{n}, P_{n})$ .
Step 7. Calculate the MCA of G′_n, which is denoted by A′_n.
Step 8. If A′_n does not exist or v₀ has more than one outgoing arcs in A′_n, go to step 4.
Step 9. Delete v₀ and its outgoing arc from A′_n to get a new candidate optimal communication topology A_n. If one of the following conditions satisfies, let $A_{o} = A_{n}, where P_{o} = P_{n}$ .
a. $w (A_{n}) < w (A_{o})$ .
b. $w (A_{n}) = w (A_{o})$ , but the sum of moving distances required for UAV position reconfiguration from P_r to P_n is less than from P_r to P_o.
Step 10. If new communication fault information is not received, go to step 4; otherwise, let $A_{o} = A_{r}$ (i.e. the communication topology reoptimization is interrupted).
Step 11. A_o is the reoptimized communication topology, where P_o is the reoptimized UAV position configuration.

UAV: unmanned aerial vehicle; MAC: minimum cost arborescence.

In step 5 of algorithm 3, each possible UAV position configuration P_n must be a permutation by taking out |V_r| elements from |V| different elements, which are, respectively, $1, 2, \dots, | V |$ and denote different positions in the formation shape. Therefore, the total of all possible P_n is $\frac{| V |!}{(| V | - | V_{r} |)!}$ . In step 9 of algorithm 3, the moving distance of a UAV required for UAV position reconfiguration is the Euclidean distance between its original position and its new position in the formation shape.

After running algorithm 3, all remaining UAVs will switch to the reoptimized communication topology and continue keeping the formation shape. The core step of algorithm 3 is step 7, where the faster implementation of Edmonds’ algorithm in Gabow et al.’s study is used. As can be seen from step 4, step 7 will be run no more than $\frac{| V |!}{(| V | - | V_{r} |)!}$ times. Therefore, the computation complexity of algorithm 3 is $O (\frac{| V |!}{(| V | - | V_{r} |)!} \times (| {E'}_{n} | + | {V'}_{r} | \times log | {V'}_{r} |)), where | {E'}_{n} | \leq | E_{n} | + | V_{r} | \leq | E | + | V | and | {V'}_{r} | = | V_{r} | + 1 \leq | V | + 1$ . The computation complexity of algorithm 3 is relatively high. However, because all UAVs are kept safe after communication topology reconfiguration, the remaining UAVs can execute algorithm 3 and then perform the UAV position reconfiguration only in their spare time during the formation flight.

Compared to the communication topology reoptimization algorithm in the studies of Giulietti et al. and Pollini et al., algorithm 3 has the following advantages:

It has adequate theoretical basis to ensure that it can achieve the optimal communication topology by UAV position reconfiguration after communication faults.

It is more flexible, because it can adapt to any formation shape.

Simulation results and analysis

Two simulations are carried out in MATLAB to demonstrate the efficiency of our proposed fault-tolerant communication topology management method under communication faults for the leader–follower UAV formation. The first simulation demonstrates the efficiency of algorithm 1 for the initial communication topology optimization before the formation flight, and the second simulation demonstrates the efficiency of algorithms 2 and 3 for the communication topology reconfiguration and reoptimization under different types of communication faults during the formation flight.

Assume that five UAVs need to form and keep a wedge formation shape as shown in Figure 2, where all positions, denoted by ${1, 2, 3, 4, 5}$ , are at the same height (h₀ = 5000) and the distances between these positions are marked out.

Figure 2.

Given formation shape before the formation flight.

In addition, only UAV₁, UAV₂, and UAV₄ can be used as the formation leader. The predefined formation reference trajectory is a one-fourth arc from $(1000, 1000, h_{0}) to (5000, 5000, h_{0})$ , where the center is $(5000, 1000, h_{0})$ , the radius is 4000 m, the speed of each UAV is 100 m/s, T_control is 0.5 s, and T_active is 2 s. The initial coordinates and heading angle of each UAV are shown below in Table 5.

Table 5.

Initial coordinates and heading angle of each UAV.

UAV	X	Y	Z	Heading angle (°)
UAV₁	1000	1000	5000	90
UAV₂	1067.34	617.77	5000	90
UAV₃	1894.84	516.62	5000	90
UAV₄	1027.77	331.76	5000	90
UAV₅	1575.76	225.64	5000	90

UAV: unmanned aerial vehicle.

Initial communication topology optimization before the formation flight

Using the above experiment parameters as input, each UAV runs algorithm 1 to calculate the optimal initial communication topology as follows: In step 1, the initial value of UAV position configuration P is set to ${1, 2, 3, 4, 5}$ (i.e. the ith position in the formation shape is assigned to UAV_i), and the communication link graph $G = (V, E, W, P)$ is constructed, which is shown in Figure 3(a). In step 2, the MCA A of G is calculated, which is shown in Figure 3(b). In step 3, the root node of A is v₁ and UAV₁ can be the formation leader, so step 4 is ignored. In step 5, A is the optimal initial communication topology, whose the total cost is 2271 as shown in Figure 3(c), and P is the most appropriate UAV position configuration.

Figure 3.

Main calculation process of algorithm 1.

Comparatively, the method in the studies of Giulietti et al. and Pollini et al. can get an optimal initial communication topology with a larger total cost (3674) as shown in Figure 4(a), and its computation complexity is higher than algorithm 1. The method in the study of Yang et al. can get the same optimal initial communication topology as algorithm 1, which is shown in Figure 4(b), but its computation complexity is higher than that of algorithm 1.

Figure 4.

Comparison of initial communication topology optimization results.

After getting the optimal initial communication topology, each UAV will use its formation controller described in equation (4) to form and keep the formation shape. Assume that no communication faults occur throughout the formation flight. Figure 5 shows the tracks of all UAVs on the horizontal plane throughout the formation flight, the positions of UAVs at t = 1 s, t = 40 s, t = 80 s and t = 128 s are marked. From this, we can see that the formation shape is formed quickly and then kept until the end.

Figure 5.

Tracks of UAVs on the horizontal plane without communication faults. UAV: unmanned aerial vehicle.

Communication topology reconfiguration and reoptimization under communication faults

To demonstrate the efficiency of our proposed method under different types of communication faults listed in Table 2, we designed six different communication fault scenarios (shown in Table 6), and then carried out the contrast experiments for these scenarios to compare our method with the methods in the studies of Giulietti et al., Pollini et al., and Yang et al., respectively. In the six scenarios, the unicast transmitter failure is divided into scenarios 2 and 3 because the method described in the study of Yang et al. does not consider the unicast transmitter failure of the formation leader. Also, the broadcast transmitter failure and the broadcast receiver failure are merged into scenario 6 because our method treats them in the same way.

Table 6.

Six different communication fault scenarios.

Scenario name	Communication fault type	Details
Scenario 1	Link interrupt	The link interrupt occurs in e ₁₂ and e ₁₃ at t = 45 s.
Scenario 2	Unicast transmitter failure of following UAV	The unicast transmitter failure occurs in UAV₂ at t = 45 s.
Scenario 3	Unicast transmitter failure of formation leader	The unicast transmitter failure occurs in UAV₁ at t = 45 s.
Scenario 4	Unicast receiver failure	The unicast receiver failure occurs in UAV₄ at t = 45 s.
Scenario 5	Unicast transceiver failure	The unicast transceiver failure occurs in UAV₁ at t = 45 s.
Scenario 6	Broadcast transmitter or receiver failure	The broadcast transmitter failure occurs in UAV₃ t = 45 s.

UAV: unmanned aerial vehicle.

Next, we take scenario 2 as an example to illustrate the main calculation process of algorithms 2 and 3. When the unicast transmitter failure occurs in UAV₂, UAV₂ itself can detect this fault and will notify other UAVs of this information through the BC. After receiving this information, each UAV must quickly reconfigure the formation topology to ensure the safety of all UAVs. Therefore, without exchanging the UAV positions in the formation shape, each UAV runs algorithm 2 to calculate the reconfigured communication topology as follows: In step 1, the reconfigured communication link graph G_r and the optimal reconfigured communication topology A_r are initialized. In step 2, the faulty arcs in G_r and in the current communication topology A are deleted according to this communication fault, and the modified G_r and the modified A are shown in Figure 6(a) and (b), respectively. In step 3, because e₂₃ and e₂₄ are deleted by step 2, the remaining operations of step 3 are not executed. In steps 4 and 5, because v₂ is not deleted by step 2, the remaining operations of steps 4 and 5 are also not executed. In step 6, the extended reconfigured communication link graph G′_r is established and shown in Figure 6(c). In step 7, the MCA A′_r of G′_r is calculated and shown in Figure 6(d). In step 8, because v₀ has only an outgoing arc e₀₁ in A′_r, the optimal reconfigured communication topology A_r is obtained by deleting v₀ and e₀₁ from A′_r, and A_r is shown in Figure 6(e).

Figure 6.

Main calculation process of algorithm 2 in scenario 2.

After the communication topology reconfiguration described above, all UAVs are kept safe and each UAV can reoptimize the communication topology by the UAV position reconfiguration in the formation shape. Therefore, each UAV runs algorithm 3 to calculate the reoptimized communication topology as follows: In step 1, the reoptimized communication topology A_o is initialized as the reconfigured communication topology A_r. In step 2, because no UAV leaves the formation, go to step 3. In step 3, because $w (A_{o})$ is 2656 and w(A) is 2271, which means that $w (A_{o}) > w (A)$ , the communication topology reoptimization is needed, and go to step 4. Then, steps 4–10 will be executed repeatedly several times. For example, when n = 13 in step 4, go to step 5 because n <5!. In step 5, P_n is {1,4,2,3,5} and the corresponding communication link graph G_n is established and shown in Figure 7(a). In step 6, the extended communication link graph G′_n is established and shown in Figure 7(b). In step 7, the MCA A′_n of G′_n is calculated and shown in Figure 7(c). In step 8, because A′_n exists and v₀ has only one outgoing arc e₀₁ in A′_n, go to step 9. In step 9, a new candidate optimal communication topology A_n, shown in Figure 7(d), is obtained by deleting v₀ and e₀₁ from A′_n. Because $w (A_{n}) = 2271 and w (A_{o}) = 2656$ , which means that $w (A_{n}) < w (A_{o})$ , then A_o will be replaced by A_n and P_o will be replaced by P_n. In step 10, because no new communication fault information is received, go to step 4 and perform the next execution. After all executions, the reoptimized communication topology A_o in step 11 is shown in Figure 7(e), where P_o is {1,4,3,2,5}. Compared with A_n in Figure 7(d), $w (A_{n}) = w (A_{o}) = 2271$ , the sum of moving distances required for UAV position reconfiguration from $P_{r} = {1, 2, 3, 4, 5} to P_{n} = {1, 4, 3, 2, 5}$ is 1000, and the sum of moving distances required for UAV position reconfiguration from $P_{r} = {1, 2, 3, 4, 5} to P_{o} = {1, 4, 2, 3, 5}$ is 2085, so A_o in Figure 7(e) is better than A_n in Figure 7(d) according to the second condition in step 9.

Figure 7.

Main calculation process of algorithm 3 in scenario 2.

The results of six contrast experiments are listed in Table 7. From which we can reach the following conclusions:

Our method can handle more types of communication faults than the methods in the studies of Giulietti et al., Pollini et al., and Yang et al., whereas the method in Yang et al.’s study can only handle the link interrupt as in scenario 1 and the unicast transmitter failure of following UAV as in scenario 2, and the method in the studies of Giulietti et al. and Pollini et al. cannot handle the broadcast transmitter failure or the broadcast receiver failure as in scenario 6.

Our method can get a better reconfigured communication topology in all scenarios than the method in the studies of Giulietti et al. and Pollini et al. and the method in Yang et al.’s study.

Our method can reoptimize the communication topology by UAV position reconfiguration in the formation shape like the method in the studies of Giulietti et al. and Pollini et al., but the method in Yang et al.’s study cannot do.

Our method can get a better reoptimized communication topology in all scenarios than the method in the studies of Giulietti et al. and Pollini et al..

Table 7.

Results of communication topology reconfiguration and reoptimization under communication faults.

Scenario name	Method used	Reconfigured communication topology	Reoptimized communication topology
Scenario 1: the link interrupts of e ₁₂ and e ₁₃	Our method		No change
	Method in Yang et al.’s study		No support
	Method in the studies of Giulietti et al. and Pollini et al.		No change
Scenario 2: the unicast transmitter failure of UAV₂	Our method
	Method in Yang et al.’s study		No support
	Method in the studies of Giulietti et al. and Pollini et al.		No change
Scenario 3: the unicast transmitter failure of UAV₁	Our method		No change
	Method in Yang et al.’s study	No support	No support
	Method in the studies of Giulietti et al. and Pollini et al.
Scenario 4: the unicast receiver failure of UAV₄	Our method		No change
	Method in Yang et al.’s study	No support	No support
	Method in the studies of Giulietti et al. and Pollini et al.
Scenario 5: the unicast transceiver failure of UAV₁	Our method		No change
	Method in Yang et al.’s study	No support	No support
	Method in the studies of Giulietti et al. and Pollini et al.
Scenario 6: the broadcast transmitter failure of UAV₃	Our method
	Method in Yang et al.’s study	No support	No support
	Method in the studies of Giulietti et al. and Pollini et al.	No support	No support

UAV: unmanned aerial vehicle.

It must be stressed that in scenarios 3 and 5, the reoptimized communication topology achieved by the method in the studies of Giulietti et al. and Pollini et al. is even worse than its reconfigured communication topology, which means that the method in the studies of Giulietti et al. and Pollini et al. is not always reliable in the communication topology reoptimization. By contrast, algorithm 3 is based on Edmonds’ algorithm for the MCA problem in graph theory, so it has an adequate theoretical basis to ensure that it will achieve a reoptimized communication topology that is no worse than its reconfigured communication topology.

Figure 8 shows the tracks of all UAVs on the horizontal plane throughout the formation flight in the six communication fault scenarios, respectively, where the positions of UAVs at t = 1 s, t = 40 s, t = 80 s, and t = 128 s are marked.

Figure 8.

Tracks of all UAVs on the horizontal plane, respectively, in six communication fault scenarios. UAV: unmanned aerial vehicle.

As shown in Figure 8(a) and (c), when link interrupt occurs in e₁₂ and e₁₃, or the unicast transmitter failure occurs in UAV₁, UAV₂ and UAV₃ cannot receive the information from UAV₁, and can only maintain their current speed and heading angle. Therefore, they begin to deviate from their correct trajectory. Meanwhile, UAV₄ and UAV₅ also begin to deviate from their correct trajectory, since UAV₄ follows UAV₂, and UAV₅ follows UAV₃. After T_active seconds, all UAVs switch to the reconfigured communication topology and the formation shape is quickly recovered. Further, the reoptimized communication topology is the same as the reconfigured communication topology, so the formation shape is kept until the end.

As shown in Figure 8(b), when the unicast transmitter failure occurs in UAV₂, UAV₃ and UAV₄ cannot receive the information from UAV₂, and they begin to deviate from their correct trajectory. UAV₅ also begins to deviate from its correct trajectory since it follows UAV₃. After T_active seconds, all UAVs switch to the reconfigured communication topology and the formation shape is quickly recovered. Further, after getting the reoptimized communication topology, UAV₂ and UAV₄ exchange their positions, and then the formation shape is kept until the end.

As shown in Figure 8(d), when the unicast receiver failure occurs in UAV₄, UAV₄ cannot receive the information from UAV₂ so it begins to deviate from its correct trajectory. After T_active seconds, all UAVs switch to the reconfigured communication topology, where UAV₄ is the new formation leader, and the formation shape is quickly recovered. Further, the reoptimized communication topology is the same as the reconfigured communication topology, so the formation shape is kept until the end.

As shown in Figure 8(e), when the unicast transceiver failure occurs in UAV₁, UAV₁ soon flies up to another height $h_{1} = h_{0} + 200$ to avoid collision with other UAVs, and then tracks the predefined formation reference trajectory alone at the different height h₁. UAV₂ and UAV₃ cannot receive the information from UAV₁ and they begin to deviate from their correct trajectory. Meanwhile, UAV₄ and UAV₅ also begin to deviate from their correct trajectory, since UAV₄ follows UAV₂ and UAV₅ follows UAV₃. After T_active seconds, all UAVs switch to the reconfigured communication topology and the formation shape is quickly recovered. Further, the reoptimized communication topology is the same as the reconfigured communication topology, so the formation shape is kept until the end.

As shown in Figure 8(f), when the broadcast transmitter failure occurs in UAV₃, UAV₃ soon flies up to another height $h_{3} = h_{0} + 600$ to avoid collision with other UAVs and then flies back to its own UAV base alone. UAV₅ cannot receive the information from UAV₃, it begins to deviate from its correct trajectory. After T_active seconds, all UAVs switch to the reconfigured communication topology and the formation shape is quickly recovered. Further, after receiving the reoptimized communication topology, UAV₁ fills the empty position left by UAV₃, and then the formation shape is kept until the end.

Conclusions

During the UAV formation flight, one or more UAVs may encounter some communication faults, which can cause those UAVs to become unable to keep the original formation shape. Accidental UAV collisions could also occur. Therefore, this article proposes a novel fault-tolerant communication topology management method for the leader–follower UAV formation to guarantee the safety of all UAVs and continue keeping the formation shape under multiple types of communication faults. This method is composed of three algorithms, which are based on Edmonds’ algorithm for the MCA problem in graph theory.

Given a formation shape before the formation flight, this method uses a directed weighted graph to describe all available communication links in the formation, and uses algorithm 1 to achieve the MCA of this directed weighted graph (i.e. the optimal initial formation communication topology with the minimum formation communication cost). When some communication faults occur, this method first deletes the faulty nodes or arcs in the original directed weighted graph, and then uses algorithm 2 to achieve the MCA of this modified directed weighted graph (i.e. the reconfigured and suboptimal formation communication topology), which can help all UAVs to maintain safety from collision and quickly recover the original formation shape. After the communication topology reconfiguration, this method uses algorithm 3 to reoptimize the communication topology by reconfiguring the UAV positions in the formation shape, and then continue keeping the formation shape. Simulation results have verified the effectiveness of this method.

Future research directions include (1) a fault-tolerant communication topology management method under communication faults for other types of leader–follower UAV formation that uses a new formation control method as in the studies of Hou and Fantoni and Park et al. and (2) a fault-tolerant communication topology management method under communication faults for the virtual structure-based and consensus-based UAV formation.

Footnotes

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This research is supported by the National Natural Science Foundation of China (71401048, 71671059, 71521001, 71690230, 71690235, 71472058), the Anhui Provincial Natural Science Foundation (1508085MG140), and the Fundamental Research Funds for the Central Universities (JZ2016HGTB0726).

References

Pitre

Delbalzo

. UAV Route planning for joint search and track missions-an information-value approach. IEEE Trans Aerosp Electron Sys 2012; 48(3): 2551–2565.

Nigam

Bieniawski

Kroo

. Control of multiple UAVs for persistent surveillance: algorithm and flight test results. IEEE Trans Control Sys Technol 2012; 20(5): 1236–1251.

Zhang

. Cooperative localization against GPS signal loss in multiple UAVs flight. J Sys Eng Electron 2011; 22(01): 103–112.

Han

. Low-cost multi-UAV technologies for contour mapping of nuclear radiation field. J Int Robot Sys 2013; 70(1–4): 401–410.

. Hierarchical method of task assignment for multiple cooperating UAV teams. J Sys Eng Electron 2015; 26(05): 1000–1009.

Anderson

BDO

Fidan

. UAV formation control: theory and application. In: Blondel

Boyd

Kimura

(eds) Recent advances in learning and control, London: Springer, 2008. pp. 15–33.

Giulietti

Pollini

Innocenti

. Autonomous formation flight. IEEE Control Sys 2000; 20(6): 34–44.

Pollini

Giulietti

Innocenti

. Robustness to communication failures within formation flight. In: 2002 American Control Conference (ed Taylor

), Hilton Anchorage and Egan Convention Center, Anchorage, Alaska, USA, 8–10 May 2002, pp. 2860–2866. IEEE.

Ren

. Consensus strategies for cooperative control of vehicle formations. IET Control Theory Appl 2007; 1(2): 505–512.

10.

Yang

Jiang

Zhang

. Fault-tolerant shortest connection topology design for formation control. Int J Control Automat Sys 2014; 12(1): 29–36.

11.

Chen

Jiang

Cui

. Actuator fault-tolerant control of ocean surface vessels with input saturation. Int J Robust Nonlin 2016; 26: 542–564.

12.

Chen

Shi

Lim

. Adaptive Neural Fault-Tolerant Control of a 3-DOF Model Helicopter System. Ieee Transactions on Systems Man Cybernetics-Systems 2016; 46(2): 260–270.

13.

Chen

Tao

. Adaptive Fault-Tolerant Control of Uncertain Nonlinear Large-Scale Systems With Unknown Dead Zone. Ieee Transactions on Cybernetics 2016; 46(8): 1851–1862.

14.

Seanor

Campa

. Design and flight testing evaluation of formation control laws. IEEE Trans Control Sys Technol 2006; 14(6): 1105–1112.

15.

Yun

Chen

Lum

. Design and implementation of a leader-follower cooperative control system for unmanned helicopters. J Control Theory Appl 2010; 8(1): 61–68.

16.

Kim

Tahk

. Cascade-type guidance law design for multiple-UAV formation keeping. Aerosp Sci Technol 2011; 15(6): 431–439.

17.

Hou

Fantoni

. Distributed leader-follower formation control for multiple quadrotors with weighted topology. In: 2015 10th system of systems engineering conference (SoSE) (eds Benavidez

Cinar

), San Antonio, Texas, USA, 17–20 May 2015, pp. 256–261. IEEE.

18.

Park

Cho

Lee

. Formation flight of multiple UAVs via onboard sensor information sharing. Sensors 2015; 15(7): 17397–17419.

19.

Linorman

NHM

Liu

HHT

. Formation UAV flight control using virtual structure and motion synchronization. In: 2008 American control conference (ed Annaswamy

), Westin Seattle Hotel, Seattle, Washington, USA, 11–13 June 2008, pp. 1782–1787. IEEE.

20.

Low

. A dynamic virtual structure formation control for fixed-wing UAVs. In: 2011 9th IEEE international conference on control and automation (ICCA) (eds Zhang

Pérez

), Santiago, Chile, 19–21 December 2011, pp. 627–632. IEEE.

21.

Low

. A flexible virtual structure formation keeping control for fixed-wing UAVs. In: 2011 9th IEEE International Conference on Control and Automation (ICCA) (eds Zhang

Pérez

), Santiago, Chile, 19–21 December 2011, pp. 621–626. IEEE.

22.

Giulietti

Pollini

Innocenti

. Formation flight control: a behavioral approach. In: AIAA guidance, navigation, and control conference and exhibit, Montreal, Canada, 6–9 August 2001, American Institute of Aeronautics and Astronautics.

23.

Kim

. Optimum design of three-dimensional behavioural decentralized controller for UAV formation flight. Eng Opt 2009; 41(3): 199–224.

24.

Sharma

R K

Ghose

. Collision avoidance between UAV clusters using swarm intelligence techniques. Int J Sys Sci 2009; 40(5): 521–538.

25.

Turpin

Michael

Kumar

. Decentralized formation control with variable shapes for aerial robots. In: 2012 IEEE international conference on robotics and automation (ed Meng

), River Centre, Saint Paul, Minnesota, USA, 14–18 May, 2012, pp. 23–30. IEEE.

26.

Wang

Xin

. Integrated optimal formation control of multiple unmanned aerial vehicles. IEEE Trans Control Sys Technol 2013; 21(5): 1731–1744.

27.

Dong

Shi

. Time-varying formation control for unmanned aerial vehicles: theories and applications. IEEE Trans Control Sys Technol 2015; 23(1): 340–348.

28.

Xue

Cai

. Formation flight control of multi-UAV system with communication constraints. J Aeros Technol Manage 2016; 8(2): 203–210.

29.

Yang

Jiang

. Fault tolerant formations control of UAVs subject to permanent and intermittent faults. J Int Robot Sys 2014; 73(1–4): 589–602.

30.

Bekmezcia

Sahingoza

Temel

. Flying ad-hoc networks (FANETs): a survey. Ad Hoc Networks 2013; 11(3): 1254–1270.

31.

Chu

Liu

. On the shortest arborescence of a directed graph. Sci Sinica 1965; 14: 1396–1400.

32.

Edmonds

. Optimum branchings. J Res Nat Bur Stand 1967; 71(4): 233–240.

33.

Tarjan

. Finding optimum branchings. Networks 1977; 7(1): 25–35.

34.

Gabow

Galil

Spencer

. Efficient algorithms for finding minimum spanning trees in undirected and directed graphs. Combinatorica 1986; 6(2): 109–122.