# Clone Chaotic Parallel Evolutionary Algorithm for Low-Energy Clustering in High-Density Wireless Sensor Networks

Authors: Rui Yang; Mengying Xu; Jie Zhou
Journal: Scientific Programming
 (2021)

---

## Abstract

Because the sensors are constrained in energy capabilities, low-energy clustering has become a challenging problem in high-density wireless sensor networks (HDWSNs). Usually, sensor nodes tend to be tiny devices along with constrained clustering abilities. To have a low communication energy consumption, a low-energy clustering scheme should be designed properly. In this work, a new cloned chaotic parallel evolution algorithm (CCPEA) is proposed, and a low-energy clustering model is established to lower the communication energy consumption of HDWSNs. By introducing CCPEA into the low-energy clustering, an objective function is designed for evaluating the communication energy consumption. For this problem, we define a clone operator to minimize the communication energy consumption of HDWSNs, use the chaotic operator to randomly generate the initial population to expand the search range to avoid local optimization, and find the parallel operator to speed up the convergence speed. In the experiment, the effect of CCPEA is compared to heuristic approaches of particle swarm optimization (PSO) and simulated annealing (SA) for the HDWSNs with different numbers of sensors. Simulation experiments demonstrate that the presented CCPEA method achieves a lower communication energy consumption and faster convergence speed than PSO and SA.


---

## Body

## 1. Introduction

In recent years, because of technological innovation and progress, the volume of microsensor devices has reached the size of a grain of sand. The reduction in volume has made the functions of large-scale wireless sensor networks more perfect, and the cost has also been greatly reduced [1, 2]. Besides, with the development of wireless communication technology and distributed wireless sensor network technology, the high-density wireless sensor networks (HDWSNs) with a large number of nodes, which are densely distributed, gradually become a hot research topic. The HDWSNs are usually made up of a great number of microsensor nodes distributed in the surveillance region at random without any infrastructure support and are self-organized into clusters [3, 4]. The high-density wireless sensor network generally refers to a network in which a large number of wireless sensor nodes are arranged in a small geographic area to achieve a dense perception of targets. At present, this kind of network mostly adopts tree-like and star-like structures and seldom arranges the aggregation node; the sensor node can reach the base station directly or through a few hops. Due to the high deployment efficiency of high-density sensors and strong environmental adaptability, they profoundly impact many fields, such as national defense and military, smart home, agricultural engineering, environmental monitoring, and many other fields [5, 6].The HDWSNs are widely used in remote atmospheric monitoring, seismic, radiation, and medical data collection due to their outstanding advantages in information quality, network robustness, network cost, and network adaptability [7, 8]. The HDWSNs are generally self-organizing networks but have different design goals from traditional mobile ad hoc networks. The latter maximizes bandwidth utilization by optimizing routing and resource management strategies in a highly mobile environment while providing users with certain service quality assurance [9]. Most nodes in HDWSNs are static, and there are only a few special nodes that may move. The change of network topology generally originates from the demise of node energy exhaustion or the demise of node caused by other external reasons [10, 11].In HDWSNs, sensor nodes are usually randomly dropped by drones to the target area [12]. Although the deployment is simple, the randomness of the deployment cannot guarantee the rationality of the distribution distance of the sensor nodes. Besides, the communication distance between the sensor nodes is also limited, which leads to wasted power consumption for sensor node communication [13, 14]. Therefore, how to select cluster head nodes for clustering in large-scale and high-density sensor networks, which can reduce sensor energy consumption while ensuring the completion of detection tasks and improve the life cycle of sensor networks, is a crucial problem within the research of high-density sensor networks [15, 16]. Due to their size limitation, small wireless sensors have constrained clustering ability [17]. Considering that the power supply capability of sensors is limited, low-energy clusters play a vital role in minimizing communication energy consumption, while most research for low-power clustering is corresponding to a low-power clustering algorithm [18, 19].In [20], a shuffled frog leaping algorithm (SFLA) technique is presented to search the communication energy consumption in wireless sensor networks (WSNs). SFLA can get lower communication energy consumption than the genetic algorithm (GA). The SFLA technique is simple and fast but suffers from premature convergence. A simple low-energy clustering technique based on quantum genetic algorithm (QGA) while simultaneously evaluating the communication energy consumption to obtain a lower communication energy consumption has also been attempted in [21]. The represented method has presented good results in terms of low energy and communication energy consumption. The QGA is flexible but suffers from the problem of high computational complexity. A low-energy clustering model is suggested in [22] and particle swarm optimization (PSO) is used to resolve the problem. This algorithm has been shown to perform well with a small number of sensors. However, the PSO approach cannot quickly solve the problem while incurring high computational costs.Based on the concepts and principles of parallel and chaos theory, the new CCPEA is presented in this article. Compared to the traditional evolutionary algorithms (EAs), this technology achieves a better balance and better results. Generally speaking, the hallmark of the CCPEA is a simple heuristic with a good equilibrium mechanism that can flexibly expand and adapt to global and local intelligence capabilities, which has attracted widespread research attention.In this study, the minimal power clustering issue for low-power WSNs is formulated as a combinatorial optimization problem, taking into account the constraints of energy and monitored area, which is an NP-hard problem. However, it is impossible to perform detailed searches in real-time in HDWSNs [23, 24]. Therefore, numerous heuristic algorithms have been created to reduce WSNs communication power consumption and improve WSNs performance [25–31].In this article, the clustering problem is transformed into an evolution problem and then solved by the CCPEA. First, we design a new formula for the goal function to match low-power consumption. Furthermore, two new operators, the clone and chaotic operators, are constructed to lower the communication energy consumption in HDWSNs. CCPEA uses powerful parallel operators to mix the advantages of clone selection and chaos generation to solve low-energy clustering problems. We also construct a clone selection to avoid local optima.Simulations are carried out to denote a comparison of CCPEA through the other two algorithms. From the simulation results, we can get the following conclusions:(1)
Firstly, the CCPEA can resolve the low-energy clustering problem with lower communication energy consumption than PSO and simulated annealing (SA) techniques. For example, when the number of sensor nodes is 100 and the cluster head ratio is 10%, the energy consumption reduction of CCPEA is 8.46% and 18.55% lower than PSO and SA, respectively.(2)
Secondly, the CCPEA combines the advantages of the clone operator and the chaotic operator, avoiding the premature convergence problem of PSO and SA. The simulation results show that when the cluster head ratio is 10% and the number of sensor nodes is 300 and 400, the convergence speed of CCPEA is significantly higher than that of PSO and SA.(3)
Finally, the overall energy loss of the sensor network depends on the sum of the energy loss of the sensor nodes transmitting data and receiving data. As the number of nodes increases, CCPEA can still achieve lower communication energy consumption than PSO and SA technologies while taking the same computational complexity.


## 2. Related Work

HDWSNs are widely used due to their easy deployment and strong environmental adaptability. Literature [32] installed a large number of wireless sensor nodes on the car and constructed a unique and novel vehicle self-organizing network. The in-vehicle network can analyze the data perceived by the nodes to obtain the driving behavior of the driver and finally give the corresponding insurance level. In [33], the author presents a large-scale high-density wireless sensor network for monitoring the temperature in central Tokyo. The system has a total of 200 sensor nodes arranged in eight monitoring areas, with a node density of approximately 1,800 per square kilometer.In many industrial applications, it is an important problem to optimize energy by using intelligent algorithm [34–37]. In HDWSNs, an effective low-energy clustering scheme can achieve lower energy consumption, reduce energy costs, and extend network life. For heterogeneous WSNs, literature [38] suggested a brand new distributed low-energy node protection time-driven clustering algorithm (LEPTC) to ensure more uniform energy consumption of nodes, thereby reducing energy consumption and extending network life. In this algorithm, initialization is performed according to the energy level.In [39], the author proposed an energy-efficient distributed clustering algorithm in the coverage area. This algorithm considers the redundancy of coverage and the remaining energy of nodes, making the distribution of cluster heads more reasonable. Facts have proved that this algorithm can achieve lower network energy consumption and higher coverage quality.In [40], the authors proposed a cluster-based routing algorithm in wireless sensor networks based on the genetic algorithm. This algorithm quickly reorganizes clusters in a network with uneven distribution of nodes and selects new cluster heads to achieve a balance of energy consumption, thereby achieving a longer network life.In [41], a method based on the energy-efficient genetic algorithm is proposed, which improves the overall performance of WSNs based on the Virtual Grid-Based Dynamic Routes Adjustment (VGDRA). Compared with other methods, this dynamic method better balances the load and optimizes it, thereby creating more opportunities and achieving better results with fewer loops.In literature [42], the author proposed a multiobjective Bat algorithm to find the best cluster formation in WSNs and proposed a routing model. The optimal node is used as the cluster head and the communication distance is modeled by Bat loudness parameters to optimize the energy consumption in WSNs.According to the characteristics of WSNs, the study in [43] suggested a routing algorithm for WSNs based on ant colony optimization. The outcomes demonstrate that the enhanced scheme has good performance in terms of power consumption and global optimization capabilities.Aiming at the defect of premature convergence of the traditional K-means clustering algorithm, the article [44] proposed an improved GA based on the hybrid K-means clustering algorithm, which can prevent the algorithm from falling into the local optimum by introducing an adaptive function.The study in [45] proposed a hybrid method called KGA, which aims to combine GA and K-means algorithm to search for the optimal number of clusters, thereby optimizing the communication energy in WSNs.In [46], low-energy clustering problem approach for low-energy clustering problems in WSNs to minimize the communication energy consumption is researched based on PSO. In their article, they minimize the communication energy consumption without considering energy restriction. However, it also suffers from an excessive computational time requirement.In [47], clustering design techniques based on SA have been represented in order to maximize the network lifespan in a long network lifespan. Their design is a similar concept to the GA. The SA approach is simple and fast but suffers from premature convergence.In [48], the clustering design strategy for clustering design in WSNs to maximize the network lifespan is explored based on the quantum evolutionary algorithm (QGA). The QGA method employs an individual to suggest the solution and obtains the longer network lifespan iteratively. QGA performs well in the beginning, but it suffers from premature convergence and a low convergence rate only after a few iterations.


## 3. System Model

In this section, a low-energy clustering model is proposed for the constraints of sensor node power and communication energy consumption in HDWSNs. The typical network structure diagram of HDWSNs studied in this article is shown in Figure1:Figure 1
Cluster structure of density sensor network.As shown in Figure1, in the HDWSNs, the clustering structure means that a cluster head node will be chosen from a similar area within the monitoring range, and a node cluster will be formed around the cluster head node. Each sensing node perceives the target and then uploads the sensing result to the primary cluster node in the node cluster after completing the sensing task. The cluster head node collects the sensing results uploaded by the sensing nodes in the cluster and then directly uploads the results to the gateway node in multiple hops. The monitoring task performed by the sensing node is that the gateway node publishes the task to the cluster head node; after that, the cluster head node distributes the task to the sensing nodes in the cluster.This article mainly studies how to minimize the power consumption of HDWSNs by optimizing the energy consumption of communication between nodes through reasonable clustering. As the communication distance between sensor nodes is limited, the communication power consumption of the sensor network when sending and receiving data cause serious waste of energy [17, 49, 50]. Therefore, it is extremely important to develop a reasonable and efficient low-energy clustering scheme. According to the low-energy clustering model in literature [51], the formula for the energy consumed by the sending node to transmit b bits of data to the receiving node can be obtained by the following formula:(1)costsendb,l=Eelec⋅b+εamp⋅b⋅ln.In formula (1), costsend represents the energy consumed when the node sends b bits data to the receiving node and the distance between the two nodes is l. Among them, Eelec represents the electronic energy parameter, εamp represents the power amplification parameter, and the value of n, usually between 2 and 4, is generally determined according to the quality of the communication environment. The better the communication environment, the smaller the value of n. At the same time, the communication energy required by the receiving node to receive b bits data is shown as follows:(2)costreceivedb=Eelec⋅b.In formula (2), costreceived indicates the communication energy required by the receiving node to receive b bits energy. In the model of this article, suppose b is 1 M bits, εamp=100pJ/bit/m2, Eelec=50nJ/bit, n=3.


## 4. CCPEA-Based Low-Energy Clustering Problem in HDWSNs

The EA is one of the most popular metaheuristic algorithms, which attempts to mimic the procedure of natural selection [19]. It is also an exploit method that mimics the procedure of natural selection in nature, which is an optimization algorithm to search an input region while minimizing a result function under given restraints [23, 52, 53]. The primary thought is to get inspired analogy from the natural mechanisms of gene recombination and mutation. There exist multiple alternatives to implementation for heuristic operators. EA is researched as a suitable metaheuristic, usually used to settle complicated optimization issues [54].Inspired by traditional EAs, this section describes the design of the CCPEA for the low-power clustering problem. In this article, a novel clone method has been studied to minimize the communication energy consumption in HDWSNs. Furthermore, two novel procedures, the chaotic and parallel procedures, are formed. On the one hand, we reveal that a chaotic procedure depending on the binary region can be naturally integrated with EA so that feasible solutions are completely searched. On the other hand, with the parallel operator, it is more effective for the operator of diverse lengths of chromosomes compared to the traditional EA. In CCPEA, clone, chaotic and parallel procedures are helpful to enhance the population diversity of CCPEA and avoid premature convergence.Therefore, the depicted CCPEA procedures are repeated at a time granularity stationary by HDWSNs requirements. The CCPEA employs various simple procedures in order to simulate evolution. So, the suggested CCPEA-based clustering problem can be summarized as follows:(i)
Initialize the chromosomes of CCPEA(ii)
Select superior chromosomes as parents to feed into the genetic procedure(iii)
Generate a novel population by crossover and mutation(iv)
Then, their result function value with the result function is evaluated(v)
Update the population by switching inferior chromosomesThe loop is repeated until the stopping condition is satisfied. The comprehensive description of the CCPEA utilized to explore the almost best clustering problem is defined in what follows.


### 4.1. Representation of Chromosomes

The first step to design CCPEA is to find a suitable chromosome representation scheme. The efficiency of a CCPEA depends on the encoding technique employed. In CCPEA, a solution is presented by a chromosome. For a low-energy clustering problem, each chromosome in the group might imply a collection of randomly selected clustering problems. For the scope of this article, the variable should be suggested by a binary code representing the clustering problem for the low-energy clustering problem. The Boolean coding representation is correct and powerful because it is closest to the clustering problem, and the string length is the number of sensors. A chromosome is composed of a string of binary symbols. By doing this, each chromosome is converted from the Boolean string into real numbers to gain the communication energy consumption associated with each member of the group. Each chromosome is made up of bits. CCPEA is easy to use since there are only two options to utilize to a bit: 0 or 1.If the code of a chromosome is “0100110101,” the number of genes in the chromosome is 10, and each gene represents a sensor node; that is, the quality of sensor nodes in the sensor network is 10. In other words, the chromosome symbol length is the number of sensors in the HDWSNs. When the gene at a location is 1, it means that the sensor at that location is a cluster head node, and 0 is a sensory node. For example, if the second digit of the chromosome is 1, the second sensor node is the cluster head node.


### 4.2. Initial Population

The CCPEA requires a group of potential solutions to be initialized at the beginning of the CCPEA procedure. The CCPEA solves the optimization problem by manipulating a group of chromosomes. CCPEA solves optimizing issues according to a group of a stationary number, referred to as the group size, of solutions. Generally, in the case of a very small population, only a small part of the exploited area is explored, thereby increasing the risk of premature convergence to local extremes. It keeps a group of chromosomes that evolves over successive generations. In CCPEA, a group is randomly created. In finding bits that satisfy constraints, CCPEA applies a random number generator. A random initial group is generated as a group of solutions of clustering problems. In this article, the size of the initial population is set toS, and there are N genes in the initial population; that is, there are N sensor nodes in the HDWSNs, and the amount of cluster heads is fixed to M. The population coding can be described as(3)F=q1,1q1,2…q1,N−1q1,Nq2,1q2,2…q2,N−1q2,N⋮⋮qs,n⋮⋮qS−1,1qS−1,2…qS−1,N−1qS−1,NqS,1qS,2…qS,N−1qS,N=Q1Q2⋮QS−1QSqs,n∈0,1,(4)∑n=1Nqs,n=Ms∈1,2,…,S.In formula (3), QS is expressed as the sth individual, and whether the nth sensor in the sth individual is a cluster head node is expressed by the value of qs,n. If qs,n=1, it means that the sensor node is a cluster head node; otherwise, it is a sensing node. Formula (4) is the constraint on the number of cluster head nodes in each individual, and the fixed value is M. For example, when the number of sensors in a certain individual is 100, then N=100. If the cluster head ratio is selected as 10%, then M is 10.


### 4.3. Fitness Evaluation

In the given context, we calculate the result function value of each chromosome according to the communication energy consumption. The purpose of this article is to minimize communication energy consumption. In this way, the value of fitness is lower, the quality of the chromosomes is better. CCPEA solves stochastic optimization problems, and each chromosome is evaluated by a fitness function. The fitness function blends the satisfaction of restrictions by handling the clustering design problem. For an individual in the CCPEA, its fitness value is calculated based on the fitness function. In this article, the fitness value of the chromosome is calculated by (5). In CCPEA, we calculate the communication energy consumption of each chromosome’s fitness value. Therefore, in terms of fitness value, our aim is to find a solution using(5)FitQ=∑n=1Ncostsend+costreceived.


### 4.4. Selection

The CCPEA adopts a roulette wheel selection strategy to select the parents. The selection procedure adopts the best preservation approach and roulette technique. In the roulette wheel, the individual with better result function values has more possibility of being selected. Thus, it is possible to select the same chromosome at various times. According to this selection probability, a pair of parent solutions is chosen from the current population. The algorithm then replaces low-quality solutions through recently developed high-quality solutions to obtain a much better current group. The survived chromosomes are then utilized to produce the next iteration. In this way, chromosomes that are more common in the survived population are more likely to be inherited. The replaced individual is chosen randomly, but whose result function value must be above the average level in the community.In order to ensure that individuals with lower communication energy consumption get a greater probability of being chosen, the probability of individualQs, that is, the possibility of an individual being chosen, is inversely proportional to the degree of fitness, as shown in(6)FSELECTQs=1/FitQs∑i=1S1/FitQs.


### 4.5. Crossover

By the chance of selection, the chosen chromosomes are directly transferred to the crossover. Crossover is to find a better solution to deal with the current solution. The crossover is an operation carried out to produce offspring by taking characteristics from the parents. Crossover is a heuristic procedure for recombining two parent solutions into two new solutions.According to the literature [55], the concept of GA crossover, assuming that the two individuals Q1 and Q2 are cross-operated, Q′ is first obtained through the logical and operation. Q′ is to compare the Boolean algebras of the corresponding positions in the two individuals. If the Boolean algebra of the corresponding position is the same, it remains unchanged, and if it is different, it becomes 0, as shown in Figure 2.Figure 2
Crossover.Secondly, perform the logical AND operation on the two individuals to getQ″. Q″ changes the positions of the Boolean algebra of the corresponding positions in Q1 and Q2 to 0, and the difference to 1 as shown in Figure 3.Figure 3
Crossover.Finally, evenly distribute the ‘1’ in the position ofQ″ to the corresponding position in Q′ to obtain two new individuals generated by crossover. As shown in Figure 4, the number of ‘1’ in Q″ is evenly allocated to Q′, and the position is random. Therefore, the two newly obtained individuals can be Qnew1=1000101001 and Qnew2=1000100110.Figure 4
Crossover.
(a)(b)


### 4.6. Mutation

Each chromosome had a given possibility of being mutated; for the CEAEA, this probability is defined to 0.05. The main goal of the mutation program is to maintain diversity within the group. Considering that the amount of cluster heads in an individual is constant, the mutation operation randomly changes a position of “1” in the individual to “0” with a mutation probability and randomly selects one of the positions where the value is “0” and changes it to “1,” as shown in Figure5.Figure 5
Mutation.


### 4.7. Clone

The cloning algorithm is an optimized algorithm inspired by the cloning principle of the biological immune system. The cloning algorithm combines the adaptive ability of the biological immune system with the prior knowledge of the problem, so the algorithm has good robustness in the information search process and guides the search process to converge in the direction of the global optimal solution. The CCPEA algorithm increases the population size through the cloning operator, effectively increases the diversity of the population, and helps to find the global optimal solution.


### 4.8. Chaotic

In CCPEA, when the EA initializes the population, it has a greater impact on the iterative optimization of subsequent generations. Therefore, the use of chaotic sequence logistic mapping to improve the evolutionary population can enrich the diversity of the initial population and accelerate the optimization speed. Because chaotic mapping causes chaos in the feasible region of the independent variable, it is predictable in a short initial time, but it is random in a long time. Therefore, chaotic mapping has a positive effect on the convergence speed of EAs.


### 4.9. Parallel

In CCPEA, a shared area is opened by the main thread to save the optimal individual of each thread. The child threads run their GAs, synchronize their optimal individuals to the shared area every hundred generations, and introduce optimal individuals from other threads.


### 4.10. Computational Complexity Analysis

In this part, we analyze the computational complexity of the proposed CCPEA. In the low-energy clustering problem, the distance between sensor nodes directly affects the energy cost between sensors, so it is necessary to calculate the distance and energy consumption between each sensor node. In the system model of this article, there areN sensor nodes, so the computational complexity of energy consumption calculation is ON2. For CCPEA, there are S individuals in a population, and each contains N sensor nodes. If the number of iterations is H, the computational complexity is ON2+OHSN.


## 4.1. Representation of Chromosomes

The first step to design CCPEA is to find a suitable chromosome representation scheme. The efficiency of a CCPEA depends on the encoding technique employed. In CCPEA, a solution is presented by a chromosome. For a low-energy clustering problem, each chromosome in the group might imply a collection of randomly selected clustering problems. For the scope of this article, the variable should be suggested by a binary code representing the clustering problem for the low-energy clustering problem. The Boolean coding representation is correct and powerful because it is closest to the clustering problem, and the string length is the number of sensors. A chromosome is composed of a string of binary symbols. By doing this, each chromosome is converted from the Boolean string into real numbers to gain the communication energy consumption associated with each member of the group. Each chromosome is made up of bits. CCPEA is easy to use since there are only two options to utilize to a bit: 0 or 1.If the code of a chromosome is “0100110101,” the number of genes in the chromosome is 10, and each gene represents a sensor node; that is, the quality of sensor nodes in the sensor network is 10. In other words, the chromosome symbol length is the number of sensors in the HDWSNs. When the gene at a location is 1, it means that the sensor at that location is a cluster head node, and 0 is a sensory node. For example, if the second digit of the chromosome is 1, the second sensor node is the cluster head node.


## 4.2. Initial Population

The CCPEA requires a group of potential solutions to be initialized at the beginning of the CCPEA procedure. The CCPEA solves the optimization problem by manipulating a group of chromosomes. CCPEA solves optimizing issues according to a group of a stationary number, referred to as the group size, of solutions. Generally, in the case of a very small population, only a small part of the exploited area is explored, thereby increasing the risk of premature convergence to local extremes. It keeps a group of chromosomes that evolves over successive generations. In CCPEA, a group is randomly created. In finding bits that satisfy constraints, CCPEA applies a random number generator. A random initial group is generated as a group of solutions of clustering problems. In this article, the size of the initial population is set toS, and there are N genes in the initial population; that is, there are N sensor nodes in the HDWSNs, and the amount of cluster heads is fixed to M. The population coding can be described as(3)F=q1,1q1,2…q1,N−1q1,Nq2,1q2,2…q2,N−1q2,N⋮⋮qs,n⋮⋮qS−1,1qS−1,2…qS−1,N−1qS−1,NqS,1qS,2…qS,N−1qS,N=Q1Q2⋮QS−1QSqs,n∈0,1,(4)∑n=1Nqs,n=Ms∈1,2,…,S.In formula (3), QS is expressed as the sth individual, and whether the nth sensor in the sth individual is a cluster head node is expressed by the value of qs,n. If qs,n=1, it means that the sensor node is a cluster head node; otherwise, it is a sensing node. Formula (4) is the constraint on the number of cluster head nodes in each individual, and the fixed value is M. For example, when the number of sensors in a certain individual is 100, then N=100. If the cluster head ratio is selected as 10%, then M is 10.


## 4.3. Fitness Evaluation

In the given context, we calculate the result function value of each chromosome according to the communication energy consumption. The purpose of this article is to minimize communication energy consumption. In this way, the value of fitness is lower, the quality of the chromosomes is better. CCPEA solves stochastic optimization problems, and each chromosome is evaluated by a fitness function. The fitness function blends the satisfaction of restrictions by handling the clustering design problem. For an individual in the CCPEA, its fitness value is calculated based on the fitness function. In this article, the fitness value of the chromosome is calculated by (5). In CCPEA, we calculate the communication energy consumption of each chromosome’s fitness value. Therefore, in terms of fitness value, our aim is to find a solution using(5)FitQ=∑n=1Ncostsend+costreceived.


## 4.4. Selection

The CCPEA adopts a roulette wheel selection strategy to select the parents. The selection procedure adopts the best preservation approach and roulette technique. In the roulette wheel, the individual with better result function values has more possibility of being selected. Thus, it is possible to select the same chromosome at various times. According to this selection probability, a pair of parent solutions is chosen from the current population. The algorithm then replaces low-quality solutions through recently developed high-quality solutions to obtain a much better current group. The survived chromosomes are then utilized to produce the next iteration. In this way, chromosomes that are more common in the survived population are more likely to be inherited. The replaced individual is chosen randomly, but whose result function value must be above the average level in the community.In order to ensure that individuals with lower communication energy consumption get a greater probability of being chosen, the probability of individualQs, that is, the possibility of an individual being chosen, is inversely proportional to the degree of fitness, as shown in(6)FSELECTQs=1/FitQs∑i=1S1/FitQs.


## 4.5. Crossover

By the chance of selection, the chosen chromosomes are directly transferred to the crossover. Crossover is to find a better solution to deal with the current solution. The crossover is an operation carried out to produce offspring by taking characteristics from the parents. Crossover is a heuristic procedure for recombining two parent solutions into two new solutions.According to the literature [55], the concept of GA crossover, assuming that the two individuals Q1 and Q2 are cross-operated, Q′ is first obtained through the logical and operation. Q′ is to compare the Boolean algebras of the corresponding positions in the two individuals. If the Boolean algebra of the corresponding position is the same, it remains unchanged, and if it is different, it becomes 0, as shown in Figure 2.Figure 2
Crossover.Secondly, perform the logical AND operation on the two individuals to getQ″. Q″ changes the positions of the Boolean algebra of the corresponding positions in Q1 and Q2 to 0, and the difference to 1 as shown in Figure 3.Figure 3
Crossover.Finally, evenly distribute the ‘1’ in the position ofQ″ to the corresponding position in Q′ to obtain two new individuals generated by crossover. As shown in Figure 4, the number of ‘1’ in Q″ is evenly allocated to Q′, and the position is random. Therefore, the two newly obtained individuals can be Qnew1=1000101001 and Qnew2=1000100110.Figure 4
Crossover.
(a)(b)


## 4.6. Mutation

Each chromosome had a given possibility of being mutated; for the CEAEA, this probability is defined to 0.05. The main goal of the mutation program is to maintain diversity within the group. Considering that the amount of cluster heads in an individual is constant, the mutation operation randomly changes a position of “1” in the individual to “0” with a mutation probability and randomly selects one of the positions where the value is “0” and changes it to “1,” as shown in Figure5.Figure 5
Mutation.


## 4.7. Clone

The cloning algorithm is an optimized algorithm inspired by the cloning principle of the biological immune system. The cloning algorithm combines the adaptive ability of the biological immune system with the prior knowledge of the problem, so the algorithm has good robustness in the information search process and guides the search process to converge in the direction of the global optimal solution. The CCPEA algorithm increases the population size through the cloning operator, effectively increases the diversity of the population, and helps to find the global optimal solution.


## 4.8. Chaotic

In CCPEA, when the EA initializes the population, it has a greater impact on the iterative optimization of subsequent generations. Therefore, the use of chaotic sequence logistic mapping to improve the evolutionary population can enrich the diversity of the initial population and accelerate the optimization speed. Because chaotic mapping causes chaos in the feasible region of the independent variable, it is predictable in a short initial time, but it is random in a long time. Therefore, chaotic mapping has a positive effect on the convergence speed of EAs.


## 4.9. Parallel

In CCPEA, a shared area is opened by the main thread to save the optimal individual of each thread. The child threads run their GAs, synchronize their optimal individuals to the shared area every hundred generations, and introduce optimal individuals from other threads.


## 4.10. Computational Complexity Analysis

In this part, we analyze the computational complexity of the proposed CCPEA. In the low-energy clustering problem, the distance between sensor nodes directly affects the energy cost between sensors, so it is necessary to calculate the distance and energy consumption between each sensor node. In the system model of this article, there areN sensor nodes, so the computational complexity of energy consumption calculation is ON2. For CCPEA, there are S individuals in a population, and each contains N sensor nodes. If the number of iterations is H, the computational complexity is ON2+OHSN.


## 5. Simulation and Discussion

We propose the simulation results for low-power clustering in HDWSNs with CCPEA, PSO, and SA in this section. Simulations were performed to verify the low-energy clustering performance of the proposed CCPEA method. We test the performance of the schemes on a PC with Intel Core i7-8550 U, 2.00 GHz, 8 GB RAM, Win10 operating system, and MATLAB software to denote its applicability to the clustering design problem. To evaluate the performance of the CCPEA and other heuristics, a single result function, as described in Section4, is utilized in the experimental results. Then, we develop sensor nodes, and the coordinate of each sensor node is randomly specified within the square region. Four low-power clustering problem cases with diverse numbers of sensors are tested. The performance of the CCPEA, PSO, and SA is reported.For CCPEA, the selection of parameters is based on the range of empirical values based on existing research, and the parameters are adjusted according to the range of empirical values. Due to the sensitivity of the parameters, slight changes in parameter data will affect the performance of the algorithm. Therefore, many experiments must be carried out and the parameters must be adjusted several times until the algorithm achieves better performance. At present, a simulation model close to reality is used to verify the rationality of the experimental results, which will be implemented in the actual system in the near future.In our simulation, all comparisons between CCPEA, PSO, and SA were reported using 100 generations and 40 individuals. In CCPEA, using recommendations, we select 0.05 as mutation probability and 0.8 as crossover possibility. The parameter values in the PSO are based on a parametric study, the learning factor C1 = C2 = 2 is selected, and the maximum velocity of the particle is fixed to 6. In SA, the initial temperature and annealing temperature coefficients are 200 and 0.85, respectively. The specific description of the parameters is shown in Table1.The basic concept taken in this work is as follows: the nodes are connected by wireless communication, and the energy consumption is composed of the sum of the energy consumed by the receiving node and the sending node when sending and receiving energy. In the experiment, in order to consider the influence of the number of different sensor nodes and different cluster head ratios on the experimental results, a large number of simulation experiments were done for the different numbers of sensor nodes and different cluster head ratios, and the following similar situations were obtained. This article mainly focuses on the comparison of the communication energy consumption of the three algorithm schemes when the ratio of cluster heads is 10% and the number of sensor nodes is 100, 200, 300, and 400, respectively. And when the ratio of cluster heads is 5%, 10%, 15%, and 20%, the energy consumption of the three algorithms is compared when the sensor nodes are 200, 400, 600, 800, 1000, and 1200, respectively, as shown in Table1.Table 1
Description of parameters.
ParametersDescriptionNumber of individualsAn individual represents a solution to a low-energy clustering problemNumber of iterationsAlgorithm optimization timesMutation rateProbability of binary code mutationCrossover rateProbability of binary change exchange between two individualsLearning factors C1 and C2Acceleration constant, normally, C1 = C2 = 2Maximum velocity of the particleMaximum speed of particle movementThe initial temperatureA sufficiently large temperature defined before the first iterationThe annealing temperature coefficientCooling rate coefficient, when the cooling rate coefficient is smaller, the cooling rate is fasterFigures6(a)–6(d) show the comparison of communication energy consumption optimized by CCPEA, PSO, and SA when the number of sensor nodes is 100, 200, 300, and 400 when the proportion of cluster heads is 10%. For each technique, we just choose the optimum solution in each iteration from the present population. It must be noted that the experiment of CCPEA is superior to the PSO and SA methods, which can be obtained in Figure 6. In Figure 6(a), compared to other techniques, after 100 generations, the communication energy consumption of CCPEA is reduced to 68.25 J. However, PSO and SA attain suboptimal results, and the communication power consumption acquired by the PSO and SA is 74.56 J and 83.79 J, respectively. CCPEA reduces communication energy consumption by 8.46% and 18.55% than PSO and SA.Figure 6
Energy consumption of CCPEA, PSO, and SA ((a) 100 sensor nodes; (b) 200 sensor nodes; (c) 300 sensor nodes; (d) 400 sensor nodes).
(a)(b)(c)(d)In Figures6(b)–6(d), 200, 300, and 400 sensor nodes are used to obtain similar results. In Figure 66(b), the communication energy consumption of CCPEA, PSO, and SA reached 112.52 J, 125.78 J, and 147.72 J, respectively. And compared with PSO, SA, CCPEA achieved a faster convergence rate in the first 50 generations and achieved lower energy consumption in the later 50 generations. In Figure 6(c), the communication energy consumption using the CCPEA method dropped to 162.27 J, while PSO and SA dropped to 184.68 J and 219.44 J, respectively. In Figure 6(d), the communication energy consumption of CCPEA, PSO, and SA is 183.36 J, 207.82 J, and 257.69 J, respectively. The communication energy consumption of CCPEA is reduced by 11.77% and 28.84% lower than that of PSO and SA. And before the 40th generation, the convergence speed of CCPEA was significantly faster than the other two algorithms.As shown in Figure6, the value of communication energy consumption initially decreases with the growth of generations. It can be seen that CCPEA finds high-quality experiments much faster than PSO and SA. On the other hand, the PSO and SA denotes a quite slower convergence, hence proving the superior reliability of CCPEA. CCPEA combines the advantages of the cloning operator, accelerates the convergence speed, has better reliability, and solves the shortcomings of the slow convergence speed of traditional intelligent algorithms. In CCPEA, the cloning operator is used to replicate the 5 best individuals in the population and inherit them to the population in the next generation to ensure the population in the next generation is better than the previous population. Therefore, achieving better convergence can be achieved. It is evident that CCPEA has converged to better solutions and it is prevented from premature convergence. In all 100 generations, the communication energy consumption of CCPEA is lower than that of PSO and SA, and the chaotic operator is used to generate a random initial population, expand the search range of the population, which helps to find a better solution, achieve lower energy consumption, and effectively avoid the algorithm from stagnating early. It can be seen that the solutions found by CCPEA propose stable performance, which denotes the robustness of the algorithm. The simulation results present that the suggested CCPEA method offers lower communication power consumption over the current PSO and SA methods.Figures7(a) and 7(b) show a comparison of the communication energy consumption changes of CCPEA, PSO, and SA with different amount of sensor nodes when the proportion of cluster heads is 5%, 10%, 15%, and 20%, respectively. Figure 7(a) illustrates the communication power consumption corresponding to the number of different sensor nodes while the proportion of cluster head nodes is 5%. The specific values can be seen in Table 2.Figure 7
Energy consumption of CCPEA, PSO, and SA ((a) 5% cluster head ratio; (b) 10% cluster head ratio; (c) 15% cluster head ratio; (d) 20% cluster head ratio).
(a)(b)(c)(d)Table 2
Energy consumption when the cluster head ratio is 5% (J).
200 sensors400 sensors600 sensors800 sensors1000 sensors1200 sensorsCCPEA148.70189.48224.89276.18318.60361.54PSO152.66211.72263.32295.29331.01389.77SA193.34257.26306.31387.46423.67518.82As shown in Table2, when the number of sensors is 1200, the optimal communication energy consumption of CCPEA is 361.54 J, while the communication energy consumption obtained by PSO and SA is 389.77 J and 518.82 J, revealing that the CCPEA is more robust than PSO and SA for minimizing the communication energy consumption. The same result can be obtained in Figures 7(b)–7(d).Figure7(b) illustrates the communication power consumption corresponding to the number of different sensor nodes while the proportion of cluster head nodes is 10%. It can be seen from Figure 7(b) that when the number of sensor nodes is 1200, the energy consumption cost of CCPEA is 428.42 J, and the energy consumption costs of PSO and SA are 534.56 J and 872.69 J, respectively. The energy consumption cost of CCPEA is much lower than that of PSO and SA.Figure7(c) illustrates the communication power consumption corresponding to the number of different sensor nodes while the proportion of cluster head nodes is 15%. When the number of sensor nodes is 1200, the energy consumption cost of CCPEA is 509.53 J, and the energy consumption costs of PSO and SA are 788.24 J and 1277.36 J, respectively. The energy cost of CCPEA is 35.36% and 60.11% lower than that of PSO and SA, respectively.Figure7(d) illustrates the communication power consumption corresponding to the number of different sensor nodes while the proportion of cluster head nodes is 20%. When the number of sensor nodes is 1200, the energy consumption cost of CCPEA is 663.72 J, and the energy consumption costs of PSO and SA are 1058.47 J and 1726.68 J, respectively. The energy cost of CCPEA is 37.29% and 61.56% lower than that of PSO and SA, respectively.When the number of sensor nodes is fixed at 1000, in Figure8(a)-8(b), the communication energy consumption of the three algorithms at different cluster head ratios is compared. In Figure 8(a), the communication energy of CCPEA is 318.60 J with a cluster head ratio is 5%, while the low-energy clustering solutions in PSO and SA are 331.01 J and 423.67 J, respectively. In Figure 8(b), when the cluster head ratio is 10%, the communication energy of CCPEA is 381.67 J and PSO and SA are 482.49 J and 715.77 J, respectively. Figure 8(c) represents the communication energy cost of the three algorithms when the cluster head ratio is 15%. The communication energy of CCPEA is 421.46 J, while that of PSO and SA is 623.13 J and 1108.34 J, respectively. In Figure 8(d), the communication energy of CCPEA is 318.60 J, and those of the PSO and SA are 331.01 J and 423.67 J, respectively. In Figures 8(a)–8(d), we can also clearly conclude that CCPEA is more robust and stable than ACO and SA. Simulation denotes that the suggested CCPEA strategy outperforms the conventional ACO and SA technologies with smaller communication energy consumption.Figure 8
Energy consumption when the number of sensor nodes is 1000 ((a) 5% cluster head ratio; (b) 10% cluster head ratio; (c) 15% cluster head ratio; (d) 20% cluster head ratio).
(a)(b)(c)(d)


## 6. Conclusion

This work presents a novel clone chaotic parallel evolutionary algorithm (CCPEA), which uses the merging clone operator and chaotic operator. In this article, we first describe a new formulation of the objective function to minimize the communication energy consumption to suit the low energy. By introducing CCPEA into the low-energy clustering, a result function for evaluating the communication energy consumption is designed to minimize the communication energy consumption for HDWSNs. Comprehensive analysis and experiments are carried out to assess the performance improvement of CCPEA compared to methods according to PSO and SA. The experimental results show that, in the case of different cluster head ratios and different sensor nodes, the communication energy consumption of CCPEA is lower than that of PSO and SA. The cloning operator, chaos operator, and parallel operator in CCPEA expand the scope of optimization and reduce the energy consumption of communication while avoiding the premature convergence and evolutionary stagnation of the algorithm.



---

*Source: 6630322-2021-04-29.xml*