Optimization of Cluster Head Selection in Wireless Sensor Networks Using Hierarchical Algorithm and Genetic Algorithm
محورهای موضوعی : Computer Engineering
1 - Department of Computer Engineering, Ali. C., Islamic Azad University, Aliabad Katoul, Iran.
کلید واژه: Optimization, cluster head selection, wireless sensor networks, hierarchical algorithm and genetic algorithm,
چکیده مقاله :
In the field of wireless sensor networks, optimal determination of the cluster head node is one of the most important issues, because the appropriate selection of the cluster head node can significantly decline energy utilization and ultimately increase the lifetime of the network. One way to decline energy utilization in wireless sensor networks is to cluster sensors. Two issues in this regard are how to select appropriate cluster heads and how to send aggregated data from cluster heads to sinks. In this investigation, it is suggested that when selecting cluster heads, it should be taken into account that cluster heads will play a role in sending each other's data to the sink, so that cluster heads can be selected that can perform multi-step data transmission with less energy utilization. The efficiency of the proposed method in clustering and routing of wireless sensor networks is much higher than the comparison method, which allows us to ignore this difference in computational complexity. The proposed method was evaluated using simulation and compared with several methods that solve the two problems of cluster head selection and multi-step routing between them independently in terms of network lifetime criteria. The results showed that the proposed method has improved the network lifetime.
In the field of wireless sensor networks, optimal determination of the cluster head node is one of the most important issues, because the appropriate selection of the cluster head node can significantly decline energy utilization and ultimately increase the lifetime of the network. One way to decline energy utilization in wireless sensor networks is to cluster sensors. Two issues in this regard are how to select appropriate cluster heads and how to send aggregated data from cluster heads to sinks. In this investigation, it is suggested that when selecting cluster heads, it should be taken into account that cluster heads will play a role in sending each other's data to the sink, so that cluster heads can be selected that can perform multi-step data transmission with less energy utilization. The efficiency of the proposed method in clustering and routing of wireless sensor networks is much higher than the comparison method, which allows us to ignore this difference in computational complexity. The proposed method was evaluated using simulation and compared with several methods that solve the two problems of cluster head selection and multi-step routing between them independently in terms of network lifetime criteria. The results showed that the proposed method has improved the network lifetime.
[1] RongZheng and Guanghui He and Xue Liu,"Location-free Coverage Maintenance in Wireless Sensor Networks," Technical report UH-CS-05-15,Dept. of Computer Science,University of Houston,2005.
[2] M. Cardei and J. Wu,"Coverage in Wireless Sensor Networks," in Handbook of Sensor Networks,M. Ilyas and I. Mahgoub (eds.),CRC Press,2004,ISBN: 0-8493-1968-4
[3] YOUJIA HAN, HUANGSHUI HU, AND YUXIN GUO, Energy-Aware and Trust-Based Secure Routing Protocol for Wireless Sensor Networks Using Adaptive Genetic Algorithm, accepted January 9, 2022
[4] YOUJIA HAN, HUANGSHUI HU, AND YUXIN GUO, Energy-Aware and Trust-Based Secure Routing Protocol for Wireless Sensor Networks Using Adaptive Genetic Algorithm, accepted January 9, 2022
[5] Seo H. S., Oh S. J., , Lee W. C., “Evolutionary genetic algorithm for efficient clustering of wireless sensor networks”. CCNC’09 Proceedings of the 6th IEEE Conference on Consumer Communications and Networking Conference, pp. 258- 262, 2019.
[6] Daie, P., Li, S. (2016). Hierarchical clustering for structuring supply chain network in case of product variety, Journal of Manufacturing Systems,38: 77-86.
[7] ZHENCHUN WEI, FEI LIU, XU DING, LIN FENG, ZENGWEI LYU, LEI SHI1, AND JIANJUN JI, K-CHRA: A Clustering Hierarchical Routing Algorithm for Wireless Rechargeable Sensor Networks, accepted November 25, 2018,
[8] HASSAN EL ALAMI, (Student Member, IEEE), AND ABDELLAH NAJID, ECH: An Enhanced Clustering Hierarchy Approach to Maximize Lifetime of Wireless Sensor Networks, accepted July 28, 2019
[9] Fan Xiangning1,2 Song Yulin2 1 Institute of RF-&-OE-ICs, Improvement on LEACH Protocol of Wireless Mitchell M., An Introduction to Genetic Algorithms. MIT Press, Cambridge, MA, 2016.
[10] Toor, A. S., & Jain, A. K. (2019). Energy Aware Cluster Based Multi-hop Energy Efficient Routing Protocol using Multiple Mobile Nodes (MEACBM) in Wireless Sensor Networks. AEU - International Journal of Electronics and Communications, 102 ,41-53 .https://doi.org/10.1016/j.aeue.2019.02.006
[11] Nehra, V., Sharma, A. K., &Tripathi, R. K. (2019). NMR inspired energy efficient protocol for heterogeneous wireless sensor network. Wireless Networks, 25(6), 3689-3700. https://doi.org/10.1007/s11276-019-01963-2
[12] Gupta, P., Raj, P., Tiwari, S., Kumari, P., &Mehra, P. S. (2020, Apr 1). Energy efficient diagonal based clustering protocol in wireless sensor network. Proceedings of the International Conference on Innovative Computing & Communications (ICICC), Delhi 110089, India https://ssrn.com/abstract=3565781
[13] Elsmany, E. F. A., Omar, M. A., Wan, T. C., &Altahir, A. A. (2019). EESRA: Energy Efficient Scalable Routing Algorithm for Wireless Sensor Networks. IEEE Access, 7, 96974-96983. https://doi.org/10.1109/ACCESS.2019.2929578.
[14] Anzola, J., Pascual, J., Tarazona, G., & Gonzalez Crespo, R. (2018). A clustering WSN routing protocol based on kd tree algorithm. Sensors, 18(9), 2899. https://doi.org/10.3390/s18092899
[15] L. Kaufman and P. J. Rousseeuw, "Partitioning around medoids (program pam)," Finding groups in data: an introduction to cluster analysis, vol. 344, pp. 68-125, 1990.
[16] N. R. Roy and P. Chandra, "A note on optimum cluster estimation in leach protocol," IEEE Access, vol. 6, pp. 65690-65696, 2018.
[17] Dean, J. and Ghemawat, S., “MapReduce: simplified data processing on large clusters”, Communicationsof the ACM, 51(1), pp.107-113 (doi: 10.1145/1327452.1327492).
[18] W. Wang, D. Wang, & Y. Jiang, “Energy efficient distributed compressed data gathering for sensor networks,” Ad Hoc Networks, Vol. 58, pp. 112-117, 2017.
[19] W.R. Heinzelman, A. Chandrakasan, & H. Balakrishnan, “Energy-efficient communication protocol for wireless microsensor networks,” In Proceedings of the 33rd annual Hawaii international conference on system sciences on IEEE, pp. 1-10, 2020
[20] G. Gupta, & S. Jha. “Integrated clustering and routing protocol for wireless sensor networks using Cuckoo and Harmony Search based metaheuristic techniques,” Engineering Applications of Artificial Intelligence, Vol. 68, pp. 101-109, 2018.
[21] T. Bhowmik, & I. Banerjee, “An Improved PSOGSA for Clustering and Routing in WSNs,” Wireless Personal Communications, Vol. 117, pp. 431-459, 2021.
Journal of Applied Dynamic Systems and Control,Vol.8., No.2., 2025: 7-15
| 15 |
Optimization of Cluster Head Selection in Wireless Sensor Networks Using Hierarchical Algorithm and Genetic Algorithm
Leila Ajam 1*
1* Corresponding Author: Department of Computer Engineering, Ali. C., Islamic Azad University, Aliabad Katoul, Iran.
Email: leilaajam@yahoo.com
Received: 2025.02.06; Accepted: 2025.05.14
Abstract– In the field of wireless sensor networks, optimal determination of the cluster head node is one of the most important issues, because the appropriate selection of the cluster head node can significantly decline energy utilization and ultimately increase the lifetime of the network. One way to decline energy utilization in wireless sensor networks is to cluster sensors. Two issues in this regard are how to select appropriate cluster heads and how to send aggregated data from cluster heads to sinks. In this investigation, it is suggested that when selecting cluster heads, it should be taken into account that cluster heads will play a role in sending each other's data to the sink, so that cluster heads can be selected that can perform multi-step data transmission with less energy utilization. The efficiency of the proposed method in clustering and routing of wireless sensor networks is much higher than the comparison method, which allows us to ignore this difference in computational complexity. The proposed method was evaluated using simulation and compared with several methods that solve the two problems of cluster head selection and multi-step routing between them independently in terms of network lifetime criteria. The results showed that the proposed method has improved the network lifetime.
Keywords: Optimization, cluster head selection, wireless sensor networks, hierarchical algorithm and genetic algorithm
1. Introduction
With recent advances in micro-electromechanical systems (MEMS) technology, low-power digital circuits, RF (radio frequency) sketching, Wireless sensor networks (WSN) are one of the computing technologies with high potential. Several different and diverse applications of WSNs. Contain use in collecting information in chaotic and irregular environments, monitoring weather and climate, detecting biological and chemical agent threats, and monitoring healthcare. These include the use of various equipment such as cameras, audio devices, and various physical parameters measured by sensors.
Wireless sensor networks includes wireless nodes that have limited memory and finite fiscal abilities. One of the important limitations of sketchinging this type of network is providing the power required by the sensor nodes. This is because it is not possible to alteration the battery after implementing wireless sensor networks, one of the important sketching problems in WSNs is to decline energy utilization by using energy-saving hardware, operating systems, and communication protocols.
2. Clustering in Wireless Sensor Network
Among the clustering protocols suggested for WSNs, the LEACH clustering protocol has gained particular importance among researchers in this field [1].
Among the reasons why this clustering protocol is important are the specific features of cluster formation in this protocol, which include:
· Random
· Adaptive
Self-configuring
Fig. 1. Wireless sensor network clustering[1]
1.2- Random clustering
This means that in each period, a certain number of nodes randomly choose themselves as the cluster head. The duty of cluster head is not pre-assigned to special nodes.
2.2- Adaptive clustering
Nodes that were cluster heads in the first stage cannot be elected as cluster heads in the next step. The selection of cluster heads in each stage depends on the previous stage. Therefore, we predict that all nodes will be elected as cluster heads at least once in several stages. But we will see later that this will not be the case.
3.2- Self-configuring clustering
In this clustering protocol, without the involvement of an foreign factor or a special node, the nodes of the network create a cluster, which makes the Leach clustering protocol scalable. We see below that scholars have taken many steps to ameliorate the productivity of clustering.
Unfortunately, in most of them, this feature has been lost and a specific node is responsible for selecting the cluster heads. This has a negative influence on the scalability of the network [2].
There are a series of general rules in the LEACH clustering protocol. To learn more about this protocol, we will review these rules:
1. At each stage, a random set of nodes is choice as the cluster head. This cluster head choice is not specific to any predetermined nodes.
2. Nodes that have been the cluster head in the current period cannot be candidates for the role in the next period. Therefore, the selection of cluster head candidates in each period is determined by the previous period. Thus, it is expected that after a certain number of periods, all nodes will have been selected as cluster head at least once. We will see that this will not be the case.
3. Network nodes in this protocol form clusters without the help of any external factor or specific node of the network. This increases the scale of adoption of this protocol. As we will see later, many alterations have been made by researchers to improve the productivity of this protocol. But unfortunately, in most of them this feature has been lost and a specific node is responsible for choosing the cluster head. This negatively affects network scalability.
4. With local control from the nodes of a cluster to the cluster head and from the cluster head to the main station, information is transferred; there is no need for a specific node in the network to transmission data.
5. The MAC protocol used in LEACH saves a fair amount of energy utilization by providing a Sleep feature for energy utilization.
6. Packets exalterationd between sensor nodes in the LEACH protocol have a field to determine the packet type, which is used to decide how to deal with different packets.
7. In the LEACH protocol, time is divided into equal-length segments called periods. Each period is operationally divided into two phases:
Phase 1 - Set-up
Phase 2 - Steady-State
Fig. 2. LEACH protocol[11]
The startup phase also includes two stages.
• Cluster head choice stage
• Cluster formation stage
8. In the cluster head choice stage, nodes are randomly assigned to cluster heads based on a probability function.
9. During the cluster formation phase, nodes send their membership requests to the cluster heads so that the cluster heads select their members based on a series of criteria.
3. Related works
In a study titled Improving Energy Utilization in Wireless Sensor Networks Using Genetic Algorithm, they investigated. Compared to the manners discussed, the trend of improving energy utilization in this manner is evident, and it was found that the slow trend of node death in this manner is slower than in other manners, and that the improvement was achieved at the moment of deactivation of the first node, and this percentage of growth relative to the suggested manners has improved the energy utilization by 33.3 percent, and that at the moment of death, the first node has increased 8 units later than in the previous manner. Therefore, an improvement in energy utilization has been formed in this network. Therefore, this investigation was started with the focus and goal of saving energy utilization and increasing the lifespan of the network. The simulation outcomes showed an improvement in energy utilization and the desired outcome was achieved [3].
In a study titled "Improving the cluster head selection manner and routing between clusters using genetic and ant colony algorithms" they investigated energy produtivity in WSNs. In this investigation, the aim was to be more the energy productivity of WSNs by combining genetic algorithm and ants. In the suggested manner, the meta-heuristic manner of genetic algorithm was used to solve the problem and select the cluster heads. After optimizing the location of the cluster heads in each cluster, to receive data, given that the transmission rate is the same for all sensors, a path with the lowest energy utilization must be found. For this purpose, the ant colony algorithm was used. The investigation findings showed that the presented algorithms decline the energy consumed in the transmission path by reducing the data transmission length, which is why the transmission length is considered as a cost function because the transmission rate is the same among the cluster heads. The outcomes also showed the improvement and suitability of the presented algorithms for achieving the goal of this investigation [4].
In a study titled Combination of Hierarchical Clustering and Genetic Algorithm to Decline Energy Utilization in Wireless Sensor Networks, they investigated. This protocol uses genetic algorithm to cluster network nodes based on energy level and neighborhood criteria. In the suggested manner, using hierarchical clustering algorithm, sensor nodes are divided into a number of clusters and then, from the nodes of each cluster, desirable cluster heads are selected for routing operations using genetic algorithm [5].
In a study titled “Optimizing Energy Consumption in WSNs Using Clustering,” they investigated energy utilization optimization in WSNs. WSNs, which are generally used for Supervision and control in a defined environment, They usually consist of a number of sensor nodes that are in a dense manner distributed in the environment. One of the most important challenges of this type of network is the lifetime and energy utilization of the nodes, which can be prevented and compensated by clustering. In fact, due to the large interval between each sensor, a lot of energy is deducted from them. Now, by clustering, we can divide the network into a number of independent clusters, each of which will have a cluster head. In this paper, clustering manners for decreasing energy utilization in WSNs are presented [6].
In a study titled Presenting a New Clustering Manner for Optimizing Energy Utilization in WSNs Using Genetic Algorithm, they investigated. In this study, using an unconventional application of the Fourier transform on the location of nodes and their energy, we determine the number and location of cluster heads in an desirable way and then use the genetic algorithm to specify the desirable state of the Fourier transform output. The fitness criterion will be based on the minimum energy consumed by the network nodes during each period of data transmission, which will lead to a balance in network energy utilization and, as a outcome, a longer network lifetime. The productivity of this manner and the suggested fitness criterion have been proven by simulation compared to previous clustering algorithms such as LEACH [7].
Tianshu Wang et al. (2018) studied genetic algorithms for clustering and energy-desirable routing in WSNs in a study titled. In order to recovery energy performance and increase network lifetime, an energy-desirable clustering and routing manner based on genetic algorithm called GECR is presented. We enhance the optimum solution obtained in the previous period of the network to the initial population for the current period, thereby improving the search productivity.
Furthermore, the clustering and routing scheme are integrated in a Alone chromosome to compute the total energy utilization. We obtain the fitness function out rightly based on the total energy utilization, thus reinforcing the energy performance. Also, load balancing is calculated when creating the evaluation function. Therefore, Balance energy utilization among nodes. In addition, GECR achieves the highest energy productivity (equivalent to thriftiness) with the lowermost average energy used by the cluster heads and the lowermost energy used by all nodes in the harvest [8].
Genetic algorithms are among the most famous and widely used evolutionary algorithms. This algorithm consists of a population of solutions (called chromosomes). As this algorithm runs, the creation of chromosomes gradually improves and subsequent generations are created until the algorithm reaches a termination condition. In past research, genetic algorithms have been used to solve various optimization issues in the field of sensor network clustering and have high efficiency. In the continuation of this section, examples of the application of genetic algorithm to select cluster heads are reviewed [9].
In another study, the LA2D-GA manner was presented, which, unlike other studies, uses two-dimensional chromosomes. Each two-dimensional chromosome represents a network area that is divided into a grid with equal sizes, and the presence of a value of "zero" in the grid means that there is no node in it, and the numbers "one" and "two" mean that there is a normal node and a cluster head node in that grid, In order. In this manner, instead of generating the initial population by accident, according to the LEACH algorithm, the population is initialized. The evaluation function is expressed to minimize the transmission cost and minimizes the energy consumed in data transmission [10].
In [10], a routing manner for heterogeneous sensor networks is suggested that selects nodes with higher energy as cluster heads and uses a multi-point a model for communication. The suggested algorithm divides the network area into different regions and determines a mobile node to each region.
In [11], a protocol based on the heterogeneous sensor network model is suggested that considers additional energy to improve the performance of nodes close to the sink node. By combining nodes that have more energy or other nodes, the sustainable and lifespan of the sensor network are increased.
The clustering algorithm presented in [12] diagonally divides the network area into regions and then forms clusters. The algorithm uses the k-means method to organize clusters, and sensor nodes guide data to the sink node or base station using a multi-communication model.
In the EESRA routing protocol [13], the protocol aims to increase the network lifetime and increase its size. In this protocol, The cluster head is randomly selected and adopts a three-layer hierarchical routing to reduce the traffic load of the cluster head and uses a multicast transmission model to guide sensor data within the cluster. In addition, each cluster head chooses one or more eligible nodes to act as cluster communities. Cluster populations are answerable for broadcasting and collecting measurement data from their cluster members and transmitting them to the cluster head using a hybrid MAC protocol that includes collision prevention solutions and sleep scheduling of sensor nodes for data measurement.
In [14], the K-D tree algorithm is described, a hierarchical routing protocol that uses network partitioning to arrange nodes and clusters. The network is divided into areas by this protocol and forms clusters in each area. A hierarchical network of nodes is formed by a K-D tree, which transfers data to the main node according to the location of each node. From the outcomes obtained, we see that there has been a good improvement in network delay and productivity.
4. Suggested method
One way to decline energy consumption in WSNs is to cluster sensors. Two issues in this regard are how to select appropriate cluster heads and how to send consolodidated data from cluster heads to the sink. In this study, it is suggested that when selecting cluster heads, it should be taken into account that cluster heads will play a role in sending each other's data to the sink, so that cluster heads can be selected that can perform multi-hop data transmission with less energy utilization.
The suggested manner consists of three main steps: 1) clustering and determining initial cluster heads, 2) data transfer, and 3) selecting the appropriate cluster head, which is shown in Algorithm 1.
The suggested manner consists of three main steps: 1) clustering and determining initial cluster heads, 2) data transfer, and 3) selecting the appropriate cluster head, which is shown in Algorithm 1.
Algorithm 1 :Suggested manner |
Initialization: Number of nodes, initial energy value of nodes, spatial coordinates of nodes, determination of base station location, determination of number of clusters. Step 1: K-means clustering and determination of initial cluster heads Step 2 : For each node we have: A. Sending information to the base station and reducing the node's energy level (relationship 3.1) B. In each formed cluster, calculate the chance of each node to be a cluster head using a fuzzy approach and the criteria of residual energy, centrality, trust, interval to the cluster head of relationships (4 to 7). Step 3 : Cluster head selection: choose the node with the utmost chance as the new cluster head of relations (4 to 7) Step 4 : Go to step 2. Repeat this loop until the number of nodes with energy level greater than 𝐸𝑡𝑟 is greater than the threshold 𝑁𝑡𝑟; otherwise: Step 5 : Cluster formation: Formation of new clusters using the fuzzy approach and the criteria of residual energy, interval to cluster head, interval to base station of relations (4 to 7) Step 6 : Go to step 2. Repeat this loop until the number of clusters consisting of nodes with energy levels greater than 𝐸𝑡𝑟 is greater than the threshold 𝐶𝑡𝑟; otherwise: Step 7: End of the algorithm |
4.1- Clustering and determining initial cluster heads
Since the process of building a cluster of wireless sensors is similar to the partitioning of the sample space by clustering algorithms, and since the placement conditions of the sensors are unstable, in the suggested manner, using the k-means 7 algorithm [15], the initial clustering of the sensor nodes is performed and then the initial cluster heads are selected. In addition to fast convergence and the lack of complex calculations, the k-means algorithm is less sensitive to noise and outliers compared to similar algorithms such as k-means. Since wireless sensors are dispersed in uncontrolled environmental conditions, they are easily exposed to errors and attacks that make sensor data unreliable and inaccurate. In these situations, sensor data that differs greatly from healthy behaviors is considered outlier or anomalous data. In the first step, this algorithm randomly selects k cluster representatives from between the sensor nodes. The value of k is calculated according to equation (5).[16]In the suggested manner, this sampling is done without replacement. In other words, the cluster representative is not selected repeatedly. In the second step, each node is assigned to the closest cluster representative and clusters are created.
4.2- Data transfer
After the forming of clusters, the sensed data of the non-cluster head nodes from the environment is sent to the Relevant cluster heads. After receiving the data from all the members of their cluster, the cluster heads aggregate the data and send it to the base station. During the exchange of information, the network energy is declined through data sensing, data sending, data receiving, and data aggregation. According to the Heinzelman energy model [17], each node consumes 𝐸𝑇 energy to send 𝑏 bits of data to ainterval𝑑 from itself, which is calculated from the below equation.
(1)
Where 𝐸𝑒𝑙𝑒𝑐 is the energy consumed by the sender circuit, 𝐸𝑓𝑠 and 𝐸𝑚𝑝 are the activation energies of the power amplifier for the two open and multipath states, and 𝑑0 is the threshold calculated by equation (2).
(2)
According to equation (1), if the interval is greater than the sill 𝑑0 by adjusting the transmitter power amplifier, the multipath model can be used; otherwise, the open space model is used for the channel. Also, the quantity of energy required to receive 𝑏 data bits at the receiver node is calculated from the following equation.
(3)
supposedly that the area of interest is a square with dimensions 𝑀×𝑀 square meters in which 𝑛 live nodes are uniformly divided and assuming that the base station is located in the center of the area, therefore the interval of each node to the base station or the interval of each node to its corresponding cluster head is less than 𝑑0. Therefore, the energy utilization of the cluster heads is calculated from equation (4).
(4)
(5)
Where 𝑘 is the number of cluster heads, 𝐸𝐷𝐴 is the cost of aggregating one bit of data per transmission to the base station, and 𝑑𝑡𝑜𝐵𝑆 is the average interval between the cluster head and the base station (inter-cluster interval). The energy consumed in member and non-cluster head nodes can be calculated from equation (6).
(6)
Where 𝑑𝑡𝑜𝐶𝐻 is the average interval between the member node and its relevant cluster head (intra-cluster interval). The energy consumed in each cluster in each period is calculated from equation (7).
(7)
The complete energy utilization in the network is equal to:
(8)
By calculating the energy utilization of the network for one period of data transmission from the wireless sensor nodes to the base station with different values of 𝑘, the desirable number of cluster heads can be calculated. The desirable number of cluster heads is the value for which the energy utilization of the network reaches the minimum value.
The importance of the desirable number of cluster heads is because if the number of cluster heads is greater than the desirable number, the energy utilization of the nodes and the time for selecting the cluster head increase, and if the number of selected cluster heads is less than the desirable value, the size of each cluster increases, and as a outcome, the cluster heads face severe overload and high traffic for data transference, in which case the likelihood of failure and loss of information and even rapid death of the cluster head node is very high. In both cases, the network life is declined.
4-3- Cluster head selection
Selecting a valid cluster head is a very significant subject in wireless sensor network clusters. The suggested manner expressed the following standards to choose the cluster head:
• remainder energy: This parameter indicates the residual energy in each sensor node. If the residual energy of a sensor node increases, the probability of that node changing to the cluster head increases.
Behavioral trust: This criterion is determined based on the positive behavior (pos) and negative behavior (neg) of each network node. In the suggested manner, successful data conduction by the sensor node is considered as positive behavior and unsuccessful data conduction by the sensor node is considered as negative behavior. The behavioral trust value is calculated using the mathematical equation (9):
(9)
The higher the trust value of a sensor node's behavior, the better the chance of that node being selected as the cluster head. Using this criterion leads to the interaction of trusted nodes with each other.
Centrality: This measure calculates the degree of centrality of the cluster head Ci relative to other cluster heads {cj}k = 1 in a space of dimensions 𝑀 × 𝑀. The higher the degree of a sensor node, the higher its chance of being a cluster head.
(10)
• Average interval from the cluster head to its member nodes: The smaller this interval is for a sensor node, the higher the Opportunity of being the cluster head.
(11)
where N is the number of sensor nodes and k is the number of cluster heads. In equations (10) and (11), it is calculated from the 2-dimensional (Euclidean) equation. As a reminder, assuming that p and q are the D-dimensional coordinates of two sensor nodes, the interval between the two nodes is calculated from equation (12).
(12)
4-4- Genetic algorithm workflow
Genetic algorithms, instead of working on parameters, deal with their encoded form. For example, suppose we want to maximize the function f(x,y)=X^2+Y^2 (with the constraints x and y being integers and x between 0 and 7 and y between 0 and 31). The most common encoding manner is binary encoding.
Therefore, the parameter is replaced with a suitable sequence of numbers. Any integer from 0 to 31 can be represented with 5 bits, and any integer from 0 to 7 can be represented with 3 bits. For example, the figure below shows the binary encoding of two variables x= 9 and y=5.
Therefore, to each point in the two-dimensional space (x,y) there corresponds a sequence in the form below.
Gene: The coded value of each variable is called a gene. In binary coding, the gene corresponding to x=9 is: 01001.
Chromosome: A string or sequence of genes that serves as a coded form of a possible solution (suitable or unsuitable) to a given problem is called a chromosome.
Population: In each iteration of the genetic algorithm, a certain number of chromosomes are evaluated. The set of these chromosomes is called the population.
Fitness number: The fitness or not is measured by a criterion that is related to the objective (optimization item).
Transposition or combination operator: This operator is applied to a pair of chromosomes. A type of this operator randomly swaps two chromosomes from a broken point and the broken parts of the two chromosomes.
5. Analysis of results
The suggested algorithm is an asymmetric and competitive clustering manner. The advantage of the suggested manner is the use of the genetic cuckoo search algorithm to desirably select the network clustering structure with the aim of reducing energy utilization and increasing network throughput. Accordingly, first the fitness of each node for selection as a cluster head is calculated by the suggested algorithm. After performing this operation, each node informs its neighbors of the probability of its selection, and then each node determines its own cluster head by comparing the conditions of its neighbors with the probability of its selection. After selecting the cluster heads, an optimization model is used to determine the size of each cluster. In the suggested manner, a hierarchical and genetic algorithm is used to determine the appropriate cluster head nodes and assign the appropriate radius to each cluster. After assigning the network cluster composition, a game theory-based routing algorithm is used to determine the appropriate paths to send data to the base station. The efficiency of the suggested manner has been evaluated in a simulation environment and its productivity has been compared with past algorithms. The imagery outcomes be seen that using the suggested manner, also to reducing energy utilization, it is possible to prevent traffic at the network level and distribute the load more efficiently.
5.1- Test settings
The simulation of the suggested manner was performed using MATLAB software and in accordance with the values stated. To evaluate the suggested manner, first, networks with 100 sensors and 4 cluster heads were considered, which were scattered in an area of 100 × 100 square meters. The radio range of each sensor was 40 meters and the radio range of each cluster head was 200 meters. Then, the number of cluster heads was increased from 4 to 40, and to keep the density constant, the number of sensors was also increased to 100 and the area was also increased to 100 × 100.
The data generation rate of each cluster was set to 1000 Bits/Period and the initial energy of each cluster head was set to 5 Joules. Three different conditions for the location of the well were considered: the center of the square, the lower left corner, and the middle of the lower side. In the genetic algorithm, the initial population size is 300 chromosomes and the roulette wheel selection manner with a rate of 70% is used. The genetic algorithm is run for 100 generations in each run.
The algorithm described for calculating the energy in the connected nodes is based on the model presented in [18].
In this experiment, a sensor network is considered in a limited environment in which the sensor nodes are randomly and uniformly distributed.
In this experiment, the lifetime of the sensor network is first investigated using the suggested clustering algorithm and the outcomes obtained are compared with the iPSOGSA algorithms in ICSHS in [20] and the Leach manner in [19].
5.2- Simulation results
Network lifetime is an important parameter for evaluating the productivity of clustering algorithms. Figure 3 shows the number of active network nodes in different periods of the suggested algorithm and the compared algorithms.
Fig. 3.Total energy used by nodes in each step
As shown in Figure (3), the network lifetime in the suggested manner is about 500 cycles longer than the network lifetime in the PSOGSA and CSHS manners and about 1100 cycles longer than the Leach manner. The reason for this can be attributed to the better performance of the suggested manner in determining cluster sizes and data routing. These outcomes demonstrate the productivity of the suggested algorithm in energy utilization and indicate that clustering using genetic algorithm and social property of nodes in the suggested manner can distribute the network load in a balanced manner to prevent premature energy depletion of a node. The energy used in the nodes at each stage is shown in Figure 4.
Fig.4.Total energy used by all nodes in each step
As the simulation outcomes in Figure (4) show, the energy utilization in the suggested manner is clearly lower than the iCSHS, PSOGSA, and Leach manners, which will outcome in greater network productivity and longer lifetime during the simulation. The suggested manner determines the size of each cluster with the aim of achieving the lowest energy utilization and selects nodes as cluster heads with the aim of making the network energy efficient. Also, the suggested routing algorithm based on game theory will distribute the load in the network and prevent the imposition of a large load on the nodes a period the base station, such that in the formed clustering structure, the size of the clusters close to the destination node is determined to be small, and as a outcome, the increase in energy utilization for forward data transmission and also the imposition of a large traffic load on the nodes close to the base station will be prevented. Figure (5) shows the number of successfully exchanged packets in the network for different periods in the simulation.
Fig.5.Number of packets transmitted in different stages
In Figure (5), the performance evaluation outcomes of the suggested manner from the point of view the number of packets sent are compared with the iCSHS, iPSOGSA, and Leach algorithms. As shown in Figure (5), the suggested manner can transmit more than one and a half times more data packets between network nodes than the iCSHS manner and nearly 1.8 times more than the iPSOGSA manner; Because with the continued use of the network, the sensor nodes in the iPSOGSA and iCSHS manners lose their energy, but in the suggested manner, there is still a sufficient number of nodes available for sending data and routing packets. This difference is greater compared to the Leach manner, and the suggested manner is able to exchange 5.8 times more data packets between network nodes compared to the Leach manner. This productivity in sending is the outcome of using the asymmetric clustering structure in the suggested manner. In addition to reducing energy utilization, this algorithm can transmit large data packets at the network level with appropriate load distribution. In the following section, we will examine the effect of varying the number of network nodes on the efficiency of the suggested manner.
In these experiments, the performance of the suggested manner is compared with the iCSHS[20], iPSOGSA, [21], and Leach [19] manners. In this investigation, the number of network sensor nodes varies between 100 and 300 nodes, and the network lifetime and the total number of transmitted packets are calculated. The global network lifetime is shown in Figure 6 by changing the number of sensor nodes.
Fig.6.Network lifetime by changing the number of network sensor nodes
Figure 7 also shows the number of network packets alteration for these alterations.
Fig.7. Packets exchanged for alterations in the number of sensor nodes
Figure 7 shows that as the number of sensor nodes becomes greater, the lifetime of the network becomes greater. The number of energy sources becomes greater with the number of sensors and they are involved in the routing process, which prolongs the lifetime of the network. If the clustering and routing protocol desirably uses the energy resources of the sensors, it increases the lifetime of the network.
This condition for the suggested manner can be clearly seen in Figure (7), and the suggested manner, with asymmetric clustering of network nodes and efficient data routing between cluster head nodes, prevents the energy waste of sensor nodes and further increases the network lifetime. By increasing the network lifetime by the suggested manner, it is natural that more data packets can be successfully exchanged between sensor nodes. The outcomes obtained indicate that the suggested algorithm works well in correctly clustering nodes and in efficient data routing. Based on the outcomes, the suggested manner can increase the network lifetime by 26.85% compared to the iCSHS manner and by 128.52% compared to the LEACH manner. On the other hand, the suggested manner can increase the average number of packets exchanged in the network by 31.04% compared to the iCSHS manner and by 519.25% compared to the LEACH manner. On the other hand, the computational complexity in the suggested manner and the iPSOGSA and iCSHS manners is equal to On log, which comes from the computational complexity of the population sorting operator, where " denotes the number of active nodes in the network. This complexity in the LEACH manner is equal to (n).However, although the LEACH manner has lower computational complexity than the suggested manner, the productivity of the suggested manner in clustering and routing of wireless sensor networks is much higher than the LEACH manner, which allows this difference in computational complexity to be ignored.
6. Conclusion
In this study, a manner was suggested to simultaneously solve two problems: cluster head selection and desirable multi-step routing from cluster heads to sinks. The suggested manner was assessed using simulation and compared with several manners that solve the two troubles: cluster head choice and multi-step routing between them independently, in terms of network lifetime criteria. The outcomes showed that the suggested manner improved the network lifetime.
In this investigation, an asymmetric clustering and routing algorithm was suggested for balanced load distribution in wireless sensor network. One of the advantages of the proposed manner is the choice of cluster head nodes using the suggested algorithm to minimize the energy utilization of the network. The cluster head is determined by genetic algorithm. In the suggested manner, the radius of each cluster is also determined using an optimization model. An algorithm based on the hierarchical algorithm is also used to route data between cluster heads in the network. According to the outcomes obtained, the suggested manner is an efficient clustering algorithm for lowering energy utilization and increasing network lifetime. The routing algorithm used in the suggested manner can improve the packet sending speed by distributing the appropriate load and selecting a reliable and more energy-efficient path compared to previous manners.
7. Future proposals
To continue the investigation, it is suggested that, apart from the PSO algorithm and the MHRM manner, other manners that exist for determining cluster heads and multi-step routing should be combined and used to dissolve the two problems at the same time and the outcomes should be examined. The use of other evolutionary algorithms to improve the produtivity of routing algorithms can be the basis for future work.
References
[1] RongZheng and Guanghui He and Xue Liu,"Location-free Coverage Maintenance in Wireless Sensor Networks," Technical report UH-CS-05-15,Dept. of Computer Science,University of Houston,2005.
[2] M. Cardei and J. Wu,"Coverage in Wireless Sensor Networks," in Handbook of Sensor Networks,M. Ilyas and I. Mahgoub (eds.),CRC Press,2004,ISBN: 0-8493-1968-4
[3] YOUJIA HAN, HUANGSHUI HU, AND YUXIN GUO, Energy-Aware and Trust-Based Secure Routing Protocol for Wireless Sensor Networks Using Adaptive Genetic Algorithm, accepted January 9, 2022
[4] YOUJIA HAN, HUANGSHUI HU, AND YUXIN GUO, Energy-Aware and Trust-Based Secure Routing Protocol for Wireless Sensor Networks Using Adaptive Genetic Algorithm, accepted January 9, 2022
[5] Seo H. S., Oh S. J., , Lee W. C., “Evolutionary genetic algorithm for efficient clustering of wireless sensor networks”. CCNC’09 Proceedings of the 6th IEEE Conference on Consumer Communications and Networking Conference, pp. 258- 262, 2019.
[6] Daie, P., Li, S. (2016). Hierarchical clustering for structuring supply chain network in case of product variety, Journal of Manufacturing Systems,38: 77-86.
[7] ZHENCHUN WEI, FEI LIU, XU DING, LIN FENG, ZENGWEI LYU, LEI SHI1, AND JIANJUN JI, K-CHRA: A Clustering Hierarchical Routing Algorithm for Wireless Rechargeable Sensor Networks, accepted November 25, 2018,
[8] HASSAN EL ALAMI, (Student Member, IEEE), AND ABDELLAH NAJID, ECH: An Enhanced Clustering Hierarchy Approach to Maximize Lifetime of Wireless Sensor Networks, accepted July 28, 2019
[9] Fan Xiangning1,2 Song Yulin2 1 Institute of RF-&-OE-ICs, Improvement on LEACH Protocol of Wireless Mitchell M., An Introduction to Genetic Algorithms. MIT Press, Cambridge, MA, 2016.
[10] Toor, A. S., & Jain, A. K. (2019). Energy Aware Cluster Based Multi-hop Energy Efficient Routing Protocol using Multiple Mobile Nodes (MEACBM) in Wireless Sensor Networks. AEU - International Journal of Electronics and Communications, 102 ,41-53 .https://doi.org/10.1016/j.aeue.2019.02.006
[11] Nehra, V., Sharma, A. K., &Tripathi, R. K. (2019). NMR inspired energy efficient protocol for heterogeneous wireless sensor network. Wireless Networks, 25(6), 3689-3700. https://doi.org/10.1007/s11276-019-01963-2
[12] Gupta, P., Raj, P., Tiwari, S., Kumari, P., &Mehra, P. S. (2020, Apr 1). Energy efficient diagonal based clustering protocol in wireless sensor network. Proceedings of the International Conference on Innovative Computing & Communications (ICICC), Delhi 110089, India https://ssrn.com/abstract=3565781
[13] Elsmany, E. F. A., Omar, M. A., Wan, T. C., &Altahir, A. A. (2019). EESRA: Energy Efficient Scalable Routing Algorithm for Wireless Sensor Networks. IEEE Access, 7, 96974-96983. https://doi.org/10.1109/ACCESS.2019.2929578.
[14] Anzola, J., Pascual, J., Tarazona, G., & Gonzalez Crespo, R. (2018). A clustering WSN routing protocol based on kd tree algorithm. Sensors, 18(9), 2899. https://doi.org/10.3390/s18092899
[15] L. Kaufman and P. J. Rousseeuw, "Partitioning around medoids (program pam)," Finding groups in data: an introduction to cluster analysis, vol. 344, pp. 68-125, 1990.
[16] N. R. Roy and P. Chandra, "A note on optimum cluster estimation in leach protocol," IEEE Access, vol. 6, pp. 65690-65696, 2018.
[17] Dean, J. and Ghemawat, S., “MapReduce: simplified data processing on large clusters”, Communicationsof the ACM, 51(1), pp.107-113 (doi: 10.1145/1327452.1327492).
[18] W. Wang, D. Wang, & Y. Jiang, “Energy efficient distributed compressed data gathering for sensor networks,” Ad Hoc Networks, Vol. 58, pp. 112-117, 2017.
[19] W.R. Heinzelman, A. Chandrakasan, & H. Balakrishnan, “Energy-efficient communication protocol for wireless microsensor networks,” In Proceedings of the 33rd annual Hawaii international conference on system sciences on IEEE, pp. 1-10,2020
[20] G. Gupta, & S. Jha. “Integrated clustering and routing protocol for wireless sensor networks using Cuckoo and Harmony Search based metaheuristic techniques,” Engineering Applications of Artificial Intelligence, Vol. 68, pp. 101-109, 2018.
[21] T. Bhowmik, & I. Banerjee, “An Improved PSOGSA for Clustering and Routing in WSNs,” Wireless Personal Communications, Vol. 117, pp. 431-459, 2021.
