# Hybrid Strategy of Multiple Optimization Algorithms Applied to 3-D Terrain Node Coverage of Wireless Sensor Network

Authors: Li-Gang Zhang; Fang Fan; Shu-Chuan Chu; Akhil Garg; Jeng-Shyang Pan
Journal: Wireless Communications and Mobile Computing
 (2021)

---

## Abstract

The key to the problem of node coverage in wireless sensor networks (WSN) is to deploy a limited number of sensors to achieve maximum coverage. This paper studies the hybrid strategies of multiple evolutionary algorithms, and applies them to the problem of WSN node coverage. We first proposed the hybrid algorithm SFLA-WOA (SWOA) based on Shuffled Frog Leaping Algorithm (SFLA) and Whale Optimization Algorithm (WOA). The SWOA algorithm combines the advantages of SFLA and WOA; that is, it retains the unique evolution model of WOA and also has the excellent co-evolution capability of SFLA. Secondly, using the mutation, crossover and selection operations of the differential evolution (DE) algorithm to further optimize this hybrid algorithm, the SWOA-based SFLA-WOA-DE (SWOAD) algorithm is proposed. In addition, the performance of SWOA and SWOAD has been tested by 30 benchmark functions in the CEC 2017 test set. Experimental results show that the optimization effects of these two algorithms are very outstanding. Finally, the simulation results show that the optimization algorithm proposed in this paper has a good effect on improving the signal coverage of WSN under the actual three-dimensional terrain.


---

## Body

## 1. Introduction

The Internet of Things makes use of local area networks or the Internet and other means of communication to achieve the interconnection of people, machines and things so as to realize the intelligent management of items and real-time perception of the environment [1]. WSN is one of the core technologies of the Internet of Things. It is also an important product of the integration of the information industry (computing, communications and sensors) in the new era. It has received extensive attention from various countries and organizations, and has formulated relevant strategic policies. For example, the U.S. Science Foundation (NSF) has developed a WSN research program to support research on relevant fundamental theories. The EU’s sixth framework plan also emphasizes the importance of WSN and regards it as one of the hot areas for vigorous development in the future. Compared with traditional networks, WSN is low-cost, easy to deploy, has better fault tolerance and can be placed in any environment. The organizer can quickly build a fully functional WSN under limited time and conditions. Once the WSN has been set up, the maintenance and management work are carried out within the network and does not require much workforce. Therefore, the application field of WSN is very broad, and it can be used in military, modern industry and agriculture, environmental protection and other fields [2–4].The rapid development of artificial intelligence also brings a variety of problems, and traditional calculation methods cannot solve them well. Intelligent evolutionary algorithms came into being and developed rapidly. At present, various evolutionary algorithms have been proposed, such as Genetic Algorithm (GA) [5–7], DE [8–10], Particle Swarm Optimization (PSO) [11–13], Artificial Bee Colony (ABC) [14, 15], Multi-Verse Optimizer (MVO) [16, 17], Ant Lion Optimizer (ALO) [18], Grey wolf optimizer (GWO) [19], Cuckoo Search (CS) [20–22], Moth Flame Optimizer (MFO) [23, 24], Sine Cosine Algorithm (SCA) [25, 26], QUasi-Affine TRansformation Evolutionary (QUATRE) [27, 28], pigeon inspired optimization (PIO) [29, 30], Shuffled Frog Leaping Algorithm (SFLA) [31–35], Whale Optimization Algorithm (WOA) [36–39]. Meta-heuristic algorithms have received more and more attention from researchers due to their outstanding performance in solving optimization problems. They have been widely used in problems in transportation, wireless sensor networks, industrial production, intelligence system and other fields [40, 41]. But according to the No Free Lunch (NFL) theorem, there is no meta-heuristic algorithm that can be widely applied to various problems [42, 43]. In other words, optimization algorithms that achieve good performance on some problems may perform poorly on other problems. Therefore, new algorithms need to be proposed to solve increasingly complex problems. For example, propose a new heuristic algorithm, or improve the existing algorithm [44, 45], or combine two or more different algorithms to solve more complex problems [46, 47].WSN is a network system composed of sensor nodes with sensing capabilities deployed in the detection area, and communicate through wireless communication. This emerging technology has brought a new way to obtain information and control management. And because WSN itself is very different from traditional networks, it brings a lot of challenges to people. In WSN, signal coverage can be defined as the ratio of the perceptible area to the entire area. The question of how to maximize network coverage for a given number of sensors is an important one. Intelligent evolutionary algorithms are also increasingly used to improve the coverage of WSN signals. For example, an intelligent calculation algorithm for enhancing black holes is proposed and used to solve the node coverage problem of wireless sensor networks under three-dimensional terrain [48]. An artificial bee colony algorithm with dynamic search strategy is proposed to solve the deployment problem of three-dimensional surface sensors and improve the signal coverage [49]. A genetic algorithm-based network coverage and optimization control strategy is proposed to solve the coverage problem of sensor nodes in three-dimensional terrain [50]. Therefore, this article attempts to mix WOA and SFLA to improve the performance of the original algorithm, and to deal with the problem of node coverage in WSN under 3D actual terrain.The rest of this article is organized as follows. Related work introduced the principles of WOA, SFLA and DE, as well as the problem of WSN node coverage in a 3D actual environment. In Section3, the process of mixing WOA and SFLA and the steps of using DE to optimize the hybrid algorithm are introduced. In Section 4, the performance of the proposed algorithm is tested, and the performance of the algorithm on 30 test functions is shown and analyzed. Section 5 introduces the application of the algorithm in WSN node coverage under actual terrain. Finally, the conclusion is given in Section 6.


## 2. Related Work

This section briefly introduces the principles of WOA, SFLA and DE and the problem of node coverage in WSN under actual terrain.


### 2.1. WOA

Mirjalili et al. were inspired by the humpback whale’s spiral bubble net predation strategy and proposed a new heuristic whale optimization algorithm. WOA includes three location update models: encircling mode, bubble-net attacking mode, and searching mode. The WOA flowchart is shown in Figure1.Figure 1
WOA flowchart.


#### 2.1.1. Encircling Mode

In order to cooperate in predation, the whales share the location information of their prey, and then the whales approach the whale closest to the prey in the group. Update the current whaleX⟶ according to the whale with the best position, and the update equations are as follows:
(1)D⟶=C⟶∙X∗⟶t−X⟶t(2)X⟶t+1=X∗⟶t−A⟶∙D⟶Wheret represents the current iteration number, D⟶ has different expressions at different stages, X∗⟶ is the whale with the best position so far, X⟶t is the current whale position of the t-th generation, X⟶t+1 is the current whale position of the t+1-th generation, Operator ∙ means to multiply item by item, ∣∙∣ means to take the absolute value, A⟶ and C⟶ are coefficient vectors, The update equations of vectors A⟶ and C⟶ are as follows:
(3)A⟶=2a⟶∙r⟶−a⟶(4)C⟶=2∙r⟶(5)a=21−tTr⟶ is a random vector distributed in [0,1], a⟶ linearly decreases from 2 to 0 during the iteration process, so A⟶∈−2,2, C⟶∈0,2, T is the maximum number of iterations.
(1.1.1)
Bubble-Net Attacking ModeAccording to the spiral Equation (6), the current whale moves in a spiral motion to approach the prey and update its position.
(6)X⟶t+1=D′⟶∙ebl∙cos2πl+X∗⟶t(7)D′⟶=X∗⟶t−X⟶tD′⟶ denotes the distance between the current whale and the best positioned whale; b is a constant that defines the shape of a logarithmic spiral; and l is a uniformly distributed random number within [-1,1].When whales spirally search for prey, they also shrink their encirclement. In order to simulate this behavior, the encircling prey and spiral search will be performed with the same probability. The location update equation is as follows:(8)X⟶t+1=X∗⟶t−A⟶∙D⟶,ifp<0.5D′⟶∙ebl∙cos2πl+X∗⟶t,ifp≥0.5where p is a random number in the interval (0, 1).


#### 2.1.2. Random Searching Mode

In order to improve the global search capability of whales, the current whale position is updated according to the randomly selected whales during the exploration phase. When |A| <1, select the model that encircling; when |A| ≥1, select the model of random search. The random search location update equations are as follows:(9)D⟶=C⟶∙Xrand⟶−X⟶(10)X⟶t+1=Xrand⟶−A⟶∙D⟶Among themXrand⟶ is a whale randomly selected from the current population.


### 2.2. SFLA

SFLA is a collaborative optimization algorithm proposed by Eusuff and Lansey et al. The idea of the hybrid leapfrog algorithm: When frogs hunt for food, they adjust their position through information exchange. First, the entire frog population is divided into multiple memeplexes, and each memeplex executes a local search strategy to adjust the position of the worst frog. When the memeplex iterates to the specified number of times, the memeplexes are combined and exchanged for information. The process of local search and the process of global information exchange are carried out cyclically until the end condition is met. The following are the steps of the hybrid leapfrog algorithm:Step 1: Initialize the population and calculate the fitness value of each frog. Sort the population and record the individualPb with the best position.Step 2: The population containing F frogs is now divided into m memeplexes, so that there are n frogs in each memeplex, where n = F/m. If m =3, then the distribution principle is: the first frog is assigned to memeplex1, the second to memeplex2, the third to memeplex3, the fourth to memeplex1, ..., and so on.Step 3: The local search process of the hybrid leapfrog algorithm is shown in Figure2. Each memeplex evolves separately according to the following equations and Figure 2.
(11)Di=rand∗Pb−Pw(12)Pw′=Pw+Di,Dmax≥Di≥−Dmax(13)Di=rand∗Pg−Pwwhere Pb is the frog with the best position, Pw is the frog with the worst position, rand() is a random number in [0-1], Pw′ is the adjusted position of the frog with the worst position, and Pg represents the best frog in the m memeplexes.Figure 2
Local search flow chart of the hybrid leapfrog algorithm.Step 4: After each memeplex evolves individually, it is reorganized into a population containing F frogs. Sort F frogs according to fitness value and update Pb.Step 5: If the defined iteration conditions are met, the algorithm is terminated. Otherwise, go back to step 2.


### 2.3. De

The DE algorithm was proposed by Rainer Storn and Kenneth Price to solve the problem of Chebyshev polynomials. Differential evolution uses the three key operations of mutation, crossover and selection to continuously iterate to find the optimal value. First, the DE algorithm randomly selects several individuals in the population to perform mutation operations. Then crosses between the mutant individuals and the current individuals to obtain intermediates. Finally judges the pros and cons of the intermediates and the current individual, and selects individuals with good fitness values.The mutation operation is based on all individuals in the population. Randomly select several individuals, one of which is the basis vector, and the other individuals make difference with each other to form a difference vector to construct a mutation operation. There are several combinations of basis vector and difference vector as follows:(14)m=xr1t+fxr2t−xr3twhere r1, r2, and r3 are unequal integers distributed in [1, Np], Np is the number of individuals in the population, t represents the current iteration number, m is the newly generated variant individual, f is the scale parameter for adjusting the solution size range, f∈(0,1).The crossover operation is to exchange the values of the mutated individual and the current individual in certain dimensions to form a new individual. The equation for binomial crossover is as follows:(15)ui,j=yi,j,rand0,1≤pCRord=rand1,numelxxi,j,elsewhere pCR is the cross factor belonging to [0,1], rand∙ is the function of taking random values, d is the current dimension value, and numel∙ is the function of obtaining the total dimension of the individual.The selection operation selects individuals who can enter the next generation population. If the fitness value of the new individual after mutation and crossover is better than the fitness value of the current individual, replace the current individual with the new individual, otherwise, keep the current individual.


### 2.4. 3D WSN Node Coverage

WSN has broad application prospects, and it has become one of the hot research fields today. The improvement of signal coverage in WSN has always been an important issue. The measurement of the WSN coverage can understand whether there is a blind spot for monitoring and communication, and then the deployment position of the sensor can be adjusted or the number of sensors can be increased to improve the coverage of the sensor signal. The high deployment density of sensor nodes will result in higher network coverage, but it will also cause redundancy of network coverage, resulting in a great waste of resources. In the case of a fixed number of sensors, the proper deployment location of WSN nodes will have a direct impact on network performance. Optimizing the location of wireless sensor nodes can reasonably allocate network resources and better complete environmental perception. At present, the sensor coverage strategy in the two-dimensional plane has achieved more results, applied to the three-dimensional space of the sensor coverage strategy is also gradually attracting the attention of scholars. For example, Adda Boualem et al. proposed a spider web strategy and applied it to area coverage in 3D wireless sensor networks using mobile sensor nodes [51]. Yu Xiang et al. proposed 3D space detection and coverage of wireless sensor network based on spatial correlation [52].Deploying wireless sensors on an actual three-dimensional terrain rather than a two-dimensional plane requires additional considerations. Because the communication quality between the two sensors largely depends on the actual physical environment. Surrounding obstacles cause signal fading and obstruction. The communication process between sensorS1x1,y1,z1 and sensor S2x2,y2,z2 is shown in Figure 3. When the sensor S1 communicates with the sensor S2, the signal sent out is likely to be blocked by the protruding terrain between them, so that S1 and S2 will not be able to communicate, thereby reducing the coverage of the WSN signal. This paper uses Bresenham’s line of sight (LOS) algorithm to detect whether there is terrain obstruction between two sensors to affect their signal transmission [53]. In order to determine whether the communication between the target node S1 and the node S2 within the communication range is blocked, we choose the points between S1 and S2 on the actual terrain to make judgments. If the height of any one of the points is higher than the height of the connection between S1 and S2, the communication between S1 and S2 will be blocked, that is, the S1 node cannot communicate with the S2 node.Figure 3
The communication process between sensor S1 and sensor S2.So to judge whether two nodes can communicate, first calculate the Euclidean distanceDs between sensor S1 and sensor S2 according to Equation (16).
(16)Ds=x1−x22+y1−y22+z1−z22Then use the LOS algorithm to calculate whether there is an obstruction between the two sensors. Finally, a judgment is made according to Equation (17). If Ds is less than the coverage radius Rs of the sensor, and there is no obstruction between the two sensors, it means that they can communicate, and Communication (s1, s2) is equal to 1. Otherwise, if one of the conditions is not met, it is considered that sensor S1 and sensor S2 cannot communicate, and Communication (s1, s2) is equal to 0.
(17)Communications1,s2=1,Ds<RsandNoobstacle0,elseDs is the Euclidean distance between two sensors, and Rs is the coverage radius of the sensor signal.


## 2.1. WOA

Mirjalili et al. were inspired by the humpback whale’s spiral bubble net predation strategy and proposed a new heuristic whale optimization algorithm. WOA includes three location update models: encircling mode, bubble-net attacking mode, and searching mode. The WOA flowchart is shown in Figure1.Figure 1
WOA flowchart.


### 2.1.1. Encircling Mode

In order to cooperate in predation, the whales share the location information of their prey, and then the whales approach the whale closest to the prey in the group. Update the current whaleX⟶ according to the whale with the best position, and the update equations are as follows:
(1)D⟶=C⟶∙X∗⟶t−X⟶t(2)X⟶t+1=X∗⟶t−A⟶∙D⟶Wheret represents the current iteration number, D⟶ has different expressions at different stages, X∗⟶ is the whale with the best position so far, X⟶t is the current whale position of the t-th generation, X⟶t+1 is the current whale position of the t+1-th generation, Operator ∙ means to multiply item by item, ∣∙∣ means to take the absolute value, A⟶ and C⟶ are coefficient vectors, The update equations of vectors A⟶ and C⟶ are as follows:
(3)A⟶=2a⟶∙r⟶−a⟶(4)C⟶=2∙r⟶(5)a=21−tTr⟶ is a random vector distributed in [0,1], a⟶ linearly decreases from 2 to 0 during the iteration process, so A⟶∈−2,2, C⟶∈0,2, T is the maximum number of iterations.
(1.1.1)
Bubble-Net Attacking ModeAccording to the spiral Equation (6), the current whale moves in a spiral motion to approach the prey and update its position.
(6)X⟶t+1=D′⟶∙ebl∙cos2πl+X∗⟶t(7)D′⟶=X∗⟶t−X⟶tD′⟶ denotes the distance between the current whale and the best positioned whale; b is a constant that defines the shape of a logarithmic spiral; and l is a uniformly distributed random number within [-1,1].When whales spirally search for prey, they also shrink their encirclement. In order to simulate this behavior, the encircling prey and spiral search will be performed with the same probability. The location update equation is as follows:(8)X⟶t+1=X∗⟶t−A⟶∙D⟶,ifp<0.5D′⟶∙ebl∙cos2πl+X∗⟶t,ifp≥0.5where p is a random number in the interval (0, 1).


### 2.1.2. Random Searching Mode

In order to improve the global search capability of whales, the current whale position is updated according to the randomly selected whales during the exploration phase. When |A| <1, select the model that encircling; when |A| ≥1, select the model of random search. The random search location update equations are as follows:(9)D⟶=C⟶∙Xrand⟶−X⟶(10)X⟶t+1=Xrand⟶−A⟶∙D⟶Among themXrand⟶ is a whale randomly selected from the current population.


## 2.1.1. Encircling Mode

In order to cooperate in predation, the whales share the location information of their prey, and then the whales approach the whale closest to the prey in the group. Update the current whaleX⟶ according to the whale with the best position, and the update equations are as follows:
(1)D⟶=C⟶∙X∗⟶t−X⟶t(2)X⟶t+1=X∗⟶t−A⟶∙D⟶Wheret represents the current iteration number, D⟶ has different expressions at different stages, X∗⟶ is the whale with the best position so far, X⟶t is the current whale position of the t-th generation, X⟶t+1 is the current whale position of the t+1-th generation, Operator ∙ means to multiply item by item, ∣∙∣ means to take the absolute value, A⟶ and C⟶ are coefficient vectors, The update equations of vectors A⟶ and C⟶ are as follows:
(3)A⟶=2a⟶∙r⟶−a⟶(4)C⟶=2∙r⟶(5)a=21−tTr⟶ is a random vector distributed in [0,1], a⟶ linearly decreases from 2 to 0 during the iteration process, so A⟶∈−2,2, C⟶∈0,2, T is the maximum number of iterations.
(1.1.1)
Bubble-Net Attacking ModeAccording to the spiral Equation (6), the current whale moves in a spiral motion to approach the prey and update its position.
(6)X⟶t+1=D′⟶∙ebl∙cos2πl+X∗⟶t(7)D′⟶=X∗⟶t−X⟶tD′⟶ denotes the distance between the current whale and the best positioned whale; b is a constant that defines the shape of a logarithmic spiral; and l is a uniformly distributed random number within [-1,1].When whales spirally search for prey, they also shrink their encirclement. In order to simulate this behavior, the encircling prey and spiral search will be performed with the same probability. The location update equation is as follows:(8)X⟶t+1=X∗⟶t−A⟶∙D⟶,ifp<0.5D′⟶∙ebl∙cos2πl+X∗⟶t,ifp≥0.5where p is a random number in the interval (0, 1).


## 2.1.2. Random Searching Mode

In order to improve the global search capability of whales, the current whale position is updated according to the randomly selected whales during the exploration phase. When |A| <1, select the model that encircling; when |A| ≥1, select the model of random search. The random search location update equations are as follows:(9)D⟶=C⟶∙Xrand⟶−X⟶(10)X⟶t+1=Xrand⟶−A⟶∙D⟶Among themXrand⟶ is a whale randomly selected from the current population.


## 2.2. SFLA

SFLA is a collaborative optimization algorithm proposed by Eusuff and Lansey et al. The idea of the hybrid leapfrog algorithm: When frogs hunt for food, they adjust their position through information exchange. First, the entire frog population is divided into multiple memeplexes, and each memeplex executes a local search strategy to adjust the position of the worst frog. When the memeplex iterates to the specified number of times, the memeplexes are combined and exchanged for information. The process of local search and the process of global information exchange are carried out cyclically until the end condition is met. The following are the steps of the hybrid leapfrog algorithm:Step 1: Initialize the population and calculate the fitness value of each frog. Sort the population and record the individualPb with the best position.Step 2: The population containing F frogs is now divided into m memeplexes, so that there are n frogs in each memeplex, where n = F/m. If m =3, then the distribution principle is: the first frog is assigned to memeplex1, the second to memeplex2, the third to memeplex3, the fourth to memeplex1, ..., and so on.Step 3: The local search process of the hybrid leapfrog algorithm is shown in Figure2. Each memeplex evolves separately according to the following equations and Figure 2.
(11)Di=rand∗Pb−Pw(12)Pw′=Pw+Di,Dmax≥Di≥−Dmax(13)Di=rand∗Pg−Pwwhere Pb is the frog with the best position, Pw is the frog with the worst position, rand() is a random number in [0-1], Pw′ is the adjusted position of the frog with the worst position, and Pg represents the best frog in the m memeplexes.Figure 2
Local search flow chart of the hybrid leapfrog algorithm.Step 4: After each memeplex evolves individually, it is reorganized into a population containing F frogs. Sort F frogs according to fitness value and update Pb.Step 5: If the defined iteration conditions are met, the algorithm is terminated. Otherwise, go back to step 2.


## 2.3. De

The DE algorithm was proposed by Rainer Storn and Kenneth Price to solve the problem of Chebyshev polynomials. Differential evolution uses the three key operations of mutation, crossover and selection to continuously iterate to find the optimal value. First, the DE algorithm randomly selects several individuals in the population to perform mutation operations. Then crosses between the mutant individuals and the current individuals to obtain intermediates. Finally judges the pros and cons of the intermediates and the current individual, and selects individuals with good fitness values.The mutation operation is based on all individuals in the population. Randomly select several individuals, one of which is the basis vector, and the other individuals make difference with each other to form a difference vector to construct a mutation operation. There are several combinations of basis vector and difference vector as follows:(14)m=xr1t+fxr2t−xr3twhere r1, r2, and r3 are unequal integers distributed in [1, Np], Np is the number of individuals in the population, t represents the current iteration number, m is the newly generated variant individual, f is the scale parameter for adjusting the solution size range, f∈(0,1).The crossover operation is to exchange the values of the mutated individual and the current individual in certain dimensions to form a new individual. The equation for binomial crossover is as follows:(15)ui,j=yi,j,rand0,1≤pCRord=rand1,numelxxi,j,elsewhere pCR is the cross factor belonging to [0,1], rand∙ is the function of taking random values, d is the current dimension value, and numel∙ is the function of obtaining the total dimension of the individual.The selection operation selects individuals who can enter the next generation population. If the fitness value of the new individual after mutation and crossover is better than the fitness value of the current individual, replace the current individual with the new individual, otherwise, keep the current individual.


## 2.4. 3D WSN Node Coverage

WSN has broad application prospects, and it has become one of the hot research fields today. The improvement of signal coverage in WSN has always been an important issue. The measurement of the WSN coverage can understand whether there is a blind spot for monitoring and communication, and then the deployment position of the sensor can be adjusted or the number of sensors can be increased to improve the coverage of the sensor signal. The high deployment density of sensor nodes will result in higher network coverage, but it will also cause redundancy of network coverage, resulting in a great waste of resources. In the case of a fixed number of sensors, the proper deployment location of WSN nodes will have a direct impact on network performance. Optimizing the location of wireless sensor nodes can reasonably allocate network resources and better complete environmental perception. At present, the sensor coverage strategy in the two-dimensional plane has achieved more results, applied to the three-dimensional space of the sensor coverage strategy is also gradually attracting the attention of scholars. For example, Adda Boualem et al. proposed a spider web strategy and applied it to area coverage in 3D wireless sensor networks using mobile sensor nodes [51]. Yu Xiang et al. proposed 3D space detection and coverage of wireless sensor network based on spatial correlation [52].Deploying wireless sensors on an actual three-dimensional terrain rather than a two-dimensional plane requires additional considerations. Because the communication quality between the two sensors largely depends on the actual physical environment. Surrounding obstacles cause signal fading and obstruction. The communication process between sensorS1x1,y1,z1 and sensor S2x2,y2,z2 is shown in Figure 3. When the sensor S1 communicates with the sensor S2, the signal sent out is likely to be blocked by the protruding terrain between them, so that S1 and S2 will not be able to communicate, thereby reducing the coverage of the WSN signal. This paper uses Bresenham’s line of sight (LOS) algorithm to detect whether there is terrain obstruction between two sensors to affect their signal transmission [53]. In order to determine whether the communication between the target node S1 and the node S2 within the communication range is blocked, we choose the points between S1 and S2 on the actual terrain to make judgments. If the height of any one of the points is higher than the height of the connection between S1 and S2, the communication between S1 and S2 will be blocked, that is, the S1 node cannot communicate with the S2 node.Figure 3
The communication process between sensor S1 and sensor S2.So to judge whether two nodes can communicate, first calculate the Euclidean distanceDs between sensor S1 and sensor S2 according to Equation (16).
(16)Ds=x1−x22+y1−y22+z1−z22Then use the LOS algorithm to calculate whether there is an obstruction between the two sensors. Finally, a judgment is made according to Equation (17). If Ds is less than the coverage radius Rs of the sensor, and there is no obstruction between the two sensors, it means that they can communicate, and Communication (s1, s2) is equal to 1. Otherwise, if one of the conditions is not met, it is considered that sensor S1 and sensor S2 cannot communicate, and Communication (s1, s2) is equal to 0.
(17)Communications1,s2=1,Ds<RsandNoobstacle0,elseDs is the Euclidean distance between two sensors, and Rs is the coverage radius of the sensor signal.


## 3. Hybrid Strategy of SWOA and SWOAD

This section introduces the mixing process of WOA and SFLA, and the steps to optimize the mixing algorithm with DE.


### 3.1. Hybrid Strategy of SWOA

The WOA algorithm is a new type of bionic optimization algorithm with strong global optimization performance. However, in the later stage of the algorithm iteration, it still has the disadvantage of being easy to fall into the local optimal value, so the solution accuracy is low. The SFLA algorithm can realize global information exchange through the combination and sorting of memeplexes, so that the algorithm avoids falling into local convergence, but the early search speed is slow. The above shortcomings of the algorithm can be effectively solved by combining the WOA algorithm and the SFLA algorithm. The flow chart of SWOA algorithm is shown as in Figure4.Figure 4
SWOA flow chart.SWOA’s pseudo code is in Algorithm1.Algorithm 1: SWOA.
Initialize parameters; M is the number of memeplex; ne is the number of iterations for each memeplex; Iter is the maximum number of iterations.for1 g =1: Iter do.Calculate the fitness value of each whale.Sort individuals by fitness value.Define memeplex, divide the population into M memeplexes.for2 each memeplex do.for3 n =1:Ne do.Update global optimal value.for4 each solution do.for5 each dimension do.Update Memeplex by equation (1) to equation (9).End for5.End for4.End for3.Combine M memes into a population.End for2.End for1.


### 3.2. Hybrid Strategy of SWOAD

The SWOAD algorithm integrates the differential evolution algorithm into the SWOA algorithm, so that the whale population has a mechanism of mutation, crossover, and selection, which in turn enables SWOA to have stronger search capabilities. After each iteration of SWOA, the SWOAD algorithm first randomly selects a whale individual as the basis vector, and then combines with the difference between two randomly selected whale individuals to complete the mutation. Whether in the early or late stage of algorithm iteration, this strategy can enhance the ability of whales to jump out of the local optimum. Then the mutant intermediates are crossed with the target whale individuals, thereby increasing the diversity of the whale population; finally, a selection is made. If the fitness value of the newly generated individual is better than the target individual, the newly generated individual will replace the target individual. Otherwise, keep the target individual. SWOAD execution steps are as follows:Step 1. Calculate the fitness of each individual.Step 2. Sort the populations by fitness.Step 3. According to the division rule, the population is decomposed into multiple memeplexes.Step 4. Each memeplex evolves individually.Step 4.1. Calculate the fitness value of each individual and Update global optimal value.Step 4.2. Update the position of each frog by Equation (1) to Equation (10).Step 4.3. Repeat 4.1–4.2 until the end conditions of the local search are met.Step 5. Combine memeplexes.Step 6. Performing variation, crossover and selection operations.Step 7. Repeat step 1 to 6 until the end conditions are met.The pseudo code of step 6 is in Algorithm2.Algorithm 2: DE pseudo code for step 6.
for1 each solution do.Generate variant intermediates Y by Equation (14).The current solution is X.for2 each dimension of Y do.Generate new individuals U by Equation (15).End for2.if2 fitness(U) < fitness(X).X = U.End if2.End for1.


## 3.1. Hybrid Strategy of SWOA

The WOA algorithm is a new type of bionic optimization algorithm with strong global optimization performance. However, in the later stage of the algorithm iteration, it still has the disadvantage of being easy to fall into the local optimal value, so the solution accuracy is low. The SFLA algorithm can realize global information exchange through the combination and sorting of memeplexes, so that the algorithm avoids falling into local convergence, but the early search speed is slow. The above shortcomings of the algorithm can be effectively solved by combining the WOA algorithm and the SFLA algorithm. The flow chart of SWOA algorithm is shown as in Figure4.Figure 4
SWOA flow chart.SWOA’s pseudo code is in Algorithm1.Algorithm 1: SWOA.
Initialize parameters; M is the number of memeplex; ne is the number of iterations for each memeplex; Iter is the maximum number of iterations.for1 g =1: Iter do.Calculate the fitness value of each whale.Sort individuals by fitness value.Define memeplex, divide the population into M memeplexes.for2 each memeplex do.for3 n =1:Ne do.Update global optimal value.for4 each solution do.for5 each dimension do.Update Memeplex by equation (1) to equation (9).End for5.End for4.End for3.Combine M memes into a population.End for2.End for1.


## 3.2. Hybrid Strategy of SWOAD

The SWOAD algorithm integrates the differential evolution algorithm into the SWOA algorithm, so that the whale population has a mechanism of mutation, crossover, and selection, which in turn enables SWOA to have stronger search capabilities. After each iteration of SWOA, the SWOAD algorithm first randomly selects a whale individual as the basis vector, and then combines with the difference between two randomly selected whale individuals to complete the mutation. Whether in the early or late stage of algorithm iteration, this strategy can enhance the ability of whales to jump out of the local optimum. Then the mutant intermediates are crossed with the target whale individuals, thereby increasing the diversity of the whale population; finally, a selection is made. If the fitness value of the newly generated individual is better than the target individual, the newly generated individual will replace the target individual. Otherwise, keep the target individual. SWOAD execution steps are as follows:Step 1. Calculate the fitness of each individual.Step 2. Sort the populations by fitness.Step 3. According to the division rule, the population is decomposed into multiple memeplexes.Step 4. Each memeplex evolves individually.Step 4.1. Calculate the fitness value of each individual and Update global optimal value.Step 4.2. Update the position of each frog by Equation (1) to Equation (10).Step 4.3. Repeat 4.1–4.2 until the end conditions of the local search are met.Step 5. Combine memeplexes.Step 6. Performing variation, crossover and selection operations.Step 7. Repeat step 1 to 6 until the end conditions are met.The pseudo code of step 6 is in Algorithm2.Algorithm 2: DE pseudo code for step 6.
for1 each solution do.Generate variant intermediates Y by Equation (14).The current solution is X.for2 each dimension of Y do.Generate new individuals U by Equation (15).End for2.if2 fitness(U) < fitness(X).X = U.End if2.End for1.


## 4. Results and Analysis of the Experiment

In this section, we use 30 benchmark functions in CEC2017 to test the effectiveness of the proposed hybrid algorithm.


### 4.1. Parameter Configuration

To verify the results, we compared the hybrid algorithm with the original WOA and SFLA algorithms. Each algorithm performs 100 iterations on each benchmark function, and runs 30 times to average. The test parameters of the algorithm are given in Table1. Table 2 shows the statistical results of the algorithm, including the mean (Mean) and standard deviation (Std).Table 1
Parameter settings for each related algorithm.
NameParameterWOANp =40, Lb = -100, Ub =100, dim =30SFLANp =40, Lb = -100, Ub =100, dim =30, Memeplex =5, M_it =25, Smax =10SWOANp =40, Lb = -100, Ub =100, dim =30, Memeplex =5, M_it =25SWOADNp =40, Lb = -100, Ub =100, dim =30, Memeplex =5, M_it =25, Beta_min =0.02, Beta_max =0.08, pCR =0.01Table 2
Simulation Results of CEC 2017 Benchmark Function (The optimal value is marked by bold).
FunctionsWOASFLASWOASWOADVariableMeanStdMeanStdMeanStdMeanStdF12.14E+105.14E+096.46E+108.46E+098.95E+092.81E+092.85E+091.58E+09F23.12E+401.60E+414.97E+472.25E+481.72E+334.16E+331.08E+334.77E+33F32.68E+057.76E+041.87E+054.61E+041.97E+053.72E+041.52E+054.59E+04F44.84E+031.82E+033.12E+046.43E+031.42E+035.37E+028.72E+023.60E+02F59.16E+025.80E+019.62E+024.06E+018.00E+023.15E+017.65E+023.45E+01F66.88E+021.12E+016.97E+029.89E+006.70E+027.91E+006.59E+026.88E+00F71.40E+038.81E+011.89E+031.83E+021.27E+035.11E+011.22E+037.31E+01F81.11E+033.91E+011.15E+034.21E+011.03E+032.08E+019.91E+022.85E+01F91.45E+045.55E+031.49E+042.65E+037.78E+031.04E+036.63E+031.07E+03F108.34E+036.47E+028.07E+035.23E+026.75E+035.56E+025.98E+035.56E+02F111.76E+048.70E+031.63E+044.40E+034.89E+031.38E+033.23E+039.94E+02F121.82E+098.98E+081.91E+104.74E+094.31E+083.41E+089.43E+076.22E+07F132.83E+082.26E+082.07E+106.73E+094.62E+061.05E+074.54E+062.30E+07F143.52E+062.91E+061.13E+071.35E+075.45E+054.64E+057.12E+058.59E+05F154.11E+073.90E+071.68E+091.10E+092.08E+062.18E+063.65E+056.58E+05F164.68E+035.52E+025.41E+037.09E+023.65E+033.80E+023.39E+033.46E+02F173.07E+033.16E+023.85E+031.43E+032.51E+032.21E+022.37E+032.05E+02F183.96E+073.87E+075.77E+075.76E+072.96E+063.22E+061.87E+062.24E+06F195.74E+074.26E+072.48E+091.96E+096.32E+068.39E+069.67E+051.06E+06F203.02E+032.58E+023.18E+031.21E+022.69E+031.22E+022.67E+031.87E+02F212.70E+035.99E+012.80E+035.35E+012.58E+033.15E+012.55E+034.12E+01F229.08E+031.39E+039.73E+034.48E+026.25E+031.85E+036.31E+031.84E+03F233.24E+031.18E+023.54E+031.08E+023.08E+034.33E+013.05E+038.38E+01F243.35E+039.93E+013.86E+031.88E+023.18E+036.77E+013.14E+037.70E+01F253.77E+032.42E+029.46E+031.48E+033.25E+031.17E+023.09E+037.33E+01F269.34E+039.83E+021.04E+048.53E+027.67E+031.05E+037.05E+031.18E+03F273.61E+031.82E+024.62E+033.50E+023.38E+036.44E+013.35E+037.44E+01F285.02E+035.02E+029.78E+031.68E+033.92E+032.52E+023.56E+031.46E+02F295.88E+037.14E+026.76E+031.24E+034.80E+033.66E+024.60E+032.69E+02F301.70E+081.24E+081.77E+099.80E+082.36E+071.52E+076.78E+064.89E+06From the data in the table, it can be seen that SWOA and SWOAD perform better than the original WOA and SFLA on the 30 test functions. SWOA performs better on functions F14 and F22, and SWOAD performs better on other functions. WOA has stability in function F22, SFLA has better stability in functions F10 and F20, SWOAD has excellent stability in function F1, F4, F6, F11, F12, F15, F16, F17, F18, F19, F25, F28, F29 and F30, and SWOA is more stable in other functions.In order to further evaluate the performance of the algorithm, we use the convergence curve of the algorithm to evaluate the convergence speed and convergence ability of the optimized algorithm in this paper. The iterative curves of the algorithm on 30 test functions are shown in Figure5–8. All algorithms have the same number of iterations on each function. The horizontal axis is the number of iterations of the function, and the vertical axis is the average of the fitness values of each function running 30 times.Figure 5
Convergence curves of unimodal functions.
(a)
F1(b)
F2(c)
F3Figure 6
Convergence curves of simple multimodal functions.
(a)
F4(b)
F5(c)
F6(d)
F7(e)
F8(f)
F9(g)
F10Figure 7
Convergence curves of hybrid functions.
(a)
F11(b)
F12(c)
F13(d)
F14(e)
F15(f)
F16(g)
F17(h)
F18(i)
F19(j)
F20Figure 8
Convergence curves of composition functions.
(a)
F21(b)
F22(c)
F23(d)
F24(e)
F25(f)
F26(g)
F27(h)
F28(i)
F29(j)
F30


### 4.2. Unimodal Functions

In Figure5, SWOAD’s convergence ability on function F1 is better than other algorithms. Each algorithm can find the optimal value on the function F2 and F3, but the improved two algorithms converge faster than the original algorithm.


### 4.3. Simple Multimodal Functions

In Figure6, the SWOAD algorithm has a faster convergence speed and stronger optimization ability than the WOA, SFLA and SWOA algorithms. The performance of SFLA in function F10 is better than that of WOA.


### 4.4. Hybrid Functions

In Figure7, the convergence curves of SWOA and SWOAD on the function F13, F14, F15, F18 and F19 have very little difference. But the convergence performance of SWOAD on functions F11, F16, F17 and F20 are significantly better than SWOA. The performance of SFLA in function F11 is better than that of WOA.


### 4.5. Composition Functions

In Figure8, the convergence results of SWOA and SWOAD are almost the same in F22 and F30. Among other functions, SWOAD has the best performance, followed by SWOA, which is better than WOA and SFLA.


## 4.1. Parameter Configuration

To verify the results, we compared the hybrid algorithm with the original WOA and SFLA algorithms. Each algorithm performs 100 iterations on each benchmark function, and runs 30 times to average. The test parameters of the algorithm are given in Table1. Table 2 shows the statistical results of the algorithm, including the mean (Mean) and standard deviation (Std).Table 1
Parameter settings for each related algorithm.
NameParameterWOANp =40, Lb = -100, Ub =100, dim =30SFLANp =40, Lb = -100, Ub =100, dim =30, Memeplex =5, M_it =25, Smax =10SWOANp =40, Lb = -100, Ub =100, dim =30, Memeplex =5, M_it =25SWOADNp =40, Lb = -100, Ub =100, dim =30, Memeplex =5, M_it =25, Beta_min =0.02, Beta_max =0.08, pCR =0.01Table 2
Simulation Results of CEC 2017 Benchmark Function (The optimal value is marked by bold).
FunctionsWOASFLASWOASWOADVariableMeanStdMeanStdMeanStdMeanStdF12.14E+105.14E+096.46E+108.46E+098.95E+092.81E+092.85E+091.58E+09F23.12E+401.60E+414.97E+472.25E+481.72E+334.16E+331.08E+334.77E+33F32.68E+057.76E+041.87E+054.61E+041.97E+053.72E+041.52E+054.59E+04F44.84E+031.82E+033.12E+046.43E+031.42E+035.37E+028.72E+023.60E+02F59.16E+025.80E+019.62E+024.06E+018.00E+023.15E+017.65E+023.45E+01F66.88E+021.12E+016.97E+029.89E+006.70E+027.91E+006.59E+026.88E+00F71.40E+038.81E+011.89E+031.83E+021.27E+035.11E+011.22E+037.31E+01F81.11E+033.91E+011.15E+034.21E+011.03E+032.08E+019.91E+022.85E+01F91.45E+045.55E+031.49E+042.65E+037.78E+031.04E+036.63E+031.07E+03F108.34E+036.47E+028.07E+035.23E+026.75E+035.56E+025.98E+035.56E+02F111.76E+048.70E+031.63E+044.40E+034.89E+031.38E+033.23E+039.94E+02F121.82E+098.98E+081.91E+104.74E+094.31E+083.41E+089.43E+076.22E+07F132.83E+082.26E+082.07E+106.73E+094.62E+061.05E+074.54E+062.30E+07F143.52E+062.91E+061.13E+071.35E+075.45E+054.64E+057.12E+058.59E+05F154.11E+073.90E+071.68E+091.10E+092.08E+062.18E+063.65E+056.58E+05F164.68E+035.52E+025.41E+037.09E+023.65E+033.80E+023.39E+033.46E+02F173.07E+033.16E+023.85E+031.43E+032.51E+032.21E+022.37E+032.05E+02F183.96E+073.87E+075.77E+075.76E+072.96E+063.22E+061.87E+062.24E+06F195.74E+074.26E+072.48E+091.96E+096.32E+068.39E+069.67E+051.06E+06F203.02E+032.58E+023.18E+031.21E+022.69E+031.22E+022.67E+031.87E+02F212.70E+035.99E+012.80E+035.35E+012.58E+033.15E+012.55E+034.12E+01F229.08E+031.39E+039.73E+034.48E+026.25E+031.85E+036.31E+031.84E+03F233.24E+031.18E+023.54E+031.08E+023.08E+034.33E+013.05E+038.38E+01F243.35E+039.93E+013.86E+031.88E+023.18E+036.77E+013.14E+037.70E+01F253.77E+032.42E+029.46E+031.48E+033.25E+031.17E+023.09E+037.33E+01F269.34E+039.83E+021.04E+048.53E+027.67E+031.05E+037.05E+031.18E+03F273.61E+031.82E+024.62E+033.50E+023.38E+036.44E+013.35E+037.44E+01F285.02E+035.02E+029.78E+031.68E+033.92E+032.52E+023.56E+031.46E+02F295.88E+037.14E+026.76E+031.24E+034.80E+033.66E+024.60E+032.69E+02F301.70E+081.24E+081.77E+099.80E+082.36E+071.52E+076.78E+064.89E+06From the data in the table, it can be seen that SWOA and SWOAD perform better than the original WOA and SFLA on the 30 test functions. SWOA performs better on functions F14 and F22, and SWOAD performs better on other functions. WOA has stability in function F22, SFLA has better stability in functions F10 and F20, SWOAD has excellent stability in function F1, F4, F6, F11, F12, F15, F16, F17, F18, F19, F25, F28, F29 and F30, and SWOA is more stable in other functions.In order to further evaluate the performance of the algorithm, we use the convergence curve of the algorithm to evaluate the convergence speed and convergence ability of the optimized algorithm in this paper. The iterative curves of the algorithm on 30 test functions are shown in Figure5–8. All algorithms have the same number of iterations on each function. The horizontal axis is the number of iterations of the function, and the vertical axis is the average of the fitness values of each function running 30 times.Figure 5
Convergence curves of unimodal functions.
(a)
F1(b)
F2(c)
F3Figure 6
Convergence curves of simple multimodal functions.
(a)
F4(b)
F5(c)
F6(d)
F7(e)
F8(f)
F9(g)
F10Figure 7
Convergence curves of hybrid functions.
(a)
F11(b)
F12(c)
F13(d)
F14(e)
F15(f)
F16(g)
F17(h)
F18(i)
F19(j)
F20Figure 8
Convergence curves of composition functions.
(a)
F21(b)
F22(c)
F23(d)
F24(e)
F25(f)
F26(g)
F27(h)
F28(i)
F29(j)
F30


## 4.2. Unimodal Functions

In Figure5, SWOAD’s convergence ability on function F1 is better than other algorithms. Each algorithm can find the optimal value on the function F2 and F3, but the improved two algorithms converge faster than the original algorithm.


## 4.3. Simple Multimodal Functions

In Figure6, the SWOAD algorithm has a faster convergence speed and stronger optimization ability than the WOA, SFLA and SWOA algorithms. The performance of SFLA in function F10 is better than that of WOA.


## 4.4. Hybrid Functions

In Figure7, the convergence curves of SWOA and SWOAD on the function F13, F14, F15, F18 and F19 have very little difference. But the convergence performance of SWOAD on functions F11, F16, F17 and F20 are significantly better than SWOA. The performance of SFLA in function F11 is better than that of WOA.


## 4.5. Composition Functions

In Figure8, the convergence results of SWOA and SWOAD are almost the same in F22 and F30. Among other functions, SWOAD has the best performance, followed by SWOA, which is better than WOA and SFLA.


## 5. Application of Hybrid Algorithm in WSN Node Coverage under Real Terrain

The 3-D actual terrain used in this simulation is the Dagong Island in Qingdao. Obtain topographic data of Dagong Island through satellite maps, and collect information about a coordinate point every ten meters in a prescribed area. The sensor nodes are deployed on this 3-D terrain. The terrain of Dagong Island is shown in Figure9. When the simulation is performed on the actual terrain of Dagong Island, the initial sensor nodes are randomly generated and optimized by hybrid algorithms to find a better position. To randomly generate the position of a sensor node, only the horizontal and vertical coordinates of the sensor node need to be randomly generated, and use the following method to determine the height through the available terrain data: If the randomly generated or optimized sensor node is at the intersection of the horizontal and vertical grid lines, the height value in the corresponding terrain data is the height of the sensor; Otherwise, the height of the grid intersection closest to this position is the height of the sensor node.Figure 9
Topographic map of Dagong Island (unit is 10 meters).Set a matrix CMat, and determine the coordinate points that each sensor can cover by Equation (17), and set the coordinate points that the sensor can cover in CMat to 1. Calculate the coverage rate according to Equation (18).
(18)Rate=sumCMat:==1/Xl∗Ylwhere sum∙ is a sum function, Xl and Yl are horizontal and vertical coordinate lengths, respectively.Use the hybrid algorithm in this paper to optimize the position of the sensor, and improve the signal coverage as much as possible on the premise of a fixed number of sensors. The communication radius of the sensor is set to 5 m. Test the algorithm with 30, 40, 50, and 60 nodes, respectively. Run 30 times for each group of nodes and take the average. The results of the experiment are shown in Table3. As the number of sensor nodes increases, the signal coverage also increases, and the coverage rate is the largest when 60 sensor nodes are deployed, reaching 82.56%. It can also be seen that the hybrid algorithm is far superior to the performance of WOA and SFLA.Table 3
Simulation Results of WSN node coverage (The optimal value is marked by bold).
Node numberAlgorithmWOASFLASWOASWOAD300.51320.55830.57600.5895400.60260.66210.67650.6884500.66970.74280.75190.7658600.74260.80120.81300.8256


## 6. Conclusion

In this paper, WOA and SFLA are combined to form a new hybrid algorithm. The two algorithms cooperate with each other to form an organic whole. Compared with the performance of the two algorithms alone, the performance of the hybrid algorithm is better. Through mutual fusion, the algorithm can avoid falling into the local optimum in the process of finding the global optimum. And use DE to optimize the hybrid algorithm, which further improves the algorithm’s convergence speed and optimization ability. In the experiments tested using the CEC 2017 benchmark function, the hybrid algorithm outperformed both WOA and SFLA. Finally, the hybrid algorithm is applied to the node coverage problem of wireless sensor network based on actual terrain. The simulation results show that the improved algorithm has achieved good results and increased the signal coverage of the wireless sensor network. There are many metaheuristic algorithms. In this article, we only use two algorithms for mixing. In the future, we may adopt some other algorithms [54–56] to get a hybrid approaches with better performance on WSN coverage problem.



---

*Source: 6690824-2021-08-10.xml*