# A Survey on Cluster Head Selection and Cluster Formation Methods in Wireless Sensor Networks

Authors: Bryan Raj; Ismail Ahmedy; Mohd Yamani Idna Idris; Rafidah Md. Noor
Journal: Wireless Communications and Mobile Computing
 (2022)

---

## Abstract

In recent years, wireless sensor networks (WSNs) have been growing rapidly because of their ability to sense data, communicate wirelessly, and compute data efficiently. These networks contain small and low-powered sensor nodes that organize and configure themselves to carry out their functions. Even though WSNs are cheap, easy to deploy, flexible, and efficient, there are some challenges in terms of energy efficiency and network lifetime. Clustering in WSNs is the most reliable solution for the challenges, in which nodes are grouped into few clusters, and a cluster head (CH) is selected for data aggregation and data transfer to the base station (BS). However, there are still many challenges such as energy hole and isolated node problems that exist because of inefficient CH selection and cluster formation methods. In this work, we comprehensively reviewed various nonmetaheuristic and metaheuristic methods for CH selection and cluster formation that are used in networks from various environmental settings, for a better understanding of how the aforementioned problems are tackled by some authors. Moreover, the methods’ parameter settings, advantages, limitations, and future directions are presented with a brief performance summary of the approaches.


---

## Body

## 1. Introduction

The rapid growth of wireless sensor networks (WSNs) has contributed to their wide usage in many applications such as disaster management [1], RFID networks [2], drone application [3], and medical applications [4].Since WSNs are made up of low cost and small-sized sensor nodes, they face a few limitations such as limited battery capacity, small memory size, and shorter communication ranges. The energy usage in WSNs is continuous, as it is used during data sensing, data collection, and in the data transmitting phase. The data transmitting phase uses the most amount of energy on average, where to transmit a single bit of data over 100 m by radio costs the same amount of energy as executing 3000 instructions [5]. In recent years, the energy efficiency problem has received more focus because changing or recharging the battery supply cannot be done easily for networks in large scale or remote areas [6]. Furthermore, efficient data transfer is another problem faced in WSNs. This is due to a mismanagement of WSNs that will increase the packet payload size, which directly increases the probability of dropping data packets. As such, retransmission of data packets will consume more energy as well [7].In early 2000s, Heinzelman et al. [8] introduced an energy-efficient communication protocol which is termed as LEACH (low-energy adaptive clustering hierarchy). LEACH helps in optimizing the power consumption through a clustering technique, where a few CHs are selected based on cluster rotation, and other nodes join these cluster heads to form clusters. The sensed data are sent to the respective CH to be aggregated, and the data is then transmitted to the BS by the CH [8]. Back then, this was a very successful method, where LEACH helped enhance the network lifetime by saving the energy usage in the transmission phase. Although, the method enhanced the energy efficiency, there were some challenges faced in the long run. The most common problems faced were the network hole problem and the isolated node problem. The network hole problem is also called as a hotspot problem, where the CH near the BS depletes energy faster as compared to the nodes far away from the BS in a multihop environment, as most of the data reaches to the CH near the BS for aggregation and data transfer to the BS [9–13]. On the other hand, the isolated node problem is where nodes do not join any cluster and do not have a path to send data to the BS [14–16].These problems are tackled by proposing a few techniques and methods such as unequal clustering, mobile BS, and efficient CH selection method. Unequal cluster formation is where clusters near the BS have a lower number of sensors compared to the clusters far away from the BS. Therefore, a CH near the BS uses lesser energy to communicate with its cluster members, and it can communicate with other CHs that are far from the BS, making the load balanced [4, 17, 18]. A mobile BS is where the sink is moved from time to time to collect the sensed data from the cluster heads [19]. Both methods take more effort and consume more energy in terms of cluster formation and memory usage to keep track of the location of the mobile BS. This leaves us with the appropriate CH selection method, which has been widely researched and discussed in recent years. CH selection is done by setting a few selection criteria such as residual energy of the node and the distance between cluster members (CM), CH, and BS. In some research, the selection criteria are inserted into a metaheuristic method for faster convergence and better accuracy of selecting CHs as well as ensuring a better QoS of the network.From the reviews done of the past decade, it is observed that most of the survey articles do not discuss the inclusion of metaheuristic algorithms in clustering. Most of the surveys cover topics regarding clustering objectives and the types of clustering models in terms of probabilistic and deterministic models, which will be explained and discussed further in Section2. Moreover, most of the surveys do not discuss the recently researched clustering methods and techniques. In this article, a comprehensive survey on the nonmetaheuristic and metaheuristic methods in clustering the WSNs is presented.The contributions of this work are as follows:(i)
Detailed concepts of cluster head selection techniques in nonmetaheuristic and metaheuristic methods are presented(ii)
Detailed concepts of cluster formation techniques in nonmetaheuristic and metaheuristic methods are presented(iii)
All the presented techniques are analyzed in terms of various environment settings(iv)
Various types of nonhybrid and hybrid metaheuristic techniques, including their overall parameters, setting, evaluation, advantages, and disadvantages are presented(v)
Usage of various methods in certain applications in terms of medical applications, drone applications, and disaster management are also discussed(vi)
Multiple comparative analysis tables are presented for a clearer and better understanding of the differences and similarities(vii)
The open issues and future directions of cluster head selection techniques and cluster formation techniques are discussedAt the end of this survey, readers would be able to differentiate the methods in nonmetaheuristic and metaheuristic cluster head selection and cluster formation phases in terms of their limitations and advantages. Readers will also be able to know the performance of certain methods in different environment settings such as mobile nodes, multihop and single-hop data transfer, heterogeneity of sensor nodes, and other parameters involved. The challenges and future direction may help in further research in this field of study, as having a proper CH selection or cluster formation technique may help to reduce energy consumption in various applications.The remainder of the paper is organized as follows: Section2 presents some related reviews on clustering in WSNs. Section 3 presents the overview of LEACH, with an overall taxonomy of clustering in WSNs based on nonmetaheuristic and metaheuristic methods. Section 4 presents a discussion on the various methods in nonmetaheuristic techniques. Section 5 discusses the various methods in metaheuristic techniques. Section 6 presents comparative analysis, the method’s performance discussion, open issues, and future directions of the clustering-based research. Section 7 concludes the article.


## 2. Related Work

In the past decade or so, there have been several surveys presented on the theme of clustering. After analyzing these articles, few advantages and limitations have been deduced.In 2008, a survey on cluster head selection in clustering algorithms in WSNs was presented [20]. In that article, the cluster head selection was categorized into 3 strategies, which were a deterministic scheme, an adaptive scheme (fixed parameter probabilistic and resource adaptive probabilistic models), and a combined metric scheme. An analysis was done on the comparison of various cluster head selection strategies in terms of their assistance considered in cluster head selection, parameters used, required reclustering, required cluster formation, even or fair distribution of cluster heads, and creation of balanced clusters. A similar survey was later presented by [21] where additional information was discussed on four types of clustering models that exist, which are the single-hop flat model, single-hop clustering model, multihop flat model, and multihop clustering model. In the year 2013, Tyagi and Kumar [22] presented a survey on clustering algorithms based on the LEACH protocol. The algorithms were classified into different parameters which were further categorized into various objectives that the researchers wanted to achieve. A comparison of network performances was done, and open issues that were seen by the author were also discussed.Three methods of the cluster head selection technique, which are the fuzzy logic, genetic algorithm, and neural network were presented by [23]. The advantages and disadvantages of these methods were analyzed as well. Various existing nonhybrid metaheuristic and hybrid metaheuristic algorithms were discussed in [24]. The hybrid algorithms in the article were divided into collaborative hybrids and integrative hybrids. The advantages and disadvantages of the past, present, and future algorithms were also discussed. One drawback of the article is that it does not explain the algorithm usage in a WSN environment. In the same year, a comprehensive survey was carried out on clustering algorithms [25]. In the beginning of this article, the distance and similarity functions on building clustering algorithms were discussed, followed by a discussion on the evaluation indicator used to test the validity of the clustering algorithms. The clustering algorithms were categorized as traditional clustering algorithms and modern clustering algorithms, where the analysis was done in terms of time complexity, advantages, and disadvantages of the algorithms.In 2016, a survey on mobile ad hoc network (MANET) clustering in terms of cluster formation and cluster head selection was presented [26]. The paper compared LEACH with the LID algorithm and HD algorithm, where its advantages and disadvantages were discussed in CH selection. A survey focusing on energy efficient clustering approaches in WSNs was performed by [27]. The techniques and methods were categorized into 2 hierarchical clustering approaches, the cluster-based and grid-based approaches. The groups of hierarchical clustering approaches were briefly explained, which consisted of homogeneous and heterogeneous networks, centralized or distributed algorithms, static and dynamic clustering, probabilistic and nonprobabilistic algorithms, and uniform and nonuniform clustering approaches.Twelve major clustering protocols were discussed by [28] based on several metrics such as mobility, overlap of clusters, position awareness, energy efficiency, uniform clustering, and stability of clusters. The protocols were also analyzed in chronological order for a better view on evolution of the clustering protocols. Another survey was presented on clustering algorithms in terms of probabilistic and nonprobabilistic protocols [29]. In this survey, the limitations and advantages of each protocol were clearly defined to differentiate their significance. In a recent survey, the clustering methods and techniques were categorized based on the clustering objectives [30]. This article presents a statistical analysis on several literatures in recent years that were researched to cater for certain clustering objectives, which provides a concise future research direction for clustering in WSNs. The comparison of related works is depicted in Table 1.Table 1
The comparison analysis of the existing surveys.
PaperMetaheuristic methodsCH selection techniqueCluster formation techniqueEnvironmental setting analysisParameter setting analysisYears of literature used[20]NoYesYesNoNo2000-2008[21]NoYesYesNoNo2002-2011[22]YesYesNoYesNo2000-2012[23]YesYesNoNoNo2000-2012[24]YesNoNoNoNo2001-2014[25]YesYesYesNoNo1990-2014[26]NoYesNoYesNo2009-2015[27]NoYesYesNoNo2002-2017[28]NoYesYesNoNo2002-2016[29]NoYesYesYesNo2000-2015[30]YesYesYesYesNo1981-2020The aforementioned surveys give a good understanding and wider knowledge on the idea of clustering and its techniques. However, they impose certain limitations in terms of discussions on metaheuristic algorithms, environmental setting, and parameter setting analysis and recent clustering protocols that correspond with the current trend of WSNs. The current survey furnishes a review of nonmetaheuristic and metaheuristic methods in cluster head selection and cluster formation techniques, to solve certain objectives where the methods are deployed in different environmental settings such as mobility, multihop and single-hop data transfer, heterogeneity, and other parameters. The significance and limitations of the methods as well as the future directions towards comprehensive clustering in WSNs are also presented.


## 3. Clustering in Wireless Sensor Networks

### 3.1. Low-Energy Adaptive Clustering Hierarchy (LEACH)

The sensor nodes in WSNs cooperate with each other to detect a change in physical or environmental aspects. The sensed data are then collected and sent to a primary base location called BS, for the data to be observed and analyzed [31, 32].LEACH is made up of microsensors that are cheap and energy efficient, to achieve better quality results in large scale networks [8]. LEACH organizes itself by using adaptive clustering, cluster head rotation, and local computation in order to have a balanced energy distribution in the network. There were two assumptions made in this research, which are (1) the base station is stationary and located far away from the sensor nodes and (2) the sensors in the field are homogeneous and energy constrained. Recent research has also evaluated LEACH-based clustering in heterogeneous and mobile scenarios [13, 33]. LEACH consists of two important phases which are the set-up phase and the steady-state phase. The steady-state phase is longer in comparison to the set-up phase, the aim of which is to minimize overhead. Typically, in LEACH, the CH is selected first before the clusters are formed, but it is not the same for all the existing methods of clustering, as some researchers tend to improve the objectives by performing cluster formation first, such as [34]. The overview of LEACH is shown in Figure 1. In LEACH, the cluster head is selected first before the cluster is formed.Figure 1
The overview of LEACH.In the advertisement phase, the CHs are elected first by using a threshold based on the suggested percentage of CHs in the network and the number of times a node has been a CH. The thresholdTn is computed as [8]
(1)Tn=P1−P∗rmod1/P0,,Ifn∈G,Otherwise.After all the nodes have become CH at least once, which is after1/P rounds, all the deployed nodes will be eligible again to be a CH for the second time. The elected cluster head will then broadcast an advertisement message through CSMA MAC protocol to the non-CH nodes for them to decide which cluster belongs to that particular node in that round. The cluster joining decision is based on the largest signal strength received from a CH, because it will take minimum energy for communication. However, there is a possibility for a non-CH node to receive two similar signal strengths from two CHs. In this case, it will choose a random cluster head between the two CHs. The non-CH node must send a cluster joining message to its cluster’s CH through the CSMA MAC protocol in the cluster set-up phase. Upon receiving the joining information of the nodes in its cluster, the CH then schedules a time slot for each node to transmit by using TDMA in order to avoid collision during the transmission period.After the aforementioned phases, the data transmission can commence. Data transmission is done over the sensor’s radio channel by using first order radio model [8] with certain characteristics, as shown in Table 2.Table 2
The radio characteristics and its values used in LEACH [8].
OperationEnergy dissipatedTransmitter electronic (ETx−elec)Receiver electronic (ERx−elec)(ETx−elec=ERx−elec=Eelec)50 nJ/bitTransmit amplifier (ϵamp)100 pJ/bit/m2The equations for the transmission phase are as such [8]
(2)ETxk,d=ETx−eleck+ETx−ampk,d,ETxk,d=Eelec∗k+ϵamp∗k∗d2.The equations for the receiving phase are as such [8]
(3)ERxk=ERx−eleck,ERxk=Eelec∗k.There are some assumptions taken into consideration in applying the first-order radio model which are (1) the radio channels are symmetric and (2) data are always sensed, which makes the system not an event-driven sensing type. An overview of the LEACH radio model is shown in Figure2 [8].Figure 2
First-order radio model used in LEACH [8].


## 3.1. Low-Energy Adaptive Clustering Hierarchy (LEACH)

The sensor nodes in WSNs cooperate with each other to detect a change in physical or environmental aspects. The sensed data are then collected and sent to a primary base location called BS, for the data to be observed and analyzed [31, 32].LEACH is made up of microsensors that are cheap and energy efficient, to achieve better quality results in large scale networks [8]. LEACH organizes itself by using adaptive clustering, cluster head rotation, and local computation in order to have a balanced energy distribution in the network. There were two assumptions made in this research, which are (1) the base station is stationary and located far away from the sensor nodes and (2) the sensors in the field are homogeneous and energy constrained. Recent research has also evaluated LEACH-based clustering in heterogeneous and mobile scenarios [13, 33]. LEACH consists of two important phases which are the set-up phase and the steady-state phase. The steady-state phase is longer in comparison to the set-up phase, the aim of which is to minimize overhead. Typically, in LEACH, the CH is selected first before the clusters are formed, but it is not the same for all the existing methods of clustering, as some researchers tend to improve the objectives by performing cluster formation first, such as [34]. The overview of LEACH is shown in Figure 1. In LEACH, the cluster head is selected first before the cluster is formed.Figure 1
The overview of LEACH.In the advertisement phase, the CHs are elected first by using a threshold based on the suggested percentage of CHs in the network and the number of times a node has been a CH. The thresholdTn is computed as [8]
(1)Tn=P1−P∗rmod1/P0,,Ifn∈G,Otherwise.After all the nodes have become CH at least once, which is after1/P rounds, all the deployed nodes will be eligible again to be a CH for the second time. The elected cluster head will then broadcast an advertisement message through CSMA MAC protocol to the non-CH nodes for them to decide which cluster belongs to that particular node in that round. The cluster joining decision is based on the largest signal strength received from a CH, because it will take minimum energy for communication. However, there is a possibility for a non-CH node to receive two similar signal strengths from two CHs. In this case, it will choose a random cluster head between the two CHs. The non-CH node must send a cluster joining message to its cluster’s CH through the CSMA MAC protocol in the cluster set-up phase. Upon receiving the joining information of the nodes in its cluster, the CH then schedules a time slot for each node to transmit by using TDMA in order to avoid collision during the transmission period.After the aforementioned phases, the data transmission can commence. Data transmission is done over the sensor’s radio channel by using first order radio model [8] with certain characteristics, as shown in Table 2.Table 2
The radio characteristics and its values used in LEACH [8].
OperationEnergy dissipatedTransmitter electronic (ETx−elec)Receiver electronic (ERx−elec)(ETx−elec=ERx−elec=Eelec)50 nJ/bitTransmit amplifier (ϵamp)100 pJ/bit/m2The equations for the transmission phase are as such [8]
(2)ETxk,d=ETx−eleck+ETx−ampk,d,ETxk,d=Eelec∗k+ϵamp∗k∗d2.The equations for the receiving phase are as such [8]
(3)ERxk=ERx−eleck,ERxk=Eelec∗k.There are some assumptions taken into consideration in applying the first-order radio model which are (1) the radio channels are symmetric and (2) data are always sensed, which makes the system not an event-driven sensing type. An overview of the LEACH radio model is shown in Figure2 [8].Figure 2
First-order radio model used in LEACH [8].


## 4. Nonmetaheuristic Method

Clustering in WSNs is categorized into two major methods, which are nonmetaheuristic and metaheuristic methods. These methods perform two key phases of clustering, namely, cluster head selection, and cluster formation. Figure3 describes the various methods used to perform cluster head selection and cluster formation based on several environmental settings.Figure 3
Taxonomy of clustering in WSNs.


### 4.1. Cluster Head Selection

CH selection is an important step in clustering as it has a big responsibility in WSNs to transfer data and aggregate data efficiently. In recent years, CH selection has been focused on many works of literature, because selecting the most accurate CH will enhance the entire lifetime and reliability of the network. In nonmetaheuristic methods, CH selections are solely based on selection criteria that are imposed for certain applications and environments. In this section, how various CH selection techniques are applied to different environment settings are described. Figure4 describes the environment settings and the related methods of CH selection.Figure 4
Taxonomy of cluster head selection using nonmetaheuristic methods.


#### 4.1.1. Mobility

In applications such as drone applications [3] and medical applications [4], the sensors are always mobile, where clustering is a much more difficult process because of frequent location changes, where frequent reclustering will deteriorate the entire energy level of the network quickly. This problem was tackled by some research that will be discussed below.In 2017, Khandnor and Aseri proposed a threshold distance-based clustering routing protocol taking into consideration both mobile and nonmobile environments in [13]. The method is based on LEACH as it is called LEACHDistance for the static environment and LEACHDistance-M for the mobile environment. CH selection criteria in this protocol are split according to the static and mobile scenario. In a static setting, the upper threshold distance, lower threshold distance, and remaining energy of the node are taken into consideration. On the other hand, in a mobile setting, an extra criterion of low velocity of node (least mobile node) is given attention so that the CH can efficiently communicate with its members. During simulations, LEACHDistance-M performed better than the LEACHDistance and other methods that were compared in terms of network lifetime, correlation, coefficiency, scalability, number of data packets received by the BS, and energy efficiency.The authors in [34] proposed a distributed fuzzy logic-based cluster head selection algorithm (DFLBCHSA) to maximize the network energy efficiency and to minimize the delays in packet delivery. In the network, 3 types of components are identified which are static sensor nodes, mobile gateway, and static base station. The mobile gateway consists of sensors that act as a transportation system, where the data from the CH are delivered to the BS by them. This makes it crucial to have an accurate CH selection mechanism, where the authors introduce two designs of selection criteria that are merged with the use of a fuzzy-based inference system. The two designs are the general state of a sensor node in the WSN (GSoSN) and the location of a sensor node relative to mobile gateway nodes (LoSNRtMG). In GSoSN, the criteria are residual energy, several neighbors, and mean distance between the sensor and its neighbor nodes; while in LoSNRtMG, four parameters are focused on within the transmission range, which are several gateways, distance from the nearest gateway, distance from the most faraway gateway, and the mean distance between a sensor node and gateways. In the simulation outcome, it was observed that DFLBCHSA performed well in terms of a lesser number of dead sensor nodes, higher average remaining energy, and lesser delay in packet transfer.Since the nodes keep moving, the topology keeps changing dynamically. To overcome this problem, the authors in [35] proposed an algorithm named robust, energy-efficient weighted clustering algorithm (RE2WCA). In this research, the authors focus on selecting a CH based on residual energy and group mobility, as it reduces the number of reclustering dramatically. A periodic fault detection protocol and spatial dependency with CH as CHSD hybridized with weight model are introduced to select CHs in the following rounds depending on mobility, to select a CH with reduced energy consumption and increased reliability. From the simulation carried out, the throughput, lifetime, and robustness of the network were found to be better compared to other protocols.The authors from [36] proposed a cluster manager-based cluster head selection (CMBCH) scheme to reduce the workload of the CH. In this literature, the cluster formation phase is carried out first followed by cluster manager selection and CH selection. The elected cluster manager tends to hold the backup details of the CHs, where it reduces the memory capacity limitation problem faced by CHs in a mobile environment. During the reclustering phase, the cluster manager chooses the next CH in terms of residual energy and distance of the CH to the other nodes. The authors also claimed that CMBCH is more energy-efficient and has a higher packet delivery ratio compared to other existing methods in the industry, based on their simulations.In the year 2020, the authors from [37] proposed a CH selection method based on a mobile sensor environment named energy-efficient mobility-based cluster head selection (EEMCS). In EEMCS, the cluster head is chosen based on residual energy, mobility, distance to the base station, and neighbors’ count, with the inclusion of weightage as below:
(4)Weightage=Er∗w1+Degree∗w2ML∗w3+DtoBS∗w4.EEMCS performed better in terms of network lifetime, energy consumption, average energy, and throughput when compared with several existing algorithms.There is still room for research and improvements in the mobile WSN environment, where the authors in [19] proposed the inclusion of two algorithms in two types of models namely, clustering and mobile routing with greedy approach (CMR), and clustering with artificial neural network and mobile routing with greedy approach (CNNMR). In both the models, the mobile sink route is calculated using a greedy approach. In CMR, the CH is selected based on the highest residual energy and closeness to the cluster center, while in CNNMR, the x and y coordinates and residual energy details are fed into the artificial neural network as inputs. Simulations showed that CMR and CNNMR exhibited a greater extension of network lifetime compared to other methods.


#### 4.1.2. Multihop Data Transmission

Large- and medium-scale WSNs usually adapt to multihop data transmission, as long-range transmission may deteriorate the life of a sensor node. When CHs that are farthest from the BS aggregate the received data, they send this to another CH nearer to them until it reaches the BS. Various kinds of techniques exist to select proper CHs based on the multihop environment, as discussed below.Since hotspot and energy hole problem is crucial to be mitigated in the field of WSN. Sert et al. [38] were inspired to propose multiobjective fuzzy clustering algorithm (MOFCA) for WSN. The authors considered energy efficiency towards all types of scenarios and adaptability towards implementing on real sensors in both stationary and evolving networks. MOFCA considers 3 important parameters which are distance to sink, node remaining energy, and the node’s density to select the optimal CH. The author also discusses that it does reduces the energy hole problem as it does not need a central decision node for the CH selection process. The simulation focuses on 4 scenarios with varieties of sink location and node distribution. All 4 scenarios are evaluated in respect to direct transmission or multihop routing to the sink. The simulation results show that the proposed method reasonably outperformed several existing approaches in terms of total remaining energy.The authors in [39] proposed an optimal cluster head selection method for defending gray hole and black hole attacks in WSNs. The method is based on LEACH, and it is known as LEACH-Attack Defense (LEACH-AD). Gray hole attacks are where malicious nodes block the passage of the packets in the network, while black hole attacks are where the trustworthiness is exploited to route the packets to the wrong path. These problems are tackled by implementing a good CH selection technique in a multihop data transfer environment, where a CH is selected by detecting the nodes that are already compromised and choosing the node with maximum energy from the noncompromised node, for a better lifetime of the network. The proposed technique is noted to perform better against the attacks compared to existing techniques in terms of packet delivery ratio (PDR), throughput, and end-to-end delay at several intervals.Later in the year 2016, Gawade and Nalbalwar in [40] proposed a technique to balance the energy consumption of nodes and to increase the network lifetime, namely, the centralized energy-efficient distance-based routing protocol (CEED). In the literature, the optimum number of clusters is determined by the energy dissipated by the entire network first; then, the probability of the node to become CH is determined, followed by CH selection and cluster formation. The authors also discuss the multihop routing scheme to transmit the data as it greatly preserves the energy of CHs that are far away from BS. From the simulation, it was shown that CEED is more energy-efficient than other protocols that were compared with it.The authors in [41] proposed a fuzzy logic-based cluster head selection method in two tiers called multitier algorithm (MAP). The CH is selected by using fuzzy logic based on three parameters, which are residual energy, centrality, and communication cost. Few primary nodes are then selected to help the CH transmit the data to the BS. The data transmission in this literature is also divided into parts, wherein the tier one sensed data are aggregated by the CH and sent to the primary node, which is then later sent to the BS (single-hop data transmission); whereas in tier two, the primary node, upon receiving the data from the CH, finds and transmits the data to another primary node that is nearer, to reduce energy consumption over long data transmission (multihop data transmission). From the simulation, the authors conclude that the usage of fuzzy logic has made the nodes evenly involved in data transmission, which makes it more energy-efficient and increases the network lifetime.In 2017, Luo and Xiong in [12] conducted design and analysis on the energy balance clustering technique (EBC). The CH is selected by using an improved threshold value, where the energy level of nodes and distance to sink are considered. The authors considered using multihop communication in the research as it can reduce energy consumption. In this case, the CH near the sink will die quickly due to heavy traffic loads. So, the usage of the relay node is introduced to overcome the hotspot problem. EBC yielded better performance in terms of the number of messages received and average energy consumption, as compared to existing protocols.The authors in [42] proposed a technique for selecting CHs based on residual energy, neighbor degree, and distances among CHs, named as the fixed competition-based clustering approach (FCBA). In FCBA, a hello message is sent to explore the neighborhood, and then, each node calculates and distributes its weight; the node that has the smallest weight becomes the CH, and the other nodes settle down to become the member nodes. The authors implemented this technique in a multihop environment and compared it with several existing techniques. The proposed technique seems to be effective in balanced energy consumption and improving network lifetime.Sert et al. in the year 2018 were inspired to propose another method to overcome poor data aggregation problems in multihop WSN-efficient called two-tier distributed fuzzy logic-based protocol (TTDFP) [43]. TTDFP has two tiers where tier 1 selects the optimal CHs by considering parameters such as residual energy, distance to BS, and relative node connectivity while in tier 2 the optimal routing is done by the fuzzy routing protocol by considering the average residual energy and relative distance parameters. The author discussed that the energy efficiency, scalability, and optimized run-time configuration are focused on tier 1 while energy efficiency and computational simplicity in tier 2. The authors used SA algorithm as the optimization approach to test TTDFP. The simulations are done in 2 scenarios to ensure the proposed protocol can perform well in various situations. Scenario 1 is based on fuzzy clustering tier where in case A, the sink is located outside of service area, and in case B, the sink is in the service area. Scenario 2 on the other hand focuses on the fuzzy routing tier where in case A, multihop routing is employed and in case B, proposed fuzzy routing scheme is employed. The results show that TTDFP outperformed several existing protocols in terms of energy efficiency and scalability.Since the centralized-based clustering technique may take more time and effort and affects the scalability to form clusters, the authors in [44] proposed an energy-efficient load-balanced clustering scheme based on the distributed approach in a multihop environment. This method selects the CH based on the highest candidate weighted score as shown below:
(5)Candidateweight=Er+ni.The author discusses the deployment of the relay node [12] on solving the hotspot problem. The proposed method was compared to LEACH, and through simulations, it was found to perform better in terms of the long lifetime of the network.The authors in [45] proposed the selection of cluster heads dynamically for monitoring in WSNs, using an efficient target tracking approach termed as ETTA. In ETTA, four CHs that are at the edge of the clusters are chosen and the clusters are further divided into four subareas. A collecting cluster head (CCH) is selected, making it a multihop data transmission environment, where it collects the data from CHs, aggregates, and sends it to the BS, which greatly reduces the data gathering costs. The CCH is typically chosen based on the residual energy and lowest distance to the sink. From the simulation, it was proven that ETTA outperformed the state-of-the-art approaches by having a better network lifetime and lower energy consumption.Some researchers prefer to modify LEACH in WSNs, where the authors in [46] introduced a modified LEACH algorithm (LEACH-M). LEACH-M utilizes the network address and residual energy in selecting the best CH to tackle the unreasonable cluster head selection. Moreover, a cluster head competitive mechanism is integrated into LEACH-M, where the average energy Eaver is calculated and the current residual energy Eres of a node is compared with it to select the CH. This technique prevents nodes from running out of energy quickly and maintains the WSN structure for a longer period compared to some exiting methods.Priyadarshini and Sivakumar proposed a cluster head selection technique based on minimum connected dominating set with multihop information (MCDS-MI) and bipartite graph (BG) in WSNs [47]. Initially, a set of the minimum number of nodes with the highest energy and coverage is chosen as dominators, and then, the CH is chosen from the dominators, but the head dominator might fail due to environmental changes. So, a virtual dominator (VD) is created to act as a CH from Steiner tree construction, to reduce the complexity. Furthermore, the VD interchanges the message with nodes and other clusters and reaches the BS at a faster rate. From the simulations, it was observed that the proposed method enhanced the network lifetime by having a load-balanced network.The usage of fuzzy based methods was demanding because of its advantage of performing optimally on widespread WSN optimization. So, Sert and Yazıcı [48] proposed a rule-based fuzzy routing algorithm by utilizing the modified clonal selection algorithm (CLONALG-M) where they used it to modify previously proposed method [43]. To achieve 2% improvement, the cells are created, assigned to population, and iterated without reaching stopping criteria. CLONALG-M is used to ensure the validity measures of fuzzy function are satisfied. After data collection, the authors described 2 data routing protocols called TTDFP and fuzzy path selection (FPS) which are then modified with CLONALG-M for optimality. The routing from the leaf node to CH is by single hop while data transfer from CH to BS is by multihop model. Both the modified approaches are tested and compared with its nonmodified version, and the results shows that the modified fuzzy functions using our CLONALG-M algorithm is more energy efficient and performs better.The authors in [49] proposed a hierarchical topology control algorithm named double cluster heads and multihop based on affinity propagation clustering (APDC-M) in the year 2019. Affinity propagation (AP) clustering algorithm is an unsupervised algorithm that finds the clustering centers by using information iteration of data points, and it is deemed to have fast convergence under less constraint. The CH is selected based on residual energy, and by looking at the burden of the CH to aggregate the data and sending it to the BS, a second CH is elected in the literature to transmit the data to the BS. A multihop path is also constructed with the use of the shortest path algorithm to reduce energy usage during transmission. In simulations, APDC-M managed to make a uniform cluster distribution with reasonable cluster head election by minimizing the energy consumption in data transmission and enabling it to prolong the network lifetime.In the same year, Alami and Najid proposed an enhanced clustering hierarchy (ECH) approach to maximize the lifetime of WSNs in [50]. Initially, the sleeping and waking nodes are determined and the CH is selected randomly from waking nodes. The reselection of the CH uses residual energy and local distance as selection criteria. By implementing sleeping and waking nodes, the wastage of energy without transmission is reduced dramatically in a multihop network. However, it is not applicable for some applications that have consistent data transmission such as environmental sensing nodes. The proposed method managed to reduce the data redundancy of overlapping nodes and maximize the network lifetime compared to other existing protocols.In 2020, the authors in [51] proposed a many-objective optimization model in WSNs based on LEACH, which was termed as LEACH-ABF. There are four objectives considered in this model, which are cluster distance, the sink node distance, the overall energy consumption of the network, and the network energy consumption balance to select the cluster head. Balance function strategy, genetic operation, and penalty-based boundary intersection selection strategy (PBI) are introduced to achieve the true Pareto front, to have better search capabilities, and to enhance convergence and diversity, respectively. The whole network was also designed based on the multihop model and tested with the DTLZ test suite, which showed that LEACH-ABF has better distribution and convergence as well as balanced energy consumption compared to some existing multiobjective algorithms.Later in the same year, the authors from [52] proposed a simplified clustering and improved intercluster cooperation method in WSNs, namely, energy balanced clustering routing (EBCR). During the clustering phase, the BS will sort the nodes in descending order of energy, and the first 10% of the nodes will become CHs initially. For data transmission, the location information is used by the sink to sort the nodes in descending order of distance from the sink, to determine the next hop of the CH farthest from the BS on a multihop basis. In this paper, a good parameter study is done on several CHs and intercluster routing methods based on 4 scenarios. The simulation showed that EBCR has better balanced energy usage in the energy harvesting scenario and a better lifetime in the nonenergy harvesting scenario.Looking at the advancements of using the CLONALG-M algorithm, the authors of [53] proposed on applying the algorithm to the membership function of cluster head election using fuzzy logic (CHEF) and MOFCA [38] to increase the energy efficiencies. The proposed methods are simulated in 3 different scenarios for better understanding of its optimality. In scenario 1, a smaller network dimension with small number of sensors is deployed, the size of the network is increased to test optimality in large network sizes in scenario 2 and in scenario 3, a large network size with a large number of sensors is deployed. The CLONALG-M algorithm is compared against the well-known GA where the CLONALG-M algorithm outperformed GA in all three scenarios.


#### 4.1.3. Single-Hop Data Transmission

Even though multihop transmission may seem to be likely the best option to transmit data, it still has the limitation that is called a hotspot problem. In the hotspot problem, the nodes that are placed near the BS die quickly, as many CHs that are far transmit data to the CH that is nearer to the BS, making it have a high traffic load, resulting in more energy consumed. As such, some researchers consider this issue and implement CH selection in a single-hop environment.The authors from [16] proposed an energy-efficient clustering scheme to prolong the network lifetime. The authors focused closely on traditional LEACH protocol and implemented a regional energy-aware clustering method with isolated nodes (REAC-IN). Isolated nodes are considered as one of the problems faced by clustering, where some nodes do not join any cluster and tend to transfer data directly to the BS due to random selection of the CH. Given the issue, the CH selection in this approach is done based on residual energy and regional average. The authors later discuss the data transmission of the occurring isolated node where it uses a first-order radio model, where it is still possible for the isolated nodes to exist. In a comparison of REAC-IN with LEACH and other clustering algorithms, REAC-IN performed better in terms of network lifetime and stability of the network.In the year 2019, the authors in [54] proposed two CH selection techniques which are energy- and distance-based cluster head selection (EDB-CHS) and EDB-CHS with balanced objective function (EDB-CHS-BOF). The authors considered that the cluster area has a hexagonal shape which is near to the reality in a single hop data transfer model. For the CH selection, a threshold probability is created by ensuring that the node with higher residual energy, lesser energy consumption, and the shortest distance between the sensor node and the BS is selected. In the second technique, the objective function is added to select better CHs by including the expression of node optimal probability. EDB-CHS-BOF performed better than EDB-CHS and other protocols in terms of network lifetime, balanced energy consumption, and total data delivery.Another closely LEACH referred method was introduced by the authors of [55]. The proposed method has the inclusion of selectivity function-based CH selection (SF-CHs) algorithm to select optimal CH and clustering in ubiquitous power Internet of Things (IoT). Selectivity function maxZ is implemented as below:
(6)maxZ=λ1×Er+λ2×ni+λ3×vi+λ4×ωr,where λ1+λ2+λ3+λ4=1 and λ3<0. The cluster data transmission is also discussed, where a spreading code is used by CHs to reduce the intercluster interference. From the comparison of SF-CHs, LEACH, and other protocols, SF-CHs performed better in terms of stable network and enhanced network lifetime.Dwivedi and Sharma proposed a fuzzy-based energy-efficient clustering approach (FEECA) to prolong the network lifetime in WSNs [56]. In this literature, two scenarios are considered. In scenario 1 (S1), the BS is located in the center of the network, and in scenario 2 (S2), the BS is located at the edge of the network. In FEECA, three selection criteria are considered which are residual energy, average communication distance, and communication quality. These criteria are then run through a fuzzy inference system (FIS) to select proper CHs. Data routing in the network scenarios considers single-hop data transmission for clusters near the BS, while clusters that are far away send data to the BS through the master node. From the simulations, it was observed that FEECA enhances the network lifetime and also has better throughput compared to existing algorithms.The energy consumption problem in WSNs has been researched until recently, as Pour and Javidan proposed a new energy-aware cluster head selection method for LEACH (DRE-LEACH) in [57]. Four CH selection criteria are imposed in this method, namely, residual energy, the distance between nodes and sink, the nodes centrality, and the number of neighbors of each node. A threshold value is calculated by the ratio of the number of CH with the number of alive nodes, where it is ensured that a node becomes CH only when the threshold value is below 0.05, to control the number of CHs that exist in the network at one time. DRE-LEACH outperforms other existing LEACH-based protocols in terms of network lifetime and reliability.


#### 4.1.4. Heterogeneity

Heterogeneity in WSNs is where the sensor nodes that are in the network have different abilities in terms of different amounts of energy levels and sensing ranges [58]. Some research promotes a heterogeneous environment as it greatly improves the energy efficiency and reliability of an application by selecting a CH with better ability.In 2016, the authors of [59] proposed a method with 4 variants namely, balanced energy-efficient network-integrated super heterogeneous (BEENISH), improved BEENISH (iBEENISH), mobile BEENISH (MBEENISH), and improved mobile BEENISH (iMBEENISH) protocols. The research was carried out on heterogeneous nodes in two different environmental settings, with sink mobility and without sink mobility. In this setup, four types of nodes exist with different initial energies namely, ultrasupernode, supernode, advanced node, and normal node. CH selection in BEENISH is based on the residual energy and the average energy level of the network, where the ultrasupernodes have a higher frequency to become CHs as they have the highest amount of residual energy. In improved BEENISH, absolute residual energy Tabsolute is used to determine the CH when all the higher energy nodes have become equal to a normal node, to obtain a longer stability period:
(7)Tabsolute=zE0,where z=0.71 (after running simulations many times). To obtain more energy efficiency from the network, both BEENISH and iBEENISH are equipped with sink mobility. From the simulations, it was concluded that iBEENISH performs better than BEENISH in terms of network lifetime and throughput. Moreover, it was also found that the mobile sink versions can achieve the desired objectives which make them perform better than the nonmobile sink versions.The authors in [60] proposed an energy-coverage ratio clustering protocol (E-CRCP) to be used in heterogeneous energy network environments. In this, the optimal numbers of clusters are determined first by calculating the total energy used in communication. Next, the CH is selected based on the maximum coverage ratio, so that the CHs are evenly distributed throughout the network. Then, the CH that consumes a large amount of energy is replaced in the next communication iteration. Comparing E-CRCP with other existing protocols showed that E-CRCP improves network lifetime, balances the network load, and reduces the energy consumption in heterogeneous WSNs.The authors of [61] proposed an energy-efficient scheme for heterogeneous WSNs. A multicriteria decision-making technique is included in the scheme, named as a technique for order of preference by similarity to ideal solution (TOPSIS). This scheme comprises of few phases such as the CH declaration phase, node association phase, CH-acquaintanceship phase, and CH-friendship phase. In the CH declaration phase, it is ensured that the resources such as residual energy, computational capability, and storage capacity are higher than the threshold values. In the node association phase, the decision of the child nodes in joining the clusters is based on TOPSIS. CH-acquaintanceship and CH-friendship are used to help CHs with low resources do their tasks to balance the energy usage and minimize packet drops. From the simulation, it was observed that the proposed method extends network lifetime and minimizes the reclustering frequency in a heterogeneous environment.Narayan and Daniel proposed a cluster head selection technique based on trust function in a very recent paper [62]. In this research, the authors deployed two types of nodes which are advanced and normal nodes, where the advanced nodes have higher energy levels compared to normal nodes, creating a heterogeneous environment. Firstly, the CHs are selected based on new threshold values that consist of distance ratio and weighted energy, to reduce the energy failure problem. Random selection of CHs is also avoided. Then, the trust function is used to preserve the accuracy of data in the data fusion method. The proposed protocol has shown better network lifetime and stability compared to an existing protocol in a heterogeneous environment.


#### 4.1.5. Other Parameters

Some research which are based on different network sizes, usage of weights and coefficients in CH selection, and usage of CH rotation methods are categorized in this section. There are also certain pieces of literature with no significant environmental changes. Below is some literature discussed briefly, that was carried out in a homogeneous and static network.The stochastic control problems are modelled based on semi-Markov decision processes (SMDPs) by allowing the state transitions to occur in continuous irregular times [63]. In the year 2018, Amuthan and Arulmurugan got inspired by semi-Markov and proposed a hybrid trust prediction scheme through reliable CH selection in WSNs named hyperexponential reliability factor-based cluster head election (HRFCHE) [64]. HRFCHE is aimed at minimizing the number of CHs while increasing the number of rounds in implementation by using the energy and trust factor. A CH is chosen through hyperexponential reliability factor to obtain a more energy-balanced CH. From the simulations, it was observed that the proposed method performs better than LEACH in terms of energy consumption and improves the network lifetime.Zahedi proposed a clustering protocol that is closely related to LEACH by applying weighting coefficients termed (CWC) in [65]. The main difference of the proposed algorithm compared to LEACH is that it uses weighted residual energy and distance from sink threshold to select the appropriate CH. In this literature, the clusters are formed first and then the suitable CHs are chosen for each cluster. Two scenarios are considered in terms of smaller and slightly bigger network dimensions in this research. From the comparison, it was observed that CWC shows dominance in terms of global performance compared to some exiting methods.Following the trend of using coefficients in CH selection, Turgut proposed a method called dynamic coefficient-based adaptive cluster head selection (DCoCH) in WSNs [66]. The selection criteria that are used to select CHs are the residual energy of the nodes, the intracluster communication cost, and the number of neighbors. The coefficients applied are dynamically changed from 1st round to FND, then to HND, and finally to LND. DCoCH outperformed two other adaptive-based CH selection methods in terms of prolonging network lifetime.The authors in [67] proposed another network lifetime prolonging method named improved energy-efficient clustering protocol (IEECP). In IEECP, first, the optimal numbers of balanced clusters are determined by using a mathematical model and the modified fuzzy C-means algorithm (M-FCM), which considers the overlapping case and multihop communications. Then, CH selection and CH rotation are introduced by integrating the back-off timer called (CHSRA). The backoff timer is used in the CH selection phase as it reduces the overheads of the nodes. Moreover, during the cluster rotation phase, the unbalanced energy consumption problem is tackled by threshold values using the energy consumed and the ratio from the initial energy. From the evaluation, it was observed that the proposed method performed better compared to some existing methods in terms of balanced energy consumption and improved network lifetime.Since cluster head rotation yields good results, the authors from [68] proposed a nonthreshold-based cluster head rotation scheme (NCHR) for IEEE 802.15.4 cluster-tree networks. Initially, the CH is chosen randomly as it is done in LEACH, and then, the NCHR is applied to ensure that the next CH is selected only if the cluster lifetime can be enhanced based on residual energy and hop count. The author also discusses that NCHR can be used in an environment that has dynamic topology and node heterogeneity and also handles CH failures. The NCHR mechanism performed better than some existing mechanisms, where it is highly scalable because of the multihop data transmission enabled, in addition to having a better network lifetime.


### 4.2. Cluster Formation

When we talk about CH selection, it automatically drives us to the cluster formation phase for hierarchical clustering. The ever-growing use of sensors in many applications drives the research more into CH selection methods as well as cluster formation methods. Cluster formation can be done before CH selection or after CH selection, depending on the objectives and applications that the network is used in. Cluster formation techniques help to reduce the hotspot problem in WSN deployments. This section will discuss several cluster formation techniques using nonmetaheuristic methods introduced by some researchers in recent years, as outlined in Figure5.Figure 5
Taxonomy of cluster formation with nonmetaheuristic methods.Unequal clustering (UC) is a clustering algorithm that acts as a direct solution to the hotspot and blind spot problem, as discussed in [69–71]. Unequal clustering is where the clusters near the BS are smaller and have lesser nodes than clusters far away from the BS, as visualized in Figure 6.Figure 6
Unequal clustering [72].In 2016, Gupta and Pandey proposed an improved energy-aware distributed unequal clustering protocol (EADUC) in a heterogeneous and multihop environment [69]. Improved EADUC considers several neighbors, the distance between the nodes and the BS, and the residual energy, while deciding the competition radius for the cluster formation. The proposed method was then tested with three scenarios where the nodes were uniformly deployed in scenario 1, and the nodes were nonuniformly deployed and grouped to the right and left in scenarios 2 and 3, respectively. In [70], the blind spot problem is tackled, as events are not captured due to dead nodes by using unequal clustering. In the proposed method, the unequal clusters are formed by cognitive partitions to ensure equal energy consumption in each cluster. The authors of [71] proposed an unequal clustering protocol for energy harvesting sensor networks (UCEH). In the energy harvesting application, the multihop routing strategy is adopted, creating a hotspot problem. As such, unequal clustering based on the location of nodes, field area, coordinates of BS, and distance from nodes to BS is implemented. From simulations, all the unequal clustering methods researched by the aforementioned authors showed improvements when balancing the energy consumption and increased the network lifetime compared to some existing methods.K-means clustering is another clustering algorithm that is widely used in certain applications of WSNs, as discussed in [73–75]. K-means clustering is where clusters are formed from the k number of centroids that are determined manually, as visualized in Figure 7.Figure 7
K-means clustering [79].The authors in [73] proposed a modified k-means (Mk-means) algorithm to choose the best centroid and form clusters. In this literature, a k value of 3 is used, so only 3 clusters are formed, which might limit scalability. Upon determining the 3 centroids, multiple iterations are carried out until the establishment of the optimum means, and then the final CH selects 2 more CHs that are nearer to it to load, share, and minimize the energy consumption of a single CH. In the year 2020, the authors of [74] proposed a lifetime-enhancing cooperative data gathering and relaying algorithm (LCDGRA) that could be used in event-driven monitoring applications. In LCDGRA, Huffman entropy coding is adopted in K-means clustering, as it ensures that the sensor node’s transmission distance and energy consumption are optimized during the clustering phase. Besides, in [75], the authors proposed a nonuniform clustering routing algorithm based on an improved K-means algorithm. In the proposed method, a clustering point selection method is added to reduce the randomness of centroid selection based on a threshold function. The threshold function is created based on several neighboring nodes and a reduced number of iterations to avoid blind iterations and to find the centroid quickly. From the simulations of the aforementioned research, it can be seen that the K-means method shows better performance in terms of reduced energy consumption, balanced network, and enhanced network lifetime.Baniata and Hong proposed energy-efficient unequal chain length clustering (EEUCLC) in [18]. EEUCLC consists of 3 important phases which are CH selection, chain formation, and data collection and transmission. In the CH selection phase, the CH is selected based on residual energy and distance of the node to the BS. The clusters are then formed and intracluster communication chains built, where the intracluster chains nearer to the BS are shorter compared to those farther away. The purpose of building an intracluster chain is to reduce the communication traffic at the CH. The results of the simulation show that EEUCLC enhanced the lifetime and balanced the energy consumption compared to LEACH and the other two methods.In [76], the authors proposed an energy-efficient clustering routing protocol based on a high-QoS node deployment with an intercluster routing mechanism (EECRP-HQSND-ICRM) in WSNs. This method introduces a 2-fold coverage-based node deployment strategy as shown in Figure 8. To have an even distribution of CHs in the network, the BS first acts as a center and divides the area into four small cells, where each cell selects a CH based on residual energy and distance from the node to the BS, creating a selection factor SCHEi,dtoBSi as follows:
(8)SCHEr,DtoBS=α.NorEr+β.NorDtoBS,where α+β=1 (weight factors) and Nor represents the normalization. From the simulation, it is known that EECRP-HQSND-ICRM has high coverage, information integrity, and validity.Figure 8
2-fold coverage-based model [76].The authors in [77] proposed a hybrid optimal-based cluster formation (HOBCF) algorithm. A chemical reaction model (CHRA) is adopted for cluster formation in this paper, but it gives a lesser network lifetime. So, Lagrangian relaxation and entropy model are hybridized alongside multihop transmission, which is developed to enhance the network lifetime. The Lagrangian relaxation model identifies an optimal value of the node to form a cluster based on average neighbor distance, distance to reach the BS, energy, and available bandwidth. CHRA and HOBCF were tested with 3 different, scenarios where each scenario had a different duration of the mobility model. Simulation results show that HOBCF performed better than CHRA.A cluster formation technique named grid clustering was researched by the authors in [78]. It is based on a fuzzy reinforcement learning-based energy-efficient data aggregation scheme. Initially, with two stages, the network is divided into several grid cells. In stage 1, similar rectangular lanes are created with width and height, whereas in stage 2, the created rectangular lanes are broken down further into unequal smaller lanes based on the distance between rectangular lanes and the sink. Then, each grid elects a CH based on the residual energy factor. The fuzzy reinforcement learning algorithm is used to select the data aggregator using certain parameters, to ensure the selection of a robust aggregator. The simulations show that the proposed scheme performed better in terms of reliability and energy consumption of the network.


### 4.3. Parameter and Environmental Setting Analysis of Nonmetaheuristic Methods

The simulation parameters used and the environment settings from all the aforementioned techniques in nonmetaheuristic clustering are analyzed and compared in Table3.Table 3
The comparison analysis of simulation parameters and environmental settings of nonmetaheuristic clustering.
Paper (year)CH selectionCluster formationSelection criteriaData transmissionMobilitySensor typeNetwork dimensionNo. of nodesPacket lengthSensor initial energyLocation of BS[16](2015)REAC-IN—Residual energy and the regional average energySingle hopStaticHomogeneous200m×200m100-500—2 J(100, 100)[38](2015)MOFCA—Distance to BS, remaining energy, density, and competition radiusMultihopStaticHomogeneous200m×200m, 1000m×1000m100500 bytes1 J(250, 250), (100, 100), (500, 500), (1250, 1250)[39](2016)LEACH-AD—EnergyMultihopStaticHomogeneous1500m×1500m10, 50128 bytes1 J—[40](2016)CEED—Dissipated energy of a node and its distance to BSMultihopStaticHomogeneous100m×100m10062.5 bytes0.5 J(50, 350), (100, 300)[41](2016)MAP—Residual energy, centrality, and communication costMultihopStaticHeterogeneous100m×100m100250-500 bytes0.5-2 J(50, 50)[59](2016)BEENISH—The residual energy of nodes and average energy of the networkSingle hopMobile sinkHeterogeneous100m×100m100500 bytes0.5 J—[69](2016)—EADUCResidual energy, distance, number of neighbor nodesMultihopStaticHeterogeneous200m×200m100500 bytes0.5-1.5 J-250, 100[73](2016)—Mk-meansResidual energyN/SStaticHomogeneous100m×100m100250 bytes2 J(50, 175)[13](2017)LEACH-Distance-M—Upper threshold distance, lower threshold distance, remaining energy, and least mobility.MultihopMobileHomogeneous100m×100m10-100—0.5 J(50, 50)[12](2017)EBC—Sensor nodes’ energy level and distance to the sink.MultihopStaticHomogeneous400m×400m200—2 J(200, 200)[42](2017)FCBA—Energy, degree, and distanceMultihopMobileHomogeneous100m×100m50-200—15 J(50, 50)[18](2017)—EEUCLCResidual energy and distance to BSMultihopStaticHomogeneous(0m×0m)-(400m×400m)150250 bytes1 JOutside the network[43](2017)TTDFP—Distance to BS, remaining energy, relative node connectivity, and competition radiusMultihopStaticHomogeneous1000m×1000m100500 bytes1 J(1250, 1250), (500, 500)[35](2018)DFLBCHSA—Residual energy, number of neighbors, number of gateways, most faraway gateway, and distanceN/SMobile gatewayHomogeneous350m×350m100500 bytes0.35 J—[36](2018)RE2WCA—Residual energy and group mobilityMultihopMobileHomogeneous100m×100m50—2 J—[44](2018)Distributed clustering scheme—The residual energy of nodes and the number of their neighborsMultihopStaticHomogeneous100m×100m100—2 J(150, 50)[45](2018)ETTA—CH location and residual energyMultihopStaticHomogeneous200m×200m500-3000256 bytes100 JOutside the network[46](2018)LEACH-M—Residual energy and network address of nodesMultihopStaticHomogeneous(100m×100m), (300m×300m)50250 bytes2 J—[47](2018)MCDS-MIThe energy level and coverage degreeMultihopStaticHeterogeneous1000m×1000m500—N/S—[64](2018)HRFCHE—Energy and trust parameterN/SStaticHomogeneous100m×100m100500 bytes2 J—[65](2018)CWC—The residual energy of each node by applying weighting coefficients and distance from the sinkN/SStaticHomogeneous(50m×50m), (100m×100m)20, 40500 bytes0.1 J(25, 87.5), (50, 175)[70](2018)—Cognitive partition unequal clusteringResidual energy and cumulative distanceMultihopStaticHomogeneous200m×200m300500 bytes1 J(100, 50)[48](2019)TTDFP_ CLONALG-MFPS_ CLONALG-M—N/SMultihopStaticHomogeneous500m×500m100N/S1 JIn ROI[49](2019)APDC-M—Residual energyMultihopStaticHomogeneous100m×100m100502 bytes2 JOutside the network[50](2019)ECH—Energy and local distanceMultihopStaticBoth100m×100m1003000 bytesN/S(50, 50)[54](2019)EDB-CHS—Residual energy, distance, and node’s optimal probabilitySingle hopStaticHomogeneous(200m×200m), (300m×300m), (400m×400m)100625 bytes0.5 J-100, 300[55](2019)SF-CHs—Remaining energy, number of neighbors, motion velocity, and data transmission environmentSingle hopMobileHomogeneous100m×100m200, 300500 bytes1 JCenter of the network[60](2019)E-CRCP—Residual energy and coverage ratioN/SStaticHeterogeneous100m×100m100500 bytes0.5 J(50, 50)[76](2019)—EECRP-HQSND-ICRMResidual energy and distance of nodes from BSMultihopStaticHomogeneous100 m × 90 m91500 bytes0.5 J(50, 45)[34](2020)CMBCH—Energy and distanceMultihopMobileHomogeneous1200m×1200m20-100512 bytes5000—[37](2020)EEMCS—node’s mobility level, residual energy, distance to sink, and density of neighborsMultihopMobileHomogeneous(50m×50m), (100m×100m), (150m×150m), (200m×200m), (250m×250m)50, 100, 150, 200, 250500 bytes0.1 JOutside the network[51](2020)LEACH-ABF—Cluster distance, sink node distance, overall energy consumption, and network energy consumption balanceMultihopStaticHomogeneous100m×100m100500 bytes2 J(50, 50)[52](2020)EBCR—Residual energyMultihopStaticHomogeneous100m×100m991 bitN/S(100, 50)[56](2020)FEECA—Residual energy, communication quality, average distance of BSSingle hopStaticHomogeneous100m×100m100, 200375 bytes0.5 J, 1 J(50, 50), (150, 100)[61] (2020)TOPSIS—Residual energy, available storage, and computational capabilitySingle hopStaticHeterogeneous100m×100m100500 bytes6 J–10 J—[66] (2020)DCoCH—Intracluster communication cost, number of neighboring nodes, and remaining energyN/SStaticHomogeneous(100m×100m), (300m×300m), (400m×400m), (500m×500m)50, 100, 200, 300—0.5, 1, 2 JCenter, corner, outer 1, and 2 of network[67] (2020)IEECP—Energy consumed and the ratio from the initial energyMultihopStaticHomogeneous(100m×100m), (1000m×1000m)100, 1000400 bytes1 J(50, 125), (500, 1250)[71] (2020)—UCEHResidual energyMultihopStaticHomogeneous(0m×0m)-(200m×200m)100-400500 bytes0.5 J-100, 100[74] (2020)—LCDGRACommunication distances and residual energy metricsMultihopStaticHomogeneous100m×100m100100 bytes5 J(100, 50)[75] (2020)—NonuniformK-meansNumber of neighboring nodes, residual energy, and centroid of the clusterSingle hopStaticHomogeneous300m×300m300500 bytes0.5 J(150, 400)[77] (2020)—HOBCFDistance and energyMultihopMobileHomogeneous1000m×1000m500512 bytes100 JCenter of the network[78] (2020)—Grid clusteringResidual energy, distance, neighborhood overlap, and algebraic connectivityMultihopStaticHeterogeneous200m×200m20-500500 bytes0.5, 2, 200 J(100, 100), (100, 50), (200, 200)[19] (2021)CNNMR—Distance from the cluster centre and its residual energyN/SMobile sinkHomogeneous(90m×90m), (120m×120m)100, 200500 bytes2 J—[53] (2021)MOFCA_ CLONALG-MCHEF_ CLONALG-M—N/SMultihopStaticHomogeneous(100m×100m), (1000m×1000m)100, 1000500 bytes1 J(50, 50), (500, 500)[57] (2021)DRE-LEACH—Residual energy, the position, and centrality of nodesSingle hopStaticHomogeneous70m×70m100500 bytes0.5 J(35, 47.25)[62] (2021)Threshold CH selection—Residual energy and distance from BSMultihopStaticHeterogeneous150m×150m150—0.5 J(150, 75)[68] (2021)NCHR—Residual energy and distanceMultihopStaticBoth1000m×1000m71—1 J—∗N/S: not stated.


## 4.1. Cluster Head Selection

CH selection is an important step in clustering as it has a big responsibility in WSNs to transfer data and aggregate data efficiently. In recent years, CH selection has been focused on many works of literature, because selecting the most accurate CH will enhance the entire lifetime and reliability of the network. In nonmetaheuristic methods, CH selections are solely based on selection criteria that are imposed for certain applications and environments. In this section, how various CH selection techniques are applied to different environment settings are described. Figure4 describes the environment settings and the related methods of CH selection.Figure 4
Taxonomy of cluster head selection using nonmetaheuristic methods.


### 4.1.1. Mobility

In applications such as drone applications [3] and medical applications [4], the sensors are always mobile, where clustering is a much more difficult process because of frequent location changes, where frequent reclustering will deteriorate the entire energy level of the network quickly. This problem was tackled by some research that will be discussed below.In 2017, Khandnor and Aseri proposed a threshold distance-based clustering routing protocol taking into consideration both mobile and nonmobile environments in [13]. The method is based on LEACH as it is called LEACHDistance for the static environment and LEACHDistance-M for the mobile environment. CH selection criteria in this protocol are split according to the static and mobile scenario. In a static setting, the upper threshold distance, lower threshold distance, and remaining energy of the node are taken into consideration. On the other hand, in a mobile setting, an extra criterion of low velocity of node (least mobile node) is given attention so that the CH can efficiently communicate with its members. During simulations, LEACHDistance-M performed better than the LEACHDistance and other methods that were compared in terms of network lifetime, correlation, coefficiency, scalability, number of data packets received by the BS, and energy efficiency.The authors in [34] proposed a distributed fuzzy logic-based cluster head selection algorithm (DFLBCHSA) to maximize the network energy efficiency and to minimize the delays in packet delivery. In the network, 3 types of components are identified which are static sensor nodes, mobile gateway, and static base station. The mobile gateway consists of sensors that act as a transportation system, where the data from the CH are delivered to the BS by them. This makes it crucial to have an accurate CH selection mechanism, where the authors introduce two designs of selection criteria that are merged with the use of a fuzzy-based inference system. The two designs are the general state of a sensor node in the WSN (GSoSN) and the location of a sensor node relative to mobile gateway nodes (LoSNRtMG). In GSoSN, the criteria are residual energy, several neighbors, and mean distance between the sensor and its neighbor nodes; while in LoSNRtMG, four parameters are focused on within the transmission range, which are several gateways, distance from the nearest gateway, distance from the most faraway gateway, and the mean distance between a sensor node and gateways. In the simulation outcome, it was observed that DFLBCHSA performed well in terms of a lesser number of dead sensor nodes, higher average remaining energy, and lesser delay in packet transfer.Since the nodes keep moving, the topology keeps changing dynamically. To overcome this problem, the authors in [35] proposed an algorithm named robust, energy-efficient weighted clustering algorithm (RE2WCA). In this research, the authors focus on selecting a CH based on residual energy and group mobility, as it reduces the number of reclustering dramatically. A periodic fault detection protocol and spatial dependency with CH as CHSD hybridized with weight model are introduced to select CHs in the following rounds depending on mobility, to select a CH with reduced energy consumption and increased reliability. From the simulation carried out, the throughput, lifetime, and robustness of the network were found to be better compared to other protocols.The authors from [36] proposed a cluster manager-based cluster head selection (CMBCH) scheme to reduce the workload of the CH. In this literature, the cluster formation phase is carried out first followed by cluster manager selection and CH selection. The elected cluster manager tends to hold the backup details of the CHs, where it reduces the memory capacity limitation problem faced by CHs in a mobile environment. During the reclustering phase, the cluster manager chooses the next CH in terms of residual energy and distance of the CH to the other nodes. The authors also claimed that CMBCH is more energy-efficient and has a higher packet delivery ratio compared to other existing methods in the industry, based on their simulations.In the year 2020, the authors from [37] proposed a CH selection method based on a mobile sensor environment named energy-efficient mobility-based cluster head selection (EEMCS). In EEMCS, the cluster head is chosen based on residual energy, mobility, distance to the base station, and neighbors’ count, with the inclusion of weightage as below:
(4)Weightage=Er∗w1+Degree∗w2ML∗w3+DtoBS∗w4.EEMCS performed better in terms of network lifetime, energy consumption, average energy, and throughput when compared with several existing algorithms.There is still room for research and improvements in the mobile WSN environment, where the authors in [19] proposed the inclusion of two algorithms in two types of models namely, clustering and mobile routing with greedy approach (CMR), and clustering with artificial neural network and mobile routing with greedy approach (CNNMR). In both the models, the mobile sink route is calculated using a greedy approach. In CMR, the CH is selected based on the highest residual energy and closeness to the cluster center, while in CNNMR, the x and y coordinates and residual energy details are fed into the artificial neural network as inputs. Simulations showed that CMR and CNNMR exhibited a greater extension of network lifetime compared to other methods.


### 4.1.2. Multihop Data Transmission

Large- and medium-scale WSNs usually adapt to multihop data transmission, as long-range transmission may deteriorate the life of a sensor node. When CHs that are farthest from the BS aggregate the received data, they send this to another CH nearer to them until it reaches the BS. Various kinds of techniques exist to select proper CHs based on the multihop environment, as discussed below.Since hotspot and energy hole problem is crucial to be mitigated in the field of WSN. Sert et al. [38] were inspired to propose multiobjective fuzzy clustering algorithm (MOFCA) for WSN. The authors considered energy efficiency towards all types of scenarios and adaptability towards implementing on real sensors in both stationary and evolving networks. MOFCA considers 3 important parameters which are distance to sink, node remaining energy, and the node’s density to select the optimal CH. The author also discusses that it does reduces the energy hole problem as it does not need a central decision node for the CH selection process. The simulation focuses on 4 scenarios with varieties of sink location and node distribution. All 4 scenarios are evaluated in respect to direct transmission or multihop routing to the sink. The simulation results show that the proposed method reasonably outperformed several existing approaches in terms of total remaining energy.The authors in [39] proposed an optimal cluster head selection method for defending gray hole and black hole attacks in WSNs. The method is based on LEACH, and it is known as LEACH-Attack Defense (LEACH-AD). Gray hole attacks are where malicious nodes block the passage of the packets in the network, while black hole attacks are where the trustworthiness is exploited to route the packets to the wrong path. These problems are tackled by implementing a good CH selection technique in a multihop data transfer environment, where a CH is selected by detecting the nodes that are already compromised and choosing the node with maximum energy from the noncompromised node, for a better lifetime of the network. The proposed technique is noted to perform better against the attacks compared to existing techniques in terms of packet delivery ratio (PDR), throughput, and end-to-end delay at several intervals.Later in the year 2016, Gawade and Nalbalwar in [40] proposed a technique to balance the energy consumption of nodes and to increase the network lifetime, namely, the centralized energy-efficient distance-based routing protocol (CEED). In the literature, the optimum number of clusters is determined by the energy dissipated by the entire network first; then, the probability of the node to become CH is determined, followed by CH selection and cluster formation. The authors also discuss the multihop routing scheme to transmit the data as it greatly preserves the energy of CHs that are far away from BS. From the simulation, it was shown that CEED is more energy-efficient than other protocols that were compared with it.The authors in [41] proposed a fuzzy logic-based cluster head selection method in two tiers called multitier algorithm (MAP). The CH is selected by using fuzzy logic based on three parameters, which are residual energy, centrality, and communication cost. Few primary nodes are then selected to help the CH transmit the data to the BS. The data transmission in this literature is also divided into parts, wherein the tier one sensed data are aggregated by the CH and sent to the primary node, which is then later sent to the BS (single-hop data transmission); whereas in tier two, the primary node, upon receiving the data from the CH, finds and transmits the data to another primary node that is nearer, to reduce energy consumption over long data transmission (multihop data transmission). From the simulation, the authors conclude that the usage of fuzzy logic has made the nodes evenly involved in data transmission, which makes it more energy-efficient and increases the network lifetime.In 2017, Luo and Xiong in [12] conducted design and analysis on the energy balance clustering technique (EBC). The CH is selected by using an improved threshold value, where the energy level of nodes and distance to sink are considered. The authors considered using multihop communication in the research as it can reduce energy consumption. In this case, the CH near the sink will die quickly due to heavy traffic loads. So, the usage of the relay node is introduced to overcome the hotspot problem. EBC yielded better performance in terms of the number of messages received and average energy consumption, as compared to existing protocols.The authors in [42] proposed a technique for selecting CHs based on residual energy, neighbor degree, and distances among CHs, named as the fixed competition-based clustering approach (FCBA). In FCBA, a hello message is sent to explore the neighborhood, and then, each node calculates and distributes its weight; the node that has the smallest weight becomes the CH, and the other nodes settle down to become the member nodes. The authors implemented this technique in a multihop environment and compared it with several existing techniques. The proposed technique seems to be effective in balanced energy consumption and improving network lifetime.Sert et al. in the year 2018 were inspired to propose another method to overcome poor data aggregation problems in multihop WSN-efficient called two-tier distributed fuzzy logic-based protocol (TTDFP) [43]. TTDFP has two tiers where tier 1 selects the optimal CHs by considering parameters such as residual energy, distance to BS, and relative node connectivity while in tier 2 the optimal routing is done by the fuzzy routing protocol by considering the average residual energy and relative distance parameters. The author discussed that the energy efficiency, scalability, and optimized run-time configuration are focused on tier 1 while energy efficiency and computational simplicity in tier 2. The authors used SA algorithm as the optimization approach to test TTDFP. The simulations are done in 2 scenarios to ensure the proposed protocol can perform well in various situations. Scenario 1 is based on fuzzy clustering tier where in case A, the sink is located outside of service area, and in case B, the sink is in the service area. Scenario 2 on the other hand focuses on the fuzzy routing tier where in case A, multihop routing is employed and in case B, proposed fuzzy routing scheme is employed. The results show that TTDFP outperformed several existing protocols in terms of energy efficiency and scalability.Since the centralized-based clustering technique may take more time and effort and affects the scalability to form clusters, the authors in [44] proposed an energy-efficient load-balanced clustering scheme based on the distributed approach in a multihop environment. This method selects the CH based on the highest candidate weighted score as shown below:
(5)Candidateweight=Er+ni.The author discusses the deployment of the relay node [12] on solving the hotspot problem. The proposed method was compared to LEACH, and through simulations, it was found to perform better in terms of the long lifetime of the network.The authors in [45] proposed the selection of cluster heads dynamically for monitoring in WSNs, using an efficient target tracking approach termed as ETTA. In ETTA, four CHs that are at the edge of the clusters are chosen and the clusters are further divided into four subareas. A collecting cluster head (CCH) is selected, making it a multihop data transmission environment, where it collects the data from CHs, aggregates, and sends it to the BS, which greatly reduces the data gathering costs. The CCH is typically chosen based on the residual energy and lowest distance to the sink. From the simulation, it was proven that ETTA outperformed the state-of-the-art approaches by having a better network lifetime and lower energy consumption.Some researchers prefer to modify LEACH in WSNs, where the authors in [46] introduced a modified LEACH algorithm (LEACH-M). LEACH-M utilizes the network address and residual energy in selecting the best CH to tackle the unreasonable cluster head selection. Moreover, a cluster head competitive mechanism is integrated into LEACH-M, where the average energy Eaver is calculated and the current residual energy Eres of a node is compared with it to select the CH. This technique prevents nodes from running out of energy quickly and maintains the WSN structure for a longer period compared to some exiting methods.Priyadarshini and Sivakumar proposed a cluster head selection technique based on minimum connected dominating set with multihop information (MCDS-MI) and bipartite graph (BG) in WSNs [47]. Initially, a set of the minimum number of nodes with the highest energy and coverage is chosen as dominators, and then, the CH is chosen from the dominators, but the head dominator might fail due to environmental changes. So, a virtual dominator (VD) is created to act as a CH from Steiner tree construction, to reduce the complexity. Furthermore, the VD interchanges the message with nodes and other clusters and reaches the BS at a faster rate. From the simulations, it was observed that the proposed method enhanced the network lifetime by having a load-balanced network.The usage of fuzzy based methods was demanding because of its advantage of performing optimally on widespread WSN optimization. So, Sert and Yazıcı [48] proposed a rule-based fuzzy routing algorithm by utilizing the modified clonal selection algorithm (CLONALG-M) where they used it to modify previously proposed method [43]. To achieve 2% improvement, the cells are created, assigned to population, and iterated without reaching stopping criteria. CLONALG-M is used to ensure the validity measures of fuzzy function are satisfied. After data collection, the authors described 2 data routing protocols called TTDFP and fuzzy path selection (FPS) which are then modified with CLONALG-M for optimality. The routing from the leaf node to CH is by single hop while data transfer from CH to BS is by multihop model. Both the modified approaches are tested and compared with its nonmodified version, and the results shows that the modified fuzzy functions using our CLONALG-M algorithm is more energy efficient and performs better.The authors in [49] proposed a hierarchical topology control algorithm named double cluster heads and multihop based on affinity propagation clustering (APDC-M) in the year 2019. Affinity propagation (AP) clustering algorithm is an unsupervised algorithm that finds the clustering centers by using information iteration of data points, and it is deemed to have fast convergence under less constraint. The CH is selected based on residual energy, and by looking at the burden of the CH to aggregate the data and sending it to the BS, a second CH is elected in the literature to transmit the data to the BS. A multihop path is also constructed with the use of the shortest path algorithm to reduce energy usage during transmission. In simulations, APDC-M managed to make a uniform cluster distribution with reasonable cluster head election by minimizing the energy consumption in data transmission and enabling it to prolong the network lifetime.In the same year, Alami and Najid proposed an enhanced clustering hierarchy (ECH) approach to maximize the lifetime of WSNs in [50]. Initially, the sleeping and waking nodes are determined and the CH is selected randomly from waking nodes. The reselection of the CH uses residual energy and local distance as selection criteria. By implementing sleeping and waking nodes, the wastage of energy without transmission is reduced dramatically in a multihop network. However, it is not applicable for some applications that have consistent data transmission such as environmental sensing nodes. The proposed method managed to reduce the data redundancy of overlapping nodes and maximize the network lifetime compared to other existing protocols.In 2020, the authors in [51] proposed a many-objective optimization model in WSNs based on LEACH, which was termed as LEACH-ABF. There are four objectives considered in this model, which are cluster distance, the sink node distance, the overall energy consumption of the network, and the network energy consumption balance to select the cluster head. Balance function strategy, genetic operation, and penalty-based boundary intersection selection strategy (PBI) are introduced to achieve the true Pareto front, to have better search capabilities, and to enhance convergence and diversity, respectively. The whole network was also designed based on the multihop model and tested with the DTLZ test suite, which showed that LEACH-ABF has better distribution and convergence as well as balanced energy consumption compared to some existing multiobjective algorithms.Later in the same year, the authors from [52] proposed a simplified clustering and improved intercluster cooperation method in WSNs, namely, energy balanced clustering routing (EBCR). During the clustering phase, the BS will sort the nodes in descending order of energy, and the first 10% of the nodes will become CHs initially. For data transmission, the location information is used by the sink to sort the nodes in descending order of distance from the sink, to determine the next hop of the CH farthest from the BS on a multihop basis. In this paper, a good parameter study is done on several CHs and intercluster routing methods based on 4 scenarios. The simulation showed that EBCR has better balanced energy usage in the energy harvesting scenario and a better lifetime in the nonenergy harvesting scenario.Looking at the advancements of using the CLONALG-M algorithm, the authors of [53] proposed on applying the algorithm to the membership function of cluster head election using fuzzy logic (CHEF) and MOFCA [38] to increase the energy efficiencies. The proposed methods are simulated in 3 different scenarios for better understanding of its optimality. In scenario 1, a smaller network dimension with small number of sensors is deployed, the size of the network is increased to test optimality in large network sizes in scenario 2 and in scenario 3, a large network size with a large number of sensors is deployed. The CLONALG-M algorithm is compared against the well-known GA where the CLONALG-M algorithm outperformed GA in all three scenarios.


### 4.1.3. Single-Hop Data Transmission

Even though multihop transmission may seem to be likely the best option to transmit data, it still has the limitation that is called a hotspot problem. In the hotspot problem, the nodes that are placed near the BS die quickly, as many CHs that are far transmit data to the CH that is nearer to the BS, making it have a high traffic load, resulting in more energy consumed. As such, some researchers consider this issue and implement CH selection in a single-hop environment.The authors from [16] proposed an energy-efficient clustering scheme to prolong the network lifetime. The authors focused closely on traditional LEACH protocol and implemented a regional energy-aware clustering method with isolated nodes (REAC-IN). Isolated nodes are considered as one of the problems faced by clustering, where some nodes do not join any cluster and tend to transfer data directly to the BS due to random selection of the CH. Given the issue, the CH selection in this approach is done based on residual energy and regional average. The authors later discuss the data transmission of the occurring isolated node where it uses a first-order radio model, where it is still possible for the isolated nodes to exist. In a comparison of REAC-IN with LEACH and other clustering algorithms, REAC-IN performed better in terms of network lifetime and stability of the network.In the year 2019, the authors in [54] proposed two CH selection techniques which are energy- and distance-based cluster head selection (EDB-CHS) and EDB-CHS with balanced objective function (EDB-CHS-BOF). The authors considered that the cluster area has a hexagonal shape which is near to the reality in a single hop data transfer model. For the CH selection, a threshold probability is created by ensuring that the node with higher residual energy, lesser energy consumption, and the shortest distance between the sensor node and the BS is selected. In the second technique, the objective function is added to select better CHs by including the expression of node optimal probability. EDB-CHS-BOF performed better than EDB-CHS and other protocols in terms of network lifetime, balanced energy consumption, and total data delivery.Another closely LEACH referred method was introduced by the authors of [55]. The proposed method has the inclusion of selectivity function-based CH selection (SF-CHs) algorithm to select optimal CH and clustering in ubiquitous power Internet of Things (IoT). Selectivity function maxZ is implemented as below:
(6)maxZ=λ1×Er+λ2×ni+λ3×vi+λ4×ωr,where λ1+λ2+λ3+λ4=1 and λ3<0. The cluster data transmission is also discussed, where a spreading code is used by CHs to reduce the intercluster interference. From the comparison of SF-CHs, LEACH, and other protocols, SF-CHs performed better in terms of stable network and enhanced network lifetime.Dwivedi and Sharma proposed a fuzzy-based energy-efficient clustering approach (FEECA) to prolong the network lifetime in WSNs [56]. In this literature, two scenarios are considered. In scenario 1 (S1), the BS is located in the center of the network, and in scenario 2 (S2), the BS is located at the edge of the network. In FEECA, three selection criteria are considered which are residual energy, average communication distance, and communication quality. These criteria are then run through a fuzzy inference system (FIS) to select proper CHs. Data routing in the network scenarios considers single-hop data transmission for clusters near the BS, while clusters that are far away send data to the BS through the master node. From the simulations, it was observed that FEECA enhances the network lifetime and also has better throughput compared to existing algorithms.The energy consumption problem in WSNs has been researched until recently, as Pour and Javidan proposed a new energy-aware cluster head selection method for LEACH (DRE-LEACH) in [57]. Four CH selection criteria are imposed in this method, namely, residual energy, the distance between nodes and sink, the nodes centrality, and the number of neighbors of each node. A threshold value is calculated by the ratio of the number of CH with the number of alive nodes, where it is ensured that a node becomes CH only when the threshold value is below 0.05, to control the number of CHs that exist in the network at one time. DRE-LEACH outperforms other existing LEACH-based protocols in terms of network lifetime and reliability.


### 4.1.4. Heterogeneity

Heterogeneity in WSNs is where the sensor nodes that are in the network have different abilities in terms of different amounts of energy levels and sensing ranges [58]. Some research promotes a heterogeneous environment as it greatly improves the energy efficiency and reliability of an application by selecting a CH with better ability.In 2016, the authors of [59] proposed a method with 4 variants namely, balanced energy-efficient network-integrated super heterogeneous (BEENISH), improved BEENISH (iBEENISH), mobile BEENISH (MBEENISH), and improved mobile BEENISH (iMBEENISH) protocols. The research was carried out on heterogeneous nodes in two different environmental settings, with sink mobility and without sink mobility. In this setup, four types of nodes exist with different initial energies namely, ultrasupernode, supernode, advanced node, and normal node. CH selection in BEENISH is based on the residual energy and the average energy level of the network, where the ultrasupernodes have a higher frequency to become CHs as they have the highest amount of residual energy. In improved BEENISH, absolute residual energy Tabsolute is used to determine the CH when all the higher energy nodes have become equal to a normal node, to obtain a longer stability period:
(7)Tabsolute=zE0,where z=0.71 (after running simulations many times). To obtain more energy efficiency from the network, both BEENISH and iBEENISH are equipped with sink mobility. From the simulations, it was concluded that iBEENISH performs better than BEENISH in terms of network lifetime and throughput. Moreover, it was also found that the mobile sink versions can achieve the desired objectives which make them perform better than the nonmobile sink versions.The authors in [60] proposed an energy-coverage ratio clustering protocol (E-CRCP) to be used in heterogeneous energy network environments. In this, the optimal numbers of clusters are determined first by calculating the total energy used in communication. Next, the CH is selected based on the maximum coverage ratio, so that the CHs are evenly distributed throughout the network. Then, the CH that consumes a large amount of energy is replaced in the next communication iteration. Comparing E-CRCP with other existing protocols showed that E-CRCP improves network lifetime, balances the network load, and reduces the energy consumption in heterogeneous WSNs.The authors of [61] proposed an energy-efficient scheme for heterogeneous WSNs. A multicriteria decision-making technique is included in the scheme, named as a technique for order of preference by similarity to ideal solution (TOPSIS). This scheme comprises of few phases such as the CH declaration phase, node association phase, CH-acquaintanceship phase, and CH-friendship phase. In the CH declaration phase, it is ensured that the resources such as residual energy, computational capability, and storage capacity are higher than the threshold values. In the node association phase, the decision of the child nodes in joining the clusters is based on TOPSIS. CH-acquaintanceship and CH-friendship are used to help CHs with low resources do their tasks to balance the energy usage and minimize packet drops. From the simulation, it was observed that the proposed method extends network lifetime and minimizes the reclustering frequency in a heterogeneous environment.Narayan and Daniel proposed a cluster head selection technique based on trust function in a very recent paper [62]. In this research, the authors deployed two types of nodes which are advanced and normal nodes, where the advanced nodes have higher energy levels compared to normal nodes, creating a heterogeneous environment. Firstly, the CHs are selected based on new threshold values that consist of distance ratio and weighted energy, to reduce the energy failure problem. Random selection of CHs is also avoided. Then, the trust function is used to preserve the accuracy of data in the data fusion method. The proposed protocol has shown better network lifetime and stability compared to an existing protocol in a heterogeneous environment.


### 4.1.5. Other Parameters

Some research which are based on different network sizes, usage of weights and coefficients in CH selection, and usage of CH rotation methods are categorized in this section. There are also certain pieces of literature with no significant environmental changes. Below is some literature discussed briefly, that was carried out in a homogeneous and static network.The stochastic control problems are modelled based on semi-Markov decision processes (SMDPs) by allowing the state transitions to occur in continuous irregular times [63]. In the year 2018, Amuthan and Arulmurugan got inspired by semi-Markov and proposed a hybrid trust prediction scheme through reliable CH selection in WSNs named hyperexponential reliability factor-based cluster head election (HRFCHE) [64]. HRFCHE is aimed at minimizing the number of CHs while increasing the number of rounds in implementation by using the energy and trust factor. A CH is chosen through hyperexponential reliability factor to obtain a more energy-balanced CH. From the simulations, it was observed that the proposed method performs better than LEACH in terms of energy consumption and improves the network lifetime.Zahedi proposed a clustering protocol that is closely related to LEACH by applying weighting coefficients termed (CWC) in [65]. The main difference of the proposed algorithm compared to LEACH is that it uses weighted residual energy and distance from sink threshold to select the appropriate CH. In this literature, the clusters are formed first and then the suitable CHs are chosen for each cluster. Two scenarios are considered in terms of smaller and slightly bigger network dimensions in this research. From the comparison, it was observed that CWC shows dominance in terms of global performance compared to some exiting methods.Following the trend of using coefficients in CH selection, Turgut proposed a method called dynamic coefficient-based adaptive cluster head selection (DCoCH) in WSNs [66]. The selection criteria that are used to select CHs are the residual energy of the nodes, the intracluster communication cost, and the number of neighbors. The coefficients applied are dynamically changed from 1st round to FND, then to HND, and finally to LND. DCoCH outperformed two other adaptive-based CH selection methods in terms of prolonging network lifetime.The authors in [67] proposed another network lifetime prolonging method named improved energy-efficient clustering protocol (IEECP). In IEECP, first, the optimal numbers of balanced clusters are determined by using a mathematical model and the modified fuzzy C-means algorithm (M-FCM), which considers the overlapping case and multihop communications. Then, CH selection and CH rotation are introduced by integrating the back-off timer called (CHSRA). The backoff timer is used in the CH selection phase as it reduces the overheads of the nodes. Moreover, during the cluster rotation phase, the unbalanced energy consumption problem is tackled by threshold values using the energy consumed and the ratio from the initial energy. From the evaluation, it was observed that the proposed method performed better compared to some existing methods in terms of balanced energy consumption and improved network lifetime.Since cluster head rotation yields good results, the authors from [68] proposed a nonthreshold-based cluster head rotation scheme (NCHR) for IEEE 802.15.4 cluster-tree networks. Initially, the CH is chosen randomly as it is done in LEACH, and then, the NCHR is applied to ensure that the next CH is selected only if the cluster lifetime can be enhanced based on residual energy and hop count. The author also discusses that NCHR can be used in an environment that has dynamic topology and node heterogeneity and also handles CH failures. The NCHR mechanism performed better than some existing mechanisms, where it is highly scalable because of the multihop data transmission enabled, in addition to having a better network lifetime.


## 4.1.1. Mobility

In applications such as drone applications [3] and medical applications [4], the sensors are always mobile, where clustering is a much more difficult process because of frequent location changes, where frequent reclustering will deteriorate the entire energy level of the network quickly. This problem was tackled by some research that will be discussed below.In 2017, Khandnor and Aseri proposed a threshold distance-based clustering routing protocol taking into consideration both mobile and nonmobile environments in [13]. The method is based on LEACH as it is called LEACHDistance for the static environment and LEACHDistance-M for the mobile environment. CH selection criteria in this protocol are split according to the static and mobile scenario. In a static setting, the upper threshold distance, lower threshold distance, and remaining energy of the node are taken into consideration. On the other hand, in a mobile setting, an extra criterion of low velocity of node (least mobile node) is given attention so that the CH can efficiently communicate with its members. During simulations, LEACHDistance-M performed better than the LEACHDistance and other methods that were compared in terms of network lifetime, correlation, coefficiency, scalability, number of data packets received by the BS, and energy efficiency.The authors in [34] proposed a distributed fuzzy logic-based cluster head selection algorithm (DFLBCHSA) to maximize the network energy efficiency and to minimize the delays in packet delivery. In the network, 3 types of components are identified which are static sensor nodes, mobile gateway, and static base station. The mobile gateway consists of sensors that act as a transportation system, where the data from the CH are delivered to the BS by them. This makes it crucial to have an accurate CH selection mechanism, where the authors introduce two designs of selection criteria that are merged with the use of a fuzzy-based inference system. The two designs are the general state of a sensor node in the WSN (GSoSN) and the location of a sensor node relative to mobile gateway nodes (LoSNRtMG). In GSoSN, the criteria are residual energy, several neighbors, and mean distance between the sensor and its neighbor nodes; while in LoSNRtMG, four parameters are focused on within the transmission range, which are several gateways, distance from the nearest gateway, distance from the most faraway gateway, and the mean distance between a sensor node and gateways. In the simulation outcome, it was observed that DFLBCHSA performed well in terms of a lesser number of dead sensor nodes, higher average remaining energy, and lesser delay in packet transfer.Since the nodes keep moving, the topology keeps changing dynamically. To overcome this problem, the authors in [35] proposed an algorithm named robust, energy-efficient weighted clustering algorithm (RE2WCA). In this research, the authors focus on selecting a CH based on residual energy and group mobility, as it reduces the number of reclustering dramatically. A periodic fault detection protocol and spatial dependency with CH as CHSD hybridized with weight model are introduced to select CHs in the following rounds depending on mobility, to select a CH with reduced energy consumption and increased reliability. From the simulation carried out, the throughput, lifetime, and robustness of the network were found to be better compared to other protocols.The authors from [36] proposed a cluster manager-based cluster head selection (CMBCH) scheme to reduce the workload of the CH. In this literature, the cluster formation phase is carried out first followed by cluster manager selection and CH selection. The elected cluster manager tends to hold the backup details of the CHs, where it reduces the memory capacity limitation problem faced by CHs in a mobile environment. During the reclustering phase, the cluster manager chooses the next CH in terms of residual energy and distance of the CH to the other nodes. The authors also claimed that CMBCH is more energy-efficient and has a higher packet delivery ratio compared to other existing methods in the industry, based on their simulations.In the year 2020, the authors from [37] proposed a CH selection method based on a mobile sensor environment named energy-efficient mobility-based cluster head selection (EEMCS). In EEMCS, the cluster head is chosen based on residual energy, mobility, distance to the base station, and neighbors’ count, with the inclusion of weightage as below:
(4)Weightage=Er∗w1+Degree∗w2ML∗w3+DtoBS∗w4.EEMCS performed better in terms of network lifetime, energy consumption, average energy, and throughput when compared with several existing algorithms.There is still room for research and improvements in the mobile WSN environment, where the authors in [19] proposed the inclusion of two algorithms in two types of models namely, clustering and mobile routing with greedy approach (CMR), and clustering with artificial neural network and mobile routing with greedy approach (CNNMR). In both the models, the mobile sink route is calculated using a greedy approach. In CMR, the CH is selected based on the highest residual energy and closeness to the cluster center, while in CNNMR, the x and y coordinates and residual energy details are fed into the artificial neural network as inputs. Simulations showed that CMR and CNNMR exhibited a greater extension of network lifetime compared to other methods.


## 4.1.2. Multihop Data Transmission

Large- and medium-scale WSNs usually adapt to multihop data transmission, as long-range transmission may deteriorate the life of a sensor node. When CHs that are farthest from the BS aggregate the received data, they send this to another CH nearer to them until it reaches the BS. Various kinds of techniques exist to select proper CHs based on the multihop environment, as discussed below.Since hotspot and energy hole problem is crucial to be mitigated in the field of WSN. Sert et al. [38] were inspired to propose multiobjective fuzzy clustering algorithm (MOFCA) for WSN. The authors considered energy efficiency towards all types of scenarios and adaptability towards implementing on real sensors in both stationary and evolving networks. MOFCA considers 3 important parameters which are distance to sink, node remaining energy, and the node’s density to select the optimal CH. The author also discusses that it does reduces the energy hole problem as it does not need a central decision node for the CH selection process. The simulation focuses on 4 scenarios with varieties of sink location and node distribution. All 4 scenarios are evaluated in respect to direct transmission or multihop routing to the sink. The simulation results show that the proposed method reasonably outperformed several existing approaches in terms of total remaining energy.The authors in [39] proposed an optimal cluster head selection method for defending gray hole and black hole attacks in WSNs. The method is based on LEACH, and it is known as LEACH-Attack Defense (LEACH-AD). Gray hole attacks are where malicious nodes block the passage of the packets in the network, while black hole attacks are where the trustworthiness is exploited to route the packets to the wrong path. These problems are tackled by implementing a good CH selection technique in a multihop data transfer environment, where a CH is selected by detecting the nodes that are already compromised and choosing the node with maximum energy from the noncompromised node, for a better lifetime of the network. The proposed technique is noted to perform better against the attacks compared to existing techniques in terms of packet delivery ratio (PDR), throughput, and end-to-end delay at several intervals.Later in the year 2016, Gawade and Nalbalwar in [40] proposed a technique to balance the energy consumption of nodes and to increase the network lifetime, namely, the centralized energy-efficient distance-based routing protocol (CEED). In the literature, the optimum number of clusters is determined by the energy dissipated by the entire network first; then, the probability of the node to become CH is determined, followed by CH selection and cluster formation. The authors also discuss the multihop routing scheme to transmit the data as it greatly preserves the energy of CHs that are far away from BS. From the simulation, it was shown that CEED is more energy-efficient than other protocols that were compared with it.The authors in [41] proposed a fuzzy logic-based cluster head selection method in two tiers called multitier algorithm (MAP). The CH is selected by using fuzzy logic based on three parameters, which are residual energy, centrality, and communication cost. Few primary nodes are then selected to help the CH transmit the data to the BS. The data transmission in this literature is also divided into parts, wherein the tier one sensed data are aggregated by the CH and sent to the primary node, which is then later sent to the BS (single-hop data transmission); whereas in tier two, the primary node, upon receiving the data from the CH, finds and transmits the data to another primary node that is nearer, to reduce energy consumption over long data transmission (multihop data transmission). From the simulation, the authors conclude that the usage of fuzzy logic has made the nodes evenly involved in data transmission, which makes it more energy-efficient and increases the network lifetime.In 2017, Luo and Xiong in [12] conducted design and analysis on the energy balance clustering technique (EBC). The CH is selected by using an improved threshold value, where the energy level of nodes and distance to sink are considered. The authors considered using multihop communication in the research as it can reduce energy consumption. In this case, the CH near the sink will die quickly due to heavy traffic loads. So, the usage of the relay node is introduced to overcome the hotspot problem. EBC yielded better performance in terms of the number of messages received and average energy consumption, as compared to existing protocols.The authors in [42] proposed a technique for selecting CHs based on residual energy, neighbor degree, and distances among CHs, named as the fixed competition-based clustering approach (FCBA). In FCBA, a hello message is sent to explore the neighborhood, and then, each node calculates and distributes its weight; the node that has the smallest weight becomes the CH, and the other nodes settle down to become the member nodes. The authors implemented this technique in a multihop environment and compared it with several existing techniques. The proposed technique seems to be effective in balanced energy consumption and improving network lifetime.Sert et al. in the year 2018 were inspired to propose another method to overcome poor data aggregation problems in multihop WSN-efficient called two-tier distributed fuzzy logic-based protocol (TTDFP) [43]. TTDFP has two tiers where tier 1 selects the optimal CHs by considering parameters such as residual energy, distance to BS, and relative node connectivity while in tier 2 the optimal routing is done by the fuzzy routing protocol by considering the average residual energy and relative distance parameters. The author discussed that the energy efficiency, scalability, and optimized run-time configuration are focused on tier 1 while energy efficiency and computational simplicity in tier 2. The authors used SA algorithm as the optimization approach to test TTDFP. The simulations are done in 2 scenarios to ensure the proposed protocol can perform well in various situations. Scenario 1 is based on fuzzy clustering tier where in case A, the sink is located outside of service area, and in case B, the sink is in the service area. Scenario 2 on the other hand focuses on the fuzzy routing tier where in case A, multihop routing is employed and in case B, proposed fuzzy routing scheme is employed. The results show that TTDFP outperformed several existing protocols in terms of energy efficiency and scalability.Since the centralized-based clustering technique may take more time and effort and affects the scalability to form clusters, the authors in [44] proposed an energy-efficient load-balanced clustering scheme based on the distributed approach in a multihop environment. This method selects the CH based on the highest candidate weighted score as shown below:
(5)Candidateweight=Er+ni.The author discusses the deployment of the relay node [12] on solving the hotspot problem. The proposed method was compared to LEACH, and through simulations, it was found to perform better in terms of the long lifetime of the network.The authors in [45] proposed the selection of cluster heads dynamically for monitoring in WSNs, using an efficient target tracking approach termed as ETTA. In ETTA, four CHs that are at the edge of the clusters are chosen and the clusters are further divided into four subareas. A collecting cluster head (CCH) is selected, making it a multihop data transmission environment, where it collects the data from CHs, aggregates, and sends it to the BS, which greatly reduces the data gathering costs. The CCH is typically chosen based on the residual energy and lowest distance to the sink. From the simulation, it was proven that ETTA outperformed the state-of-the-art approaches by having a better network lifetime and lower energy consumption.Some researchers prefer to modify LEACH in WSNs, where the authors in [46] introduced a modified LEACH algorithm (LEACH-M). LEACH-M utilizes the network address and residual energy in selecting the best CH to tackle the unreasonable cluster head selection. Moreover, a cluster head competitive mechanism is integrated into LEACH-M, where the average energy Eaver is calculated and the current residual energy Eres of a node is compared with it to select the CH. This technique prevents nodes from running out of energy quickly and maintains the WSN structure for a longer period compared to some exiting methods.Priyadarshini and Sivakumar proposed a cluster head selection technique based on minimum connected dominating set with multihop information (MCDS-MI) and bipartite graph (BG) in WSNs [47]. Initially, a set of the minimum number of nodes with the highest energy and coverage is chosen as dominators, and then, the CH is chosen from the dominators, but the head dominator might fail due to environmental changes. So, a virtual dominator (VD) is created to act as a CH from Steiner tree construction, to reduce the complexity. Furthermore, the VD interchanges the message with nodes and other clusters and reaches the BS at a faster rate. From the simulations, it was observed that the proposed method enhanced the network lifetime by having a load-balanced network.The usage of fuzzy based methods was demanding because of its advantage of performing optimally on widespread WSN optimization. So, Sert and Yazıcı [48] proposed a rule-based fuzzy routing algorithm by utilizing the modified clonal selection algorithm (CLONALG-M) where they used it to modify previously proposed method [43]. To achieve 2% improvement, the cells are created, assigned to population, and iterated without reaching stopping criteria. CLONALG-M is used to ensure the validity measures of fuzzy function are satisfied. After data collection, the authors described 2 data routing protocols called TTDFP and fuzzy path selection (FPS) which are then modified with CLONALG-M for optimality. The routing from the leaf node to CH is by single hop while data transfer from CH to BS is by multihop model. Both the modified approaches are tested and compared with its nonmodified version, and the results shows that the modified fuzzy functions using our CLONALG-M algorithm is more energy efficient and performs better.The authors in [49] proposed a hierarchical topology control algorithm named double cluster heads and multihop based on affinity propagation clustering (APDC-M) in the year 2019. Affinity propagation (AP) clustering algorithm is an unsupervised algorithm that finds the clustering centers by using information iteration of data points, and it is deemed to have fast convergence under less constraint. The CH is selected based on residual energy, and by looking at the burden of the CH to aggregate the data and sending it to the BS, a second CH is elected in the literature to transmit the data to the BS. A multihop path is also constructed with the use of the shortest path algorithm to reduce energy usage during transmission. In simulations, APDC-M managed to make a uniform cluster distribution with reasonable cluster head election by minimizing the energy consumption in data transmission and enabling it to prolong the network lifetime.In the same year, Alami and Najid proposed an enhanced clustering hierarchy (ECH) approach to maximize the lifetime of WSNs in [50]. Initially, the sleeping and waking nodes are determined and the CH is selected randomly from waking nodes. The reselection of the CH uses residual energy and local distance as selection criteria. By implementing sleeping and waking nodes, the wastage of energy without transmission is reduced dramatically in a multihop network. However, it is not applicable for some applications that have consistent data transmission such as environmental sensing nodes. The proposed method managed to reduce the data redundancy of overlapping nodes and maximize the network lifetime compared to other existing protocols.In 2020, the authors in [51] proposed a many-objective optimization model in WSNs based on LEACH, which was termed as LEACH-ABF. There are four objectives considered in this model, which are cluster distance, the sink node distance, the overall energy consumption of the network, and the network energy consumption balance to select the cluster head. Balance function strategy, genetic operation, and penalty-based boundary intersection selection strategy (PBI) are introduced to achieve the true Pareto front, to have better search capabilities, and to enhance convergence and diversity, respectively. The whole network was also designed based on the multihop model and tested with the DTLZ test suite, which showed that LEACH-ABF has better distribution and convergence as well as balanced energy consumption compared to some existing multiobjective algorithms.Later in the same year, the authors from [52] proposed a simplified clustering and improved intercluster cooperation method in WSNs, namely, energy balanced clustering routing (EBCR). During the clustering phase, the BS will sort the nodes in descending order of energy, and the first 10% of the nodes will become CHs initially. For data transmission, the location information is used by the sink to sort the nodes in descending order of distance from the sink, to determine the next hop of the CH farthest from the BS on a multihop basis. In this paper, a good parameter study is done on several CHs and intercluster routing methods based on 4 scenarios. The simulation showed that EBCR has better balanced energy usage in the energy harvesting scenario and a better lifetime in the nonenergy harvesting scenario.Looking at the advancements of using the CLONALG-M algorithm, the authors of [53] proposed on applying the algorithm to the membership function of cluster head election using fuzzy logic (CHEF) and MOFCA [38] to increase the energy efficiencies. The proposed methods are simulated in 3 different scenarios for better understanding of its optimality. In scenario 1, a smaller network dimension with small number of sensors is deployed, the size of the network is increased to test optimality in large network sizes in scenario 2 and in scenario 3, a large network size with a large number of sensors is deployed. The CLONALG-M algorithm is compared against the well-known GA where the CLONALG-M algorithm outperformed GA in all three scenarios.


## 4.1.3. Single-Hop Data Transmission

Even though multihop transmission may seem to be likely the best option to transmit data, it still has the limitation that is called a hotspot problem. In the hotspot problem, the nodes that are placed near the BS die quickly, as many CHs that are far transmit data to the CH that is nearer to the BS, making it have a high traffic load, resulting in more energy consumed. As such, some researchers consider this issue and implement CH selection in a single-hop environment.The authors from [16] proposed an energy-efficient clustering scheme to prolong the network lifetime. The authors focused closely on traditional LEACH protocol and implemented a regional energy-aware clustering method with isolated nodes (REAC-IN). Isolated nodes are considered as one of the problems faced by clustering, where some nodes do not join any cluster and tend to transfer data directly to the BS due to random selection of the CH. Given the issue, the CH selection in this approach is done based on residual energy and regional average. The authors later discuss the data transmission of the occurring isolated node where it uses a first-order radio model, where it is still possible for the isolated nodes to exist. In a comparison of REAC-IN with LEACH and other clustering algorithms, REAC-IN performed better in terms of network lifetime and stability of the network.In the year 2019, the authors in [54] proposed two CH selection techniques which are energy- and distance-based cluster head selection (EDB-CHS) and EDB-CHS with balanced objective function (EDB-CHS-BOF). The authors considered that the cluster area has a hexagonal shape which is near to the reality in a single hop data transfer model. For the CH selection, a threshold probability is created by ensuring that the node with higher residual energy, lesser energy consumption, and the shortest distance between the sensor node and the BS is selected. In the second technique, the objective function is added to select better CHs by including the expression of node optimal probability. EDB-CHS-BOF performed better than EDB-CHS and other protocols in terms of network lifetime, balanced energy consumption, and total data delivery.Another closely LEACH referred method was introduced by the authors of [55]. The proposed method has the inclusion of selectivity function-based CH selection (SF-CHs) algorithm to select optimal CH and clustering in ubiquitous power Internet of Things (IoT). Selectivity function maxZ is implemented as below:
(6)maxZ=λ1×Er+λ2×ni+λ3×vi+λ4×ωr,where λ1+λ2+λ3+λ4=1 and λ3<0. The cluster data transmission is also discussed, where a spreading code is used by CHs to reduce the intercluster interference. From the comparison of SF-CHs, LEACH, and other protocols, SF-CHs performed better in terms of stable network and enhanced network lifetime.Dwivedi and Sharma proposed a fuzzy-based energy-efficient clustering approach (FEECA) to prolong the network lifetime in WSNs [56]. In this literature, two scenarios are considered. In scenario 1 (S1), the BS is located in the center of the network, and in scenario 2 (S2), the BS is located at the edge of the network. In FEECA, three selection criteria are considered which are residual energy, average communication distance, and communication quality. These criteria are then run through a fuzzy inference system (FIS) to select proper CHs. Data routing in the network scenarios considers single-hop data transmission for clusters near the BS, while clusters that are far away send data to the BS through the master node. From the simulations, it was observed that FEECA enhances the network lifetime and also has better throughput compared to existing algorithms.The energy consumption problem in WSNs has been researched until recently, as Pour and Javidan proposed a new energy-aware cluster head selection method for LEACH (DRE-LEACH) in [57]. Four CH selection criteria are imposed in this method, namely, residual energy, the distance between nodes and sink, the nodes centrality, and the number of neighbors of each node. A threshold value is calculated by the ratio of the number of CH with the number of alive nodes, where it is ensured that a node becomes CH only when the threshold value is below 0.05, to control the number of CHs that exist in the network at one time. DRE-LEACH outperforms other existing LEACH-based protocols in terms of network lifetime and reliability.


## 4.1.4. Heterogeneity

Heterogeneity in WSNs is where the sensor nodes that are in the network have different abilities in terms of different amounts of energy levels and sensing ranges [58]. Some research promotes a heterogeneous environment as it greatly improves the energy efficiency and reliability of an application by selecting a CH with better ability.In 2016, the authors of [59] proposed a method with 4 variants namely, balanced energy-efficient network-integrated super heterogeneous (BEENISH), improved BEENISH (iBEENISH), mobile BEENISH (MBEENISH), and improved mobile BEENISH (iMBEENISH) protocols. The research was carried out on heterogeneous nodes in two different environmental settings, with sink mobility and without sink mobility. In this setup, four types of nodes exist with different initial energies namely, ultrasupernode, supernode, advanced node, and normal node. CH selection in BEENISH is based on the residual energy and the average energy level of the network, where the ultrasupernodes have a higher frequency to become CHs as they have the highest amount of residual energy. In improved BEENISH, absolute residual energy Tabsolute is used to determine the CH when all the higher energy nodes have become equal to a normal node, to obtain a longer stability period:
(7)Tabsolute=zE0,where z=0.71 (after running simulations many times). To obtain more energy efficiency from the network, both BEENISH and iBEENISH are equipped with sink mobility. From the simulations, it was concluded that iBEENISH performs better than BEENISH in terms of network lifetime and throughput. Moreover, it was also found that the mobile sink versions can achieve the desired objectives which make them perform better than the nonmobile sink versions.The authors in [60] proposed an energy-coverage ratio clustering protocol (E-CRCP) to be used in heterogeneous energy network environments. In this, the optimal numbers of clusters are determined first by calculating the total energy used in communication. Next, the CH is selected based on the maximum coverage ratio, so that the CHs are evenly distributed throughout the network. Then, the CH that consumes a large amount of energy is replaced in the next communication iteration. Comparing E-CRCP with other existing protocols showed that E-CRCP improves network lifetime, balances the network load, and reduces the energy consumption in heterogeneous WSNs.The authors of [61] proposed an energy-efficient scheme for heterogeneous WSNs. A multicriteria decision-making technique is included in the scheme, named as a technique for order of preference by similarity to ideal solution (TOPSIS). This scheme comprises of few phases such as the CH declaration phase, node association phase, CH-acquaintanceship phase, and CH-friendship phase. In the CH declaration phase, it is ensured that the resources such as residual energy, computational capability, and storage capacity are higher than the threshold values. In the node association phase, the decision of the child nodes in joining the clusters is based on TOPSIS. CH-acquaintanceship and CH-friendship are used to help CHs with low resources do their tasks to balance the energy usage and minimize packet drops. From the simulation, it was observed that the proposed method extends network lifetime and minimizes the reclustering frequency in a heterogeneous environment.Narayan and Daniel proposed a cluster head selection technique based on trust function in a very recent paper [62]. In this research, the authors deployed two types of nodes which are advanced and normal nodes, where the advanced nodes have higher energy levels compared to normal nodes, creating a heterogeneous environment. Firstly, the CHs are selected based on new threshold values that consist of distance ratio and weighted energy, to reduce the energy failure problem. Random selection of CHs is also avoided. Then, the trust function is used to preserve the accuracy of data in the data fusion method. The proposed protocol has shown better network lifetime and stability compared to an existing protocol in a heterogeneous environment.


## 4.1.5. Other Parameters

Some research which are based on different network sizes, usage of weights and coefficients in CH selection, and usage of CH rotation methods are categorized in this section. There are also certain pieces of literature with no significant environmental changes. Below is some literature discussed briefly, that was carried out in a homogeneous and static network.The stochastic control problems are modelled based on semi-Markov decision processes (SMDPs) by allowing the state transitions to occur in continuous irregular times [63]. In the year 2018, Amuthan and Arulmurugan got inspired by semi-Markov and proposed a hybrid trust prediction scheme through reliable CH selection in WSNs named hyperexponential reliability factor-based cluster head election (HRFCHE) [64]. HRFCHE is aimed at minimizing the number of CHs while increasing the number of rounds in implementation by using the energy and trust factor. A CH is chosen through hyperexponential reliability factor to obtain a more energy-balanced CH. From the simulations, it was observed that the proposed method performs better than LEACH in terms of energy consumption and improves the network lifetime.Zahedi proposed a clustering protocol that is closely related to LEACH by applying weighting coefficients termed (CWC) in [65]. The main difference of the proposed algorithm compared to LEACH is that it uses weighted residual energy and distance from sink threshold to select the appropriate CH. In this literature, the clusters are formed first and then the suitable CHs are chosen for each cluster. Two scenarios are considered in terms of smaller and slightly bigger network dimensions in this research. From the comparison, it was observed that CWC shows dominance in terms of global performance compared to some exiting methods.Following the trend of using coefficients in CH selection, Turgut proposed a method called dynamic coefficient-based adaptive cluster head selection (DCoCH) in WSNs [66]. The selection criteria that are used to select CHs are the residual energy of the nodes, the intracluster communication cost, and the number of neighbors. The coefficients applied are dynamically changed from 1st round to FND, then to HND, and finally to LND. DCoCH outperformed two other adaptive-based CH selection methods in terms of prolonging network lifetime.The authors in [67] proposed another network lifetime prolonging method named improved energy-efficient clustering protocol (IEECP). In IEECP, first, the optimal numbers of balanced clusters are determined by using a mathematical model and the modified fuzzy C-means algorithm (M-FCM), which considers the overlapping case and multihop communications. Then, CH selection and CH rotation are introduced by integrating the back-off timer called (CHSRA). The backoff timer is used in the CH selection phase as it reduces the overheads of the nodes. Moreover, during the cluster rotation phase, the unbalanced energy consumption problem is tackled by threshold values using the energy consumed and the ratio from the initial energy. From the evaluation, it was observed that the proposed method performed better compared to some existing methods in terms of balanced energy consumption and improved network lifetime.Since cluster head rotation yields good results, the authors from [68] proposed a nonthreshold-based cluster head rotation scheme (NCHR) for IEEE 802.15.4 cluster-tree networks. Initially, the CH is chosen randomly as it is done in LEACH, and then, the NCHR is applied to ensure that the next CH is selected only if the cluster lifetime can be enhanced based on residual energy and hop count. The author also discusses that NCHR can be used in an environment that has dynamic topology and node heterogeneity and also handles CH failures. The NCHR mechanism performed better than some existing mechanisms, where it is highly scalable because of the multihop data transmission enabled, in addition to having a better network lifetime.


## 4.2. Cluster Formation

When we talk about CH selection, it automatically drives us to the cluster formation phase for hierarchical clustering. The ever-growing use of sensors in many applications drives the research more into CH selection methods as well as cluster formation methods. Cluster formation can be done before CH selection or after CH selection, depending on the objectives and applications that the network is used in. Cluster formation techniques help to reduce the hotspot problem in WSN deployments. This section will discuss several cluster formation techniques using nonmetaheuristic methods introduced by some researchers in recent years, as outlined in Figure5.Figure 5
Taxonomy of cluster formation with nonmetaheuristic methods.Unequal clustering (UC) is a clustering algorithm that acts as a direct solution to the hotspot and blind spot problem, as discussed in [69–71]. Unequal clustering is where the clusters near the BS are smaller and have lesser nodes than clusters far away from the BS, as visualized in Figure 6.Figure 6
Unequal clustering [72].In 2016, Gupta and Pandey proposed an improved energy-aware distributed unequal clustering protocol (EADUC) in a heterogeneous and multihop environment [69]. Improved EADUC considers several neighbors, the distance between the nodes and the BS, and the residual energy, while deciding the competition radius for the cluster formation. The proposed method was then tested with three scenarios where the nodes were uniformly deployed in scenario 1, and the nodes were nonuniformly deployed and grouped to the right and left in scenarios 2 and 3, respectively. In [70], the blind spot problem is tackled, as events are not captured due to dead nodes by using unequal clustering. In the proposed method, the unequal clusters are formed by cognitive partitions to ensure equal energy consumption in each cluster. The authors of [71] proposed an unequal clustering protocol for energy harvesting sensor networks (UCEH). In the energy harvesting application, the multihop routing strategy is adopted, creating a hotspot problem. As such, unequal clustering based on the location of nodes, field area, coordinates of BS, and distance from nodes to BS is implemented. From simulations, all the unequal clustering methods researched by the aforementioned authors showed improvements when balancing the energy consumption and increased the network lifetime compared to some existing methods.K-means clustering is another clustering algorithm that is widely used in certain applications of WSNs, as discussed in [73–75]. K-means clustering is where clusters are formed from the k number of centroids that are determined manually, as visualized in Figure 7.Figure 7
K-means clustering [79].The authors in [73] proposed a modified k-means (Mk-means) algorithm to choose the best centroid and form clusters. In this literature, a k value of 3 is used, so only 3 clusters are formed, which might limit scalability. Upon determining the 3 centroids, multiple iterations are carried out until the establishment of the optimum means, and then the final CH selects 2 more CHs that are nearer to it to load, share, and minimize the energy consumption of a single CH. In the year 2020, the authors of [74] proposed a lifetime-enhancing cooperative data gathering and relaying algorithm (LCDGRA) that could be used in event-driven monitoring applications. In LCDGRA, Huffman entropy coding is adopted in K-means clustering, as it ensures that the sensor node’s transmission distance and energy consumption are optimized during the clustering phase. Besides, in [75], the authors proposed a nonuniform clustering routing algorithm based on an improved K-means algorithm. In the proposed method, a clustering point selection method is added to reduce the randomness of centroid selection based on a threshold function. The threshold function is created based on several neighboring nodes and a reduced number of iterations to avoid blind iterations and to find the centroid quickly. From the simulations of the aforementioned research, it can be seen that the K-means method shows better performance in terms of reduced energy consumption, balanced network, and enhanced network lifetime.Baniata and Hong proposed energy-efficient unequal chain length clustering (EEUCLC) in [18]. EEUCLC consists of 3 important phases which are CH selection, chain formation, and data collection and transmission. In the CH selection phase, the CH is selected based on residual energy and distance of the node to the BS. The clusters are then formed and intracluster communication chains built, where the intracluster chains nearer to the BS are shorter compared to those farther away. The purpose of building an intracluster chain is to reduce the communication traffic at the CH. The results of the simulation show that EEUCLC enhanced the lifetime and balanced the energy consumption compared to LEACH and the other two methods.In [76], the authors proposed an energy-efficient clustering routing protocol based on a high-QoS node deployment with an intercluster routing mechanism (EECRP-HQSND-ICRM) in WSNs. This method introduces a 2-fold coverage-based node deployment strategy as shown in Figure 8. To have an even distribution of CHs in the network, the BS first acts as a center and divides the area into four small cells, where each cell selects a CH based on residual energy and distance from the node to the BS, creating a selection factor SCHEi,dtoBSi as follows:
(8)SCHEr,DtoBS=α.NorEr+β.NorDtoBS,where α+β=1 (weight factors) and Nor represents the normalization. From the simulation, it is known that EECRP-HQSND-ICRM has high coverage, information integrity, and validity.Figure 8
2-fold coverage-based model [76].The authors in [77] proposed a hybrid optimal-based cluster formation (HOBCF) algorithm. A chemical reaction model (CHRA) is adopted for cluster formation in this paper, but it gives a lesser network lifetime. So, Lagrangian relaxation and entropy model are hybridized alongside multihop transmission, which is developed to enhance the network lifetime. The Lagrangian relaxation model identifies an optimal value of the node to form a cluster based on average neighbor distance, distance to reach the BS, energy, and available bandwidth. CHRA and HOBCF were tested with 3 different, scenarios where each scenario had a different duration of the mobility model. Simulation results show that HOBCF performed better than CHRA.A cluster formation technique named grid clustering was researched by the authors in [78]. It is based on a fuzzy reinforcement learning-based energy-efficient data aggregation scheme. Initially, with two stages, the network is divided into several grid cells. In stage 1, similar rectangular lanes are created with width and height, whereas in stage 2, the created rectangular lanes are broken down further into unequal smaller lanes based on the distance between rectangular lanes and the sink. Then, each grid elects a CH based on the residual energy factor. The fuzzy reinforcement learning algorithm is used to select the data aggregator using certain parameters, to ensure the selection of a robust aggregator. The simulations show that the proposed scheme performed better in terms of reliability and energy consumption of the network.


## 4.3. Parameter and Environmental Setting Analysis of Nonmetaheuristic Methods

The simulation parameters used and the environment settings from all the aforementioned techniques in nonmetaheuristic clustering are analyzed and compared in Table3.Table 3
The comparison analysis of simulation parameters and environmental settings of nonmetaheuristic clustering.
Paper (year)CH selectionCluster formationSelection criteriaData transmissionMobilitySensor typeNetwork dimensionNo. of nodesPacket lengthSensor initial energyLocation of BS[16](2015)REAC-IN—Residual energy and the regional average energySingle hopStaticHomogeneous200m×200m100-500—2 J(100, 100)[38](2015)MOFCA—Distance to BS, remaining energy, density, and competition radiusMultihopStaticHomogeneous200m×200m, 1000m×1000m100500 bytes1 J(250, 250), (100, 100), (500, 500), (1250, 1250)[39](2016)LEACH-AD—EnergyMultihopStaticHomogeneous1500m×1500m10, 50128 bytes1 J—[40](2016)CEED—Dissipated energy of a node and its distance to BSMultihopStaticHomogeneous100m×100m10062.5 bytes0.5 J(50, 350), (100, 300)[41](2016)MAP—Residual energy, centrality, and communication costMultihopStaticHeterogeneous100m×100m100250-500 bytes0.5-2 J(50, 50)[59](2016)BEENISH—The residual energy of nodes and average energy of the networkSingle hopMobile sinkHeterogeneous100m×100m100500 bytes0.5 J—[69](2016)—EADUCResidual energy, distance, number of neighbor nodesMultihopStaticHeterogeneous200m×200m100500 bytes0.5-1.5 J-250, 100[73](2016)—Mk-meansResidual energyN/SStaticHomogeneous100m×100m100250 bytes2 J(50, 175)[13](2017)LEACH-Distance-M—Upper threshold distance, lower threshold distance, remaining energy, and least mobility.MultihopMobileHomogeneous100m×100m10-100—0.5 J(50, 50)[12](2017)EBC—Sensor nodes’ energy level and distance to the sink.MultihopStaticHomogeneous400m×400m200—2 J(200, 200)[42](2017)FCBA—Energy, degree, and distanceMultihopMobileHomogeneous100m×100m50-200—15 J(50, 50)[18](2017)—EEUCLCResidual energy and distance to BSMultihopStaticHomogeneous(0m×0m)-(400m×400m)150250 bytes1 JOutside the network[43](2017)TTDFP—Distance to BS, remaining energy, relative node connectivity, and competition radiusMultihopStaticHomogeneous1000m×1000m100500 bytes1 J(1250, 1250), (500, 500)[35](2018)DFLBCHSA—Residual energy, number of neighbors, number of gateways, most faraway gateway, and distanceN/SMobile gatewayHomogeneous350m×350m100500 bytes0.35 J—[36](2018)RE2WCA—Residual energy and group mobilityMultihopMobileHomogeneous100m×100m50—2 J—[44](2018)Distributed clustering scheme—The residual energy of nodes and the number of their neighborsMultihopStaticHomogeneous100m×100m100—2 J(150, 50)[45](2018)ETTA—CH location and residual energyMultihopStaticHomogeneous200m×200m500-3000256 bytes100 JOutside the network[46](2018)LEACH-M—Residual energy and network address of nodesMultihopStaticHomogeneous(100m×100m), (300m×300m)50250 bytes2 J—[47](2018)MCDS-MIThe energy level and coverage degreeMultihopStaticHeterogeneous1000m×1000m500—N/S—[64](2018)HRFCHE—Energy and trust parameterN/SStaticHomogeneous100m×100m100500 bytes2 J—[65](2018)CWC—The residual energy of each node by applying weighting coefficients and distance from the sinkN/SStaticHomogeneous(50m×50m), (100m×100m)20, 40500 bytes0.1 J(25, 87.5), (50, 175)[70](2018)—Cognitive partition unequal clusteringResidual energy and cumulative distanceMultihopStaticHomogeneous200m×200m300500 bytes1 J(100, 50)[48](2019)TTDFP_ CLONALG-MFPS_ CLONALG-M—N/SMultihopStaticHomogeneous500m×500m100N/S1 JIn ROI[49](2019)APDC-M—Residual energyMultihopStaticHomogeneous100m×100m100502 bytes2 JOutside the network[50](2019)ECH—Energy and local distanceMultihopStaticBoth100m×100m1003000 bytesN/S(50, 50)[54](2019)EDB-CHS—Residual energy, distance, and node’s optimal probabilitySingle hopStaticHomogeneous(200m×200m), (300m×300m), (400m×400m)100625 bytes0.5 J-100, 300[55](2019)SF-CHs—Remaining energy, number of neighbors, motion velocity, and data transmission environmentSingle hopMobileHomogeneous100m×100m200, 300500 bytes1 JCenter of the network[60](2019)E-CRCP—Residual energy and coverage ratioN/SStaticHeterogeneous100m×100m100500 bytes0.5 J(50, 50)[76](2019)—EECRP-HQSND-ICRMResidual energy and distance of nodes from BSMultihopStaticHomogeneous100 m × 90 m91500 bytes0.5 J(50, 45)[34](2020)CMBCH—Energy and distanceMultihopMobileHomogeneous1200m×1200m20-100512 bytes5000—[37](2020)EEMCS—node’s mobility level, residual energy, distance to sink, and density of neighborsMultihopMobileHomogeneous(50m×50m), (100m×100m), (150m×150m), (200m×200m), (250m×250m)50, 100, 150, 200, 250500 bytes0.1 JOutside the network[51](2020)LEACH-ABF—Cluster distance, sink node distance, overall energy consumption, and network energy consumption balanceMultihopStaticHomogeneous100m×100m100500 bytes2 J(50, 50)[52](2020)EBCR—Residual energyMultihopStaticHomogeneous100m×100m991 bitN/S(100, 50)[56](2020)FEECA—Residual energy, communication quality, average distance of BSSingle hopStaticHomogeneous100m×100m100, 200375 bytes0.5 J, 1 J(50, 50), (150, 100)[61] (2020)TOPSIS—Residual energy, available storage, and computational capabilitySingle hopStaticHeterogeneous100m×100m100500 bytes6 J–10 J—[66] (2020)DCoCH—Intracluster communication cost, number of neighboring nodes, and remaining energyN/SStaticHomogeneous(100m×100m), (300m×300m), (400m×400m), (500m×500m)50, 100, 200, 300—0.5, 1, 2 JCenter, corner, outer 1, and 2 of network[67] (2020)IEECP—Energy consumed and the ratio from the initial energyMultihopStaticHomogeneous(100m×100m), (1000m×1000m)100, 1000400 bytes1 J(50, 125), (500, 1250)[71] (2020)—UCEHResidual energyMultihopStaticHomogeneous(0m×0m)-(200m×200m)100-400500 bytes0.5 J-100, 100[74] (2020)—LCDGRACommunication distances and residual energy metricsMultihopStaticHomogeneous100m×100m100100 bytes5 J(100, 50)[75] (2020)—NonuniformK-meansNumber of neighboring nodes, residual energy, and centroid of the clusterSingle hopStaticHomogeneous300m×300m300500 bytes0.5 J(150, 400)[77] (2020)—HOBCFDistance and energyMultihopMobileHomogeneous1000m×1000m500512 bytes100 JCenter of the network[78] (2020)—Grid clusteringResidual energy, distance, neighborhood overlap, and algebraic connectivityMultihopStaticHeterogeneous200m×200m20-500500 bytes0.5, 2, 200 J(100, 100), (100, 50), (200, 200)[19] (2021)CNNMR—Distance from the cluster centre and its residual energyN/SMobile sinkHomogeneous(90m×90m), (120m×120m)100, 200500 bytes2 J—[53] (2021)MOFCA_ CLONALG-MCHEF_ CLONALG-M—N/SMultihopStaticHomogeneous(100m×100m), (1000m×1000m)100, 1000500 bytes1 J(50, 50), (500, 500)[57] (2021)DRE-LEACH—Residual energy, the position, and centrality of nodesSingle hopStaticHomogeneous70m×70m100500 bytes0.5 J(35, 47.25)[62] (2021)Threshold CH selection—Residual energy and distance from BSMultihopStaticHeterogeneous150m×150m150—0.5 J(150, 75)[68] (2021)NCHR—Residual energy and distanceMultihopStaticBoth1000m×1000m71—1 J—∗N/S: not stated.


## 5. Metaheuristic Method

### 5.1. Cluster Head Selection (Nonhybrid)

Metaheuristic methods are where a nature-inspired or bioinspired theory is converted to mathematical computations to solve optimization problems. The word metaheuristic is split into two, meta and heuristic, where meta means a high-level methodology and heuristic refers to a technique of solving problems by finding new strategies [80]. To achieve an optimal solution, it is very important for the metaheuristic algorithm to balance its exploration and exploitation capability so that the algorithm does not fall into local optimum easily or has a slow convergence rate [81]. A nonhybrid metaheuristic method refers to an algorithm that has no inclusions of other techniques’ algorithmic components to solve optimization problems. This will be further discussed below in this section.In this section, the usage of nonhybrid metaheuristic algorithms in CH selection is explained in terms of various environmental settings. Figure9 describes the environment settings and their related methods of CH selection.Figure 9
Taxonomy of cluster head selection using nonhybrid metaheuristic methods.


#### 5.1.1. Mobility

In 2018, the authors of [82] proposed a honeybee algorithm to select CHs in a mobile WSN (BeeWSN). In this, the selection criteria of CH selection are based on the remaining energy of the node, degree, speed, and direction. In the honeybee algorithm, two types of bees are identified, the onlooker and employed bees. The onlooker bees are the control packets that search for the most suitable CH by using the selection criteria, while the employed bees are data packets. This algorithm is deemed to have good exploration in the form of onlooker bees and exploitation in the form of employed bees. From the simulations, it was seen that BeeWSN forms more balanced clusters compared to some existing methods.Mobile WSNs have limitations of frequent topology changes and scalability issues. In [83], the authors proposed a bioinspired clustering scheme using the dragonfly algorithm (DA) for the internet of drone application (BICIoD) to handle the issues. Dragonflies have two swarming behaviors called static swarming (finding food), which promotes exploitation, and dynamic behavior (migration), which promotes exploration capability. In this proposed method, the CH is selected using connectivity to BS, residual energy, and position of drones. The formed clusters are then managed by DA, where the cluster members need to follow the movement of the CHs and adjust themselves. Comparison of BICIoD with other algorithms proved that BICIoD performs better in terms of cluster lifetime, energy consumption, and delivery rates.


#### 5.1.2. Multihop Data Transmission

In the year 2015, the authors in [84] proposed an enhanced PSO-based clustering method for energy optimization termed as EPSO-CEO in a multihop data transmission environment. PSO is a theory based on the movement of particles where the position and velocity are updated till the global best solution is reached. The literature discusses cluster formation and CH selection based on centralized clustering by using PSO. A CH is selected based on the fitness function that involves the distance and energy using PSO, where the global best value achieved by PSO will be the CH of the particular cluster. The authors also precisely discuss inter- and intracluster multihop data transmission using distance and residual energy. The simulation showed that EPSO-CEO performs better by minimizing the energy consumption and enhancing the network lifetime, when compared with other competitive methodologies.Sengottuvelan and Prasath proposed another metaheuristic method for optimal CH selection called the breeding artificial fish swarm algorithm (BAFSA) in [85]. BAFSA is the modified version of AFSA, where the solutions are randomly split, and the network performs either a swarming or a following behavior. A tournament selection is also used to produce the best solutions. The fitness function based on end-to-end delay and energy is applied to BAFSA for an optimal CH to be selected. The proposed method not only had fast convergence, good fault tolerance, and good local search capability but also performed well in terms of reduced packet loss and enhancing the network lifetime, compared to some existing methods.Mann and Singh on the other hand, proposed another clustering and routing method for energy efficiency using artificial bee colony (ABC) in [86]. In this literature, ABC is used in a multihop and static environment. ABC is used in CH selection based on a fitness function that contains residual energy, the distance between CH and BS, and the distance between CH and CH as functions. ABC is then used to obtain optimized routing to have the least energy dissipation through communication. From the simulations, it could be observed that ABC performed better in terms of packet delivery, energy consumption, and throughput as compared to other algorithms.Since bioinspired algorithms tend to have fast convergence compared to nonmetaheuristic methods, more studies were conducted on metaheuristic methods. In 2017, the authors in [87] proposed a bioinspired algorithm, named firefly cluster head selection algorithm (FFCHSA). FFCHSA uses the fitness function based on energy, packet loss ratio, and end-to-end delay to select the CH in a multihop WSN, as discussed by the author in the introduction. From the simulations, it was seen that the proposed algorithm improves the overall performance compared to PSO and genetic algorithm (GA).By considering the hotspot problem, Gupta and Jha proposed an integrated clustering and routing protocol using cuckoo and harmony search (iCSHS) in WSNs [88]. The authors proposed two different algorithms for two different protocols, where cuckoo is used for clustering and harmony search is used for routing. Four different objectives have to be minimized in the objective function in improved cuckoo search to select the optimal CH, which are node energy, degree of a node, intracluster distance, and coverage of the CH. Multihop data routing is adopted in the literature by using improved harmony search to reduce communication energy consumption. A simulation based on the two different scenarios with varying sink locations showed that the proposed iCSHS performs better compared to some existing algorithms.In the year 2019, the authors of [89] proposed sampling-based spider monkey optimization and energy-efficient cluster head selection (SSMOECHS). This method was proposed to solve the location-based CH selection approach problems. Spider monkey optimization (SMO) is based on monkeys searching for food with good exploration capability. The CH is selected based on the sampling method of SMO where coverage and energy of notes are considered the objective function that must be maximized. The method is simulated through a homogeneous and heterogeneous environment by adopting multihop data transmission, which shows that SSMOECHS improved network lifetime and energy efficiency.Pathak proposed a proficient bee colony-clustering protocol (PBC-CP) in [90]. The concept of a bee colony is the same as the aforementioned method by [78], but in this research, it was implemented in a static and multihop data transmission environment because of the fast-searching feature of the algorithm. The fitness function is based on residual energy and node degree, used by the bee colony algorithm to select the CH efficiently. PBC-CP performed well in terms of extending network lifetime compared to several existing protocols.Chawra and Gupta proposed a load-balanced node clustering scheme using an improved memetic algorithm to solve the energy hole problem that occurs in a multihop WSN environment [91]. The CH in this scheme is selected based on node degree, intracluster communication distance, and residual energy, by having these parameters in the fitness function of the memetic algorithm. From the performance comparison with other existing algorithms, it was seen that the memetic algorithm performed better in terms of energy consumption and network lifetime.


#### 5.1.3. Single Hop Data Transmission

Since the usage of the swarm intelligence algorithm shows many improvements in CH selection, Sarkar and Murugan proposed a CH selection and routing method based on firefly with cyclic randomization (FCR) in a single hop environment [92]. Comparing to [87], FCR replaces the firefly by following certain conditions in a particular cycle, and FCR can handle multiple objectives as well. The CHs are selected based on a cost function that includes distance, energy, and the delay as parameters. Simulation results show that FCR performs better than some existing algorithms.Mood and Javidi on the other hand proposed a modified gravitational search algorithm (GSA) in WSNs [81]. Since it is very important to have a balance between exploitation and exploration, GSA is modified with varying mass value over time and the inclusion of a tournament selection method. Modified GSA uses a fitness function based on the distance of nodes to the CH and residual energy to select the optimal CH. The proposed method was evaluated using several unimodal functions, basic multimodal functions, and composition functions, where modified GSA performed well in terms of network lifetime and delivery of data packets.Metaheuristic algorithms are not only used to achieve energy efficiency but they are also used for optimized area coverage, as discussed by Peng and Xiong in [93]. In this literature, improved adaptive PSO (IAPSO) is applied to solve coverage and energy optimization problems in a single-hop environment, where the inertia weight in PSO is adaptively changed for balance exploration and exploitation capability. To optimize the energy consumption problem, an optimal CH is selected based on the total residual energy ratio and energy consumption balance degree of CH candidates. Comparison with some existing algorithms shows that IAPSO performs well in terms of achieving balanced energy consumption.The authors of [94] proposed a multiobjective CH selection mechanism using a fitness averaged rider optimization algorithm (FA-ROA) in a single-hop smart city application. The multiobjectives that are optimized in this mechanism are the load, temperature, delay, and distance between nodes. ROA is based on the idea of a group of riders riding to reach a goal where it comprises bypass, follower, overtaker, and attacker riders. In this literature, ROA is improved in the processing of the group update phase to enhance performance. Simulation results show that FA-ROA managed to perform well in terms of delay, normalized energy, and alive nodes compared to some existing metaheuristic algorithms.


#### 5.1.4. Heterogeneity

The authors in [95] proposed a multiobjective clustering and routing method in WSNs by using an improved nondominated sorting particle swarm optimizer (INSPSO). When we say multiple objectives, it means there is the inclusion of minimizing and maximizing objectives, where in this paper, the sum of residual energy must be maximized, and the energy consumption must be minimized to select the optimal CH. The performance evaluation is done by considering heterogeneous scenarios, where there are different numbers of sensors and gateways in the network. INSPSO performed well in selecting the CH through multiobjective factors efficiently by improving the network lifetime and reducing energy consumption.In the year 2019, a new bioinspired algorithm based on earthworm breeding in nature named earthworm optimization algorithm (EWA) was proposed by Pasupuleti and Balaswamy in [10]. In this algorithm, there are 2 types of nodes which are normal nodes and advanced nodes, where advanced nodes contain greater energy than normal nodes. EWA is used to select the optimal CH according to the highest fitness value based on energy and the distance between CH and nodes. In EWA, there are two types of breeding, where the first type is a reproduction by a single earthworm, and the second type is reproduction by varying number of parents and offspring. From the simulation, it was observed that EWA performed better in terms of delay, throughput, network lifetime, and energy consumption compared to GA and PSO.Later, in the same year, the authors of [96] proposed a genetic algorithm (GA) based on CH selection (GAOC) in heterogeneous WSNs. To solve the well-known hotspot problem, multiple data sinks are deployed in the network (MS-GAOC). Since it is focused on a heterogeneous network, three types of nodes are deployed, which are advanced, intermediate, and normal nodes with three different energy levels EADV, EINT, and ENRM, respectively.
(9)EADV=E0×1+α×n×m,(10)EINT=E0×1+β×n×m0,(11)ENRM=E0×1−m−m0×n.The energy fractions of advanced and intermediate nodes are denoted asα and β. The fitness function used in GA is based on energy factor, the distance between node and sink, and node density, which are used to select the optimal CH. Simulation shows that using a single data sink is efficient for a small area network and multiple data sinks fare better for a larger area of a network.In [97], the authors proposed a method to select the best CH and to avoid energy hole problems where energy centers are searched using PSO (EC-PSO). Initially, CHs are chosen using a geometric method as the nodes are homogeneous. After the network spends the first period, the network energy becomes heterogeneous and the PSO is executed to search the energy centers, so that a node near it will become the CH for the following period. The low-energy nodes are then protected from forwarding by using a threshold. The evaluation shows that EC-PSO performs better in terms of energy consumption and network lifetime compared to some existing methods.To have an energy-balanced and optimized WSN, the authors in [98] proposed an enhancement to the distributed energy-efficient clustering (DEEC) method by using the threshold game theory algorithm (TGDEEC). Game theory is a mathematical computation that facilitates decision-making scenarios. In this literature, heterogeneous networks with advanced nodes, normal nodes, and supernodes are assumed. TGDEEC uses a weighted factor β that considers CH and cluster member’s energy consumption to create a threshold. The CH is then selected by using the threshold and calculating the distance and energy used. TGDEEC is known to perform better compared to several other algorithms in terms of throughput and network lifetime.In [99], the authors proposed a clustering algorithm based on the section-based routing protocol (SBHRA) and artificial bee colony algorithm (ABC). SBHRA splits up the network into few sections with three types of nodes, namely, type-1, type-2, and type-3, making it a heterogeneous environment. The mechanism of ABC is similar to [82], but in this literature, it is deployed in a heterogeneous and sectioned environment. CH selection is done on type-2 and type-3 nodes’ regions by considering the residual energy parameter as a fitness function in ABC. The simulation of SBHRA, with the inclusion of ABC for CH selection, shows that network throughput, stability period, and lifetime is increased compared to other existing methods.


#### 5.1.5. Other Parameters

Although the aforementioned papers have network environmental setting information, certain works do not mention the type of data transmission or do not impose significant environmental changes for the research to be carried out. Below are some summarized state-of-the-art methods that can be carried out in a static and homogenous network setup.The authors in [100] proposed the usage of particle swarm optimization for energy-efficient CH selection (PSO-ECHS). In this literature, parameters such as intracluster distance, sink distance, and residual energy of sensor nodes are considered for optimal energy-efficient CH selection using PSO. Simulation of the proposed algorithm is done based on a varying number of nodes, CHs, and the location of BS. PSO-ECHS performs better than some existing algorithms in terms of network lifetime, data packets delivered, and total energy consumption.In the year 2017, a new metaheuristic algorithm was introduced by Jadhav and Shanker, called whale optimization algorithm (WOA) for CH selection, termed as WOA-C [101]. WOA uses the concept of the hunting behavior of humpback whales, where the random or optimal search is used to hunt the prey (exploration) and a spiral bubble-net attacking mechanism is used to catch the prey (exploitation). The CH is chosen based on the node that has the highest fitness value, where the fitness function considers residual energy and number of neighbors for fitness calculation. From the simulations, WOA-C outperforms some contemporary existing protocols in terms of increased throughput, network lifetime, and stability period.Wang and Zhu were inspired by the usage of metaheuristic algorithms in WSNs and proposed a chicken swarm optimization (CSO) algorithm. CSO was introduced in [102] with the idea of having classification as a rooster (CH), hen, and chicken, where the highest fitness value is the rooster, and the lowest fitness value is the chicken and others are marked as hens. However, CSO is found to have a probability of the algorithm falling into local optimum. As such, the levy flight method is added to improve diversity and ensure global search capability. The fitness value to choose the CH is based on the energy consumption factor, the distance between CH and BS, and point cluster compactness. The evaluation of the algorithm shows that CSO outperformed LEACH by enhancing the network lifetime.In [103], the authors proposed an improved well-known multiobjective, nondominated sorting genetic algorithm (NSGA-II) for clustering in WSN, termed NSMC. The proposed method consists of 5 objectives to be optimized to select the best CH, where two are about energy, one is about distance, one about load balance, and the last is about the number of CHs. A procedure called release-random is added to prevent the solution where only the CH with one excellent objective value is chosen. NSMC performed better as compared to traditional NSGA-II in terms of lifespan and stable period by employing reduced energy consumption and efficient data transfer.In 2019, the usage of metaheuristic algorithms seemed to give the best solutions in CH selection, so the authors in [104] proposed a genetic algorithm- (GA-) based CH selection technique. A genetic algorithm is made with the concept of mutation and selection of chromosomes [105]. The fitness function of the nodes is calculated based on the distance of each sensor to the CH and the total distance from sensors to the BS and the CH. Since the fitness function in this paper does not focus on energy metrics, there is a high possibility of selecting a CH with a low energy level which might cause problems later. From the simulations, GA was able to extend the network lifetime by having a balanced load among the nodes as compared to K-means and LEACH algorithms.Daniel and Rao [106] proposed a mutation chemical reaction optimization algorithm based on an energy-efficient clustering protocol termed MCRO-ECP, under a multihop environment. In MCRO-ECP, two important operators are used, the turning operator and mutation operator. The turning operator is used to enhance the optimal quality and reliability of the algorithm, while the mutation operator is used to improve solution diversity and convergence of the algorithm. In selecting the CH, three functions are considered, which are the minimum distance between sensor nodes, minimum BS distance, and energy ratio. From the simulation, it was observed that MCRO-ECP performed well compared to existing protocols in terms of total energy consumption, network lifetime, number of data packets received by the BS, and convergence rate.In [107], the authors proposed an optimal LEACH with an improved bat algorithm in WSNs to enhance the CH selection method. Bat algorithm (BA) is the principle of echolocation used in bat predation. In this literature, the authors improved the algorithm with the inclusion of triangle flip and curve strategy in BA based on LEACH (FTBA-TC-LEACH) to improve global search performance, as initially, bat algorithm had more exploitation capability. Initially, a temporary CH is chosen based on residual energy, and then, a modified BA is applied to find the optimal position of the CH. Simulations on three different curve shapes and six different parameter combinations were made, where FTBA-TC-LEACH performed better than some existing algorithms.Lavanya and Shanker got inspired by the energetic searching and gliding behavior of flying squirrels and proposed a CH selection method using a squirrel search algorithm (SSA) in a homogeneous network [108]. In this literature, the energy of nodes acts as the food source while the squirrel movement is the changing location of the CH. The authors also introduced seasonal monitoring conditions, gliding constant, and predator presence probability to avoid the algorithm from falling into local optima and to give a balance between the exploration and exploitation capability. The CHs are selected based on a fitness function that considers energy and distance. From the simulations, even though the first node had died quicker in SSA as compared to other metaheuristic algorithms, it was found to perform better at the end, than any other algorithms, and helped in extending the network lifetime.In the same year, another energy-efficient clustering technique in WSNs was proposed by the authors in [109] using a yellow saddle goatfish algorithm (YSGA). YSGA is divided into subpopulations by the K-means algorithm, and the individuals are categorized into two roles which are chaser and blocker. In every group, the individual with the best fitness value becomes the chaser, and the others become the blockers. Using this principle, the CH is selected by considering two main criteria, which are the distance from CH to BS and residual energy of the CH. YSGA was also later used to find optimal network configurations by using the optimal sets of selected CHs. The proposed algorithm was compared with several other algorithms where YSGA managed to increase network lifetime and provide robust communications.


### 5.2. Cluster Head Selection (Hybrid)

The hybrid metaheuristic method is the idea of combining components from different algorithms or search techniques to find the optimal solution [110]. Even though many new metaheuristic algorithms have been introduced in recent years, some algorithms do not have the balance between exploration and exploitation capabilities. This leads to problems such as falling into local optimum easily, slow convergence, and so on. As seen in the nonhybrid section, many metaheuristic algorithms include certain functions or methods to enhance the global search (exploration) and local search (exploitation) ability. The same concept is applied in hybridization, but it combines components of different metaheuristic algorithms or the algorithm itself to ensure a balance between exploration and exploitation capabilities in finding the optimal solution.In this section, the usage of hybrid metaheuristic algorithms in CH selection is explained in terms of various environmental settings. Figure10 describes the environmental settings and their related methods of CH selection.Figure 10
Taxonomy of cluster head selection using nonhybrid metaheuristic methods.


#### 5.2.1. Mobility

Mobile ad hoc networks (MANETs) are known to self-organize mobile devices that are autonomous and are able to move freely, making them an infrastructureless wireless network [111]. In the year 2019, Prasad and Balakrishna proposed an improved genetic algorithm with simulated annealing (SAGA) to improve network lifetime and energy efficiency in MANETs [112]. The CH in this literature is selected based on the CH degree and the energy value. The genetic algorithm has greater global search capability but has problems such as slow convergence rate and weak local search capability. The authors claimed that SAGA would be able to overcome genetic algorithm limitations and large combinational optimization problems in MANETs. From the simulations, the SAGA protocol was able to select CHs with better performance compared to other existing protocols.


#### 5.2.2. Multihop Data Transmission

Kumar and Kumar in [113] proposed a new hybrid ABCACO algorithm which consists of the artificial bee colony (ABC) algorithm and the ant colony optimization (ACO) algorithm. Ant colony algorithm is based on the food hunting behavior of ants which use pheromone trails to communicate which each other. This paper focuses on tackling the squared optimization problem by dividing the field into subregions where ABC is used for CH selection and ACO is used to get optimized routing in a multihop WSN environment. The CH selection process is achieved by using a fitness function that contains the parameters such as communication energy and the distance from nodes to the BS. A subcluster head (SCH) is also selected using the fitness function in each subregion part to communicate with nodes and the CH. The authors also discussed the use of the proposed scheme in fire detection real-time application. ABCACO managed to decrease the communication distance and increase network lifetime, stability, and goodput compared to few existing algorithms.Energy-efficient cluster head selection and routing (ECHSR) in disaster management in IoT networks was researched by the authors in [1]. In this literature, an improved hybrid particle swarm optimization (PSO) and harmony search algorithm (HSA) for CH selection is proposed. Later, a PSO-based multihop routing system with enhanced tree encoding is adopted for data transmission. For the CH selection based on the proposed algorithm, a fitness function is evaluated based on energy-efficiency criterion, cluster closeness, and network coverage, to select the optimal CH. To evaluate the fitness function to have optimal solutions towards the multiobjective optimization problem (MOOP), an adaptive weighted sum (AWS) method is used. The proposed method was simulated in a forest fire scenario by varying sink locations, where ECHSR performed better compared to some related methods.Prolonging network lifetime is the main objective of many WSNs research studies, which led the authors of [114] to propose an enhanced-LEACH (E-LEACH) algorithm that uses grey wolf optimization (GWO) and discrete particle swarm optimization (D-PSO) to have an optimal CH and helper CH (HCH) selection in a multihop environment. HCH is selected to reduce the burden of the CH and to have balanced energy dissipation. During the CH selection process, the GWO takes a random number and residual energy as input, whereas D-PSO takes distance and centrality as input. These inputs are processed in parallel to select the CH and HCH. The proposed E-LEACH achieved a longer network lifetime by reducing energy consumption compared to other algorithms.In recent years of research, a multiweighted chicken swarm based genetic algorithm (MWCSGA) for energy-efficient clustering in multihop WSNs was proposed in [115]. The GA’s crossover and mutation operators are embedded into the chicken swarm optimization (CSO) algorithm to ensure diversity in obtaining the optimal solution. The efficient CH is selected by considering the energy consumption, distance between CH and BS, and distance between node and CH in fitness function evaluation. The multiweights in terms of localization of nodes and their residual energy are also added before selecting the CH, to reduce energy consumption. From the simulations, it was evaluated that MWCSGA performed better as compared to several existing state of the art methods in terms of energy efficiency, end-to-end delay, throughput, and packet delivery ratio.


#### 5.2.3. Single-Hop Data Transmission

The capability of ABC in yielding optimal solutions has pulled some researchers to hybridize ABC with different algorithms to obtain the best optimal solution. As such, authors in [116] proposed a hybrid clustering protocol based on a metaheuristic approach (CPMA) using the artificial bee colony (ABC) algorithm and harmony search algorithm (HSA) in a single-hop network structure. The CH is selected based on HSA, where two factors are considered, which are total energy cost and the predicted energy distribution ratio. On the other hand, ABC is used to tune the CH ratio and weight factor in fitness function so that the most optimal CH is selected. Simulations were made with varying BS locations, where CPMA managed to prolong the network lifetime and increase the throughput compared to some existing methods.


#### 5.2.4. Heterogeneity

In [117], the authors proposed a hybrid approach to optimize clustering in WSNs. The hybrid approach considers genetic algorithm (GA) and particle swarm optimization (PSO), termed as (GAPSO-H), where GA is used to select the optimal CH and PSO is used to select optimal routing for the mobile sink in a heterogeneous network. Three levels of energy heterogeneity are deployed which are supernode, advanced node, and normal nodes. The fitness function that is used to select the best CH comprises of five fitness parameters which are residual energy, average energy, the distance between sink and node, number of neighbors, and energy consumption rate. The proposed GAPSO-H outperformed several existing algorithms as it achieved an improved stability period.


#### 5.2.5. Other Parameters

In this section, we have summarized few hybrid metaheuristic methods used for CH selection that lack environmental information from literature, because the papers solely focus on the CH selection process closely. All the literature discussed below uses a homogeneous network setup with static nodes which can be denoted as a standard setup.The authors in [118] proposed a CH selection algorithm based on fuzzy clustering and particle swarm algorithm (FCPSO). Initially, a subset is formed according to nodes’ locations by using fuzzy clustering. The cluster head selection in this method is done by using particle swarm optimization (PSO) with inertia weight. PSO is used to minimize the objective functions which are used for CH selection, which are maximum average distance, maximum distance from CH to BS, and total energy consumption. From the simulation, it was observed that FCPSO reduced the mortality rate of the nodes and extended the network lifetime.A hybrid harmony search algorithm (HSA) and PSO (HSA-PSO) were proposed in [119] for energy-efficient CH selection in WSNs. HSA is based on the concept of finding the pleasing harmony by a musician, and HSA is deemed to have good exploration capability [120]. The proposed algorithm gives a balance between global search and local search to obtain the optimal CH. The CH is selected based on Euclidean distance f1and the ratio of initial energy of nodes f2, where the objective functions fobj are calculated with the inclusion of scaling factor ε, as shown below:
(12)fobj=ε×f1+1−ε×f2.The proposed algorithm managed to have a higher searching capability in high-dimensional problems and outperformed the nonhybridized algorithm in terms of network lifetime and throughput.In the year 2017, Yadav and Kumar proposed a teaching learning-based optimization (TLBO) algorithm based on the LEACH protocol (LEACH-T) for CH selection in WSNs [121]. The TLBO algorithm is based on the classroom concept of teacher and learner. Two modifications are made to TLBO in the CH selection phase, which are the implementation of genetic crossover and mutation operators to improve the convergence rate. The CH is selected based on the fitness function that evaluates the energy consumed in data transmission. From the comparison with traditional LEACH, LEACH-T has better performance in terms of live nodes and packets sent.The authors of [122] proposed a hybrid approach for optimal CH selection using LEACH and monkey search algorithm (MSO), termed as LEACH-MS. MSO is slightly similar to the aforementioned spider monkey optimization (SMO) [89], where it is on the concept of how monkeys search for food by climbing trees. In this paper, the CHs are chosen in two different ways. Initially, for the first 600 rounds, the selection is done through random numbers and the threshold value, which is using the LEACH process of CH selection. After 600 rounds, the CH is selected based on the MSO algorithm by considering the distance of nodes to the BS and residual energy. The proposed hybrid algorithm was able to increase network lifetime and throughput compared to the nonhybrid LEACH and MSO algorithms.In [123], the authors proposed a hybrid artificial bee colony and monarch butterfly optimization algorithm (HABC-MBOA) for optimal CH selection in WSNs. MBOA is based on the migration of butterflies from one area to another [124]. In this literature, the algorithm is proposed to prevent the solutions from falling into local optimal by replacing the employee bee phase of ABC with a mutated butterfly adjusted operator. The CH selection is done based on residual energy, the distance between CH and BS, and intercluster distance. The simulation was carried out with a huge number of sensors and varying sink positions and showed that the proposed algorithm outperforms several existing algorithms in terms of the number of nodes alive and the throughput.Lavanya and Shanker proposed an energy-efficient CH selection algorithm using a hybrid squirrel harmony search algorithm (SHSA) in a homogeneous WSN [125]. The nonhybrid squirrel search algorithm (SSA) was introduced in the year 2020, as discussed in the nonhybrid section. The main objective for the authors to introduce a hybrid method was to have a balance between the exploration and exploitation capability, where SSA, which has a good global search ability and harmony search algorithm (HSA) displays high search efficiency in a search space. The CH is selected based on the fitness function used by SHSA, which contains energy and separation energy as the fitness parameters. The SHSA was found to outperform the nonhybrid version by having an extended first node death, making it extend network lifetime by increasing the energy efficiency.Another new hybrid metaheuristic algorithm for CH selection proposed by the authors in [126] is called a new fitness-based glowworm swarm with fruitfly algorithm (FGF), which hybridizes glowworm swarm optimization (GSO) and fruitfly optimization algorithm (FFOA). The concept of GSO is based on a luminescence amount called luciferin of glowworm, to determine its movement and its neighbors [127], whereas FFOA is based on the concept of the food searching behavior of fruit flies. GSO and FFOA have some limitations such as poor local search capability and less convergence rate, respectively. To perform effective CH selection, the algorithms are hybridized to solve the problems above and certain parameters such as distance, delay, and energy utilized are used in fitness calculation. The comparison of FGF with some hybrid and nonhybrid algorithms showed that FGF performed better in terms of nodes being alive and energy consumption.Since many researchers implemented metaheuristic methods to optimize the CH selection and to obtain an energy-efficient network, Alghamdi proposed a hybrid concept of dragonfly algorithm (DA) and firefly algorithm (FF), termed firefly replaced position update in dragonfly (FPU-DA) [128]. The basic ideas of dragonfly and firefly algorithms are discussed in [80, 84], respectively. Treating DA and FF separately poses some limitations such as reduced internal memory and slow convergence. As such, the conventional levy update process of DA is replaced by the FF position update process to improve the convergence. The CH is selected by the proposed algorithm by considering four criteria which are energy, delay, distance, and security. Comparison results of FPU-DA with some state-of-the-art algorithms show that the proposed algorithm has better convergence, network lifetime, and normalized energy.The authors in [129] proposed a hybrid approach of firefly algorithm with particle swarm optimization (HFAPSO). LEACH-C [130], which was proposed earlier, uses the simulated annealing algorithm in CH selection, which causes more computation process time and consumes more energy. To overcome this issue, HFAPSO is embedded in LEACH-C to obtain optimal CHs to improve network lifetime, where the fitness function is evaluated using the remaining energy of the nodes and the distance between nodes and the CH. HFAPSO in the LEACH-C algorithm managed to prolong network lifetime and reduce energy consumption compared to the firefly algorithm and conventional LEACH-C algorithm.Moreover, in [131], the authors discussed hybrid grey wolf optimizer-based sunflower optimization (HGWSFO) to determine energy-efficient CHs in a homogeneous network environment. This proposed algorithm is also introduced to balance the exploration and exploitation capabilities, because grey wolf optimization (GWO) algorithm might fall into local optimum easily, and sunflower optimization (SFO) algorithm may have slower convergence rate. GWO follows the concept of a wolf pack that consists of leaders that are female, and a male termed as α who decides on sleeping location, time for walking and hunting, and all the other activities (exploitation). On the other hand, SFO is a method that uses the law of radiation to reduce the distance between the plant and the sun to get better sunlight (exploration). In CH selection, energy and distance constraints are used by the objective function of HGWSFO to have the most optimal CH selected. HGWSFO outperformed some existing state-of-art algorithms in terms of network lifetime and stability.


### 5.3. Cluster Formation

Similar to nonmetaheuristic algorithms, the metaheuristic approach uses two popular cluster formation methods which are unequal clustering andK-means clustering, followed by CH selection using a metaheuristic algorithm. In this section, the cluster formation phase will be discussed further to understand the impact of these popular techniques, which will then influence a better network deployment, as described in Figure 11.Figure 11
Taxonomy of cluster formation with metaheuristic methods.Sangeetha and Sabari in the year 2018 published two papers [132, 133] that discuss both unequal clustering (UC) and K-means clustering (KC) approaches with metaheuristic methods. These literature works were proposed to improve network lifetime by reducing energy consumption in mobile WSNs. In the first paper, the authors discuss the implementation of PSO in unequal clustering (UC-PSO) and K-means clustering (KC-PSO) approaches. In UC-PSO, the CH is selected first based on mobility metric, residual energy, neighbor’s connectivity, and distance from CH to BS. After that, the member nodes join the CH, forming unequal clusters, to prevent the CH of the cluster near to the BS from dying quickly. On the other hand, in KC-PSO, the clusters are partitioned into equal sizes first, and then, an optimal CH is selected based on PSO. The two proposed methods were compared with LEACH and from the results, it was deduced that KC-PSO performed better in terms of reduced energy consumption and enhancing the network lifetime.In the second paper by the same authors, the implementation of GA in unequal clustering (UC-GA) andK-means clustering (KC-GA) approaches was done. UC-GA and KC-GA have a similar process as UC-PSO and KC-PSO. In UC-GA, the CH is selected initially using the same parameters mentioned above and then the unequal clusters are formed, and in KC-GA, the partition of clusters is performed initially before selecting the CH for each partition. The usage of GA in this literature enables the network to have more stability in dynamic clustering problems. The results from the simulation show that KC-GA performs better in terms of reduced energy consumption and enhancing the network lifetime as compared to UC-GA and LEACH. To put it in a nutshell, the K-means clustering algorithm performs better than the unequal clustering approach. The limitation of both pieces of literature is that they did not compare the clustering approaches to determine which performs better in terms of the usage of different metaheuristic algorithms.Even thoughK-means has better performance compared to unequal clustering, deploying K-means can be tedious, and selecting the wrong k value might affect the whole network. Therefore, unequal clustering, which can dynamically create clusters, is given more attention in recent years. The authors in [134] proposed a metaheuristic ant colony optimization (ACO) based on unequal clustering (MHACO-UC) in WSNs. Initially, the network is set up for a few different scenarios that vary the location of the BS. Then, the neighboring nodes are identified for clustering, and unequal clusters are formed to achieve balanced energy consumption. The nodes join the cluster based on the single-hop transmission and the concept of rendezvous node (Rnode) is introduced, where Rnode is chosen by the CH based on proximity to help CH transfer data to the BS. The simulation under different scenarios shows that MHACO-UC enhances the network performance efficiently.The success of unequal clustering in solving energy hole problems has lured the authors of [135] to propose an energy-efficient nonuniform clustering routing protocol (E2NUCR). Nonuniform clustering in this literature is done by the calculation of the prior probability of data distribution to form a prior knowledge Pi based on the degree of similarity of data packets and the distance of the node from the sink. If the Pi values of nodes are similar, then they will be in the same cluster. Later, an improved shuffled frog leaping algorithm (ISFLA) is introduced for optimal CH selection, where ISFLA is based on the concept of the movement direction of frogs. The proposed E2NUCR was able to improve energy efficiency and network lifetime.In [136], the authors proposed an energy-balanced cluster-routing protocol (EBCRP) based on PSO with five mutation operators. PSO is known to have the issue of falling into local optimum easily [137]. So, it is hybridized with 5 mutation operators to improve the diversity, so that the algorithm will have good exploration capability and would not fall to local optimum easily. PSO with five mutation operators is used to optimally determine the number of clusters and to group the sensor nodes into clusters evenly by optimizing the number of clusters and their centroids. The CH is selected considering the residual energy based on CH rotation in each round, to achieve balanced energy consumption. Based on the simulation results, it can be inferred that EBCR can prolong the network lifetime by better balancing the energy consumption as compared to some other methods.


### 5.4. Parameter and Environmental Setting Analysis of Metaheuristic Methods

The simulation parameters used and the environment settings from all the aforementioned techniques in nonhybrid and hybrid metaheuristic clustering are analyzed and compared in Table4.Table 4
The comparison analysis of simulation parameters and environmental settings of metaheuristic clustering.
Paper (year)CH selectionCluster formationHybrid/ nonhybridSelection criteriaData transmissionMobilitySensor typeNetwork dimensionNo. of nodesPacket lengthSensor initial energyLocation of BS[84] (2015)EPSO-CEO—NonhybridAverage distance and average energy of the member nodesMultihopStaticHomogeneous200m×200m100—3 J—[118] (2015)FCPSO—HybridEnergy consumption and distance factorsN/SStaticBoth500m×500m100500 bytes0.5, (0.3 J-0.7 J)(250, 250), (500, 575)[85] (2016)BAFSA—NonhybridEnd to end delay and energyMultihopStaticHomogeneous2000m×2000m100-1000625 bytes0.5 J—[86] (2016)ABC—NonhybridEnergy, distance between CH and BSMultihopStaticHomogeneous100m×100m35, 75, 150, 195, 250625 bytesN/S—[100] (2016)PSO-ECHS—NonhybridIntracluster distance, sink distance and residual energy of sensor nodes.N/SStaticHomogeneous200m×200m300–700500 bytes2 J(100–300), (100–300)[113] (2016)ABCACO—HybridEnergy and distanceMultihopStaticHomogeneous100m×100m200m×200m, 300m×300m100, 225—0.5 J, 1 J(50, 50)[119] (2016)HSA-PSO—HybridResidual energy and distanceN/SStaticHomogeneous100m×200m100512 bytes0.5 J(50,150)[87] (2017)FFCHSA—NonhybridEnd-to-end delay, packet delivery ratio and energy consumption.MultihopStaticHomogeneous1250m×1250m100—40 J—[95] (2017)INSPSO—NonhybridResidual energy and distanceMultihopStaticHeterogenous500m×500m300, 400, 500Gateway=10J(500,250)Nodes=2J[101] (2017)WOA-C—NonhybridResidual energy of the node and the sum of energy of adjacent nodes.N/SStaticHomogeneous100m×100m100, 300, 500500 bytes0.5 J(50×50), (100×100, (50×200)[102] (2017)CSO—NonhybridEnergy consumption, distance between CH and BS, and cluster compactnessN/SStaticHomogeneous100m×100m150256 bytes0.5 J(50, 150)[103] (2017)NSGA-II—NonhybridCrowding and ranking system to efficiently selecting the individualN/SStaticHomogeneous200m×200m48-96500 bytes0.5nJ-100, 100[121] (2017)LEACH-T—HybridResidual energyN/SStaticHomogeneous100m×100m100—0.5 JCenter of the network[122] (2017)LEACH-MS—HybridResidual energy and distanceN/SStaticHomogeneous100m×100m150256 bytes0.5 J-50,150[82] (2018)BeeWSN—NonhybridThe remaining energy of node, degree, speed, and directionN/SMobileHomogeneous3000m×3000m×3000m<200175 bytesN/S—[88] (2018)iCSHS—NonhybridResidual node energy, degree of node, intra-cluster distance and coverage ratio.MultihopStaticHomogeneous200m×200m100-300500 bytes0.5 J, 2 J, 200 J(100, 100), (150, 50), (200, 200)[132](2018)—KC-GAUC-GA—Node residual energy, connectivity degree, distance from sensor node to BS, and mobility factor.MultihopStaticHomogeneous100m×100m200512 bytes2 J(50, 175)[133](2018)—KC-PSOUC-PSO—Mobility metric, residual energy, neighbor’s connectivity, and distance from the CH to the BS.MultihopStaticHomogeneous100m×100m200512 bytes2 J(50, 175)[83] (2019)BICIoD—NonhybridResidual energy level and position of the drones.MultihopMobileHomogeneous1000m×1000m, 2000m×2000m, 3000m×3000m15, 20, 25, 30, 35—80 Wh—[89] (2019)SSMOECHS—NonhybridNode distribution, node energy, distanceMultihopStaticBoth100m×100m100800 bytes1 J, (0.5-1 J)-50, 150[92] (2017)FCR—NonhybridEnergy, distance, and delaySingle hopStaticHomogeneous100m×100mN/S—0.5 JCenter of the network[81] (2019)MO-GSA—NonhybridDistance of nodes to their corresponding cluster head and remaining energySingle hopStaticHomogeneous100m×100m100800 bytes0.5 J(50, 175)[93] (2019)IAPSO—NonhybridResidual energy ratio and energy consumption balance degreeSingle hopStaticHomogeneous500m×500m100-200500 bytes2 J-250,250[10] (2019)EWA—NonhybridEnergy, distance, and delayMultihopStaticHeterogenous100m×100m100—0.5 JCenter of the network[96] (2019)GAOC—NonhybridResidual energy, distance to the sink, and node density.Single hopStaticHeterogenous100m×100m, 500m×500m100, 200250 bytes0.5 J—[97] (2019)EC-PSO—NonhybridNodes close to the energy centersMultihopStaticHeterogenous1000m×1000m400125 bytes0.5 JCenter of the network[104] (2019)GA based clustering—NonhybridHighest residual energy and lowest distance to BSN/SStaticHomogeneous100m×100m404 bytes1000 JCenter of the network[106] (2019)MCRO-ECP—NonhybridNeighbor node distance, base station distance, ratio of energy, intra-cluster distance, and CH node degreeN/SStaticHomogeneous400m×400m200, 400, 600, 800, 1000512 bytes2 J(0, 0)[107] (2019)FTBA-TC-LEACH—NonhybridResidual energyN/SStaticHomogeneous100m×100m100500 bytes0.5 J(50, 50)[112] (2019)SAGA—HybridResidual energy and distanceSingle hopMobileHomogeneous1000m×1000m150780 bytes10 J—[123] (2019)HABC-MBOA—HybridResidual energy, distance between the cluster head, the base station and intercluster distance extracted from the network.N/SStaticHomogeneous400m×400m1000512 bytes0.5 JCenter of the network[125] (2019)SHSA—HybridEnergy and separation energyN/SStaticHomogeneous100m×100m100512 bytes0.5 J—[126] (2019)FGF—HybridEnergy, the distance among nodes, packet delayN/SStaticHomogeneous100m×100m100—0.5 JCenter of the network[134] (2019)—MHACO-UC—Proximity, residual energy, and link quality factor (LQF)MultihopStaticHomogeneous200m×200m, 400m×400m, 600m×600m100-800150-512 bytes1000 mJCorner, center and top level of network[90] (2020)PBC-CP—NonhybridNode’s energy, degree of node, and distance from base station to nodeMultihopStaticHomogeneous100m×200m100512 bytes0.5 J(50, 150)[91] (2020)Memetic algorithm—NonhybridNode degree, intracluster communication cost, and residual energy.MultihopStaticHomogeneous400m×400m200500 bytes2 J(0,0)[98] (2020)TGDEEC—NonhybridResidual energy and distanceMultihopStaticHeterogenous100m×100m50—0.5 JCenter of the network[99] (2020)SBHRA/ ABC—NonhybridResidual energy and distanceSingle hopStaticHeterogenous400m×400m400500 bytes0.5 J—[108] (2020)SSA—NonhybridSensor nodes energy and distance between the interactive elementsN/SStaticHomogeneous100m×100m100512 bytes0.5 J—[109] (2020)YSGANonhybridDistance from CH to the base station and the residual energy of CHN/SStaticHomogeneous100m×100m100500 bytes0.07 JCenter of the network[1] (2020)ECHSR—HybridEnergy efficiency criterion (EE), cluster closeness (CC) and network coverage (NC).MultihopStaticHomogeneous100m×200m100512 bytes0.5 J(50, 150), (100, 100), (0, 100), (50, 200)[114] (2020)E-LEACH—HybridGWO takes a random number and residual energyD-PSO takes distance and centrality as inputMultihopStaticHomogeneous1000m×1000m50512 kilobytes100 JCenter of the network[116] (2020)CPMA—HybridTotal energy cost and energy distribution ratioSingle hopStaticHomogeneous200m×200m100500 bytes1 J(100, 100), (100, 200), (0, 200)[117] (2020)GAPSO-H—HybridEnergy, distance, node degree, average energy, and energy consumption rate (ECR).MultihopStaticHeterogenous100m×100m, 500m×500m100, 200250 bytes0.5 J—[128] (2020)FPU-DA—HybridEnergy, delay, distance, and security.N/SStaticHomogeneous100m×100m100—0.5 JCenter of the network[129] (2020)HFAPSO—HybridEnergy and average distanceN/SStaticHomogeneous100m×100m100500 bytes1–5 J(50, 175)[131] (2020)HGWSFO—HybridDistance and energyN/SStaticHomogeneous200m×200m100—0.5 J—[135] (2020)—E2NUCR—Residual energy factor, location factor within clusters, and location factor between clustersMultihopStaticHomogeneous200m×200m400—0.5 J(100, 250)[136] (2020)—EBCRP—Residual energyN/SStaticHomogeneous100m×100m50-200500 bytes0.1 J—[94] (2021)FA-ROA—NonhybridEnergy, distance and delay, load, and temperatureSingle hopStaticHomogeneous100m×100m100—0.5 JCenter of the network[115] (2021)MWCSGA—HybridEnergy consumption, distance between the CH and the BS, and the distance between nodes and the CH.MultihopStaticHomogeneous1000m×1000m100500 bytes0.5 J—∗N/S: not stated.


## 5.1. Cluster Head Selection (Nonhybrid)

Metaheuristic methods are where a nature-inspired or bioinspired theory is converted to mathematical computations to solve optimization problems. The word metaheuristic is split into two, meta and heuristic, where meta means a high-level methodology and heuristic refers to a technique of solving problems by finding new strategies [80]. To achieve an optimal solution, it is very important for the metaheuristic algorithm to balance its exploration and exploitation capability so that the algorithm does not fall into local optimum easily or has a slow convergence rate [81]. A nonhybrid metaheuristic method refers to an algorithm that has no inclusions of other techniques’ algorithmic components to solve optimization problems. This will be further discussed below in this section.In this section, the usage of nonhybrid metaheuristic algorithms in CH selection is explained in terms of various environmental settings. Figure9 describes the environment settings and their related methods of CH selection.Figure 9
Taxonomy of cluster head selection using nonhybrid metaheuristic methods.


### 5.1.1. Mobility

In 2018, the authors of [82] proposed a honeybee algorithm to select CHs in a mobile WSN (BeeWSN). In this, the selection criteria of CH selection are based on the remaining energy of the node, degree, speed, and direction. In the honeybee algorithm, two types of bees are identified, the onlooker and employed bees. The onlooker bees are the control packets that search for the most suitable CH by using the selection criteria, while the employed bees are data packets. This algorithm is deemed to have good exploration in the form of onlooker bees and exploitation in the form of employed bees. From the simulations, it was seen that BeeWSN forms more balanced clusters compared to some existing methods.Mobile WSNs have limitations of frequent topology changes and scalability issues. In [83], the authors proposed a bioinspired clustering scheme using the dragonfly algorithm (DA) for the internet of drone application (BICIoD) to handle the issues. Dragonflies have two swarming behaviors called static swarming (finding food), which promotes exploitation, and dynamic behavior (migration), which promotes exploration capability. In this proposed method, the CH is selected using connectivity to BS, residual energy, and position of drones. The formed clusters are then managed by DA, where the cluster members need to follow the movement of the CHs and adjust themselves. Comparison of BICIoD with other algorithms proved that BICIoD performs better in terms of cluster lifetime, energy consumption, and delivery rates.


### 5.1.2. Multihop Data Transmission

In the year 2015, the authors in [84] proposed an enhanced PSO-based clustering method for energy optimization termed as EPSO-CEO in a multihop data transmission environment. PSO is a theory based on the movement of particles where the position and velocity are updated till the global best solution is reached. The literature discusses cluster formation and CH selection based on centralized clustering by using PSO. A CH is selected based on the fitness function that involves the distance and energy using PSO, where the global best value achieved by PSO will be the CH of the particular cluster. The authors also precisely discuss inter- and intracluster multihop data transmission using distance and residual energy. The simulation showed that EPSO-CEO performs better by minimizing the energy consumption and enhancing the network lifetime, when compared with other competitive methodologies.Sengottuvelan and Prasath proposed another metaheuristic method for optimal CH selection called the breeding artificial fish swarm algorithm (BAFSA) in [85]. BAFSA is the modified version of AFSA, where the solutions are randomly split, and the network performs either a swarming or a following behavior. A tournament selection is also used to produce the best solutions. The fitness function based on end-to-end delay and energy is applied to BAFSA for an optimal CH to be selected. The proposed method not only had fast convergence, good fault tolerance, and good local search capability but also performed well in terms of reduced packet loss and enhancing the network lifetime, compared to some existing methods.Mann and Singh on the other hand, proposed another clustering and routing method for energy efficiency using artificial bee colony (ABC) in [86]. In this literature, ABC is used in a multihop and static environment. ABC is used in CH selection based on a fitness function that contains residual energy, the distance between CH and BS, and the distance between CH and CH as functions. ABC is then used to obtain optimized routing to have the least energy dissipation through communication. From the simulations, it could be observed that ABC performed better in terms of packet delivery, energy consumption, and throughput as compared to other algorithms.Since bioinspired algorithms tend to have fast convergence compared to nonmetaheuristic methods, more studies were conducted on metaheuristic methods. In 2017, the authors in [87] proposed a bioinspired algorithm, named firefly cluster head selection algorithm (FFCHSA). FFCHSA uses the fitness function based on energy, packet loss ratio, and end-to-end delay to select the CH in a multihop WSN, as discussed by the author in the introduction. From the simulations, it was seen that the proposed algorithm improves the overall performance compared to PSO and genetic algorithm (GA).By considering the hotspot problem, Gupta and Jha proposed an integrated clustering and routing protocol using cuckoo and harmony search (iCSHS) in WSNs [88]. The authors proposed two different algorithms for two different protocols, where cuckoo is used for clustering and harmony search is used for routing. Four different objectives have to be minimized in the objective function in improved cuckoo search to select the optimal CH, which are node energy, degree of a node, intracluster distance, and coverage of the CH. Multihop data routing is adopted in the literature by using improved harmony search to reduce communication energy consumption. A simulation based on the two different scenarios with varying sink locations showed that the proposed iCSHS performs better compared to some existing algorithms.In the year 2019, the authors of [89] proposed sampling-based spider monkey optimization and energy-efficient cluster head selection (SSMOECHS). This method was proposed to solve the location-based CH selection approach problems. Spider monkey optimization (SMO) is based on monkeys searching for food with good exploration capability. The CH is selected based on the sampling method of SMO where coverage and energy of notes are considered the objective function that must be maximized. The method is simulated through a homogeneous and heterogeneous environment by adopting multihop data transmission, which shows that SSMOECHS improved network lifetime and energy efficiency.Pathak proposed a proficient bee colony-clustering protocol (PBC-CP) in [90]. The concept of a bee colony is the same as the aforementioned method by [78], but in this research, it was implemented in a static and multihop data transmission environment because of the fast-searching feature of the algorithm. The fitness function is based on residual energy and node degree, used by the bee colony algorithm to select the CH efficiently. PBC-CP performed well in terms of extending network lifetime compared to several existing protocols.Chawra and Gupta proposed a load-balanced node clustering scheme using an improved memetic algorithm to solve the energy hole problem that occurs in a multihop WSN environment [91]. The CH in this scheme is selected based on node degree, intracluster communication distance, and residual energy, by having these parameters in the fitness function of the memetic algorithm. From the performance comparison with other existing algorithms, it was seen that the memetic algorithm performed better in terms of energy consumption and network lifetime.


### 5.1.3. Single Hop Data Transmission

Since the usage of the swarm intelligence algorithm shows many improvements in CH selection, Sarkar and Murugan proposed a CH selection and routing method based on firefly with cyclic randomization (FCR) in a single hop environment [92]. Comparing to [87], FCR replaces the firefly by following certain conditions in a particular cycle, and FCR can handle multiple objectives as well. The CHs are selected based on a cost function that includes distance, energy, and the delay as parameters. Simulation results show that FCR performs better than some existing algorithms.Mood and Javidi on the other hand proposed a modified gravitational search algorithm (GSA) in WSNs [81]. Since it is very important to have a balance between exploitation and exploration, GSA is modified with varying mass value over time and the inclusion of a tournament selection method. Modified GSA uses a fitness function based on the distance of nodes to the CH and residual energy to select the optimal CH. The proposed method was evaluated using several unimodal functions, basic multimodal functions, and composition functions, where modified GSA performed well in terms of network lifetime and delivery of data packets.Metaheuristic algorithms are not only used to achieve energy efficiency but they are also used for optimized area coverage, as discussed by Peng and Xiong in [93]. In this literature, improved adaptive PSO (IAPSO) is applied to solve coverage and energy optimization problems in a single-hop environment, where the inertia weight in PSO is adaptively changed for balance exploration and exploitation capability. To optimize the energy consumption problem, an optimal CH is selected based on the total residual energy ratio and energy consumption balance degree of CH candidates. Comparison with some existing algorithms shows that IAPSO performs well in terms of achieving balanced energy consumption.The authors of [94] proposed a multiobjective CH selection mechanism using a fitness averaged rider optimization algorithm (FA-ROA) in a single-hop smart city application. The multiobjectives that are optimized in this mechanism are the load, temperature, delay, and distance between nodes. ROA is based on the idea of a group of riders riding to reach a goal where it comprises bypass, follower, overtaker, and attacker riders. In this literature, ROA is improved in the processing of the group update phase to enhance performance. Simulation results show that FA-ROA managed to perform well in terms of delay, normalized energy, and alive nodes compared to some existing metaheuristic algorithms.


### 5.1.4. Heterogeneity

The authors in [95] proposed a multiobjective clustering and routing method in WSNs by using an improved nondominated sorting particle swarm optimizer (INSPSO). When we say multiple objectives, it means there is the inclusion of minimizing and maximizing objectives, where in this paper, the sum of residual energy must be maximized, and the energy consumption must be minimized to select the optimal CH. The performance evaluation is done by considering heterogeneous scenarios, where there are different numbers of sensors and gateways in the network. INSPSO performed well in selecting the CH through multiobjective factors efficiently by improving the network lifetime and reducing energy consumption.In the year 2019, a new bioinspired algorithm based on earthworm breeding in nature named earthworm optimization algorithm (EWA) was proposed by Pasupuleti and Balaswamy in [10]. In this algorithm, there are 2 types of nodes which are normal nodes and advanced nodes, where advanced nodes contain greater energy than normal nodes. EWA is used to select the optimal CH according to the highest fitness value based on energy and the distance between CH and nodes. In EWA, there are two types of breeding, where the first type is a reproduction by a single earthworm, and the second type is reproduction by varying number of parents and offspring. From the simulation, it was observed that EWA performed better in terms of delay, throughput, network lifetime, and energy consumption compared to GA and PSO.Later, in the same year, the authors of [96] proposed a genetic algorithm (GA) based on CH selection (GAOC) in heterogeneous WSNs. To solve the well-known hotspot problem, multiple data sinks are deployed in the network (MS-GAOC). Since it is focused on a heterogeneous network, three types of nodes are deployed, which are advanced, intermediate, and normal nodes with three different energy levels EADV, EINT, and ENRM, respectively.
(9)EADV=E0×1+α×n×m,(10)EINT=E0×1+β×n×m0,(11)ENRM=E0×1−m−m0×n.The energy fractions of advanced and intermediate nodes are denoted asα and β. The fitness function used in GA is based on energy factor, the distance between node and sink, and node density, which are used to select the optimal CH. Simulation shows that using a single data sink is efficient for a small area network and multiple data sinks fare better for a larger area of a network.In [97], the authors proposed a method to select the best CH and to avoid energy hole problems where energy centers are searched using PSO (EC-PSO). Initially, CHs are chosen using a geometric method as the nodes are homogeneous. After the network spends the first period, the network energy becomes heterogeneous and the PSO is executed to search the energy centers, so that a node near it will become the CH for the following period. The low-energy nodes are then protected from forwarding by using a threshold. The evaluation shows that EC-PSO performs better in terms of energy consumption and network lifetime compared to some existing methods.To have an energy-balanced and optimized WSN, the authors in [98] proposed an enhancement to the distributed energy-efficient clustering (DEEC) method by using the threshold game theory algorithm (TGDEEC). Game theory is a mathematical computation that facilitates decision-making scenarios. In this literature, heterogeneous networks with advanced nodes, normal nodes, and supernodes are assumed. TGDEEC uses a weighted factor β that considers CH and cluster member’s energy consumption to create a threshold. The CH is then selected by using the threshold and calculating the distance and energy used. TGDEEC is known to perform better compared to several other algorithms in terms of throughput and network lifetime.In [99], the authors proposed a clustering algorithm based on the section-based routing protocol (SBHRA) and artificial bee colony algorithm (ABC). SBHRA splits up the network into few sections with three types of nodes, namely, type-1, type-2, and type-3, making it a heterogeneous environment. The mechanism of ABC is similar to [82], but in this literature, it is deployed in a heterogeneous and sectioned environment. CH selection is done on type-2 and type-3 nodes’ regions by considering the residual energy parameter as a fitness function in ABC. The simulation of SBHRA, with the inclusion of ABC for CH selection, shows that network throughput, stability period, and lifetime is increased compared to other existing methods.


### 5.1.5. Other Parameters

Although the aforementioned papers have network environmental setting information, certain works do not mention the type of data transmission or do not impose significant environmental changes for the research to be carried out. Below are some summarized state-of-the-art methods that can be carried out in a static and homogenous network setup.The authors in [100] proposed the usage of particle swarm optimization for energy-efficient CH selection (PSO-ECHS). In this literature, parameters such as intracluster distance, sink distance, and residual energy of sensor nodes are considered for optimal energy-efficient CH selection using PSO. Simulation of the proposed algorithm is done based on a varying number of nodes, CHs, and the location of BS. PSO-ECHS performs better than some existing algorithms in terms of network lifetime, data packets delivered, and total energy consumption.In the year 2017, a new metaheuristic algorithm was introduced by Jadhav and Shanker, called whale optimization algorithm (WOA) for CH selection, termed as WOA-C [101]. WOA uses the concept of the hunting behavior of humpback whales, where the random or optimal search is used to hunt the prey (exploration) and a spiral bubble-net attacking mechanism is used to catch the prey (exploitation). The CH is chosen based on the node that has the highest fitness value, where the fitness function considers residual energy and number of neighbors for fitness calculation. From the simulations, WOA-C outperforms some contemporary existing protocols in terms of increased throughput, network lifetime, and stability period.Wang and Zhu were inspired by the usage of metaheuristic algorithms in WSNs and proposed a chicken swarm optimization (CSO) algorithm. CSO was introduced in [102] with the idea of having classification as a rooster (CH), hen, and chicken, where the highest fitness value is the rooster, and the lowest fitness value is the chicken and others are marked as hens. However, CSO is found to have a probability of the algorithm falling into local optimum. As such, the levy flight method is added to improve diversity and ensure global search capability. The fitness value to choose the CH is based on the energy consumption factor, the distance between CH and BS, and point cluster compactness. The evaluation of the algorithm shows that CSO outperformed LEACH by enhancing the network lifetime.In [103], the authors proposed an improved well-known multiobjective, nondominated sorting genetic algorithm (NSGA-II) for clustering in WSN, termed NSMC. The proposed method consists of 5 objectives to be optimized to select the best CH, where two are about energy, one is about distance, one about load balance, and the last is about the number of CHs. A procedure called release-random is added to prevent the solution where only the CH with one excellent objective value is chosen. NSMC performed better as compared to traditional NSGA-II in terms of lifespan and stable period by employing reduced energy consumption and efficient data transfer.In 2019, the usage of metaheuristic algorithms seemed to give the best solutions in CH selection, so the authors in [104] proposed a genetic algorithm- (GA-) based CH selection technique. A genetic algorithm is made with the concept of mutation and selection of chromosomes [105]. The fitness function of the nodes is calculated based on the distance of each sensor to the CH and the total distance from sensors to the BS and the CH. Since the fitness function in this paper does not focus on energy metrics, there is a high possibility of selecting a CH with a low energy level which might cause problems later. From the simulations, GA was able to extend the network lifetime by having a balanced load among the nodes as compared to K-means and LEACH algorithms.Daniel and Rao [106] proposed a mutation chemical reaction optimization algorithm based on an energy-efficient clustering protocol termed MCRO-ECP, under a multihop environment. In MCRO-ECP, two important operators are used, the turning operator and mutation operator. The turning operator is used to enhance the optimal quality and reliability of the algorithm, while the mutation operator is used to improve solution diversity and convergence of the algorithm. In selecting the CH, three functions are considered, which are the minimum distance between sensor nodes, minimum BS distance, and energy ratio. From the simulation, it was observed that MCRO-ECP performed well compared to existing protocols in terms of total energy consumption, network lifetime, number of data packets received by the BS, and convergence rate.In [107], the authors proposed an optimal LEACH with an improved bat algorithm in WSNs to enhance the CH selection method. Bat algorithm (BA) is the principle of echolocation used in bat predation. In this literature, the authors improved the algorithm with the inclusion of triangle flip and curve strategy in BA based on LEACH (FTBA-TC-LEACH) to improve global search performance, as initially, bat algorithm had more exploitation capability. Initially, a temporary CH is chosen based on residual energy, and then, a modified BA is applied to find the optimal position of the CH. Simulations on three different curve shapes and six different parameter combinations were made, where FTBA-TC-LEACH performed better than some existing algorithms.Lavanya and Shanker got inspired by the energetic searching and gliding behavior of flying squirrels and proposed a CH selection method using a squirrel search algorithm (SSA) in a homogeneous network [108]. In this literature, the energy of nodes acts as the food source while the squirrel movement is the changing location of the CH. The authors also introduced seasonal monitoring conditions, gliding constant, and predator presence probability to avoid the algorithm from falling into local optima and to give a balance between the exploration and exploitation capability. The CHs are selected based on a fitness function that considers energy and distance. From the simulations, even though the first node had died quicker in SSA as compared to other metaheuristic algorithms, it was found to perform better at the end, than any other algorithms, and helped in extending the network lifetime.In the same year, another energy-efficient clustering technique in WSNs was proposed by the authors in [109] using a yellow saddle goatfish algorithm (YSGA). YSGA is divided into subpopulations by the K-means algorithm, and the individuals are categorized into two roles which are chaser and blocker. In every group, the individual with the best fitness value becomes the chaser, and the others become the blockers. Using this principle, the CH is selected by considering two main criteria, which are the distance from CH to BS and residual energy of the CH. YSGA was also later used to find optimal network configurations by using the optimal sets of selected CHs. The proposed algorithm was compared with several other algorithms where YSGA managed to increase network lifetime and provide robust communications.


## 5.1.1. Mobility

In 2018, the authors of [82] proposed a honeybee algorithm to select CHs in a mobile WSN (BeeWSN). In this, the selection criteria of CH selection are based on the remaining energy of the node, degree, speed, and direction. In the honeybee algorithm, two types of bees are identified, the onlooker and employed bees. The onlooker bees are the control packets that search for the most suitable CH by using the selection criteria, while the employed bees are data packets. This algorithm is deemed to have good exploration in the form of onlooker bees and exploitation in the form of employed bees. From the simulations, it was seen that BeeWSN forms more balanced clusters compared to some existing methods.Mobile WSNs have limitations of frequent topology changes and scalability issues. In [83], the authors proposed a bioinspired clustering scheme using the dragonfly algorithm (DA) for the internet of drone application (BICIoD) to handle the issues. Dragonflies have two swarming behaviors called static swarming (finding food), which promotes exploitation, and dynamic behavior (migration), which promotes exploration capability. In this proposed method, the CH is selected using connectivity to BS, residual energy, and position of drones. The formed clusters are then managed by DA, where the cluster members need to follow the movement of the CHs and adjust themselves. Comparison of BICIoD with other algorithms proved that BICIoD performs better in terms of cluster lifetime, energy consumption, and delivery rates.


## 5.1.2. Multihop Data Transmission

In the year 2015, the authors in [84] proposed an enhanced PSO-based clustering method for energy optimization termed as EPSO-CEO in a multihop data transmission environment. PSO is a theory based on the movement of particles where the position and velocity are updated till the global best solution is reached. The literature discusses cluster formation and CH selection based on centralized clustering by using PSO. A CH is selected based on the fitness function that involves the distance and energy using PSO, where the global best value achieved by PSO will be the CH of the particular cluster. The authors also precisely discuss inter- and intracluster multihop data transmission using distance and residual energy. The simulation showed that EPSO-CEO performs better by minimizing the energy consumption and enhancing the network lifetime, when compared with other competitive methodologies.Sengottuvelan and Prasath proposed another metaheuristic method for optimal CH selection called the breeding artificial fish swarm algorithm (BAFSA) in [85]. BAFSA is the modified version of AFSA, where the solutions are randomly split, and the network performs either a swarming or a following behavior. A tournament selection is also used to produce the best solutions. The fitness function based on end-to-end delay and energy is applied to BAFSA for an optimal CH to be selected. The proposed method not only had fast convergence, good fault tolerance, and good local search capability but also performed well in terms of reduced packet loss and enhancing the network lifetime, compared to some existing methods.Mann and Singh on the other hand, proposed another clustering and routing method for energy efficiency using artificial bee colony (ABC) in [86]. In this literature, ABC is used in a multihop and static environment. ABC is used in CH selection based on a fitness function that contains residual energy, the distance between CH and BS, and the distance between CH and CH as functions. ABC is then used to obtain optimized routing to have the least energy dissipation through communication. From the simulations, it could be observed that ABC performed better in terms of packet delivery, energy consumption, and throughput as compared to other algorithms.Since bioinspired algorithms tend to have fast convergence compared to nonmetaheuristic methods, more studies were conducted on metaheuristic methods. In 2017, the authors in [87] proposed a bioinspired algorithm, named firefly cluster head selection algorithm (FFCHSA). FFCHSA uses the fitness function based on energy, packet loss ratio, and end-to-end delay to select the CH in a multihop WSN, as discussed by the author in the introduction. From the simulations, it was seen that the proposed algorithm improves the overall performance compared to PSO and genetic algorithm (GA).By considering the hotspot problem, Gupta and Jha proposed an integrated clustering and routing protocol using cuckoo and harmony search (iCSHS) in WSNs [88]. The authors proposed two different algorithms for two different protocols, where cuckoo is used for clustering and harmony search is used for routing. Four different objectives have to be minimized in the objective function in improved cuckoo search to select the optimal CH, which are node energy, degree of a node, intracluster distance, and coverage of the CH. Multihop data routing is adopted in the literature by using improved harmony search to reduce communication energy consumption. A simulation based on the two different scenarios with varying sink locations showed that the proposed iCSHS performs better compared to some existing algorithms.In the year 2019, the authors of [89] proposed sampling-based spider monkey optimization and energy-efficient cluster head selection (SSMOECHS). This method was proposed to solve the location-based CH selection approach problems. Spider monkey optimization (SMO) is based on monkeys searching for food with good exploration capability. The CH is selected based on the sampling method of SMO where coverage and energy of notes are considered the objective function that must be maximized. The method is simulated through a homogeneous and heterogeneous environment by adopting multihop data transmission, which shows that SSMOECHS improved network lifetime and energy efficiency.Pathak proposed a proficient bee colony-clustering protocol (PBC-CP) in [90]. The concept of a bee colony is the same as the aforementioned method by [78], but in this research, it was implemented in a static and multihop data transmission environment because of the fast-searching feature of the algorithm. The fitness function is based on residual energy and node degree, used by the bee colony algorithm to select the CH efficiently. PBC-CP performed well in terms of extending network lifetime compared to several existing protocols.Chawra and Gupta proposed a load-balanced node clustering scheme using an improved memetic algorithm to solve the energy hole problem that occurs in a multihop WSN environment [91]. The CH in this scheme is selected based on node degree, intracluster communication distance, and residual energy, by having these parameters in the fitness function of the memetic algorithm. From the performance comparison with other existing algorithms, it was seen that the memetic algorithm performed better in terms of energy consumption and network lifetime.


## 5.1.3. Single Hop Data Transmission

Since the usage of the swarm intelligence algorithm shows many improvements in CH selection, Sarkar and Murugan proposed a CH selection and routing method based on firefly with cyclic randomization (FCR) in a single hop environment [92]. Comparing to [87], FCR replaces the firefly by following certain conditions in a particular cycle, and FCR can handle multiple objectives as well. The CHs are selected based on a cost function that includes distance, energy, and the delay as parameters. Simulation results show that FCR performs better than some existing algorithms.Mood and Javidi on the other hand proposed a modified gravitational search algorithm (GSA) in WSNs [81]. Since it is very important to have a balance between exploitation and exploration, GSA is modified with varying mass value over time and the inclusion of a tournament selection method. Modified GSA uses a fitness function based on the distance of nodes to the CH and residual energy to select the optimal CH. The proposed method was evaluated using several unimodal functions, basic multimodal functions, and composition functions, where modified GSA performed well in terms of network lifetime and delivery of data packets.Metaheuristic algorithms are not only used to achieve energy efficiency but they are also used for optimized area coverage, as discussed by Peng and Xiong in [93]. In this literature, improved adaptive PSO (IAPSO) is applied to solve coverage and energy optimization problems in a single-hop environment, where the inertia weight in PSO is adaptively changed for balance exploration and exploitation capability. To optimize the energy consumption problem, an optimal CH is selected based on the total residual energy ratio and energy consumption balance degree of CH candidates. Comparison with some existing algorithms shows that IAPSO performs well in terms of achieving balanced energy consumption.The authors of [94] proposed a multiobjective CH selection mechanism using a fitness averaged rider optimization algorithm (FA-ROA) in a single-hop smart city application. The multiobjectives that are optimized in this mechanism are the load, temperature, delay, and distance between nodes. ROA is based on the idea of a group of riders riding to reach a goal where it comprises bypass, follower, overtaker, and attacker riders. In this literature, ROA is improved in the processing of the group update phase to enhance performance. Simulation results show that FA-ROA managed to perform well in terms of delay, normalized energy, and alive nodes compared to some existing metaheuristic algorithms.


## 5.1.4. Heterogeneity

The authors in [95] proposed a multiobjective clustering and routing method in WSNs by using an improved nondominated sorting particle swarm optimizer (INSPSO). When we say multiple objectives, it means there is the inclusion of minimizing and maximizing objectives, where in this paper, the sum of residual energy must be maximized, and the energy consumption must be minimized to select the optimal CH. The performance evaluation is done by considering heterogeneous scenarios, where there are different numbers of sensors and gateways in the network. INSPSO performed well in selecting the CH through multiobjective factors efficiently by improving the network lifetime and reducing energy consumption.In the year 2019, a new bioinspired algorithm based on earthworm breeding in nature named earthworm optimization algorithm (EWA) was proposed by Pasupuleti and Balaswamy in [10]. In this algorithm, there are 2 types of nodes which are normal nodes and advanced nodes, where advanced nodes contain greater energy than normal nodes. EWA is used to select the optimal CH according to the highest fitness value based on energy and the distance between CH and nodes. In EWA, there are two types of breeding, where the first type is a reproduction by a single earthworm, and the second type is reproduction by varying number of parents and offspring. From the simulation, it was observed that EWA performed better in terms of delay, throughput, network lifetime, and energy consumption compared to GA and PSO.Later, in the same year, the authors of [96] proposed a genetic algorithm (GA) based on CH selection (GAOC) in heterogeneous WSNs. To solve the well-known hotspot problem, multiple data sinks are deployed in the network (MS-GAOC). Since it is focused on a heterogeneous network, three types of nodes are deployed, which are advanced, intermediate, and normal nodes with three different energy levels EADV, EINT, and ENRM, respectively.
(9)EADV=E0×1+α×n×m,(10)EINT=E0×1+β×n×m0,(11)ENRM=E0×1−m−m0×n.The energy fractions of advanced and intermediate nodes are denoted asα and β. The fitness function used in GA is based on energy factor, the distance between node and sink, and node density, which are used to select the optimal CH. Simulation shows that using a single data sink is efficient for a small area network and multiple data sinks fare better for a larger area of a network.In [97], the authors proposed a method to select the best CH and to avoid energy hole problems where energy centers are searched using PSO (EC-PSO). Initially, CHs are chosen using a geometric method as the nodes are homogeneous. After the network spends the first period, the network energy becomes heterogeneous and the PSO is executed to search the energy centers, so that a node near it will become the CH for the following period. The low-energy nodes are then protected from forwarding by using a threshold. The evaluation shows that EC-PSO performs better in terms of energy consumption and network lifetime compared to some existing methods.To have an energy-balanced and optimized WSN, the authors in [98] proposed an enhancement to the distributed energy-efficient clustering (DEEC) method by using the threshold game theory algorithm (TGDEEC). Game theory is a mathematical computation that facilitates decision-making scenarios. In this literature, heterogeneous networks with advanced nodes, normal nodes, and supernodes are assumed. TGDEEC uses a weighted factor β that considers CH and cluster member’s energy consumption to create a threshold. The CH is then selected by using the threshold and calculating the distance and energy used. TGDEEC is known to perform better compared to several other algorithms in terms of throughput and network lifetime.In [99], the authors proposed a clustering algorithm based on the section-based routing protocol (SBHRA) and artificial bee colony algorithm (ABC). SBHRA splits up the network into few sections with three types of nodes, namely, type-1, type-2, and type-3, making it a heterogeneous environment. The mechanism of ABC is similar to [82], but in this literature, it is deployed in a heterogeneous and sectioned environment. CH selection is done on type-2 and type-3 nodes’ regions by considering the residual energy parameter as a fitness function in ABC. The simulation of SBHRA, with the inclusion of ABC for CH selection, shows that network throughput, stability period, and lifetime is increased compared to other existing methods.


## 5.1.5. Other Parameters

Although the aforementioned papers have network environmental setting information, certain works do not mention the type of data transmission or do not impose significant environmental changes for the research to be carried out. Below are some summarized state-of-the-art methods that can be carried out in a static and homogenous network setup.The authors in [100] proposed the usage of particle swarm optimization for energy-efficient CH selection (PSO-ECHS). In this literature, parameters such as intracluster distance, sink distance, and residual energy of sensor nodes are considered for optimal energy-efficient CH selection using PSO. Simulation of the proposed algorithm is done based on a varying number of nodes, CHs, and the location of BS. PSO-ECHS performs better than some existing algorithms in terms of network lifetime, data packets delivered, and total energy consumption.In the year 2017, a new metaheuristic algorithm was introduced by Jadhav and Shanker, called whale optimization algorithm (WOA) for CH selection, termed as WOA-C [101]. WOA uses the concept of the hunting behavior of humpback whales, where the random or optimal search is used to hunt the prey (exploration) and a spiral bubble-net attacking mechanism is used to catch the prey (exploitation). The CH is chosen based on the node that has the highest fitness value, where the fitness function considers residual energy and number of neighbors for fitness calculation. From the simulations, WOA-C outperforms some contemporary existing protocols in terms of increased throughput, network lifetime, and stability period.Wang and Zhu were inspired by the usage of metaheuristic algorithms in WSNs and proposed a chicken swarm optimization (CSO) algorithm. CSO was introduced in [102] with the idea of having classification as a rooster (CH), hen, and chicken, where the highest fitness value is the rooster, and the lowest fitness value is the chicken and others are marked as hens. However, CSO is found to have a probability of the algorithm falling into local optimum. As such, the levy flight method is added to improve diversity and ensure global search capability. The fitness value to choose the CH is based on the energy consumption factor, the distance between CH and BS, and point cluster compactness. The evaluation of the algorithm shows that CSO outperformed LEACH by enhancing the network lifetime.In [103], the authors proposed an improved well-known multiobjective, nondominated sorting genetic algorithm (NSGA-II) for clustering in WSN, termed NSMC. The proposed method consists of 5 objectives to be optimized to select the best CH, where two are about energy, one is about distance, one about load balance, and the last is about the number of CHs. A procedure called release-random is added to prevent the solution where only the CH with one excellent objective value is chosen. NSMC performed better as compared to traditional NSGA-II in terms of lifespan and stable period by employing reduced energy consumption and efficient data transfer.In 2019, the usage of metaheuristic algorithms seemed to give the best solutions in CH selection, so the authors in [104] proposed a genetic algorithm- (GA-) based CH selection technique. A genetic algorithm is made with the concept of mutation and selection of chromosomes [105]. The fitness function of the nodes is calculated based on the distance of each sensor to the CH and the total distance from sensors to the BS and the CH. Since the fitness function in this paper does not focus on energy metrics, there is a high possibility of selecting a CH with a low energy level which might cause problems later. From the simulations, GA was able to extend the network lifetime by having a balanced load among the nodes as compared to K-means and LEACH algorithms.Daniel and Rao [106] proposed a mutation chemical reaction optimization algorithm based on an energy-efficient clustering protocol termed MCRO-ECP, under a multihop environment. In MCRO-ECP, two important operators are used, the turning operator and mutation operator. The turning operator is used to enhance the optimal quality and reliability of the algorithm, while the mutation operator is used to improve solution diversity and convergence of the algorithm. In selecting the CH, three functions are considered, which are the minimum distance between sensor nodes, minimum BS distance, and energy ratio. From the simulation, it was observed that MCRO-ECP performed well compared to existing protocols in terms of total energy consumption, network lifetime, number of data packets received by the BS, and convergence rate.In [107], the authors proposed an optimal LEACH with an improved bat algorithm in WSNs to enhance the CH selection method. Bat algorithm (BA) is the principle of echolocation used in bat predation. In this literature, the authors improved the algorithm with the inclusion of triangle flip and curve strategy in BA based on LEACH (FTBA-TC-LEACH) to improve global search performance, as initially, bat algorithm had more exploitation capability. Initially, a temporary CH is chosen based on residual energy, and then, a modified BA is applied to find the optimal position of the CH. Simulations on three different curve shapes and six different parameter combinations were made, where FTBA-TC-LEACH performed better than some existing algorithms.Lavanya and Shanker got inspired by the energetic searching and gliding behavior of flying squirrels and proposed a CH selection method using a squirrel search algorithm (SSA) in a homogeneous network [108]. In this literature, the energy of nodes acts as the food source while the squirrel movement is the changing location of the CH. The authors also introduced seasonal monitoring conditions, gliding constant, and predator presence probability to avoid the algorithm from falling into local optima and to give a balance between the exploration and exploitation capability. The CHs are selected based on a fitness function that considers energy and distance. From the simulations, even though the first node had died quicker in SSA as compared to other metaheuristic algorithms, it was found to perform better at the end, than any other algorithms, and helped in extending the network lifetime.In the same year, another energy-efficient clustering technique in WSNs was proposed by the authors in [109] using a yellow saddle goatfish algorithm (YSGA). YSGA is divided into subpopulations by the K-means algorithm, and the individuals are categorized into two roles which are chaser and blocker. In every group, the individual with the best fitness value becomes the chaser, and the others become the blockers. Using this principle, the CH is selected by considering two main criteria, which are the distance from CH to BS and residual energy of the CH. YSGA was also later used to find optimal network configurations by using the optimal sets of selected CHs. The proposed algorithm was compared with several other algorithms where YSGA managed to increase network lifetime and provide robust communications.


## 5.2. Cluster Head Selection (Hybrid)

The hybrid metaheuristic method is the idea of combining components from different algorithms or search techniques to find the optimal solution [110]. Even though many new metaheuristic algorithms have been introduced in recent years, some algorithms do not have the balance between exploration and exploitation capabilities. This leads to problems such as falling into local optimum easily, slow convergence, and so on. As seen in the nonhybrid section, many metaheuristic algorithms include certain functions or methods to enhance the global search (exploration) and local search (exploitation) ability. The same concept is applied in hybridization, but it combines components of different metaheuristic algorithms or the algorithm itself to ensure a balance between exploration and exploitation capabilities in finding the optimal solution.In this section, the usage of hybrid metaheuristic algorithms in CH selection is explained in terms of various environmental settings. Figure10 describes the environmental settings and their related methods of CH selection.Figure 10
Taxonomy of cluster head selection using nonhybrid metaheuristic methods.


### 5.2.1. Mobility

Mobile ad hoc networks (MANETs) are known to self-organize mobile devices that are autonomous and are able to move freely, making them an infrastructureless wireless network [111]. In the year 2019, Prasad and Balakrishna proposed an improved genetic algorithm with simulated annealing (SAGA) to improve network lifetime and energy efficiency in MANETs [112]. The CH in this literature is selected based on the CH degree and the energy value. The genetic algorithm has greater global search capability but has problems such as slow convergence rate and weak local search capability. The authors claimed that SAGA would be able to overcome genetic algorithm limitations and large combinational optimization problems in MANETs. From the simulations, the SAGA protocol was able to select CHs with better performance compared to other existing protocols.


### 5.2.2. Multihop Data Transmission

Kumar and Kumar in [113] proposed a new hybrid ABCACO algorithm which consists of the artificial bee colony (ABC) algorithm and the ant colony optimization (ACO) algorithm. Ant colony algorithm is based on the food hunting behavior of ants which use pheromone trails to communicate which each other. This paper focuses on tackling the squared optimization problem by dividing the field into subregions where ABC is used for CH selection and ACO is used to get optimized routing in a multihop WSN environment. The CH selection process is achieved by using a fitness function that contains the parameters such as communication energy and the distance from nodes to the BS. A subcluster head (SCH) is also selected using the fitness function in each subregion part to communicate with nodes and the CH. The authors also discussed the use of the proposed scheme in fire detection real-time application. ABCACO managed to decrease the communication distance and increase network lifetime, stability, and goodput compared to few existing algorithms.Energy-efficient cluster head selection and routing (ECHSR) in disaster management in IoT networks was researched by the authors in [1]. In this literature, an improved hybrid particle swarm optimization (PSO) and harmony search algorithm (HSA) for CH selection is proposed. Later, a PSO-based multihop routing system with enhanced tree encoding is adopted for data transmission. For the CH selection based on the proposed algorithm, a fitness function is evaluated based on energy-efficiency criterion, cluster closeness, and network coverage, to select the optimal CH. To evaluate the fitness function to have optimal solutions towards the multiobjective optimization problem (MOOP), an adaptive weighted sum (AWS) method is used. The proposed method was simulated in a forest fire scenario by varying sink locations, where ECHSR performed better compared to some related methods.Prolonging network lifetime is the main objective of many WSNs research studies, which led the authors of [114] to propose an enhanced-LEACH (E-LEACH) algorithm that uses grey wolf optimization (GWO) and discrete particle swarm optimization (D-PSO) to have an optimal CH and helper CH (HCH) selection in a multihop environment. HCH is selected to reduce the burden of the CH and to have balanced energy dissipation. During the CH selection process, the GWO takes a random number and residual energy as input, whereas D-PSO takes distance and centrality as input. These inputs are processed in parallel to select the CH and HCH. The proposed E-LEACH achieved a longer network lifetime by reducing energy consumption compared to other algorithms.In recent years of research, a multiweighted chicken swarm based genetic algorithm (MWCSGA) for energy-efficient clustering in multihop WSNs was proposed in [115]. The GA’s crossover and mutation operators are embedded into the chicken swarm optimization (CSO) algorithm to ensure diversity in obtaining the optimal solution. The efficient CH is selected by considering the energy consumption, distance between CH and BS, and distance between node and CH in fitness function evaluation. The multiweights in terms of localization of nodes and their residual energy are also added before selecting the CH, to reduce energy consumption. From the simulations, it was evaluated that MWCSGA performed better as compared to several existing state of the art methods in terms of energy efficiency, end-to-end delay, throughput, and packet delivery ratio.


### 5.2.3. Single-Hop Data Transmission

The capability of ABC in yielding optimal solutions has pulled some researchers to hybridize ABC with different algorithms to obtain the best optimal solution. As such, authors in [116] proposed a hybrid clustering protocol based on a metaheuristic approach (CPMA) using the artificial bee colony (ABC) algorithm and harmony search algorithm (HSA) in a single-hop network structure. The CH is selected based on HSA, where two factors are considered, which are total energy cost and the predicted energy distribution ratio. On the other hand, ABC is used to tune the CH ratio and weight factor in fitness function so that the most optimal CH is selected. Simulations were made with varying BS locations, where CPMA managed to prolong the network lifetime and increase the throughput compared to some existing methods.


### 5.2.4. Heterogeneity

In [117], the authors proposed a hybrid approach to optimize clustering in WSNs. The hybrid approach considers genetic algorithm (GA) and particle swarm optimization (PSO), termed as (GAPSO-H), where GA is used to select the optimal CH and PSO is used to select optimal routing for the mobile sink in a heterogeneous network. Three levels of energy heterogeneity are deployed which are supernode, advanced node, and normal nodes. The fitness function that is used to select the best CH comprises of five fitness parameters which are residual energy, average energy, the distance between sink and node, number of neighbors, and energy consumption rate. The proposed GAPSO-H outperformed several existing algorithms as it achieved an improved stability period.


### 5.2.5. Other Parameters

In this section, we have summarized few hybrid metaheuristic methods used for CH selection that lack environmental information from literature, because the papers solely focus on the CH selection process closely. All the literature discussed below uses a homogeneous network setup with static nodes which can be denoted as a standard setup.The authors in [118] proposed a CH selection algorithm based on fuzzy clustering and particle swarm algorithm (FCPSO). Initially, a subset is formed according to nodes’ locations by using fuzzy clustering. The cluster head selection in this method is done by using particle swarm optimization (PSO) with inertia weight. PSO is used to minimize the objective functions which are used for CH selection, which are maximum average distance, maximum distance from CH to BS, and total energy consumption. From the simulation, it was observed that FCPSO reduced the mortality rate of the nodes and extended the network lifetime.A hybrid harmony search algorithm (HSA) and PSO (HSA-PSO) were proposed in [119] for energy-efficient CH selection in WSNs. HSA is based on the concept of finding the pleasing harmony by a musician, and HSA is deemed to have good exploration capability [120]. The proposed algorithm gives a balance between global search and local search to obtain the optimal CH. The CH is selected based on Euclidean distance f1and the ratio of initial energy of nodes f2, where the objective functions fobj are calculated with the inclusion of scaling factor ε, as shown below:
(12)fobj=ε×f1+1−ε×f2.The proposed algorithm managed to have a higher searching capability in high-dimensional problems and outperformed the nonhybridized algorithm in terms of network lifetime and throughput.In the year 2017, Yadav and Kumar proposed a teaching learning-based optimization (TLBO) algorithm based on the LEACH protocol (LEACH-T) for CH selection in WSNs [121]. The TLBO algorithm is based on the classroom concept of teacher and learner. Two modifications are made to TLBO in the CH selection phase, which are the implementation of genetic crossover and mutation operators to improve the convergence rate. The CH is selected based on the fitness function that evaluates the energy consumed in data transmission. From the comparison with traditional LEACH, LEACH-T has better performance in terms of live nodes and packets sent.The authors of [122] proposed a hybrid approach for optimal CH selection using LEACH and monkey search algorithm (MSO), termed as LEACH-MS. MSO is slightly similar to the aforementioned spider monkey optimization (SMO) [89], where it is on the concept of how monkeys search for food by climbing trees. In this paper, the CHs are chosen in two different ways. Initially, for the first 600 rounds, the selection is done through random numbers and the threshold value, which is using the LEACH process of CH selection. After 600 rounds, the CH is selected based on the MSO algorithm by considering the distance of nodes to the BS and residual energy. The proposed hybrid algorithm was able to increase network lifetime and throughput compared to the nonhybrid LEACH and MSO algorithms.In [123], the authors proposed a hybrid artificial bee colony and monarch butterfly optimization algorithm (HABC-MBOA) for optimal CH selection in WSNs. MBOA is based on the migration of butterflies from one area to another [124]. In this literature, the algorithm is proposed to prevent the solutions from falling into local optimal by replacing the employee bee phase of ABC with a mutated butterfly adjusted operator. The CH selection is done based on residual energy, the distance between CH and BS, and intercluster distance. The simulation was carried out with a huge number of sensors and varying sink positions and showed that the proposed algorithm outperforms several existing algorithms in terms of the number of nodes alive and the throughput.Lavanya and Shanker proposed an energy-efficient CH selection algorithm using a hybrid squirrel harmony search algorithm (SHSA) in a homogeneous WSN [125]. The nonhybrid squirrel search algorithm (SSA) was introduced in the year 2020, as discussed in the nonhybrid section. The main objective for the authors to introduce a hybrid method was to have a balance between the exploration and exploitation capability, where SSA, which has a good global search ability and harmony search algorithm (HSA) displays high search efficiency in a search space. The CH is selected based on the fitness function used by SHSA, which contains energy and separation energy as the fitness parameters. The SHSA was found to outperform the nonhybrid version by having an extended first node death, making it extend network lifetime by increasing the energy efficiency.Another new hybrid metaheuristic algorithm for CH selection proposed by the authors in [126] is called a new fitness-based glowworm swarm with fruitfly algorithm (FGF), which hybridizes glowworm swarm optimization (GSO) and fruitfly optimization algorithm (FFOA). The concept of GSO is based on a luminescence amount called luciferin of glowworm, to determine its movement and its neighbors [127], whereas FFOA is based on the concept of the food searching behavior of fruit flies. GSO and FFOA have some limitations such as poor local search capability and less convergence rate, respectively. To perform effective CH selection, the algorithms are hybridized to solve the problems above and certain parameters such as distance, delay, and energy utilized are used in fitness calculation. The comparison of FGF with some hybrid and nonhybrid algorithms showed that FGF performed better in terms of nodes being alive and energy consumption.Since many researchers implemented metaheuristic methods to optimize the CH selection and to obtain an energy-efficient network, Alghamdi proposed a hybrid concept of dragonfly algorithm (DA) and firefly algorithm (FF), termed firefly replaced position update in dragonfly (FPU-DA) [128]. The basic ideas of dragonfly and firefly algorithms are discussed in [80, 84], respectively. Treating DA and FF separately poses some limitations such as reduced internal memory and slow convergence. As such, the conventional levy update process of DA is replaced by the FF position update process to improve the convergence. The CH is selected by the proposed algorithm by considering four criteria which are energy, delay, distance, and security. Comparison results of FPU-DA with some state-of-the-art algorithms show that the proposed algorithm has better convergence, network lifetime, and normalized energy.The authors in [129] proposed a hybrid approach of firefly algorithm with particle swarm optimization (HFAPSO). LEACH-C [130], which was proposed earlier, uses the simulated annealing algorithm in CH selection, which causes more computation process time and consumes more energy. To overcome this issue, HFAPSO is embedded in LEACH-C to obtain optimal CHs to improve network lifetime, where the fitness function is evaluated using the remaining energy of the nodes and the distance between nodes and the CH. HFAPSO in the LEACH-C algorithm managed to prolong network lifetime and reduce energy consumption compared to the firefly algorithm and conventional LEACH-C algorithm.Moreover, in [131], the authors discussed hybrid grey wolf optimizer-based sunflower optimization (HGWSFO) to determine energy-efficient CHs in a homogeneous network environment. This proposed algorithm is also introduced to balance the exploration and exploitation capabilities, because grey wolf optimization (GWO) algorithm might fall into local optimum easily, and sunflower optimization (SFO) algorithm may have slower convergence rate. GWO follows the concept of a wolf pack that consists of leaders that are female, and a male termed as α who decides on sleeping location, time for walking and hunting, and all the other activities (exploitation). On the other hand, SFO is a method that uses the law of radiation to reduce the distance between the plant and the sun to get better sunlight (exploration). In CH selection, energy and distance constraints are used by the objective function of HGWSFO to have the most optimal CH selected. HGWSFO outperformed some existing state-of-art algorithms in terms of network lifetime and stability.


## 5.2.1. Mobility

Mobile ad hoc networks (MANETs) are known to self-organize mobile devices that are autonomous and are able to move freely, making them an infrastructureless wireless network [111]. In the year 2019, Prasad and Balakrishna proposed an improved genetic algorithm with simulated annealing (SAGA) to improve network lifetime and energy efficiency in MANETs [112]. The CH in this literature is selected based on the CH degree and the energy value. The genetic algorithm has greater global search capability but has problems such as slow convergence rate and weak local search capability. The authors claimed that SAGA would be able to overcome genetic algorithm limitations and large combinational optimization problems in MANETs. From the simulations, the SAGA protocol was able to select CHs with better performance compared to other existing protocols.


## 5.2.2. Multihop Data Transmission

Kumar and Kumar in [113] proposed a new hybrid ABCACO algorithm which consists of the artificial bee colony (ABC) algorithm and the ant colony optimization (ACO) algorithm. Ant colony algorithm is based on the food hunting behavior of ants which use pheromone trails to communicate which each other. This paper focuses on tackling the squared optimization problem by dividing the field into subregions where ABC is used for CH selection and ACO is used to get optimized routing in a multihop WSN environment. The CH selection process is achieved by using a fitness function that contains the parameters such as communication energy and the distance from nodes to the BS. A subcluster head (SCH) is also selected using the fitness function in each subregion part to communicate with nodes and the CH. The authors also discussed the use of the proposed scheme in fire detection real-time application. ABCACO managed to decrease the communication distance and increase network lifetime, stability, and goodput compared to few existing algorithms.Energy-efficient cluster head selection and routing (ECHSR) in disaster management in IoT networks was researched by the authors in [1]. In this literature, an improved hybrid particle swarm optimization (PSO) and harmony search algorithm (HSA) for CH selection is proposed. Later, a PSO-based multihop routing system with enhanced tree encoding is adopted for data transmission. For the CH selection based on the proposed algorithm, a fitness function is evaluated based on energy-efficiency criterion, cluster closeness, and network coverage, to select the optimal CH. To evaluate the fitness function to have optimal solutions towards the multiobjective optimization problem (MOOP), an adaptive weighted sum (AWS) method is used. The proposed method was simulated in a forest fire scenario by varying sink locations, where ECHSR performed better compared to some related methods.Prolonging network lifetime is the main objective of many WSNs research studies, which led the authors of [114] to propose an enhanced-LEACH (E-LEACH) algorithm that uses grey wolf optimization (GWO) and discrete particle swarm optimization (D-PSO) to have an optimal CH and helper CH (HCH) selection in a multihop environment. HCH is selected to reduce the burden of the CH and to have balanced energy dissipation. During the CH selection process, the GWO takes a random number and residual energy as input, whereas D-PSO takes distance and centrality as input. These inputs are processed in parallel to select the CH and HCH. The proposed E-LEACH achieved a longer network lifetime by reducing energy consumption compared to other algorithms.In recent years of research, a multiweighted chicken swarm based genetic algorithm (MWCSGA) for energy-efficient clustering in multihop WSNs was proposed in [115]. The GA’s crossover and mutation operators are embedded into the chicken swarm optimization (CSO) algorithm to ensure diversity in obtaining the optimal solution. The efficient CH is selected by considering the energy consumption, distance between CH and BS, and distance between node and CH in fitness function evaluation. The multiweights in terms of localization of nodes and their residual energy are also added before selecting the CH, to reduce energy consumption. From the simulations, it was evaluated that MWCSGA performed better as compared to several existing state of the art methods in terms of energy efficiency, end-to-end delay, throughput, and packet delivery ratio.


## 5.2.3. Single-Hop Data Transmission

The capability of ABC in yielding optimal solutions has pulled some researchers to hybridize ABC with different algorithms to obtain the best optimal solution. As such, authors in [116] proposed a hybrid clustering protocol based on a metaheuristic approach (CPMA) using the artificial bee colony (ABC) algorithm and harmony search algorithm (HSA) in a single-hop network structure. The CH is selected based on HSA, where two factors are considered, which are total energy cost and the predicted energy distribution ratio. On the other hand, ABC is used to tune the CH ratio and weight factor in fitness function so that the most optimal CH is selected. Simulations were made with varying BS locations, where CPMA managed to prolong the network lifetime and increase the throughput compared to some existing methods.


## 5.2.4. Heterogeneity

In [117], the authors proposed a hybrid approach to optimize clustering in WSNs. The hybrid approach considers genetic algorithm (GA) and particle swarm optimization (PSO), termed as (GAPSO-H), where GA is used to select the optimal CH and PSO is used to select optimal routing for the mobile sink in a heterogeneous network. Three levels of energy heterogeneity are deployed which are supernode, advanced node, and normal nodes. The fitness function that is used to select the best CH comprises of five fitness parameters which are residual energy, average energy, the distance between sink and node, number of neighbors, and energy consumption rate. The proposed GAPSO-H outperformed several existing algorithms as it achieved an improved stability period.


## 5.2.5. Other Parameters

In this section, we have summarized few hybrid metaheuristic methods used for CH selection that lack environmental information from literature, because the papers solely focus on the CH selection process closely. All the literature discussed below uses a homogeneous network setup with static nodes which can be denoted as a standard setup.The authors in [118] proposed a CH selection algorithm based on fuzzy clustering and particle swarm algorithm (FCPSO). Initially, a subset is formed according to nodes’ locations by using fuzzy clustering. The cluster head selection in this method is done by using particle swarm optimization (PSO) with inertia weight. PSO is used to minimize the objective functions which are used for CH selection, which are maximum average distance, maximum distance from CH to BS, and total energy consumption. From the simulation, it was observed that FCPSO reduced the mortality rate of the nodes and extended the network lifetime.A hybrid harmony search algorithm (HSA) and PSO (HSA-PSO) were proposed in [119] for energy-efficient CH selection in WSNs. HSA is based on the concept of finding the pleasing harmony by a musician, and HSA is deemed to have good exploration capability [120]. The proposed algorithm gives a balance between global search and local search to obtain the optimal CH. The CH is selected based on Euclidean distance f1and the ratio of initial energy of nodes f2, where the objective functions fobj are calculated with the inclusion of scaling factor ε, as shown below:
(12)fobj=ε×f1+1−ε×f2.The proposed algorithm managed to have a higher searching capability in high-dimensional problems and outperformed the nonhybridized algorithm in terms of network lifetime and throughput.In the year 2017, Yadav and Kumar proposed a teaching learning-based optimization (TLBO) algorithm based on the LEACH protocol (LEACH-T) for CH selection in WSNs [121]. The TLBO algorithm is based on the classroom concept of teacher and learner. Two modifications are made to TLBO in the CH selection phase, which are the implementation of genetic crossover and mutation operators to improve the convergence rate. The CH is selected based on the fitness function that evaluates the energy consumed in data transmission. From the comparison with traditional LEACH, LEACH-T has better performance in terms of live nodes and packets sent.The authors of [122] proposed a hybrid approach for optimal CH selection using LEACH and monkey search algorithm (MSO), termed as LEACH-MS. MSO is slightly similar to the aforementioned spider monkey optimization (SMO) [89], where it is on the concept of how monkeys search for food by climbing trees. In this paper, the CHs are chosen in two different ways. Initially, for the first 600 rounds, the selection is done through random numbers and the threshold value, which is using the LEACH process of CH selection. After 600 rounds, the CH is selected based on the MSO algorithm by considering the distance of nodes to the BS and residual energy. The proposed hybrid algorithm was able to increase network lifetime and throughput compared to the nonhybrid LEACH and MSO algorithms.In [123], the authors proposed a hybrid artificial bee colony and monarch butterfly optimization algorithm (HABC-MBOA) for optimal CH selection in WSNs. MBOA is based on the migration of butterflies from one area to another [124]. In this literature, the algorithm is proposed to prevent the solutions from falling into local optimal by replacing the employee bee phase of ABC with a mutated butterfly adjusted operator. The CH selection is done based on residual energy, the distance between CH and BS, and intercluster distance. The simulation was carried out with a huge number of sensors and varying sink positions and showed that the proposed algorithm outperforms several existing algorithms in terms of the number of nodes alive and the throughput.Lavanya and Shanker proposed an energy-efficient CH selection algorithm using a hybrid squirrel harmony search algorithm (SHSA) in a homogeneous WSN [125]. The nonhybrid squirrel search algorithm (SSA) was introduced in the year 2020, as discussed in the nonhybrid section. The main objective for the authors to introduce a hybrid method was to have a balance between the exploration and exploitation capability, where SSA, which has a good global search ability and harmony search algorithm (HSA) displays high search efficiency in a search space. The CH is selected based on the fitness function used by SHSA, which contains energy and separation energy as the fitness parameters. The SHSA was found to outperform the nonhybrid version by having an extended first node death, making it extend network lifetime by increasing the energy efficiency.Another new hybrid metaheuristic algorithm for CH selection proposed by the authors in [126] is called a new fitness-based glowworm swarm with fruitfly algorithm (FGF), which hybridizes glowworm swarm optimization (GSO) and fruitfly optimization algorithm (FFOA). The concept of GSO is based on a luminescence amount called luciferin of glowworm, to determine its movement and its neighbors [127], whereas FFOA is based on the concept of the food searching behavior of fruit flies. GSO and FFOA have some limitations such as poor local search capability and less convergence rate, respectively. To perform effective CH selection, the algorithms are hybridized to solve the problems above and certain parameters such as distance, delay, and energy utilized are used in fitness calculation. The comparison of FGF with some hybrid and nonhybrid algorithms showed that FGF performed better in terms of nodes being alive and energy consumption.Since many researchers implemented metaheuristic methods to optimize the CH selection and to obtain an energy-efficient network, Alghamdi proposed a hybrid concept of dragonfly algorithm (DA) and firefly algorithm (FF), termed firefly replaced position update in dragonfly (FPU-DA) [128]. The basic ideas of dragonfly and firefly algorithms are discussed in [80, 84], respectively. Treating DA and FF separately poses some limitations such as reduced internal memory and slow convergence. As such, the conventional levy update process of DA is replaced by the FF position update process to improve the convergence. The CH is selected by the proposed algorithm by considering four criteria which are energy, delay, distance, and security. Comparison results of FPU-DA with some state-of-the-art algorithms show that the proposed algorithm has better convergence, network lifetime, and normalized energy.The authors in [129] proposed a hybrid approach of firefly algorithm with particle swarm optimization (HFAPSO). LEACH-C [130], which was proposed earlier, uses the simulated annealing algorithm in CH selection, which causes more computation process time and consumes more energy. To overcome this issue, HFAPSO is embedded in LEACH-C to obtain optimal CHs to improve network lifetime, where the fitness function is evaluated using the remaining energy of the nodes and the distance between nodes and the CH. HFAPSO in the LEACH-C algorithm managed to prolong network lifetime and reduce energy consumption compared to the firefly algorithm and conventional LEACH-C algorithm.Moreover, in [131], the authors discussed hybrid grey wolf optimizer-based sunflower optimization (HGWSFO) to determine energy-efficient CHs in a homogeneous network environment. This proposed algorithm is also introduced to balance the exploration and exploitation capabilities, because grey wolf optimization (GWO) algorithm might fall into local optimum easily, and sunflower optimization (SFO) algorithm may have slower convergence rate. GWO follows the concept of a wolf pack that consists of leaders that are female, and a male termed as α who decides on sleeping location, time for walking and hunting, and all the other activities (exploitation). On the other hand, SFO is a method that uses the law of radiation to reduce the distance between the plant and the sun to get better sunlight (exploration). In CH selection, energy and distance constraints are used by the objective function of HGWSFO to have the most optimal CH selected. HGWSFO outperformed some existing state-of-art algorithms in terms of network lifetime and stability.


## 5.3. Cluster Formation

Similar to nonmetaheuristic algorithms, the metaheuristic approach uses two popular cluster formation methods which are unequal clustering andK-means clustering, followed by CH selection using a metaheuristic algorithm. In this section, the cluster formation phase will be discussed further to understand the impact of these popular techniques, which will then influence a better network deployment, as described in Figure 11.Figure 11
Taxonomy of cluster formation with metaheuristic methods.Sangeetha and Sabari in the year 2018 published two papers [132, 133] that discuss both unequal clustering (UC) and K-means clustering (KC) approaches with metaheuristic methods. These literature works were proposed to improve network lifetime by reducing energy consumption in mobile WSNs. In the first paper, the authors discuss the implementation of PSO in unequal clustering (UC-PSO) and K-means clustering (KC-PSO) approaches. In UC-PSO, the CH is selected first based on mobility metric, residual energy, neighbor’s connectivity, and distance from CH to BS. After that, the member nodes join the CH, forming unequal clusters, to prevent the CH of the cluster near to the BS from dying quickly. On the other hand, in KC-PSO, the clusters are partitioned into equal sizes first, and then, an optimal CH is selected based on PSO. The two proposed methods were compared with LEACH and from the results, it was deduced that KC-PSO performed better in terms of reduced energy consumption and enhancing the network lifetime.In the second paper by the same authors, the implementation of GA in unequal clustering (UC-GA) andK-means clustering (KC-GA) approaches was done. UC-GA and KC-GA have a similar process as UC-PSO and KC-PSO. In UC-GA, the CH is selected initially using the same parameters mentioned above and then the unequal clusters are formed, and in KC-GA, the partition of clusters is performed initially before selecting the CH for each partition. The usage of GA in this literature enables the network to have more stability in dynamic clustering problems. The results from the simulation show that KC-GA performs better in terms of reduced energy consumption and enhancing the network lifetime as compared to UC-GA and LEACH. To put it in a nutshell, the K-means clustering algorithm performs better than the unequal clustering approach. The limitation of both pieces of literature is that they did not compare the clustering approaches to determine which performs better in terms of the usage of different metaheuristic algorithms.Even thoughK-means has better performance compared to unequal clustering, deploying K-means can be tedious, and selecting the wrong k value might affect the whole network. Therefore, unequal clustering, which can dynamically create clusters, is given more attention in recent years. The authors in [134] proposed a metaheuristic ant colony optimization (ACO) based on unequal clustering (MHACO-UC) in WSNs. Initially, the network is set up for a few different scenarios that vary the location of the BS. Then, the neighboring nodes are identified for clustering, and unequal clusters are formed to achieve balanced energy consumption. The nodes join the cluster based on the single-hop transmission and the concept of rendezvous node (Rnode) is introduced, where Rnode is chosen by the CH based on proximity to help CH transfer data to the BS. The simulation under different scenarios shows that MHACO-UC enhances the network performance efficiently.The success of unequal clustering in solving energy hole problems has lured the authors of [135] to propose an energy-efficient nonuniform clustering routing protocol (E2NUCR). Nonuniform clustering in this literature is done by the calculation of the prior probability of data distribution to form a prior knowledge Pi based on the degree of similarity of data packets and the distance of the node from the sink. If the Pi values of nodes are similar, then they will be in the same cluster. Later, an improved shuffled frog leaping algorithm (ISFLA) is introduced for optimal CH selection, where ISFLA is based on the concept of the movement direction of frogs. The proposed E2NUCR was able to improve energy efficiency and network lifetime.In [136], the authors proposed an energy-balanced cluster-routing protocol (EBCRP) based on PSO with five mutation operators. PSO is known to have the issue of falling into local optimum easily [137]. So, it is hybridized with 5 mutation operators to improve the diversity, so that the algorithm will have good exploration capability and would not fall to local optimum easily. PSO with five mutation operators is used to optimally determine the number of clusters and to group the sensor nodes into clusters evenly by optimizing the number of clusters and their centroids. The CH is selected considering the residual energy based on CH rotation in each round, to achieve balanced energy consumption. Based on the simulation results, it can be inferred that EBCR can prolong the network lifetime by better balancing the energy consumption as compared to some other methods.


## 5.4. Parameter and Environmental Setting Analysis of Metaheuristic Methods

The simulation parameters used and the environment settings from all the aforementioned techniques in nonhybrid and hybrid metaheuristic clustering are analyzed and compared in Table4.Table 4
The comparison analysis of simulation parameters and environmental settings of metaheuristic clustering.
Paper (year)CH selectionCluster formationHybrid/ nonhybridSelection criteriaData transmissionMobilitySensor typeNetwork dimensionNo. of nodesPacket lengthSensor initial energyLocation of BS[84] (2015)EPSO-CEO—NonhybridAverage distance and average energy of the member nodesMultihopStaticHomogeneous200m×200m100—3 J—[118] (2015)FCPSO—HybridEnergy consumption and distance factorsN/SStaticBoth500m×500m100500 bytes0.5, (0.3 J-0.7 J)(250, 250), (500, 575)[85] (2016)BAFSA—NonhybridEnd to end delay and energyMultihopStaticHomogeneous2000m×2000m100-1000625 bytes0.5 J—[86] (2016)ABC—NonhybridEnergy, distance between CH and BSMultihopStaticHomogeneous100m×100m35, 75, 150, 195, 250625 bytesN/S—[100] (2016)PSO-ECHS—NonhybridIntracluster distance, sink distance and residual energy of sensor nodes.N/SStaticHomogeneous200m×200m300–700500 bytes2 J(100–300), (100–300)[113] (2016)ABCACO—HybridEnergy and distanceMultihopStaticHomogeneous100m×100m200m×200m, 300m×300m100, 225—0.5 J, 1 J(50, 50)[119] (2016)HSA-PSO—HybridResidual energy and distanceN/SStaticHomogeneous100m×200m100512 bytes0.5 J(50,150)[87] (2017)FFCHSA—NonhybridEnd-to-end delay, packet delivery ratio and energy consumption.MultihopStaticHomogeneous1250m×1250m100—40 J—[95] (2017)INSPSO—NonhybridResidual energy and distanceMultihopStaticHeterogenous500m×500m300, 400, 500Gateway=10J(500,250)Nodes=2J[101] (2017)WOA-C—NonhybridResidual energy of the node and the sum of energy of adjacent nodes.N/SStaticHomogeneous100m×100m100, 300, 500500 bytes0.5 J(50×50), (100×100, (50×200)[102] (2017)CSO—NonhybridEnergy consumption, distance between CH and BS, and cluster compactnessN/SStaticHomogeneous100m×100m150256 bytes0.5 J(50, 150)[103] (2017)NSGA-II—NonhybridCrowding and ranking system to efficiently selecting the individualN/SStaticHomogeneous200m×200m48-96500 bytes0.5nJ-100, 100[121] (2017)LEACH-T—HybridResidual energyN/SStaticHomogeneous100m×100m100—0.5 JCenter of the network[122] (2017)LEACH-MS—HybridResidual energy and distanceN/SStaticHomogeneous100m×100m150256 bytes0.5 J-50,150[82] (2018)BeeWSN—NonhybridThe remaining energy of node, degree, speed, and directionN/SMobileHomogeneous3000m×3000m×3000m<200175 bytesN/S—[88] (2018)iCSHS—NonhybridResidual node energy, degree of node, intra-cluster distance and coverage ratio.MultihopStaticHomogeneous200m×200m100-300500 bytes0.5 J, 2 J, 200 J(100, 100), (150, 50), (200, 200)[132](2018)—KC-GAUC-GA—Node residual energy, connectivity degree, distance from sensor node to BS, and mobility factor.MultihopStaticHomogeneous100m×100m200512 bytes2 J(50, 175)[133](2018)—KC-PSOUC-PSO—Mobility metric, residual energy, neighbor’s connectivity, and distance from the CH to the BS.MultihopStaticHomogeneous100m×100m200512 bytes2 J(50, 175)[83] (2019)BICIoD—NonhybridResidual energy level and position of the drones.MultihopMobileHomogeneous1000m×1000m, 2000m×2000m, 3000m×3000m15, 20, 25, 30, 35—80 Wh—[89] (2019)SSMOECHS—NonhybridNode distribution, node energy, distanceMultihopStaticBoth100m×100m100800 bytes1 J, (0.5-1 J)-50, 150[92] (2017)FCR—NonhybridEnergy, distance, and delaySingle hopStaticHomogeneous100m×100mN/S—0.5 JCenter of the network[81] (2019)MO-GSA—NonhybridDistance of nodes to their corresponding cluster head and remaining energySingle hopStaticHomogeneous100m×100m100800 bytes0.5 J(50, 175)[93] (2019)IAPSO—NonhybridResidual energy ratio and energy consumption balance degreeSingle hopStaticHomogeneous500m×500m100-200500 bytes2 J-250,250[10] (2019)EWA—NonhybridEnergy, distance, and delayMultihopStaticHeterogenous100m×100m100—0.5 JCenter of the network[96] (2019)GAOC—NonhybridResidual energy, distance to the sink, and node density.Single hopStaticHeterogenous100m×100m, 500m×500m100, 200250 bytes0.5 J—[97] (2019)EC-PSO—NonhybridNodes close to the energy centersMultihopStaticHeterogenous1000m×1000m400125 bytes0.5 JCenter of the network[104] (2019)GA based clustering—NonhybridHighest residual energy and lowest distance to BSN/SStaticHomogeneous100m×100m404 bytes1000 JCenter of the network[106] (2019)MCRO-ECP—NonhybridNeighbor node distance, base station distance, ratio of energy, intra-cluster distance, and CH node degreeN/SStaticHomogeneous400m×400m200, 400, 600, 800, 1000512 bytes2 J(0, 0)[107] (2019)FTBA-TC-LEACH—NonhybridResidual energyN/SStaticHomogeneous100m×100m100500 bytes0.5 J(50, 50)[112] (2019)SAGA—HybridResidual energy and distanceSingle hopMobileHomogeneous1000m×1000m150780 bytes10 J—[123] (2019)HABC-MBOA—HybridResidual energy, distance between the cluster head, the base station and intercluster distance extracted from the network.N/SStaticHomogeneous400m×400m1000512 bytes0.5 JCenter of the network[125] (2019)SHSA—HybridEnergy and separation energyN/SStaticHomogeneous100m×100m100512 bytes0.5 J—[126] (2019)FGF—HybridEnergy, the distance among nodes, packet delayN/SStaticHomogeneous100m×100m100—0.5 JCenter of the network[134] (2019)—MHACO-UC—Proximity, residual energy, and link quality factor (LQF)MultihopStaticHomogeneous200m×200m, 400m×400m, 600m×600m100-800150-512 bytes1000 mJCorner, center and top level of network[90] (2020)PBC-CP—NonhybridNode’s energy, degree of node, and distance from base station to nodeMultihopStaticHomogeneous100m×200m100512 bytes0.5 J(50, 150)[91] (2020)Memetic algorithm—NonhybridNode degree, intracluster communication cost, and residual energy.MultihopStaticHomogeneous400m×400m200500 bytes2 J(0,0)[98] (2020)TGDEEC—NonhybridResidual energy and distanceMultihopStaticHeterogenous100m×100m50—0.5 JCenter of the network[99] (2020)SBHRA/ ABC—NonhybridResidual energy and distanceSingle hopStaticHeterogenous400m×400m400500 bytes0.5 J—[108] (2020)SSA—NonhybridSensor nodes energy and distance between the interactive elementsN/SStaticHomogeneous100m×100m100512 bytes0.5 J—[109] (2020)YSGANonhybridDistance from CH to the base station and the residual energy of CHN/SStaticHomogeneous100m×100m100500 bytes0.07 JCenter of the network[1] (2020)ECHSR—HybridEnergy efficiency criterion (EE), cluster closeness (CC) and network coverage (NC).MultihopStaticHomogeneous100m×200m100512 bytes0.5 J(50, 150), (100, 100), (0, 100), (50, 200)[114] (2020)E-LEACH—HybridGWO takes a random number and residual energyD-PSO takes distance and centrality as inputMultihopStaticHomogeneous1000m×1000m50512 kilobytes100 JCenter of the network[116] (2020)CPMA—HybridTotal energy cost and energy distribution ratioSingle hopStaticHomogeneous200m×200m100500 bytes1 J(100, 100), (100, 200), (0, 200)[117] (2020)GAPSO-H—HybridEnergy, distance, node degree, average energy, and energy consumption rate (ECR).MultihopStaticHeterogenous100m×100m, 500m×500m100, 200250 bytes0.5 J—[128] (2020)FPU-DA—HybridEnergy, delay, distance, and security.N/SStaticHomogeneous100m×100m100—0.5 JCenter of the network[129] (2020)HFAPSO—HybridEnergy and average distanceN/SStaticHomogeneous100m×100m100500 bytes1–5 J(50, 175)[131] (2020)HGWSFO—HybridDistance and energyN/SStaticHomogeneous200m×200m100—0.5 J—[135] (2020)—E2NUCR—Residual energy factor, location factor within clusters, and location factor between clustersMultihopStaticHomogeneous200m×200m400—0.5 J(100, 250)[136] (2020)—EBCRP—Residual energyN/SStaticHomogeneous100m×100m50-200500 bytes0.1 J—[94] (2021)FA-ROA—NonhybridEnergy, distance and delay, load, and temperatureSingle hopStaticHomogeneous100m×100m100—0.5 JCenter of the network[115] (2021)MWCSGA—HybridEnergy consumption, distance between the CH and the BS, and the distance between nodes and the CH.MultihopStaticHomogeneous1000m×1000m100500 bytes0.5 J—∗N/S: not stated.


## 6. Comparison, Discussion, and Open Issues

In this section, we will be comparing the network stability, reliability, and overall complexity as well as the advantages, limitations, and future directions suggested by the papers of both nonmetaheuristic methods and metaheuristic methods used for clustering in WSNs. A detailed comparison of nonmetaheuristic methods and metaheuristic methods in mobile, multihop data transmission, single-hop data transmission, heterogeneity, and other parameters (static and homogeneous) is provided in Tables5–9, respectively.Table 5
Comparison table of various methods in mobile node or sink environment.
Method (year) [paper]Objective(s)AdvantagesLimitationsFuture direction suggestedTime complexity (TC) & space complexity (SC)NonmetaheuristicLEACH-distance-M (2017) [13]Improve network load balance.Improve network lifetime.Discusses for both static and mobile environments.The hotspot problem and single hop transmission problem are analyzed.Usage of many criteria may increase the computation calculation.The increase in mobile sensor nodes (SNs) while varying their velocities can be analyzed.Heterogeneity in SNs can be tested.Pseudocode or algorithm is not clearly discussed.Discussion on the mathematical computation only.DFLBCHSA (2018) [34]Minimizing energy consumption.Reduce delays in packet delivery.Reducing communication overhead by applying the linear prediction method to estimate the next locations of the moving gateway nodes.Storing the location of the gateway nodes will limit the memory capacity and might increase energy usage as well.High process complexity.DFLBCHSA has a high value of delay in a shorter number of rounds.Automatically induce the membership functions using the genetic algorithm method to enhance the performance.Replacing other energy-efficient combination techniques for GSoSN and LoSNRtMG factors should be considered.TC:On2SC: OnRE2WCA (2018) [35]Increase energy efficiency.Increase robustness.Clustering times will be dramatically reduced due to group mobility.Design a periodic fault detection protocol to exclude the fault node.Discusses topology maintenance for energy-efficient communication.Only applicable to the mobile sensor as it uses group mobility as one of the selection criteria.To enhance the robustness and trust function of the network.TC:On2SC: On2CMBCH (2020) [36]Reduce energy consumption.Minimum communication delay.This CM coordination with CH results in reducing the communication delay, secure data communication, complete data loss reduction, and improves network efficiency.Selecting CM and CH might be time-consuming and might drain CM storage as well.There are 3 split zones, so the scalability of the network is limited.Maintaining data security during packet transmission in the network can be an area that is concentrated on in the future.TC:OnlognSC: OnEEMCS (2020) [37]Reduce energy consumption.Prolong the lifetime of WSN.Focuses and explains reclustering cases.The analysis is made in various network sizes and a varying number of nodes.Selecting the appropriate weight for each parameter in CH selection might be difficult as it may affect the whole system.Implementing heterogeneous nodes.Using mobility prediction model to predict the movement of sensor nodes to select the CH.TC:OnSC: OnCNNMR (2021) [19]Prolong network lifetime.Minimize energy consumption.A mobile sink is used to reduce the energy consumption of the cluster heads.Addresses the energy hole problem.Deployment of moving BS with no energy constriction is difficult.CNNMR uses more energy at the initial stages compared to CMR and FESRA.The genetic algorithm can be used to draw routes for efficient routing.The CMR and CNNMR proposed can be compared with other algorithms.TC:On2SC: OnMetaheuristic (nonhybrid)BeeWSN (2018) [82]Minimize the end-to-end delay.The search process is designed in such a way that both the exploitation and the exploration of honeybees can be carried out jointly.HBA may skip the true solution due to large step sizes (fall into local optimum).—TC:On2SC: O1BICIoD (2019) [83]Reduce energy consumption.Used actively in drone application.The optimal path selection mechanism is used for better communication between drones.The proposed method is tested on a small scale.The complexity of the algorithm is not analyzed.A hybrid methodology can be introduced to improve overall performance.TC:On2SC: OnMetaheuristic (hybrid)SAGA (2019) [112]Improve network lifetime.Minimize the energy consumption.Fusion of GA and SA algorithm is implemented to overcome the large combinational optimization problems.SAGA has a higher routing overhead with a greater number of nodes.It is more towards exploration capability and no discussion on balance between exploration and exploitation capability.Incorporating fuzzy logic during data transmission in MANET can be implemented to improve SAGA.TC:On2SC: OnTable 6
Comparison table of various methods in multihop data transfer environment.
Method (year) [paper]Objective(s)AdvantagesLimitationsFuture direction suggestedTime complexity (TC) & space complexity (SC)NonmetaheuristicMOFCA (2015) [38]Improve energy efficiency.Distribution-independent WSNsFocuses on routing of the clustered WSN.Ensures the proposed method performs well in both uniform and nonuniform distribution.Ensures perform well in different sink locations from the network.Mobility is only considered as natural terrestrial movements.Algorithmic evaluation to be done by considering international mobility.TC:On2SC: OnLEACH-AD (2016) [39]Improve energy efficiency.Improve security defence of WSN.Focuses on security attacks on WSN.The honest nodes are also determined to be entrusted as cluster heads during the packet transmission phase.The algorithm might be complex, and the process might be time-consuming.Modify the proposed algorithm to reduce communication overhead.Provide security over the packet transmission phase.TC:OnlognSC: O1CEED (2016) [40]Increase network lifetime.Discusses on keeping the energy balanced by selecting the proper CH.Might cause an energy hole problem.—Pseudocode or algorithm is not clearly discussed.Discussion on the mathematical computation only.MAP (2016) [41]Uses two zones of clustering to reduce the energy consumption near the BS.Two-tier clustering might increase the time taken for better clustering and might cause isolated nodes problem.The stability of this algorithm to be compared against LEACH and SEP algorithms.TC:OnSC: O1EBC (2017) [12]Balanced energy consumptionFocuses on giving a balance of energy consumption to the CH nearer to the BS.Focuses on hotspot problem.The probability of signal collision and interference is ignored.The method consumes more energy when it is iterated for more rounds.—Pseudocode or algorithm is not clearly discussed.Discussion on the mathematical computation only.FCBA (2017) [42]Minimize energy consumption.Global sensor information is available for efficient clustering.It may contribute to the energy hole problem.The interference is ignored.To compute the impact of the deployment of heterogeneous nodes and consider more factors to select CHs for enhanced performance.TC:On2SC: O1TTDFP (2018) [43]Improve energy efficiency.Improve efficiency of data aggregation.Focuses on various scenarios by varying sink locations and protocol used for multihop routing.Focuses on routing of the clustered WSN.Only SA algorithm is used to test the optimization ability of the proposed method.Does not consider small network sizes.PSO can be used for to test the optimization ability.Node’s mobility also to be focused in future.TC:On2SC: OnDistributed clustering scheme (2018) [44]Increase the energy efficiency.Optimize load balance.Distributed cluster head mechanism is utilized that is able to reduce the network overheads.Discusses optimizing data forwarding.May cost hotspot problem as the CH near BS might die off quickly due to multihops.—Pseudocode or algorithm is not clearly discussed.Discussion on the mathematical computation only.ETTA (2018) [45]Balance energy consumption.Increase energy efficiency.CH is dynamically chosen on the edge of a cluster.CCH is used to collect the sensed data where the data are aggregated near to the data source and the transmitting data are decreased.Cluster maintenance is discussed.Organizing the network into clusters makes the forming of the network difficult and time-consuming.The selection of CH and CCH might increase the selection time.LEACH still performs better in terms of transmission delay.—TC:On2SC: OnLEACH-M (2018) [46]Balance the network energy burden.A CH competitive mechanism is focused on to mitigate the communication energy cost.The ex-cluster head avoids running out of its energy and still serves as a “subordinate” for the new “commander” after becoming an ordinary child node.Does not discuss the hotspot problem that it might face.Might face problem in storing network address of nodes if the network is huge.Factors such as distance between cluster head and BS, space from a cluster member to its cluster head, and energy consumption in the last round can be taken into consideration for CH selection.Pseudocode or algorithm is not clearly discussed.Discussion on the mathematical computation only.MCDS-MI (2018) [47]Maximize energy efficiency and reliability in data transfer.Computational complexity is reduced by incorporating the method.For fault-tolerant and transmission reliability, a highly improved Steiner tree is constructed.Focuses on the energy hole problem as well.Might not be easily scalable in terms of the number of nodes.Usage of many techniques might increase the overall complexity.The algorithm can be applied in different transmission and sensing ranges of heterogeneous swarm networks.The proposed work can be extended considering security issues in WSN.TC:On2SC: OnTTDFP_ CLONALG-MFPS_ CLONALG-M (2019) [48]Improve data routing efficiency.Focuses on efficient routing to reduce the energy hole problemIt does not focus on CH selection methods.Rule generation or rule-based compaction can be considered for efficient computation requirements.Target type-2 fuzzy set for performance optimization in WSN.TC:On2SC: OnAPDC-M (2019) [49]Prolong network lifetime.Two CH are chosen, one is to collect data, and one to transfer data to reduce the energy consumption of a single node.An election strategy based on the reference point was added to reduce the computation.Multihop transmission based on the shortest path is discussed for efficient routing.Did not emphasize on energy hole problem.Selecting two CHs and the involvement of many processes might increase the algorithm’s process time.—TC:On2lognSC: OnECH (2019) [50]Maximize energy efficiency.Maximize network lifetime.Minimize data redundancy.Focuses on maximizing the network lifetime by minimizing data redundancy (sleeping and waking node).The accuracy and complexity of the algorithm is evaluated.Random selection of CH, in the beginning, might select the CH with less energy which might cause the node to die quickly.It can be expanded to test network with mobile sink.To carry out theoretical analysis on the network lifetime maximization.ECH can be implemented with recent routing protocols of WSNs.TC:On2SC: O1LEACH-ABF (2020) [51]Balanced energy.Extend network lifetime.ABF adaptively combines the diversity function and convergence function and uses genetic operations to produce better solutions, so that the optimal solution can be found more efficiently in the solution space.The computational complexity of the algorithm is also discussed.The inclusion of three other methods might increase the overall complexity of the algorithm.LEACH-ABF does not converge well in multimodal problems.To make the routing protocol performance better, a study can be made for specific applications of WSNs.TC:On2SC: OnEBCR (2020) [52]Maximize the WSN life.Improve energy utilization.Balance energy consumption.The intercluster cooperative routing algorithm greatly improves the transmission efficiency between cluster heads.The proposed method tends to balance the burden of cluster heads and alleviate hot zone issues.Usage of many methods and functions might reduce the execution time and increase the overall complexity.Nonuniform clustering is proposed in this paper, which requires a lot of centralized calculations.The parameter selection will be discussed for the proposed method.TC:On2SC: O1MOFCA_ CLONALG-MCHEF_ CLONALG-M(2021) [53]ImproveThe energy efficiency.Focuses on efficient routing to reduce the energy hole problemSimulation is done with various networks scale to ensure the scalability of the proposed method.It does not focus on CH selection methods.Artificial neural networks or Tabu search can be used to compare with the proposed method.Online approximation of fuzzy functions can be used to ensure it is light weight.TC:On2SC: OnMetaheuristic (nonhybrid)EPSO-CEO (2015) [84]Maximizing the lifetime.Routing and data aggregation by CH is discussed by calculating the cost path for efficient routing.Usage of PSO may lead to a fall in local optima.Usage of multiple sinks or mobile sinks and efficient data collection using data aggregation to reduce the delay in the system can be done.Pseudocode or algorithm is not clearly discussed.Discussion on the mathematical computation only.BAFSA (2016) [85]Reduce packet loss.Reduce energy consumption.Usage of the transfer function to improve the performance of BAFSA.The nature-based algorithm might not solve the nonlinear and multimodal problems.—TC:On2SC: O1ABC (2016) [86]Minimum energy consumption.Least hop-count for data packet delivery.Uses TDMA schedule to ensure that there will be no collisions among data packets sent by various nodes.ABC has drawbacks like preference on exploration at the cost of exploitation and skipping the true solution due to large step sizes.The algorithm can be tested on real testbeds with a large density of SNs.TC:On2SC: O1FFCHSA (2017) [87]Minimize energy consumption.The algorithm helps to avoid selecting multiple CH nodes to reduce complexity and unnecessary energy consumption.Firefly algorithm usually suffers from the drawback of easily getting stuck at local optima.—TC:On3SC: O1iCSHS (2018) [88]Maximize energy efficiency.Maximize data transfer.Discusses the energy hole problem.Optimum routing is discussed by using HSA.The algorithm is performed separately for CH selection and routing, which will increase the overall complexity.The proposed algorithm can be enhanced by incorporating the issues of communication void, network with obstacles, and delay sensitivity.TC: OnlognSC: OnSSMOECHS (2019) [89]Extend the lifetime and stability.The optimal CHs are obtained from sampling and optimized using a modified SMO algorithm, thus preventing the divergence between ideal CH location and actual CH node location.In SMO, if nodes are with discrete location, it will fail the exploration.The weight must be appropriately set to be used as the sampling probability or the expected value will be wrong.—TC:On2SC: O1PBC-CP (2020) [90]Prolonging network lifetime.The search process is designed in such a way that both the exploitation and the exploration of honeybees can be carried out jointly.Uses TDMA to avoid packet collision.ABC is well known for drawbacks like preference on exploration at the cost of exploitation and skipping the true solution due to large step sizes.The proposed method can be analyzed in mobile sensor networks.TC:On3SC: O1Memetic algorithm (2020) [91]Efficient load balance.Usage of unequal clustering might cause cost overhead.No significant difference in performance when compared to GA.Discusses energy hole problem.Congestion control and security issues during packet transmission can be given more attention in the future.TC: On2SC: OnMetaheuristic (hybrid)ABCACO (2016) [113]Improved network stability.Increase the network lifetime.Discusses square optimization problems and the scalability.Discusses on the application of fire detection in real-time.Usage of 2 algorithms separately will increase the overall method complexity.To come up with better bioinspired solutions for real-world WSNs such as neural swarm system, swarm fuzzy system, and neural fuzzy system.TC:On3SC: OnECHSR (2020) [1]Reduce energy consumption.Increase energy efficiency.The method includes enhanced tree encoding and a modified data packet format for better routing.Using the adaptive weighted sum (AWS) method as a mathematical model can obtain lower optimization cost.Multicriteria decision-making (MCDM) schemas are considered to solve MOOP efficiently.PSO faces high-dimensional optimization limitation.HSA has the limitation of being restricted to only a certain region.The usage of AWS might increase the complexity of the method.An efficient MAC protocol based on this application will be designed to prevent long delays and extend simulation scenarios in heterogeneous networks.TC:On3SC: OnE-LEACH (2020) [114]Prolong the node’s energy.Prolong network lifetime.The optimization algorithms GWO and D-PSO are operated in parallel to minimize the processing time of the algorithms.Dynamic fuzzy-based transmission helps to avoid packet loss.Usage of many algorithms might increase energy consumption to execute the algorithms.Implementing CH and HCH might increase the cluster numbers if the cluster numbers are not fixed, which indirectly limits scalability.A large-scale network can be used to test the algorithm based on a specific application.TC:On2lognSC: OnMWCSGA (2021) [115]Reduce energy consumption.Increase the lifetime of the network.Selects the second CH for fault tolerance.The CH selection is enhanced by using the genetic algorithm crossover and mutation process to maximize the diversity of the population of the network.Multiweight model that works with uniform clustering is used to ensure reduction in energy consumptionThe algorithm contains six sections which will increase the complexity of the overall algorithm.GA has a slow convergence by nature.There is a possibility of experiencing delays during communication.The normalized proposed method can be compared with P-SEP and N-SEP for formal validation in the future.TC:On2SC: OnTable 7
Comparison table of various methods in single-hop data transfer environment.
Method (year) [paper]Objective(s)AdvantagesLimitationsFuture direction suggestedTime complexity (TC) & space complexity (SC)NonmetaheuristicREAC-IN (2015) [16]Prolong network lifetime.Focuses on isolated nodes.Uses regional average energy and the distance between sensors to determine the data transmission for efficient data transmission.The calculation of regional energy might increase the process time.Usage of regional energy might still exhaust the individual energy quickly.—Pseudocode or algorithm is not clearly discussed.Discussion on the mathematical computation only.EDB-CHS (2019) [54]Balancing energy consumptionExtend network lifetime.A tight closed-form expression is proposed for the optimal number of cluster heads (CHs).Deriving a new optimal probability for a sensor node to serve as a CH for EDB-CHS-BOF protocol for the reason of achieving a balanced energy consumption.The clustering shape used is hexagonal as it is closer to reality.The involvement of many operations might increase the overall complexity of the algorithm.Having adjacent CHs may cause long-distance communications, which lead to increased energy consumption.—Pseudocode or algorithm is not clearly discussed.Discussion on the mathematical computation only.SF-CHs (2019) [55]Balanced energy consumption.Improve network lifetime.The SF-CHs algorithm can reduce the residual energy variance of nodes in the network.The optimization of the threshold function selects the optimal CHs.Each sensor randomly generates a number in [0, 1] for CH selection in DEAL, where the random selection is still not the optimized way for CH selection.Implement the method in a real environment for verification.Develop the method for application specific WSNs.Pseudocode or algorithm is not clearly discussed.Discussion on the mathematical computation only.FEECA (2020) [56]Prolong network lifetime.Network division in the diagonal form to reduce the load of the network.Optimal values for the fuzzy inference system are analyzed.Data routing is discussed for optimal routing.Setting the optimal parameters might be a difficult job and might also limit scalability.A genetic algorithm can be used for CH selection and cluster formation to enhance the network lifetime.TC:On2lognSC: OnDRE-LEACH (2021) [57]Reduce the energy consumption.Improve network lifetime.A variable range is used to localize the required calculations, which leads to less computation.The involvement of many calculations to determine the nodes’ score might consume more energy.Multihop routing between CH environments and constant route updates should be considered as routes dynamically change in WSNs for better routing.TC:On2SC: OnMetaheuristic (nonhybrid)FCR (2017) [92]Maximize the energy efficiency.Minimize time delay.Usage of cyclic randomization improves the performance of the algorithm.Discusses the ability of FCR to handle multiple objectives.Firefly algorithm might easily get stuck at local optima.The proposed algorithm suffers a high computational cost, which requires substantial minimization.High processing complexity.Security constraints and other practical constraints can be considered in network modeling in the future.TC:On3lognSC: OnMO-GSA (2019) [81]Maximize the WSN’s lifetime.Maximize energy efficiency.Focuses on controlling exploitation and exploration capabilities of GSA by using tournament selection.TDMA schedule is organized by the cluster head to avoid data collisions.Solely focuses on energy efficiency and does not consider QoS.GSA might have problems with exploration and exploitation if treated separately.To introduce a controller or a function that can determine the value of the algorithm parameters user and problem independently.The time and computational complexity of the algorithm can be analyzed.TC:OnlognSC: O1IAPSO (2019) [93]High coverage ratio.Low redundancy ratio.Energy consumption balance.Discusses multiobjective optimization model due to the uncertainty between coverage ratio and redundancy ratio.To achieve better optimization, this paper improves inertia weight to PSO.PSO individually may fall into local optima.The number of cluster head influences the number of nodes alive using IAPSO, which might not be efficient.—TC:On3SC: OnFA-ROA (2021) [94]Maximize the normalized energy.Minimize the distance, delay, load, and temperature.Optimizing multiobjectives is focused.The suggested model achieves a large coverage ratio and less redundancy ratio.The algorithm might suffer from a balance between exploration and exploitation.The proposed method can be implemented to test network traffic rate, network density, and quality of service (QoS) of the network.TC:On2SC: OnMetaheuristic (hybrid)CPMA (2020) [116]Prolong network lifetime.Increase energy efficiency.Artificial bee colony (ABC) algorithm to optimize its crucial parameters which are done offline.Harmony search (HS) algorithm is used for CH selection, and it is done online.Single hop might cause the CH far away from BS to consume more energy.Tuning parameters might worsen the performance of the algorithm if the wrong tuning is made and needs more effort.CPMA has relatively high process time.Deploy the method in a large-scale and mobile network environment considering the IoT applications that exist.Use different energy harvesting constraints in CPMA to improve the network’s throughput.TC:On2SC: O1Table 8
Comparison table of various methods in a heterogeneous environment.
Method (year) [paper]Objective(s)AdvantagesLimitationsFuture direction suggestedTime complexity (TC) & space complexity (SC)NonmetaheuristicBEENISH (2016) [59]Increase energy efficiency.iBEENISH solves the high-energy nodes energy punishing problem by dynamically adjusting the CH selection probability.iBEENISH manipulates the probability of CH according to the variation of residual energy.Focuses on avoiding long-distance communication.Discusses sink mobility in terms of controlled and uncontrolled mobility to avoid energy hole problems.iBEENISH dynamically varies the CH selection probability in an efficient manner leading to increased network lifetime.Deploying the algorithm can be very costly and time-consuming.—Pseudocode or algorithm is not clearly discussed.Discussion on the mathematical computation only.E-CRCP (2019) [60]Minimum energy consumption.Regional coverage maximization.Focuses on getting maximum coverage by considering the coverage ratio for CH selection.The execution time might be increased due to more CH calculations.—TC:On2SC: O1TOPSIS (2020) [61]Reduce energy consumption.Prolong network lifetime.In the CH-friendship phase, the CH with low resources may request the high resources CH to operate on behalf of the low resources CH to avoid early failure and data loss.The CHs are not frequently changed, reducing the control overhead.Transmitting data from lowest resource CH to rich resource CH might deplete both the CHs’ energy.The application is used in wildlife monitoring, but the network area used is small.—TC:On2SC: OnmThreshold CH selection (2021) [62]Enhance network lifetime.The data fusion method based on the trust function is used to get accurate data.The proposed protocol prevents randomness in the selection process of CH.The algorithm can be optimized further and concentrates on energy issues alone.Use fuzzy logic method to enhance CH selection in the future.Pseudocode or algorithm is not clearly discussed.Discussion on the mathematical computation only.Metaheuristic (nonhybrid)INSPSO (2017) [95]Equilibrium between total energy consumption and energy balance.The hot spot problem is discussed by using passive and active ways to determine the residual energy of nearby nodes.Gateways/CHs are predefined, where the cost overhead involved in planning the network can be increased.Can consider a more effective objective to optimize the performance further.TC:On2SC: OnEWA (2019) [10]Minimize the energy consumption.Minimize the delay.Discusses the hotspot problem.Usage of Cauchy mutation operator to make EWA jump out of local optima.Optimal route selection is also made.EWA may fall into local optima.A hybrid optimization algorithm can be implemented to solve the multiobjective optimization problem in improving energy efficiency.TC:On2SC: OnGAOC (2019) [96]Minimize energy consumption.Maximize the stability period of the network.Discusses the hot spot problem and multiple sinks are used to mitigate the problem.Focuses on exploitation to mitigate GA’s deficiency.Multiple sink nodes can increase the overall cost.GA is slow in terms of convergence.The moving sink scenario can be implemented in the network design in the future.TC:On3SC: OnEC-PSO (2019) [97]Maximize energy efficiency.Balanced load.Discusses the energy hole problem.A low energy protection mechanism was used to avoid weak nodes from becoming relay nodes.The initial choosing of CH using the grid might not choose the best CH in the beginning (which uses geometric method).—TC:On2SC: O1TGDEEC (2020) [98]Reduced energy waste.Balanced energy.The threshold will filter out nodes that are not suitable to be cluster heads, so the wrong cluster head selection will not occur.In the beginning, the simulation results are not stable because there are nodes that use excessive energy.—TC:OnlognSC: O1SBHRA (2020) [99]Minimize energy consumption.Clustering is done by portioning for better CH selection.Efficient routing based on ABC is also discussed.Needs a lot of planning on the node’s placement.Cannot be used in a large-scale environment and is not easily scalable.Network performance can be enhanced more by considering other factors.The security issues can also be added in future work.Analyze packet loss of the network.Pseudocode or algorithm is not clearly discussed.Discussion on the mathematical computation only.Metaheuristic (hybrid)GAPSO-H (2020) [117]Improve energy consumption and network lifetime.GAPSO-H addresses the hot-spot problem.GAPSO-H is found to be computationally optimized.Focuses on a balance between global and local searches.The usage of nodes with different energy levels can increase the process complexity.Mobility of the sink can be expensive.Focus on reducing the end-to-end delay and network cost-effectiveness in the future.Implement multiple sink mobility scenarios in the network for better performance.TC:On2SC: O1Table 9
Comparison table of various methods for homogeneous and static environment.
Method (year) [paper]Objective(s)AdvantagesLimitationsFuture direction suggestedTime complexity (TC) & space complexity (SC)NonmetaheuristicHRFCHE (2018) [64]Improve the lifetime of the network.Uniform rotation of cluster head aids in balancing the energy drain of the network.Confirms a stable clustering.Focuses on minimizing the number of CHs.Usage of many criteria might slow down the clustering process.The transition probabilities computed for the sensor nodes are not normalized.To improve network lifetime, a semi-Markov modulated process-based cluster election scheme can be introduced in the future.TC:OnlognSC: O1CWC (2018) [65]Increase energy efficiency.Focuses on energy efficiency.Weighting coefficients are used for optimal CH selection.The coefficient has a great effect on the results, so it needs more effort to be selected carefully.The complexity of the proposed algorithm in the CH selection process is higher.—TC:O5nSC: O1DCoCH (2020) [66]Enhance network lifetime.Due to the usage of time-based clustering, desired parameters are guaranteed to be elected as CHs.Time-division multiple access (TDMA) and code division multiple access (CDMA) is used to avoid collisions.The alterations of coefficients can be tedious and may cause network stabilization issues.Must accurately set the coefficients for different applications.—TC:OnSC: O1IEECP (2020) [67]Prolong network lifetime.A new integration of the back-off timer mechanism for CH selection is used to reduce energy overhead.Forming balanced clusters that reduce the cost in the intra-distance based on modified fuzzy C-means algorithm.Usage of many functions and the number of CHs may increase the complexity of the overall algorithm.The execution time might be increased as well.In the future, the FCM algorithm can be improved by considering the random initial selection.Improving the objective function of CH selection using weighted energy-based distance for adjacent CHs.TC:OnxIround+K−1SC: OK2+50NCHR (2021) [68]Increase network lifetime.The proposed method supports topological changes, node heterogeneity, and can also handle CH failures.The proposed method is implemented in a testbed setup.Calculating the parameters for CH rotation might increase the energy consumption of the nodes.The study can be extended to entrust the CH with extra responsibilities of synchronizing the entire cluster coordinators in the future.TC:OnSC: O1Metaheuristic (nonhybrid)PSO-ECHS (2016) [100]Maximizing lifetime.Minimizing energy consumption.Increase the number of data packets.It uses an efficient scheme for particle representation and novel fitness functions for optimal CH selection.Usage of PSO may lead to a fall in local optima.A metaheuristic algorithm can be developed considering energy balancing and fault tolerance of WSNs issues.Deploying of the method in a heterogeneous network can also be done.TC:On2SC: O1WOA-C (2017) [101]Maximizing the energy efficiency of the network.WOA has some sort of balance between exploration and exploitation capability.TDMA (time division multiple access) and CDMA (carrier sense multiple access) is used to avoid collision of data.The fitness function only focuses more on the exploration capability of the algorithm.Develop algorithms that consider more factors of the fitness function.Hybrid algorithms can be developed to increase search efficiency.A heterogeneous environment can also be researched in the future.TC:On3SC: OnCSO (2017) [102]Reduce the energy consumption of the WSN.Improve the survival time of the network.Levy flight is used to make CSO jump out of local optima and to ensure global capability.CSO might fall into local optimum.Energy problem issues still exist, so more energy efficiency-focused research can be carried out.TC:On2SC: O1NSGA-II (2017) [103]Improve the stability.Extend the lifetime of the network.A step named release-random is added in the sorting procedure to prevent the solution only with one excellent objective value from being chosen.The proposed multiobjective clustering algorithm is more complex than the traditional clustering algorithm.The clustering is also handled by the sink which will slow the process.The complexity of the algorithm should be reduced in future research.Pseudocode or algorithm is not clearly discussed.Discussion on the mathematical computation only.GA based Clustering (2019) [104]Optimize energy consumption.Discusses on hotspot/energy hole problem.GA can be slow in terms of convergence. It can also be inaccurate.Develop a more scalable algorithm in the future to test it with real-time applications.TC:On2SC: OnMCRO-ECP (2019) [106]Reduce energy consumption.Enhance network lifetime.The new protocol that combines CRO with a turning operator and a mutation operator which enables quick convergence and capability to break out from the local optima.The mutation operator algorithm increases the chance of generating more powerful results not less than twice of the original CRO for every basic reaction.Having a lot of selection criteria might increase the complexity for a linear programming model to select a CH.Improved clustering and routing protocols can be developed for better efficiency in CH selection.TC:On2SC: OnFTBA-TC-LEACH (2019) [107]Reduce energy consumption.Enhance energy efficiency.Discusses reaching global optimum using bat algorithm.Ensures the balance between global search and local search capability.Many algorithms and enhancements are added to enhance the local and global search capability of BA which might increase the overall complexity.In the future, the modified BA will be used in relevant optimization problems.TC:On2SC: OnSSA (2020) [108]Maximize energy efficiency.Discusses trade-offs between exploration-exploitation and global search constraints.Focuses on saving energy when the network is low on energy (seasonal monitoring condition).PSO performs better than SSO when lesser number of rounds is applied.SSA can be hybridized with different algorithms to enhance energy efficiency in WSNs.TC:On2SC: O1YSGA (2020) [109]Increase the network lifetime.Reduce energy consumption.The cluster structure of the network is reconfigured by YSGA to ensure an optimal distribution of cluster heads and reduce the transmission distance.Discusses a better balance of exploration-exploitation capabilities of the algorithm.Exchange of roles and change of zone operators are added to enhance the algorithm.YSGA may have the limitation of premature convergence and the tendency to be trapped in local optima when treated as a separate algorithm.CHs far away from the BS can die quickly.The offline execution of the protocol can be considered as the main drawback of the proposed method.Uniform cluster sizes can be implemented for better load balancing.The encoded candidate solutions might be arranged differently so that the dimensionality of the optimization problem can be considerably reduced.TC:On2SC: O1Metaheuristic (hybrid)FCPSO (2015) [118]Prolong the network life cycle.Enhance topology control.The network, nodes are divided into several clusters of fuzzy subsets, all sub-clusters will perform in parallel, thereby the size and time of computation in each subset will be reduced.PSO might fall into local optimum.Different PSO variants can be introduced to solve the problem of cluster head selection.TC:On4SC: OnHSA-PSO (2016) [119]Improve energy consumption.Improve network lifetime.The proposed hybrid approach makes use of the high searching efficiency of HSA combined with the dynamic nature of PSO.It focuses on exploration and exploitation balance in the algorithm.PSO faces high-dimensional optimization limitation and HSA has the limitation of being restricted to only a certain region when they are treated separately.—TC:On2SC: OnmLEACH-T (2017) [121]Reduce power consumption.Increase the network lifetime.Inclusion of genetic crossover and mutation operators to increase the convergence rate.Teaching learning-based optimization (TLBO) algorithm does not have a high convergence rate.Teaching learning-based optimization (TLBO) algorithm can be used in routing of the data for enhanced performance of WSNs.TC:On3SC: O1LEACH-MS (2017) [122]Minimizes energy consumption.Improves the lifetime of the network.The algorithms are hybridized to obtain a balance between exploration and exploitation capability.Hybridizing a full algorithm might increase the complexity of the algorithm.Conventional LEACH algorithm performs better in the initial stages.Other bioinspired algorithms likeK-means, ant colony optimization, artificial immune system, and genetic algorithm can also be combined to design an energy-efficient hybrid scheme.TC:On2SC: O1HABC-MBOA (2019) [123]Improve energy consumption and network lifetime.Focuses on escaping the local minima and delayed convergence problem.Focuses on a balance between exploration and exploitation.The method of spectral clustering is used by the base station to construct the graph modelling for optimized clustering.Levy flight or mutation operators are used for diversity.Both conventional monarch butterfly optimization algorithm and artificial bee colony algorithm suffer from falling into local optima problem when treated separately.For energy stabilized cluster head selection, in the future, a hybrid artificial bee colony and bacterial foraging algorithm can be researched.TC:On2SC: O1SHSA (2019) [125]Improve the overall throughput and residual energy of nodes.Focuses on the exploration and exploitation capability to select the optimal CH.The hybridization of two algorithms might increase the overall complexity.In future, the use of different constraints such as delay and sensing capabilities in different applications can be researched.TC:On2SC: OnmFGF (2019) [126]Maximize the lifetime of the network as well as energy efficiency.Minimize delay.Focuses on achieving a good exploration and exploitation capability.This proposed work also considers the QoS parameter as the major parameter for efficient network performance.GSO suffers in solving the high-dimensional problem and has poor local search capability, where FFOA has less convergence rate in search space when treated separately.The proposed method does not perform efficiently with a lower number of rounds in terms of nodes alive.—TC:On2SC: OnFPU-DA (2020) [128]Maximize energy efficiency.Maximize network lifetime.Ensures the balance between exploration and exploitation is achieved for optimal CH selection.The initialization phase and the number of iterations must be appropriately done as it might lead to a trade-off in terms of achieving the objectives at a reasonable computational cost.The cost function is high at low iteration.In the future, an advanced metaheuristic algorithm can be proposed to attain better coverage and connectivity performance in WSN.TC:On2SC: OnHFAPSO (2020) [129]Minimize the energy consumption.HFAPSO tries hard to mutually balance the trade-off between computational cost and network lifetime.The computational cost of the developed HFAPSO is inexpensive.The time complexity of the proposed algorithm will be increased compared to the nonhybrid algorithms.Both firefly and PSO might fall into local optima.The firefly algorithm can be combined with other nature-inspired algorithms to improve the network lifetime.The proposed method can be tested for real-time applications, can be used for the positioning of heterogeneous WSNs, and can be utilized in mobile WSNs.TC:On4SC: OnHGWSFO (2020) [131]Prolonging network lifetimeFocuses on the trade-off between exploration and exploitation.The coefficient vectors of the GWO algorithm enhance the efficiency of exploitation.SFO algorithm under the variable step size of the plants covers the global search.The grey wolf algorithm can easily fall into the local optimum, and sunflower algorithm can have slow convergence when treated as an individual algorithm.The complexity of the proposed scheme is higher.The current study can be extended by implementing the proposed method on the Internet of Things (IoT) for sensing applications and networks beyond 5G.TC:Odn (d: dimensionality)SC: On


## 7. Discussion

The comparison above comprises 79 pieces of literature on cluster head selection with different implementations in various network environments. From the comparison, we can summarize the network stability, load balancing, reliability, scalability, and overall complexity of the methods. Network stability in WSNs is determined by the frequency of route changes and overhead of network maintenance such as reclustering [138]. Some of the aforementioned methods such as FFCHSA, MCRO-ECP, ECHSR, HABC-MBOA, and iCSHS tend to add more selection criteria or fitness value calculation factors to ensure the CH selected will last a longer period to minimize the frequency of recalculation for a new CH. Heterogeneous WSNs such as GAPSO-H, BEENISH, E-CRCP, INSPSO, EWA, GAOC, and some other protocols are also a great contribution in ensuring the network stability is high as the node with a higher energy level is selected as CH, which will reduce the frequency of reclustering.Network load balancing is a method that ensures that all the nodes consume energy equally, making the nodes degrade together [139]. One prominent limitation in this method is that the network will die off completely at the same point, making the network lifetime prolonging a difficult objective to achieve. Methods such as EBC, distributed clustering scheme, ETTA, LEACH-M, LEACH-ABF, and memetic algorithm are multihop transmission methods that want to achieve a balanced load in the network. Load balance can be achieved by determining a threshold value for the CHs where when the fitness value of a CH is below the threshold value, the network then decides to choose another CH with higher residual energy. This is because a CH is the node that will consume more energy compared to normal nodes. After all, it tends to transfer data as well as aggregate the data of its member nodes in a cluster. Therefore, it can be said that a network that has nodes with different energy values can ensure optimal load balance as used in INSPSO, EC-PSO, and TGDEEC.High reliability in WSNs is essential, as failure to have good reliability may fail the whole network [140]. The hotspot or energy hole problem which is discussed earlier in this paper contributes to the low reliability of a network. In methods such as ABCACO, which is used to simulate fire detection application, and ECHSR which is used in disasters, the management application needs real-time data for better monitoring. Since the hotspot problem makes the CH near the BS die quickly, the network tends to fail quickly as well. Reliability issues are handled by several methods efficiently such as MCDS-MI and SBHRA, where MCDS-MI creates a Steiner tree path for fault tolerance of data transfer, and SBHRA partitions the network to ensure a prominent CH is selected. Even though these methods can resolve reliability issues, they might limit the scalability of the network.Scalability in WSNs is important where it helps to scale and adapt to network topology changes as the network grows larger or the workload increases [141]. In a mobile node environment, the topology often changes, which causes the reclustering frequency to increase. In this situation, a proper CH has to be selected to reduce clustering overhead in a mobile and scalable network, as adopted by the RE2WCA, BeeWSN, BICIoD, SAGA, and EEMCS methods. Not all the methods are efficient in both large-scale and small-scale networks. However, some studies mentioned above have been carried out with varying network sizes to ensure scalability in the proposed method such as GAOC, ABCACO, and GAPSO-H.Furthermore, the overall complexity of the proposed method has to be analyzed mannerly to ensure an energy efficient WSN. However, to ensure that the objective of WSNs is achieved, the complexity of the algorithms or methods is usually ignored. For example, hybrid algorithms such as HSA-PSO, SHSA, FGF, and HFAPSO can impose a higher architectural complexity as well as a higher processing complexity, as they run two algorithms to find the optimal solution. Complexity indirectly contributes to the energy consumption of a network, where if there is a high load of processing that has to be done to select the optimal CH, more energy is consumed by the network. This opens a path for deeper research on the complexity of the methods proposed.


### 7.1. Nonmetaheuristic vs. Metaheuristic

Metaheuristic methods these days are more suitable to be used for cluster head selection in WSNs; as the network grows, the metaheuristic algorithms tend to find optimal solutions quickly as compared to nonmetaheuristic methods. The nonhybrid metaheuristic methods are also not high in complexity compared to the nonmetaheuristic methods, but hybrid algorithms possess higher complexity than both nonhybrid and nonmetaheuristic methods. Metaheuristic methods can also provide an optimal solution in terms of having better convergence and diversity compared to nonmetaheuristic methods. Metaheuristic methods also possess good capability in solving MOOP in WSNs such as NSGA-II [142], SPEA2 [143], OMOPSO [144], and MOSPF [7].


### 7.2. Comparison of Cluster Formation Techniques

Unequal andK-means clustering in WSNs are the commonly used cluster formation techniques to enhance energy efficiency, reliability, and network lifetime. In this paper, 15 pieces of literature were reviewed and summarized in the previous sections. Some of the advantages and limitations of these techniques are described in Table 10.Table 10
Comparison between the advantages and limitations of cluster formation techniques.
MethodsAdvantagesLimitationsUnequal clusteringEADUCEEUCLCCognitive partition unequal clusteringUCEHUC-GA UC-PSOMHACO-UCHelps to solve network hole problem (hotspot problem). Balances the energy consumption of CHs.Improves network lifetime.Deploying the unequal clusters can be tedious and may cause process overhead.Not very scalable.Might take a long time to form clusters.K-means clusteringMk-meansLCDGRAUnuniform K-meansKC-GAKC-PSOEasy to implement.Helps to solve energy hole problem and isolated node problem.Can only be effectively used for small-scale networks.The performance of the network will reduce dramatically if the k value selected is not appropriate.OthersGrid clusteringThe network regions are divided into grids and each grid selects a CH and a data aggregator which lessens the burden of the CH.The CH and data aggregator might die quickly if the network size increases.Not very efficient in terms of enhancing network lifetime.EECRP-HQSND-ICRMFocuses more on coverage of the target area by nodes for better QoS.Dijkstra algorithm is used to solve the shortest path optimization problem for better routing.Separating the sensing region into four parts makes it an application-specific deployment.Even though cluster formation techniques might seem like they solve WSN-related problems, an active intervention is still needed to solve the scalability problem. Furthermore, for all the other methods discussed in CH selection, section clusters are formed based on some criteria like the distance between a node and a CH and the energy level of a CH. This is to ensure that the nodes are prevented from joining wrong clusters which might later exhaust the energy of a node because of the long transmission distance.


### 7.3. Open Issues and Future Direction

In this paper, we have thoroughly discussed the various nonmetaheuristic and metaheuristic methods and their implementations in various environmental settings. Even though there are many methods explained here which can be used in various applications, there are still many problems and issues that exist in wireless sensor networks. The future of WSNs leads to the integration of WSNs into the Internet of Things (IoT) as Industrial Revolution (IR) 4.0 suggests more development of machines and things fitted with sensors [145]. Besides this, developments in vehicular ad hoc networks (VANETs) and smart city applications that use WSNs are also growing rapidly.The most common problems faced by this WSN development are energy and quality of service (QoS). To have a WSN with better performance and a longer lifetime, these problems have to be mitigated simultaneously. The minimization of energy consumption and maximization of QoS leads to the multiobjective optimization problem (MOOP). There is very little research on solving the MOOP, which paves a path for deeper research using various metaheuristic algorithms to obtain optimal solutions.Moreover, security is another common issue faced by WSNs in face of the rapid growth of technology. Applications used in health and military need a high level of security for the data collected. Deploying traditional security patches is not a viable option as it needs a high number of resources, and this might also deteriorate the QoS of the system. As such, there is a need to develop a mechanism that can efficiently ensure the confidentiality and integrity of data as well as minimum resource usage in a WSN. When we talk about VANETs and smart city applications, it is important to know that in a highly mobile system, the collection and aggregation of data are much more difficult as compared to a static system. It also needs highly real-time data for the systems to ensure the safety of people on the road. Since the usage of these systems is huge, it is important to adapt to machine learning techniques for efficiency and better performance.In IoT systems, the data from multimedia sensors such as surveillance systems can be big, as images of a monitoring area are captured. Managing huge sizes of data can be difficult as the nature of a WSN is to contain sensors with small memory size, small storage size, small battery capacity, and small sensing and communication area. Without proper resource allocation, it may cause further issues such as packet dropping problems. These huge data must be retrieved, processed, and stored safely, which can be achieved by using deep learning techniques. Furthermore, it is important to ensure that the delay, latency, and throughput are given more attention, as the data are crucial to the application.


## 7.1. Nonmetaheuristic vs. Metaheuristic

Metaheuristic methods these days are more suitable to be used for cluster head selection in WSNs; as the network grows, the metaheuristic algorithms tend to find optimal solutions quickly as compared to nonmetaheuristic methods. The nonhybrid metaheuristic methods are also not high in complexity compared to the nonmetaheuristic methods, but hybrid algorithms possess higher complexity than both nonhybrid and nonmetaheuristic methods. Metaheuristic methods can also provide an optimal solution in terms of having better convergence and diversity compared to nonmetaheuristic methods. Metaheuristic methods also possess good capability in solving MOOP in WSNs such as NSGA-II [142], SPEA2 [143], OMOPSO [144], and MOSPF [7].


## 7.2. Comparison of Cluster Formation Techniques

Unequal andK-means clustering in WSNs are the commonly used cluster formation techniques to enhance energy efficiency, reliability, and network lifetime. In this paper, 15 pieces of literature were reviewed and summarized in the previous sections. Some of the advantages and limitations of these techniques are described in Table 10.Table 10
Comparison between the advantages and limitations of cluster formation techniques.
MethodsAdvantagesLimitationsUnequal clusteringEADUCEEUCLCCognitive partition unequal clusteringUCEHUC-GA UC-PSOMHACO-UCHelps to solve network hole problem (hotspot problem). Balances the energy consumption of CHs.Improves network lifetime.Deploying the unequal clusters can be tedious and may cause process overhead.Not very scalable.Might take a long time to form clusters.K-means clusteringMk-meansLCDGRAUnuniform K-meansKC-GAKC-PSOEasy to implement.Helps to solve energy hole problem and isolated node problem.Can only be effectively used for small-scale networks.The performance of the network will reduce dramatically if the k value selected is not appropriate.OthersGrid clusteringThe network regions are divided into grids and each grid selects a CH and a data aggregator which lessens the burden of the CH.The CH and data aggregator might die quickly if the network size increases.Not very efficient in terms of enhancing network lifetime.EECRP-HQSND-ICRMFocuses more on coverage of the target area by nodes for better QoS.Dijkstra algorithm is used to solve the shortest path optimization problem for better routing.Separating the sensing region into four parts makes it an application-specific deployment.Even though cluster formation techniques might seem like they solve WSN-related problems, an active intervention is still needed to solve the scalability problem. Furthermore, for all the other methods discussed in CH selection, section clusters are formed based on some criteria like the distance between a node and a CH and the energy level of a CH. This is to ensure that the nodes are prevented from joining wrong clusters which might later exhaust the energy of a node because of the long transmission distance.


## 7.3. Open Issues and Future Direction

In this paper, we have thoroughly discussed the various nonmetaheuristic and metaheuristic methods and their implementations in various environmental settings. Even though there are many methods explained here which can be used in various applications, there are still many problems and issues that exist in wireless sensor networks. The future of WSNs leads to the integration of WSNs into the Internet of Things (IoT) as Industrial Revolution (IR) 4.0 suggests more development of machines and things fitted with sensors [145]. Besides this, developments in vehicular ad hoc networks (VANETs) and smart city applications that use WSNs are also growing rapidly.The most common problems faced by this WSN development are energy and quality of service (QoS). To have a WSN with better performance and a longer lifetime, these problems have to be mitigated simultaneously. The minimization of energy consumption and maximization of QoS leads to the multiobjective optimization problem (MOOP). There is very little research on solving the MOOP, which paves a path for deeper research using various metaheuristic algorithms to obtain optimal solutions.Moreover, security is another common issue faced by WSNs in face of the rapid growth of technology. Applications used in health and military need a high level of security for the data collected. Deploying traditional security patches is not a viable option as it needs a high number of resources, and this might also deteriorate the QoS of the system. As such, there is a need to develop a mechanism that can efficiently ensure the confidentiality and integrity of data as well as minimum resource usage in a WSN. When we talk about VANETs and smart city applications, it is important to know that in a highly mobile system, the collection and aggregation of data are much more difficult as compared to a static system. It also needs highly real-time data for the systems to ensure the safety of people on the road. Since the usage of these systems is huge, it is important to adapt to machine learning techniques for efficiency and better performance.In IoT systems, the data from multimedia sensors such as surveillance systems can be big, as images of a monitoring area are captured. Managing huge sizes of data can be difficult as the nature of a WSN is to contain sensors with small memory size, small storage size, small battery capacity, and small sensing and communication area. Without proper resource allocation, it may cause further issues such as packet dropping problems. These huge data must be retrieved, processed, and stored safely, which can be achieved by using deep learning techniques. Furthermore, it is important to ensure that the delay, latency, and throughput are given more attention, as the data are crucial to the application.


## 8. Conclusion

Clustering in WSNs in recent years is given more attention due to its advantages of reducing energy consumption and extending the network lifetime. Low-energy adaptive clustering hierarchy (LEACH) protocol was the first clustering protocol introduced, which gave rise to the idea of creation of many existing clustering techniques. In clustering, the cluster head selection is one of the most vital phases, where the CH is the node that collects data from its cluster members, aggregates, and transmits it to the BS efficiently. As such, failure to select the most qualified node as a CH might collapse the whole network’s efficiency and performance. Besides, cluster formation is also another important phase in clustering, where proper cluster formation can enhance energy efficiency and lifetime.In this study, we have done a complete survey on techniques and methods of clustering in WSNs published between the years 2015 and 2021. The methods are categorized into nonmetaheuristic and metaheuristic algorithms, for a better and clearer understanding of these two approaches. Furthermore, these approaches are categorized into several environmental settings such as mobility, multihop data transfer, single-hop data transfer, heterogeneity, and other parameters (homogeneous and static). Both CH selection and cluster formation of these two approaches in various environmental settings are described in detail. Moreover, the parameter settings, advantages, limitations, and future suggestions given by the respective authors are listed in detail. A brief discussion on the network’s stability, load balancing, reliability, scalability, and overall complexity of the methods is also conducted, to help use a particular technique in certain applications.



---

*Source: 5322649-2022-03-28.xml*