# Research on Wireless Sensor Network Coverage Path Optimization Based on Biogeography-Based Optimization Algorithm

Authors: Guojun Chen; Xiangdong Qin; Ningsheng Fang; Wenbo Xu
Journal: Complexity
 (2021)

---

## Abstract

Path selection is one of the key technologies of wireless sensor network (WSN). A reasonable choice of coverage path can improve the service quality of WSN and extend the life cycle of WSN. Biogeography-based optimization (BBO) is widely used in the field of cluster intelligent optimization because its search method has a better incentive mechanism for population evolution. In this paper, the move-in and move-out operation and mutation operation of the BBO algorithm enable WSN to find an efficient routing path. In this paper, simulation experiments are carried out in two scenarios of regular deployment and random deployment of WSN nodes. The experimental results show that the quality of the WSN coverage path solution optimized by the BBO algorithm in the two scenarios is better than that of the particle swarm algorithm and genetic algorithm.


---

## Body

## 1. Introduction

With the gradual deepening research of quality of service (QoS) issues in WSN, we are paying more attention to the coverage path optimization of wireless sensor network [1, 2]. As the energy of sensor nodes in WSN is limited and cannot be maintained in time, establishing an efficient path connection method can not only effectively save network energy on the one hand but also improve the quality of service of WSN on the other hand. The main goal of WSN coverage path optimization is to establish an efficient and reliable path from the sensor sending node to the receiving node and maximize the network life of the WSN as much as possible [3, 4].In this paper, through the research and improvement of the biogeography-based optimization algorithm, it will make full use of the ability of the biogeography-based optimization algorithm to sense interactive data in multidimensional and high-dimensional problems to achieve the optimal construction of the wireless sensor network coverage path.The main contributions of this article are as follows:(1)
Analyze the main problems of wireless sensor network coverage path optimization, explain the impact of coverage path optimization on wireless sensor network deployment performance, and give a specific optimization model.(2)
Explain in detail the main principles, mathematical model, migration, and mutation operation steps of the biogeography-based optimization algorithm, and apply it to the WSN coverage path optimization problem. Through the comparison with the coverage path optimization experiments of the genetic algorithm and particle swarm optimization (PSO) algorithm, the effectiveness of the biogeography-based optimization algorithm for wireless sensor network coverage path optimization is further verified, and the local convergence problem in the iterative optimization process is solved and also the robustness of the communication link after WSN networking is enhanced.The rest of this paper is organized as follows. Section2 explains the structure and principle of the WSN coverage path optimization model. Section 3 explains the main mechanism and principle of the BBO algorithm. Section 4 gives the design of the WSN coverage path optimization algorithm based on the BBO algorithm. Section 5 explains the simulation experiments conducted under two WSN node deployment conditions to verify the effectiveness of the BBO algorithm in the WSN coverage path optimization problem.


## 2. WSN Coverage Path Optimization Model

In WSN structure, sensor nodes are divided into source node, sink node, and target node. The sensor node that collects monitoring data is the source node, whose data are summarized to the sink node through a certain multihop path and then sent to the target node (or user) through the Internet [5–9]. In order to improve the efficiency of data transmission and balance the energy consumption of the entire network, all sensor nodes of WSN are grouped [10–13]. Each group of sensor nodes is called a cluster. A cluster head is selected from the cluster as the sink node of the cluster to process the data of the cluster and communicate with other clusters and users. The cluster head node of each cluster is the target node on the communication path of the cluster, which is not fixed, but dynamically adjusted according to some energy consumption mechanism [14–17]. As the energy of each node will gradually decrease as the time goes on, the coverage path in each cluster of WSN needs to be adjusted timely according to the energy situation of the whole network. Because of the complicated topological structure of WSN, the plane structure of WSN will be simplified in order to facilitate research without losing the effectiveness of the algorithm [18, 19]. The WSN cluster is simplified to a rectangular area with a known size in a two-dimensional space. The number and location of sensor nodes in the area are known [20–22]. The sensor nodes are homogeneous nodes (the sensing radius, communication radius, and initial energy are the same), and these nodes are treated as a point within the region and are numbered in an orderly manner 1,2,…,n. Therefore, an undirected graph can be used to describe the WSN system structure. The undirected weight graph of any cluster G=V,E, where V=VHead,V1,V2,…,Vn is the node set in the cluster, VHead is the cluster head node of G, and Vii=1,2,…,n is other sensor nodes in G.The communication link set between nodes is denoted byE=e1,e2,…,em, which can be written as follows:(1)E=ei|DVj,Vk≤λ0;i=1,2,…,m;Vj,Vk∈V,where λ0 is the effective transmission distance between each sensor node. The energy consumption set of the link between nodes j and k is Cj,k=Ck,j. The judgment value of whether the communication link between node j and node k is connected is as follows:(2)Lj,k=Lk,j=1,DVj,Vk≤λ0,0,DVj,Vk>λ0.In summary, the mathematical model of WSN coverage path optimization is as follows:(3)∑j=1n∑k=1k≠jnCj,kLj,k,(4)Lj,k∈0,1.Equation (4) can ensure the shortest path between the source node and the target node [23, 24].The node selection mechanism of WSN coverage path optimization problem is different from the simple routing node selection of traditional wireless network [25–27]. The limit energy of sensor nodes in WSN, the more difficult positioning of the nodes, and the uncertainty of the monitoring area environment make it necessary for the WSN to take into account a lot of factors when selecting the path, thus using more complex routing mechanisms [28, 29].Aiming at this more complex routing mechanism, this paper uses the BBO algorithm with an adaptive mechanism to optimize the WSN coverage path.


## 3. BBO Algorithm

The BBO algorithm is also an intelligent algorithm based on biological populations, which is similar to PSO. Biological populations live in different habitats, and each habitat has its own fitness index (HSI) [30, 31]. Factors affecting HSI include rainfall, vegetation diversity, and climate conditions, which form a set of fitness vectors (SIV) [32, 33]. The population distribution and individual migration of habitats are greatly affected by HSI. Habitats with higher HSI hold more populations, and the ecological load tends to be saturated, so the emigration rate is high and the immigration rate is low [34, 35]. Habitats with lower HSI hold fewer populations, so the emigration rate is low and the emigration rate is high. Of course, as the population moves out and the biodiversity of the habitat declines, HSI will also decrease. In the same way, as populations move in and the biodiversity of the habitat increases, HSI will also increase. In addition, it is also necessary to consider that organisms will have a certain probability of mutation, which will also affect HSI.In the BBO algorithm, the habitat suitability vector SIV corresponds to the solution of the optimization problem [36, 37]. Habitat migration and migration operations correspond to the information sharing of the algorithm. The program with higher HSI operates according to its own migration rate and shares the information with the program with lower HSI. The program with lower HSI starts from higher. The HSI scheme has received many new problem-solving factors; the existence of mutation factors can help the diversity of the population to a certain extent, which increases the search ability of the algorithm in the optimization problem space.


### 3.1. Migration Model

The migration model of a certain habitat population in biogeography is shown in Figure1. The abscissa represents the number of populations in the habitat, and the ordinate represents the rate of habitat migration. The emigration rate and immigration rate of the population are denoted by μs and λs respectively.Figure 1
Habitat population migration model.Assume thatμs and λs are the immigration rate and the emigration rate when the number of habitat populations is s. During the time period from t to t+Δt, the probability that the habitat accommodates s populations at the same time is as follows.Supposeμs and λs are the emigration rate and the emigration rate when the number of habitat population is s, respectively. In the time period from t to t+Δt, the probability that the habitat can accommodate s populations at the same time is as follows:(5)Pst+Δt=pst1−λsΔt−μsΔt+Ps−1λs−1Δt+Ps+1μs+1Δt.In order for the habitat to haves populations at any time t+Δt, the following three conditions must be met:(1)
At timet, there are s populations in the habitat, and no populations will be migrated in or out during the period from t to t+Δt(2)
At timet, there are s − 1 populations in the habitat, and only one population migrates in the time period from t to t+Δt(3)
At timet, there are s + 1 populations in the habitat, and only one population migrates out from t to t+ΔtFor the convenience of calculation, it is assumed thatΔt is so small that the migration in or out of the population within the time period can be ignored. Then, let Δt⟶0 and find the limit of equation (5) as follows:(6)P˙s=−λs+μsPs+μs+1Ps+1,s=0,−λs+μsPs+λs−1Ps−1+μs+1Ps+1,1≤s≤Smax−1,−λs+μsPs+λs−1Ps−1,s=Smax.In which,n=Smax, P=P0,…,PnT, and we can get the matrix form of P˙s as follows:(7)P˙s=AP.In equation (7), the matrix A is as follows:(8)A=−λ0+μ0μ10…0λ0−λ1+μ1μ2⋱⋮⋮⋱⋱⋱⋮⋮⋱λn−2−λn−1+μn−1μn0…0λn−1−λn+μn.According to the migration model function shown in Figure1, if a given population size is k, the emigration rate and immigration rate corresponding to this population size can be calculated as follows:(9)μk=Ekn,λk=I1−kn.Considering the special case whenE = I, (10)A=E−11n0…0nn−12n⋱⋮⋮⋱⋱⋱⋮⋮⋱2n−1nn0…01n−1=EA′.In [3], the author gives the calculation of special cases. When the eigenvalue of A′ is 0, the corresponding eigenvector is as follows:(11)v=v1,…,vn+1,vi=n!n+1−i!i−1!,i=1,…,ceiln+12,vn+2−i,i=ceiln+12+1,…,n+1,in which ceil ∗ is the function that takes the upper limit integer of the formal parameter.At the same time, it can be also inferred that when the maximum population number in the habitat isn, the vector of probability composition corresponding to different population numbers is as follows:(12)Pn=Ps1,…,Psn=v∑i=1n+1vi.


### 3.2. Migration Operation

Migration operation is an important part of the BBO algorithm. Through the mutual migration of populations between various habitats, the algorithm makes a wide-area search in the solution space [38]. This feature is similar to the genetic strategy in the genetic algorithm. There is a mapping relationship between HSI and population size in the BBO algorithm. Before the migration operation is performed, all habitats are sorted according to their HSI values. s1 represents the habitat with lower HSI, and s2 represents the habitat with higher HSI; then, λs1>λs2 and μs1<μs2. In the process of migration operation, the probability of habitat change is proportional to its migration rate and the probability of change of the habitat of the new population is proportional to its migration rate.It is assumed that the BBO algorithm is consisted ofn habitats, each habitat has a D-dimensional fitness variable, and the vector xi=xi1,xi2,…,xiD represents the potential solutions in the D-dimensional search space, i=1,2,…,n. First, the algorithm determines whether habitat i is selected for the introduction of new populations according to the global migration rate Pmod∈0,1. Under a certain probability, if the habitat is selected, the suitability variable xij of habitat i,j=1,2,…,D will be determined whether to be changed or not according to its immigration rate λsi. If the suitability variable of habitat i is selected, the selection is made according to the emigration rate μsk of other habitats kk≠i. If habitat k is selected as the immigration source of habitat i, then the suitability variable xkl, l=1,2,…,D of habitat k will replace the suitability variable xijof habitat i.


### 3.3. Mutation Operation

The mutation operation ensures that the potential solutions of the BBO algorithm have a certain diversity and will not be degenerated in the iterative process. The main problem of mutation operation lies in how to give the corresponding mutation probability according to the existing population number in the habitat. The probability of the population quantity in the habitat has been given by equation (6), which represents the pre-existing possibility of the solution to the problem. If the population probability of a habitat is low, the probability of an optimal solution is low too, but if the habitat is mutated, then the optimal or better solution may appear. In contrast, if the population probability of a habitat is high, the probability of a new solution mutated is very low. Based on this, the equation for mutation operation can be obtained as follows:(13)mS=mmax1−PsPmax,in which mmax is the maximum mutation rate of the user-defined population and Pmax is the migration probability when the population size of the habitat reaches the maximum.


## 3.1. Migration Model

The migration model of a certain habitat population in biogeography is shown in Figure1. The abscissa represents the number of populations in the habitat, and the ordinate represents the rate of habitat migration. The emigration rate and immigration rate of the population are denoted by μs and λs respectively.Figure 1
Habitat population migration model.Assume thatμs and λs are the immigration rate and the emigration rate when the number of habitat populations is s. During the time period from t to t+Δt, the probability that the habitat accommodates s populations at the same time is as follows.Supposeμs and λs are the emigration rate and the emigration rate when the number of habitat population is s, respectively. In the time period from t to t+Δt, the probability that the habitat can accommodate s populations at the same time is as follows:(5)Pst+Δt=pst1−λsΔt−μsΔt+Ps−1λs−1Δt+Ps+1μs+1Δt.In order for the habitat to haves populations at any time t+Δt, the following three conditions must be met:(1)
At timet, there are s populations in the habitat, and no populations will be migrated in or out during the period from t to t+Δt(2)
At timet, there are s − 1 populations in the habitat, and only one population migrates in the time period from t to t+Δt(3)
At timet, there are s + 1 populations in the habitat, and only one population migrates out from t to t+ΔtFor the convenience of calculation, it is assumed thatΔt is so small that the migration in or out of the population within the time period can be ignored. Then, let Δt⟶0 and find the limit of equation (5) as follows:(6)P˙s=−λs+μsPs+μs+1Ps+1,s=0,−λs+μsPs+λs−1Ps−1+μs+1Ps+1,1≤s≤Smax−1,−λs+μsPs+λs−1Ps−1,s=Smax.In which,n=Smax, P=P0,…,PnT, and we can get the matrix form of P˙s as follows:(7)P˙s=AP.In equation (7), the matrix A is as follows:(8)A=−λ0+μ0μ10…0λ0−λ1+μ1μ2⋱⋮⋮⋱⋱⋱⋮⋮⋱λn−2−λn−1+μn−1μn0…0λn−1−λn+μn.According to the migration model function shown in Figure1, if a given population size is k, the emigration rate and immigration rate corresponding to this population size can be calculated as follows:(9)μk=Ekn,λk=I1−kn.Considering the special case whenE = I, (10)A=E−11n0…0nn−12n⋱⋮⋮⋱⋱⋱⋮⋮⋱2n−1nn0…01n−1=EA′.In [3], the author gives the calculation of special cases. When the eigenvalue of A′ is 0, the corresponding eigenvector is as follows:(11)v=v1,…,vn+1,vi=n!n+1−i!i−1!,i=1,…,ceiln+12,vn+2−i,i=ceiln+12+1,…,n+1,in which ceil ∗ is the function that takes the upper limit integer of the formal parameter.At the same time, it can be also inferred that when the maximum population number in the habitat isn, the vector of probability composition corresponding to different population numbers is as follows:(12)Pn=Ps1,…,Psn=v∑i=1n+1vi.


## 3.2. Migration Operation

Migration operation is an important part of the BBO algorithm. Through the mutual migration of populations between various habitats, the algorithm makes a wide-area search in the solution space [38]. This feature is similar to the genetic strategy in the genetic algorithm. There is a mapping relationship between HSI and population size in the BBO algorithm. Before the migration operation is performed, all habitats are sorted according to their HSI values. s1 represents the habitat with lower HSI, and s2 represents the habitat with higher HSI; then, λs1>λs2 and μs1<μs2. In the process of migration operation, the probability of habitat change is proportional to its migration rate and the probability of change of the habitat of the new population is proportional to its migration rate.It is assumed that the BBO algorithm is consisted ofn habitats, each habitat has a D-dimensional fitness variable, and the vector xi=xi1,xi2,…,xiD represents the potential solutions in the D-dimensional search space, i=1,2,…,n. First, the algorithm determines whether habitat i is selected for the introduction of new populations according to the global migration rate Pmod∈0,1. Under a certain probability, if the habitat is selected, the suitability variable xij of habitat i,j=1,2,…,D will be determined whether to be changed or not according to its immigration rate λsi. If the suitability variable of habitat i is selected, the selection is made according to the emigration rate μsk of other habitats kk≠i. If habitat k is selected as the immigration source of habitat i, then the suitability variable xkl, l=1,2,…,D of habitat k will replace the suitability variable xijof habitat i.


## 3.3. Mutation Operation

The mutation operation ensures that the potential solutions of the BBO algorithm have a certain diversity and will not be degenerated in the iterative process. The main problem of mutation operation lies in how to give the corresponding mutation probability according to the existing population number in the habitat. The probability of the population quantity in the habitat has been given by equation (6), which represents the pre-existing possibility of the solution to the problem. If the population probability of a habitat is low, the probability of an optimal solution is low too, but if the habitat is mutated, then the optimal or better solution may appear. In contrast, if the population probability of a habitat is high, the probability of a new solution mutated is very low. Based on this, the equation for mutation operation can be obtained as follows:(13)mS=mmax1−PsPmax,in which mmax is the maximum mutation rate of the user-defined population and Pmax is the migration probability when the population size of the habitat reaches the maximum.


## 4. Design of WSN Coverage Path Optimization Algorithm

Since the BBO algorithm is an iterative algorithm, a fitness function is needed to judge the degree of superiority of each iteration of the algorithm. For the fitness function of the sensor nodes in the process of WSN path optimization, not only the energy of the node must be considered but also the distance to the neighbor node and the energy consumption during communication. In order to further simplify the algorithm, the distance between nodes can be used to measure the energy consumption during communication. The specific fitness function is as follows:(14)Ct=ω1ct+ω2n−1∑i=1,i=tncididi+1,where t is the sensor node number, n is the total number of sensor nodes, ct is the current energy value of sensor node t, ci is the remaining energy of sensor node i for sleep, di is the Euclidean distance between sensor node i and current node t, ω1 is the energy weighting coefficient of sensor node t, ω2 is the energy weighting coefficient of neighboring nodes, and ω1+ω2 = 1 and 0<ω1,ω2<1.


### 4.1. Setting Parameters

N sensor nodes are deployed in the monitoring area, and the coordinates, radius, initial energy, and other information of the sensor nodes are known. Assuming that the total number of habitats isn, the fitness variable of each habitat has D dimensions, the maximum can habitat accommodate the population is Smax, the maximum mutation rate of the population is mmax, the migration probability when the habitat population reaches the maximum is Pmax, the maximum number of iterations of the algorithm is MaxNum, and the number of elite individuals retained in each generation is z.


### 4.2. Algorithm Flow

The implementation process of the WSN coverage path optimization algorithm is as follows:Step 1.
The fitness of energy consumption of each habitat is calculated according to equations (3) and (14), and it is taken as the adaptation index HSI of each habitat.Step 2.
Habitats are ranked according to HSI value from small to large.Step 3.
The habitat data of groupZ with the largest value of HSI were saved as the elite group.Step 4.
The corresponding immigration rateλi and emigration rate μi are calculated according to the population number of each habitat. According to the pseudocode of the above migration operation, each habitat is migrated.Step 5.
The mutation rate of each habitat is calculated according to equation (13), and then mutation operation is carried out on each habitat according to their respective mutation rate.Step 6.
The HSI of each habitat is calculated, and the habitats are sorted from small to large.Step 7.
The retained data ofz elite groups are assigned to the habitat group z with the lowest HSI at this time.Step 8.
The HSI of each habitat was calculated again and sorted from small to large, and the optimal value was recorded.Step 9.
If the termination condition of the algorithm is met (the maximum number of iterations is MaxNum, or the global optimal value is found), the algorithm is terminated; otherwise, it returns to Step (4) to continue execution.


## 4.1. Setting Parameters

N sensor nodes are deployed in the monitoring area, and the coordinates, radius, initial energy, and other information of the sensor nodes are known. Assuming that the total number of habitats isn, the fitness variable of each habitat has D dimensions, the maximum can habitat accommodate the population is Smax, the maximum mutation rate of the population is mmax, the migration probability when the habitat population reaches the maximum is Pmax, the maximum number of iterations of the algorithm is MaxNum, and the number of elite individuals retained in each generation is z.


## 4.2. Algorithm Flow

The implementation process of the WSN coverage path optimization algorithm is as follows:Step 1.
The fitness of energy consumption of each habitat is calculated according to equations (3) and (14), and it is taken as the adaptation index HSI of each habitat.Step 2.
Habitats are ranked according to HSI value from small to large.Step 3.
The habitat data of groupZ with the largest value of HSI were saved as the elite group.Step 4.
The corresponding immigration rateλi and emigration rate μi are calculated according to the population number of each habitat. According to the pseudocode of the above migration operation, each habitat is migrated.Step 5.
The mutation rate of each habitat is calculated according to equation (13), and then mutation operation is carried out on each habitat according to their respective mutation rate.Step 6.
The HSI of each habitat is calculated, and the habitats are sorted from small to large.Step 7.
The retained data ofz elite groups are assigned to the habitat group z with the lowest HSI at this time.Step 8.
The HSI of each habitat was calculated again and sorted from small to large, and the optimal value was recorded.Step 9.
If the termination condition of the algorithm is met (the maximum number of iterations is MaxNum, or the global optimal value is found), the algorithm is terminated; otherwise, it returns to Step (4) to continue execution.


## 5. Simulation Results and Analysis

The simulation experiment is carried out in Matlab2019 (b), and the BBO algorithm is compared with the PSO algorithm and genetic algorithm.The experiment is divided into group A and group B. In the experiment of group A, 20 sensor nodes are regularly deployed in a two-dimensional plane and the data of sensor nodes are known, which is shown in Figure2. Group B randomly deployed 20 sensor nodes in a two-dimensional plane, and the data of sensor nodes were also known, which is shown in Figure 3. In the two sets of experiments, the number of iterations of each algorithm is 200. In order to make the final results without loss of generality, 100 experiments were carried out for the three algorithms in the two sets of experiments, and the final results were averaged. The WSN coverage paths were optimized by the BBO algorithm for the sets of experiments which are shown in Figures 4 and 5, respectively. The comparison results of the three algorithms in the two sets of experiments are shown in Tables 1 and 2 and Figures 6 and 7.Figure 2
Initial deployment of experimental WSN in group A.Figure 3
Initial deployment of experimental WSN in group B.Figure 4
Optimization of WSN coverage path based on the BBO algorithm in group A.Figure 5
WSN coverage path optimization based on the BBO algorithm in group B.Table 1
Comparison of the experimental results of the three algorithms
AlgorithmThe success rateNumber of nodes that exceed a numerical valueFitnessGenetic algorithm (GA)88.3760.9077PSO algorithm94.8520.9536BBO algorithm98.9200.9902Table 2
Comparison of experimental results of the three algorithms in group B.
AlgorithmThe success rate (%)Number of nodes that exceed a numerical valueFitnessGenetic algorithm (GA)65.1290.8321PSO algorithm91.0250.9117BBO algorithm96.7920.9449Figure 6
Comparison of fitness values of the optimal solutions of the three algorithms in group A.Figure 7
Comparison of fitness values of the optimal solutions of the three algorithms in group B.It can be seen from Figure6 and Table 1 that in the experiment of group A, the distribution of communication links between the sensor nodes after the rule deployment is relatively even, the optimization result of the PSO algorithm has good adaptability and success rate, while the BBO algorithm further increased the fitness to 0.9902, and no nodes that exceeded the threshold appeared. Figure 5 shows the WSN coverage path optimization results of the BBO algorithm in the A group experiment.Through the above experimental results of Figure7 and Table 2, it can be observed that the relative positions deployed by the sensor nodes are distributed irregularly, and the construction of the coverage path is more complicated. The success rate of the genetic algorithm and the PSO algorithm in the coverage path optimization and the fitness is not ideal enough, and there are many nodes that exceed the threshold. Although there are 2 nodes exceeding the threshold in the optimization results of the BBO algorithm, its success rate and adaptability are better than those of the genetic algorithm and the PSO algorithm. Figure 5 also shows the WSN coverage path of the BBO algorithm in the B group experiment. As a result of the optimization, the communication link between each node belongs to the global optimal state. In addition, because the BBO algorithm does not generate a large number of new population individuals (except for a small number of mutant individuals) in the iterative process, the entire population is continuously optimized through the sharing of excellent individual information between the populations, so the BBO algorithm also effectively solves the local convergence problems that may occur in the genetic algorithm and the PSO algorithm.


## 6. Conclusions

This paper uses the better optimization performance of the BBO algorithm to optimize the WSN coverage path. Of course, in order to get a better optimal solution, the speed of the algorithm is sacrificed, which reflects that in WSN, and part of the energy in the initial stage of network deployment is sacrificed in the WSN in exchange for minimizing energy consumption after the network is stabilized. Future research will be inclined to further improve the convergence speed of the algorithm on the premise of ensuring the optimization of the coverage path.



---

*Source: 7826132-2021-05-17.xml*