Localized Fault Tolerant Algorithm Based on Node Movement Freedom Degree in Flying Ad Hoc Networks

Abstract

Flying ad hoc network (FANET) is a communication network for data transmission among Unmanned Aerial Vehicles (UAVs). In ad hoc network, the UAVs movement is usually applied to improve network fault-tolerance, but it easily causes the disconnection of communication links, and the success rate is low. In this paper, we propose a local fault-tolerant control algorithm based on node movement freedom degree (LFTMF). Under the constraint of node movement freedom degree, the algorithm transforms the single-connected network into bi-connected network through the autonomous movement of UAVs to improve the fault-tolerant ability of the FANET network. Firstly, the consistency between k-hop cut-points and global cut-points in FANET network is analyzed. Then, based on the k-hop local topology of FANET network, the UAV node movement freedom degree model is established. Finally, according to the location distribution of k-hop cut-points in the FANET network, the bi-connected fault-tolerant network is realized by UAVs cascade movement. Compared with the existing algorithms, simulation results show that the proposed algorithm achieves better performance in success rate, deviation distance, cascade movement ratio and adjustment period.

1. Introduction

Unmanned Aerial Vehicles (UAVs) cluster intelligence and cooperation depend on timely and effective information exchange between different nodes, therefore the communication network is one of the most important design issues of multi-UAV system [1]. UAVs exchange data or instructions through one or more hops in FANET, which is a center-free ad hoc network between UAVs [2]. In three-dimensional single-connected FANET networks, the movement or failure of some UAVs will lead to the disconnection of communication links or network partition, resulting in data transmission failure [3,4,5]. Therefore, it is an urgent problem to establish fault-tolerant networks to ensure the reliable end-to-end connection between UAVs.

A network is defined as bi-connected if there are two disjoint communication paths between any pair of UAV nodes in the network, which is the basic goal of the FANET network fault-tolerant design [6]. Topology control is an effective method to realize fault-tolerant networks [7], which can be divided into three categories. The first method is to maintain network connectivity by adjusting the transmit power of nodes in the network [8,9]. Fidel Aznar [10] proposed a theoretical model of the swarm energy consumption to describe the UAVs energy consumed. R. Ramanathan [11] proposed two distributed heuristic algorithms, which adaptively adjust the transmit power of nodes according to the topology changes and attempts to maintain the topology connectivity using the minimum power. In [12], an adaptive topology control algorithm is proposed to improve the network performance by controlling the transmit power to change the transmission range. M. Mozaffari [13] and F. Lagum [14] analyzed the deployment of a UAV as a flying base station and minimized the total required transmit power of UAV while covering the entire area. However, sometimes the distance between UAVs is so long that the maximum transmit power may be unable to achieve connectivity. The second method is to add relay nodes to the network to improve the fault tolerance capability of UAV network [15,16]. Kashyap A [17] reconstructed the topology of ad hoc network by adding relay nodes to meet the fault tolerance requirements of the network. Jie LI [18] proposed maintaining the fault tolerance UAV ad hoc network through the speed control of relay nodes. However, the additional relay nodes increase the UAV quantity cost. The third method is to use UAV movement in cluster to achieve bi-connected fault-tolerant network [19]. Prithwish first proposed the centralized block movement algorithm [20], but the global topology information of UAV cluster is difficult to obtain and the distance of deviation from original track is too long. Shantanu proposed the distributed node movement algorithm to implement a bi-connected fault-tolerant network [21], but the algorithm causes the disconnection of the original communication link, and the recovery success rate in the sparse network is not high. UAV moves in three-dimensional space, but the existing research on mobile topology control is based on two-dimensional space [19,20,21,22]. Therefore, the research of distributed movement control based on three-dimensional space is of great significance to improve the fault tolerance of UAV dynamic network.

To realize fault-tolerant network, we adopt local movement management to control the network topology. As every UAV has its own task, we can only change its movement in a limited range and direction, which is challenging work. In this paper, we propose the localized fault-tolerant algorithm based on node movement freedom degree (LFTMF) for single-connected FANET networks to realize fault-tolerant network with minimum movement cost. The main contributions are as follows. Firstly, the movement freedom degree model of UAV nodes is established based on k-hop local topology of UAV nodes in three-dimensional FANET. Then, we analyze the consistency of k-hop cut points and global cut points. Finally, we adopt local cascade movement management to achieve bi-connected fault tolerant networks.

The rest of this paper is organized as follows. In Section 2, the system model and problem analysis are introduced. Section 3 presents the local cut point detection algorithm and LFTMF algorithm. Simulation results are discussed in Section 4 and Section 5 gives conclusion.

2. Model and Problem Analysis

The signal transmission in space will cause the change of the receiving power, which will decrease with the increase of the distance between the transmission node and the receiving node. This phenomenon is called large-scale fading model, which is the most basic channel model for FANET network research. When a UAV node $v_i$ sends a wireless signal to $v_j$ in FANET, the receiving power $p_{jr}$ of UAV node j is shown in Equation (1).

$$p_{jr}={\left(\frac{\lambda }{4\pi l_{ij}}\right)}^{\alpha }\frac{G_t{G}_r}{L_m}{p}_{it}$$

(1)

Equation (1) is Fries transfer formula, where $p_{it}$ is the transmission power of node $v_i$, and $\alpha$ is the carrier wavelength of the wireless signal. $l_{ij}$ is the distance between the transmission node $v_i$ and the receiving node $v_j$. $\alpha$ is the path loss coefficient and the worse the environment, the greater the value. $G_t$ is the antenna gain of the transmission node and $G_r$ is the antenna gain of the receiving node. $L_m$ is the loss factor.

In free space, the value of power $p_N$ of noise and interference is assumed to be constant. $SN{R}_{th}$ is the threshold of SNR. Then, the receiving power $p_{jr}$ satisfies Equation (2).

$$p_{jr}=\frac{p_{jr}}{p_N}\ge SN{R}_{th}$$

(2)

When $L_m=1$, $G_t=1$, and $G_r=1$, the maximum transmission distance $R_c$ is shown as Equation (3).

$$R_c=\frac{\lambda }{4\pi }{\left(\frac{p_{it}}{p_N{10}^{\frac{SN{R}_{th}}{10}}}\right)}^{\frac{1}{\alpha }}$$

(3)

The paper assumes that the transmitters are the same and the receivers are the same in FANET network. The values of $\lambda$, $\alpha$ and $p_N$ are constant. Then, the definition of constant C is shown as Equation (4).

$$R_c=\frac{\lambda }{4\pi }{\left(\frac{1}{p_N{10}^{\frac{SN{R}_{th}}{10}}}\right)}^{\frac{1}{\alpha }}$$

(4)

Equation (3) is further abbreviated as Equation (5).

$$R_c=c_1{p}_{it}^{\frac{1}{\alpha }}$$

(5)

From Equation (5), it can be seen that the maximum transmission distance $R_c$ is proportional to the powers of transmission power $p_{it}$. Given the value of transmission power, the value of the maximum transmission distance of the signal is unique. Therefore, we use the distance to represent transmission power in the latter sections.

UAV cluster carries out reconnaissance tasks in three-dimensional barrier-free space, flying in a straight line and every UAV is equipped with GPS and a wireless transceiver with communication distance $R_c$. If the distance between two UAVs is not greater than $R_c$, the two UAV nodes are neighbors and have bi-way communication links. This paper assumes that FANET is an isomorphic network. Nodes $v\in V$ corresponds to UAVs and the bi-way communication links between nodes is represented as edges $e\in E$. UAV nodes and communication links constitute three-dimensional FANET networks topology graph $G=(V,E)$, and the network topology schematic diagram is shown in Figure 1. As the network topology only represents the relative position relationship between UAVs, the topology is planform of three-dimensional network topology in this paper.

At the initial time, the FANET network is single connected, but it is prone to be partitioned, which leads to the failure of communication links. Therefore, it is necessary to construct fault-tolerant network and minimize the distance of deviation from original track.

2.1. Node Movement Freedom Degree Model

To better describe the node movement freedom degree model, some symbols and their definitions are shown in

Table 1. Partial symbols and their definitions.

Symbols	Definitions
$\tau$	The time for each adjustment period.
${\mathit{x}}_i\left(t\right)$	Location of UAV Node $v_i$ at time t.
${\mathit{x}}_{\mathit{p}i}(t+\tau )$	Predictive Location of UAV $v_i$ at time $t+\tau$ in k-hop local topology.
${\mathit{x}}_i^{\prime }(t+\tau )$	The calculated Location of UAV $v_i$ in k-hop local topology at time $t+\tau$.
$l_{ij}$	Distance between UAV Nodes $v_i$ and $v_j$.
$N\left(v_i\right)$	The set of neighbor nodes of UAV $v_i$.
$N_k\left(v_i\right)$	Set of k-hop neighbor nodes of UAV $v_i$.
$N\left[v_i\right]$	Closed set of neighbors of UAV $v_i$, $N\left[v_i\right]=N\left(v_i\right)\cup v_i$.
$D_{mean}$	Network node density.

.

Some important definitions are as follows.

Definition 1.

k-hop local topology, also known as k-hop derived subgraph. Suppose $v_i$ is a node in the network topology graph G and $G_s$ is the derived subgraph of G. If all the nodes in $G_s$ are composed of $v_i$ and its k-hop neighbors, then G is the k-hop local topology of $v_i$ of G.

Definition 2.

k-hop cut point. In the network topology graph G, if c is the cut point of its k-hop local topology, then c is the k-hop cut point.

Definition 3.

Network node density, also called average node degree. The ratio value of the node degree of all nodes in the network topology graph G to the total number of nodes in G is the network node density.

Definition 4.

Generalized leaf nodes. Nodes with a node degree of 1 in the network topology graph G are called leaf nodes. For a cut point c, there exists a set $A\subset N\left(c\right)$, and the neighbor nodes of any node $v_i$ in set A satisfy condition $N\left(v_i\right)\subset A\cup c$, then the nodes in set A are called generalized leaf nodes.

In the k-hop topology of cut point c, the the movement freedom degree ${\alpha }_{i\mathit{d}}$ of node $v_i$ on direction $\mathit{d}$ is defined as the maximum distance that node $v_i$ could move while maintaining connectivity with all its neighbors $N\left(v_i\right)$ in direction $\mathit{d}$. That is to say, the minimum value of the maximum distance of deviation from original track on direction $\mathit{d}$ on the premise that node $v_i$ is connected to each neighbor node $v_k\in N\left(v_i\right)$, and the details are shown in Equation (6).

$${\alpha }_{i\mathit{d}}=\left\{\begin{array}{cc}0,\hfill & v_i\in N_k\left(c\right)\hfill \\ min\left({\mathit{D}}_{i\mathit{d}}\right),\hfill & v_i\notin N_k\left(c\right)\hfill \end{array}\right.$$

(6)

where ${\mathit{D}}_{i\mathit{d}}=\left\{{\alpha }_{i\mathit{d}j}\right\}$ is the maximum distance matrix of deviation from original track of node $v_i$ on direction $\mathit{d}$, constrained by its neighbor node $N\left(v_i\right)$. Element ${\alpha }_{i\mathit{d}j}$ in ${\mathit{D}}_{i\mathit{d}}$ denotes the maximum movement distance of node $v_i$ on direction $\mathit{d}$ only under the constraint of its neighbor $v_j$. According to cosine theorem, ${\alpha }_{i\mathit{d}j}$ satisfies Equation (7).

$$\begin{array}{c}{R}_c^2=l_{ij}^2+{\alpha }_{i\mathit{d}j}^2-2l_{ij}·{\alpha }_{i\mathit{d}j}cos{\theta }_{i\mathit{d}j}\hfill \\ s.t.v_i\notin N_k\left(c\right),l_{ij}<R_c,v_j\in N\left(v_i\right),v_j\mathrm{is}\mathrm{not}\mathrm{generalized}\mathrm{leaf}\mathrm{nodes}\hfill \end{array}$$

(7)

where ${\theta }_{i\mathit{d}j}=<\mathit{d},{\mathit{x}}_j-{\mathit{x}}_i>$ represents the angle between vector $\mathit{d}$ and vector ${\mathit{x}}_j-{\mathit{x}}_i$ and $N_k\left(c\right)$ represents the set of kth-hop neighbor nodes of cut point c. The conditions under which Equation (7) has a feasible solution are shown as the inequality in Equation (8).

$$l_{ij}^{2}co{s}^2{\theta }_{i\mathit{d}j}+R_c^2-l_{ij}^2,l_{ij}<R_c$$

(8)

The inequality in Equation (8) is always established. Thus, the solution of Equation (7) is shown in Equation (9), and the derivation process is as follows.

$${\alpha }_{i\mathit{d}j}=l_{ij}cos{\theta }_{i\mathit{d}j}\pm \sqrt{l_{ij}^{2}si{n}^2{\theta }_{i\mathit{d}j}+R_c^2},l_{ij}<R_c$$

Because $l_{ij}\le R_c$,

$$\begin{array}{c}{l}_{ij}cos{\theta }_{i\mathit{d}j}-\sqrt{l_{ij}^{2}si{n}^2{\theta }_{i\mathit{d}j}+R_c^2}\hfill \\ \le l_{ij}cos{\theta }_{i\mathit{d}j}-\sqrt{l_{ij}^{2}si{n}^2{\theta }_{i\mathit{d}j}+l_{ij}^2}=l_{ij}(cos{\theta }_{i\mathit{d}j}-\sqrt{1+si{n}^2{\theta }_{i\mathit{d}j}}<0\hfill \end{array}$$

$${\alpha }_{i\mathit{d}j}=l_{ij}cos{\theta }_{i\mathit{d}j}+\sqrt{l_{ij}^{2}si{n}^2{\theta }_{i\mathit{d}j}+R_c^2},l_{ij}<R_c$$

(9)

2.2. Problem Analysis

To describe the problem more conveniently, some of the theorems are as follows.

Theorem 1.

If the network is bi-connected, there are no global cut-points in the network topology. If there are no global cut-points in the network topology, the network is bi-connected at least, which means that the network has bi-connectivity or higher connectivity.

Proof of Theorem 1.

Firstly, if the network topology graph G satisfies bi-connectivity, there will be at least two disjoint communication paths between any pair of nodes $v_i$ and $v_j$ in the graph G. Assuming that there is a global cut-point c in the topology graph of a bi-connected network G and a pair nodes $v_i,v_j\in G$. After removing node c, there is no communication path between $v_i$ and $v_j$, which is in contradiction with that G satisfies bi-connectivity. Therefore, if the network topology graph G satisfies bi-connectivity, there is no global cut-point in the G. Then, if the network topology graph G does not have global cut-points, removing any node will not lead to network partition. Therefore, G is not single-connected and it is bi-connected at least. □

A network topology graph G is defined as k-connected if there are k disjoint communication paths between any pair of UAV nodes in the network. When $k=1$, the network topology G is single connected and when $k\ge 2$, the network topology G has fault-tolerant ability and good invulnerability. Therefore, $k=2$ is set to construct a bi-connected fault-tolerant network in this paper. According to Theorem 1, the construction of bi-connected fault-tolerant network can be transformed into the problem of changing cut-points into non-cut points in the network. As the global topology information is unknown, it is necessary to study the cut-point detection algorithm based on k-hop local topology, and approximately minimize the node offset distance based on k-hop local topology of cut-points. The offset distance is the distance of deviation from original track of UAV in this paper.

FANET network fault-tolerant control problem is abstracted as the closed-loop control model shown in Figure 2, and the red node in the predicted topology is cut-point.

The initial network topology is single connected and every UAV executes the control flow.

Step 1: The location of every UAV $v_i$ in the cluster is ${\mathit{x}}_i\left(t\right)$ at time t, and the location predictor of $v_i$ predicts its location ${\mathit{x}}_{\mathrm{p}i}(t+\tau )$ of time $t+\tau$. The k-hop local topology information, which contains the ID of each node and the location information of every UAV at time t and time $t+\tau$, is obtained by k times information exchange with its neighbors. According to the location relationship of nodes, we could get the k-hop local topology $G_s\left(t\right)$ of time t and the k-hop local topology $G_p^{\prime }(t+\tau )$ of time $t+\tau$.

Step 2: The cut-point detector on $v_i$ executes the cut-point detection algorithm based on $G_p^{\prime }(t+\tau )$ to determine whether $v_i$ itself is a cut-point. If $v_i$ is a cut-point, update the cut-point information of the k-hop local topology $G_p^{\prime }(t+\tau )$ and then obtain $G_p(t+\tau )$ by once information exchange with its neighbors.

Step 3: The topology controller of node $v_i$ recalculates the location of UAV nodes in the k-hop local topology of time $t+\tau$ according to the network fault-tolerance requirements and the predicted local network topology $G_p(t+\tau )$. Then, the movement instructions are sent to the destination UAV node through k times information exchange. Finally, the destination UAV node updates its speed according to the decision rules.

3. The Construction of Bi-Connected Fault-Tolerant Networks

3.1. Cut-Point Detection Algorithm Based on k-Hop Local Topology Information

It is the premise of the construction of bi-connected fault-tolerant network to analyze the consistency between k-hop cut-point and global cut-point. Therefore, we study cut-point detection algorithm based on k-hop local topology information. UAV node c can obtain its k-hop local topology by k times information exchange with its neighbors. Then, the depth first search (DFS) algorithm is used to determine whether it is a k-hop cut-point. The flow chart of the algorithm is shown in Figure 3.

3.2. Localized Fault-Tolerant Algorithm Based on Node Movement Freedom Degree (LFTMF)

There are two methods to control node movement: block movement and cascade movement [19]. Block movement is that all UAV nodes in a connected block participate in the movement, which would have a bad impact on the original task. The cascade movement is that some nodes participate in the movement, while others move in the original direction. Therefore, cascade motion is adopted to realize bi-connected fault-tolerant network.

As shown in Figure 4, at time t, the k-hop local topology of a cut-point c is $G_s\left(t\right)$ where the node c is a cut-point. The predicted location of UAV nodes at time $t+\tau$ is ${\mathit{x}}_{\mathit{p}i}(t+\tau )$, which corresponds to the predicted k-hop local topology graph $G_p(t+\tau )$, consisting of nodes $\{1^{\prime },2^{\prime },3,4,5,6\}$ and black solid lines among them of time $t+\tau$. Based on $G_p(t+\tau )$, the locations of node $1^{\prime }$ and node $2^{\prime }$a are moved to node 1 and node 2, respectively. Then, the location at time $t+\tau$ is temporarily updated to ${\mathit{x}}_i^{\prime }(t+\tau )$, as shown in Equation (10), which corresponds to the k-hop local topology graph $G_s^{\prime }(t+\tau )$, consisting of nodes $\{1,2,3,4,5,6\}$ and black solid lines or red dashed lines among them at time $t+\tau$.

$$\begin{array}{c}{\mathit{x}}_i^{\prime }(t+\tau )={\mathit{x}}_{\mathrm{p}i}(t+\tau )+{\mathbf{\Delta }\mathit{x}}_i^{\prime }(t+\tau )\hfill \\ s.t.\parallel {\mathbf{\Delta }\mathit{x}}_i^{\prime }(t+\tau )\parallel <{\alpha }_{i{\mathbf{\Delta }\mathit{x}}_i^{\prime }(t+\tau )}\hfill \end{array}$$

(10)

where ${\mathit{x}}_{\mathrm{p}i}(t+\tau )={\mathit{x}}_i\left(t\right)+v\tau$ predicted by location predictor is the location of node $v_i$ at time $t+\tau$. ${\mathbf{\Delta }\mathit{x}}_i^{\prime }(t+\tau )$ is the offset vector of node $v_i$ and corresponds to the red dashed arrows which from node $1^{\prime }$ to node 1 and from node $2^{\prime }$ to node 2 in Figure 4. All location points $(x_i,y_i,z_i)$ are three-dimensional. ${\alpha }_{i{\mathbf{\Delta }\mathit{x}}_i^{\prime }(t+\tau )}$ is the movement freedom degree of node $v_i$ in the direction ${\mathbf{\Delta }\mathit{x}}_i^{\prime }(t+\tau )$. The total offset distance $l^{\prime }$ based on the k-hop local topology of the cut-point c is shown in Equation (11). The objective of optimization is to minimize $l^{\prime }$, while guaranteeing the realization of bi-connected fault-tolerant networks.

$$\begin{array}{c}\hfill l^{\prime }=\sum _{v_i\in G_s^{\prime }(t+\tau )}\parallel {\mathbf{\Delta }\mathit{x}}_i^{\prime }(t+\tau )\parallel ,s.t.\parallel {\mathbf{\Delta }\mathit{x}}_i^{\prime }(t+\tau )\parallel <{\alpha }_{i{\mathbf{\Delta }\mathit{x}}_i^{\prime }(t+\tau )}\end{array}$$

(11)

The decision rules for directive execution are as follows. Since a node $v_i$ may exists in the k-hop local topology of different cut-points, $v_i$ receives multiple movement instructions. At this time, the movement instructions of the sending node whose node degree is the largest and ID is the smallest is executed. Therefore, the actual offset ${\mathbf{\Delta }\mathit{x}}_i(t+\tau )$ of node $v_i$ at time $t+\tau$ is the ${\mathbf{\Delta }\mathit{x}}_i^{\prime }(t+\tau )$, which meets the above conditions. The actual location ${\mathit{x}}_i(t+\tau )$ of $v_i$ at time $t+\tau$ is shown in Equation (12), and corresponds to the k-hop local topology graph $G_s(t+\tau )$. The total offset distance l is shown in Equation (13). Therefore, the actual trajectory of node 1 and node 2 is the red solid line from node 1 of time t to node 1 of time $t+\tau$ and from node 2 of time t to node 2 of time $t+\tau$ in Figure 4.

$$\begin{array}{c}{\mathit{x}}_i(t+\tau )={\mathit{x}}_{\mathrm{p}i}(t+\tau )+{\mathbf{\Delta }\mathit{x}}_i(t+\tau )\hfill \end{array}$$

(12)

$$\begin{array}{c}\hfill l=\sum _{v_i\in G_s(t+\tau )}\parallel {\mathbf{\Delta }\mathit{x}}_i(t+\tau )\parallel \end{array}$$

(13)

The main idea of LFTMF algorithm is as follows.

• Move the non-cut points to connect the nodes except c based on k-hop local topology $G_p(t+\tau )$ predicted by k-hop cut-point c. Thus, the cut-point c is changed into non-cut point until all global cut points are changed into non-cut points to realize bi-connected fault-tolerant network.
• The value of k is greater than or equal to 3 and the cut-point c is kept static. To ensure the connectivity between the k-hop local topology and the external topology, the movement freedom degrees of the kth-hop nodes of c are 0, and they do not participate in the movement. The k-hop cut-point and $(k-1)$-hop cut-point of the cut-point c are regarded as non-cut points.
• The generalized leaf nodes do not participate in the calculation when calculating the degree of freedom of the cut-point.

We discuss them in three cases according to the characteristics and number of cut-points in k-hop local topology of a cut-point c.

• Case 1: The are no other cut-points in the 1-hop neighbor nodes of cut-point c.
• Case 2: There is only one other cut-point in the 1-hop neighbor nodes of cut-point c.
• Case 3: There are multiple other cut-points in the 1-hop neighbor nodes of cut-point c.

3.2.1. No Other Cut-Points in the 1-Hop Neighbor Nodes of Cut-Point c

Step 1: The k-hop local topology of cut-point c, which excludes cut-point c itself, is divided into M disjoint blocks $S=\{S_1,S_2,\cdots ,S_{\mathrm{M}}\}$, and the nodes in the block are connected. Find the set $S_{max}$ with the largest number of nodes and the block $S_{\mathrm{N}}$ nearest to $S_{max}$. $S_{\mathrm{N}}$ satisfies Equation (14), where $\mathit{x}$ is the locations of nodes.

$$\begin{array}{c}\hfill \parallel {\mathit{x}}_{\mathit{i}}-{\mathit{x}}_{\mathit{j}}\parallel =min(\parallel {\mathit{x}}_i-{\mathit{x}}_j\parallel ),s.t.v_i\in S_{max},v_j\in S_{\mathrm{N}},v_k\in S-S_{max}\end{array}$$

(14)

Step 2: The node $v_i$ in $S_{max}$ and node $v_j$ in $S_{\mathrm{N}}$ are moved to be exactly connected under the constraint of movement freedom degree. Assuming that the distance between the two adjacent nodes $v_i$ and $v_j$ to be moved is $d_s$, to form a direct communication link, the final distance $d_e$ between the two nodes satisfies condition that $d_e\le R_c$. The movement distance is the smallest when $d_e=R_c$. The location offset vector of node $v_i$ and $v_j$ after moving is shown as Equation (15).

$$\begin{array}{c}\hfill \left\{\begin{array}{c}\alpha =\parallel {\alpha }_{{\mathit{x}}_j-{\mathit{x}}_i}+{\alpha }_{{\mathit{x}}_i-{\mathit{x}}_j}\parallel ,\alpha >d_e\hfill \\ {\mathbf{\Delta }\mathit{x}}_i^{\prime }(t+\tau )=\frac{{\alpha }_{{\mathit{x}}_j-{\mathit{x}}_i}}{\alpha }(d_s-d_e)\hfill \\ {\mathbf{\Delta }\mathit{x}}_j^{\prime }(t+\tau )=\frac{{\alpha }_{{\mathbf{x}}_i-{\mathbf{x}}_j}}{\alpha }(d_s-d_e)\hfill \end{array}\right.s.t.v_i\in S_{max},v_j\in S_{\mathrm{N}}\end{array}$$

(15)

where ${\alpha }_{{\mathit{x}}_j-{\mathit{x}}_i}$ is the movement freedom degree of node $v_i$ in the direction ${\mathit{x}}_j-{\mathit{x}}_i$ and ${\alpha }_{{\mathit{x}}_i-{\mathit{x}}_j}$ is the movement of node $v_j$ in the direction ${\mathit{x}}_i-{\mathit{x}}_j$. $\alpha$ is the sum of two movement freedom degrees. ${\mathit{x}}_i$ is the location of node $v_i$ and ${\mathit{x}}_j$ is the location of node $v_j$. Substitute them into Equation (10) to get the temporary location ${\mathit{x}}_i^{\prime }(t+\tau )$ of node $v_i$ and ${\mathit{x}}_i^{\prime }(t+\tau )$ of $v_j$. If the maximum displacement under the constraint of movement freedom degree is still unable to form a direct communication link, the node and another node with limited movement freedom degree are regarded as a whole to recalculate the movement freedom degree of the node.

Step 3: Update the set $S_{max}$ for $S_{max}^{\prime }=S_{max}\cup S_{\mathrm{N}}$. Repeat the steps above to include all the nodes in the set $S_{max}$.

Figure 5 shows the 2-hop derived subgraph intention in k-hop local topology of a cut-point c. Arrows indicate the movement direction of UAV nodes based on predicted k-hop local topology and the red shadow node c is cut-point. The $S_{max}=\{4,5,6,7\}$, $S_{\mathrm{N}}=1,2,3$. The distance of moving from node 4 to node 3 is $d_1$ and the distance from node 3 to node 4 is $d_2$. Finally, the distance between node 3 and node 4 is $R_c$, which forms a direct communication link. Changes of communication links after movement are shown as red dashed lines in Figure 6. If the link between node 3 and node 4 cannot be formed under the constraint of movement freedom degree, then node 4 and node 5 are regarded as a whole to recalculate the movement freedom degree in the direction ${\mathit{x}}_3-{\mathit{x}}_4$ and move again.

3.2.2. Only One Other Cut-Point in the 1-Hop Neighbor Nodes of Cut-Point c

Step 1: The cut-point c and its neighbor cut-point $c_1$ are regarded as a whole, and the remaining nodes in the topology are divided into several blocks where the nodes are connected.

Step 2: Under the constraint of movement freedom degree, according to the method in Case 1, the nodes except node c and $c_1$ are included into a connected set through the movement of nodes, and the two cut-points c and $c_1$ are “surrounded” to change two cut-points into non-cut points finally.

Figure 6 shows the 3-hop derived subgraph intention in k-hop local topology of a cut-point c. Arrows indicate the movement direction of UAV nodes based on predicted k-hop local topology, the red shadow node c and node $c_1$ are cut-points. The nodes outside the cut-points are divided into three sets $\{4,5,6,7\}$, $\left\{3\right\}$ and $\{1,2,8\}$. Under the constraint of the movement freedom degree of nodes, nodes 3 and 4 form direct communication link by moving in opposite directions. Similarly, direct communication link is formed between nodes 7 and 8. Changes of communication links after movement are shown as red dashed lines in Figure 6. The original links remain connected and the two cut-points of c and $c_1$ are changed into non-cut points.

3.2.3. Multiple Other Cut-Point in the 1-Hop Neighbor Nodes of Cut-Point c

Step 1: According to the method in Case 1, cut-point c and its neighbor cut-points are regarded as a whole. Change all cut-points into non-cut points. If fails, execute the following steps.

Step 2: Connecting the cut-points except the cut-point c, the rules of movement are the same as those of the previous two cases, following the constraint of movement freedom degree of nodes. If the communication link between the generalized leaf node and the cut-point is broken during the movement process, the generalized leaf nodes need to be moved to maintain the connection with the cut-point.

Step 3: Treat all cut-points as a whole and repeat the first step. Eventually “surround” all cut points and change all the cut-points into non-cut points.

Figure 7 shows the 3-hop derived subgraph intention in k-hop local topology of a cut-point c and node 6 and node 7 are generalized leaf nodes. Arrows indicate the movement direction of UAV nodes based on predicted k-hop local topology and the red shadow node c, node $c_1$ and node $c_2$ are cut-points. If the first step fails, the cut-points $c_1$ and $c_2$ are moved to form a direct communication link, so that the other cut-points except cut point c are connected. However, the communication link between two generalized leaf nodes 6 and 7 and cut-point $c_1$ are disconnected. It is necessary to move node 6 and node 7 to maintain their link with the cut-point $c_1$. Then, node 5 and node 6 can be connected exactly. Nodes except all the cut-points are divided into four sets $\{4,5,6,7\}$, $\left\{3\right\}$, $\{1,2,9\}$, $\left\{8\right\}$ at this time. Under the constraint of movement freedom degree, node 3 and node 4 form direct communication link by moving in opposite directions. Similarly, direct communication link are formed between node 8 and node 9, and direct links are formed between node 7 and node 8. Changes of communication links after movement are shown as red dashed lines in Figure 7. The original links remain connected and the three cut-points c, $c_1$ and $c_2$ are changed into non-cut points.

3.3. Complexity Analysis

In k-hop topology $G_s$ of any node $v_i$, the number of nodes is $N_v$. The computation of constructing adjacency tables is $O\left(N_v^2\right)$. Assuming that the maximum connected block after removing node $v_i$ is $G_m$ and the number of nodes is $N_{mv}$. In the worst case, the cut-point detection algorithm needs to traverse the neighbors of all nodes in $G_m$ to get the DFS-tree set R. Therefore the computation of cut-point detection algorithm is shown in Equation (16).

$$C_c=O\left(N_{mv}{D}_{mean}\right)$$

(16)

where the network node density $D_{mean}$ is constant.

In the process of establishing the model, it is necessary to calculate the movement freedom degree of all nodes in the $(k-1)$-hop local topology of node $v_i$ and traverse all nodes and their neighbors. Therefore, the computation of establishing the movement freedom degree model is shown in Equation (17).

$$C_f=O\left(N_{2v}{D}_{mean}\right)$$

(17)

where $N_{2v}$ is the number of nodes in $(k-1)$-hop local topology of node $v_i$.

When dividing the network into $N_b$ blocks, it is necessary to traverse all nodes and their neighbors excepting cut-points in $G_s$. Therefore, the computation of partition is $O\left((N_v-N_c)D_{mean}\right)$, where $N_c$ is the number of cut-points in $G_s$. The computation of finding node pairs $v_i$ and $v_j$ that need moving is $O\left(N_{mi}{N}_{ni}\right)$, where $N_{mi}$ is the number of nodes in $S_{\mathrm{M}}$ and $N_{ni}$ is the number of nodes in $S_{\mathrm{N}}$ during iteration. Therefore, the computation of updating the location of nodes in $G_s$ is shown in Equation (18).

$$C_{ud}=O\left((N_v-N_c)D_{mean}\right)+O\left(\sum _{i=1}^{N_b-1}\left(N_{mi}{N}_{ni}\right)\right)$$

(18)

In Cases 1 and 2, the computation of the LFTMF algorithm is shown in Equation (19).

$$C_1=C_c+C_f+C_{ud}=O\left(D_{mean}(N_{mv}+N_{2v}+N_v-N_c)+\sum _{i=1}^{N_b-1}\left(N_{mi}{N}_{ni}\right)\right)$$

(19)

In Case 3, in the worst case, the cut-points will also be involved in the deviation and the computation is shown in Equation (20).

$$C_1=C_c+C_f+C_{ud}=O\left(D_{mean}(N_{mv}+N_{2v}+N_v)+\sum _{i=1}^{N_b-1}\left(N_{mi}{N}_{ni}\right)\right)$$

(20)

In summary, $C_1<O\left(N_v^2\right)$$\&\&$$C_2<O\left(N_v^2\right)$. Therefore, the complexity of LFTMF algorithm is within $O\left(N_v^2\right)$.

4. Simulation Result

To verify the feasibility of the LFTMF algorithm and test its performance, we conducted simulation experiments to compare the performance of LFTMF algorithm, global block movement algorithm [17] and localized movement control algorithm [18]. The test simulated the application layer to transfer data and assumed an ideal MAC layer underneath, with no communication loss and instantaneous delivery of messages.

4.1. Simulation Environment and Parameter Setting

UAV carried out reconnaissance tasks in three-dimensional obstacle-free environment. UAV nodes were randomly distributed within a certain range, and the height distribution of the UAV cluster was kept within 100 m. UAV’s speed was 30 m/s, if it did not participate in the bi-connected fault-tolerant network adjustment. The UAV that participates in the adjustment can reach the destination on time during the adjustment period. The maximum communication range of UAV was $R_c=160$ m, and the duration of each topology update period was $\tau =2$ s. FANET was isomorphic and the initial network was single-connected.

4.2. Evaluating Indicator

Five hundred randomly single-connected network topologies were selected in the experiment and the number of maximum adjustment period was five equivalent to time t to time $t+5\tau$. The success rate of the achievement of fault-tolerant network, the average distance of deviation from original track, the ratio of nodes participating in cascade movement and the average adjustment period were taken as evaluation indexes. Definitions are as follows.

The consistency of k-hop cut-points and global cut-points is defined as the ratio of the number of global cut-points to the number of k-hop cut-points.

The success rate of achieving FANET fault-tolerant network ($RAFN$) is defined as:

$$RAFN=\frac{B}{ST}$$

(21)

where $ST$ is the total number of single-connected network topologies and B is the number of bi-connected fault-tolerant network topologies in five adjustment periods.

The average distance of deviation from original location ($ADDO$) is also called average offset distance, which is the total distance that all UAV nodes deviate from their original track in the process of realizing a bi-connected fault-tolerant network in a single-connected network.

$$ADDO=\sum _{i=1}^{N_0}\parallel {\mathit{x}}_i-{\mathit{x}}_{0i}\parallel$$

(22)

where ${\mathit{x}}_i$ is the location of every node in the adjusted UAV cluster, and ${\mathit{x}}_{0i}$ is the original location of every node in the UAV cluster assuming no adjustment.

The ratio of UAV nodes participating in cascade movement ($RCM$) is defined as:

$$RCM=\frac{N_c}{N_0}$$

(23)

where $N_c$ is the number of nodes involved in cascade movement and $N_0$ is the total number of nodes in the network topology. $RCM$ reflects the degree of change in the original network topology, and has a great impact on computing and communication cost. The larger is the $RCM$, the greater are the computing cost and communication cost.

The average adjustment period $AAP$ is the number of periods required for a single-connected network to become a bi-connected fault-tolerant network. The smaller is the $AAP$, the smaller is the communication cost.

4.3. Discussion of Simulation Results

4.3.1. Experiment 1: Consistency of k-Hop Cut-Points and Global Cut-Points

The value of k was $\{1,2,3,4\}$ and the number of nodes $N_0=50$. Simulated experiment of cut-points detection was carried in 500 random three-dimensional single-connected networks.

Figure 8 shows the relationship between the consistency of k-hop cut-points and global cut-points and network node density when k takes different values. With the increase of network node density, the consistency between k-hop cut-points and global cut-points increased. If the node degree were certain, the greater was the value of k, the greater was the consistency. The larger was the value of k, the higher was the communication cost. However, too small a value of k led to too many k-hop cut-points, which means non-global cut-points being recognized as global cut-points, resulting in unnecessary movement cost. Therefore, the value of k was 3 in subsequent experiments. It is worth noting that the global cut-points must be k-hop cut-points, so eliminating all k-hop cut-points means eliminating all global cut-points.

4.3.2. Experiment 2: With a Certain Number of UAV Nodes, Analyses of the Relationships among the Performances of LFTMF Algorithm, Global Block Movement Algorithm, Localized Movement Control Algorithm and the Network Node Density by Simulation

First, $k=3$ and the number of UAV nodes $N_0=50$ were set. Based on 500 random three-dimensional single-connected networks, the relationship between the performance of different algorithms and the network node density was tested, as shown in Figure 9.

A parse networks means $D_{mean}=4,5$. In Figure 9a, it can be seen that, when the network was sparse, the success rate of the achievement of bi-connected fault-tolerant network was more than 90%, while the success rate of the localized movement control algorithm was only 35–45%. When $D_{mean}>6$, the success rate of the localized movement control algorithm increased with the increase of $D_{mean}$, and finally reached more than 90%. in Figure 9b, it can be seen that, in sparse networks, the adjustment period of LFTMF algorithm was much shorter than that of localized movement control algorithm. With the increase of $D_{mean}$, the value of $AAP$ was close to 1, but the value of $AAP$ of LFTMF algorithm was always smaller than that of localized movement control algorithm.

The reasons for the above results are as follows. In sparse networks, there are many consecutive cut-points without the constraint of movement freedom degree in the localized movement control algorithm. The movement of some nodes leads to the disconnection of the original communication link and the generation of new cut-points. In LFTMF algorithm, the movement freedom degree of the third-hop node of cut-point is 0, and it does not participate in movement, forming a “barrier” to ensure the connectivity with the external topology. With the constraint of node freedom, no new cut-points will be generated. When the network node density is large, the number of cut-points is small, and both algorithms have higher success rate and smaller adjustment period.

In Figure 9c,d, it can be seen that the ratio of UAV nodes participating in cascade movement and average offset distance of the global block movement algorithm were larger than those of the two distributed algorithms. This is because the nodes move in blocks in block movement algorithm, resulting in more UAV nodes participating in the movement and a larger offset distance. Compared with LFTMF algorithm, localized movement control algorithm has a larger ratio of nodes participating in cascade movement and movement cost because it may lead to the generation of new cut-points, and the adjustment period is longer.

In summary, the performance of all the algorithms improved with the increase of network node density when the number of UAV nodes was certain. Compared with localized movement control algorithm, LFTMF algorithm has obvious advantages in sparse network.

4.3.3. Experiment 3: With a Certain Network Node Density, Analyses of the Relationships among the Performances of LFTMF Algorithm, Global Block Movement Algorithm, Localized Movement Control Algorithm and the Number of UAV Nodes by Simulation

First, $k=3$ and the network node density $D_{mean}=6$ were set. Based on 500 random three-dimensional single-connected networks, the relationship between the performance of different algorithms and the number of UAV nodes was tested, as shown in Figure 10.

It can be seen in Figure 10a,b that, with the increase of the number of nodes, the success rate of LFTMF algorithm remained above 95%, and the adjustment period was about 1.5, independent of the number of nodes. The success rate of the localized movement control algorithm decreased continuously, and finally stabilized at about 65%. The adjustment period increased continuously, and finally stabilized at about 3.5. The reasons is that, when the network scale increases, the 3-hop local topology cannot represent the global topology. Localized movement control algorithm will cause the disconnection between the local topology and the rest of the nodes in the global topology, resulting in new cut-points. When the number of nodes reached more than 80, the influence tended to be stable. In the LFTMF algorithm, the third-hop nodes of 3-hop local topology do not participate in the migration, and the movement freedom degree can effectively maintain the connectivity of the original link.

In Figure 10c,d, it can be seen that the performance of the local algorithm was better than that of the global block movement algorithm when the network scale was large, because the block movement algorithm participated in the movement as a block. The ratio of UAV nodes participating in cascade movement of the three algorithms decreased with the increase of network scale, and the average offset distance increased with the increase of network scale. The reason is that most of the nodes will participate in the movement when the network scale is small. Only the nodes around the cut-points participate in the movement when the network scale is large and at this point. The ratio of nodes participating in cascade movement is small, but the number of nodes involved in the movement increases leading to the increase of offset distance. Compared with localized movement control algorithm, the LFTMF algorithm had smaller ratio of participating in cascade movement and average offset distance.

In summary, when the network node density was certain, with the increase of network scale, the success rate of LFTMF algorithm in realizing bi-connected fault-tolerant network was always above 95%, and the overall performance was better than global block movement algorithm and localized movement control algorithm.

5. Conclusions

In this paper, we propose a localized fault-tolerant algorithm based on node movement freedom degree (LFTMF). The algorithm solves the problem that the single-connected FANET network is easily segmented due to the dynamic characteristics of the UAVs. In three-dimensional FANET, we establish the movement freedom degree model, and propose three movement strategies according to the distribution of cut-points in the k-hop local topology of cut-points. The performance of LFTMF algorithm in three-dimensional FANET network was studied by numerical simulation. The simulation results show that, compared with localized movement control algorithm and global block movement algorithm, the proposed algorithm improves the success rate of the achievement of bi-connected fault-tolerant network under the constraint of movement freedom degree, and has smaller adjustment period, offset distance and the ratio of nodes of participating in cascade movement, maintaining the connectivity of the original link at the same time. The performance advantage of this algorithm is particularly prominent when the network is sparse or the network scale is large. This topology control algorithm has potential application prospects in network fault-tolerant control.