A Novel Dynamic Transmission Power of Cluster Heads Based Clustering Scheme

Abstract

Clustering methods are promising tools for ensuring the network scalability and maintainability of large-scale flying ad hoc networks (FANETs). However, due to the high mobility and limited energy resources of unmanned aerial vehicles (UAVs), it is difficult to maintain the network reliability and extend the network life of FANETs. In this paper, a new K-means algorithm is developed, and a dynamic transmission power of the cluster heads based clustering (DTPCH-C) scheme is proposed. The goal of this scheme is presented for FANETs to improve the reliability and lifetime of FANETs. Firstly, the optimal number of clusters is calculated and the initial UAV clusters are set up by a K-means algorithm. Then, using a weighted clustering algorithm, the adaptive node degree, the node energy and the distance from the cluster head are weighted and summed for the cluster head election. In the process of inter-cluster communication, the cluster head adjusts its transmit power in real-time through meshing and mobile prediction, thus saving the energy consumption and improving the network lifetime. The proposed DTPCH-C simultaneously optimizes the cluster number, the cluster head energy consumption, the selected cluster head, and the cluster maintenance process. The simulation results show that compared with traditional clustering methods, the proposed DTPCH-C has obvious advantages in terms of the network reliability, network life, and energy consumption.

1. Introduction

With the booming development of the unmanned aerial vehicles (UAV), UAVs have been widely used in agriculture, inspection, security, rescue, and other fields [1]. Currently, using a single UAV for executing tasks is a typical practice [2]. However, when the task area is large, the UAV requires several round-trips or multiple transitions to fully cover the entire task area, which is time-consuming and inefficient. In some places, the terrain factors also limit the communication between the UAV and the ground control station. Since the UAV cannot reach the target area, the task may not be completed.

Recently, the flying ad hoc network (FANET) has attracted great attention, because it has significant advantages compared to the single UAV technique in the face of the above difficulties. The FANET is a dynamic ad hoc network system with an arbitrary, temporary, and autonomous network topology [3]. As a network node of FANET, each UAV is equipped with FANET communication modules (including routing and message forwarding functions), and can form any network topology through wireless connections [4]. As a result, in this network, the UAV can be used as a task node or a relay node. When being regarded as the task node, the UAV executes the task when under the control of the ground control station or other UAVs. If being used as the relay node [5], the UAV participates in routing maintenance and packet forwarding according to the routing policy and routing table of the network. Multiple UAVs work together to sense the task environments, through the FANET technique, which shares the information between multiple UAVs. The UAVs can also complete the task of the large scale region monitoring when line-of-sight communications are blocked [6], further reducing the dependence of the UAV swarm system on individuals. Because the individual UAV leaves or joins the system, the whole swarm system still has certain integrity and can continue to perform tasks.

For FANETs, the increasing demand of routing in the field of communication is the most important subject currently. It is a challenge for a routing protocol to calculate the best optimal path in any network. Because of the dynamic spatial and temporal mobility of FANET nodes, the performance and efficiency of the routing protocol become very critical. One study [7] presents a novel routing protocol for FANET using modified AntHocNet. The protocol has better dependability than most current legacy best path selection techniques.

Additionally, to exploit the advantages of UAV swarm systems, the number of nodes, the distribution range, and the network scale of FANET need to be enlarged. The use of an algorithm [8] is an effective method to improve the performance of FANET. This clustering algorithm can manage network energy consumption effectively and prolong the whole network life. By applying the cluster algorithm, the whole UAV network is divided into several smaller clusters. A cluster consists of a cluster head (CH) and several cluster members (CMs). The CH needs to be selected reasonably, as it is used to manage and maintain the cluster to which it belongs [9]. Compared with the planar structure, the clustered network structure can reduce the influence of local topological changes on the whole network [10]. In the process of route calculation and generation, only partial nodes are required to participate in the clustering algorithm, effectively reducing the cost of routing and control. In addition, the cluster network structure can improve the network scalability.

Since the CH is important for a cluster, it is necessary to design a reasonable cluster head selection strategy, to guarantee the stability of the clustering structure. Moreover, because the CH needs to receive, process and send a lot of information, the energy consumption of the CH is very heavy, which is fatal to the lifetime of the whole FANET. Therefore, reducing the energy consumption of the CH should be considered. However, most existing clustering algorithms such as [7,9] do not simultaneously optimize the cluster number, the CH selection, the communication resource allocation, and the cluster structure stability. Some algorithms such as [8] even randomly assign the CHs and the cluster number, degrading the stability of the whole network. Therefore, it is necessary to design a scheme to overcome the shortcomings of the above algorithms and improve the overrall performance of FANETs.

To address the related issues, this paper proposes a dynamic transmission power of the cluster heads based clustering (DTPCH-C) scheme, developed using the new K-means algorithm. Different from the traditional K-means algorithm, the clustering process is optimized in the new K-means algorithm. The number of clusters and the selection of CHs are optimized. Firstly, in the clustering process, to reduce the clustering overhead, the primary number of clusters needs to be optimally determined for the initial clustering center selection. Subsequently, according to the CH election strategy, the UAV node with the highest fitness value is selected as the CH in a cluster, while the remainders are CMs, which can improve the reliability of FANETs. We also design a moving prediction model-based dynamic transmission strategy to allocate the power of the CH. By predicting the distance between cluster heads and CMs, the transmission power of the CHs is adjusted, so as to reduce the energy consumption of CHs and enhance the life of the cluster network.

The key contributions of this paper are summarized as follows:

• A novel clustering scheme with dynamic transmission power of CHs is presented for FANETs to improve reliability and lifetime of FANETs. The proposed DTPCH-C scheme is realized by initialing the cluster, reducing the energy consumption of the CHs, selecting CHs and maintaining clusters.
• The variable transmission power mechanism of the CH is proposed. Using grid mode-based transmission power adjustment and movement prediction, the CH can flexibly adjust its transmitting power according to its distance to different CMs, which saves energy and improves the lifetime of FANETs.
• Meanwhile, we propose a weighted summation-based CH selection algorithm, where the adaptive node degree, the remaining energy ratio and the distance between nodes are all involved in the selection criteria. The UAV node with the maximum weight is selected as the CH. As a result, the probability of the most appropriate node becoming a CH is improved so that the packet delivery ratio (PDR) grows. Therefore, the reliability of the network is enhanced.
• According to the simulation results, the proposed DTPCH-C scheme has more advantages than the existing clustering methods in terms of reliability, lifetime and energy consumption.

The rest of this paper is organized as follows: Section 2 describes the background about FANETs and related works. The system model is introduced in Section 3. In Section 4, the proposed DTPCH-C scheme is presented in detail. In Section 5, we compare the performance of the DTPCH-C algorithm with the other two algorithms and draw the conclusion that the performances of the DTPCH-C is better than the others. In Section 6, we summarize of the whole paper.

2. Background and Related Works

The lowest identification (LID) clustering algorithm was put forward by Gerla et al. [11]. This algorithm is based on the least node ID cluster head election. The node is assigned a random ID and selects the neighbor nodes. The smallest ID node is the cluster head. The cluster structure maintenance method is based on the ID value. The LID algorithm has low computational complexity, but easily leads to an unbalanced load and has fixed cluster head selection. To improve the rationality of cluster head selection and enhance the adaptability of the scene, Wang et al. proposed a weighted clustering algorithm (WCA) [12], which comprehensively considers the node degree, distance, and mobility. In the WCA, malicious nodes can be selected as CHs in the process of clustering, which in turn accompanies some security issues. For this reason, some researchers also propose improved or variant WCAs.

According to the energy characteristics of the nodes, a series of clustering algorithms based on the number of nodes are presented. For example, the low-power adaptive clustering algorithm (Leach) selects CHs through random probability and changes CHs at certain intervals to balance the load in terms of the network energy and extend the network life. The disadvantage of Leach is that only the remaining energy of the node is considered, and the performance of this method is poor in the actual application process. Moreover, since CHs are assumed to be able to communicate with the base station, the method is not suitable for large-scale networks.

Some researchers are inspired by biological behaviors and apply these for the clustering the FANETs. In [13], an ant colony optimization (ACO) clustering scheme is proposed for optimal clustering and data transmission in the FANETs. CHs are vertices in the search space, and each round provides the set of CHs from specific environments. The algorithm uses two objective functions to evaluate the fitness value of each cycle, namely, the Euclidean distance and the delta difference. In [14], the grey wolf optimization (GWO) algorithm is proposed for an energy-efficient routing protocol. This algorithm has the advantage of high robustness and accuracy, and its convergence rate is faster than similar algorithms. However, the disadvantage of this algorithm is that the convergence rate is too slow in the late stage, and it is easy to fall into the local optimal solution.

In FANETs, maintaining network connectivity is an important consideration when designing UAV clustering algorithms. Lu et al. [15] designed a connectivity degree-based high connectivity clustering (HCC) algorithm to implement UAV clustering. In the HCC algorithm, the node with the largest number of neighbors is first selected as the CH, and then a limited number of clusters is generated. Due to the movement of the UAV (i.e., the node), the number of neighbor nodes of each node may change, which means that the cluster head needs to be re-selected accordingly. Due to the frequent selection of cluster heads and multiple reconnections of nodes, the HCC algorithm has poor adaptability and reduced throughput for dynamic UAV nodes.

Many researchers also combine some mature clustering algorithms with the characteristics of FANETs to design different UAV clustering algorithms [16]. The study [17] proposes a K-means-based (KMB) UAV clustering algorithm for the cluster head selection, and added a mobile agent to collect and fuse the data in the cluster. This algorithm overcomes the shortcomings of traditional K-means algorithm, and has the advantages, such as avoiding local optima, high precision solution and simple operations. The authors of [18] studied an evenly split ring-based UAV clustering (SRC) algorithm by applying fuzzy logic. In this algorithm, the energy of the node, the node degree, node-to-node distance, the ring width, and the staring energy parameters are utilized as the input of fuzzy rules. Then, the optimal number of clusters can be obtained. The study [19] proposes an energy-efficient swarm-intelligence-based clustering (SIC) algorithm, in which the particle fitness function is exploited for intercluster distance, intracluster distance, residual energy, and geographic location. For energy-efficient clustering, cluster heads are selected based on improved particle optimization. In [20], the authors propose a dynamic scale UAV weighted clustering algorithm (DSWCA). By determining the optimal, maximum and minimum values of the cluster scale and make the cluster scale dynamic, the algorithm can achieve superior performance in network load balance.

Table 1. DTPCH-C performance positioning with other clustering schemes in FANETs.

Methods	Clustering Overhead	Location Awareness	Reliability	Energy Efficiency	PDR	Communication Safety
WCA [12]	High	🗸	×	🗸	×	×
ACO [13]	Moderate	×	🗸	🗸	🗸	×
GWO [14]	High	×	×	🗸	🗸	×
HCC [15]	Low	🗸	🗸	×	×	🗸
KMB [17]	High	×	🗸	🗸	×	×
SRC [18]	Low	🗸	🗸	×	×	🗸
SIC [19]	High	🗸	×	🗸	🗸	×
DSWCA [20]	Low	×	🗸	🗸	🗸	×
DTPCH-C	Low	🗸	🗸	🗸	🗸	×

summarizes the performance positioning of the discussed clustering schemes in FANETs. Compared with other algorithms, the proposed DTPCH-C scheme comprehensively considers the reliability, energy efficiency, and PDR in the FANET.

3. Preliminaries

In this section, we will introduce the system model, the structure of the HELLO message and the optimization goal.

3.1. System Model

The system model is shown in Figure 1, where all UAVs are managed in the cloud. The cloud formulates clusters and maintains the backbone routing table for communicating with the CHs. The cloud broadcasts central control commands to all UAVs through the CHs.

In this system, all the UAVs are equipped with location-aware components and wireless communication interfaces so that they can obtain the velocity, direction and location information about themselves and also have the capability of routing. Through the cloud, the FANET will be clustered. Each cluster is composed of a CH and CMs. After clustering, CHs in each cluster divides the grid within their own communication range. According to the exchange of the HELLO message, the CH can obtain the position and speed of CMs. According to the communication grid position of CMs, the CH adjusts its signal transmission power, to save the energy and prolong the system lifetime. At the same time, the CH also predicts the movement of CMs, judges the position of CMs in the future, and adjusts the signal transmission power in time. Finally, the cloud will periodically repartition clusters and elect CHs by the weighted summation-based cluster head selection algorithm because of the real-time changing topology, which ensures normal communication in the network and avoids the influence of the excessive energy consumption of a node on the network lifetime.

3.2. HELLO Message

UAVs obtain information of surrounding nodes for clustering through HELLO message exchange. The structure of HELLO message is shown in Figure 2. The HELLO message contains the following contents:

• ID: the identification of the UAV node.
• Cluster ID: the identification of the cluster.
• Role: the value can be 0 or 1, where 0 represents CH and 1 represents CM.
• Weight: the weight of a CH candidate in the CH selection phase.
• Speed: the speed of the UAV node.
• Direction: the flying direction angle of the UAV node.
• Position: the position of the UAV node.

3.3. Optimization Goal

3.3.1. The reliability of the FANET

We can measure the reliability of the network by packet delivery ratio (PDR). The PDR is defined by

$$PDR=\frac{P_R}{P_S},$$

(1)

where $P_R$ represents the number of data packets successfully received by the destination nodes, and $P_S$ represents the total number of data packets generated by the source nodes. The destination node are the CHs, and the CHs will upload data to the cloud.

The higher the PDR, the better the communication quality. In this paper, the optimized cluster head election strategy and the cluster maintenance process increase the PDR. Using the cluster head election strategy, the stable CHs will be selected to forward packets so that the success rate of information transmission will be improved. Moreover, the effective cluster maintenance reduces the probability of link disconnection, which improves the connectivity of UAVs and the transmission success ratio.

3.3.2. The Lifetime of the FANET

When the remaining energy of a node is less than 20% of the initial value of the node, it is regarded as a dead node and removed from the FANET [21]. If the number of dead nodes is too large, the performance of the FANET will be greatly reduced. So when the number of dead nodes reaches half, the network will be considered invalid. The lifetime of the FANET can thus be expressed as

$$T=t_e-t_s,$$

(2)

where $t_s$ is the time when the FANET starts working, and $t_e$ represents the time when the FANET becomes invalid.

Compared with CMs, CHs undertake more tasks and consume more energy. Therefore, if the energy consumption of CH can be reduced, the lifetime of the FANET will be greatly improved. Relying on the scheme with dynamic transmission power of CHs, the CH can flexibly adjust its transmitting power according to the distance to different CMs, avoiding redundant energy consumption and saving resources. As a result, the rate of node death is slowed down and the lifetime of the FANET is increased.

4. Proposed Approach

In this section, we will introduce the DTPCH-C algorithm in detail considering four aspects: (1) Section 4.1 introduces the method used to calculate the optimal cluster head number; (2) in Section 4.2, the cluster head election strategy is proposed; (3) in Section 4.3, Section 4.4, Section 4.5 and Section 4.6, the principle of the scheme with the dynamic transmission power of CHs is introduced in detail; and (4) Section 4.7 describes the cluster maintenance process.

4.1. Calculation of Optimal Cluster Head Number

In the traditional K-means algorithm, the primary number of clusters is set randomly in the clustering process. If the number of clusters is not set properly, the performance of FANETs deteriorates. When the number of clusters is small, the energy consumption for communication will increase, but if the number of clusters is large, the advantages brought by UAV clustering will be weakened. In the clustering process, to reduce the clustering overhead and utilize the bandwidth efficiently, the primary number of clusters needs to be optimally determined for the initial clustering center selection. According to [22], the throughput of a single node in the FANET can be expressed as

$$T=\Theta \left(\frac{B}{\sqrt{N}}\right),$$

(3)

where N is the number of network nodes, B is the communication bandwidth, and $\Theta \left(·\right)$ is the asymptotically tight bound. After clustering, we can obtain the throughput of each CM, as given by

$$T{}_{\mathrm{CM}}=\Theta \left(B_1/\sqrt{\frac{N}{k}}\right),$$

(4)

where $B_1$ is the bandwidth within the cluster and k is the number of clusters. In addition, the throughput of each CH is

$$T{}_{\mathrm{CH}}=\Theta \left(\frac{B_2}{\sqrt{k}}\right),$$

(5)

where $B_2$ is the bandwidth between clusters. It assumes that the network traffic is uniformly distributed. Because of the throughput balance between the inter-cluster and the intra-cluster communications the proportion of $T{}_{\mathrm{CM}}$ used for traffic in/out to other clusters is $\frac{k-1}{k}$, and the portion should be smaller or equal to $T{}_{\mathrm{CH}}$ [23], i.e.,

$$\frac{k-1}{k}T{}_{\mathrm{CM}}\le T{}_{\mathrm{CH}}.$$

(6)

When $\frac{k-1}{k}T{}_{\mathrm{CM}}$ reaches the maximum throughput, namely, when inequality (6) holds, the primary number of clusters n is obtained as

$$n=\frac{B_2}{B_1}\sqrt{N}+1.$$

(7)

If N is large enough, the optimal number of clusters n is approximated to

$$n=\frac{B_2}{B_1}\sqrt{N}.$$

(8)

Based on the optimal number n, K-means clustering algorithm can be used to divide N UAVs into clusters. The pseudocode of the K-means clustering algorithm is listed in Algorithm 1.

Algorithm 1 K-means Clustering Algorithm

Input:  The optimal number of clusters n, The UAV nodes are modeled as a point set S = {$s_1$, $s_2$, ..., $s_n$} Output:  /*Initialization*/   randomly select n initial clustering centers uniformly from S 1: Repeat 2: calculate the distance from each node to each cluster center, and the node is assigned to the nearest cluster 3: after all nodes are allocated, the centroids of n clusters are recalculated 4: until centroids remain unchanged 5: return clusters set $CL$ = {$C{L}_1$, $C{L}_2$, …, $C{L}_n$}

4.2. Cluster Head Election Strategy

In the traditional K-means clustering algorithm, the election of CHs is inappropriate. To improve the performance and lifetime of FANETs, it is important to select the appropriate cluster head of each cluster. In a cluster, an appropriate cluster head should meet the following criteria: (1) in order to improve the success rate of information exchange between cluster head and cluster members and the utilization of network bandwidth resources, we should choose the node with high adaptive node degree; (2) in order to improve the lifetime of FANETs and avoid data transmission failure due to cluster head death, we should choose the node that has more energy left; (3) to ensure that the topology of the network does not change too much after each round of cluster maintenance, the distance between the node i and its cluster head should not be far.

To elect the CH satisfying the above conditions, in this subsection, we will focus on the optimization of the CH election, where the adaptive node degree, node remaining energy, and the Euclidean distance between nodes are jointly considered.

4.2.1. Adaptive Node Degree

In order to improve the utilization of network bandwidth resources, the number of neighbor nodes around the CH is controlled. The adaptive node degree [12] is used in this paper to avoid network congestion. The degree is positively correlated to the probability of a node being selected as the CH. In the network, each node obtains the node degree of itself by exchanging HELLO messages. The node degree of node i is defined as

$$d_i=\sum _{j=0}^N{d}_j^i,$$

(9)

$$d_j^i=\left\{\begin{array}{c}\hfill 0d_{ij}\ge r\\ \hfill 10<d_{ij}<r,\end{array}\right.$$

(10)

where $d_{ij}$ is the distance between the node i and the node j, and r is the node communication radius. The adaptive node degree difference is defined as

$${\epsilon }_i=|d_i-\frac{N}{n}|,$$

(11)

where n is the optimal number of clusters determined by (8). After normalization, the adaptive node degree of node i is

$$D_i=e^{-{\epsilon }_i}.$$

(12)

4.2.2. Node Remaining Energy

The remaining energy of the UAV node is also an important election criterion. If a UAV node has low energy, it is less likely to become the cluster head. This is because the remaining energy of this node may not be enough to maintain its continuous work, thereby affecting the communication of the whole network. The residual energy ratio $E_i$ of node i can be expressed as

$$E_i=\frac{E_0-E{}_{\mathrm{T}}}{E_0},$$

(13)

where $E_0$ is the total energy of node i. $E{}_{\mathrm{T}}$ is the total energy consumption of node i, which is written as

$$E{}_{\mathrm{T}}=E{}_{\mathrm{TX}}+E{}_{\mathrm{RX}}+E_{{\mathrm{F}}^{\prime }}$$

(14)

where $E_{{}_{\mathrm{TX}}}$ is the energy consumed by sending message of node i. $E_{{}_{\mathrm{RX}}}$ is the energy consumed by receiving message of node i. $E_{{}_{\mathrm{F}}}$ is the flying consumption of node i, which is calculated as

$$E_{{}_{\mathrm{F}}=}{\int }_0^{t_{{}_{\mathrm{F}}}}{P}_{{}_{\mathrm{F}}}dt,$$

(15)

where

$$P_{{}_{\mathrm{F}}=}\sqrt{\frac{\left(m{}_{\mathrm{UAV}}g\right){}^3}{2\pi n_w{r}_w{\rho }_{air}}},$$

(16)

$t_{{}_{\mathrm{F}}}$ is the flying time of UAV. $m{}_{\mathrm{UAV}}$ is the mass of UAV, ${\rho }_{air}$ and g are the air density and earth gravity, respectively. $n_w$ is the number of wings. $r_w$ is the radius of wings.

4.2.3. Euclidean Distance from the Node to the Cluster Head

The Euclidean distance between the node i and its cluster head is considered. Shortening the distance can increase the probability that the node i becomes the next cluster head, which is conducive to maintaining the reliability of the entire network structure. We use the symbol $l_i$ to represent the distance index of this node. $l_i$ can be expressed as

$$l_i=\sqrt{{\left(x_i-x_H\right)}^2+{\left(y_i-y_H\right)}^2+{\left(z_i-z_H\right)}^2}$$

(17)

where $x_i$ and $y_i$ are the horizontal and vertical coordinates of the node i; and $x_H$ and $y_H$ are the horizontal and vertical coordinates of the cluster head. The distance is normalized by

$$L_i=log\left(\frac{l_i}{r}+1\right)$$

(18)

4.2.4. Weighted Metric Criterion

Based the above $D_i$, $E_i$ and $L_i$, the updated criteria of cluster head measurement weight is expressed as

$$R=a_1{D}_i+a_2{E}_i+a_3{\frac{1}{L}}_i,$$

(19)

where $a_1$, $a_2$, $a_3$ are the weights of the three factors, and $a_1+a_2+a_3=1$. Moreover, these weights are defined on the interval [0, 1]. The specific proportion coefficient’s value can be assigned according to task requirements. Through this criterion, the randomness of cluster head election and the defect of falling into local optimal solution can be avoided effectively.

Based on the definition of the three factors, the cluster head selection is proposed, of which the pseudocode is listed in Algorithm 2.

Algorithm 2 Cluster Head Selection Algorithm.

Input:  The optimal number of clusters n, clusters set $CL$ = {$C{L}_1$, $C{L}_2$, …, $C{L}_n$} Output:  Every node gets information about its adaptive node degree and distance by   HELLO message sent by the neighbor nodes 1: Every node i calculates the weight $R_i$ by the Equation (19) 2: The node with the largest value of R in each cluster is set as the cluster head and broadcasts its message within the cluster 3: return$C{H}_1$, $C{H}_2$, …, $C{H}_n$

4.3. Analysis of Cluster Head Transmission Power

The motion states of UAVs include the position, speed, direction, and so on. To adapt the clustering algorithm to the highly dynamic characteristics of nodes, the motion characteristics of UAVs was analyzed. Assume that UAVs can obtain high-precision positioning information in real time through the Global Positioning System(GPS). In the system, each UAV can obtain the specific location information according to its positioning equipment, and transmit the location information through the HELLO message broadcast by the system. The node within the receiving range receives the information to obtain the geographical location information of the neighboring node, so that the neighbor list can be maintained. After the UAVs are clustered, the cluster head can find the distance between the cluster members and itself according to its neighbor list.

According to the distance between the cluster members, the cluster head can adjust the transmitting power by reducing the transmitting power when transmitting information to the node within a short distance and increasing the transmitting power when sending data packets to the node within the maximum communication range. The ideal communication loss (free space) [24] between UAVs can be expressed as

$$P{}_{\mathrm{LOS}}\left(\mathrm{dBm}\right)=32.5+20lg\left(d\right)+20lg\left(f\right),$$

(20)

where d is the propagation distance and f is the working frequency. In practical applications, because wireless communication is affected by various external factors, such as atmosphere, barriers, multipath, etc., the $P_{\mathrm{LOS}}$ is high. By plugging the reference value into (20), the total transmission loss can be calculated [25].

The transmitting power of the cluster head should not be less than the sum of the wireless transmission loss and the reception sensitivity of the UAV. Considering that the working frequency and reception sensitivity of UAVs are constant, the relationship between the transmitting power and propagation distance can be obtained, as given by

$$P{}_{\mathrm{LOS}}\left(\mathrm{dBm}\right)=32.5+20lg\left(d\right)+20lg\left(f\right)+P_{rs}+P{}_{{\mathrm{LOS}}^{\prime }},$$

(21)

where $P_{\mathrm{rs}}$ is the transmitting loss caused by the reception sensitivity, and $P{}_{{\mathrm{LOS}}^{\prime }}$ is the transmitting loss due to the multipath fading, atmospheric loss, and so on.

4.4. Grid Mode for Cluster Head Transmission Power Adjustment

Since the UAV moves at a high speed, if the transmission power of the cluster head is changed due to the distance between the UAVs, the cluster head needs to calculate the required transmission power all the time, wasting resources. We designed a grid mode-based transmission power adjustment method, as shown in Figure 3. The transmission power of cluster heads was set discretely, and each grid has different colors corresponding to the different sizes of transmission power. The advantages of this design are: (1) avoiding the frequent change in transmitting power and thus reducing the energy consumption caused by its internal calculation; and (2) predicting the moving trajectory, so that the cluster head can analyze the trend of cluster members and accurately adjust its transmitting power.

4.5. Prediction of Cluster Member Movement

4.5.1. Problem Description

Because UAVs are not always relatively static, cluster heads need to adjust their transmitting power in real-time according to the distance between the UAVs and cluster members. This can avoid resource waste caused by excessive transmitting power or the failure of cluster members to receive information due to the CH’s insufficient transmitting power, as shown in Figure 4. A movement prediction mechanism is set up in this paper, which is used to predict the grid position of its members in the next transmission cycle and adjust the transmission power in time.

4.5.2. Mobility Model

In the FANET, the node movement is regular and cannot be described by a completely random entity movement model. The group mobility is also taken into account. We applied the Gauss-Markov model [26] to represent the movement trajectory of nodes, which overcomes the defect of the sudden stop and turn. So this model is more consistent with reality.

For the convenience of analysis, this paper assumes that the UAV node can obtain its position and speed information through GPS. Since we set the UAVs to fly at the same altitude, so we only concentrate on the x and y axes of the coordinate system. Moreover, the CH is regarded as static, and the coordinate system is set with it as the center to analyze the node movement.

Theory: When calculating the new speed and direction, each node has an initial speed and direction, and an average speed and direction. In each time step, we calculated the new speed and direction at the next moment, and repeated the operation.

Define: Q is a square with sides of length S, which represents the moving region of the node, where S is no more than the communication diameter of the node. It was assumed that all UAVs have a velocity with the same direction and magnitude at the beginning of the experiment. We removed this velocity and just considered the relative motion of each UAV so that the movement of UAVs was easier to analyze. At the beginning, n nodes are evenly distributed in the set area. Additionally, at the same time, UAVs will start to move according to the Gauss-Markov model, while being restricted in the area Q based on the actual situation. Since the UAV is regarded as a point and the scale of FANET is not particularly large, the case of collision between the UAVs is not considered. U = ($u_1$,$u_2$…$u_n$), represents the collection of nodes, $u_i$ is the i-th node, $\forall u_i\in$U; $\left(x_i,y_i\right)\in Q$ represents the position of the i-th node; $v_i$ represents the speed of the i-th node; and ${\theta }_i$ represents the angle between velocity reversal and the X-axis. The time interval of HELLO message exchange is discretized, i.e., $\Delta T=t_n-t_{n-1}=k\Delta t$, where $\Delta t$ is time step, k is the number of time segments. At time $t_n$ the CH obtains the CM${}_i$′s velocity $v_i\left(t_n\right)$, direction angle ${\theta }_i\left(t_n\right)$ and the position $\left(x_i\left(t_n\right),y_i\left(t_n\right)\right)$ from HELLO message exchange. Hence, the CM${}_i$′s velocity and direction angle at time $(t_n+m\Delta t)$ can be calculated as

$$\left\{\begin{array}{c}\hfill v_i(t_n+m\Delta t)=\alpha v_i(t_n+(m-1)\Delta t)+(1-\alpha )\overline{v}+\sqrt{1-{\alpha }^2}{v}_i(t_n+(m-1)\Delta t)\\ \hfill {\theta }_i(t_n+m\Delta t)=\alpha {\theta }_i(t_n+(m-1)\Delta t)+(1-\alpha )\overline{\theta }+\sqrt{1-{\alpha }^2}{\theta }_i(t_n+(m-1)\Delta t),\end{array}\right.$$

(22)

where $\alpha$ is the relevant memory parameter, denoting the correlation between the current time slot and the previous time slot in speed and direction, and $0\le \alpha \le 1$. The strength of the correlation can be changed by adjusting the value of $\alpha$; $1\le m\le k$, m represents the m-th time slot; and $\overline{v}$ and $\overline{\theta }$ represent the average velocity and the average directional angle over the period. Therefore, according to (22), we can predict the velocity and direction angle of the node at any time in the periodic interval, and the position of CM${}_i$ at $(t_n+m\Delta t)$ can be obtained by:

$$\left\{\begin{array}{c}\hfill x_i(t_n+m\Delta t)=x_i\left(t_n\right)+\sum _{l=1}^m{v}_i(t_n+l\Delta t)\Delta tcos{\theta }_i(t_n+l\Delta t)\\ \hfill y_i(t_n+m\Delta t)=y_i\left(t_n\right)+\sum _{l=1}^m{v}_i(t_n+l\Delta t)\Delta tsin{\theta }_i(t_n+l\Delta t).\end{array}\right.$$

(23)

4.6. Link Expiration Time

Using the movement prediction model, the CH can successfully predict the location of cluster members at the next instance. To adjust the transmitting power quickly and conveniently, the CH calculates the link connection time when the transmitting power needs to be changed by calculating the link connection time. This can avoid the resource waste caused by the frequent calculation of the CH.

Figure 5 shows the movement trajectory of the CM${}_i$ during a HELLO message switching period. At time $t_n$, the CM${}_i$ is in the light blue grid; after l time slots, the CM${}_i$ moves to the dark blue grid. Then, the CM${}_i$ moves to the light blue grid again until the next HELLO message exchange starts, i.e., the $t_{n+1}$ moment. As shown in

Table 3. Table of variation of cluster head transmitting power.

Time	${\mathit{t}}_{\mathit{n}}$ to ${\mathit{t}}_{\mathit{n}}+\mathit{l}\mathbf{\Delta }\mathit{t}$	${\mathit{t}}_{\mathit{n}}+\mathit{l}\mathbf{\Delta }\mathit{t}$ to ${\mathit{t}}_{\mathit{n}}+\mathit{p}\mathbf{\Delta }\mathit{t}$	${\mathit{t}}_{\mathit{n}}+\mathit{p}\mathbf{\Delta }\mathit{t}$ to ${\mathit{t}}_{\mathit{n}+1}$
Grid	Light blue	Dark blue	Light blue
P/mW	$P_3$	$P_2$	$P_3$

, the cluster head can predict the grid position of CM${}_i$ at any time within the HELLO message exchange cycle according to the prediction model, so as to adjust its own transmitting power in time.

The pseudocode of dynamic transmission power of cluster heads algorithm is listed in Algorithm 3.

Algorithm 3 Dynamic Transmission Power of Cluster Heads Algorithm

Input:  Sender node: CH${}_i$, receiver node: CM${}_j$, data message Output:    1: CH${}_i$ gets the velocity, direction angle and the position information of CM${}_j$ by HELLO message 2: CH${}_i$ calculates the position of CM${}_j$ at time t by Equations (22) and (23) 3: After a simple calculation, CH${}_i$ gets the grid which CM${}_j$ is in at time t 4: Table 1 look-up process 5: return CH${}_i$ will send the data message to CM${}_j$ with the power of P${}_x$ at time t

4.7. Cluster Maintenance

In the FANETs, due to the high-speed movement of UAVs, UAVs often join or leave the cluster. Violent node movement sometimes leads to the updating of the CH and the reconfiguration of network structure, which introduces large computation and communication overhead. Therefore, a reasonable cluster maintenance mechanism is needed to minimize the overhead and maintain the stability of the cluster structure.

4.7.1. Node Exiting Operation

To maintain the clusters effectively, the CHs broadcast their HELLO messages to their CMs periodically with a period T, and a CM replies with an ACK (acknowledgement) message to its CH, immediately after receiving the HELLO message. If the CH cannot receive an ACK from the CM for q periods, the CM is considered to not be in the transmission range and is depleted from the CM list. If a CH leaves the cluster, a CH reselection process is triggered.

4.7.2. Node Joining Operation

When a node exits the old cluster, it sends its HELLO message to the nearest CH to join a new cluster network. The CH will reply with an ACK message to the new node. Then, the new node will update its CH information, and the CH will add the new node to its members list.

The pseudocode of cluster maintenance is listed in Algorithm 4.

Algorithm 4 Cluster Maintenance

1: if ACK from CM${}_j$ is not received by CH${}_i$ 2: CH will deplete CM${}_j$ from its members list 3: The node which just exited the cluster will set its CH to null and broadcast its HELLO message 4: The nearest CH’ will reply with an ACK message to the node immediately 5: This node will update its CH information to CH’ 6: CH’ will add this node to its members list 7: end if

5. Performance Evaluation

In this section, the performance of the proposed DTPCH-C scheme is evaluated. First, the simulation settings are introduced in detail and the DTPCH-C is analyzed by different ways to divide the grid. Then, the performance of the proposed DTPCH-C is evaluated and compared with the benchmark methods, i.e., the grey wolf optimization (GWO) [14] and dynamic scale UAV weighted clustering algorithm (DSWCA) [20]. The metrics used in the simulation are the packet delivery ratio (PDR), network lifetime, and energy consumption.

5.1. Simulation Environment

The simulation parameters are listed in

Table 4. Simulation parameters.

Parameter	Value
Network area	2000 m × 2000 m
UAV maximum transmission power	0.3 mW
UAV reception sensitivity	0.3 nW
Intra-cluster carrier frequency	2.4 GHz
Inter-cluster carrier frequency	5 GHz
Number of UAVs	20–120
Speed of UAVs	40 m/s
Transmission range	500 m
Mobility model	Gauss-Markov
Initial energy of a node	10 J
Traffic type	CBR
CBR rate	2 Mbps
HELLO message interval	2 s
Data packet interval	1 s
Data packet size	4000 bit
Control packet size	100 bit
UAV reception sensitivity	−95 dBm
Number of runs	1500
Consumption of adjusting transmission power	0.1 mJ

. The number of UAV nodes varies from 20 to 100. The weighting coefficients of CH election strategy are $a_1$ = 0.45, $a_2$ = 0.43 and $a_3$ = 0.12. The initial energy of a node is set as 10 J. When the remaining energy of the node is less than 2 J, it will be regarded as a dead node; when the number of dead nodes reaches half, the network will be considered invalid. The energy parameters of flying consumption are set as $m_{\mathrm{UAV}}$ = 0.7 kg, $n_w$ = 4, and $r_w$ = 0.15 m [21].

5.2. Analysis of DTPCH-C Clustering Scheme

Firstly, the optimal grid division density is determined. If the grid division is very sparse, some cluster members can receive data packets from the cluster head without a lot of transmitting power. In this case, the energy is wasted because much transmitting power is set by the grid. However, when the grid division is dense, the transmitting power of CHs is frequently changed, which results in energy consumption. Figure 6 shows three ways to divide the grid. M represents the number of discrete transmission power levels of the CH (in different colors). $M=4$, $M=7$ and $M=10$ indicate that the transmission power of the CH is divided into four levels, seven levels and ten levels, respectively. Through the simulation, the scheme with the longest CH survival time can be obtained, which will be applied for the subsequent experimental tests. To accurately find the optimal partition scheme, we conducted two groups of experiments.

Figure 7 shows the survival time of FANET versus the number of UAVs under different grid partitioning conditions. We can observed that the lifetime of FANET based on the clustering scheme decreases as the number of UAV increases. This is because the mobility and the stability of FANET become dramatic when the number of UAVs increases, resulting in a reduction in the lifetime of FANET.

Figure 8 shows the lifetime of FANET versus the number of UAVs under different grid partitioning conditions. We observed that when the number of grids is small at the beginning, with the increased number of grids, the lifetime of the network increases; when the grid partition range is increased to seven intervals, the FANET survives the longest time. After that, the lifetime of the network decreases as the number of intervals increases. This is because when the division of the communication range is small, the division scope of the transmission power settings is also small, the effect of saving energy is not obvious. However, when the grid division is very dense, CHs need to switch transmission power frequently, which also causes energy loss. As shown in Figure 8, the optimal value is M = 7 in this simulation environment. We will conduct subsequent comparative tests with M = 7 which indicates that the transmission power of the CH is divided into seven levels.

The specific transmission power settings of the optimal scheme are listed in

Table 5. Specific transmission power settings.

Grid	P/mW
Purple	0.015 mW
Dark blue	0.035 mW
Light blue	0.065 mW
Green	0.1 mW
Yellow	0.15 mW
Orange	0.2 mW
Red	0.3 mW

. To improve the success rate of information transmission, we adjusted each value appropriately.

5.3. Clustering Scheme Comparison

In this section, we compared different clustering algorithms in terms of the node life cycle, the energy consumption, and the transmission success ratio under different UAV nodes.

Figure 9 shows the energy consumption of different clustering schemes within a certain amount of time under different numbers of UAV nodes. It can be seen that the energy consumption of the DTPCH-C scheme is lower than the other two counterparts. This is because the cluster head can flexibly adjust its transmitting power according to the distance with different cluster members, avoiding redundant energy consumption and saving resources.

Figure 10 compares the performances of the proposed DTPCH-C scheme with conventional DSWCA and GWO algorithms in terms of lifetime of FANET by varying the number of UAVs. We can see from Figure 10 that the network lifetime in all three schemes decreases with the number of UAVs increases. However, because the DTPCH-C scheme optimizes the cluster head selection and cluster head transmission power, the energy consumption of cluster head nodes in the network is reduced and the election of cluster head is more reasonable. As a result, the network survival time of the proposed method is much higher than that of DSWCA and GWO.

Figure 11 shows that packet delivery ratio of three schemes grows with the increasing number of UAV nodes. This is because as the number of UAV nodes increases, the average distance between UAVs decreases. As a result, the nodes become more dense, and the reliability of communication increases. It can also be seen that under the condition of the same number of nodes, the DTPCH-C scheme outperforms the other two candidates. The reason for this is that the DTPCH-C scheme optimizes the cluster head election. The elected cluster head is more stable in that it can reduce the probability of link disconnection, thereby improving the packet delivery ratio.

5.4. Time Complexity Analysis

The time complexity of Algorithm 1 K-means Clustering in the proposed DTPCH-C scheme is $O\left(KNI\right)$, where N is the number of UAVs, K is the number of clusters, and I is the number of iterations which is set to 50 in the simulation. The time of Algorithm 2 Cluster Head Selection is $O\left(N\right)$. The time complexity of Algorithm 3 Dynamic Transmission Power of Cluster Heads is $O(K\times \frac{N}{K}\times K)$=$O\left(KN\right)$. The time complexity of Algorithm 4 Cluster Maintenance is dominated by Algorithm 2.

Table 6. Time complexity analysis.

Methods	Cluster Formation	CH Selection	Dynamic Transmission Power of CH	Cluster Maintenance	Overall Complexity
DTPCH-C	$O\left(KNI\right)$	$O\left(N\right)$	$O\left(KN\right)$	$O\left(N\right)$	$O\left(KNI\right)$
GWO [14]	$O\left(KNI\right)$	-	-	$O\left(N\right)$	$O\left(KNI\right)$
DSWCA [20]	$O\left(KNI\right)$	$O\left(N\right)$	-	$O\left(N\right)$	$O\left(KNI\right)$

summarizes the time complexity of the proposed DTPCH-C scheme and the two benchmark methods, namely, GWO and DSWCA.

6. Conclusions

This paper has optimized the clustering algorithm of the FANET to adapt to the complex combat environment and make the network reliable. Based on the traditional K-means algorithm, this paper has presented the clustering and CH election method. The variable transmission power mechanism of CH has been also proposed. The simulation results show that, compared with DSWCA and GWO, the proposed DTPCH-C has enhanced the lifetime of the FANET, reduced the energy consumption and improved the packet delivery ratio. In the subsequent study, we will continue to further study the improvement of the FANET’s lifetime. We will consider the optimization of energy consumption for CMs to make the lifetime of the FANET longer.