|Computers, Materials & Continua |
Optimization of Head Cluster Selection in WSN by Human-Based Optimization Techniques
1Department of Electrical & Electronics Engineering, Istanbul Gelisim University, Istanbul, 34310, Turkey
2Department of Energy Systems Engineering, Ankara Yildirim Beyazit University, Ankara, 06010, Turkey
3MLALP Research Group, University of Sharjah, Sharjah, 27272, UAE
4Department of Computer Science, University of Sharjah, Sharjah, 27272, UAE
*Corresponding Author: Osama Ahmad Alomari. Email: firstname.lastname@example.org
Received: 19 December 2021; Accepted: 08 March 2022
Abstract: Wireless sensor networks (WSNs) are characterized by their ability to monitor physical or chemical phenomena in a static or dynamic location by collecting data, and transmit it in a collaborative manner to one or more processing centers wirelessly using a routing protocol. Energy dissipation is one of the most challenging issues due to the limited power supply at the sensor node. All routing protocols are large consumers of energy, as they represent the main source of energy cost through data exchange operation. Cluster-based hierarchical routing algorithms are known for their good performance in energy conservation during active data exchange in WSNs. The most common of this type of protocol is the Low-Energy Adaptive Clustering Hierarchy (LEACH), which suffers from the problem of the pseudo-random selection of cluster head resulting in large power dissipation. This critical issue can be addressed by using an optimization algorithm to improve the LEACH cluster heads selection process, thus increasing the network lifespan. This paper proposes the LEACH-CHIO, a centralized cluster-based energy-aware protocol based on the Coronavirus Herd Immunity Optimizer (CHIO) algorithm. CHIO is a newly emerging human-based optimization algorithm that is expected to achieve significant improvement in the LEACH cluster heads selection process. LEACH-CHIO is implemented and its performance is verified by simulating different wireless sensor network scenarios, which consist of a variable number of nodes ranging from 20 to 100. To evaluate the algorithm performances, three evaluation indicators have been examined, namely, power consumption, number of live nodes, and number of incoming packets. The simulation results demonstrated the superiority of the proposed protocol over basic LEACH protocol for the three indicators.
Keywords: WSN; LEACH; coronavirus herd immunity optimizer; cluster head selection
Wireless sensor networks (WSNs) became very popular in the last few years because of their numerous applications such as crisis management, health care, transportation, forest fire detection, and industrial applications . WSN can monitor many physical parameters, like vibration, temperature, strain, pressure, etc. . It also can be used in smart cities for traffic and parking management, atmospheric pollution detecting, monitoring structural health, and preventing noise pollutions. Tracking military vehicles is another example, by sensing their speeds and trajectories and by communicating with other sensor nodes, this information will be sent to the Sink/Base Station Node (BSN) for processing .
A sensor-node consists of a radio transceiver, microcontroller, sensing device, and a battery as energy source . They are considered somehow cheap components, but their costs can vary depending on their design complexity. Limited battery power is the main source of limiting WSN lifecycle . For a given sensor-node type, the challenge is to keep these sensor-node alive for a maximum time by reducing the energy consuming during the sensor-node active operating time . Sensor nodes play a critical role in sensing, monitoring, data processing, and collaborative decision making, which will pose challenges to the network with complex systems, such as energy, bandwidth, speed, storage, and node localization .
Data are collected by sensor nodes from the field, processed, and sent to the BSN according to various routing algorithm strategies . The physical/chemical data are sensed, processed, and sent wirelessly to the user without the need for infrastructure to the BSN, which acts as gateway between sensor nodes and application user . BSN has improved memory and computing ability compared to normal sensor-node, enables it to perform complex processing and classification procedures before sending data to the supervisory party via a communication network . Transmitting data from the field to the BSN using a routing algorithm presents the most critical operation in terms of communication and energy-consuming affecting WSN performances and lifetime .
Optimization have gained wide popularity since their concept has first recognized by the founder of algebra Al-Khwarizmi. Optimization is the process of finding the minimum or maximum optimal solution for a specific problem or a specific arithmetic operation within a range of constraints . It should be known that not all optimization algorithms deal with the same problems and give the same result. Therefore, the problem must be carefully analyzed to identify the most appropriate algorithm for it to obtain the optimal result. Some researches have used optimization to improve the routing problem in WSN by reducing their energy consumption, enhancing the localization of nodes, and bypassing the problem of bandwidth to prolong the network lifetime. Thus, the follow-up of developments on algorithms has been concluded, after several attempts and research, that meta-heuristic algorithms are one of the preferred algorithms to be used in improving the performance of WSN. Thereby Prompted by the aforementioned points, we propose a protocol that improves the CHs selection process to reduce the energy consumption and extend the WSN network lifecycle of LEACH protocol based on one of the recently meta-heuristic optimizations, which is the Coronavirus Herd Immunity Optimizer (CHIO).
The paper is summarized as follow: in Section 2 the related works are presented. Section 3 defines the problem and is divided into three subsections: in Sections 1 and 2 a brief explanation of both LEACH and CHIO protocols is given, and Section 3 presents the proposed protocol.Section 4 provides the experimental results and discussion of simulating LEACH-CHIO Finally, Section 5 conclude the work.
2 Related Works
To extend the life of WSNs, several hierarchical routing protocols have been developed including LEACH. Many researches have proposed the optimization of some WSN parameters to improve the characteristics of the LEACH and other routing protocols by reducing power consumption.
An energy-saving clustering protocol based on an Artificial Bee Colony (ABC) optimization algorithm has been designed . It is a centralized control algorithm with a proposed fitness function, taking node power level, power consumption, and quality of service as constraints. The simulation results show an improved efficiency compared to LEACH and Particle Swarm Optimization (PSO)-based routing protocols in terms of network lifecycle as well as reducing the delay. A new improved version of LEACH by using ABC for a dynamic clustering routing protocol has been proposed in . The residual energy collected from the simulation shows a significant improvement in the case of ABC-based LEACH.
A population-based metaheuristic algorithm, for optimal CH selection, known as the Bat Swarm Optimization (BSO) has been introduced in . The simulation has been performed for four network deployments with a fitness function intended to inter-cluster compactness. The results show a better lifecycle range compared with the classic LEACH. A Multi-Level Hybrid clustering routing Protocol (MLHP) has been presented in . It is based on Gray Wolf Optimizer (GWO) and consists of three levels for selecting the optimal CHs. The simulation results have shown improved performance compared to the most popular routing protocols in terms of network life, power efficiency, and stability period. A routing protocol for optimum data transmission, based on the Ant Colony Optimizer (ACO) has been designed in . The simulation results have detected an improvement in the energy consumption, network lifespan, and the number of dead nodes in comparison to Energy Efficient Ant Based Routing (EEABR), LEACH-ACO, and the Optimized Ant Routing Algorithm (OARA). A new hierarchical clustering protocol inspired by the behaviors of the Artificial Fish Swarm Algorithm (AFSA) has been introduced in . The optimal selection of CH depends on the three behaviors of AFSA which are: Prey CH, Swarm CH, and Follow CH. It aims to establish a balanced hierarchical structure to ensure a good distribution of CH and its members by minimizing the distance between them as well as between the CH and BSN. The simulations have shown an improvement in terms network lifetime compared to the LEACH-C protocol. A clustering model for choosing the optimal CHs using a hybrid algorithm has been presented . The algorithm (FPU-DA) is a combination of Firefly and Dragonfly optimization algorithms concepts. The simulation results show an increase in performance compared to some well-known optimization algorithms in terms of delay, safety, and power. An improved routing protocol based on the Firefly Optimization Algorithm (FOA) for optimal CH selection and cluster formation has been suggested . It has been compared to the Firefly's basic algorithm, LEACH, and PSO. The results have shown a better and more consistent performances than the other protocols.
An Energy-Balanced Cluster-Routing Protocol (EBCRP) based on PSO with five mutations operators to balance the number of sensor nodes inside the clusters has been presented in . A rotating CHs selection process is used. An optimal hybrid algorithm based on a simulated annealing optimization algorithm has been introduced in . It is used for optimal CHs selection to optimize the energy consumption. A case study is examined and the simulation results demonstrated the superiority of the proposed protocol in the throughput, accuracy, efficiency, and energy utilization over LEACH, Differential Evolution, HSA (Harmony Search Algorithm), and Modified HSA. In , a multi-objective routing protocol called EEHRP for optimal route selection has been designed. The performance efficiency in terms of throughput, delay, energy, and overhead has been evaluated. The results of EEHRP outcomes the Simple Hybrid Routing Protocol (SHRP), and DyMORA algorithms. A novel Type II Fuzzy Logic-based Cluster Head (CH) selection with Low Complexity Data Aggregation (T2FLCH-LCDA) technique for WSN has been developed in . The model includes a two-phase process (clustering and data aggregation). The technique shows an improvement in energy efficiency, lifetime, Compression Ratio (CR), and power dissipation.
Recently, CHIO as a new optimizer, has started to attract attention. The parameters of the CHIO algorithm have been modified to solve one of the Np-hard problems which is the capacitated vehicle routing problem CVRP . The enhanced CHIO has shown a competitive result in comparison with other methods. The modified CHIO has shown its efficiency in solving and adopting the problem of CVRP.
In this section the process of both LEACH and CHIO as well as the proposed centralized cluster-based energy-aware protocol LEACH-CHIO, is explained.
3.1 LEACH Protocol
LEACH Protocol is a self-organizing cluster-based routing protocol that has first been introduced by Heinzelman . The main objective of LEACH is to increase the network life by balancing the energy dissipation through a pseudo-random selection of the CH in every round. The number of clusters, and then the number of CHs, is determined by the percentage of the node to become a CH. The algorithm is composed by two phases namely; the set-up and the steady-state, where each one is made up of many overlapping sub stages. The set-up phase known also as the advertisement phase is composed by two sub stages which are the CH selection and the clusters formation. The CH selection starts by choosing CHs among candidate sensor nodes according to the equation:
where, P is the CHs probability (percentage of the node to become CH), r is the current round index, G is the set of nodes that was not chosen as CH in the last epoch (1/P rounds).
Node n selects a random number RN(n) between 0 and 1, and compare it with the calculated T(n). Node n is selected as CH if RN(n) < T(n), otherwise, a next node is examined as CH candidate. WSN nodes use this distributed process to performs the decision on CH selection depending on the amount of remaining energy. After 1/P rounds, the process is reset to start a new selection. CH known as a bridge-node between sensor nodes and the BSN to minimize energy dissipation during data transmission by adopting clustering strategy as depicted in the Fig. 1. This is positively reflected to the WSN life cycle. After the selection of CHs, the formation of clusters begins by integrating nodes within radio range as cluster member as shown in Fig. 2.
CHs advertise themselves by broadcast its ID using Carrier Sense Multiple Access (CSMA) MAC protocol to the surrounding nodes which in turn determine the optimal CH to join based on Received Signal Strength Indicator (RSSI). Sensor nodes within range receive signal invites (advertisements) from all CHs but after assessing the strength of the received signal, one cluster with the higher power (presumably the closest) is selected and then a join message is sent to the CH. In order to reduce operating energy losses, the CH creates a TDMA slots transmission schedule for its cluster members, so nodes are switch-off when they don't have information to exchange.
The clusters are formed; the steady-state phase starts by collecting data from sensor nodes, sending it to the CH according to the predetermined schedule. CHs aggregates the data from the nodes in the clusters, then perform signal processing functions to compress the data into a single packet signal and sent it to BSN. The CH node must keep its receiver on to receive all the data from the nodes in the cluster. The aggregation process at this stage plays a positive role in reducing energy consumption, as it reduces the bandwidth and unnecessary communication traffic resulting from the nodes sensing to similar data. After transmitting data from various sensor nodes to the CH, data is aggregated in a convenient form, and finally transmitted to the BSN [27,28].
3.2 Coronavirus Herd Immunity Optimizer (CHIO)
Coronavirus Herd Immunity Optimizer (CHIO), is a natural-inspired human-based algorithm . The inspiration for the name for this algorithm comes from the new virus that has recently spread in the world (Covid-19). The CHIO algorithm deals with two concepts: social distancing and herd immunity. The transition from the susceptible state to the infected and from there to the immunized state against infection depends on the herd immunity threshold that has been taken from the Darwinian method (survival of the fittest). The population of herd immunity in case of an epidemic has been divided into three cases due to the reproduction rate and based on the principle of social distancing (susceptible, infected, and immune). The principle of herd immunity can be achieved by vaccination to immunize the majority of individuals from the disease, or when exposing a category of infected population to another category of susceptible population with weaker immunity. The speed of disease spread is called the basic reproduction rate . The immune system of individuals will create an immune memory of the disease. This later will lead the majority of the population to be immune from infection again. The principle of social distancing, is based on reducing the number of infected cases to control the outbreak of the disease. This principle has represented in the algorithm by taking the difference between a person's current state and that of a randomly selected person of the three possibilities: susceptible, infected, immune, and it called Random-Random-Random strategy. To determine whether the gene of individual is preserved in its current state or affected by social distancing, it depends on the basic reproduction rate , which is done through three rules:
where is a random number between 0 and 1. Where refers to the newly generated infected case due to the effect of social distancing which is represented by taking the difference of currently selected status of a gene () and a randomly selected status of the gene of an infected case () depending on the status vector (), where .
And for the susceptible case, whose value ranges between () and it is represented by:
where is taken from the difference of currently selected status of a gene and a randomly selected gene status of a susceptible one depending on the status vector (), where . The last case is the immune case, in which the value of r is between () and represented by:
Depending on the principle of social distancing, the difference has taken between the current state of the gene with a randomly selected gene of an immune case depending on the status vector (), where . Based on the previous equations, the population of herd immunity and the objective function or the immunity rate has also been calculated for each new case. Then the fatality can be detected by monitoring the immunity rate of the currently infected case . Where if the case has not developed from infected to immune after a certain number of iterations as shown in parameter , the current case will be considered dead. The advantage of this step can be shown in terms of diversifying the current population and bypassing the best local solution. Then at the end of the iterations, the herd immunity, which contains two types of cases, namely susceptible and immune, has achieved with the disappearance of the infected cases. In Fig. 3 the flowchart of Coronavirus Herd Immunity Optimizer (CHIO) is depicted.
A centralized cluster-based energy-aware protocol based on the CHIO algorithm is proposed in this paper, LEACH-CHIO. WSN routing protocol (LEACH) is implemented with the use of one of the newest optimization algorithms (CHIO), for increasing the network lifetime. LEACH-CHIO considers nodes with the highest energy level to be the CHs, that means; selecting optimal CHs depending on their energy levels. The optimal selection of CHs results in a net saving in energy because the process of data aggregation and transmission to the BSN, which is performed by CHs, consumes more energy than other activities. The newly proposed protocol aims to select the most efficient CH in terms of energy to be able to extend the life of the network and deliver a greater number of data packets compared to LEACH. In Tab. 1 the synonyms of CHIO algorithm parameters with its corresponding in WSN is presented.
LEACH-CHIO operates as LEACH, which consists of several rounds with two phases namely: set-up phase and steady-state phase. Sensor nodes are randomly distributed to locations within the deployment area at the start of each simulated scenario. Furthermore, the BSN provides members for each cluster regarding Nodes (n) are the cases of herd immunity population, either immune or susceptible and represent the CHs. The round starts with a set-up phase through which the nodes send their information to the BSN including current energy level, ID, and cross-distance between all nodes and between the nodes and BSN. In turn, the BSN does the selection of CHs depending on the remaining energy by operating the proposed protocol. It selects the top nodes in terms of energy level, energy consumption in the network, and adopting the shortest distance between the communication elements to perform its task as CH to the end of the current round. The shortest distance can be considered by the nodes themselves by calculating the distance between each other and between BSN, relying on the received signal strength that comes from the advertisement messages each sensor-node sends. After that, it transmits these data to the BSN for utilizing it in the process of selecting CH and its members. The GPS has not been used in this protocol, to reduce the cost of energy, where it is sufficient to exchange advertising messages between nodes for determining their locations. For sending the advertisement messages CSMA-MAC protocol is used.
3.3.2 Communication Energy Model
The communication in WSN is based on the first order radio model (free-space model) because the transmission distance is limited without real obstacles between nodes. Communication activities between sensor nodes as transmitter-receiver are the cause of energy dissipation due to non-ideal electronics and the physical fading of the wireless channel . The Transmitter and the Receiver circuits are considered as analogous except the amplifier. The circuit dissipation for and is :
where and , are the and in-circuit dissipation, L is the transmitted/received bits number while is a constant depending on electronic circuits. Because of the limited nodes inter-distance, the signal energy fading between and is equal to:
where, d is the − distance, and is the amount of consumed energy/bit in the RF-amplifier. For a large nodes inter-distance networks, the multi-path fading model is adopted with instead of in Eq. (7). The channel between two sensor nodes is considered as symmetric in energy losses characteristics where the total consuming energy and for L-bit transmission/reception are:
3.3.3 Fitness Function
Optimal CH selection is done by minimizing the predefined fitness function . For the present work, a fitness function of three values has been selected with a very important role in expanding exploration and exploitation within the herd immunity population. The fitness value should be inversely proportional to the amount of energy consumed to choose the optimal CH, meaning that the best choice of CH is with the largest fitness value. The first fitness value is to find the highest energy level for the node (battery level) as shown in the following equation:
where is a parameter to adjust the convexity degree of the fitness function and it specified to 20.72, i is node index, n is the number of nodes in the network, m is CHs number, j is CHs index for the current round and is the node current energy level . The second fitness value is achieved through reducing the energy consumed by taking into consideration the distance between nodes and CH and between the CH and the BSN, which can be seen by the following equation:
where is nodes number in cluster, j is the index of the cluster, is the distance between the BSN and CH, is the distance between node and CH and w is the multiplication of constant value () by time. The third fitness value, includes one of the quality-of-service QoS parameters, which is the data packets delay of the clusters, that can be defined by the total number of data packets received in a certain period that's directly proportional to the number of cluster members (It takes more time in TDMA schedule), it can be represented by the following equation:
where n is cluster number and is the number of cluster member. CH is the node that consumes more energy within the network as it sends the fused data after collecting it from the sensor nodes to the BSN. After a certain energy level, those nodes that were selected as CHs will have insufficient energy to complete these operations if they are selected again as CH, it is best to treat it as a medium-sensing node only. The proposed equation for the fitness function is:
where, δ, β and σ are weight parameters for the fitness function between [0, 1] and must not exceed one when combined. It's used to assign a single fitness value to the fitness functions mentioned in the previous equations to determine whether this node is going to be selected as CH depending on its energy level.
After the BSN identifies the CHs and cluster members for the current round, it sends an announcing message to the network containing the identity of the CHs and their cluster members. The second phase of the round starts when the CH creates a TDMA schedule for each node, based on which they send data in a specific period. This serves to avoid collision between the cluster member data and also contributes to node energy saving. The second phase here is the same as in LEACH protocol, where it turns to sleepy mode after transmitting the data at the specified time. While the CH node must keep its receiver on to receive all the data from the nodes in the cluster. Moreover, CHs aggregates the data from the nodes in the clusters, then perform signal processing functions to compress the data into a single packet signal and finally transmitted to the BSN. This entire process is represented as shown in the flowchart in Figs. 4 and 5.
4 Results and Discussion
To evaluate the performances of the proposed algorithm, the simulation of four scenarios is performed as presented in Tab. 2. In scenario-1 five case studies are simulated with 5 clusters depending on the number of nodes in the WSN as indicated in Tab. 3. While in the scenario-2 a WSN has been simulated with a number of clusters equal to 5% of the total number of nodes, that means when a WSN consists of 20 nodes, one cluster is presented, and for a 100-node WSN, 5 will be the number of clusters. Scenario-3 is based on the selection of 10% of the total number of nodes as clusters. Finally, 15% of the number of nodes is selected in scenario-4. There are five case studies for each scenario that differ in its number of nodes, as shown in Tab. 3. These case studies are selected to examine the behavior of LEACH and LEACH-CHIO protocols for various node number, and with variety of cluster numbers for every WSN. The number of rounds is fixed for all simulations to 1500, which is approved to be enough for results analysis. The total energy for deployed sensor nodes is a function of the sensor-node number. It is selected to be the same for all simulations, equal to 0.05 J/sensor-node. Other characteristics of energy dissipation due to transmission, reception, data aggregation, and packet length are listed in Tab. 4 according to the model adopted in the development of LEACH . The dependence of these values will not affect the conclusions of the simulation because it is a comparative study between LEACH and LEACH-CHIO.
The topology and the simulation results of the 20-node WSN case study with a single cluster is depicted in Figs. 6–9. The total residual energy of LEACH at the end of simulation rounds (1500) is 0.00002272 J, while for LEACH-CHIO is equal to 0.00135 J. Both protocols start at 0.2 J. The energy values are scaled by 100 in the figure for clarity. At the midpoint of simulation (round 750), LEACH-CHIO has preserved 26.21% of its initial energy, while LEACH is almost vanished with an amount of 0.0009362 J. LEACH-CHIO start to lose its first node after round 812 when LEACH has only one alive node. LEACH is transmitting 2949000 data packets, whereas LEACH-CHIO had 6206000 packets received. The residual energy comparison between LEACH-CHIO and LEACH for the scenario-4, 100-node WSN is shown in Fig. 10. The node death process starts at round 1338 for LEACH-CHIO, and end the simulation with 57 alive nodes, while all nodes die before round 600 for LEACH. While in the case of LEACH, all its node has died after round 888 as shown in Fig. 11. Preserving sensor-node energy plays an important role in influencing both the number of alive nodes and then the number of received packets. The total number of received packets during the simulation process of 100 nodes WSN for LEACH protocol is 2704000, while in case of LEACH-CHIO is 9439000.
To clarify the effect of clusters number on both protocols performance, the results of the previous four scenarios are used for a comparison for only the 100-node WSN. The results for 5% (5 clusters), 10% (10 clusters), and 15% (15 clusters) for both LEACH and LEACH-CHIO, are shown in the Figs. 12 and 13.
The comparison is done to test the optimum number of clusters for the proposed algorithm (LEACH-CHIO). The optimum number of clusters in LEACH, has been determined analytically to be 5% as reported in . According to the simulation, it has also been proved the effectiveness of choosing 5%. Last node dies at rounds 1045, 725, and 892 for 5%, 10%, and 15% respectively. Prolong in the lifetime of the sensors network, provides an increase in the total number of data packets received by the BSN. In addition, it has also decreased the network energy consumption, which leads to getting the extreme benefit from the WSN. In Fig. 13, the proposed LEACH-CHIO protocol is examined in the same context with 5%, 10%, and 15% clusters. Results have shown that the protocol is performing better for higher cluster number (15%). The node death process starts at round 1018 for the case study of 5 cluster, while it is in rounds 1275 and 1338 for 10 and 15 clusters respectively. This proves that the greater the number of clusters, the longer it leads to a prolonged lifecycle of the network sensor nodes, which in turn leads to an increase in the number of data packets received by the BSN, and a reduction in the energy consumption within the network. This fruitful results is owing to the fact that CHIO has aided the Leach protocol in finding the best locations of cluster head, which is leading to decrease the power consumption in the routing process and boost the life of the network.
LEACH protocol has considered as one of the well-known hierarchical routing protocols in terms of performance in the WSN. One of the drawbacks of the LEACH protocol is the use of a pseudo-random process for selecting CH which leads to the fast power consumption of the WSN. This energy is consumed by the communication processes between the node and between the CHs of the BSN. Thus, many researchers are taking serious steps regarding optimizing this protocol to reduce power consumption and extending the life of the network. One of the latest optimization protocols that appeared recently is CHIO, which is adopted in this research for the purpose of optimizing the process of CHs selection in LEACH by selecting the sensor-node with the highest energy. Four scenarios have been simulated for a WSN with different number of nodes and clusters using LEACH-CHIO in comparison to LEACH alone. The simulation results presented the total residual energy of the nodes, the total number of alive nodes and the total number of packets received in the network. By observing the simulation results for the four scenarios, the network improvement is clearly seen when 15% of the nodes are used as CHs. This proves that the greater the number of clusters, the longer it leads to a prolonged lifecycle of the network sensor nodes, which in turn leads to an increase in the number of data packets received by the BSN, and a reduction in the energy consumption within the network. As a future work, we can suggest simulating with a wide geographical range of WSN deployment to observe the effect of the distance with the same percentages of CH selection. Since LEACH-CHIO is a centralized algorithm, so may by maximizing the distance a decline in the performance happens. Moreover, improvements in terms of modification or hybridization can be applied on CHIO that lead to enhance the performance of WSN.
Funding Statement: The authors received no specific funding for this study.
Conflicts of Interest: The authors declare that they have no conflicts of interest to report regarding the present study.
|This work is licensed under a Creative Commons Attribution 4.0 International License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.|