|Computer Systems Science & Engineering |
UAV Clustering Scheme for FANETs using Elbow-Hybrid Metaheuristic Techniques
1Department of Electronics and Communication Engineering, National Institute of Technology Patna, Patna, 800005, India
*Corresponding Author: Kundan Kumar. Email: email@example.com
Received: 10 January 2021; Accepted: 23 February 2021
Abstract: Great strides have been made to realistically deploy multiple Unmanned Aerial Vehicles (UAVs) within the commercial domain, which demands a proper coordination and reliable communication among the UAVs. UAVs suffer from limited time of flight. Conventional techniques suffer from high delay, low throughput, and early node death due to aerial topology of UAV networks. To deal with these issues, this paper proposes a UAV parameter vector which considers node energy, channel state information and mobility of UAVs. By intelligently estimating the proposed parameter, the state of UAV can be predicted closely. Accordingly, efficient clustering may be achieved by using suitable metaheuristic techniques. In the current work, Elbow method has been used to determine optimal cluster count in the deployed FANET. The proposed UAV parameter vector is then integrated into two popular hybrid metaheuristic algorithms, namely, water cycle-moth flame optimization (WCMFO) and Grey Wolf-Particle Swarm optimization (GWPSO), thereby enhancing the lifespan of the system. A methodology based on the holistic approach of parameter and signal formulation, estimation model for intelligent clustering, and statistical parameters for performance analysis is carried out by the energy consumption of the network and the alive node analysis. Rigorous simulations are run to demonstrate node density variations to validate the theoretical developments for various proportions of network system sizes. The proposed method presents significant improvement over conventional state-of-the-art methods.
Keywords: Clustering; elbow method; hybrid; UAVs; FANETs; energy consumption
UAVs have witnessed widespread application in a varied range of application area. Collaboration of UAVs has been employed for patrolling of borders , disaster management , rescue and search operations , wildfire monitoring , remote sensing and agriculture , ground and position tracking [6,7], etc. The unique characteristics and advantages of the UAVs such as flexible operation, minimal cost requirements, scalability, flexibility and speed of operation qualify them for the diverse set of applications .
With the help of UAVs, a new area of ad-hoc networking is introduced as the Flying Ad-hoc Network. In this network architecture, all the UAVs communicate among each other and at the most one UAV will communicate with the control station for coordination and exchange of information. FANETs face certain challenges owing to the unique features of the UAVs . Most of the design requirements are with respect to these features. The first challenge encountered is the unstable topology due to high mobility of the UAVs . This results in high overhead in routing due to frequent change in positions, unreliable communication and link outage. When the UAVs are very sparsely deployed, the distance over which the communication is taking place is high. Consequently, the energy requirement increases which alleviates the performance of the FANETs as they are equipped with limited battery resources .
Clustering is an efficient approach to address the stable topology and energy efficiency requirement of the UAVs . This is by virtue of the scalable and the minimum overhead requirement characteristics of clustering . The clustering process will divide the UAVs in the FANETs into different groups. Based on the performance of the UAVs, one UAV from each group takes up the task of head-node . The head-node aggregates the information of its cluster and forwards it to the destination. This ensures topology maintenance with minimum resource overheads  and lowered cost for communication amongst the UAVs. An illustration of UAV clustering is shown in Fig. 1.
Swarm intelligence has found extensive applications in the field of clustering in ad-hoc networks . Clustering process requires certain benchmarks to achieve the formation of optimal clusters. Further, clustering can also be viewed as an optimization problem . Literature shows the execution of various metaheuristic techniques for clustering in ad-hoc networks. Optimization techniques like Particle Swarm Optimization (PSO) involve position and velocity update for every iteration, and it has been extensively used in mobile ad hoc networks (MANETs) . Ant Colony Optimization (ACO) closely mimics the pheromone-dependent behavior of honeybees popularly used in vehicular ad hoc networks (VANETs) . Glowworm swarm optimization (GSO) is yet another luciferin-based metaheuristic technique amongst many more which are being implemented for clustering in flying ad hoc networks (FANETs) .
1.1 Literature Review
Various works considering the design restrictions of UAVs and its resulting problems have been carried out in the past. Authors in Zafar et al.  proposed a clustering technique to ensure the reliable transmission of data in FANETS. Based on their position, they are divided into clusters. Appointment of head-node is dependent on the signal to noise ratio (SNR). Data transmission can be from either cluster head to cluster head, or from relaying of data to the destination based on the link quality of the cluster heads between which the communications needs to take place. Shi et al.  considers both clustering and route maintenance for improving the efficiency in the collaboration of the UAVs. It defines two transmission ranges each, for intra cluster and inter cluster communication. Head nomination is based on the speed, degree, residual energy, and tactical value. The tactical value is defined as the node weightage.
In Zang et al. , an algorithm focused on the high mobility of the UAVs based on weighted-clustering technique has been proposed. Several factors such as neighborhood probability of the UAV node, link expiration time and degree of connectivity etc. dominate the selection of the optimal cluster head. Based on these factors, a weightage function is created. Node having the highest weightage is elected as cluster head. Park et al.  proposes multiple approaches for cluster head election in UAVs by considering distance between ground control station (GCS) and the UAV, and the residual energy as the primary metrics. The clustering process is controlled by the GCS. The first method works on random election of cluster heads, while the second method selects the cluster heads based on its highest residual energy. Finally, the last method considers both the metrics for election. Addressing the issue of routing and battery resource limitations, a k-means sorted algorithm is proposed in Aadil et al. . The algorithm implements the k-means algorithm which appoints the head-nodes with the highest reservoir of energy, neighborhood, and the distance parameter. It also has a provision for electing different transmission power based on the distance between the two UAVs under communication. Different power levels for different transmission ranges are also defined.
It is evident from literature that metaheuristic techniques are being employed for clustering in FANETs and other ad-hoc networks. Also, implementation of hybrid algorithm is carried out to improve the efficacy of the network. A three phase method based on the combined effect of luciferin attraction of glowworm swarm optimization (GSO) and the marine ecosystem inspired Krill Herd (KH) algorithm is proposed in Khan et al. . The method attempts to improve the energy efficiency of the network, thereby, improving the lifetime of the network. The first phase of the method is the cluster formation, which is carried out by GSO. This is followed by management of the topology by the KH. Finally, the network-maintenance phase monitors the energy and working levels of the UAVs. However, the work lacks intelligent estimation techniques that would have, otherwise, helped in cluster formation. In Khan et al. , GSO is implemented as a self-organization based method for clustering. Based on the behavioral nature of GSO, the connectivity and the residual energy of each UAV node, clustering of nodes is carried out. If the connectivity is not there, the node with highest residual energy is elected as the cluster head. The method also includes the management of its topology for stability and improved lifetime. However, it leaves the scope of improvement because of exclusion of channel state information, which is critical to the performance of FANETs because of rapidly changing environment around the UAVs.
A polynomial time algorithm and spiral network discovery for optimal count of UAV to cover the target area is devised in Lyu et al. . UAV clustering may also be optimized by formulation of a constrained mixed integer cost function to deal with high communication cost without data aggregation, as described in Thammawichai et al. . While some works have treated UAVs as static, a more accurate representation is to incorporate dynamic clustering, which would subsequently lower the transmit power as compared to traditional clustering schemes such as k-means clustering. One such approach has been attempted using modified Louvain method  and the results are shown to be superior in several aspects. Besides mobility of the UAVs, there are restrictions on cluster size in terms of physical coverage area as well as the number of UAVs per cluster. By considering these constraints, the inefficiency of clustering process may be improved. A game theoretic proposition has been worked out in Xing et al.  for coalition framework modelling, and the results have been shown to enhance UAV clustering efficiency under controlled conditions. Since UAV networks suffer from high delay during transmission of data, an intelligent clustering method using block coordinate descent method has been demonstrated to reduce this delay by improving cluster coverage in FANETs. The recent related works on UAVs have been given in Tab. 1.
1.2 Motivations and Applications
UAV has been used extensively by governing bodies to secure hostile  terrains by scanning them aerially. Typically, human intervention is nil. UAVs are beneficial in agricultural mapping [30,31] and monitoring. E-commerce is at its nascent stage of delivering goods [32,33] and services with the help of UAVs. The commercial viability has enabled in providing mobile base stations with the help of UAVs to selectively sense and gather data in an on-demand basis.
Since most of the works in literature have addressed various parameters of UAV clusters in detail, it is imperative that we consider some of these parameters together to come up with intelligent estimation technique that would determine the clustering behavior of UAVs in FANETs. This is the prime motivation behind current work, and the authors have tried to quantify their findings to the best of their knowledge. A holistic overview of the approach in this paper has been illustrated in Fig. 2. Here, the formulation phase leads to a mathematical implementation phase, followed by a verification phase to come up with lifetime and computation related parameters of the proposed method. Considering the restrictions and the possible approaches, the paper contributes the following:
a) A System Model is presented which highlights parameters of the UAVs critical to clustering and data transmission.
b) An intelligent estimation of UAV-parameters is derived mathematically to be integrated into clustering techniques.
c) Elbow Method is implemented to determine the suitable size of cluster in the deployment scenario of the FANET.
d) Estimated UAV parameter vector is used to modify two popular hybrid metaheuristic algorithms, first, a combined framework of Water Cycle Algorithm (WCA) inspired from the hydrological balance between the three states of water on earth, and the spiral hovering of moth around a light source, named aptly Moth Flame Optimization (MFO). Second, Grey Wolf Optimization (GWO) which mimics the cooperative hunting ability of a pack of wolves, is combined with the swarm behavior of Particle Swarm Optimization (PSO) for performing the clustering and election of cluster heads.
e) To corroborate the theoretical findings, rigorous simulations are run to demonstrate node density variations for various proportions of network system sizes. The results are compared with other techniques to highlight the improvement gained due to intelligent UAV parameter estimation.
To the best of the authors’ knowledge, hybrid metaheuristics with UAV parameter estimation have not been attempted together in the literature for efficient clustering of UAV networks. Therefore, the findings of the current paper are new. The paper has been organized as mentioned: Section 2 describes the Parameter, Signal and System Model of clustering of UAVs. Numerical computations are carried out in Section 3 to validate theoretical findings. Closing remarks are mentioned in Section 4.
2 Proposed Method
UAV nodes in the FANETs have been clustered to address the issues of limited energy and stability in FANETs. The method initially determines the number of clusters required for the deployment scenario. It optimizes the energy consumed in the FANETs as it ensures a tradeoff distance for communication among the head-node and the cluster members. The number of clusters is achieved by the Elbow Method. Further, the network area is partitioned into sub regions based on the number of appropriate clusters to be formed via the k-means algorithm. This is followed by the clustering process and cluster head selection done by the hybrid algorithms, namely, water cycle-moth flame optimization (WCMFO) and Grey Wolf-particle swarm optimization (GWPSO). Cluster heads are elected depending upon the energy level of the UAV nodes and the delay apprehended in the network. Communication amongst the UAVs is carried out via the head UAV which forwards the data towards the control station either directly or via nearest cluster head UAV. Re-clustering is carried out when the head UAV node reaches its threshold condition. The broad outline of clustering approach is presented in Fig. 3. This section provides the network model, details of the hybrid algorithms implemented and the fitness function.
2.1 System Model
We consider a group of multi- energy UAVs where the cluster heads are equipped with the ability to transmit short pulses of higher amplitude. The clusters count of consist of similar energy UAVs that are within connectivity range of each other. The received pulse at any UAV in a cluster under Gaussian noise is given by
where, is the free space channel impulse response of jth UAV in ith cluster. The vector form of Eq. (1) is given as
where, is the free space channel vector from the cluster members to the cluster head. The critical dependence of optimal clustering is decided by energy level and communication range of any UAV, amongst other parameters. We propose a ‘Span-out model’ to enable efficient clustering as explained below:
Let a trio of UAV elements , , cover a span of aerial space denoted by region . Based on the proximity of these three UAVs, they share the updated values of energy , channel state information and mobility . A vector called ‘UAV- parameter’ is proposed, which is a linearly weighted mixture of three parameters, namely, energy , channel state information and mobility .
where , and are the linear coefficient matrices corresponding to each of the three respective parameters. Since a triangulated region is the bare-minimum criteria to form an enclosed space, these three UAV elements are now free to assess any other UAV endurance and continuously monitor this parameter in order to assist in election of next set of cluster heads optimally. Once this information spans out throughout the cluster, the cluster head UAV selection becomes much easier. Based on the current UAV parameter vector, the estimated UAV parameter vector needs to be predicted for the next instance for improved head selection.
Let the minimum mean square estimate (MMSE) of the UAV parameter be given by
where, the signal model is as follows
where is Gaussian Noise with zero mean and variance . To estimate the unknown UAV parameter, let the unknown parameter be . Then, the likelihood function associated with is given by
where, is the covariance matrix of the noise associated with measurement of . To gauge the suitability of measured values, the correlation matrix between energy and mobility is found to be , where, represents the charge content of energy cells which power up the UAVs and is the matrix associated with the rate of change of position of the UAVs. Then, the covariance matrix of , denoted by is computed by
Thus, the MMSE estimate may be calculated according to Bayesian Gauss-Markov Theorem  as:
where, is the covariance matrix of measurement noise. The estimated UAV parameter has an error performance of , which is yet again a random variable. is characterized by zero mean and covariance
The significance of Proposition 1 is that it enables us to monitor UAV health parameters for improved cluster head prediction.
2.2 Network Model
In this paper, FANET is considered over a network area of q×q m2 area deploying ‘K’ UAV nodes having a geographical location of (xk, yk, zk) and an initial energy level of Ek. Fig. 4a depicts the initial deployment scenario. The control station is assumed to be at the boundary of the network area. Since the UAVs are mostly in line of sight (LoS) , Free Space Path Loss (FSPL) propagation model is considered. The implementation of the presented method yields ‘N’ clusters with each cluster having a cluster head HN. The scenario after clustering is shown in Fig. 4b. The communication among the UAVs follows the First Order Radio Model as in Aadil et al.  where the L2-norm between the UAVs decides the energy consumption during transmission-reception of signals. In view of maintaining a stable topology the Reference Point Group Mobility (RPGM) Model is followed . According to this, the cluster members congregate in tandem with the movement of the head UAV nodes, thus maintaining the topology.
A flowchart describing the estimation of parameter- based UAV clustering is shown in Fig. 3. The general framework of any metaheuristic clustering technique requires initialization of UAV positions followed by residual energy calculation of each UAV. If the UAVs require clustering, then first the parameters discussed in section 2.1 are estimated for each UAV. Then, the number of clusters is optimally found by utilizing elbow method. Using K-means technique, an initial set of clusters is created. Based on estimated individual parameter values, a cost function is formulated and subjected to various constraints. The cost function is then solved using emerging hybrid metaheuristic techniques to determine the optimum cluster heads. After every round of transmission, the same technique is evaluated again, till the UAVs have either completed all transmissions, or they deplete their energies completely. The role of estimation-based clustering enables accurate cluster head prediction. This cluster head prediction is possible when the UAV health vector is tuned according to UAV energy, its channel state information and the mobility factor of FANET.
2.3 Elbow Method
The elbow method is introduced to ensure optimal numbers of clusters for clustering . The method considers the L2-norm between the cluster head and the cluster members to determine the optimal situation. This distance is known as the within cluster sum of squares (WCSS). It tries to deduce the number of clusters wherein there is tradeoff between the WCSS in terms of forming distinct and closed clusters. Considering two network areas of 1000 × 1000 m2 and 2000 × 2000 m2, for a node density of 55, the optimal number of clusters was found to be 6, using the Elbow Method. This is depicted in Fig. 5.
2.4 Clustering by Hybrid Metaheuristics
In this method, after the initial segmentation to ‘N’ sub regions based on the K-means algorithm, a hybrid metaheuristic algorithm is implemented for selecting the optimal cluster heads. The optimal selection depends on certain factors such as energy levels and the delay introduced by it. This section details the hybrid algorithm and the process by which it is being incorporated into the proposed method.
2.4.1 Algorithm 1: WCMFO
The hybrid algorithm of the Water Cycle Algorithm (WCA) and the Moth Flame Optimization (MFO) is implemented as in Khalilpourazari et al. . The algorithm improves the exploration and exploitation capacity of the WCA. The local search is improved by introducing the spiral movement of the moth, while the randomization by the Levy flight increases the global search ability in the area where the ‘K’ UAV nodes are randomly deployed. The solution for the algorithm is the sea, which is the fittest among ‘M’ streams initialized. Hence, the solution space is ‘M’ streams that contains ‘N’ eligible cluster heads selected from each sub-region. The streams are further segregated to sea, rivers and streams as shown in Eqs. (10) and (11), respectively.
where, is the combined count of all rivers and a sea, is the number of streams which flow into the rivers or may flow directly into the sea. The distance of the sea from the river and stream respectively is calculated further. The position of the streams, rivers are updated based on the spiral movement of the moths as in Eqs. (12)–(14). Based on the fitness function of the new position, again the sea, rivers and streams are designated.
where, denotes the new position of water body at iteration, denotes the old position of water body at iteration, denotes the distance between sea and streams. is the convergence constant which has an output range of , is a constant for defining shape of the spiral and t is a random number between . The streams undergo the Levy flight to introduce the randomization factor and also, the evaporation condition is checked as in Eqs. (15)–(17). The process continues till the termination condition is attained. Output of the algorithm is ‘N’ cluster heads and its corresponding cluster members.
where, and are the maximum distance between any two consecutive water bodies during and iteration, is the maximum number of iterations, and are the respective positions of stream and river in the iteration. and are the upper and lower bounds respectively of their stream positions.
The flowchart of the estimator modified WCMFO algorithm is given in Fig. 6. The network and algorithmic parameters are initialized first, followed by selection of UAVs having energy higher than the threshold. Then the eligible cluster heads are initialized just like rain drops of water cycle algorithm. The UAV parameter vector is then intelligently estimated to determine the future mobility, energy, and channel state information of the UAVs and the network. Based on these parameters, the fitness function of each UAV is computed. Fitness value also determines the classification of water bodies into streams, rivers, and seas. The upcoming position of UAVs is determined by following the spiral movement of moths towards the central flame, and the position of streams using Levy’s flight. Depletion of UAV energy is emulated by evaluating the evaporation condition. Upon completing a finite number of rounds, the process is terminated, and we check for the number of rounds which have been optimally clustered.
2.4.2 Algorithm 2: GWPSO
In the implementation of the GWPSO , Particle Swarm Optimization (PSO) and the Grey Wolf Optimization (GWO) are incorporated. In this algorithm, the improvement in the local search of PSO is introduced by the global search capabilities of the GWO. The search space for the algorithm is the network area of the FANET with the ‘N’ sub region. A set of ‘M’ particles with ‘N’ cluster heads is initialized as the search space. Based on the fitness these particles are designated as the alpha, beta, and delta particles. An inertia constant value is introduced in the Eq. (18) which governs the encircling behavior of the particles. ‘p’ in Eq. (18) can be alpha, beta, or delta particle. The position of these particles are then updated as in Eqs. (19)–(21), where i = 1, 2, 3.
where, , , are respectively the radius of encirclement of particle, the inertia of the particle p, the position of the particle p.
where, decreases linearly from 2 to 0. r1, r2, r3 are random values. and are the respective velocities and positions. The final position is determined as in Eqs. (22) and (23). The process continues till the termination condition is reached, yielding the cluster heads and the corresponding clusters.
The flowchart of the intelligent estimator modified GWPSO algorithm is shown in Fig. 7. The first phase involves initialization of set of parameters for the algorithm as well as the UAV network. The UAVs having energy above threshold are selected and cluster heads are eligible for particle initialization. Then the UAV parameter vector is intelligently estimated to determine the next potential UAV energy, mobility, and channel state information of the network. This parameter vector is used to determine the position of three kinds of particles, namely alpha, beta and delta. The position and velocity of UAVs are updated according to the particles of swarm. The convergence constant ‘a’ is computed to check for optimality condition. These steps are iterated till the UAV nodes run out of energy, or successful transmissions are completed.
2.4.3 Fitness Function
The quality of the cluster head required for the process of clustering is determined by the fitness function. The main function of the optimization approach is to bring about a tradeoff among the objectives to be achieved. The fitness function in this method considers the energy level and the delay as the basis for cluster head election. Energy level is considered to check the survivability of the head nodes, while delay is associated with the reliable and timely transmission of the data. The multi-objective minimization function as shown in Eq. (24).
The functions fa, fb are adapted from [39,40] and incorporated to obtain the optimum situation in the FANETs. They denote the cost functions related to energy requirement and delay associated with each UAV. The Eqs. (25) and (26) govern these factors, . ‘K’ number of UAV nodes are deployed and ‘N’ number of clusters are formed in the search space. HN denotes the cluster head for the cluster N. Eres depicts the residual energy of each nodes and NumN denotes the degree of nodes in the cluster K.
3 Results and Analysis
This section briefs the simulation setup and the results obtained based on the parameter evaluation. The parameters considered are the energy consumption and the alive node analysis. Both the parameters give an insight to the lifetime and efficiency of the network. The correlation coefficient between different UAV estimation parameters is crucial because it links charge content of UAV power source with the rate of change of position of UAV, in the presence of a dynamically changing channel state information.
3.1 Simulation Setup
The proposed method is simulated for a FANET setup, where the nodes are randomly deployed. Two network areas, 1000 × 1000 m2 and 2000 × 2000 m2 are considered and the node density is varied from 25 to 55. Simulation parameters are tabulated in Tab. 2. MATLAB is the platform used for the simulations.
3.2 Performance Analysis
The performance of the two hybrid algorithms implemented in the proposed method is compared with respect to network energy consumption and the analysis of the number of alive-nodes. In both the proposed methods, UAV parameter estimation phase is exploited to compute the fitness function to come up with the requisite node analyses. Energy consumption of the proposed method depends on the following constraints: Correlation coefficient between the charge content of UAV power source and the rate of change of position of UAV.
3.3 Energy Consumption
The importance of controlled energy exhaustion is critical due to the limited battery availability of the UAVs. The communication amongst the UAVs are considered using First Order Radio Model. The energy consumption is checked for a stipulated number of transmissions. Fig. 8. depicts the energy consumption of the network for both the network areas. It is evident that WCMFO performs better than the GWPSO, which implies limited energy consumption and a longer network lifetime. With increasing node distance, energy consumption sees an upward growth trend, with the proposed method exhibiting slower growth than the competing models, meaning improved performance.
3.4 Alive Node Analysis
Alive nodes analysis gives an insight of the operational nodes per round of transmission in the network. The lifetime and operation of the network can be determined with the help of alive node analysis. Fig. 9. shows the alive node analysis of the network where the number of nodes operational is checked for the first 5000 rounds. It is carried out for an initial node density of 45. The graphs reveal that WCMFO lifetime is better compared to the GWPSO, hence depicting its efficiency in terms of node lifetime. The number of alive nodes rapidly ceases during the first 3000 rounds in case of competing methods (PSO and WCA).
Tab. 3 summarizes the comparative results in tabular form.
Summarizing the findings of Section 3, the computational analysis included energy consumption and alive node determination for different node deployment sizes. Observing the results, the superiority of the proposed techniques was established with respect to the convergence rate, node density, node death rate etc. In terms of convergence rate, the proposed GWPSO was found to converge faster than conventional PSO, and the proposed WCMFO was found to converge faster than WCA. Energy consumption wise WCMFO was found to be the most efficient, then followed by the proposed GWPSO, while PSO consumed the most energy.
In this paper, the proposed method for clustering in FANETs was presented. It addressed the limited battery availability and unstable topology issues of the UAVs. An intelligent estimation of UAV parameter vector was formulated, and mathematical expression was derived to compute the errors associated with prediction of next state of UAVs. Ideal number of clusters required by the network scenario was then determined by the Elbow Method. Clustering by two emerging hybrid methods WCMFO and GWPSO was implemented by incorporating UAV parameter estimation into the respective fitness functions. Simulations were run for two network areas by varying the node densities. The performances were evaluated based on the energy consumption of the network and the alive nodes to analyze the improvement in the lifetime of the network and to compare with existing schemes. The results demonstrated superior attributes of WCMFO algorithm within the scope of analysis. The better performance of the WCMFO might be attributed to the improvement in the exploration and exploitation phase in the WCA with the inclusion of spiral movement and Levy flight, making it more robust and efficient. The superior performance of modified hybrid techniques over the existing conventional ones highlighted the importance of accurately estimating the UAV parameters and their subsequent inclusion into the cost function to incorporate machine-intelligent UAV clustering in modern-day FANETs.
Funding Statement: The authors received no specific funding for this study.
Conflicts of Interest: The authors declare that they have no conflicts of interest to report regarding the present study.
|This work is licensed under a Creative Commons Attribution 4.0 International License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.|