# A Node Placement Optimization Algorithm in Heterogeneous WSN Based on Neighbor Nodes

Authors: Yijie Zhang; Zhan Guo
Journal: Wireless Communications and Mobile Computing
 (2022)

---

## Abstract

Wireless sensor network (WSN) is an important part of the Internet of Things. With the application and development of the Internet of Things, the heterogeneity of WSN is put forward a higher demand. Node placement is a critical step in the heterogeneous wireless sensor network (HEWSN). It is very important to optimize the node placement to fundamentally prolong the lifetime, improve the performance, and decrease the cost of the HEWSN. In this paper, the node placement optimization problem of HEWSN with different sensing types’ nodes is studied. An improved algorithm named neighbor nodes directed evolved nondominated sorting genetic algorithm (NN-DENSGA) is proposed to solve the multiobjective optimization problem. Homogeneous neighbor nodes are considered to promote directional evolution, and heterogeneous neighbor nodes are considered to repair the coverage holes. In addition, a forced update strategy is designed to increase diversity of population. Experiments have shown that the proposed algorithm not only has improvements in optimization performance but also in convergence speed and stability.


---

## Body

## 1. Introduction

Wireless sensor network (WSN) is a collection of sensor nodes with characteristics of self-organization characteristics. Sensor nodes form a network through routing protocols to realize information collection and data transmission in specified target monitoring area [1]. For different functions and purposes, sensor nodes can be divided into different types according to their sensing ability, computing ability, communication ability, and energy. A heterogeneous wireless sensor network (HEWSN) is a network composed of many types of sensor nodes. In recent years, most studies have focused on homogeneous wireless sensor networks (HOWSN) with single sensor node types [2–4]. However, in real applications, WSNs with different types of sensor nodes are more practical. Therefore, the heterogeneity of WSNs must be considered.Node placement is the first step when building a WSN, as well as for the HEWSN. A good node placement can reduce consumption and prolong the WSN’s lifetime while obtaining satisfactory coverage. In HEWSN, sensor nodes may have different functions, sensing types, mobility, and various parameters. Some researchers have proposed appropriate node placement schemes and node placement optimization algorithms for specific HEWSN [5–8]. This paper is mainly aimed at HEWSNs with different sensing types and the same parameters. It is also known as hardware heterogeneity. Under hardware heterogeneity, prolonging the lifetime of WSNs is one of the main problems faced by WSNs [9].There are few studies on node placement problem specifically for WSN with hardware heterogeneity. Cao et al. [10] focused on node placement in heterogeneous wireless directional sensor networks and proposed several distributed parallel multiobjective evolutionary algorithms (MOEAs) to optimize the coverage connectivity quality and lifetime of the network. However, Cao et al.’s study has not considered the node movement in optimization. Therefore, the proposed algorithms can only design the initial node placement but cannot adjust the existing node placement. Wang et al. [11] used the Hungarian algorithm to solve the movement problem represented by a minimum cost bipartite assignment problem and proposed a greedy movement algorithm (GMA) to optimize the coverage and movement cost. However, the speed of convergence is not fast enough. In my previous studies [12], a directed evolved NSGA2 (DENSGA) for HOWSN has been proposed. The algorithm uses the node density to promote the directional evolution of node placement. However, there are still challenges in the algorithm. For instance, the algorithm needs to avoid falling into local optimum. The speed of convergence still needs improvement.This paper mainly studies the node placement optimization algorithm for HEWSN, aimed at designing an algorithm with strong adaptability and fast convergence speed on the basis of previous studies. Specifically, the main contributions of this paper are as follows:(1)
Improve the model based on coordinate displacement and the optimization algorithm DENSGA to make it applicable for HEWSN(2)
Consider the effects of neighbor nodes. Find the same and different types of neighbor nodes, and then, put them into homogeneous and heterogeneous neighbor node sets. Adaptively calculate the crossover probability according to the node density of the corresponding type of sensor nodes. The calculation method considers not only the redundancy exclusion between homogeneous neighbor nodes but also the coverage hole detection through heterogeneous neighbor node sets(3)
Propose the forced crossover probability. It can increase the diversity of the population and effectively prevent the node distribution from falling into the local optimal solutionThe rest of the paper is organized as follows: Section2 describes the model for node placement problem in HEWSN; Section 3 introduces the DENSGA for HEWSN; Section 4 introduces the proposed operator and the improved algorithm; Section 5 contains the experiments, results, and analysis of the proposed algorithm when applied to the node placement problem. Section 6 contains the comparison experiment between NN-DENSGA and other algorithms. Finally, some conclusions are drawn in Section 7.


## 2. Model for Node Placement Problem in HEWSN

A HEWSN deploysn sensor nodes in the xmon×ymon monitoring area. These sensor nodes can be divided into tnum kinds and have the same parameters except for the sensing type. The sensor node set of the itnumth (itnum∈1,⋯,tnum) kind is ntnumitnum. Node placement problem in HEWSN needs the deployment of sensor nodes so that each kind of node can meet the requirement of coverage, and the HEWSN can meet some other requirements of application, such as the energy consumption and balance of the whole network, the moving distance for adjusting the layout.In this paper, the node placement optimization model based on node coordinate displacement [12] is adopted. The coverage and the network lifetime are taken as two optimization objectives. It is a constrained multiobjective optimization problem, and the model is described as follows:
(1)maxf=f1Δx,Δy,f2Δx,Δy,s.t.Δx∈−alimitxmon,alimitxmon,Δy∈−alimitymon,alimitymon,x0+Δx∈0,xmon,y0+Δy∈0,ymon,where Δx=Δx1,Δx2,⋯,Δxm,⋯,Δxn and Δy=Δy1,Δy2,⋯,Δym,⋯,Δyn, respectively, represent the horizontal and vertical displacement row vectors of all the nodes’ coordinates; Δxm and Δym are the row vectors of the mth node’s coordinate displacement; xmon and ymon, respectively, represent the length and width of the monitoring area; x0,y0 is the initial node coordinate vectors; alimit is a coefficient that restricts the movement of nodes. In this paper, alimit=0.1.There are different types of sensor nodes with different sensing capabilities in HEWSN. Clearly, the objective of coverage should comprehensively take the coverage of each type of node into consideration. Therefore, the average coverage of different types of nodes can be chosen as the primary optimization objective of the problem, as shown in the following equation:(2)f1Δx,Δy=1tnum∑itnum=1tnumCoverageitnum,where tnum represents the total number of node types, itnum∈1,⋯,tnum represents a node type, and Coverageitnum represents the coverage of the itnumth type.The objective of the lifetime (including energy consumption and node movement) [12] is shown in the following equation:
(3)f2Δx,Δy=RestEnergy=minErestm,r,cm−Ed⋅dism,mdism=Δxm2+Δym2,where Erestm,r,cm is the remaining energy of the mth node after r rounds, which can be calculated by the LEACH protocol, energy consumption model in [13]; Ed represents an energy consumption coefficient of node movement; dism denotes the moving distance of the mth node.


## 3. DENSGA for HEWSN

The DENSGA has proposed a directional crossover operator which is based on the NSGA2 [12]. In HOWSN, the directional crossover operator will determine a chromosome fragment’s crossover probability by the coverage degree of the grid point where the corresponding node is located. The chromosome segments corresponding to nodes in redundant positions will have a high crossover probability. The adaptive crossover probability can help get better coverage within a limited time.This method is also effective in HEWSN. It only needs to calculate the node density distribution for different types of nodes. Therefore, this section will adjust the directional crossover operator to make it suitable for HEWSN. It is also a preparation for further improvement in the next section.As different types of nodes collect different types of data, a completely covered position should be covered by all types of nodes. When calculating the density distribution, only homogeneous nodes should be considered.Figure1(a) shows a random placement graph of HEWSN with 2 types of nodes. Figures 1(b) and 1(c) show their gray-scale map of node density, respectively. Comparing the three images, the more times a certain pixel point is covered by a type of node, the darker it is in the gray-scale map, and the higher the crossover probability of a node in this position will be.Figure 1
Random node placement.
(a)
Node placement of all nodes(b)
Node density of 1st nodes(c)
Node density of 2nd nodeTo obtain the node density, the first step is to judge whether a pixel pointi,j is covered by the mth node, as shown in Equations (4) and (5). Then, count the number of times that each pixel is covered by how many nodes of the same type. These numbers can be called overridden numbers. The overridden number qitnumi,j of the i,j pixel, covered by all the itnumth type nodes, is described in Equation (6).
(4)dmi,j=i−xm2+j−ym2,(5)pi,jm=1dmi,j≤rs,0else,(6)qitnumi,j=∑m∈ntnumitnumpi,jm,where itnum represents type of the nodes, ntnumitnum represents the node set of type itnum, and pi,jm expresses whether the i,j pixel is covered by the mth node.If there aretnum kinds of nodes in HEWSN, tnum number ofxmon×ymon matrices Qitnum can be obtained. Among them, the overridden matrix Qitnum of the itnumth type of nodes can represent the density distribution of the itnumth type node, as shown in Equation (7). The itnumth type node’s overridden number Numm,itnum of the position of the mth node can be obtained by searching the matrix Qitnum, defined in Equation (8).
(7)Qitnum=qitnum1,1qitnum1,2⋯qitnum1,ymonqitnum2,1qitnum2,2⋯qitnum2,ymon⋯⋯⋯⋯qitnumxmon,1qitnumxmon,2⋯qitnumxmon,ymon,(8)Numm,itnum=qitnumxm,ym,where qitnumi,j represents overridden numbers of the i,j pixel covered by all the itnumth type nodes; xm and ym, respectively, represent the row vectors of the mth node’s coordinates.The largerNumm,tnumm is, the more densely homogeneous the nodes are. The crossover probability of the corresponding chromosome fragment can be calculated according to [12]. For subsequent improvement, the crossover probability pcm in this paper is changed to the cumulative calculation. Set the initial crossover probability of all nodes to 0. If there is redundancy at the position of the mth node, a certain crossover probability will add to pcm. In addition, there is an upper limit pcmax on the crossover probability for each node. The equation is shown as follows:
(9)pcm=minpcm,pcmaxNumm,tnumm=1,minpcm+pc1,pcmaxNumm,tnumm=2,minpcm+pc2,pcmaxNumm,tnumm>2,where pcm represents the crossover probability for the mth node; pc1, pc2, and pcmax are three constant parameters, set as 0.5, 0.9, and 0.95 in this paper, respectively..


## 4. The Improved Neighbor Nodes Directed Evolved Algorithm

The original directional crossover operator only considers the redundancy exclusion between nodes of the same type, cannot find the coverage hole. In addition, the experimental results in [12] show that in regions with a uniform initial node placement, the directional crossover operator may lead to low crossover probability for some nodes, which may depress the population diversity and result in a local optimum. Therefore, the influence of node density on neighbor nodes and a forced update probability are proposed in this section to help improving the performance of algorithm.The proposed method is based on the original directional crossover operator, named neighbor node directional crossover operator. The operator is an improved multipoint crossover operator. Each individual can be represented by a chromosome withn fragments. The crossover probability of each fragment can be adaptively calculated according to the node density of the corresponding node and its neighbor nodes.


### 4.1. Neighbor Nodes

In many studies, neighbor nodes refer to the nodes connected to the selected node for data transmission. They are neighbors in the network topology. However, this paper mainly aimed at the coverage. As long as the moving distance is short, the coverage hole can be filled nearby. Therefore, the neighbor nodes proposed in this section are not neighbors in the network topology, but neighbors in the space distance. Nodes whose coordinates are closed to the selected node can be defined as its neighbor nodes. If the coordinate of nodem is xm,ym, node mN which satisfies Equation (10) is one of the neighbor nodes of the node m.
(10)xm‐lN≤xmN≤xm+lN,ym‐lN≤ymN≤ym+lN,where lN represents the range of neighbor; xmN and ymN, respectively, represent the horizontal and vertical position coordinates of the mNth node’s.Figure2 shows a selected node and its neighbor nodes in HEWSN.Figure 2
Neighbor nodes in HEWSN.For the range of neighborlN, the spacing between each node in a uniform distribution (shown in Figure 3) can be used as a reference. For HEWSN, the spacing of each type of node can be calculated according to the size of the monitor area and the sensing radius of the sensor node. As shown in Figure 3, for uniform distribution in the square monitoring area, the number of the itnumth nodes in each row/column is nitnum. Therefore, the uniform distribution spacing luniitnum can be calculated by the following equation:
(11)luniitnum=xmnitnum.Figure 3
A uniform distribution.Whenxmon=ymon=100, n=100, tnum=2, and n1=n2=50, the uniform distribution spacing can be calculated that luni1=luni2=1.18rs1=1.18rs2. Appropriately enlarged luni and set lN=1.5rs1=1.5rs2.When all neighbor nodes are found, they should be classified according to the node type to get thetnum neighbor node sets of each node. The neighbor node set of the itnumth node of the node m is Nitnum=mN1,⋯,mNnom,itnum, where mN is the node number of the itnumth node satisfying Equation (10) and nom,itnum is the number of neighbor nodes of the itnumth node of the node m.In this way, the neighbor node set for each type of each node is obtained. According to the homogeneity and heterogeneity between the neighbor nodes and the selected node, neighbor nodes can be further divided into homogeneous neighbor nodes and heterogeneous neighbor nodes. The crossover probability calculation of these two kinds of neighbor nodes will be designed, respectively.


### 4.2. Homogeneous Neighbor Nodes

Figure4 shows the homogeneous neighbor nodes in HEWSN. For the network composed of all nodes of the same type in HEWSN, it can be regarded as a HOWSN. Except for adjusting the crossover probability which is corresponding to the selected node itself (as shown in Equation (9)), the homogeneous neighbor nodes’ crossover probability should also adjust.Figure 4
Homogeneous neighbor nodes in HEWSN.For a nodem, judge the type tnumm of node and build a homogeneous neighbor node set Ntnumm. For a homogeneous neighbor node mN in this set, a crossover probability can be added and calculated by the density of the node of type tnumm and the distance between the neighbor nodemN and the selected nodem.WhenNumm,tnumm=1, this position is covered by only one homogeneous node m, and the homogeneous node placement at this position may be suitable or sparse. In addition to fixing the position of the selected node m to prevent coverage decrease, the moving probability of homogeneous neighbor nodes should be slightly increased. It could help adjust the placement of the surrounding homogeneous nodes and prevent local optimization. Therefore, the crossover probability corresponding to homogeneous neighbor nodes should be slightly increased. The closer the homogeneous neighbor node mN is to the selected node m, the greater the crossover probability will be increased. When Numm,tnumm=2, this position is covered by two homogeneous nodes, and the homogeneous node placement at this position may be suitable or dense. Since the crossover probability of the selected node m has been appropriately increased, it is not necessary to adjust the crossover probability corresponding to its homogeneous neighbor nodes. When Numm,tnumm>2, this position is covered by at least three homogeneous nodes, and the homogeneous node placement at this position is evidently redundant. Even if the selected node m moves, the density of homogeneous nodes in the local area is too high. Moving homogeneous neighbor nodes may make improvements. Therefore, the crossover probability corresponding to homogeneous neighbor nodes should be appropriately increased. The closer the homogeneous neighbor node mN is to the selected node m, the greater the crossover probability will be increased. The equation is as follows:
(12)pcmN=minpcmN+aho1dm,mN,pcmaxNumm,tnumm=1,minpcmN,pcmaxNumm,tnumm=2,minpcmN+aho2dm,mN,pcmaxNumm,tnumm>2,where pcmN represents the crossover probability corresponding to a homogeneous neighbor node mN∈Ntnumm; dm,mN represents the coordinate distance between m and mN; aho1 and aho2 are two constant parameters, set as 0.1rs and 0.2rs in this paper, respectively.


### 4.3. Heterogeneous Neighbor Nodes

Figure5 shows the heterogeneous neighbor nodes in HEWSN. Heterogeneous neighbor nodes should be classified into different types, and then, analyze each type of heterogeneous neighbor nodes separately.Figure 5
Heterogeneous neighbor nodes in HEWSN.For a selected nodem of type tnumm, first choose a type of heterogeneous nodes itnum≠tnumm. Find the itnumth type node’s overridden number Numm,itnum of the position in the matrix Qitnum, and then find the itnumth type heterogeneous neighbor node set Nitnum. The crossover probability corresponding to heterogeneous neighbor nodes in the set should also adjust.WhenNumm,itnum=0, this position has not been covered by any itnumth type node. There is a coverage hole of itnumth type node. The moving probability of itnumth type heterogeneous neighbor nodes should be increased to move the surrounding nodes to compensate for the hole. Since the movement of several neighbor nodes may lead to new coverage holes, the moving probability should be greatly increased. The closer the itnumth type neighbor node mN is to the selected node m, the greater the crossover probability will be increased. When Numm,itnum=1 or Numm,itnum=2, the itnumth type node placement at this position may be suitable. It is unnecessary to adjust the placement of this type of neighbor nodes and change the crossover probability corresponding to these nodes. When Numm,itnum>2, the itnumth type node placement at this position is evidently redundant. However, this has been considered in itnumth type homogeneous neighbor nodes (shown in Equations (9) and (12)). Therefore, there is no need for repeated adjustment. The equation is shown as follows:
(13)pcmNitnum=minpcmNitnum+ahedm,mN,pcmaxNumm,itnum=0,minpcmNitnum,pcmaxNumm,itnum≥1,where pcmNitnum represents the crossover probability corresponding to a itnumth type heterogeneous neighbor node mNitnum∈Nitnum; ahe is a constant parameter, set as 0.6rs in this paper.


### 4.4. Neighbor Node Directional Crossover Operator with Forced Update Probability

To prevent low population diversity because of the low crossover probability, a certain probability can be set to force update node placement. When the forced update condition is met, the crossover probability will be set to a high value.The experiment results in [12] show that this situation is more likely to occur in the early stage of evolution, so the forced update probability pF should be higher at the beginning. However, with the node placement gradually optimized, nodes in some regions may have reached the global optimal placement. Then, the forced update probability pF should be reduced. Generally, the forced update probability is in a certain range and should decrease gradually with the increase of generation k. The calculation of pF is shown in Equation (14), and the update of pc is shown in Equation (15).
(14)pFk=bpf⋅e−apf⋅k/kmax,(15)pcm=pcmrandom<pF,pcmaxrandom≥pF,where k represents the current generation, kmax represents the max generation, apf and bpf are constant parameters, and random represents a randomly generated number between [0,1].In neighbor-node directional crossover operator, Equations (9), (12), and (13) are combined to calculate the crossover probability. Calculate the currently forced update probability by Equation (14), and then, update the crossover probability by Equation (15). Finally, judge each chromosome segment of the paternal individual whether crossover occurred.The proposed method introduces homogeneous and heterogeneous neighbor nodes and forced update probability on the basis of the directional crossover operator, so it is called the neighbor node directional crossover operator. It can quickly and effectively compensate for the coverage hole in HEWSN and effectively increase the diversity of the population.


### 4.5. The Flow of NN-DENSGA

Based on DENSGA, the neighbor node directional crossover operator is introduced to help fill coverage holes and increase population diversity. The improved algorithm for HEWSN is called neighbor nodes directed evolved NSGA2 (NN-DENSGA).The flow chart of the NN-DENSGA for node placement problem of HEWSN is shown in Figure6.Figure 6
Flow chart of NN-DENSGA.


## 4.1. Neighbor Nodes

In many studies, neighbor nodes refer to the nodes connected to the selected node for data transmission. They are neighbors in the network topology. However, this paper mainly aimed at the coverage. As long as the moving distance is short, the coverage hole can be filled nearby. Therefore, the neighbor nodes proposed in this section are not neighbors in the network topology, but neighbors in the space distance. Nodes whose coordinates are closed to the selected node can be defined as its neighbor nodes. If the coordinate of nodem is xm,ym, node mN which satisfies Equation (10) is one of the neighbor nodes of the node m.
(10)xm‐lN≤xmN≤xm+lN,ym‐lN≤ymN≤ym+lN,where lN represents the range of neighbor; xmN and ymN, respectively, represent the horizontal and vertical position coordinates of the mNth node’s.Figure2 shows a selected node and its neighbor nodes in HEWSN.Figure 2
Neighbor nodes in HEWSN.For the range of neighborlN, the spacing between each node in a uniform distribution (shown in Figure 3) can be used as a reference. For HEWSN, the spacing of each type of node can be calculated according to the size of the monitor area and the sensing radius of the sensor node. As shown in Figure 3, for uniform distribution in the square monitoring area, the number of the itnumth nodes in each row/column is nitnum. Therefore, the uniform distribution spacing luniitnum can be calculated by the following equation:
(11)luniitnum=xmnitnum.Figure 3
A uniform distribution.Whenxmon=ymon=100, n=100, tnum=2, and n1=n2=50, the uniform distribution spacing can be calculated that luni1=luni2=1.18rs1=1.18rs2. Appropriately enlarged luni and set lN=1.5rs1=1.5rs2.When all neighbor nodes are found, they should be classified according to the node type to get thetnum neighbor node sets of each node. The neighbor node set of the itnumth node of the node m is Nitnum=mN1,⋯,mNnom,itnum, where mN is the node number of the itnumth node satisfying Equation (10) and nom,itnum is the number of neighbor nodes of the itnumth node of the node m.In this way, the neighbor node set for each type of each node is obtained. According to the homogeneity and heterogeneity between the neighbor nodes and the selected node, neighbor nodes can be further divided into homogeneous neighbor nodes and heterogeneous neighbor nodes. The crossover probability calculation of these two kinds of neighbor nodes will be designed, respectively.


## 4.2. Homogeneous Neighbor Nodes

Figure4 shows the homogeneous neighbor nodes in HEWSN. For the network composed of all nodes of the same type in HEWSN, it can be regarded as a HOWSN. Except for adjusting the crossover probability which is corresponding to the selected node itself (as shown in Equation (9)), the homogeneous neighbor nodes’ crossover probability should also adjust.Figure 4
Homogeneous neighbor nodes in HEWSN.For a nodem, judge the type tnumm of node and build a homogeneous neighbor node set Ntnumm. For a homogeneous neighbor node mN in this set, a crossover probability can be added and calculated by the density of the node of type tnumm and the distance between the neighbor nodemN and the selected nodem.WhenNumm,tnumm=1, this position is covered by only one homogeneous node m, and the homogeneous node placement at this position may be suitable or sparse. In addition to fixing the position of the selected node m to prevent coverage decrease, the moving probability of homogeneous neighbor nodes should be slightly increased. It could help adjust the placement of the surrounding homogeneous nodes and prevent local optimization. Therefore, the crossover probability corresponding to homogeneous neighbor nodes should be slightly increased. The closer the homogeneous neighbor node mN is to the selected node m, the greater the crossover probability will be increased. When Numm,tnumm=2, this position is covered by two homogeneous nodes, and the homogeneous node placement at this position may be suitable or dense. Since the crossover probability of the selected node m has been appropriately increased, it is not necessary to adjust the crossover probability corresponding to its homogeneous neighbor nodes. When Numm,tnumm>2, this position is covered by at least three homogeneous nodes, and the homogeneous node placement at this position is evidently redundant. Even if the selected node m moves, the density of homogeneous nodes in the local area is too high. Moving homogeneous neighbor nodes may make improvements. Therefore, the crossover probability corresponding to homogeneous neighbor nodes should be appropriately increased. The closer the homogeneous neighbor node mN is to the selected node m, the greater the crossover probability will be increased. The equation is as follows:
(12)pcmN=minpcmN+aho1dm,mN,pcmaxNumm,tnumm=1,minpcmN,pcmaxNumm,tnumm=2,minpcmN+aho2dm,mN,pcmaxNumm,tnumm>2,where pcmN represents the crossover probability corresponding to a homogeneous neighbor node mN∈Ntnumm; dm,mN represents the coordinate distance between m and mN; aho1 and aho2 are two constant parameters, set as 0.1rs and 0.2rs in this paper, respectively.


## 4.3. Heterogeneous Neighbor Nodes

Figure5 shows the heterogeneous neighbor nodes in HEWSN. Heterogeneous neighbor nodes should be classified into different types, and then, analyze each type of heterogeneous neighbor nodes separately.Figure 5
Heterogeneous neighbor nodes in HEWSN.For a selected nodem of type tnumm, first choose a type of heterogeneous nodes itnum≠tnumm. Find the itnumth type node’s overridden number Numm,itnum of the position in the matrix Qitnum, and then find the itnumth type heterogeneous neighbor node set Nitnum. The crossover probability corresponding to heterogeneous neighbor nodes in the set should also adjust.WhenNumm,itnum=0, this position has not been covered by any itnumth type node. There is a coverage hole of itnumth type node. The moving probability of itnumth type heterogeneous neighbor nodes should be increased to move the surrounding nodes to compensate for the hole. Since the movement of several neighbor nodes may lead to new coverage holes, the moving probability should be greatly increased. The closer the itnumth type neighbor node mN is to the selected node m, the greater the crossover probability will be increased. When Numm,itnum=1 or Numm,itnum=2, the itnumth type node placement at this position may be suitable. It is unnecessary to adjust the placement of this type of neighbor nodes and change the crossover probability corresponding to these nodes. When Numm,itnum>2, the itnumth type node placement at this position is evidently redundant. However, this has been considered in itnumth type homogeneous neighbor nodes (shown in Equations (9) and (12)). Therefore, there is no need for repeated adjustment. The equation is shown as follows:
(13)pcmNitnum=minpcmNitnum+ahedm,mN,pcmaxNumm,itnum=0,minpcmNitnum,pcmaxNumm,itnum≥1,where pcmNitnum represents the crossover probability corresponding to a itnumth type heterogeneous neighbor node mNitnum∈Nitnum; ahe is a constant parameter, set as 0.6rs in this paper.


## 4.4. Neighbor Node Directional Crossover Operator with Forced Update Probability

To prevent low population diversity because of the low crossover probability, a certain probability can be set to force update node placement. When the forced update condition is met, the crossover probability will be set to a high value.The experiment results in [12] show that this situation is more likely to occur in the early stage of evolution, so the forced update probability pF should be higher at the beginning. However, with the node placement gradually optimized, nodes in some regions may have reached the global optimal placement. Then, the forced update probability pF should be reduced. Generally, the forced update probability is in a certain range and should decrease gradually with the increase of generation k. The calculation of pF is shown in Equation (14), and the update of pc is shown in Equation (15).
(14)pFk=bpf⋅e−apf⋅k/kmax,(15)pcm=pcmrandom<pF,pcmaxrandom≥pF,where k represents the current generation, kmax represents the max generation, apf and bpf are constant parameters, and random represents a randomly generated number between [0,1].In neighbor-node directional crossover operator, Equations (9), (12), and (13) are combined to calculate the crossover probability. Calculate the currently forced update probability by Equation (14), and then, update the crossover probability by Equation (15). Finally, judge each chromosome segment of the paternal individual whether crossover occurred.The proposed method introduces homogeneous and heterogeneous neighbor nodes and forced update probability on the basis of the directional crossover operator, so it is called the neighbor node directional crossover operator. It can quickly and effectively compensate for the coverage hole in HEWSN and effectively increase the diversity of the population.


## 4.5. The Flow of NN-DENSGA

Based on DENSGA, the neighbor node directional crossover operator is introduced to help fill coverage holes and increase population diversity. The improved algorithm for HEWSN is called neighbor nodes directed evolved NSGA2 (NN-DENSGA).The flow chart of the NN-DENSGA for node placement problem of HEWSN is shown in Figure6.Figure 6
Flow chart of NN-DENSGA.


## 5. Parameter Analysis

Forced crossover constant coefficientapf and bpf are the main parameters in NN-DENSGA. Among them, apf can be determined by calculation, which will be shown in Section 5.1. Therefore, bpf will be tested and analyzed in this section.


### 5.1. Experimental Environment and Parameters

In this paper, the simulation of HEWSN and the test of algorithms are realized by MATLAB (Matlab R2016a). All programs have been run on a Windows 10 operating system (64 bits), with a computer configuration of 2.60 GHz processor and 32 GB RAM.The proposed algorithm is implemented in a centralized architecture, and the base station is responsible for the execution of the algorithm and broadcasting the moving plan to all sensor nodes.The HEWSN to be optimized consists of 100 sensor nodes randomly distributed in the area of100×100 to be monitored and a sink node outside the area. There are mainly two types of sensor nodes, with the same number, the same parameters, and different sensing types. LEACH is chosen as the WSN routing protocol, the energy consumption model, and related parameters are shown in [12].Parameters used in the experiments are shown in Table1.Table 1
Parameter settings.
Length and width of the monitoring area,xmon, ymon/m100Coordinates of the sink node,xsink,ysink/m(50,175)Total number of nodes,n100Type number of nodes,tnum2Sensing range of the node,rs/m12Size of the population,Psize20Maximum generation of the algorithm,kmax100Crossover probability constant 1,pc10.5Crossover probability constant 2,pc20.9Max crossover probability,pcmax0.95Forced crossover constant 1,apf2.3Mutation probability,pm0.1Homogeneous neighbor node crossover probability constant 1,aho11.2Homogeneous neighbor node crossover probability constant 2,aho22.4Heterogeneous neighbor node crossover probability constant,ahe7.2Initial energy of nodes,Eo/J0.5In Section4.4, the equation to calculate the forced crossover probability is shown in Equation (14) with constant parameters apf and bpf. If pF is set between [0.05,bpf], according to pFkmax=0.05, it can be calculated that apf=‐ln0.1≈2.3.


### 5.2. Parameter Analysis forbpf

One of the forced crossover constant coefficientsbpf can determine the initial forced crossover probability value. In this experiment, set 6 different values for bpf∈0.1,0.2,0.3,0.4,0.5,0.6.The influences ofbpf for a random node placements are shown in Figure 7, which is composed of (a) and (b), respectively, corresponding to two optimization objectives, f1=Coverage and f2=RestEnergy. Figure 7(a) shows the average Coverage of the first dominance level in 5 runs for different values of bpf. Figure 7(b) shows the average RestEnergy of the first dominance level in 5 runs for different values of bpf.Figure 7
The optimal results for different values ofbpf.
(a)
AverageCoverage for different bpf(b)
AverageRestEnergy for different bpfThe following conclusions can be obtained from Figure7: The value of bpf has little effects on RestEnergy, but large effects on Coverage. If the value of bpf is too small, the performance of final Coverage is not good. This is mainly because NN-DENSGA may have a poor population diversity and fall into local optimum. If the value of bpf is too large, the Coverage may have a slow convergence. This is mainly because NN-DENSGA will degrade to NSGA2 and lose the ability of fast convergence.In this paper, considering the optimization effect and convergence speed, choosebpf=0.4.


## 5.1. Experimental Environment and Parameters

In this paper, the simulation of HEWSN and the test of algorithms are realized by MATLAB (Matlab R2016a). All programs have been run on a Windows 10 operating system (64 bits), with a computer configuration of 2.60 GHz processor and 32 GB RAM.The proposed algorithm is implemented in a centralized architecture, and the base station is responsible for the execution of the algorithm and broadcasting the moving plan to all sensor nodes.The HEWSN to be optimized consists of 100 sensor nodes randomly distributed in the area of100×100 to be monitored and a sink node outside the area. There are mainly two types of sensor nodes, with the same number, the same parameters, and different sensing types. LEACH is chosen as the WSN routing protocol, the energy consumption model, and related parameters are shown in [12].Parameters used in the experiments are shown in Table1.Table 1
Parameter settings.
Length and width of the monitoring area,xmon, ymon/m100Coordinates of the sink node,xsink,ysink/m(50,175)Total number of nodes,n100Type number of nodes,tnum2Sensing range of the node,rs/m12Size of the population,Psize20Maximum generation of the algorithm,kmax100Crossover probability constant 1,pc10.5Crossover probability constant 2,pc20.9Max crossover probability,pcmax0.95Forced crossover constant 1,apf2.3Mutation probability,pm0.1Homogeneous neighbor node crossover probability constant 1,aho11.2Homogeneous neighbor node crossover probability constant 2,aho22.4Heterogeneous neighbor node crossover probability constant,ahe7.2Initial energy of nodes,Eo/J0.5In Section4.4, the equation to calculate the forced crossover probability is shown in Equation (14) with constant parameters apf and bpf. If pF is set between [0.05,bpf], according to pFkmax=0.05, it can be calculated that apf=‐ln0.1≈2.3.


## 5.2. Parameter Analysis forbpf

One of the forced crossover constant coefficientsbpf can determine the initial forced crossover probability value. In this experiment, set 6 different values for bpf∈0.1,0.2,0.3,0.4,0.5,0.6.The influences ofbpf for a random node placements are shown in Figure 7, which is composed of (a) and (b), respectively, corresponding to two optimization objectives, f1=Coverage and f2=RestEnergy. Figure 7(a) shows the average Coverage of the first dominance level in 5 runs for different values of bpf. Figure 7(b) shows the average RestEnergy of the first dominance level in 5 runs for different values of bpf.Figure 7
The optimal results for different values ofbpf.
(a)
AverageCoverage for different bpf(b)
AverageRestEnergy for different bpfThe following conclusions can be obtained from Figure7: The value of bpf has little effects on RestEnergy, but large effects on Coverage. If the value of bpf is too small, the performance of final Coverage is not good. This is mainly because NN-DENSGA may have a poor population diversity and fall into local optimum. If the value of bpf is too large, the Coverage may have a slow convergence. This is mainly because NN-DENSGA will degrade to NSGA2 and lose the ability of fast convergence.In this paper, considering the optimization effect and convergence speed, choosebpf=0.4.


## 6. Comparison Experiment between NN-DENSGA and Other Algorithms

In this section, NN-DENSGA will be compared with DENSGA [12] and NSGA2 [14] in the HEWSN’s node placement optimization experiments. DENSGA in this section is the modified algorithm for HEWSN mentioned in Section 3.The experimental environment has been described in Section5.1, and the parameters of NN-DENSGA and DENSGA used in the experiment are shown in Table 1. According to the parameter experiment in Section 5.2, set bpf=0.4. Therefore, the change of forced crossover probability is shown in Figure 8. Tournament selection operator, multipoint crossover operator, and single point mutation operator are used in NSGA2, which pc=0.9, pm=0.1.Figure 8
Change of forced crossover probability.Besides, the optimization objectives of the regional optimization for node placement,Coverage and RestEnergy, four additional evaluation indicators are used in this paper. The coverage of each type of node Coverage1 and Coverage2, comprehensive score Score=f1⋅f2 [12], the total moving distance of nodes D=∑m=1ndism [12], the coverage growth in the unit distance RD=ΔCoverage/D [15] are selected as evaluation indicators.The largerCoverage1, Coverage2, and Score is, the better the optimization results of the algorithm are. The smaller D is, the less energy the node movement consumes, and the better the optimization result of the algorithm will be.Randomly set an initial node placement (node placement 1). NN-DENSGA, DENSGA, and NSGA2 are used to optimize the node placement of HEWSN. To eliminate the influence caused by randomness, each algorithm will run 5 times and the average results are taken. The results of the nondominated solutions are analyzed and compared.Figure9 shows the results of different algorithms in each generation. Among the four figures, Figure 9(a) shows the average coverage curves, Figure 9(b) shows the average rest energy curves, Figure 9(c) shows the average score curves, and Figure 9(d) shows the max score curves. The average coverage curves and average rest energy curves, respectively, represent the average value of the first dominance level’s Coverage and RestEnergy. The average score curves and the max score curves, respectively, represent the average value made and the max value of the first dominance level’s Score.Figure 9
Results for NSGA2, DENSGA, and NN-DENSGA (node placement 1).
(a)
AverageCoverage(b)
AverageRestEnergy(c)
AverageScore(d)
MaxScoreFigures9(a) and 9(b) show that NN-DENSGA can achieve node placement with better coverage and longer lifetime within fewer generations rather than DENSGA and NSGA2. Figures 9(c) and 9(d) show that the results of NN-DENSGA and DENSGA have better Score than NSGA2, while NN-DENSGA can get better results faster than DENSGA.For further analyzing the optimization of these three algorithms, the average results and its standard deviations of all the nondominated solutions (k=100) in 5 runs are shown in Table 2, where the optimal results are highlighted in bold.Table 2
Results of a random node placement (node placement 1).
CoverageCoverage1Coverage2RestEnergy/JScoreD/mRD/m-1Initial node placement0.8651±0.00000.8377±0.00000.8925±0.00000.2640±0.00000.2284±0.0000--NN-DENSGA0.9533±0.00990.9536±0.01150.9530±0.01120.2822±0.00310.2690±0.0049794.1±15.51.11E−4±1.25E−5DENSGA0.9483±0.01920.9485±0.02150.9482±0.01870.2820±0.00160.2673±0.0051798.9±21.51.04E−4±2.41E−5NSGA20.9489±0.00920.9480±0.00990.9498±0.01290.2815±0.00260.2670±0.0029790.5±16.31.06E−4±1.17E−5The following conclusions can be obtained from Table2: The optimization results of DENSGA are a little better than NSGA2, but with higher standard deviations. It means that the stability of DENSGA is not good enough. Sometimes, DENSGA may fall into a local optimum due to low population diversity. Within 100 generations, the optimization results of NN-DENSGA are better than DENSGA and NSGA2 with lower standard deviations. It means that the performance and stability of NN-DENSGA are all best. To achieve better optimization results, the moving distance of NN-DENSGA is slightly larger than NSGA2 but still smaller than DENSGA, but its movement is the most efficient.To eliminate the contingency and the effect due to the initial node placement, two other initial node placements (node placement 2 and node placement 3) are tested. The results are shown in Figures10 and 11. Figure 10 shows that the conclusions obtained from node placement 1 and node placement 2 are similar. Figure 11 shows that in node placement 3, NN-DENSGA performs similar to DENSGA and much better than NSGA2. It can be concluded that, compared with DENSGA, the stability of NN-DENSGA has a significant improvement while the performance has also increased.Figure 10
Results for NSGA2, DENSGA, and NN-DENSGA (node placement 2).
(a)
AverageCoverage(b)
AverageRestEnergy(c)
AverageScore(d)
MaxScoreFigure 11
Results for NSGA2, DENSGA, and NN-DENSGA (node placement 3).
(a)
AverageCoverage(b)
AverageRestEnergy(c)
AverageScore(d)
MaxScoreIn addition, two nonparametric statistical tests, Wilcoxon Signed Rank Test [16] and Friedman Test [16], are used to compare the algorithms. In nonparametric statistical tests, the two optimization objectives (Coverage and RestEnergy) of the node placement problem are analyzed. NN-DENSGA, DENSGA, and NSGA2 tests for 10 different random initial node placements and each situation run 5 times. The results are shown in Table 3.Table 3
Results of 10 different random initial node placements.
No.Coverage of NN-DENSGACoverage of DENSGACoverage of NSGA2RestEnergy of NN-DENSGARestEnergy of DENSGARestEnergy of NSGA210.95330.94830.94890.28220.28200.281520.94890.94290.94710.28750.28710.287530.94380.93440.93380.27100.27430.274040.96640.95640.96240.27900.27870.277250.95830.95080.94380.28060.28100.279960.93990.93070.94220.28020.28060.280370.94780.94830.94590.27920.27640.277780.95760.94290.95100.27820.27810.278590.95110.95560.95920.27760.27620.2764100.96450.96730.96110.27830.28080.2780TheCoverage and RestEnergy can be ranked according to their values. Large rank values represent better performances. Let R+ be the sum of ranks for the problems in which the first algorithm outperformed the second and R− the sum of ranks for the opposite. The larger the difference between R+ and R− is, the more differences in the algorithm performance are [16]. A p value provides information about whether a statistical hypothesis test is significant or not, and it also indicates something about how significant the result is: the smaller the p value, the more obvious the differences between two algorithms [17].The Wilcoxon Signed Rank Test is used to compare NN-DENSGA with one other algorithm. The results of the Wilcoxon Signed Rank Test are shown in Table4.Table 4
Results of Wilcoxon Signed Rank Test.
ComparisonR+R−Coveragep valueRestEnergyp valueNN-DENSGA to DENSGA15126.50.0280.878NN-DENSGA to NSGA2174.500.0930.260The following conclusions can be obtained from Table3: NN-DENSGA shows an improvement over DENSGA and NSGA2, especially in terms of Coverage. The Coverage of NN-DENSGA shows an improvement over NSGA2 with a level of significance α=0.1 and over DENSGA with a level of significance α=0.05.The Friedman Test can detect differences over the whole multiple comparisons. The box-plot of Friedman Test results are shown in Figure12.Figure 12
Results of Friedman Test.
(a)
Box-plot of averageCoverage(b)
Box-plot of averageRestEnergyFigure12 shows that NN-DENSGA has an improvement on Coverage over NSGA2 and DENSGA. NSGA2 and DENSGA are not stable enough, rarely achieve good optimization results. The stability of NN-DENSGA is better than that of NSGA2 and DENSGA.To further analyze the convergence speed of these three algorithms, the generations of the algorithms that average coverage reaches the assigned values are shown in Figure13. The algorithm tests for 5 different random initial node placements and each situation run 5 times. k90 to k94, respectively, represent the generation in which average Coverage reaches 0.90 to 0.94 for the first time. The smaller k90 to k94 are, the faster the convergence speed is.Figure 13
Convergence speed for NSGA2, DENSGA, and NN-DENSGA.Figure13 shows the convergence speed for different algorithms. It is obvious to find that NN-DNSGA can obtain the required coverage faster than DENSGA and NSGA.In conclusion, the improvements proposed in this paper are effective. Neighbor node directional crossover operator can help repair the coverage holes and improve the optimization performance and convergence speed. The forced update probability can help increase population diversity, prevent falling into local optimum, and enhance the stability and universality of the algorithm. Therefore, NN-DENSGA can obtain satisfactory node placements in HEWSN.


## 7. Conclusions

In view of the increasing demand for HEWSN with different sensors in practical applications, this paper proposes an improved algorithm called NN-DENSGA for the node placement optimization problem in HEWSN.In this paper, the directional crossover operator is modified to apply for HEWSN. Then, the influences of neighbor nodes are considered and analyzed. In addition, a forced update strategy is proposed to increase the diversity of population. Finally, a new neighbor node directional crossover operator with forced update probability is designed. Experiments show that the proposed algorithm has improvements in both searching performance and convergence speed when solving the node placement problem in HEWSN. It also has great improvements in diversity and stability, which ensure NN-DENSGA can achieve satisfactory results each time.In conclusion, the proposed algorithm can effectively increase performance and extend the lifetime of HEWSN with a low moving cost. It also provides a theoretical and experimental basis for the setting and maintenance of the Internet of Things composed of different sensor nodes. However, in this paper, sensors differ only in the sensing type. In future research, more differences between sensors will be considered, while the convergence speed and stability of the algorithm need to be further improved.



---

*Source: 6820076-2022-08-22.xml*