Level Set Based Coverage Holes Detection and Holes Healing Scheme in Hybrid Sensor Network

Abstract

A fundamental issue in sensor network is the coverage problem. Since the distribution of sensor nodes is not usually uniform due to random deployment and node failures, the coverage holes are hardly avoided in sensor network. And the coverage holes are important health indicators of the sensor network. This paper firstly proposes a level set based coverage holes detection algorithm for hybrid sensor network. This algorithm could estimate the number of holes and the size of the holes. Then we propose genetic algorithms based coverage holes healing algorithm. This algorithm could leverage mobility to optimize the average coverage rate and the average movement distance of the mobile nodes. Simulation results show that the proposed method could detect the holes efficiently. The holes healing algorithm outperforms the Random and Delaunay methods.

1. Introduction

In recent years, advance in the electronic and wireless communication technology has led to the development of wireless sensor network. WSN has the potential to provide unique capabilities for monitoring battle field and environment through the large number of randomly deployed sensor nodes [1]. A typical sensor node includes sensing, processing, communication, storage, and power units. The sensor nodes measure several physical quantities, possibly process the measurements in a collaborative manner, and route the results to the sink node.

A fundamental issue in WSN is the coverage problem because it is directly relate to optimization of resources in the field. According to the application circumstances, the coverage problem can be divided into categories, namely, area coverage, target coverage, and barrier coverage [2]. The aim of the area coverage is to sufficiently cover the whole sensor field. Target coverage, on the other hand, mainly deals with how to cover a set of discrete targets with known locations. Barrier coverage aims at detecting intruders that attempt to cross the network. In this paper we investigate the area coverage problem.

After a sensor network is deployed, some nodes may fail due to the depletion of energy or physical damage. As the number of dead sensors increases, sensing holes arise. The coverage holes formation deteriorates the overall quality by changing the network structures like the breach paths or communication routes. The coverage holes may affect the network connectivity and may result in losing the sensed data [3]. So it is necessary to determine the number and size of network holes and fill them with other redundant nodes to keeping desired coverage.

In this paper, we firstly propose level set based coverage holes detection algorithm. This algorithm could estimate not only the number of holes but also the size of holes. After deciding the existence of the coverage holes and their size, the base station awakens the mobile nodes and arranges them to move to the appropriate locations to heal the network. A genetic algorithms based holes healing algorithm is proposed. In this algorithm, the partially mapped crossover and exchange mutation operations are employed to avoid the duplicate numbers in a chromosome.

The rest of the paper is organized as follows. Section 2 presents the related works. Section 3 describes the sensing model and problem formulation. In Sections 4 and 5, we introduce the level set base coverage holes detection and genetic algorithms based coverage holes healing algorithms, respectively. Some simulation results are presented in Section 6. The conclusions are given in Section 7.

2. Related Works

After the network is deployed, the coverage holes may emerge due to the failed sensor nodes. The failed nodes in the field may partition the connectivity and the coverage of the network endangering the reliability of the network. Therefore, the network needs to be maintained periodically. For the network maintenance algorithm, there are two issues that need to be addressed. Firstly, the coverage holes need to be detected and the size of the holes need to be estimated, that is, the coverage holes detection issue. Secondly, the coverage holes needs to be healed, that is, coverage holes healing issue. In this section, we review a number of existing studies about the two issues.

2.1. Coverage Holes Detection

Coverage holes detection is of prime importance and several works have been investigated to detect the coverage holes. Morphological image processing tools [4] are used to locate the sensing holes in the network. The holes identification of this method can be performed by forming the related iso-sensing graph which is used to differentiate the area with high or low sensing quality. A Voronoi diagram [5] based method is proposed to estimate the exact number of coverage holes in the sensing field. According to the property of Voronoi diagram, all the pints inside a Voronoi polygon are close to only one sensor that lies within that polygon. If the polygon is not covered by the sensor lying inside the polygon, it will not be covered by any other sensor, thus contributing to coverage holes. In order to simplify the proposed method in [5], the authors proposed to use the distance between the sensor node and its furthest Voronoi vertex to decide the coverage holes and the size of the holes [6]. If such distance is larger than its sensing range, then the coverage holes exist and the size of the hole is proportional to this distance. The Delaunay triangulation [7] is used to detect the coverage holes. The set of static nodes are triangulated into many triangles and the circumcenter of every triangle is calculated. Then this algorithm detects whether the circumcenter is covered by the three static sensors that formed the triangle. If the circumcenter is covered, it is not a coverage hole.

Most of the above methods use the disc sensing model since it will simplify analysis. However, this model is not realistic. In this paper, we employ the Neyman-Pearson based sensing model to analyze the coverage holes detection problem.

2.2. Coverage Holes Healing

The previous research on coverage holes healing for wireless sensor network is briefly described in the following. This problem can be categorized into two types: robot assisted and mobility assisted healing methods.

For robot assisted healing methods, the sensor nodes are all static. The mobile robots serve as the maintainer of the network and deploy the new nodes into the field to improve the coverage rate. A robot assisted coverage holes healing method is proposed in concave boundaries [8]. The robot can deploy the new sensor node efficiently with full coverage. In [9], the authors use a small number of mobile robots to replace failed sensors. This scheme sets up the guardian-guardee relationship among sensor nodes in initialization step. And then three robot coordination algorithms are proposed to repair the networks. This scheme relies on the nodes communication with each other frequently in order to sustain the guardian-guardee relationship, so this scheme will consume more energy. In [10], the authors proposed a network maintenance and repair method via relays deployment. The Fielder value is firstly used as an indicator of the network health, and then the network maintenance problem is formulated as a semidefinite programming optimization problem that can be solved in polynomial time. This method could determine the minimum number of relays during network repair process. In [11], the authors modeled the robot-assisted coverage problem as one-commodity traveling salesman problem.

For mobility assisted healing methods, all or parts of the nodes are assumed to have mobility. In [12], a mobile sensor relocation scheme is designed to solve the optimization of movement assisted deployment problem. This scheme can not only solve the coverage holes problem but also significantly increase the network lifetime of the resulting WSN after the relocation. Coverage pattern based movement strategy is proposed in [13, 14]. The destination locations of the mobile nodes are determined based on a predefined coverage pattern that can meet both area coverage requirements. The virtual force based node movement strategies are investigated in [15, 16]. The two mobile nodes expel each other if their distance is too close or attract each other if their distance is too far. The mobile node may also experience other types of force. The overall force specifies the direction and distance that a mobile node should move to. The grid quorum base movement strategies are proposed in [17, 18]. The sensing field is partitioned into many grid cells, and then the mobile node redeployment problem is viewed as a load balancing problem.

3. Sensing Model and Problem Formulation

In this section, we firstly present the sensing model. Then we describe some required assumptions and definitions.

3.1. Sensing Model

The most commonly used model in coverage problems is the disk model. It assumes that the sensing region for a sensor is a circular area centered at it. A point within the sensing radius of a sensor is detected with probability 1 while the point outside this circle of influence is not detected with probability 0. The disk model is commonly adopted for its analytical simplicity, but it is based on unrealistic assumption of perfect coverage for sensors [19]. So this model has certain limitations in describing how well the field is covered.

The disc model cannot represent the degradation of a sensor's sensing capability as the distance between the sensor and measuring point increases. The sensors have widely different sensing characteristics. Depending on the specific sensor and application environment, different sensing models can be constructed to capture the sensing characteristics of the sensors. The detection probability of Elfes' model [20] is described such that the physical properties of the sensors are accommodated by generic model parameters. The detection probability of a point i by sensor j is

$$\begin{array}{cc}& p_{ij}=\{\begin{array}{cc}\mathrm{1},\hfill & d_{ij}\le d_{T\mathrm{1}},\hfill \\ e^{-\lambda {\left(d_{ij}-d_{T\mathrm{1}}\right)}^{\beta }},\hfill & d_{T\mathrm{1}}<d_{ij}<d_{T\mathrm{2}},\hfill \\ \mathrm{0},\hfill & d_{T\mathrm{2}}\le d_{ij},\hfill \end{array}\end{array}$$

(1)

where the parameters $d_{T\mathrm{1}}$ , $d_{T\mathrm{2}}$ , λ, and β are adjusted according to the physical properties of the sensor. $d_{ij}$ is the Euclidean distance between point i and sensor j.

The above two models do not consider the false alarm rate and signal characteristics. In this paper, we employ the Neyman-Pearson criterion based sensing model [21]. It is assumed that the sensors operate in the presence of additive white Gaussian noise and the noise at each sensor is assumed to be statistically independent. The measurements of sensor j under two different hypotheses are given by

$$\begin{array}{cc}& y_i=\{\begin{array}{cc}\frac{\beta }{R_{ij}^{\gamma /\mathrm{2}}}+n_i,\hfill & H_{\mathrm{1}},\hfill \\ n_i,\hfill & H_{\mathrm{0}},\hfill \end{array}\end{array}$$

(2)

where $y_i$ is the received signal and $n_i$ is the white Gaussian noise. $H_1$ is the target present hypothesis, $H_0$ is the target absent hypothesis, $R_{ij}$ is the distance between point i and sensor j, β is a scalar, and γ is the attenuation coefficient.

The probability density function under $H_0$ and $H_1$ is given by

$$\begin{array}{cc}& P_{ij}\left(y_i\mid H_{\mathrm{0}}\right)=\frac{\mathrm{1}}{\sqrt{\mathrm{2}\pi {\sigma }^{\mathrm{2}}}}\exp \left[-\frac{y_i^{\mathrm{2}}}{\mathrm{2}{\sigma }^{\mathrm{2}}}\right],\\ P_{ij}\left(y_i\mid H_{\mathrm{1}}\right)=\frac{\mathrm{1}}{\sqrt{\mathrm{2}\pi {\sigma }^{\mathrm{2}}}}\exp \left[-\frac{\mathrm{1}}{\mathrm{2}{\sigma }^{\mathrm{2}}}{\left(y_i-\frac{\beta }{R_{ij}^{\gamma /\mathrm{2}}}\right)}^{\mathrm{2}}\right],\end{array}$$

(3)

where σ is the standard variance of the Gaussian noise.

According to the Neyman-Pearson criterion,

$$\begin{array}{l}{L}_i\left(y_i\right)=\frac{P\left(y_i\mid H_{\mathrm{1}}\right)}{P\left(y_i\mid H_{\mathrm{0}}\right)}\\ =\exp \left\{\frac{\mathrm{1}}{\mathrm{2}{\sigma }^{\mathrm{2}}}\left(\mathrm{2}{y}_i\frac{\beta }{R_{ij}^{\gamma /\mathrm{2}}}-{\left(\frac{\beta }{R_{ij}^{\gamma /\mathrm{2}}}\right)}^{\mathrm{2}}\right)\right\}\stackrel{H_{\mathrm{1}}}{\underset{H_{\mathrm{0}}}{\gtrless }}\omega ,\end{array}$$

(4)

where ω is the threshold.

According to (4), we can obtain

$$\begin{array}{cc}& \underset{h}{\underbrace{y_i\frac{{\beta }_k}{R_{ij}^{\gamma /\mathrm{2}}}}}\stackrel{H_{\mathrm{1}}}{\underset{H_{\mathrm{0}}}{\gtrless }}\underset{k}{\underbrace{{\sigma }^{\mathrm{2}}\ln \omega +\frac{\mathrm{1}}{\mathrm{2}}{\left(\frac{\beta }{R_{ij}^{\gamma /\mathrm{2}}}\right)}^{\mathrm{2}}}}.\end{array}$$

(5)

The false alarm rate can be expressed as

$$\begin{array}{cc}& P_F=P\left(h>k\mid H_{\mathrm{0}}\right)=\mathrm{1}-\mathrm{\Phi }\left(\frac{k}{{\sigma }_{\mathrm{1}}}\right).\end{array}$$

(6)

The detection probability $P_D$ is given by

$$\begin{array}{cc}& P_D=P\left(h>k\mid H_{\mathrm{1}}\right)=\mathrm{1}-\mathrm{\Phi }\left({\mathrm{\Phi }}^{-\mathrm{1}}\left(\mathrm{1}-\alpha \right)-\frac{\beta }{\sigma }\sqrt{\frac{\mathrm{1}}{R_{ij}^{\gamma }}}\right),\end{array}$$

(7)

where α is the false alarm probability $\alpha =P_F$ .

The comparison of the three sensing models is shown in Figure 1.

Figure 1

Different sensing models.

A point may be detected by K sensors, so the joint detection probability (JDP) of point i is

$$\begin{array}{cc}& P_i=\mathrm{1}-\prod _{j=\mathrm{1}}^K\left(\mathrm{1}-P_{ij}\right),\end{array}$$

(8)

where K is the number of nodes around point i. $P_{ij}$ is the joint detection probability of point i by sensor j.

3.2. Assumptions and Definitions

The sensing field is divided into a grid of points. The field is divided into a grid Ψ with cells and grid resolution, for example, a $100\times 100$ field with $10\times 10$ cells and the grid resolution $k=10$ . Each cell is represented by a point. In this paper, the grid resolution is $k=1$ . The required definitions for this paper are defined as follows.

Base station is the controller of the networks and it is responsible for initiating the networks setup. And it also stores information about the networks, including a list of nodes. It is responsible for detecting the coverage holes and deciding the number of mobile nodes and the target locations of these mobile nodes to heal the holes.

Static node is the active node when it is initially deployed in the field. It has the ability to collect sensed data, forward message, and process data. Typically, the static node does not move once it is deployed.

Mobile node is the inactive node when it is initially deployed in the field. It not only has the capability of static node but also has mobility. When the network needs to be repaired, the mobile node will move to the desired positions.

Coverage hole is a closed area in which the JDP of the points is lower than 0.01.

Average coverage rate is defined as

$$\begin{array}{cc}& \text{ACR}=\frac{{\sum }_{i=\mathrm{1}}^n{\sum }_{j=\mathrm{1}}^m{P}_{ij}}{n·m}.\end{array}$$

(9)

Consider a wireless sensor network, where the $N_s$ static nodes and $N_m$ mobile nodes are randomly deployed over the 2-dimensional field Ω. The base station is located in the center of the field. As soon as the network is formed, each node knows its location information through the localization method and it sends this information to base station.

The base station calculates the JDP of each grid according to (8). Figure 2 shows the distribution of JDP value in each point.

Figure 2

The distribution of probability in each grid point.

4. Level Set Based Coverage Holes Detection

In this section, we propose a level set based coverage holes detection method that decides the existence of a coverage holes and their size.

The level set method is employed for tracking the motion of the structural boundaries under a speed function and in the presence of potential topological changes. The principal idea is to remove material in regions of low stress and to add material in regions of high stress. A removal rate is established representing a percentage of the maximal initial stress below which material may be eliminated and above which material should be added. The removal rate determines the closed stress contours along which new holes are cut and also the velocity of the boundary motion [22]. One attractive attribute of the level set method is that it gives a natural way of describing closed boundaries, also known as a region representation. Furthermore, it allows for automatic changes of topology, such as merging and breaking, and its calculations can be easily made on a fixed rectilinear grid [23].

Li et al. proposed the local binary fitting (LBF) model [24] which utilized the local information as constraints can segment well objects with intensity inhomogeneities. In this paper the LBF model is used to detect the holes. $I:\Omega \to R$ is the input matrix (the element of the matrix is the JDP in each grid). The level set method could find the coverage hole according to the input matrix. The basic idea of this model is to introduce a kernel function to define the following energy functional:

$$\begin{array}{l}E\left(C,f_{\mathrm{1}},f_{\mathrm{2}}\right)={\lambda }_{\mathrm{1}}{\int }_{\Omega }{\int }_{\text{inside}\left(C\right)}{G}_{\sigma }\left(x-y\right)\\ \hspace{1em}\hspace{1em}\phantom{}\times {\left|I\left(y\right)-f_{\mathrm{1}}\left(x\right)\right|}^{\mathrm{2}}dydx\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}+{\lambda }_{\mathrm{2}}{\int }_{\Omega }{\int }_{\text{outside}\left(C\right)}{G}_{\sigma }\left(x-y\right)\\ \hspace{1em}\hspace{1em}\hspace{1em}\phantom{}\times {\left|I\left(y\right)-f_{\mathrm{2}}\left(x\right)\right|}^{\mathrm{2}}dydx,\end{array}$$

(10)

where ${\lambda }_{\mathrm{1}}$ and ${\lambda }_{\mathrm{2}}>\mathrm{0}$ are the fixed parameters. $G_{\sigma }$ is a Gaussian kernel with standard deviation σ. $f_1$ and $f_2$ are two smooth functions that approximate the local data intensities inside and outside the contour C, respectively.

For level set method, $C\subset \Omega$ can be expressed by the zero level set of Lipschitz function ϕ. Minimizing (10) with respect to ϕ, we have the gradient descent flow as follows:

$$\begin{array}{cc}& \frac{\partial \varphi }{\partial t}=-{\delta }_{\epsilon }\left(\varphi \right)\left({\lambda }_{\mathrm{1}}{e}_{\mathrm{1}}-{\lambda }_{\mathrm{2}}{e}_{\mathrm{2}}\right).\end{array}$$

(11)

In order for stable evolution of the level set function, a regularized distance is incorporated into (11) and the Euclidean length is used to regularize the zero contour of ϕ. So the final gradient flow equation is as follows:

$$\begin{array}{l}\frac{\partial \varphi }{\partial t}=\mu \left(\mathrm{\Delta }\varphi -\mathrm{div}\left(\frac{\nabla \varphi }{\left|\nabla \varphi \right|}\right)\right)+v{\delta }_{\epsilon }\left(\varphi \right)\mathrm{div}\left(\frac{\nabla \varphi }{\left|\nabla \varphi \right|}\right)\\ \hspace{1em}\hspace{1em}-{\delta }_{\epsilon }\left(\varphi \right)\left({\lambda }_{\mathrm{1}}{e}_{\mathrm{1}}-{\lambda }_{\mathrm{2}}{e}_{\mathrm{2}}\right),\end{array}$$

(12)

where we set ${\lambda }_{\mathrm{1}}={\lambda }_{\mathrm{2}}$ . And $e_1$ and $e_2$ are defined as follows:

$$\begin{array}{cc}& e_{\mathrm{1}}\left(x\right)={\int }_{\Omega }{G}_{\sigma }\left(y-x\right){\left|I\left(x\right)-f_{\mathrm{1}}\left(y\right)\right|}^{\mathrm{2}}dy,\\ e_{\mathrm{1}}\left(x\right)={\int }_{\Omega }{G}_{\sigma }\left(y-x\right){\left|I\left(x\right)-f_{\mathrm{2}}\left(y\right)\right|}^{\mathrm{2}}dy,\end{array}$$

(13)

$$\begin{array}{cc}& f_{\mathrm{1}}\left(x\right)=\frac{G_{\sigma }*\left[H_{\epsilon }\left(\varphi \right)I\left(x\right)\right]}{G_{\sigma }*H_{\epsilon }\left(\varphi \right)},\\ f_{\mathrm{2}}\left(x\right)=\frac{G_{\sigma }*\left[\left(\mathrm{1}-H_{\epsilon }\left(\varphi \right)\right)I\left(x\right)\right]}{G_{\sigma }*\left(\mathrm{1}-H_{\epsilon }\left(\varphi \right)\right)},\end{array}$$

(14)

where the standard deviation σ of the kernel is the scale parameter that controls the region scalability from small neighborhood to the whole grids. A too small σ may cause undesirable result, while a too large σ will cause high computational cost [24].

The regularized versions of Heaviside function and Dirac function are utilized as $H_{\epsilon }(\varphi )=(\mathrm{1}/\mathrm{2})[\mathrm{1}+(\mathrm{2}/\pi )\arctan (\varphi /\epsilon )]$ , ${\delta }_{\epsilon }(\varphi )=(\mathrm{1}/\pi )·(\epsilon /({\epsilon }^{\mathrm{2}}+{\varphi }^{\mathrm{2}}))$ . And the parameter ε affects the profile of ${\delta }_{\epsilon }(\varphi )$ .

The pseudocode of the level set based coverage holes detection strategy is shown in Pseudocode 1.

Pseudocode 1

(1) The field is divided into grid. The number of grid points is nm.

(2) Calculate the detection probability of each grid on $p_{ij}$ .

(3) Initial the Level Set ϕ and set the iterative number $t=1$ , the maximum iterative number $t_{\max }=\mathrm{400}$ .

(4) While $t<t_{\max }$

(5)  Calculate the Heaviside function $H_{\epsilon }$ (ϕ).

(6)  Calculate the smooth functions according (13).

(7)  Calculate Dirac function ${\delta }_{\epsilon }$ (ϕ) and $e_1$ and $e_2$ .

(8)  Calculate final gradient flow equation according (12).

(9)  Update the Level Set function $\varphi =\varphi +\partial \varphi /\partial t$ .

(10) End

(11) Find the grid points which $\varphi \left(i,j\right)<\mathrm{0}$ and denotes as φ.

Figure 3(a) shows the deployment of the static nodes. The results of the level set based coverage holes detection are shown in Figure 3(b).

Figure 3

(a) The deployment of the static nodes. (b) The results of the level set based coverage holes detection.

The positions of holes are the set of the grid points which satisfy $\varphi (i,j)<\mathrm{0}$ ; that is, the value in ϕ is less than zero. The candidate grid points set φ is the set of the grid points in which $\varphi (i,j)<\mathrm{0}$ . The number of φ is S. As shown in Figure 3, the number of coverage holes is equal to the number of contours. The coverage holes rate is defined as

$$\begin{array}{cc}& \text{HR}=\frac{S}{n·m}.\end{array}$$

(15)

If the number of coverage holes is larger than a threshold ${\text{NH}}_{\mathrm{tr}}$ or the average coverage rate is less than a threshold ${\text{ACR}}_{\mathrm{tr}}$ , the coverage holes healing strategy should be implemented.

5. Genetic Algorithms Based Coverage Holes Healing

After deciding the existence of the coverage holes and their size, we need to decide the target locations of these mobile nodes to heal the holes. In a hybrid sensor network, one of the movement objectives is maximizing area coverage; that is, after the mobile nodes' movement, the average coverage rate can be greatly increased compared to that of without moving. Another moving objective is to reduce the movement cost, that is, reducing the movement distance. In this section, we introduce how to leverage mobility to optimize the average coverage rate and the average movement distance of the mobile nodes. We firstly convert the coverage holes healing problem into multiobjective optimization problem. Then the genetic algorithms (GAs) [25] are employed to solve this problem. The basic idea of the GAs is to enhance candidate solutions by simulating the mechanisms of natural evolution, such as selection, crossover, and mutation.

A number of variables must be defined before the problem can be clearly described. Let S the number of candidate grid points,  ${\phi }_i$ the position of ith candidate grid points, $N_m$ the number of mobile nodes, and $P_i^M$ the position of the ith mobile node.

Order is the most common representation of chromosomes with combinatorial optimization problems that GAs have to tackle. The length of the chromosome is equal to the candidate grid points. The gene representation is shown as

$$\begin{array}{cc}& X=\left[X_{\mathrm{1}},X_{\mathrm{2}},X_{\mathrm{3}},\dots ,X_S\right].\end{array}$$

(16)

If $X_i=0$ , it means there are none of mobile nodes moving to ith candidate grid points. If $X_i=n$ , it means that nth mobile node moves to ith candidate grid points.

In order to illustrate the gene representation, we provide a simple example: there are 5 mobile nodes and 10 candidate grid points. The gene representation is shown in Figure 4.

Figure 4

An example of gene representation.

The objective function of the coverage healing problem can be stated as

$$\begin{array}{cc}& \mathrm{Min}\hspace{0.17em}F=\frac{{\sum }_{i=\mathrm{1}}^S{\delta }_i\left[{\sum }_{j=\mathrm{1}}^{N_m}{\epsilon }_j\parallel P_j^M-{\phi }_i\parallel \right]}{\text{ACR}},\end{array}$$

(17)

where

$$\begin{array}{cc}& {\delta }_i=\{\begin{array}{cc}\mathrm{1},\hfill & X_i\ne \mathrm{0},\hfill \\ \mathrm{0},\hfill & X_i=\mathrm{0},\hfill \end{array}\\ {\epsilon }_i=\{\begin{array}{cc}\mathrm{1},\hfill & j=X_i,\hfill \\ \mathrm{0},\hfill & j\ne X_i.\hfill \end{array}\end{array}$$

(18)

Even though order representation facilitates GAs to handle combinatorial optimization problems, it also causes an intrinsic constraint in the operation of chromosomes, because no duplicate numbers (except 0) are allowed in a chromosome [26]. Therefore, the traditional crossover and mutation cannot be directly applied to order based GAs. In this paper, we introduce the partially mapped crossover and exchange mutation [27] to solve this problem.

The partially mapped crossover (PMX) operator was suggested by Goldberg and Lingle [28]. The PMX can be regarded as a modification of two-point crossover but additionally uses a mapping relationship to legalize offspring that has duplicate numbers. The PMX operator creates an offspring in the following way. (1) Select uniformly at random two cut points along the parent strings. (2) Select one substring for each parent randomly, and exchange the two selected substrings to produce proto-offspring. (3) Determine the mapping relationship based on the selected substrings. (4) Legalize proto-offspring with the mapping relationship. The zero may map many values. We randomly select some elements whose value is zero in chromosomes X to do the mapping.

The exchange mutation operator randomly selects two elements in the string and exchanges them.

Selection operator is the process of choosing the chromosomes from the current population that will be used to form the next generation by reproduction [25]. And we employ the proportional selection scheme in this paper.

The pseudocode of the genetic algorithms based coverage holes healing algorithm is shown in Pseudocode 2.

Pseudocode 2

(1) Create the initial random population and initialize the iteration $t=1$ and maximum iteration $t_{\max }=\mathrm{60}$ .

(2) while ( $t<t_{\max }$ )

(3)  Evaluate the fitness of all chromosomes in population.

(4)  Select the parents from the population according to the selection scheme for objective function F.

(5)  Mix the selected parents to form a new

(6)  Create the new offspring according the selected parents by partially mapped crossover and exchange

    mutation operators.

(7) End

(8) Evaluate the fitness of all chromosomes in population. And select the chromosomes which own the

  minimum value of objective function F.

6. Performance Evaluation

In this section, some simulation results will be present to show the performance of our proposed algorithms. In this simulation, 140 static nodes and 50 mobile nodes are deployed in a region of size 200 m × 200 m. The level set based coverage holes detection algorithm computes the number of holes and the average coverage rate periodically. If the network needs healing operator, the base station awakens the mobile nodes and arranges the mobile nodes to move to candidate positions to achieve the network healing. We perform the comparative performance analysis of the genetic algorithms based holes healing and the existing Random and Delaunay healing strategies.

Figure 5 shows the relation between the number of mobile nodes and the average coverage probability. We can see that the average coverage probability has saturated when the number of mobile nodes is 45 for Delaunay strategy. And the average coverage probability has saturated when the number of mobile nodes is 30 for the proposed algorithm. Compared with Random and Delaunay strategies, the proposed algorithm needs less mobile nodes to achieve full coverage.

Figure 5

The number of mobile nodes versus average coverage rate.

In Figure 6, we study the impact of the number of mobile nodes on the average movement distance. It can be observed that the number of mobile nodes has a significant impact on the three algorithms. The average movement distance decreases as the number of mobile nodes increases. The proposed algorithm has similar performance with the Delaunay algorithm. So our proposed algorithm achieves higher coverage rate with relatively the same average movement distance when compared with Random and Delaunay strategies.

Figure 6

The number of mobile nodes versus average movement distance.

In Figure 7, we study the relations between the false alarm rate and the average coverage rate when the number of mobile nodes is 20. It can be observed that the average coverage rate decreases as the false alarm rate increases. The proposed algorithm has achieved higher average coverage rate than Random and Delaunay strategies.

Figure 7

The false alarm rate versus average coverage rate.

The impact of false alarm rate on the average movement distance is investigated in Figure 8. It can be observed that the false alarm rate has very little impact on average movement distance.

Figure 8

The false alarm rate versus average movement distance.

7. Conclusions

In this paper, we investigated the coverage holes detection and healing problem for hybrid sensor network which consists of mobile nodes and static nodes. We firstly introduced a Neyman-Pearson criterion based sensing model. Based on the level set method, we proposed a novel coverage holes detection algorithm. This algorithm could estimate the number of holes and their size. We also proposed a genetic algorithm based coverage holes healing algorithm. Simulation results show that our proposed algorithm achieved higher coverage rate with less movement distance in comparison with uniform and Delaunay algorithms.