# Elite Adaptive Simulated Annealing Algorithm for Maximizing the Lifespan in LSWSNs

Authors: Jie Zhou; Wenxian Jia; Menghan Liu; Mengying Xu
Journal: Journal of Sensors
 (2021)

---

## Abstract

Large-scale wireless sensor networks (LSWSNs) are currently one of the most influential technologies and have been widely used in industry, medical, and environmental monitoring fields. The LSWSNs are composed of many tiny sensor nodes. These nodes are arbitrarily distributed in a certain area for data collection, and they have limited energy consumption, storage capabilities, and communication capabilities. Due to limited sensor resources, traditional network protocols cannot be directly applied to LSWSNs. Therefore, the issue of maximizing the LSWSNs’ lifetime by working with duty cycle design algorithm has been extensively studied in this paper. Encouraged by annealing algorithm, this work provides a new elite adaptive simulated annealing (EASA) algorithm to prolong LSWSNs’ lifetime. We then present a sensor duty cycle models, which can make sure the full coverage of the monitoring targets and prolong the network lifetime as much as possible. Simulation results indicate that the network lifetime of EASA algorithm is 21.95% longer than that of genetic algorithm (GA) and 28.33% longer than that of particle swarm algorithm (PSO).


---

## Body

## 1. Introduction

Large-scale wireless sensor networks (LSWSNs) have broad application prospects in various fields, such as agriculture, industry, military, and environmental monitoring because of their real-time data collection and flexibility of deployment methods. The use of LSWSNs to detect harmful gas leaks is one of the research hotspots. Classical harmful gas detection mainly includes detection methods such as wired fixed devices and portable instruments. However, these ways have disadvantages such as poor flexibility, low real-time performance, and inaccurate location of leaks. LSWSNs rely on their low cost, high real-time performance, and good collaboration. It provides a new system for remote detection of harmful gases.At present, traditional LSWSNs usually deploy dense static sensor nodes in industrial plants to obtain more accurate results. Nevertheless, in actual situations, since LSWSN is composed of a certain battery power and related sensor nodes within the sensor range, the sensing resources are limited. In addition, sensing, monitoring, and obtaining information in the target monitoring area are the basic and ultimate goals of LSWSN deployment nodes. Sensing nodes are generally randomly deployed in the monitoring area, which is likely to cause uneven distribution of nodes and lead to problems such as coverage blind areas [1]. This will affect the coverage quality of LSWSN. Moreover, the quality of coverage will directly affect the quality of service of the network, so coverage optimization is a basic issue that needs to be studied and analyzed in the deployment of LSWSN nodes [2, 3]. Therefore, coverage optimization is a fundamental issue that needs to be studied and analyzed in the deployment of LSWSN nodes. The coverage optimization problem of LSWSN nodes is essential to use as few nodes as possible to achieve the maximum deployment of sensory coverage and communication coverage of the target monitoring area under the premise of ensuring the quality of network connectivity. In order to achieve this goal, it is necessary to design an appropriate deployment strategy, comprehensively consider the characteristics of the node itself, and allocate various resources rationally by optimizing the deployment of the LSWSN node. The traditional deployment method is to use large-scale static nodes to complete the coverage of the target area. This method will cause problems such as high node redundancy. Therefore, in the case of full coverage, how to extend the network lifetime by deploying LSWSN nodes has become a research hotspot.To cover all the predetermined targets, the research point of paper [4, 5] was from the perspective of the power limitation of LSWSNs. Paper [6] used the feature that the sensor can charge the battery, and the solar sensor was applied to extend the working life of the wireless sensors. Paper [4] also proposed a probabilistic perception model (PSM). In the paper, each sensor could switch between charging and working status and perform cooperative sensing. The timing of monitoring common targets was well arranged. Paper [5] proposed the target Q coverage rate, which used a greedy heuristic algorithm to restrict the use of sensors with poor coverage. However, the convergence effects of these three target coverage mechanisms were not satisfactory. When the number of iterations increases, the convergence speed became slowly.Paper [7] proposed a node state prediction method based on hidden Markov model. Under the premise of full coverage, the sensor could monitor all target nodes by determining the working sequence of the nodes. However, in the solution obtained by the methods, the working life of LSWSNs was short.In this paper, we propose a method EASA to solve the problem of duty cycle, while ensuring full coverage of the monitoring target, and extend the lifetime of the LSWSNs as much as possible to ensure the monitoring effect of the target.To enhance the lifespan of LSWSNs, we first set up an objective function for evaluating the working life of LSWSNs. Then, ECSA is designed to maximize the lifetime of LSWSNs. Advanced operators such as elite operator and adaptive operator are also incorporated into the EASA to extra raise the explore ability. ECSA simultaneously generates a large number of results to investigate the search region and to prevent local optima. Perform data simulation to judge the performance of EASA. Simulation results indicate the proposed algorithm can achieve a higher working life of LSWSNs over GA and PSO [8–13].


## 2. Related Work

Tiny sensing units are widely used by sensor nodes, and at the same time, the sensing capabilities of sensor nodes are limited. Since LSWSNs are restricted in sensing capabilities, the duty cycle plays a vital role in maximizing the working life of LSWSNs. Most of the research on duty cycle design is related to heuristic algorithms, such as exhaustive exploit. However, its computational complexity is too high to be used in real-time applications [14]. GA, SA, and PSO were specially exploited for this kind of problem.Paper [15] proposed GA to solve the problem of the sensor working in the monitored area with obstacles. The paper gave the correspondence between the evolution theory and the terms in GA, so that the sensor layout problem could be solved. It provided the coding scheme of the algorithm and the solution of the sensor placement problem. Finally, the GA solution could be used as a map for identifying obstacles in the monitored area. But this kind of full-coverage sensor placement method tended to converge prematurely when the number of generations increased.To achieve more coverage and the lower energy consumption, a nondominated sorting genetic algorithm (NSGA-II) was proposed in [16] to optimize the coverage. The paper used a multiobjective optimization method to extend LSWSNs’ lifespan and coverage. The paper proposed not only increased the coverage area and lifetime of the wireless sensor, but also ensured the connectivity of the wireless sensor. But it tended to converge prematurely when the cyclic algebra became larger.In [17], it proposed a combined algorithm of VF-PSO. In order to increase the coverage of the wireless network, it used virtual forces to move the sensor to a suitable location to solve the problem. In the paper, the accelerated convergence of particles was guided by virtual forces. The algorithm solved the problem of poor optimization ability of virtual force algorithm and also used PSO to maximize the coverage target area. But VF-PSO increased the complexity of the algorithm.For extending the lifespan of WSN, paper [18] adopted the coverage model of VCH-PSO. It took into account the energy consumption and coverage of the sensor and extended the lifetime of the WSN so that each target was covered by a single sensor. It was also compared with the existing technology by simulation, and the conclusion showed that this model had great advantages in terms of sensor lifetime and the time of transition between different areas. But the model only considered the wireless networks’ lifetime, and the coverage rate in the target detection area was easy to fall into the local optimum.


## 3. Duty Cycle Model of LSWSNs

Duty cycle is when there is redundancy in the node, in order to ensure that the monitoring task can be completed, a part of the nodes is put into a sleep state, and the remaining nodes are put into a working state. Completing the monitoring task in this way can reduce the overall energy consumption, thereby prolonging the network life cycle. We can also wake up sleeping nodes or set working nodes to sleep as needed. Sleeping nodes can generally turn off the sensing and communication modules in order to reduce energy consumption.


### 3.1. Plane Duty Cycle Model

Assume that there is a monitored areaψ in a two-dimensional planar area. The sensor nodes in the monitored area are randomly distributed. The area of the monitored area is S, and the number of nodes is n. The communication radius of the node is rc, and the sensing radius is rs.In the monitored areaψ, the set of sensor nodes Γ=N1x1,y1,N2x2,y2⋯Nixi,yi⋯, where Nixi,yi represents the position coordinates of node i isxi,yi,i=1,2,⋯,n. Any space ψj in the monitoring area ψ can be sensed by at least one sensor node, expressed as ψj⊆ω.The sensing range of the sensor can be represented as follows:(1)RNi=xi−x2+yi−y2≤rs,where x,y is the coordinate of the node, rs is the perception radius, and the constraint is x,y∈ψ.The set of neighbor nodes of sensor nodeNi is expressed as
(2)ΘNi=xi−xj2+yi−yj2≤rt,where xi,yi is a neighbor node of xj,yj, rt is the communication radius, and its constraints are uj∈w and ui≠uj.Each work cycle of LSWSNs is called a round. There are two stages in each round, which are divided into sleeping node stage and working stage.As shown in the coverage relationship Figure1, the sensor nodes N1, N2, N3, and N4 are represented by four squares at the center of the circle. The circle represents the sensing radius of the sensor node, and the monitored targets M1, M2, and M3 are represented by three triangles, respectively. In Figure 1, four sensing nodes N1, N2, N3, and N4 with a circular sensing radius are monitoring the targets M1, M2, and M3. The requirement of monitoring is that each target is covered by at least one sensor node at the same time. That is, in the lifetime of the sensor network, it is necessary to maintain the network’s full coverage of all three targets.Figure 1
Coverage relationship between sensors and targets.Through the above description, we can summarize the corresponding coverage relationship as follows:N1⟶M1,M2,N2⟶M2,M3,N3⟶M1,M3,N4⟶M1,M2,M3.We assume that each sensor can work for 2 rounds. If we turn on four sensors throughout the working time of the sensor, the coverage time is 2 rounds. That is, the sensor set turned on in the first round isN1,N2,N3,N4, and the sensor set turned on in the second round is N1,N2,N3,N4 too. Since the energy of the four sensors is exhausted after two rounds, the sensors can no longer work. If we divide the sensor set into different coverage sets, start only one coverage set in each round and ensure that each coverage set can complete full coverage of all three targets at the same time; then, the LSWSNs’ working life can be extended by duty cycle. For example, we divide the sensor into a set N1,N2 and a set N3,N4. Through the coverage relationship, it can be concluded that the set N1,N2 can complete the full coverage of all three target sets M1,M2,M3. Similarly, the set N3,N4 can also cover all three target sets M1,M2,M3. Therefore, if the sensor N1,N2 is turned on in the first two rounds as shown in Figure 2, and the sensor N3,N4 is turned on after two rounds as shown in Figure 3, the life of the LSWSNs can reach four rounds.Figure 2
Schematic diagram of the working of sensorsN1 and N2.Figure 3
Schematic diagram of the working of sensorsN3 and N4.However, four rounds are not the limit of the working time of the LSWSNs. If we allow the same sensor to belong to different coverage sets, we can further extend the lifetime of the LSWSNs. For example, turn on the sensor setN1,N2 in the first round, turn on the sensor set N2,N3 in the second round, and turn on the sensor set N1,N3 in the third round. Turning on the sensor set N4 in the fourth and fifth rounds can extend the lifetime of the LSWSNs to 5 rounds while maintaining full coverage of the target.


### 3.2. Mathematical Model

In the two-dimensional target coverage model, not only must the detection rate be guaranteed, but also the average distance between the sensor node and the monitored target must be minimized. This monitoring effect is the best. Assuming that there areF monitoring targets and E sensor nodes in the LSWSNs, matrix A represents a coverage relationship, the relationship between the sensor nodes in the monitoring range and the monitored target.
(3)A=a1,1a1,2⋯a1,F−1a1,Fa2,1a2,2⋯a2,F−1a2,F⋮⋮ae,f⋮⋮aE−1,1aE−1,2⋯aE−1,F−1aE−1,FaE,1aE,2⋯aE,F−1aE,Fae,f∈0,1.In matrixA, the monitoring relationship between the eth sensor node and the fth monitored target is represented by ae,f. The coverage of the eth sensor node contains the fth monitored target, and the value is expressed as ae,f=1. If it is 0, the opposite is true.Due to energy limitations, among theE sensor nodes, round D represents each sensor’s longest lifespan, and the maximum lifetime of the network is round ED, that is, the duty cycle order matrix of the sensors can be written as formula (4):
(4)B=b1,1b1,2⋯b1,E−1b1,Eb2,1b2,2⋯b2,E−1b2,E⋮⋮bi,e⋮⋮bED−1,1bED−1,2⋯bED−1,E−1bED−1,EbED,1bED,2⋯bED,E−1bED,Ebi,e∈0,1.In the formula,bi,e=1 means that the eth sensor node is in the active state in the ith round. Conversely, if the eth sensor is in the sleeping state dormant in the ith round, it will be expressed as bi,e=0.If we multiply the two matrices, it can be obtained that the monitoring relationship between theeth sensor node and the fth monitored target in each round.
(5)C=∑e=1Eb1,EaE,1∑e=1Eb1,EaE,2⋯∑e=1Eb1,EaE,F−1∑e=1Eb1,EaE,F∑e=1Eb2,EaE,1∑e=1Eb2,EaE,2⋯∑e=1Eb2,EaE,F−1∑e=1Eb1,EaE,F⋮⋮∑e=1Nbi,EaE,f⋮⋮∑e=1EbED−1,EaE,1∑e=1EbED−1,EaE,2⋯∑e=1EbED−1,EaE,F−1∑e=1EbED−1,EaE,F∑e=1EbED,EaE,1∑e=1EbED,EaE,2⋯∑e=1EbED,EaE,F−1∑e=1EbED,EaE,F.In matrixC, ∑e=1Ebi,EaE,f>0 indicates that the fth target monitored in round i is monitored by at least one sensor. And ∑e=1Ebi,EaE,f<0 means that the fth monitored target in the ith round is not monitored by any sensor. When LSWSN has completed all coverage in this round, the elements in this row are all positive numbers. The row number where the first zero element appears in matrix C is the round number than LSWSNs cannot complete the full coverage, and the round number minus one is the lifespan of LSWSN.For the convenience of representation, we stipulate that the functionrowzero represents the number of rows where the first zero element appears in the matrix C, and the duty cycle model of LSWSNs can be expressed as formulas (6) and (7):
(6)Objective:fC=rowzeroC−1,(7)Subjectto:∑i=1NDbi,n≤D,n=1⋯N.


## 3.1. Plane Duty Cycle Model

Assume that there is a monitored areaψ in a two-dimensional planar area. The sensor nodes in the monitored area are randomly distributed. The area of the monitored area is S, and the number of nodes is n. The communication radius of the node is rc, and the sensing radius is rs.In the monitored areaψ, the set of sensor nodes Γ=N1x1,y1,N2x2,y2⋯Nixi,yi⋯, where Nixi,yi represents the position coordinates of node i isxi,yi,i=1,2,⋯,n. Any space ψj in the monitoring area ψ can be sensed by at least one sensor node, expressed as ψj⊆ω.The sensing range of the sensor can be represented as follows:(1)RNi=xi−x2+yi−y2≤rs,where x,y is the coordinate of the node, rs is the perception radius, and the constraint is x,y∈ψ.The set of neighbor nodes of sensor nodeNi is expressed as
(2)ΘNi=xi−xj2+yi−yj2≤rt,where xi,yi is a neighbor node of xj,yj, rt is the communication radius, and its constraints are uj∈w and ui≠uj.Each work cycle of LSWSNs is called a round. There are two stages in each round, which are divided into sleeping node stage and working stage.As shown in the coverage relationship Figure1, the sensor nodes N1, N2, N3, and N4 are represented by four squares at the center of the circle. The circle represents the sensing radius of the sensor node, and the monitored targets M1, M2, and M3 are represented by three triangles, respectively. In Figure 1, four sensing nodes N1, N2, N3, and N4 with a circular sensing radius are monitoring the targets M1, M2, and M3. The requirement of monitoring is that each target is covered by at least one sensor node at the same time. That is, in the lifetime of the sensor network, it is necessary to maintain the network’s full coverage of all three targets.Figure 1
Coverage relationship between sensors and targets.Through the above description, we can summarize the corresponding coverage relationship as follows:N1⟶M1,M2,N2⟶M2,M3,N3⟶M1,M3,N4⟶M1,M2,M3.We assume that each sensor can work for 2 rounds. If we turn on four sensors throughout the working time of the sensor, the coverage time is 2 rounds. That is, the sensor set turned on in the first round isN1,N2,N3,N4, and the sensor set turned on in the second round is N1,N2,N3,N4 too. Since the energy of the four sensors is exhausted after two rounds, the sensors can no longer work. If we divide the sensor set into different coverage sets, start only one coverage set in each round and ensure that each coverage set can complete full coverage of all three targets at the same time; then, the LSWSNs’ working life can be extended by duty cycle. For example, we divide the sensor into a set N1,N2 and a set N3,N4. Through the coverage relationship, it can be concluded that the set N1,N2 can complete the full coverage of all three target sets M1,M2,M3. Similarly, the set N3,N4 can also cover all three target sets M1,M2,M3. Therefore, if the sensor N1,N2 is turned on in the first two rounds as shown in Figure 2, and the sensor N3,N4 is turned on after two rounds as shown in Figure 3, the life of the LSWSNs can reach four rounds.Figure 2
Schematic diagram of the working of sensorsN1 and N2.Figure 3
Schematic diagram of the working of sensorsN3 and N4.However, four rounds are not the limit of the working time of the LSWSNs. If we allow the same sensor to belong to different coverage sets, we can further extend the lifetime of the LSWSNs. For example, turn on the sensor setN1,N2 in the first round, turn on the sensor set N2,N3 in the second round, and turn on the sensor set N1,N3 in the third round. Turning on the sensor set N4 in the fourth and fifth rounds can extend the lifetime of the LSWSNs to 5 rounds while maintaining full coverage of the target.


## 3.2. Mathematical Model

In the two-dimensional target coverage model, not only must the detection rate be guaranteed, but also the average distance between the sensor node and the monitored target must be minimized. This monitoring effect is the best. Assuming that there areF monitoring targets and E sensor nodes in the LSWSNs, matrix A represents a coverage relationship, the relationship between the sensor nodes in the monitoring range and the monitored target.
(3)A=a1,1a1,2⋯a1,F−1a1,Fa2,1a2,2⋯a2,F−1a2,F⋮⋮ae,f⋮⋮aE−1,1aE−1,2⋯aE−1,F−1aE−1,FaE,1aE,2⋯aE,F−1aE,Fae,f∈0,1.In matrixA, the monitoring relationship between the eth sensor node and the fth monitored target is represented by ae,f. The coverage of the eth sensor node contains the fth monitored target, and the value is expressed as ae,f=1. If it is 0, the opposite is true.Due to energy limitations, among theE sensor nodes, round D represents each sensor’s longest lifespan, and the maximum lifetime of the network is round ED, that is, the duty cycle order matrix of the sensors can be written as formula (4):
(4)B=b1,1b1,2⋯b1,E−1b1,Eb2,1b2,2⋯b2,E−1b2,E⋮⋮bi,e⋮⋮bED−1,1bED−1,2⋯bED−1,E−1bED−1,EbED,1bED,2⋯bED,E−1bED,Ebi,e∈0,1.In the formula,bi,e=1 means that the eth sensor node is in the active state in the ith round. Conversely, if the eth sensor is in the sleeping state dormant in the ith round, it will be expressed as bi,e=0.If we multiply the two matrices, it can be obtained that the monitoring relationship between theeth sensor node and the fth monitored target in each round.
(5)C=∑e=1Eb1,EaE,1∑e=1Eb1,EaE,2⋯∑e=1Eb1,EaE,F−1∑e=1Eb1,EaE,F∑e=1Eb2,EaE,1∑e=1Eb2,EaE,2⋯∑e=1Eb2,EaE,F−1∑e=1Eb1,EaE,F⋮⋮∑e=1Nbi,EaE,f⋮⋮∑e=1EbED−1,EaE,1∑e=1EbED−1,EaE,2⋯∑e=1EbED−1,EaE,F−1∑e=1EbED−1,EaE,F∑e=1EbED,EaE,1∑e=1EbED,EaE,2⋯∑e=1EbED,EaE,F−1∑e=1EbED,EaE,F.In matrixC, ∑e=1Ebi,EaE,f>0 indicates that the fth target monitored in round i is monitored by at least one sensor. And ∑e=1Ebi,EaE,f<0 means that the fth monitored target in the ith round is not monitored by any sensor. When LSWSN has completed all coverage in this round, the elements in this row are all positive numbers. The row number where the first zero element appears in matrix C is the round number than LSWSNs cannot complete the full coverage, and the round number minus one is the lifespan of LSWSN.For the convenience of representation, we stipulate that the functionrowzero represents the number of rows where the first zero element appears in the matrix C, and the duty cycle model of LSWSNs can be expressed as formulas (6) and (7):
(6)Objective:fC=rowzeroC−1,(7)Subjectto:∑i=1NDbi,n≤D,n=1⋯N.


## 4. EASA-Based Duty Cycle for Maximizing the Lifespan in LSWSNs

To solve the LSWSN target coverage problem, we propose a heuristic optimization algorithm EASA that combines elite selection and adaptive strategy. In this way, we can prevent the best individuals of the current group from being lost in the next generation, and the fitness value of each person can also be dynamically changed to improve the convergence speed. Different from traditional artificial intelligence GA, our proposed EASA takes SA as the framework and uses SA and GA to generate a new generation of individuals in the iterative process. When selecting new individuals, an adaptive selection strategy is adopted. According to the different fitness values of individuals in the current community, individuals are adaptively selected. It is ensured that every individual with low fitness in the community is eliminated, so that excellent individual genes can be preserved. In the subsequent steps, the crossover strategy is a multipoint crossover of the target individual rather than a single point. In order to ensure the diversity of individual genes, we have adopted a mutation strategy. But the mutation rate in this article is lower than that in the genetic algorithm. The process of EASA can be described as initializing population, calculating fitness, adaptive selection, crossover, mutation, temperature initialization, and termination condition.


### 4.1. Initializing Community

Unlike other evolutionary methods, EASA’s solution competes for survival in evolutionary iterations. The EASA does not paper on a single variable but on a community with variables that undergoes an evolutionary process starting via the initial community. Additionally, a larger community size, when paired with an elitist adaptive selection method, allows the algorithm to reach a good solution more quickly than a smaller community size. In EASA, each target is randomly initialized by a random number generator. Because the random value has great discreteness, the accuracy of the solution will be lower if it is used directly. Therefore, EASA developed the best solution for improvement according to formula (10).For the LSWSNs to solve the optimal coverage set selection problem, the working and sleeping state of the wireless sensorNi are represented by the bit string G=g1,g2,⋯,gh,⋯,gH, through formula (1), and the actual space is converted into the corresponding coding space.
(8)gh=1,Niwasselectedasaworkingnodeinroundh0,otherwise,wheregh represents any sensor node.Assuming a total of 8 sensor nodes are placed in the monitoring area, the length of stringG is 8. If the nodes N1,N4,N6 are working, this string can be expressed as 1,0,0,1,0,1,0,0.In order to convert the search for the genotype individual space into the problem of finding the optimal solution to the community, we set the sensor community to three dimensions. And all sensors are working within the number of working rounds. Then, the community code is as follows:(9)ChromD,E,NUM=1,where matrixChrom is the initial community and NUM is the number of initial communities. D represents the maximum number of rounds that the sensor can work, and E is the number of sensors.


### 4.2. Calculating Fitness

The fitness of an individual is directly corresponding to its objective value. In this paper, the objective value of a solution variable depends on the working life of sensor network. In this way, the longer the lifespan, the better the individual is. During each iteration, use formula (10) to evaluate individuals. The specific operation is as follows:First, calculate the fitness value of the individual, then select the minimum fitness value in the community, and finally subtract the minimum fitness value from each individual in the community to obtain a new fitness value. We propose a three-dimensional communityChromD,E,NUM. The fitness value we proposed is to calculate the working life of the LAWSNs, that is, to calculate the number of positive numbers in each row of the matrix C in Chapter 3. The initial fitness value is DE. The existence of zero elements in matrix C means that the sensor network cannot complete the complete coverage in this round, so the applicability of formula (10) is modified. To increase the fitness value, we add an adaptive factor. This method can also optimize the group coverage problem. The adaptive selection formula is shown in formula (11).
(10)FitnessWn=fitnessWn−1,whereWn represents any network entity and nϵ1,NUM.
(11)FitnessWn=fitnessWn−minfitness.


### 4.3. Adaptive Selection

Selection is a genetic operation, which is to select an individual from the current community and place it in the next generation’s community. Individuals with low fitness values are generally discarded.In result, the probability of premature convergence decreases relatively and the preservation of individual is improved. In this respect, it is important to note that not all individuals are chosen. The way to be selected is as in formulas (12), (13), and (14).
(12)pWn=fitnessW∑n=1NUMfitnessWnn=1,2,⋯,NUM,(13)Pn=Pn−1+pWnn=1,2,⋯,NUM,(14)PWn−1<rand<PWnn=1,2,⋯,NUM.Wn represents any network entity,fitnessWn is the fitness value of the Wnth sensor network, pWn represents the probability of the sensor network Wn being selected, and rand is a random number between 0 and 1.Repeat the above steps until the iteration is complete. The new community generated is composed of members of the current self or the parent community. In this way, the community is constantly updated. After multiple iterations, the elimination of low fitness values can be achieved in the simulation, and the high retention can be achieved.


### 4.4. Crossover

After finishing the operation of selecting individuals from the current iteration community, the next step is to perform crossover and selection operations to generate the second iteration community. In the crossover operation, the children copy the parent’s gene, and the point where the parent chromosome crosses is randomly generated. Each of these couples will have two children. The crossover operation is not static; there is one point, two points, and uniform crossover. In EASA, the multipoint crossover based on the target value is used to modify, and the expression is defined as formulas (15) and (16).We set the parent matrix representing the individual asX1 and X2, and the child matrixes are X1′ and X2′. Assume that the number of sensors in each LSWSNs is 3, and the number of sensors working rounds is 4. Randomly generate a number U between 1 and 4 and cross all the numbers from 1 to U in matrix X1 with the numbers from 1 to U in matrix X2. After crossover, child matrices X1′ and X2′ are generated.
(15)X1=111111111111X2=000000000000.After crossover,(16)X1′=110111011101X2′=001000100010.


### 4.5. Mutation

Sporadically, in biological systems, there will be unavoidable errors in copying random information, and mutations will occur. This kind of mutation puts it in the mutation operation. Therefore, the mutation operation is to randomly select an individual and randomly select the position of this individual to mutate. Mutation operation is to randomly select individuals in the community and then invert the values of some of its columns or mutate a certain gene of the individual to perform mutation operations. The mutation in this paper is to change the value of some bits of an individual from 1 to 0 or from 0 to 1. It is worth noting that the probability of mutation is very small.


### 4.6. Annealing Operator

The physical annealing process consists of the following three parts: heating process, isothermal process, and cooling process. The SA realizes a large-scale coarse search and a local fine search by controlling the initial valueT0 of the annealing temperature and its attenuation change process. Generally speaking, only a large enough T0 can meet the algorithm requirements. Because when the problem scale is large, too small T0 often makes it difficult for the algorithm to escape the local trap and fail to reach the global optimum. But in order to reduce the amount of calculation, T0 should not be too large. Set the number of cycles at the same temperature as count.The steps of the annealing operator are as follows:(1)
Set the fitness value of the current population as the initial optimal solution(2)
Set the number of cycles count at the same temperature to0(3)
Perturb the population that currently generates the optimal solution, generate a new solution, and calculate a new fitness valueUu. According to formula (17), if the difference between the new solution Uu and the old solution Uu−1 is greater than 0, the new solution is accepted. Otherwise, the acceptance probability q of a new solution is generated. Then, compare q with the random number rand, and if q is greater than the random number, accept it; otherwise, do not accept it
(17)q=exp−Um−Um−1Tk,ifUm<Um−1,1ifUm≥Um−1.(4)
If the cycle number is less than count, then add 1 and return to step (3). Otherwise, execute formula (17). α is the attenuation coefficient. T is the current temperature
(18)T=αT.


### 4.7. Termination Condition

Termination is the criterion by which EASA decides whether to continue the iteration or stop. In the process of repeating the iterative loop, until the solution of the predetermined number of iterations is reached. When the target value reaches a certain threshold, EASA will terminate according to the number of iterations. After the maximum number of iterations, the process is terminated, and the individual with the highest fitness in the community is the final solution.


### 4.8. Steps of the Algorithm

First, initialize the algorithm parameters and the community. Then, calculate the initial community fitness value and perform adaptive selection, crossover, and mutation. Next, an annealing operation is performed to determine the size of the new value and the old value in turn. Finally, determine whether the termination condition is reached. The specific details of the EASA process are shown in Figure4.Figure 4
Steps of EASA.


## 4.1. Initializing Community

Unlike other evolutionary methods, EASA’s solution competes for survival in evolutionary iterations. The EASA does not paper on a single variable but on a community with variables that undergoes an evolutionary process starting via the initial community. Additionally, a larger community size, when paired with an elitist adaptive selection method, allows the algorithm to reach a good solution more quickly than a smaller community size. In EASA, each target is randomly initialized by a random number generator. Because the random value has great discreteness, the accuracy of the solution will be lower if it is used directly. Therefore, EASA developed the best solution for improvement according to formula (10).For the LSWSNs to solve the optimal coverage set selection problem, the working and sleeping state of the wireless sensorNi are represented by the bit string G=g1,g2,⋯,gh,⋯,gH, through formula (1), and the actual space is converted into the corresponding coding space.
(8)gh=1,Niwasselectedasaworkingnodeinroundh0,otherwise,wheregh represents any sensor node.Assuming a total of 8 sensor nodes are placed in the monitoring area, the length of stringG is 8. If the nodes N1,N4,N6 are working, this string can be expressed as 1,0,0,1,0,1,0,0.In order to convert the search for the genotype individual space into the problem of finding the optimal solution to the community, we set the sensor community to three dimensions. And all sensors are working within the number of working rounds. Then, the community code is as follows:(9)ChromD,E,NUM=1,where matrixChrom is the initial community and NUM is the number of initial communities. D represents the maximum number of rounds that the sensor can work, and E is the number of sensors.


## 4.2. Calculating Fitness

The fitness of an individual is directly corresponding to its objective value. In this paper, the objective value of a solution variable depends on the working life of sensor network. In this way, the longer the lifespan, the better the individual is. During each iteration, use formula (10) to evaluate individuals. The specific operation is as follows:First, calculate the fitness value of the individual, then select the minimum fitness value in the community, and finally subtract the minimum fitness value from each individual in the community to obtain a new fitness value. We propose a three-dimensional communityChromD,E,NUM. The fitness value we proposed is to calculate the working life of the LAWSNs, that is, to calculate the number of positive numbers in each row of the matrix C in Chapter 3. The initial fitness value is DE. The existence of zero elements in matrix C means that the sensor network cannot complete the complete coverage in this round, so the applicability of formula (10) is modified. To increase the fitness value, we add an adaptive factor. This method can also optimize the group coverage problem. The adaptive selection formula is shown in formula (11).
(10)FitnessWn=fitnessWn−1,whereWn represents any network entity and nϵ1,NUM.
(11)FitnessWn=fitnessWn−minfitness.


## 4.3. Adaptive Selection

Selection is a genetic operation, which is to select an individual from the current community and place it in the next generation’s community. Individuals with low fitness values are generally discarded.In result, the probability of premature convergence decreases relatively and the preservation of individual is improved. In this respect, it is important to note that not all individuals are chosen. The way to be selected is as in formulas (12), (13), and (14).
(12)pWn=fitnessW∑n=1NUMfitnessWnn=1,2,⋯,NUM,(13)Pn=Pn−1+pWnn=1,2,⋯,NUM,(14)PWn−1<rand<PWnn=1,2,⋯,NUM.Wn represents any network entity,fitnessWn is the fitness value of the Wnth sensor network, pWn represents the probability of the sensor network Wn being selected, and rand is a random number between 0 and 1.Repeat the above steps until the iteration is complete. The new community generated is composed of members of the current self or the parent community. In this way, the community is constantly updated. After multiple iterations, the elimination of low fitness values can be achieved in the simulation, and the high retention can be achieved.


## 4.4. Crossover

After finishing the operation of selecting individuals from the current iteration community, the next step is to perform crossover and selection operations to generate the second iteration community. In the crossover operation, the children copy the parent’s gene, and the point where the parent chromosome crosses is randomly generated. Each of these couples will have two children. The crossover operation is not static; there is one point, two points, and uniform crossover. In EASA, the multipoint crossover based on the target value is used to modify, and the expression is defined as formulas (15) and (16).We set the parent matrix representing the individual asX1 and X2, and the child matrixes are X1′ and X2′. Assume that the number of sensors in each LSWSNs is 3, and the number of sensors working rounds is 4. Randomly generate a number U between 1 and 4 and cross all the numbers from 1 to U in matrix X1 with the numbers from 1 to U in matrix X2. After crossover, child matrices X1′ and X2′ are generated.
(15)X1=111111111111X2=000000000000.After crossover,(16)X1′=110111011101X2′=001000100010.


## 4.5. Mutation

Sporadically, in biological systems, there will be unavoidable errors in copying random information, and mutations will occur. This kind of mutation puts it in the mutation operation. Therefore, the mutation operation is to randomly select an individual and randomly select the position of this individual to mutate. Mutation operation is to randomly select individuals in the community and then invert the values of some of its columns or mutate a certain gene of the individual to perform mutation operations. The mutation in this paper is to change the value of some bits of an individual from 1 to 0 or from 0 to 1. It is worth noting that the probability of mutation is very small.


## 4.6. Annealing Operator

The physical annealing process consists of the following three parts: heating process, isothermal process, and cooling process. The SA realizes a large-scale coarse search and a local fine search by controlling the initial valueT0 of the annealing temperature and its attenuation change process. Generally speaking, only a large enough T0 can meet the algorithm requirements. Because when the problem scale is large, too small T0 often makes it difficult for the algorithm to escape the local trap and fail to reach the global optimum. But in order to reduce the amount of calculation, T0 should not be too large. Set the number of cycles at the same temperature as count.The steps of the annealing operator are as follows:(1)
Set the fitness value of the current population as the initial optimal solution(2)
Set the number of cycles count at the same temperature to0(3)
Perturb the population that currently generates the optimal solution, generate a new solution, and calculate a new fitness valueUu. According to formula (17), if the difference between the new solution Uu and the old solution Uu−1 is greater than 0, the new solution is accepted. Otherwise, the acceptance probability q of a new solution is generated. Then, compare q with the random number rand, and if q is greater than the random number, accept it; otherwise, do not accept it
(17)q=exp−Um−Um−1Tk,ifUm<Um−1,1ifUm≥Um−1.(4)
If the cycle number is less than count, then add 1 and return to step (3). Otherwise, execute formula (17). α is the attenuation coefficient. T is the current temperature
(18)T=αT.


## 4.7. Termination Condition

Termination is the criterion by which EASA decides whether to continue the iteration or stop. In the process of repeating the iterative loop, until the solution of the predetermined number of iterations is reached. When the target value reaches a certain threshold, EASA will terminate according to the number of iterations. After the maximum number of iterations, the process is terminated, and the individual with the highest fitness in the community is the final solution.


## 4.8. Steps of the Algorithm

First, initialize the algorithm parameters and the community. Then, calculate the initial community fitness value and perform adaptive selection, crossover, and mutation. Next, an annealing operation is performed to determine the size of the new value and the old value in turn. Finally, determine whether the termination condition is reached. The specific details of the EASA process are shown in Figure4.Figure 4
Steps of EASA.


## 5. Simulation and Results

The EASA method we proposed to solve the sensor duty cycle problem will carry out a series of experiments and compare EASA with GA and PSO to prove its effectiveness. The comparison of algorithms is carried out under different number of sensors. In addition, all test cases are completed on a computer equipped with matlab2018a, and the applicability used in the algorithm is calculated according to formula (10).In order to be able to compare these three algorithms under the same experimental conditions, we uniformly define the parameters commonly used in the sensor duty cycle problem in LSWSNs. The number of iterations is set to100 generations, and the population size is 40. The surveillance area of LSWSNs is set as a square area with a side length of 200, and the coordinates of the sensor and target node are randomly generated in this area.The comparison between the three algorithms uses the same number of iterations of 50 and community size of 50. And the coordinate parameters of the sensor nodes are the same, and each individual has the same number of genes. The specific parameters of GA, PSO, and EASA are in Tables1–3.Table 1
Parameters of the GA.
Iteration numbersCommunity sizeCrossover probabilityMutation probabilityGA100500.90.05Table 2
Parameters of the PSO.
Iteration numbersCommunity sizeThe maximum velocityThe cognitive and social parametersPSO1005042Table 3
Parameters of the EASA.
Iteration numbersCommunity sizeThe initial temperatureAttenuation coefficientEASA100502000.9The key to affecting the behavior and performance in GA is the probability of crossover and mutation. The greater the crossover probability, the faster the iteration speed of the new individual. And too much crossover probability will increase the risk of genetic model being destroyed. If the mutation probability is too small, too few new individuals will be produced. Therefore, in this simulation calculation, the crossover probability is set to0.9, and the mutation probability is 0.05.In PSO, the maximum speed determines the maximum moving distance of the particles in a cycle, which is set to4. Both cognitive and social parameters are set to 2, namely, c1=c2.In EASA, the area where the global maximum fitness value is located can only be found in the initial large-scale search stage, and the search range can be gradually reduced. Therefore, only a sufficiently large initial temperature can meet the algorithm requirements, so the initial temperature is set to 200. The settings of crossover probability are 0.9. And mutation probability is 0.03. The attenuation coefficient determines the cooling process. If the attenuation coefficient is too large, it will slow down the temperature attenuation process, resulting in an increase in the number of iterations of the algorithm, so it should not be too large, and set it to 0.9.Figure5 shows the convergence speed and lifespan change of the three algorithms of EASA, GA, and PSO under different sensor numbers. It can be seen that EASA has a longer network life than GA and PSO. It is because when selecting a new generation of individuals, EASA adopts an adaptive selection strategy. This will eliminate individuals with low fitness in each community and ensure the ability of the new community to find the best. And the mutation strategy of EASA increases the diversity of individuals in the community and prevents EASA from falling into local extremes. Although GA also uses a mutation strategy, the probability of mutation is lower than that of GA, which reduces the risk of model damage. In Figure 5(a), the GA and PSO solutions were not very different at the beginning and the sensor number is 80. Gradually, the 10th generation opened the gap. At the same time, EASA’s solution has always been higher than the other two algorithms. When EASA converges, the final LSWSNs’ lifetime is 76.65. The LSWSNs’ lifetimes of the other two algorithms, GA and PSO, are 69.13 and 60, respectively.Figure 5
The lifespan of the three algorithms. (a) 80 sensors; (b) 90 sensors; (c) 100 sensors; (d) 110 sensors.
(a)(b)(c)(d)In Figure5(b), as the number of sensors is 90, the growth trends of the three solutions are roughly the same. Ultimately, the maximum lifespan of EASA is 81.35, GA is 76.85, and PSO is 73.38. In Figures 5(c) and 5(d), when the sensor number is 100 and 110, there are changes compared with the previous two simulation results. In Figure 5(c), at the beginning, the growth rate of GA is greater than that of EASA and PSO, until the situation changes when the number of iterations reaches 30. EASA’s solutions continue to grow, while GA tends to be smooth, gradually converging to 83.85. Finally, EASA is 88.97, and PSO is 80. In Figure 5(d), under the condition that the sensor is 110, PSO’s solutions are relatively flat, as well as EASA and GA continued to grow until EASA’s solution is 91.97 and GA is 87.87. And PSO is 80.78.Figure6 is made to better show the convergence speed of the three algorithms. In Figure 6(a), we take the LSWSNs’ lifetime as 60 and the number of sensors as 80. The solutions of the three algorithms are, respectively, 30, 48, and 60 iterations. The trend of the histograms in Figures 6(b) and 6(a) is the same, but the condition in Figure 6(b) is that the number of sensors is 90, and the common lifespan is 73. The iteration time required for the three solutions is 22, 32, and 60 in order. Figure 6(c) shows that when the number of sensors is 90, the number of iterations required for the three algorithms to reach a lifetime of 73 together is 32, 32, and 47. In Figure 6(d), as the sensor number is 110, and the lifespan is 80, EASA, GA, and PSO require 32 iterations, 38 iterations, and 37 iterations in turn.Figure 6
The number of iterations required for the three algorithms to reach 4 different network lifetimes, respectively. (a) The number of sensors is 80, and the solutions of the three algorithms reach 60; (b) the number of sensors is 90, and the solutions of the three algorithms reach 73; (c) the number of sensors is 100, and the solutions of the three algorithms reach 80; (d) the number of sensors is 110, and the solutions of the three algorithms reach 80.
(a)(b)(c)(d)Figures7(a)–7(d) show the trend of the three algorithms more clearly in the form of line charts. Specifically, in Figure 7(a), it is shown that when the number of sensors is 40, the convergence speed of EASA is faster than the other two solutions, and EASA maintains a higher lifespan in the iterative process. From the beginning of the iterative process, the lifetime value of EASA is higher than GA and PSO, and EASA keeps a higher value until the algorithm convergence is reached. In Figure 7(a), the difference between PSO and GA is not very obvious, and their optimal solutions are 47.14 and 45.56, respectively. On the contrary, the lifespan of EASA can reach 53.14.Figure 7
The lifespan of the three algorithms. (a) 40 sensors; (b) 50 sensors; (c) 60 sensors; (d) 70 sensors.
(a)(b)(c)(d)In Figure7(b), although the solutions of EASA and PSO converge at the same time, the network lifetime of EASA is significantly higher than that of PSO. As the number of iterations increases, EASA’s solution has been higher than the other two algorithms until all three algorithms converge. Before the 41st generation, the solution of PSO is higher than that of GA, but PSO tends to converge to 55.78, and GA continues to increase until the lifespan is 59.78. Finally, the maximum lifespan reached by EASA is 64.45.Other than that, there is little difference between the trends in Figures7(c) and 7(d). EASA’s solutions are all the highest, but the iteration in which the three solutions tend to converge is different. In Figure 7(c), the maximum lifetimes of EASA, GA, and PSO are 68.97, 60.85, and 55.34, respectively. Similarly, in Figure 5(d), the values of the three solutions are 73.77, 67.99, and 60.00.In order to better illustrate the advantages of EASA, in Table4, EASA is compared with GA and PSO, and the percentage increase in network lifespan is shown.Table 4
Improvement percentage of network lifespan by EASA compared with GA and PSO.
Sensor number40506070GA16.55%7.81%13.34%8.50%PSO12.73%15.54%24.6322.95%Table4 shows that when the number of sensors is 40, 50, 60, and 70, EASA has a higher lifetime percentage than GA and PSO. It can be seen that EASA can be up to 16.55% higher than GA and 24.63% higher than PSO.


## 6. Conclusions

In this paper, we propose an elite adaptive simulated algorithm (EASA) to settle the target coverage problem in LSWSNs. We first formulate our aim function as formula (10) to maximize the working life of sensor network under multiple constraints. To demonstrate the advantages of EASA, the target coverage problem was simulated. And we used GA and PSO for performance comparison. Simulation experiments show that our proposed EASA solution has a longer lifespan of LSWSNs than GA and PSO, and its complexity is lower than previous methods.



---

*Source: 9915133-2021-06-28.xml*