Strong k -Barrier Coverage for One-Way Intruders Detection in Wireless Sensor Networks

Abstract

Intruders detection is one of the very important applications in Wireless Sensor Networks (WSNs). Sometimes detecting intruders is not sufficient; distinguishing whether an intruder is legal or illegal is necessary. Since k-barrier coverage is widely used in detecting intruders, a barrier construction algorithm is needed, which can not only detect an intruder but also judge an illegal intruder. An intruder is defined as illegal if and only if it crosses straightly through the monitored region from the special side to another side. On the contrary, it is a legal intruder. To detect an intruder and distinguish whether the intruder is legal or illegal, a strong k-barrier coverage algorithm is proposed. The strong k-barrier coverage is a local barrier constructing algorithm and can detect any intruder crossing the k-barrier with a full probability. The strong k-barrier coverage detects all intruders penetrating the annular region for k times. What is more, the proposed strong k-barrier algorithm can provide a reliable judgement on whether an intruder is legal or illegal, and the constructed k-barrier coverage is different from the traditional one-way barrier coverage using binary barriers that are intersected but not overlapped. Some simulation tests show that the proposed algorithm can construct strong k-barrier coverage very well.

1. Introduction

Wireless Sensor Networks (WSNs) have been studied for years, which have many important applications for their particular capabilities in monitoring environment, such as in a battlefield or in an international border; all these circumstances need a comprehensive monitoring. Barriers in WSNs for intruders detection have been studied a lot, which can assure that all intruders crossing a belt annular can be detected. In some applications, only one direction crossing the region is illegal. For example, people can leave a theater without their movie tickets being detected, whereas they are not allowed to see a movie without tickets. In the above applications, it is not appropriate to use the traditional barrier coverage models since they cannot distinguish the legal and illegal intrusion behaviors.

In most previous works, researchers only considered whether or not WSNs can form barrier coverage or whether WSNs provide k-barrier coverage. The theoretical basis of designing barriers of WSNs is studied in [1]. In one barrier coverage, intruders may cross the barrier from the gap without being detected. Since one barrier coverage cannot meet the requirements of intrusion detection in many applications, high degree of coverage must be taken into account, and the reasons of requiring k-barrier rather than 1 barrier are discussed in [1]. A weekly k-barrier coverage has been studied in many literatures, such as [2]. For some applications of WSNs, weekly k-barrier coverage is not enough; thus the strong k-barrier coverage is needed, for example, a WSN with a really high detecting probability. Detecting intruders with highly probability relies on a strong barrier coverage.

In the study of barrier coverage, construction algorithms for barrier have been researched much. Generally speaking, there are two kinds of research directions, local barrier construction and the global barrier construction algorithms. Though global barrier coverage, such as the one in [3], which requires much fewer sensors than full coverage, is a befitting model of coverage for intrusion detection, it also has limitations. Then a local barrier coverage algorithm is studied intensively in [4–7].

Our contributions in this paper are as follows:

• (1)

We find that traditional one-barrier coverage model is not suitable for some applications of WSNs in intruders detection, especially in one-way intruders detection.

(2)

Comparing the previously binary barriers models, we consider using a k- (more than 2) barrier model to achieve the one-way intruders detection, which does not need to satisfy the conditions in binary barrier model.

(3)

We propose a k-barrier coverage algorithm, which can easily construct k barriers in monitored areas; then we use the formed k-barrier coverage model to realize the goal of one-way intruders detection without satisfying the limitations of binary barriers coverage.

The remainder of the paper is organized as follows. Section 2 introduces the related work. Then the system model, the barrier construction algorithm, and the barrier mending model are presented in Section 3. Section 4 shows an important application of our model. The simulation results are presented in Section 5. Finally, conclusion of this paper is presented in Section 6.

2. Related Work

The authors in [1] research the mathematical conditions of building a weak barrier coverage in randomly deployment WSNs and devise a centralized algorithm to determine whether a region is k-barrier covered. In literatures [8–11], the authors study barrier coverage intensively. The authors in the literature [12] suppose the situation of one barrier, and they study an energy-efficient border intrusion detection algorithm, with measuring and guaranteeing the coverage quality of WSNs.

In [2], the authors introduce a weak k-barrier coverage problem by at least k sensors in a belt region and propose a simple algorithm to determine whether a belt region is weakly k-barrier covered. The strong barrier coverage of WSNs is introduced in [9], which is a model with a really high probability to detect intruders. The authors in [13] describe the worst- and best-case coverage calculation for homogeneous isotropic of WSNs, in which they combine the Voronoi diagram and graph search algorithm. In literatures [14, 15], the authors present a fundamental geometric data structure of the Voronoi diagram, which present us with a preliminary knowledge of the Voronoi diagram. Sometimes it is not sufficient for weak k-barrier coverage. In the literatures [16–18], the strong barrier coverage has been researched deeply. And the authors propose the minimum and maximum exposure path algorithms, respectively. The minimal exposure path is thought to be the worst-case coverage of WSNs, which is a weak barrier coverage. On the contrary, the maximum exposure is best-case coverage of WSNs.

The authors in [4–7] consider that the sensors cannot locally determine whether the sensor deployment provides global barrier coverage. So the authors present a localized sleep-wake-up algorithm for maximizing the network lifetime. Barriers in the above literatures are all presented in one-dimensional space. In the literatures [19, 20], a k-barrier scheduling for the intruder detection in 2-dimensional space is introduced. The authors propose a distributed scheme whose target is providing low detection delay and low energy. Considering that the detection delay and low energy at the same time are a challenge, it is essential to consider them in multidimensional space. Besides, a new concept of one-way barrier coverage with wireless sensors has been introduced in [21–23], and the authors propose the concept of one-way barrier and establish a necessary condition for WSNs to provide a one-way barrier coverage, which requires that WSNs report illegal intruders but ignore the legal ones. However, the two barriers, which are intersected but not overlapped, are limited in binary barriers.

Motivated by works of the above literatures, we propose to use k-barrier coverage of WSNs to replace the previous binary barriers to achieve the one-way detection while achieving the same goal in the literatures [21–23]. A strong k-barrier coverage algorithm is proposed, which is a local barrier algorithm and can detect any intruders crossing the k-barrier with a full probability, assuring that all intruders penetrating the annular region can be detected k times. Furthermore, the proposed k-barrier model can make a reliable judgement on whether an intruder is legal or illegal, which is different from the traditional one-way barrier coverage. When compared with the algorithm proposed in [24] and another sensor deployment, the number of sensors is much less.

3. System Model

3.1. Network Model

This paper assumes that sensors are deployed in an annular region to detect intruders which try to cross straightly through the monitored region and to report the illegal intruders. An illegal intruder is an intruder crossing through the monitored area from the special side to the other side. If not, it is a legal intruder on opposite moving direction. In this section, we give some basic definitions for the annular region. The annular region is a special case of a belt region whose two left and right boundaries coincide with each other while its two upper and lower boundaries are parallel, as shown in Figure 1. In addition, some definitions about k-barrier coverage are given. In Figure 1, we can see that it is combined with two concentric rings, with the radius of outer ring being $R_O$ and inner ring being $R_I$ , respectively. The center of the area is marked as O, and its coordinate is known as $(x_O,y_O)$ .

Figure 1

The initial wireless sensor network; sensors are distributed as the Gaussian distribution.

The sensors are deployed following the Gaussian deployment, and the total number of sensors is N. Each sensor has an identical sensing radius $r_s$ , and the coverage model of a sensor is called a disk model. When an intruder is in the sensor's sensing range, the intruders can be detected with full probability. On the contrary, the intruders cannot be detected. The disk model usually adopts the Voronoi diagram to evaluate the detection possibility. In the literatures [14, 15], the Voronoi diagram has been well studied. Besides, the number of sensors in each single ring is different, and the number of sensors deployed in each ring increases in proportion to the circumference of each ring, which is shown in (3). The locations of sensors or their coordinates can be obtained by GPS. Sensors can communicate with each other while the distance between them is in the communication radius $R_c$ . $R_c\ge \mathrm{2}{r}_s$ , where $r_s$ is the sensing radius of a sensor.

Definition 1 (annular belt region).

A region bounded with two up and down parallel curves and two overlapping right and left boundary curves is called an annular belt region.

Definition 2 (barrier).

A barrier is a sensor group with sensing area overlap to form a belt coverage region starting from the left boundary to the right. There might be more than one barrier in belt region.

Definition 3 (k-barrier coverage).

A circular region is referred to as k-barrier coverage if and only if any intruders crossing through the region can be detected k times by the WSNs.

Definition 4 (traditional 2-barrier coverage model).

It is a model with two barriers whose lower boundary of one barrier and upper boundary of the other barrier overlap.

Definition 5 (global and local barriers).

Global barrier means that sensors can know a global knowledge of WSNs to build a barrier; on the contrary, local barrier is defined as a barrier; the constructing sensors of the barrier only know a local background of WSNs.

Definition 6 (strong barrier coverage and weak barrier coverage).

A weak barrier has at least one gas and a strong barrier has no gap, so that no intruders can cross the monitored area without being detected no matter what crossing paths intruders would choose, but there is at least one safety path that intruders could cross the monitored area without being detected.

Definition 7 (alarm line).

An alarm line is the bottom line (or curve) of the innermost barrier, which will report an alarm when an intruder crosses the alarm line from the other barriers to the inner of region but does not report any alarm whenever an intruder crosses the line from the inner region to the outer region.

Definition 8 (one-way barrier coverage).

A circular region over which sensors are deployed is defined as one-way barrier covered if and only if whenever an intruder crosses the monitored region from the outer ring to the inner ring, and at least one sensor reports an alarm; otherwise, there is not any.

In this paper, we consider a belt region with its two approximate vertical boundaries being overlapped, that is, a circular region in Figure 1. The network model shown in Figure 2 describes the loop dividing, and the monitored area S is divided into k equal concentric loops, which can be expressed as

$$\begin{array}{cc}& d_w=\frac{\left(R_O-R_I\right)}{k},\end{array}$$

(1)

where k is the required parameter predesigned. Assume that all sensors know their local coordinates, and the coordinate of the center point O is known. Each sensor can communicate with its neighbor sensors within its communication range. Considering a sensor $N_u$ , whose coordinate is $\left(x_u,y_u\right)$ , a set of its neighbor sensors is marked as $N(u)=\{u_{\mathrm{1}},u_{\mathrm{2}},\dots ,u_t\}$ , $0<t<n$ . As shown in Figure 2, the blue rings represent the inner and outer rings, and the black rings represent the divided virtual rings.

Figure 2

The loop dividing figure, where the blue lines are the dividing line, and the black lines are the two borders, and k is preset in our opinion, and $k\ge \mathrm{2}$ .

3.2. Strong k-Barrier Construction Algorithm

In this section, we propose an algorithm to achieve k-barrier coverage, which needs much less sensors in building barriers. As mentioned the part of network model, the monitored area is a circular area, which is divided into k equal parts. In addition, the way of building every barrier is identical in each part. The construction of one barrier is introduced as follows, such as the innermost circular loop, and others do the same.

There are two steps in the barrier construction algorithm. The first step is to assign some basic information to sensors and let them know the information of their neighbors' locations. Then the other step is to find the remaining sensors used in building a barrier.

3.2.1. Information Assignment

In this step, we divide the S into k equal parts, and, in every part, a barrier is going to be designed, as shown in Figure 2. Since the total number of sensors is N, we suppose that the number of sensors in the innermost ring is n, and the number of other circular rings increases according to the circumference of each ring. Suppose that circumference of the innermost ring is $c_i$ , and the circumference of adjacent outer ring is $c_{i+\mathrm{1}}$ , and the radii of sensors are $r_i$ and $r_{i+\mathrm{1}}$ , respectively. Then the relationship of the radii is given by

$$\begin{array}{cc}& r_{i+\mathrm{1}}=r_i+d_w,\end{array}$$

(2)

where $d_w$ is described in (1). These variables get the following formulation:

$$\begin{array}{cc}& \frac{n_i}{n_{i+\mathrm{1}}}=\frac{c_i}{c_{i+\mathrm{1}}}=\frac{\mathrm{2}\pi \left(r_i\right)}{\mathrm{2}\pi \left(r_{i+\mathrm{1}}\right)}=\frac{r_i}{r_{i+\mathrm{1}}},\end{array}$$

(3)

where $n_i$ and $n_{i+\mathrm{1}}$ are the numbers of sensors deployed in two adjacent circular rings deployed as the Gaussian distribution. Moreover there is

$$\begin{array}{cc}& n_{\mathrm{1}}+n_{\mathrm{2}}+\cdots +n_k=N.\end{array}$$

(4)

Previous sections have mentioned that the coordinates of sensors are known, which are marked as $\left(\left(x_{\mathrm{1}},y_{\mathrm{1}}\right),\dots ,\left(x_n,y_n\right)\right)$ . One of the limitations is the Euclidean distance between two adjacent critical sensors; that is,

$$\begin{array}{cc}& d\left(x_{\mathrm{1}},x_{\mathrm{2}}\right)=\sqrt{{\left(x_{\mathrm{1}}-x_{\mathrm{2}}\right)}^{\mathrm{2}}+{\left(y_{\mathrm{1}}-y_{\mathrm{2}}\right)}^{\mathrm{2}}}.\end{array}$$

(5)

And it must satisfy the following condition:

$$\begin{array}{cc}& d\left(x_{\mathrm{1}},x_{\mathrm{2}}\right)\le \mathrm{2}{r}_s,\end{array}$$

(6)

where $\mathrm{2}{r}_s$ is the critical condition for building an effective barrier; the ultimate goal of our paper is to detect foreign invaders. If $d\left(x_{\mathrm{1}},x_{\mathrm{2}}\right)>\mathrm{2}{r}_s$ , there will be a gap in the barrier; then it has to miss some invaders. $\mathrm{2}{r}_s\le R_c$ is to keep the WSNs connecting and to ensure that adjacent sensors can communicate with each other.

3.2.2. Barrier Construction Algorithm

The last step is specific to constructing the barrier. Firstly, we randomly find a starting sensor and search the next satisfying sensor in turn. In order to simplify the operation, we do the search along the clockwise. Equation (6) describes the distance limitation of two adjoining sensors, but it cannot help us find the ideal candidate sensor. Then at least one more condition is really needed, which is the angular restriction. Noting that, we consider the polar coordinates of sensors. The specific expression of a sensor $N_u$ is as follows:

$$\begin{array}{cc}& x_u={\rho }_u\cos {\theta }_u\\ y_u={\rho }_u\sin {\theta }_u,\end{array}$$

(7)

where ${\rho }_u$ is the polar radius and ${\theta }_u$ is the polar angle. Since the coordinate $(x_u,y_u)$ of a sensor is known, the center point O is supposed as the pole, whose rectangular coordinate is described as $\left(x_O,y_O\right)$ , and we can transform the rectangular coordinate to the pole coordinate.

When finding the next sensor, it is not necessary to search it in global scope because we have to construct k strong barriers, which has no gap between two adjoining sensors. To satisfy the distance limitation, that is, (6), it must be in the polar angle $\Delta \theta$ interval, which is a constant value. As shown in Figure 3, the maximum polar angle to find the candidate sensor is described in detail. There are two tangent disks along clockwise, whose centers are $N_m$ and $N_{m+\mathrm{1}}$ , respectively. Since radius of S is big enough for the radii of sensors, the length of arc between $N_m$ and $N_{m+\mathrm{1}}$ is as approximate as the Euclidean distance $\mathrm{2}{r}_s$ .

Figure 3

Graph of the next sensor in the maximum polar angle. $r_s$ is the sensing radius of sensors, $R_i$ is the innermost radius of the circular ring, and $\Delta \theta$ is the same in each single circular rings.

In the triangle $\Delta \left(N_{m}O{N}_z\right)$ , $N_z$ is the intersection of the center line $N_m{N}_{m+\mathrm{1}}$ and circle $N_{m+\mathrm{1}}$ , and rectangular coordinate is known as $(x_z,y_z)$ . $\Delta \theta =\mathrm{4}\pi /⌈\pi r\left(m\right)/r_s⌉$ is the approximate maximum polar angle interval, which can be obtained by using the Cosine theorem; that is,

$$\begin{array}{cc}& \cos \Delta \theta =\frac{d_{N_{m}O}^{\mathrm{2}}+d_{N_{z}O}^{\mathrm{2}}-d_{N_m{N}_z}^{\mathrm{2}}}{\mathrm{2}{d}_{N_{m}O}{d}_{N_{z}O}}.\end{array}$$

(8)

Then we can get $\Delta \theta$ as follows:

$$\begin{array}{cc}& \max \left(\Delta \theta =\arccos \frac{d_{N_{m}O}^{\mathrm{2}}+d_{N_{z}O}^{\mathrm{2}}-d_{N_m{N}_z}^{\mathrm{2}}}{\mathrm{2}{d}_{N_{m}O}{d}_{N_{z}O}}\right),\end{array}$$

(9)

where $d_{N_m{N}_z}=\mathrm{3}{r}_s$ and $d_{N_m}$ , $d_{N_{\mathrm{2}}O}$ can be calculated by using (5), and in every circular ring $\Delta \theta$ is a constant value, which is just different from the polar radius. Equation (9) is another condition to find the next candidate. The angle interval diagram is shown in Figure 3. Then the remaining sensors can be found to construct barriers in the same way as before. At the same time, we will implement this method in other rings. But while constructing the barrier, there may be a situation that such a satisfying candidate sensor cannot be found regardless of any efforts, so we have to dissolve this barrier.

In our k-barrier coverage algorithm, we can calculate the minimal amount of nodes that can be used to create a k-barrier deployment. It is a variable changing with the perimeter of ideal barriers and the sensing radius of sensor nodes. Let us take $n_{\mathrm{m}\mathrm{i}\mathrm{n}}$ as the minimal amount of nodes, and $r\left(i\right)$ is the radius of the ideal barriers, $i=\mathrm{1,2},\dots ,k$ ; then the formula is as follows:

$$\begin{array}{cc}& n_{\mathrm{m}\mathrm{i}\mathrm{n}}=⌈\frac{\pi ·r\left(i\right)}{r_s}⌉.\end{array}$$

(10)

And the degree of redundancy of deployed nodes in each circular is at least six times of the minimal amount of nodes. When the degree is larger than six, our algorithm can construct k-barrier coverage more easily. The number of sensors nodes deployed in each single circular rings is marked as $n_i$ , $n_i=\mathrm{6}·n_{\mathrm{m}\mathrm{i}\mathrm{n}}$ , $i=\mathrm{1,2},\dots ,k$ . The six times is not literally designed; it is achieved by many times of simulation.

The computational complexity of the proposed algorithm is marked as $O\left(f\left(n\right)\right)$ , which is relative with k, Z and $X_Z$ . Z is the maximal times of each searching in theory; $X_Z$ is the actual searching number:

$$\begin{array}{cc}& O\left(f\left(n\right)\right)={\displaystyle \sum }_{m=\mathrm{1}}^k\left\{c_{\mathrm{1}}+\mathrm{5}{c}_{\mathrm{2}}+\mathrm{3}{c}_{\mathrm{3}}+{\displaystyle \sum }_{p=\mathrm{1}}^Z\left[c_{\mathrm{6}}+{\displaystyle \sum }_{q=m+\mathrm{1}}^X\left(\mathrm{4}{c}_{\mathrm{1}}+A_{\mathrm{1}}{c}_{\mathrm{2}}+\mathrm{9}{c}_{\mathrm{3}}+A_{\mathrm{2}}{c}_{\mathrm{6}}+A_{\mathrm{3}}·c_{\mathrm{7}}+\mathrm{2}{c}_{\mathrm{8}}+c_{\mathrm{9}}\right)\right]\right\}.\end{array}$$

(11)

$Z_{\mathrm{1}}$ , $Z_{\mathrm{2}}$ , $Z_{\mathrm{3}}$ are variables satisfying some conditions. $c_{\mathrm{1}}$ represents an identity matrix. $c_{\mathrm{2}}$ represents a variable assignment. $c_{\mathrm{3}}$ represents a constant assignment. $c_{\mathrm{4}}$ represents a comparison. $c_{\mathrm{5}}$ represents a multiplication. $c_{\mathrm{6}}$ represents a addition. $c_{\mathrm{7}}$ represents a square root. $c_{\mathrm{8}}$ means taking the absolute value. The details of our k-barrier are shown in Algorithm 1.

Algorithm 1: A strong k-barrier construction algorithm.

Require:   $r_s$ = the sensing radius of a sensor; $R_c$ = the communication radius between two adjacent nodes; $m_i$ = the number

of sensors deployed following the Gaussian deployment in the $i_{\mathrm{t}\mathrm{h}}$ circular ring; $R_O$ = the outer radius; $R_I$ = the inner

radius; $d(n_i,n_j)$ = the Euclidean distance between sensor $n_i$ and $n_j$ ;   $\mathrm{\Delta }x$ = the searching radius, which is a positive

discrete number;  k = the barrier number.

Ensure:   $m_{\mathrm{1}}$ is the number of sensors deployed in first circular ring according to the Gaussian distribution, set as

    $A=(x_{\mathrm{1}},x_{\mathrm{2}},\dots ,x_{m_{\mathrm{1}}})$

while   $z=\mathrm{1}$   do

   $n_{\mathrm{1}}$ is the starting sensor, its polar coordinates is

   $\left(x_{\mathrm{1}},y_{\mathrm{1}}\right),\hspace{0.17em}\hspace{0.17em}{x}_{\mathrm{1}}=r\left(i\right)\cos {\theta }_m,\hspace{0.17em}\hspace{0.17em}{y}_{\mathrm{1}}=r\left(i\right)\sin {\theta }_m.\hspace{0.17em}\hspace{0.17em}i=\mathrm{1,2},\dots ,k,\hspace{0.17em}\hspace{0.17em}r(i)~N(r(m)+w/\mathrm{2},\mathrm{d}\mathrm{e}\mathrm{l}\mathrm{t}\mathrm{a}),{\theta }_m=$

   ${\theta }_i~U(\mathrm{0,2}\pi ),\hspace{0.17em}\hspace{0.17em}r(i)=ri+(i-\mathrm{1})\ast w,\hspace{0.17em}\hspace{0.17em}w={(R}_O-R_I)/k$ .

end while

repeat

  search the next satisfying sensor, $n_z\in A$

until   $z\le m_{\mathrm{1}}$ , max $\hspace{0.17em}\hspace{0.17em}d(n_{z-\mathrm{1}}{n}_z)\le \mathrm{2}{r}_s$ , $\mathrm{m}\mathrm{a}\mathrm{x}\hspace{0.17em}\hspace{0.17em}\mathrm{\Delta }\theta$ ,

          $\mathrm{\Delta }\theta =\frac{\mathrm{4}\pi }{⌈\pi r\left(i\right)/r_s⌉}$

if   $d(n_z{n}_{z+\mathrm{1}})\ge \mathrm{2}{r}_s$ , or $\mathrm{m}\mathrm{a}\mathrm{x}\hspace{0.17em}\hspace{0.17em}\mathrm{\Delta }\theta \ge \mathrm{4}\pi /⌈\pi r\left(i\right)/r_s⌉$   then

  break, fail to find sensor $n_z$

end if

if   $\mathrm{m}\mathrm{a}\mathrm{x}\hspace{0.17em}\hspace{0.17em}\mathrm{\Delta }\theta \le \mathrm{4}\pi /⌈\pi r\left(i\right)/r_s⌉,\hspace{0.17em}\hspace{0.17em}z\le m_{\mathrm{1}}$   then

   turn to next step

   if   $d{n}_{\mathrm{2}}{n}_{\mathrm{1}}\le \mathrm{2}{r}_s$   then

    successfully find the next sensor

   end if

end if

go back to repeat to find the next valid sensor;

while the number of sensors $n_s$ in one barrier is equal to

the minimal number $n_{\mathrm{m}\mathrm{i}\mathrm{n}}=⌈\mathrm{2}\pi r(i)/\mathrm{2}r(s)⌉$   do

if   $d_{n_{\mathrm{m}\mathrm{i}\mathrm{n}}{n}_{\mathrm{1}}}\le \mathrm{2}{r}_s$ , then

  succeed in building a barrier, break;

else

   $d_{n_{\mathrm{m}\mathrm{i}\mathrm{n}}{n}_{\mathrm{1}}}\ge \mathrm{2}{r}_s$ , continue to find the next valid senor, then

  go back to step before two steps;

  end if

end while

3.3. Barrier Mending Model

3.3.1. Energy Model

After running for a certain time, nodes failure may be an unavoidable problem by running out of energy or by some physical damage. In previous works, most of them consider the remaining energy of an individual sensor, which can be a good way to decide whether a barrier needs to be mended. As one sensor fails, the barrier will be destroyed. In this paper, we consider a strong k-barrier coverage, which should detect all intruders permeating the monitored area almost being detected k times. Once a hole appears in a barrier, intruders may pass through the barrier without being detected. Gap is the crack without any barrier detecting an intruder's incursion.

To maintain the monitoring quality, a barrier mending model is required. We can get the remaining energy (described as $E_r$ ) of sensors as follows:

$$\begin{array}{cc}& E_r={\displaystyle \sum }_{i=\mathrm{1},j=\mathrm{1},i\ne j}^{n_i}{E}_i-\left[\left(e_i^R+e_i^T\right)·d_{ij}^R-e^S\right]·\left(t_i\right),\end{array}$$

(12)

where $e_i^R$ and $e_i^T$ are energy for receiving and transmitting one unit data, respectively; they all decline with the distance $d_{ij}$ between two adjacent sensors i and j, $i,j=\mathrm{1,2},\dots ,n$ . And α is the parameters of signal decline. $e^S$ is energy required for sensing one unit data. $E_i$ is the initial energy reserve of ${\mathrm{s}\mathrm{e}\mathrm{n}\mathrm{s}\mathrm{o}\mathrm{r}}_i$ . $t_i$ is the network lifetime of ${\mathrm{b}\mathrm{a}\mathrm{r}\mathrm{r}\mathrm{i}\mathrm{e}\mathrm{r}}_i$ ; when (12) is equal to zero, the network lifetime of barrier is achieving the upper bound. We can get the distance of two neighboring sensors by the GPS. We quote (12) from the literature [24]. We can use (12) to calculate the lifetime of a single barrier. And the lifetime of a barrier is related to both the number of overlapping sensors ( $P{O}_i$ ) in a barrier and the coverage ratio ( $P{C}_i$ ) of a barrier:

$$\begin{array}{cc}& {\text{work time of barrier}}_i=P{O}_i·P{C}_i.\\ P{O}_i=\frac{{\text{the number of overlap sensor}}_i}{{\text{the total number in barrier}}_i}.\\ P{C}_i=\frac{\text{a certain barrier coverage area}}{\text{maximum coverage area}}.\end{array}$$

(13)

Then we can get relationship between network lifetime and coverage ratio. Assuming that T is the work time of network, we can get the relationship as follows:

$$\begin{array}{cc}& t_i=\frac{P{O}_i·P{C}_i}{{\sum }_{i=\mathrm{1}}^{k}P{O}_i·P{C}_i}·T.\end{array}$$

(14)

Once the remaining energy of a sensor is equal to zero, it means that the sensor is dead. Two neighboring sensors around the sensor in the same barrier can detect its failure. The two neighboring sensors can transmit information to each other. The previous sensor before the dead one in the barrier has to find another sensor to replace the dead one. At the same time, the replacement sensor connecting with the latter sensor of the dead sensor in the barrier mending model must satisfy some requirements. In other words, the new barrier can monitor one line of the field and no intruders can pass through the line without being detected. In other words, the new barrier can monitor one line of the field and no intruder can pass through the line without being detected. There are some limitations needing to be satisfied. The limitations are the Euclidean distance between the dead sensor and the replacement sensor and the distance between the replacement sensor and the latter sensor. These distances all must be shorter than two times the sensing range, whereas the Euclidean distance between the dead sensor and the latter sensor should be shorter than the communication range $R_c$ . The mathematical expressions are $d_{\mathrm{N}\mathrm{2}\mathrm{N}\mathrm{3}}\le (\mathrm{2}{r}_s)$ , $d_{\mathrm{N}\mathrm{3}\mathrm{N}\mathrm{5}}\le (\mathrm{2}{r}_s)$ , $d_{\mathrm{N}\mathrm{2}\mathrm{N}\mathrm{5}}\le R_c$ , $R_c=\mathrm{2}{r}_s$ . As shown in Figure 4, sensors N0, N1, N2, N3, N5, and N9 belong to the same barrier, and these sensors monitor one of the circular rings of the interested area. Suppose that sensor N3 is dead, and both sensors N2 and N5 can detect its failure. Since N2 is the previous sensor, it is responsible for finding the replacement sensor N4 according to the following rules. Then N2 sends N4 a flag message, tells N4 the remaining energy of N3, and judges whether it should wake up immediately or later. If yes, the sensor N4 sets the flag = 1 and sends it to senor N2. If no, the sensor N4 sets flag = 0, and it keeps sleeping. After N2 and N5 receive the message flag = 1, they will know that the replacement sensor will join the barrier to keep it working effectively. The new barrier becomes N0, N1, N2, N4, N5, and N9.

Figure 4

An example of barrier reconstruction.

Since the remaining energy of each sensor can be calculated according to (10), there is $E_r=\eta E_i$ , where η is a small mathematical variable less than 1, and it can be calculated at every working time. η change with the time being spent on communication with the neighbor sensors is worth discussion. As our barrier constructing algorithm is a real-time communicating algorithm, the communication time can really be ignored; then η can be set as zero or nearing zero.

The procedure of finding a replacement sensor should satisfy the following rules.

Rule 1.

The previous sensor should select the replacement one among the nearest neighborhoods in its ring, while they are free to use.

Rule 2.

If such a suitable sensor is not found, we can borrow a suitable replacement one to form the other rings.

Rule 3.

If no sensor can be found based on the above two rules, the current barrier cannot be mended; then we release the remaining sensors, which become redundant sensors and are free to help other barriers in case some sensors fail.

3.3.2. A Barrier Health System

The remaining energy of the dying ${\mathrm{s}\mathrm{e}\mathrm{n}\mathrm{s}\mathrm{o}\mathrm{r}}_i$ is $E_{r_i}$ ; when it satisfies the condition that $E_{r_i}=A·E_i$ , its neighbor nodes need to search an alternative node for it. A is a least coefficient of the initial energy reserve of ${\mathrm{s}\mathrm{e}\mathrm{n}\mathrm{s}\mathrm{o}\mathrm{r}}_i$ , which is relative with the distance ( $d_{ij}$ ) between two neighbor nodes, and the speed of data transmission. The Euclidean distance between two neighbors can be calculated according to their coordinates, and the coordinates can be obtained by GPRS.

Suppose that the speed of data transmission is equal, marked as v. Then the time of data transmission between the dying node and its neighbor nodes is $t_{ij}$ . $t_{ij}=\left(d_{ij}/v\right)t_{jk}=d_{jk}/v$ ; they describe the time of date transmitting from two neighboring nodes i, j, and j, k. And sensor i represents the dying sensor node:

$$\begin{array}{cc}& A_{\mathrm{m}\mathrm{i}\mathrm{n}}=\frac{\left[\left(e_i^R+e_i^T\right)·d_{ij}-e^S\right]·\left(t_{ij}+t_{jk}\right)}{E_i}.\end{array}$$

(15)

The remaining energy of the dying node is at least $A_{\mathrm{m}\mathrm{i}\mathrm{n}}$ times the initial energy of ${\mathrm{s}\mathrm{e}\mathrm{n}\mathrm{s}\mathrm{o}\mathrm{r}}_i$ ; its neighbor sensor nodes need to find its alternative node. Only, in this way, we may ensure that the neighbors can find an alternative node before the dying node dies.

And an actual protocol that can be used to send the alerts to the base station is in reference [6]. In [6], nodes in a cooperative node group will be considered as opponents to each other; therefore, each node will maintain a Q-value which reflects the payoff that would have been received if that node selects one action and the other nodes jointly selected the other action. After that, the node with the highest total payoff will be elected to forward the data packet to the next cooperative node group towards the sink node.

4. Practical Application

This part presents the application of our WSNs in one-way intruders detection. By using the barrier construction algorithm proposed in this paper, a k-barrier coverage can be finally achieved as an ideal situation, as shown in Figure 5. Since the sensors in our network are distributed following the Gaussian distribution when $\mu =\mathrm{0}$ , $\sigma =\mathrm{1}$ , we can construct the preset k-barrier coverage very well by using our algorithm. In the former section, it shows that the barriers are almost constructed in the center of every circular ring. After k-barrier bridges being constructed perfectly, they will be ultimately used in a practical application which is called one-way barrier coverage. That is to say every single intruder crossing straightly through the monitored area can be detected to be legal or illegal.

Figure 5

Application of one-way barrier in detecting different intruders. s1 and s2 are the trajectories of crossing straight through the monitored area and s3 is the trajectories of incompletely crossing line.

Previous works using barriers to provide one-way barrier coverage have been studied a lot. A new coverage model called one-way barrier was firstly proposed in [6]. It proposed the concept of neighboring barriers and designed different protocols to provide one-way barrier coverage for different sensor models based on neighboring barriers. In addition, a one-way barrier coverage has been proposed in [19], and the single intruder has been considered in [19]. But when used to detect multiple intruders, it is not so effective.

In this section, the model is used to detect the illegal and legal intrusion. We also need to set an alarm line like in [6, 7, 19]. But there is little different between the alarm line in this paper and in literatures [6, 7, 19] because the barriers in [6, 7, 19] are two neighboring barriers which have a continuous overlapping region. There are two special barriers. However, in our WSNs, the above limitations are not necessary conditions. This is an improvement we have made. Our detection system is shown in Figure 5. In the monitored area, it has formed k-barrier coverage being described by the black rings with arrows. This situation is the ideal situation and the direction of arrows is the direction of building barriers. In fact, it does not matter how k-barrier coverage is constructed by using our algorithm; k has to be more than two. When k is equal to two, our algorithm is just the neighboring barriers proposed in [6, 7, 19]. That is to say, it is a special situation of our model.

4.1. One Intruder

Obviously, WSNs with only one barrier cannot furnish one-way barrier coverage. As mentioned before, two barriers can provide one-direction barrier coverage, but it must follows some special assumptions, such as the limitations mentioned in literatures [21–23]. This paper concentrates on using k-barrier coverage to achieve the same goal. Here we suppose that there is only one intruder crossing the annual region. As shown in Figure 5, there are three possible paths that one intruder may follow. For example, the three red dotted lines with arrows are some possible invasion paths of the intruders in Figure 5, described as s1, s2, and s3, respectively.

We assume that intruders penetrating straightly through the circular monitored area from outside to inner region are illegal intruders, which need to be detected. In practical situation the circular monitoring area is like an isolation belt, and only the intruders thoroughly penetrating the area from outside to inside need to be broadcast, such as s1. On the contrary, intruders not thoroughly penetrating the monitoring area or penetrating the area from the inside to outside are thought to be legal, like the paths s2 and s3 in Figure 5. In order to distinguish the illegal intruders, we quote the notion of alarm line in literature [6]. And the alarm line in [6] is a little different from to the one in this paper. An alarm line here is a line or curve along the belt with the following property: the network reports an alarm whenever an intruder crosses the alarm line from outside to inside, but it does not report any alarm when an intruder crosses the line from inside to outside. The bottom line of the innermost barrier of WSNs is chosen as the alarm line.

Here we take k-barrier as an example. When an intruder thoroughly penetrates the monitoring area and enters into the protected region, the intruder will be detected k times and will trigger the alarm line. It is illegal that the intruder is detected k times at first and then triggers the alarm line. On the contrary, it is legal. For example, the path s1 in Figure 5 is illegal, and the path s3 is legal, which will not report any alarm. When the alarm is reported, we can easily distinguish the illegal one. Since some intruders are not going to enter the inner region of our monitored area, such as the path s3 shown in Figure 5, an intruder enters into the monitoring area and is detected several times being less than the maximum number of barriers constructed in our model, but does not trigger the alarm line; then the intruder is also thought to be legal. It is obvious to see that our model can effectively detect the illegal intruders, and it does not require two neighboring barriers, and it can be used more widely. Above all, there are some common situations most likely happened in our monitored area.

4.2. Multiple Intruders

When considering more than one intruder at the same time, our k-barrier coverage can provide one-way barrier coverage if the intruders cross straight through the region satisfying some constrains. AS shown in Figures 6(a), 6(b), and 6(c), there are three possible penetrating paths of intruders.

Figure 6

Three kinds of invasion ways.

When intruders cross the circular area along the same direction, such as in Figures 6(a) and 6(b), intruders a and b either penetrate the circular rings from the outer boundary to the inner boundary or from the inner boundary to the outer boundary. In this case, intruders are detected $k-1$ times first; then they trigger the alarm line or trigger the alarm line first; then they will be detected $k-1$ times. Obviously, when there are multiple intruders, we can detect the illegal intruders depending on the order of triggering the alarm line first or being detected $k-1$ times first. There is no effect on each intruder when intruders cross the circular rings with different directions, as shown in Figure 6(c). There exits a situation that intruder b triggers the alarm line while intruder b penetrates the circular rings and triggers the alarm line at the same; then the detecting system may ignore the behavior of intruder a. So our k-barrier coverage cannot detect multiple intruders well under this circumstance.

5. Extended Application

In previous sections, we studied k-barrier coverage of WSNs in a circular area; here we are talking about its extended application used in more generalized environment, for example, with rectangular area. As seen in Figures 7(a) and 7(b), the length is 100 m, and width is 80 m. In Figure 7(a), the rectangular area has been divided into four width parts equally, and sensors are deployed in the middle line of each part following Gaussian deployment ( $\Delta =\mathrm{1},\hspace{0.17em}\hspace{0.17em}\mu =y+\Delta y$ ).

Figure 7

Extended application in rectangular area.

When sensors are deployed randomly in monitored area, there are risks of sensors being deployed in some place with high density; on the country, some places are with very few sensors. Since the strong k-barriers mean that no intruders can penetrate the monitored area without being detected, no gaps are allowed in barriers. To make sure of building strong k-barriers in WSNs with sensors randomly deployed, we should deploy more than enough sensors in monitored area.

The minimal amount of nodes in each barrier calculated according to formula (10) is $\mathrm{5,5},\mathrm{5,5}$ . And we can see in Figure 7(b), which costs $\mathrm{6,6},\mathrm{6,6}$ sensors in practical, our k-barrier coverage can be used well in rectangular area, since the error can be ignored in terms of the whole WSNs. Above all, the proposed k-barrier algorithm can not only be use in a circular area, but also can be used in a more generalized environment where the upper and lower boundaries are parallel.

6. Performance Evaluation

6.1. Simulation Methodology

The simulation results are obtained in MATLAB. The objectives of the evaluation are threefold: (1) testing the feasibility and effectiveness of our algorithm in constructing k-barrier coverage; (2) testing our sensor network in detecting whether an intruder is legal or illegal; and (3) studying the performance of our algorithm under different system parameters, such as different sensing radii of sensors, different barrier constructing models, and different sensor distributions.

In the simulations, deploy 640 nodes in an annular region. The distribution of sensors follows the Gaussian distribution and radius of the annual region ranges from 20 m to 100 m. The sensing radii of all sensors are identical. Intruders try to cross the region from one ring to the other ring. Here the annular region is divided into four parts with equal width. Without loss of generality, we assume that the intruders' always move from any of the two edges of the annular region. We study different influence of sensor sensing radius in constructing our barriers. Then we study the impact of system parameters and intruders characteristics. The sensing range is set as 8 m and the communication range is set as 16 m. The number of k is assumed to be 4 in advance. Since the sensors are deployed as the Gaussian deployment, the real value of k may not exactly be 4. The number of sensors in each part of the four annular regions is 64, 128, 192, 256, respectively, which are calculated according to the perimeter of each ring.

6.2. Construction of the WSNs

To test the feasibility and effectiveness of our algorithm, Figure 8 shows the initial Gaussian deployment diagram, and we take $k=\mathrm{4}$ . The initial number of sensors is set as 56, 104, 152, 208 from the innermost circular ring to the outermost, respectively. The sensors are almost deployed around the middle virtual line. Here we take $\mu =\mathrm{0}$ , $\sigma =\mathrm{1}$ .

Figure 8

Initial Gaussian deployment of sensors with $\mu =\mathrm{0}$ , $\sigma =\mathrm{1}$ , $r_s=\mathrm{10}\hspace{0.17em}\mathrm{m}$ , and $R_c=\mathrm{10}\hspace{0.17em}\mathrm{m}$ .

Figure 9 shows the simulation results of our algorithm. We take $r_{\mathrm{s}}=\mathrm{8}\hspace{0.17em}\mathrm{m}$ , $r_c=\mathrm{2}{r}_s=\mathrm{16}\hspace{0.17em}\mathrm{m}$ , and $\mu =\mathrm{0}$ , and $\sigma =\mathrm{1}$ . Figure 9(a) shows the barriers formed in the model in Figure 8. We can see that there are four barriers in our annular region. We do 20 times in MATLAB, and we get four barriers more than 14 times. But there is also the situation like in Figure 9(b) and there is only three barriers in our monitored region, and the number of k is smaller than the preset value. But it just appears about 4 times in the 20 times simulations. In Figures 9(a) and 9(b), the blue smooth circular rings are our detected annular region and the red dotted line is our generated barrier. Moreover, the points are marked as sensors. In Figure 9, it is just shown the sensors constructing barriers in each annular ring.

Figure 9

k-barrier constructing model with $\mu =\mathrm{0}$ , $\sigma =\mathrm{1}$ , $r_s=\mathrm{8}\hspace{0.17em}\mathrm{m}$ , and $R_c=\mathrm{16}\hspace{0.17em}\mathrm{m}$ .

In the innermost circular ring of Figure 9(a), there is an incomplete dotted line, which does not construct a complete barrier, and the incomplete barrier is enlarged in Figure 9(b). It shows that the barrier cannot find a next suitable sensor under our constraints. Such a barrier is not needed, then we will dissolve it. And the sensors in the incomplete barrier can go to sleep until they are waken up.

6.3. Impact of Sensing Radius

To evaluate the impact of sensing radius on the performance of our barrier constructing algorithm, we set the initial numbers of sensors as 56, 104, 152, 208 from the innermost annular ring to the outermost one, and sensors are deployed following the Gaussian deployment in every annular ring. In addition, if we can build one barrier, the number of sensors is enough. The sensing radii of sensors are set to be 8 m and 10 m for each evaluation, respectively. Different sensing radii are shown in Figure 10. In Figure 10, we can see that the larger the sensing radius is, the less the sensors are needed to build a barrier in the same situation. For example, when $r_s=\mathrm{8}\hspace{0.17em}$ m, it needs 13, 25, 34, 45 sensors in every barrier from the innermost to the outermost like Figure 9(c), but it only needs 13, 16, 28, 38 sensors, when $r_s=\mathrm{10}$  m. If we want to build a barrier to cover the same region, we would better choose the sensors with larger sensing radius.

Figure 10

Number of sensors constructing k-barrier with $r_s=\mathrm{8}\hspace{0.17em}\mathrm{m}$ and $r_s=\mathrm{10}\hspace{0.17em}\mathrm{m}$ , $k=\mathrm{4}$ , $\mu =\mathrm{0}$ , and $\sigma =\mathrm{1}$ .

6.4. Comparison with Another Model

As the purpose of our k-barrier coverage in WSNs is to detect intruder invasion, we can compare it with [21], which uses a two-neighbor barrier coverage to detect one-way intruders. We construct such a two-neighbor barrier coverage using our k-barrier coverage algorithm. As shown in Figure 11(a), in Figure 11(b), it is a 2-barrier coverage constructed by our k-barrier coverage algorithm, where $k=\mathrm{2}$ . They are different in nature. The two neighboring barriers in Figure 11(a) are continuously intersected but not anastomosed. But the 2-barrier coverage in Figure 11(b) is separate. And the circular area is decided into two width parts. The environment of these two situations is the same. Sensor nodes are deployed following Gaussian deployment in the middle line of each circular ring. When the total number of sensor nodes deployed in the monitored area is identical, we can see from Figure 11(c) that the number of sensor nodes used in building two barriers between Figures 11(a) and 11(b) is basically the same because the error is negligible in terms of the whole WSNs. The comparison on the number of sensor nodes used in building two barriers between Figures 11(a) and 11(b) shows that our k-barrier algorithm can achieve a good performance when realizing the same purpose.

Figure 11

Relevant comparison with our k-barrier coverage.

6.5. Impact of Sensor Distribution

To evaluate the impact of sensor distribution on the performance of our algorithm, we adopt the Gaussian development model in Figure 8 and calculate the number of sensors needed to build a barrier in Figure 9(a). Here we discuss another sensor distribution, which is the Uniform distribution, and compare the sensor number used in building barriers with the Gaussian deployment model. The reason why we choose the Uniform distribution is that it is widely used in past researches. The result is shown in Figures 11(a), 11(b), and 11(c). Figure 12(a) shows the Uniform distribution generated in MATLAB, and we can see that sensors are deployed randomly and with no rules in the monitored region. To compare the influence of sensor distribution with Gaussian distribution, the number of sensors distributed in every single annular region is the same as the number in Figure 8.

Figure 12

Comparing our sensor distribution with random deployment.

To build the barriers by using the algorithm proposed in our paper, it is obvious that more sensors are required. Figure 12(b) is a simulation result, and there are also four barriers in the annular region. The sensing radius, the range of our annular region, and the simulation times are the same as the previous Figure 9. Comparing Figure 12(b) with Figure 9(b), it is easy to see that it takes more sensors to build barriers. In Figure 12(b), it shows 4 barriers constructed by using sensors with the Uniform distribution. Figure 12(c) shows the contrast figure of the Gaussian distribution and Uniform distribution, which plots the number of sensors in every barrier. In Figure 13, we can see more about the relationship between randomly deployed sensor redundancy and the number of strong k-barrier coverage. Since sensors are deployed following random deployment, it is more hard to construct barriers than Gaussian deployment. In our k-barrier coverage algorithm, we can calculate the minimal amount of nodes that can be used to build a k-barrier deployment according to formula (10).

Figure 13

The relationship between the percentage of nodes utilization and nodes redundancy.

The degree of redundancy changes from six times to nine times the minimal amount of sensor nodes in every barrier. As can be seen in Figure 13, the higher the redundancy, the lower the utilization rate of the nodes. It means that the number of sensor nodes used in building barriers is inverse to the nodes redundancy. When the degree is lower than six, it is very difficult to complete k-barrier coverage.

6.6. Impact of Delta Value (i.e., σ)

In this part, we evaluate the impact of parameter σ on the performance of our algorithm. As seen in simulations, σ varies from 1 to 8. The results are shown in Figures 14(a) and 14(b). After 20-time simulations, we note that the number of sensors used in building barriers is related to the delta value σ. When σ is getting bigger, the performance is getting worse. And when σ is big enough, the Gaussian distribution tends to be Uniform distribution. In Figure 14(a), it is shown that there are almost four overlapped lines, and when σ is equal to 1, 2, 3, 4, respectively, the number of sensors used in building barriers is nearly equal. As shown in Figure 14(b), the total number of the sensors used to build the barriers is different. It is shown that when $\sigma =\mathrm{1}$ , the performance is the best because the number of sensors used in building 4-barrier coverage is the least. In addition, when σ is smaller than 5, their performance is similar to each other. Therefore the bigger the σ is, the more the total number of sensors is needed. For example, when σ is more than 9, it is hard to get 4-barrier coverage, since sensors are always developed outside the annular region, as seen in Figure 14(c). At this time, the distribution of sensors approximates the Uniform distribution adopted in Figure 12.

Figure 14

Comparing with different delta (i.e., $\mu =\mathrm{0}$ , delta).

7. Conclusion

In this paper, we propose a barrier constructing algorithm in WSNs for intruder detection, which constructs k-barrier in a circular area, and apply our algorithm in one-way intruders detecting. When an intruder is detected k times at first, and it is broadcasted at last, it is an illegal intruder. On the contrary, if it is broadcasted at first, then it will be detected at least one time; it is a legal intruder. The goal of detecting whether an intruder is legal or illegal is achieved well. On one hand, the simulation results prove that our protocol can build k-barrier very well. On the other hand, the simulation results prove that the total number of sensors used in building k-barrier is small. Therefore the Gaussian distribution with low σ is a good choice.