# A Binary Adaptive Clone Shuffled Frog Leaping Algorithm for Three-Dimensional Low-Energy Target Coverage Optimization in Environmental Monitoring Wireless Sensor Networks

Authors: Bao Liu; Rui Yang; Mengying Xu; Jie Zhou
Journal: Journal of Sensors
 (2021)

---

## Abstract

In recent years, more and more researchers have paid attention to the three-dimensional target coverage of environmental monitoring wireless sensor networks (EMWSNs) under real environmental conditions. However, the target coverage method studied in the traditional two-dimensional plane is full of loopholes when applied in the real three-dimensional physical world. Most coverage algorithms usually only optimize for a single problem of target coverage or network energy consumption and cannot reduce network energy consumption while improving coverage. This paper proposes a novel binary adaptive clone shuffled leapfrog algorithm (BACSFLA) suitable for EMWSNs. BACSFLA has an excellent performance in the coverage of three-dimensional nodes, which can significantly reduce the network energy consumption of ENWSNs in the coverage process, and greatly improve the coverage of nodes. Through simulation experiments, BACSFLA was compared with simulated annealing (SA) and genetic algorithm (GA) in the same conditional parameters. The coverage rate of BACSFLA in EMWSNs is3.9% higher than that of GA and 5.4% higher than that of SA. The network energy consumption of BACSFLA is 36.0% lower than GA and 35.9% lower than SA. Moreover, BACSFLA can significantly reduce the calculation time and get better results in a shorter time.


---

## Body

## 1. Introduction

EMWSN is a self-organizing network composed of sensor nodes deployed in the environmental monitoring area. The nodes have the characteristics of small size, low cost, and low-power consumption. They can perceive, collect, and process the information of the monitored objects in real-time. Coverage optimization is a basic problem of EMWSNs. The proper coverage of EMWSN nodes will directly affect network performance and network life. Therefore, the coverage optimization of EMWSN nodes has always been a hot issue of concern and research by scholars. In recent years, some researchers have made breakthroughs in improving the energy efficiency and coverage of wireless sensor networks (WSNs) [1, 2].The primary purpose of EMWSN coverage is to expand its monitoring range and increase the coverage of the target and secondly to ensure certain network performance. At present, most of the research on covering this basic problem by researchers is carried out in an ideal two-dimensional environment [3]. However, most of the actual application scenarios of EMWSNs are in the three-dimensional environment, and the coverage method studied in the two-dimensional plane will have very bad performance when applied in the real three-dimensional physical world. Because the space and surface location of the target in the real world is mostly in the environment of agriculture, forestry, and wild [4]. It is urgent to design coverage perception models and corresponding algorithms that conform to three-dimensional scenes, to improve the practical applicability of EMWSNs. At the same time, EMWSNs need to further design more complete 3D perception models and effective coverage optimization algorithms. The impact of space size, target, and the number of sensor monitoring nodes on the coverage performance of wireless sensor networks is extremely important [5].Target coverage is generally used to reflect the sensing ability of EMWSNs to the objective world and can also be used as a standard to measure the quality of network monitoring services [6]. The coverage of EMWSNs reflects the quality of EMWSNs’ monitoring of target areas and target nodes and is the basis for providing perception services required by the system. Through the coverage control technology, the space allocation of the network can also be optimized, and the tasks of object perception, information acquisition, and data transmission can be completed more energy-saving and efficient [7]. Coverage optimization control is one of the key technologies for network construction and normal network operation. Target coverage optimization directly affects network performance indicators such as network energy consumption and network monitoring area [8].Due to the particularity of the application environment of EMWSNs, in most cases, the staff cannot reach it on the spot. Sensor nodes can only be distributed in the target area reached by aircraft [9]. The throwing process is simple and random [10]. How to use a limited number of sensor nodes to monitor the coverage of the target area to the maximum extent, build a reliable sensor network, and maximize the network’s monitoring efficiency of the target area has always been one of the research hotspots of EMWSN technology [11].Based on the above background, this article is aimed at improving the 3D coverage of EMWSNs and saving network energy consumption in the real application environment. This article focuses on the 3D perception model close to the actual application environment and the corresponding 3D coverage deployment method. EMWSN coverage optimization method. By designing coverage perception models and corresponding algorithms that are closer to the real 3D application environment, the applicability of EMWSN coverage in real-life environments can be effectively improved. Besides, taking into account performance indicators such as network energy consumption based on meeting coverage requirements is also of practical significance in terms of improving network perceived service quality [12].Literature [13] proposed a new coverage optimization algorithm for WSNs based on SA optimization. SA can significantly improve the global optimization capability of the algorithm and has the characteristics of fast convergence. The results show that SA can improve network coverage efficiency and reduce node energy consumption. However, the algorithm is simulated in a two-dimensional environment, and its robustness is poor, and it has little reference significance in the real environment.Literature [14] proposed an improved GA to optimize the coverage efficiency of WSNs. The result is that the improved GA is better than other intelligent optimization algorithms in the coverage process of WSNs and has better performance than the immune algorithm and the whale optimization algorithm. The improved GA is better than the comparison algorithm in coverage, network overhead, and stability. However, the algorithm’s convergence performance is poor, the convergence speed is slow, and the calculation complexity is relatively large. And because three-dimensional environmental factors are not considered, the performance of the algorithm, in reality, cannot be evaluated.Literature [15] proposed a new type of GA with efficient coverage, which has very good performance in WSNs. The algorithm combines an improved crossover operator, which can maintain high accuracy in the fitness function calculation. The result is that the quality and stability of the solution of this algorithm are better than that of the comparison algorithm. However, the algorithm does not consider the network energy consumption during the coverage process, and the network overhead cannot be estimated. Moreover, since the simulation environment of the algorithm is performed in a two-dimensional ideal plane, the performance in a three-dimensional real environment may be quite different from the ideal result.Literature [16] proposed a new heuristic algorithm based on a GA to optimize the target coverage of WSNs. This algorithm can extend the life of the network to a large extent and has a faster convergence speed and better performance than the comparison algorithm. However, this algorithm greatly increases the complexity of the algorithm, and if it encounters a high-density three-dimensional network, poor results may occur.Literature [17] proposed an improved greedy algorithm to extend the network lifetime of WSNs. A greedy algorithm has the characteristics of simple structure, easy implementation, fast convergence, and strong robustness. The results show that the algorithm can significantly improve the survival time of the network and has a faster convergence rate compared with the comparison algorithm. However, since only the network lifetime is considered, the optimal effect is not achieved in terms of coverage.Literature [18] proposed an improved Bat algorithm to improve the coverage efficiency of 3D WSNs. The algorithm takes into account the harsh environment in the three-dimensional space and adopts a multiobjective optimization strategy to improve the coverage rate while reducing network energy consumption. The results show that compared with the comparison algorithm, this algorithm can reduce the energy consumption of nodes by a greater degree of uniform node energy. However, the global search of the algorithm is not strong, the convergence is also poor, and the implementation is relatively complicated.The main contributions of this paper are as follows:(1)
This paper proposes a new target coverage model for EMWSNs. The model uses a binary coding scheme, which can greatly reduce the computational complexity and speed up the calculation. And for the three-dimensional coverage of the nodes in EMWSNs, a 3D target coverage model was constructed to extend the traditional planar coverage to spatial coverage. Because the model has strong stability, it can also have excellent performance in real-world EMWSNs(2)
This paper proposes an improved target coverage algorithm. Based on the selection of the optimal target coverage node-set, BACSFLA considers the energy consumption of the nodes, which can greatly improve the coverage optimization performance and network energy consumption of EMWSNs. Because BACSFLA combines adaptive operators and clone operators, it has good global search performance and can get the optimal solution in a short time. Compared with the two-dimensional space, the three-dimensional space has an increase of an order of magnitude in both the complexity and the amount of calculation. Compared with the comparison algorithm, BACSFLA has a faster convergence speed, higher coverage, and lower network in three-dimensional space(3)
This paper proposes an improved low-power clone selection operator. This operator is aimed at reducing network energy consumption. For individuals to be cloned, a certain cloning ratio is used to generate a new population according to the energy consumption. The results show that using this operator not only does not increase the amount of calculation of the algorithm but also can significantly reduce network energy consumptionThe structure of this article is as follows. Section2 introduces the target coverage model and binary coding scheme of EMWSNs. Section 3 uses BACSFLA to optimize the target coverage algorithm. Section 4 presents the results of simulation experiments and discusses the performance of BACSFLA in comparison with other algorithms in EMWSNs. Then, Section 5 concludes.


## 2. EMWSN Target Coverage Model

EMWSN is a network system composed of a large number of sensor nodes deployed in monitoring areas such as forests, grasslands, and oceans. It is self-organized through wireless communication. It mainly cooperatively senses, collects, and processes the information of the sensed objects in the network coverage area [19]. And send it to the monitor.EMWSN node deployment methods can be divided into static deployment, dynamic deployment, and hybrid deployment. Considering that the environment of EMWSNs is usually more complicated and harsh, the simulation environment in this article is static deployment. In this case, sensor nodes can usually be deployed in the area to be monitored in a deterministic or random manner, and generally, no longer move after deployment [20].According to the classification of application attributes, the coverage of EMWSNs can be divided into area coverage, target coverage, and barrier coverage, which, respectively, cover the entire area and certain fixed points or paths in the area [21]. This article uses the target coverage model. Target coverage studies the realization of the perception of special locations or monitoring points in the area to be covered. The model where the target is successfully covered in the 3D environment is shown in Figure 1.Figure 1
EMWSN target coverage.In EMWSNs, the monitoring node must not only monitor the target but also estimate the area where the target is located, so when the target is covered by three or more sensor monitoring nodes, the target can be guaranteed to be successfully covered. When covering, energy-saving coverage should be considered. If sensor monitoring nodes are randomly distributed, to maximize the network survival time and monitor reliability, this paper sets the goal of the minimum number of sensor monitoring nodes successfully covered to three.This article uses a probabilistic perception model. Considering the complexity of the actual application environment, the probabilistic model can more reasonably represent the perception characteristics of sensor nodes [22]. In actual EMWSNs, the various sensing signals of the sensors will attenuate with the increase of the propagation distance, and the sensor nodes deployed in the field will also be interfered with by various environmental noises. When the target is very close to the sensor monitoring node, the sensor monitoring node can be sure to detect the target. As the distance between the target and the sensor monitoring node increases, the sensing signal strength gradually attenuates and is subject to various interferences [23]. And the detection ability of the target increases with the increase of the distance shows a gradual weakening trend, which affects the certainty of the target detection by the sensor monitoring node [24].For any sensor nodelm, its maximum sensing radius is kl, and the sensing area is divided into a definite sensing area and a probability sensing area according to the Euclidean distance from lm, denoted as Cla and Clb, where the definite sensing radius of the area is kla. For the target rn in space, if the point is in Cla, the monitoring probability of the sensor monitoring node lm when the target is located at the point rn is 1. If the point is in Clb, the detection probability of the sensor when the target is located at rn decreases as the Euclidean distance between the target and the sensor increases; if the target is located outside the sensing area, the target cannot be detected when the target is located at rn. The sensor node lm is detected. The coordinates of lm are tm,wm,vm, and the coordinates of rn are tn,wn,vn. In the probabilistic perception model, the probability dlm,rn that is detected by the sensor lm when the target is located at rn is
(1)dlm,rn=1,ulm,rn≤kla,e−θρβ,kla≤ulm,rn≤kl0,ulm,rn>kl.,In equation (1), ulm,rn is the Euclidean distance between sensor monitoring node lm and target rn, and its calculation formula is equation (2). ρ=ulm,rn−kla. θ and β are the path loss indexes of the sensor’s detection signal strength. Both parameters are determined by the physical characteristics of the sensor. In this paper, θ=β=1. It can be seen that when ρ is large enough, the value of dlm,r will quickly decay to close to zero.
(2)ulm,rn=tm−tn2+wm−wn2+vm−vn2.Assuming that there areM sensor monitoring nodes and N targets in EMWSNs, the target coverage relationship matrix P is obtained by equation (3) when the binary coding scheme is adopted.
(3)P=pma1,1pmam1,2⋯pma1,M−1pma1,Mpma2,1pma22⋯pma2,M−1pma2,M⋮⋮pman,m⋮⋮pmaN−1,1pmaN−1,2⋯pmaN−1,M−1pmaN−1,MpmaN,1pmaN,2⋯pmaN,M−1pmaN,M.In equation (3), pman,m represents the situation of the target being sensed by the sensor monitoring node, and its value formula is
(4)pman,m=1,dlm,rn>drand,0,dlm,rn<drand.In equation (4), drand represents the random probability. If the perceptual probability dlm,rn is greater than the random probability drand, then the target is successfully covered by the monitoring node. At this time, pman,m=1; otherwise, pman,m=0.To reduce the energy consumption of EMWSNs and at the same time limit the sensing performance of sensor monitoring nodes, this paper sets the maximum monitoring target number of a sensor asH. According to performance constraints, a new perception relationship matrix Q can be obtained as
(5)Q=qma1,1qma1,2⋯qma1,M−1qma1,Mqma2,1qma22⋯qma2,M−1qma2,M⋮⋮qman,m⋮⋮qmaN−1,1qmaN−1,2⋯qmaN−1,M−1qmaN−1,MqmaN,1qmaN,2⋯qmaN,M−1qmaN,M.In equation (5), qman,m represents the condition of the target being sensed by the sensor monitoring node, and qman,m=1 means that the target is sensed and monitored by the corresponding sensor node. If qman,m=0, it means that the target is not sensed by the corresponding sensor node or sensed by the corresponding sensor node but not monitored. The Q matrix constraint relationship can be expressed as
(6)∑n=1Nqman,m≤H,m=1⋯M.The target coverage matrix optimization model of EMWSNs described in this paper is the process of adding constraints to theP matrix to obtain the optimized Q matrix. BACSFLA has high-efficiency computing performance and excellent global search capabilities, which can solve the optimization target coverage problem in EMWSNs with excellent performance.


## 3. BACSFLA for High-Coverage and Low-Energy Consumption in EMWSNs

In this paper, BACSFLA adopts a binary population coding scheme and produces two brand-new operators for EMWSNs. The adaptive operator improves the global search capability during the BACSFLA iteration process and at the same time prevents the algorithm from falling into the local optimal solution. The addition of the low-power selection feature to the clone operator is of great help in accelerating the iteration speed of BACSFLA and reducing the overall energy consumption. As a coevolutionary algorithm, BACSFLA combines stochastic and deterministic methods. The schematic diagram of BACSFLA is shown in Figure2.Figure 2
BACSFLA principle diagram.The principle of BACSFLA is to assume that there is a group of frogs in the pond, and there are a lot of rocks in the pond. The frogs can jump through these rocks and finally find food. First, the frog population is divided into several subgroups with the same number. Each subgroup starts to forage independently of each other, but the frogs within the subgroup can exchange information with each other to ensure that the frogs in each subgroup can be directed towards the subgroup. The excellent frogs in the group learn. After a certain period of food, the subgroups send their excellent frogs to communicate to ensure that the overall frogs learn from the best frogs. This process is also called memetic evolution. BACSFLA can be seen as a combination of local optimization and global optimization, that is, each subgroup is a process of local optimization, and the exchange of information between subgroups is a process of global optimization.BACSFLA is based on the collective search for food by the frog population, focusing on grouping information exchange, and centering on the internal communication of subgroups and global information exchange to realize the whole process of optimizing, adding an improved adaptive operator, and low-power consumption. Clone the selection operator, to achieve the purpose of searching and optimizing. The algorithm steps of BACSFLA are as follows:Step 1.
In the stage of randomly generating the initial population, a total ofI frogs are generated.Step 2.
In the sorting stage, the fitness function is designed according to the target coverage rate, and the fitness value of theI frog is calculated and sorted from small to large.Step 3.
In the grouping stage, it is divided intoI1 subgroups and a single subgroup contains I2 frogs. The grouping is carried out according to the alternating principle. After sorting, the frogs with serial numbers from 1 to I1 are taken out, and each subgroup is placed in descending order. The frogs with serial numbers from I1+1 to 2I1 are taken out and one for each subgroup in descending order. And so on, until all the frogs are divided.Step 4.
In the subgroup internal search stage, determine the number of searches within the subgroup, and then search for the next subgroup after completing one subgroup search, until all subgroups have been searched.Step 5.
In the mixed subgroup stage, after completing the evolution ofI1 subgroups, reorder all the subgroups in the mixture according to the method in step two.Step 6.
In the low-power cloning stage, a certain number of individuals are selected and placed in the cloning warehouse according to the sorting situation from good to bad. The individuals in the clone warehouse are set to different clone ratios according to the energy consumption. The smaller the energy consumption, the greater the clone ratio. Finally, a mutation operation is performed on the newly generated population after cloning to generate a new population.Step 7.
In the judgment stage, if the number of global information exchanges is reached or the set termination condition is reached, the optimal solution is output; otherwise, it returns to step2.The algorithm flow chart is shown in Figure3.Figure 3
BACSFLA flow chart.


### 3.1. The Population Initialization Operation and Binary Encoding of BACSFLA

The locations of sensor nodes in EMWSNs are distributed randomly and distributed according to specific areas. When the sensor nodes are randomly distributed, they are placed anywhere in the monitoring area, and the nodes are static and immovable after they are placed. Since EMWSNs are affected by different environmental factors when monitoring the environment, the required area will show a certain distribution law. The simulated three-dimensional monitoring environment in this paper is divided into random distribution in the region, band distribution in the region, and spherical distribution in the region. The coordinate distribution of the target is the same as the coordinate distribution of the sensor node. The distribution of targets and sensors in the monitoring area is shown in Figure4.Figure 4
Schematic diagram of target and sensor node distribution: (a) random distribution; (b) banded distribution; (c) spherical distribution.
(a)(b)(c)The population coding adopts a binary coding scheme, and theP matrix is obtained after the sensor monitoring node and the target position are successfully deployed. After adding constraints to the P matrix, i different Q matrices are generated, and each Q matrix is an individual frog.


### 3.2. The Fitness Function Design of BACSFLA

The fitness function plays an important role in BACSFLA. In EMWSN target coverage optimization, it is the core of optimized search. The choice of fitness function will directly affect the accuracy of the algorithm results and the final optimization results. This paper sets the target coverage rategSi in the network as the fitness function of BACSFLA and adopts the principle that the bigger the better. The calculation formula is shown in
(7)gSi=∑n=1N∑m=1Mqman,m≥hN.In equation (7), h is the minimum number of sensor monitoring nodes that the target is successfully covered, which balances network energy consumption and coverage accuracy. In this paper, h=3. Si is denoted as the ith frog in the population.


### 3.3. BACSFLA’s Intragroup Frog Update Operation

Determine the best and worst frogs in the group after BACSFLA grouping. There must be good or bad frogs in the group. The best frog in all subgroups is denoted asSj, the worst frog is denoted as So, and the best frog in the population is denoted as Sf. Improve the position of the worst frog, the worst frog So obtains the intermediate vector according to
(8)Temp=rand×Sj−So.In equation (8), Temp is the intermediate vector between the best frog Sj in the middle group and the worst frog So in the group. rand represents a random number, 0≤rand≤1. Then, a new frog is generated, which is obtained by
(9)Sonew=So+Temp,Tempmin≤Temp≤Tempmax.In equation (9), Tempmin is the minimum jump distance of the frog, and Tempmax is the maximum jump distance of the frog. The value of Temp must be between the two. If the value of Temp overflows, it will be processed according to
(10)Temp=Tempmin,Temp<Tempmin,Temp,Tempmin≤Temp≤Tempmax,Tempmax,Temp>Tempmax.In this process, the frog jumps to find a position better thanSo, and if it is found, it will update the worst frog, otherwise, proceed to the next step. Replace the best frog Sj in the subgroup with the best frog Sf in the subgroup. Repeat equations (8), (9), and (10), if you still cannot find a better position to improve the worst in the subgroup frog So, proceed to the next step. Generate a random frog, no matter the frog is good or bad, use it instead of So.


### 3.4. BACSFLA’s Low-Power Clone Selection Operation

After BACSFLA is updated within the group, the entire population is reordered according to fitness. The low-power clone selection operation first selects a certain number of individuals with adaptability from large to small and puts them into the clone warehouse. Assume that the number of frog individuals in the cloned warehouse isNUM. Therefore, the coverage of individual frogs in the warehouse must be greater than the coverage of the remaining unselected individuals. Then, calculate the energy consumption of individual frogs in the cloned warehouse, and the calculation of network energy consumption is shown in
(11)ECSi=∑m=1Mdt×ncelec+dt×εfs×ulm,rn2.In equation (11), dt represents the data size that the sensor monitoring node needs to send when monitoring the target. ncelec represents the energy consumption during data transmission. εfs is a parameter in the signal transmission process, set εfs=1. It can be seen that the closer the sensor monitoring node is to the target, the lower the network energy consumption. In this way, when the sensor node monitors the target, it will give priority to selecting the target close to itself, thereby reducing the energy consumption of the network communication of the entire EMWSNs.After calculating the network energy consumption of individual frogs in the cloned warehouse, sort them in ascending order of energy consumption. The smaller the energy consumption, the greater the proportion of cloned individuals. The clone ratio selection is shown in(12)rate1+⋯+ratenum+⋯+rateNUM=1.In equation (12), ratenum represents the proportion of the numth frog in the clone warehouse in the total population, rate1 represents the proportion of frogs with the smallest energy consumption, and rateNUM represents the proportion of frogs with the largest energy consumption proportion. According to the energy consumption of individual frogs corresponding to the clone ratio, the clone ratio satisfies
(13)rate1>rate2>⋯>ratenum>⋯>rateNUM.After selecting the new cloning ratio, the individual to be cloned is cloned according to the cloning ratio. After the cloning operation is completed, a new intermediate population is obtained. The degree of similarity of the intermediate population is too high to perform the global search performance of BACSFLA, so the next step is to perform an adaptive mutation operation.


### 3.5. Adaptive Mutation Operation of BACSFLA

After BACSFLA performs the low-power clone selection operation, it needs to perform adaptive mutation operations on the frogs in the population to obtain differentiated individuals. This operation is conducive to search in the vicinity of the global optimal solution, while ensuring that BACSFLA will not fall into the local optimal solution, increasing the diversity of the population, and has important significance for the rapid convergence of the algorithm.BACSFLA will adaptively change the mutation probabilityBR of the population. The size of the mutation probability is affected by the fitness of the individual, and it is also affected by the speed of convergence in the iterative process. If the fitness of the individual frog is to be mutated, and the coverage rate of the frog is small, the probability of mutation will increase. In the iterative process, if the fitness of the optimal frog individual relative to the previous generation does not increase much, or no better individual is found, the mutation probability will gradually increase, and the mutation probability will not decrease until a better individual is found. The formula for changing the adaptive mutation probability is shown in
(14)BR=1−gSi∑i=1IgSi+LRgen.In equation (14), LRgen represents the driving variation factor of BACSFLA iteration to the genth generation. The calculation formula is shown in
(15)LRgen=LRgen+δ,ggen−1Sf=ggenSf,0,ggen−1Sf<ggenSf,0,gen=1.In equation (15), δ is the increment of mutation probability, set δ=0.05. It can be seen from the update equation of BR that the probability of mutation is affected by two factors. If in the iterative process, the global optimal individual has not been updated, there may be two situations, either the optimal solution has been found or the locally optimal solution is trapped. At this time, it is necessary to increase the mutation probability of all individuals, increase the global optimization ability, and judge whether the optimal solution has been found. The fitness of an individual also affects the probability of individual mutation. The greater the fitness, the smaller the probability of individual mutation. When the fitness value of an individual is large, it proves that the coverage rate of the individual is large, so it is only necessary to find the optimal solution in the close range of the individual. If the fitness value of an individual is small, it proves that the individual is far from the optimal solution, so increases the probability of mutation and expands the search range of the solution.


## 3.1. The Population Initialization Operation and Binary Encoding of BACSFLA

The locations of sensor nodes in EMWSNs are distributed randomly and distributed according to specific areas. When the sensor nodes are randomly distributed, they are placed anywhere in the monitoring area, and the nodes are static and immovable after they are placed. Since EMWSNs are affected by different environmental factors when monitoring the environment, the required area will show a certain distribution law. The simulated three-dimensional monitoring environment in this paper is divided into random distribution in the region, band distribution in the region, and spherical distribution in the region. The coordinate distribution of the target is the same as the coordinate distribution of the sensor node. The distribution of targets and sensors in the monitoring area is shown in Figure4.Figure 4
Schematic diagram of target and sensor node distribution: (a) random distribution; (b) banded distribution; (c) spherical distribution.
(a)(b)(c)The population coding adopts a binary coding scheme, and theP matrix is obtained after the sensor monitoring node and the target position are successfully deployed. After adding constraints to the P matrix, i different Q matrices are generated, and each Q matrix is an individual frog.


## 3.2. The Fitness Function Design of BACSFLA

The fitness function plays an important role in BACSFLA. In EMWSN target coverage optimization, it is the core of optimized search. The choice of fitness function will directly affect the accuracy of the algorithm results and the final optimization results. This paper sets the target coverage rategSi in the network as the fitness function of BACSFLA and adopts the principle that the bigger the better. The calculation formula is shown in
(7)gSi=∑n=1N∑m=1Mqman,m≥hN.In equation (7), h is the minimum number of sensor monitoring nodes that the target is successfully covered, which balances network energy consumption and coverage accuracy. In this paper, h=3. Si is denoted as the ith frog in the population.


## 3.3. BACSFLA’s Intragroup Frog Update Operation

Determine the best and worst frogs in the group after BACSFLA grouping. There must be good or bad frogs in the group. The best frog in all subgroups is denoted asSj, the worst frog is denoted as So, and the best frog in the population is denoted as Sf. Improve the position of the worst frog, the worst frog So obtains the intermediate vector according to
(8)Temp=rand×Sj−So.In equation (8), Temp is the intermediate vector between the best frog Sj in the middle group and the worst frog So in the group. rand represents a random number, 0≤rand≤1. Then, a new frog is generated, which is obtained by
(9)Sonew=So+Temp,Tempmin≤Temp≤Tempmax.In equation (9), Tempmin is the minimum jump distance of the frog, and Tempmax is the maximum jump distance of the frog. The value of Temp must be between the two. If the value of Temp overflows, it will be processed according to
(10)Temp=Tempmin,Temp<Tempmin,Temp,Tempmin≤Temp≤Tempmax,Tempmax,Temp>Tempmax.In this process, the frog jumps to find a position better thanSo, and if it is found, it will update the worst frog, otherwise, proceed to the next step. Replace the best frog Sj in the subgroup with the best frog Sf in the subgroup. Repeat equations (8), (9), and (10), if you still cannot find a better position to improve the worst in the subgroup frog So, proceed to the next step. Generate a random frog, no matter the frog is good or bad, use it instead of So.


## 3.4. BACSFLA’s Low-Power Clone Selection Operation

After BACSFLA is updated within the group, the entire population is reordered according to fitness. The low-power clone selection operation first selects a certain number of individuals with adaptability from large to small and puts them into the clone warehouse. Assume that the number of frog individuals in the cloned warehouse isNUM. Therefore, the coverage of individual frogs in the warehouse must be greater than the coverage of the remaining unselected individuals. Then, calculate the energy consumption of individual frogs in the cloned warehouse, and the calculation of network energy consumption is shown in
(11)ECSi=∑m=1Mdt×ncelec+dt×εfs×ulm,rn2.In equation (11), dt represents the data size that the sensor monitoring node needs to send when monitoring the target. ncelec represents the energy consumption during data transmission. εfs is a parameter in the signal transmission process, set εfs=1. It can be seen that the closer the sensor monitoring node is to the target, the lower the network energy consumption. In this way, when the sensor node monitors the target, it will give priority to selecting the target close to itself, thereby reducing the energy consumption of the network communication of the entire EMWSNs.After calculating the network energy consumption of individual frogs in the cloned warehouse, sort them in ascending order of energy consumption. The smaller the energy consumption, the greater the proportion of cloned individuals. The clone ratio selection is shown in(12)rate1+⋯+ratenum+⋯+rateNUM=1.In equation (12), ratenum represents the proportion of the numth frog in the clone warehouse in the total population, rate1 represents the proportion of frogs with the smallest energy consumption, and rateNUM represents the proportion of frogs with the largest energy consumption proportion. According to the energy consumption of individual frogs corresponding to the clone ratio, the clone ratio satisfies
(13)rate1>rate2>⋯>ratenum>⋯>rateNUM.After selecting the new cloning ratio, the individual to be cloned is cloned according to the cloning ratio. After the cloning operation is completed, a new intermediate population is obtained. The degree of similarity of the intermediate population is too high to perform the global search performance of BACSFLA, so the next step is to perform an adaptive mutation operation.


## 3.5. Adaptive Mutation Operation of BACSFLA

After BACSFLA performs the low-power clone selection operation, it needs to perform adaptive mutation operations on the frogs in the population to obtain differentiated individuals. This operation is conducive to search in the vicinity of the global optimal solution, while ensuring that BACSFLA will not fall into the local optimal solution, increasing the diversity of the population, and has important significance for the rapid convergence of the algorithm.BACSFLA will adaptively change the mutation probabilityBR of the population. The size of the mutation probability is affected by the fitness of the individual, and it is also affected by the speed of convergence in the iterative process. If the fitness of the individual frog is to be mutated, and the coverage rate of the frog is small, the probability of mutation will increase. In the iterative process, if the fitness of the optimal frog individual relative to the previous generation does not increase much, or no better individual is found, the mutation probability will gradually increase, and the mutation probability will not decrease until a better individual is found. The formula for changing the adaptive mutation probability is shown in
(14)BR=1−gSi∑i=1IgSi+LRgen.In equation (14), LRgen represents the driving variation factor of BACSFLA iteration to the genth generation. The calculation formula is shown in
(15)LRgen=LRgen+δ,ggen−1Sf=ggenSf,0,ggen−1Sf<ggenSf,0,gen=1.In equation (15), δ is the increment of mutation probability, set δ=0.05. It can be seen from the update equation of BR that the probability of mutation is affected by two factors. If in the iterative process, the global optimal individual has not been updated, there may be two situations, either the optimal solution has been found or the locally optimal solution is trapped. At this time, it is necessary to increase the mutation probability of all individuals, increase the global optimization ability, and judge whether the optimal solution has been found. The fitness of an individual also affects the probability of individual mutation. The greater the fitness, the smaller the probability of individual mutation. When the fitness value of an individual is large, it proves that the coverage rate of the individual is large, so it is only necessary to find the optimal solution in the close range of the individual. If the fitness value of an individual is small, it proves that the individual is far from the optimal solution, so increases the probability of mutation and expands the search range of the solution.


## 4. Results and Discussion

This section will verify the performance of BACSFLA through simulation experiments and select GA and SA as the comparison algorithm. All nodes in EMWSNs are composed of static nodes, and all sensor nodes have omnidirectional sensors, and their perception model is a probabilistic perception model. This article carries on the experiment simulation under the environment of MATLAB R2019a, and the simulation platform is the Intel Core I7 processor. After multiple tests on BACSFLA parameters, the optimal value of each parameter was determined. The parameter values in the target coverage of EMWSNs are shown in Table1.Table 1
Simulation experiment parameter settings.
ParameterValuekla70 mkl100 mTempmax50Tempmin5dt4096 bitsncelec50 nJ/bitsIn Table1, the maximum jump distance Tempmax is set to 50, which means that the maximum number of changes in the sensor monitoring node perception relationship in the Q matrix each time the worst frog individual is updated is 50. The maximum jump distance Tempmin is set to 5, which means that each update cannot be less than 5 sensor monitoring nodes.The target coverage methods of BACSFLA, GA, and SA are used in the simulation, and the sensor monitoring nodes and target distribution are randomly distributed. The selection operation in GA adopts the roulette method, the crossover operation is a single point crossover, and the mutation probability is 0.05. The initial temperature in SA is set to 1000 degrees Celsius, the lower bound of the temperature is a number close to zero, and the temperature drop rate is 0.98. The number of individuals in the population is set to 50, where the number of subpopulations in BACSFLAI1=10, the number of frog individuals in each subpopulation I2=5, and the number of iterations within the group is 5. The number of targets N is 1000, and the number of sensor monitoring nodes is 700. The maximum number of targets that the sensor can monitor is H=5. When the monitoring area is 400m×400m×400m, 500m×500m×500m, 600m×600m×600m, and 700m×700m×700m, the simulation result curve is shown in Figure 5.Figure 5
Algorithm coverage curve in different monitoring areas: (a)400m×400m×400m; (b) 500m×500m×500m; (c) 600m×600m×600m; (d) 700m×700m×700m.
(a)(b)(c)(d)It can be seen from Figure5 that when the monitoring area changes, the coverage of BACSFLA and the comparison algorithm are both affected. When the number of sensor monitoring nodes and the number of targets remain unchanged, as the monitoring area increases, the coverage of GA and SA will decrease to a large extent, while the decrease of BACSFLA is not large. This result shows that BACSFLA has better performance than GA and SA when the dimensionality of the coverage problem increases. As the number of iterations of the algorithm increases, the coverage of BACSFLA, GA, and SA all increase rapidly at the beginning. However, the curve of SA tends to be flat in the subsequent optimization process, because SA’s global optimization performance is poor, and the algorithm falls into premature convergence during operation, and the solution obtained is the local optimal solution instead of the global optimal solution. The result of GA is better than that of SA, and the convergence speed and the final solution are greatly improved compared to SA. However, the optimization process of GA is slow, which is reflected in the curve, which is that although the coverage rate increases with the increase of the number of iterations, the increase is smaller. Compared with GA and SA, BACSFLA has a significant improvement in both the convergence speed and the final result. This is because the clone operator of BACSFLA increases the global search performance, and the adaptive algorithm increases the local search performance. Therefore, BACSFLA can obtain the optimal solution with a faster convergence rate. In the iterative process, each iteration of BACSFLA in the early stage of the operation will greatly improve the results, so better results can be obtained in the early stage of algorithm operation. After getting the optimal result, BACSFLA can terminate the algorithm iteration process early. The coverage rates of BACSFLA, GA, and SA in three-dimensional monitoring areas of different sizes are shown in Table 2.Table 2
The coverage of the three algorithms in different areas.
BACSFLAGASA400m×400m×400m92.3%90.4%88.8%500m×500m×500m92.8%90.0%87.4%600m×600m×600m90.8%88.4%87.4%700m×700m×700m91.3%87.4%86.2%It can be seen from Table2 that under the conditions of different monitoring areas and the same number of sensor nodes and targets, the coverage rate of BACSFLA is increased by 1.9% to 3.9% than that of GA and 3.4% to 5.4% than that of SA. Compared with the two-dimensional plane in the three-dimensional area, the complexity of the problem and the amount of calculation show an exponential increase. BACSFLA shows very good three-dimensional performance, and the optimal results can still be obtained in solving the covering problem. However, GA and SA cannot meet the performance requirements of EMWSNs facing the three-dimensional area and perform poorly in the process of solving the target coverage problem. The running time of the three algorithms is shown in Figure 6.Figure 6
The running time of the algorithm in different monitoring area sizes.It can be seen from Figure6 that the running time of the BACSFLA algorithm is shorter than that of GA and SA. This shows that while BACSFLA improves the coverage performance of EMWSNs, it does not increase the time complexity of the algorithm compared to the comparison algorithm. BACSFLA can show better coverage in a shorter time. In real-world applications, the performance of nodes and networks in EMWSNs is limited. BACSFLA can consume less computing power and get better results.It can be concluded from the results that monitoring areas of different sizes have a significant impact on BACSFLA. To analyze the influence of the number of sensor monitoring nodes and the number of targets on BACSFLA, the algorithm parameters will be adjusted next to obtain new simulation results. Set the monitoring area to be400m×400m×400m, and the maximum monitoring number of sensors H=7. The number of targets is 900, 100, 1100, and 1200. The number of sensor nodes is 800, 850, 900, and 950. The simulation results are shown in Figure 7.Figure 7
The influence of sensor monitoring node number and target number change on coverage: (a) targets 900; (b) targets 1000; (c) targets 1100; (d) targets 1200.
(a)(b)(c)(d)It can be seen from Figure7 that with the increase of sensor nodes, the coverage rates of BACSFLA, GA, and SA all increase. The degree of increase in BACSFLA is greater than that of GA and SA. Although the number of sensor monitoring nodes increases, the number of monitored targets in EMWSNs will increase. However, the number of calculations required by the algorithm in a three-dimensional environment will increase greatly. GA and SA are limited by algorithm performance and cannot make rational use of the added sensors. When facing a large number of sensors and targets, BACSFLA can give full play to the performance of the algorithm, reasonably allocate target coverage relationships, and improve coverage. Compared with GA and SA, BACSFLA has more complex problems, more sensor nodes, and more targets, the more obvious the performance advantage will be. In EMWSNs, the environment that needs to be monitored is often huge, which means that more targets need to be monitored and the number of sensor monitoring nodes deployed. However, BACSFLA’s excellent performance in handling a large number of nodes can meet the performance requirements of EMWSNs.Although coverage is an important performance parameter of EMWSNs, network energy consumption also has an important impact on EMWSNs. The energy consumption of EMWSNs when the monitoring area is400m×400m×400m, the number of sensor nodes is 800, and the target number is 900 and 1000 is shown in Table 3.Table 3
Network energy consumption in EMWSNs.
BACSFLAGASA900 target0.5870 J0.9173 J0.9163 J1000 target0.6169 J0.9095 J0.9077 JIt can be seen from Table3 that under the same conditions, the network energy consumption of BACSFLA is much smaller than that of GA and SA. The results show that the network energy consumption of BACSFLA is reduced by 36.0% compared with GA and 35.9% compared with SA. This is because BACSFLA’s low-power clone selection operator promotes sensor monitoring nodes to preferentially cover targets that are close in the iterative process. However, GA and SA only optimize the target coverage of EMWSNs without considering the size of network energy consumption. Although GA and SA can also complete the target coverage, the huge energy cost is not acceptable.The random distribution of node positions in EMWSNs can simulate most real-life scenarios. However, the target distribution in some areas will show certain rules. Therefore, this paper also adopts two distribution methods, belt-shaped distribution and spherical distribution, to simulate the environment in the real three-dimensional world. The parameter setting in the strip space is400m×300m×300m in the monitoring area. In the spherical space, the radius of the monitoring area is set to 200 m. The number of sensor monitoring nodes is 900, the target number is 1000, and the maximum number of sensors monitored is H=6. The simulation results are shown in Figure 8.Figure 8
The coverage results of the three algorithms under spherical and zonal distributions.It can be seen from Figure8 that compared with GA and SA, BACSFLA still has a higher target coverage after changing the distribution types of sensor monitoring nodes and targets. GA and SA are more affected under the band distribution, while the results of BACSFLA are better. This is because the adaptive operator of BACSFLA will quickly adjust the parameters of the algorithm when facing changes in the environment to obtain a higher coverage rate.


## 5. Conclusion

Coverage has always been a basic problem in the research of EMWSNs, and its purpose is to ensure a certain network performance while maximizing the target coverage as much as possible. Because the traditional 2D perception model and its corresponding target coverage algorithm are difficult to directly apply to the real 3D environment, this paper mainly studies the low-energy target coverage optimization problem of 3D EMWSN nodes. A low-power target coverage algorithm BACSFLA suitable for the three-dimensional physical world is proposed. In a static network, the performance pros and cons of BACSFLA, GA, and SA are discussed. The results show that BACSFLA has better performance than the comparison algorithm in terms of target coverage, algorithm running time, and network energy consumption. BACSFLA combines cloning operators and adaptive operators, which can better adapt to changes in external parameters and obtain better results. The individual uses a binary coding scheme, which greatly reduces the calculation time of the algorithm and reduces the time complexity. Through simulation experiments, BACSFLA has shown good performance advantages in three-dimensional space and has less network energy consumption while maintaining high coverage. These results show that BACSFLA has a very good application prospect in EMWSNs.However, the target coverage optimization method we proposed in this article has problems such as a small scale of sensor monitoring nodes and poor coordination among nodes. The design of distributed algorithms that are suitable for large-scale three-dimensional environments and cooperate among nodes can be used as the next research direction. Besides, the method proposed in this paper is static and immovable when the sensor monitors the node during the target coverage process. Future work can focus on moving the sensor to monitor the position of the node under dynamic conditions, balance the network energy consumption of EMWSNs, and extend the life of the network.



---

*Source: 4510335-2021-09-13.xml*