Fault Tolerant Line-Based Barrier Coverage Formation in Mobile Wireless Sensor Networks

Abstract

Barrier coverage is a fundamental problem for lots of applications in wireless sensor networks. In reality, sensor nodes' true locations may not be known to us considering that not every sensor node is equipped with a GPS. The measured locations of sensor nodes obtained by applying node localization algorithm often have errors, which makes it difficult to form a line-based barrier with mobile sensor nodes. In this paper, we study how to efficiently schedule mobile sensor nodes to form a barrier when sensor nodes suffer from location errors. We explore the relationship between the existence of uncovered hole and location errors and find that the lengths of uncovered holes are decided by the cumulative location errors. We also propose a method in frequency domain to efficiently calculate the distributions of the cumulative location errors. The possibility of the existence of uncovered holes can be derived by analyzing the step responses of the cumulative location errors. Extensive experimental results demonstrate the effectiveness of the proposed algorithm.

1. Introduction

Wireless sensor networks (WSNs) [1–6] have been widely used in a variety of application scenarios. In WSNs, the quality of sensing [7–10], which is often referred to as coverage, is a fundamental concern. Barrier coverage deploys sensor nodes in a long, narrow region of interest (ROI) which carries out detecting the targets when they penetrate into the region. It finds significant application in WSNs. For example, in the application of border surveillance, we are able to detect unauthorized intrusions by deploying sensor nodes along the boundary of interest.

The first and most important aspect to form a barrier is how to design sensor nodes deployment. When the sensor nodes are placed to the expected locations, the quality of barrier coverage is guaranteed. However, in actual applications, most cases of the ROI are in harsh environment, which make it difficult to obtain the expected locations and deploy the nodes there. Sensor nodes are deployed randomly in most practical cases; for example, they can be dropped from aircraft [11]. To this end, the sensor nodes are not deployed to the expected locations initially, and they could not form a barrier. Fortunately, thanks to recent advances in mobility-assistant technology, sensor nodes have the ability to move around to carry out tasks [12, 13]. Hence, a barrier coverage could be formed by controlling the senor mobility.

Firstly, each mobile sensor node obtains its location before moving to the expected locations. Therefore, the problem of achieving barrier coverage is covert to the localization problem of mobile nodes. Equipping GPS receivers on each node to get the accurate location information is too cost-expensive. Hence, in practical use, only several nodes are equipped with GPS receivers. The other nodes are located by integrating the relative locations to their neighboring nodes using localization algorithms. In the past years, lots of localization algorithms have been proposed, such as Time of Arrival (TOA) [14], Time Difference of Arrival (TDOA) [15, 16], Angle of Arrival (AOA) [17, 18], and Received Signal Strength Indicator (RSSI) [19–21]. However, the location results provided by these algorithms have low accuracy and in most cases with location errors. Due to location errors, mobile nodes' measured locations are different from their actual locations. Thus, they cannot stop and be deployed at the expected locations in real applications. To guarantee the quality of barrier coverage, barrier formation should be adaptive to the location errors. However, little literature considers the effects of location errors.

Moreover, the location errors of the localization algorithms are diverse and may follow a random distribution. Traditional methods always analyze the worst cases, that is, the lower and upper bounds. However, worst case analysis is always conservative and hard to capture the higher-order location error characteristics. For example, node A is equipped with a GPS receiver; node B is located relative to node A, and the location error follows a uniform distribution: $U [- 3 m, 3 m]$ ; node C is located relative to node B, and the location error follows $U [- 5 m, 5 m]$ . Thus, the measured location of node C deviates from its actual location, and the deviation equals the cumulative location error. The cumulative location error follows the joint distribution of $U [- 3 m, 3 m]$ and $U [- 5 m, 5 m]$ . From the error distribution, we could get the probability of location error of any value other than the lower and upper bounds ( $- 8 m$ and $8 m$ ). However, previous work rarely studied the distributions of the cumulative location errors.

In this paper, we investigate how to efficiently schedule mobile sensor nodes to form a barrier when sensor nodes suffer from undetermined location errors. Firstly, we investigate how the uncovered holes are generated by the location errors and find that the lengths of uncovered holes are decided by the cumulative location errors. Then we analyze how to calculate the distributions of cumulative location errors. Since each location error follows a distribution, convoluting the distributions of individual location errors to get the distribution of the cumulative location error is inefficient. Its computational cost is extremely high when the network is large. In this paper, we calculate the location errors in the frequency domain. Convolution is converted to multiplication and the computation complexity is heavily reduced. Third, after the cumulative location errors are obtained in frequency domain, we analyze the characteristics of their step responses (e.g., probability distribution functions). Then, the probability of uncovered holes existing could be easily obtained from the step responses. Finally, when the possibilities are high, we reduce the possibilities by deploying more nodes, equipping more GPSs, or improving sensing range to guarantee the quality of barrier coverage adaptively.

To the best of our knowledge, our work is the first applying frequency analysis on studying barrier coverage problem when nodes have location errors. The major intellectual contributions of this paper are summarized as follows: (i)

We theoretically analyze the relationships between the lengths of the uncovered holes and the location errors. The mathematical expressions of calculating the uncovered holes' length from the cumulative location errors are given.

(ii)

When each location error follows a distribution, we give an efficient method to calculate the distribution of the cumulative location error in frequency domain.

(iii)

We propose a method of analyzing the step response of the cumulative location error to get the probability of the uncovered hole existing.

(iv)

We study some cases to show how to use our framework and guarantee the quality of barrier coverage adaptively.

The rest of this paper is organized as follows. Section 2 surveys the related work and Section 3 analyzes the barrier coverage when location errors exist. We give theoretical expressions of calculating the uncovered hole length in Section 4. Then in Section 5 we calculate the cumulative location errors in frequency domain and get the probabilities of the uncovered holes existing. Section 6 gives examples of using our framework and corresponding evaluation and Section 7 provides conclusions.

2. Related Work

Barrier coverage is a fundamental problem for lots of applications in wireless sensor networks and has been widely researched. Kumar et al. [22] firstly defined the notion of k-barrier coverage and introduced weak and strong coverage in a belt region. Liu et al. [23] proposed a solution for strong barrier coverage when sensor nodes are randomly deployed according to a Poisson point distribution process. Li et al. [24] investigated the weak k-barrier coverage problem and derive a lower bound for the probability of weak k-barrier coverage. Since most cases of the ROI are in harsh environment and difficult for human being to reach, Saipulla et al. [11] investigated barrier coverage with airdropped wireless sensors under line-based deployments and give a lower bound for the existence of barrier coverage. In [25], He et al. showed the suboptimality of line-based deployment when the length of shortest line segment is larger than that of shortest path and for the first time quantified the need of curve-based deployment; then they introduced a concept of distance-continuous curve and provided an algorithm to obtain the optimal sensor deployment when the deployment curve is distance continuous. Chen et al. [26, 27] proposed the methods of scheduling sensors energy efficiently while guaranteeing the detection probability of any intrusion across the region based on probabilistic sensing model, which is a more actual sensing model.

Due to recent technological advances, nodes have the ability to move around to carry out tasks. Barrier coverage in mobile sensor network is a hot research area. He et al. [28] guaranteed that each point along the barrier line is monitored periodically by mobile sensors by using a periodic monitoring scheduling algorithm. Saipulla et al. [29] presented a method which could construct the maximum number of barriers under the constraints of sensor mobility. Shen et al. [30] found that barrier coverage could be achieved with fewer mobile sensors than stationary sensors when applying random deployment. Wang et al. [31] proposed a method of using minimum number of mobile sensor nodes to improve barrier coverage when the stationary nodes are not forming a barrier after initial deployment. He et al. [32] designed a periodic monitoring scheduling algorithm in which each point along the barrier line is monitored periodically by mobile sensors and propose a coordinated sensor patrolling algorithm to further improve the barrier coverage, where each sensor's current movement strategy is derived from the information of intruder arrivals in the past.

Using mobility-assistant nodes in randomly deployment barrier coverage can achieve higher quality sensing performance if they could move to the designed locations. However, due to high equipment cost, not all mobile nodes are equipped with GPS receivers. We locate them using typical localization algorithms. However, location errors exist which will significantly affect the quality of coverage. Thus, in this paper, we investigate how to efficiently schedule mobile sensor nodes to form a barrier when sensor nodes obtain locations with errors.

3. Barrier Coverage When Location Errors Exist

Mobile wireless sensor networks usually consist of large number of mobile sensor nodes. We denote $S_{i}$ as the index of ith sensor node. Each sensor node can detect the target or event if it is within the sensing range and then the sensor nodes can communicate with each other. We assume that all sensor nodes have the same sensing range and communication range. As shown in Figure 1, the sensing range is denoted as $r_{s}$ . A sensor node can detect an intruder within its sensing range, for example, intruder A, in Figure 1. However, it cannot detect the intruder beyond its sensing range $r_{s}$ , such as intruder B. The communication range is denoted as $r_{c}$ , which is larger than the sensing range $r_{s}$ . We assume that $r_{c} > 2 r_{s}$ .

Figure 1

Sensing range and communication range of sensor node.

We construct the model of the region of interest (ROI) with a closed line interval $[0 : L]$ , whose line has two endpoints, 0 and $L > 0$ . The sensor nodes are deployed on this line to form a barrier coverage. The total number of nodes is N, and these N nodes are uniformly deployed, which means, if we denote $D = L / N$ , the node to the left end is deployed at location $D / 2$ , the node to the right end is deployed at location $N D / 2$ , and the interval between any two neighboring nodes is D. To guarantee the overlap of any two neighboring nodes, condition $D \leq 2 r_{s}$ must be satisfied.

Considering the limitation of the sensing range and communication range of the nodes, the minimum number of nodes we need to form a barrier to cover L is

\begin{matrix} N_{\min} = ceil (\frac{L}{2 r_{s}}) . \end{matrix}

(1)

As shown in Figure 2(a), we deploy $N_{m i n}$ nodes on line L. D is set to $2 r_{s}$ , and node $S_{i}$ is deployed at $(2 i - 1) r_{s}$ . If the nodes are deployed at these locations, the whole line L could be successfully covered.

Figure 2

An example of line-based barrier coverage: (a) nodes are deployed in the expected location; minimum number of nodes is used to form a barrier; (b) when location error exists, the barrier has uncovered holes on it.

However, in practical scenario, the ROI is probably in a harsh environment, and sensor nodes are usually deployed randomly. In such case, the sensor nodes are not deployed in the expected location initially, and the barrier cannot be formed. Fortunately, with mobility-assistant technology, the mobile nodes can move to the designed locations to form a barrier. However, it is too expensive to equip each node with a GPS receiver. In a typical network, only several nodes are equipped with a GPS receiver, which act as the beacon nodes. Then, we can use localization algorithms to locate other nodes that are neighboring these beacon nodes. When these locations are obtained, they also become beacon nodes to the other neighboring nodes. With such method, all the nodes' locations can be obtained.

Actually, there is localization error in practical process. Take example of node $S_{a}$ , with its true location being $x_{a}$ , and the corresponding measured location is denoted by ${\hat{x}}_{a}$ . If $S_{a}$ is equipped with a GPS receiver, then ${\hat{x}}_{a} = x_{a}$ . If there is a node $S_{b}$ neighboring node $S_{a}$ which needs to be located, using the above-mentioned localization algorithms, we can get the measured location of $S_{b}$ and the distance ${\hat{L}}_{a, b}$ between $S_{a}$ and $S_{b}$ . When $S_{b}$ is on the left of $S_{a}$ , the measured location of $S_{b}$ is

\begin{matrix} {\hat{x}}_{b} = {\hat{x}}_{a} - {\hat{L}}_{a, b}; \end{matrix}

(2)

otherwise, the measured location of

S_{b}

\begin{matrix} {\hat{x}}_{b} = {\hat{x}}_{a} + {\hat{L}}_{a, b} . \end{matrix}

(3)

In wireless sensor networks, none of the existing localization algorithms can obtain perfectly accurate location; that is, the location errors exist actually. Hence, we get

\begin{matrix} Δ L_{h o p}^{b} = {\hat{L}}_{a, b} - L_{a, b}, \end{matrix}

(4)

where

{\hat{L}}_{a, b}

denotes the measured distance between node

S_{a}

and node

S_{b}

and

L_{a, b}

denotes the actual distance between these two nodes;

Δ L_{h o p}^{b}

denotes the one-hop location error of node

S_{b}

Definition 1.

The one-hop location error $L_{h o p}$ is the measurement error of the distance from sensor node to its corresponding beacon node.

While there is location error, mobile nodes cannot move to the optimized locations. We take an example to demonstrate the impact of the location errors. As shown in Figure 2(b), we utilize $N_{m i n}$ number of mobile nodes to cover the line L, with several nodes being equipped with a GPS receiver. However, most of the nodes need to be located by using localization algorithms. For ith node which does not have any GPS receiver, its measured location is ${\hat{x}}_{i}$ . When the sensor node finishes moving, we get

\begin{matrix} {\hat{x}}_{i} = (2 i - 1) r_{s} . \end{matrix}

(5)

However, due to location error, we get

\begin{matrix} x_{i} \neq {\hat{x}}_{i} = (2 i - 1) r_{s}; \end{matrix}

(6)

that is, its actual location

x_{i}

does not equal the expected location. Thus, as shown in Figure 2(b), such condition incurs uncovered holes on the barrier.

4. Models of the Uncovered Holes

In the above section, we show that due to the existence of the location errors the nodes cannot move to the expected locations. Hence, this situation incurs uncovered holes on the barrier. The uncovered holes could be classified into three categories: (1) the uncovered hole between two neighboring nodes where one node is located based on the other node; (2) the uncovered hole between two neighboring nodes where the two nodes are not located based on one another; (3) the uncovered holes between the leftmost (or rightmost) node and the left (or right) endpoints of L. We define them as the first, second, and third type of uncovered hole, respectively, in the following description. We will give detailed analysis of these three types of uncovered holes in this section.

4.1. The First Type of the Uncovered Hole

The first type of uncovered hole is shown as in Figure 3. There are two neighboring nodes, nodes $S_{p}$ and $S_{q}$ , in the network. Node $S_{p}$ is the beacon node of $S_{q}$ . Due to the location error, an uncovered hole may exist between the locations of them. We get the following.

Figure 3

Node $S_{p}$ is the beacon of node $S_{q}$ : (a) nodes overlap with each other and no uncovered hole exists; (b) nodes do not overlap with each other and an uncovered hole exists.

Theorem 2.

For two neighboring nodes, nodes $S_{p}$ and $S_{q}$ in the network, when node $S_{p}$ is the beacon node of node $S_{q}$ , the length of the uncovered hole between them is

\begin{matrix} h_{t p 1} = \max (0, D - 2 r_{s} - Δ L_{h o p}^{q}) . \end{matrix}

(7)

Proof.

The interval between nodes $S_{p}$ and $S_{q}$ is set to D; we get

\begin{matrix} {\hat{x}}_{q} - {\hat{x}}_{p} = D = \hat{L_{p, q}} . \end{matrix}

(8)

Combining with (4) and (8), we get

\begin{matrix} L_{p, q} = \hat{L_{p, q}} - Δ L_{h o p}^{q} = D - Δ L_{h o p}^{q} . \end{matrix}

(9)

As shown in Figure 3(a), when

2 r_{s} - L_{p, q} > 0

, nodes

S_{p}

and

S_{q}

overlap with each other. Thus, there is no uncovered hole between these two locations; that is,

h_{p, q} = 0

. However, as shown in Figure 3(b), when

2 r_{s} - L_{p, q} < 0

, nodes

S_{p}

and

S_{q}

do not overlap with each other. There is an uncovered hole between them, and its corresponding length is

\begin{matrix} h_{p, q} = L_{p, q} - 2 r_{s} . \end{matrix}

(10)

Combining with (9) and (10), we get

h_{p, q} = D - 2 r_{s} - Δ L_{h o p}^{q}

4.2. The Second Type of the Uncovered Hole

The second type of uncovered hole is shown as in Figure 4. There are two neighboring nodes, nodes $S_{d}$ and $S_{e}$ , in the network. Node $S_{d - i}$ 's beacon node is node $S_{d - i - 1}$ , and node $S_{d - M}$ is equipped with a GPS receiver. Similarly, node $S_{e + i}$ 's beacon node is $S_{e + i + 1}$ , and node $S_{e + K}$ is equipped with a GPS receiver. M is defined as the hops from node $S_{d}$ to its nearest GPS node. K is defined as the hops from node $S_{e}$ to its nearest GPS node. When $M = 0$ or $K = 0$ , there is a GPS receiver equipped on $S_{d}$ or $S_{e}$ , respectively. We get the following.

Figure 4

$S_{d}$ and $S_{e}$ are not located based on the other: (a) no uncovered hole exists; (b) an uncovered hole exists.

Theorem 3.

For two neighboring nodes, nodes $S_{d}$ and $S_{e}$ in the network, where the two nodes are not located based on one another,

\begin{matrix} h_{t p 2} = \max (0, D - 2 r_{s} + \sum_{i = 1 - M}^{K - 1} Δ L_{h o p}^{d + i}) . \end{matrix}

(11)

Proof.

Since the interval between nodes $S_{d}$ and $S_{e}$ is set to D, we get

\begin{matrix} {\hat{x}}_{e} - {\hat{x}}_{d} = D . \end{matrix}

(12)

Obviously, we get

\begin{matrix} {\hat{x}}_{d} = {\hat{x}}_{d - M} + {\hat{L}}_{d - M, d - M + 1} + \dots + {\hat{L}}_{d - 1, d} . \end{matrix}

(13)

Combining with (4), we get

\begin{matrix} {\hat{x}}_{d} = {\hat{x}}_{d - M} + (L_{d - M, d - M + 1} + \dots + L_{d - 1, d}) + \sum_{i = 1}^{M} Δ L_{h o p}^{d - i + 1} . \end{matrix}

(14)

Since

S_{d - M}

is equipped with GPS receiver, we have

{\hat{x}}_{d - M} = x_{d - M}

. Hence, we get

\begin{matrix} {\hat{x}}_{d} = x_{d - M} + (L_{d - M, d - M + 1} + \dots + L_{d - 1, d}) + \sum_{i = 1}^{M} Δ L_{h o p}^{d - i + 1} = x_{d} + \sum_{i = 1}^{M} Δ L_{h o p}^{d - i + 1} . \end{matrix}

(15)

Similarly, for $S_{e}$ , we get

\begin{matrix} {\hat{x}}_{e} = x_{e} - \sum_{j = 1}^{K} Δ L_{h o p}^{e + j - 1} . \end{matrix}

(16)

As shown in Figure 4(a), when $x_{e} - x_{d} - 2 r_{s} < 0$ , that is, nodes $S_{d}$ and $S_{e}$ overlap with each other, there is no uncovered hole between these two locations. However, as shown in Figure 4(b), when $x_{e} - x_{d} - 2 r_{s} > 0$ , that is, they have no overlapping area, there is an uncovered hole between them and its length is

\begin{matrix} h_{d, e} = x_{e} - x_{d} - 2 r_{s} . \end{matrix}

(17)

Combining with (12), (15), (16), and (17), we get

h_{d, e} = D - 2 r_{s} + \sum_{i = 1}^{M} Δ L_{h o p}^{d - i + 1} + \sum_{j = 1}^{K} Δ L_{h o p}^{e + j - 1}

. Since nodes

S_{d}

and

S_{e}

are neighboring nodes, we get

e = d + 1

. Hence,

h_{d, e} = D - 2 r_{s} + \sum_{i = 1 - M}^{K - 1} Δ L_{h o p}^{d + i}

4.3. The Third Type of the Uncovered Hole

The third type of uncovered hole is shown as in Figure 5. Node $S_{l}$ is the leftmost node of the network, and node $S_{r}$ is the rightmost node of the network. Node $S_{l + i}$ 's beacon node is $S_{l + i - 1}$ , and $S_{l + P}$ is equipped with a GPS receiver. Similarly, node $S_{r - j}$ 's beacon node is $S_{r - j - 1}$ , and $S_{r - Q}$ is equipped with a GPS receiver. P is defined as the hops from node $S_{l}$ to its nearest GPS node. Q is defined as the hops from node $S_{r}$ to its nearest GPS node. When $P = 0$ or $Q = 0$ , GPS receivers are equipped on $S_{l}$ or $S_{r}$ , respectively.

Figure 5

The uncovered hole between the leftmost (rightmost) node and the left (right) endpoint of L: (a) uncovered holes do not exist; (b) uncovered holes exist.

Theorem 4.

The length of the uncovered hole between the leftmost node $S_{l}$ and the left endpoint of L is

\begin{matrix} h_{t p 3 l} = \max (0, \frac{D}{2} - r_{s} + \sum_{i = 1}^{P} Δ L_{h o p}^{l + i - 1}) . \end{matrix}

(18)

And the length of the uncovered hole between the rightmost node

S_{r}

and the right endpoint of L is

\begin{matrix} h_{t p 3 r} = \max (0, \frac{D}{2} - r_{s} + \sum_{j = 1}^{Q} Δ L_{h o p}^{r - j + 1}) . \end{matrix}

(19)

Proof.

For the uncovered hole between the leftmost node and the left endpoint of L, since the leftmost node is set to be deployed at $D / 2$ , we get

\begin{matrix} {\hat{x}}_{l} = \frac{D}{2} . \end{matrix}

(20)

Then, we get

\begin{matrix} {\hat{x}}_{l} = {\hat{x}}_{l + P} - {\hat{L}}_{l + P - 1, l + P} - \dots - {\hat{L}}_{l, l + 1} . \end{matrix}

(21)

Since node

S_{l + P}

is equipped with a GPS receiver, we can get

{\hat{x}}_{l + P} = x_{l + P}

. Combining with (4) and (21), we get

\begin{matrix} {\hat{x}}_{l} = x_{l + P} - (L_{l + P - 1, l + P} + \dots + L_{l + 1, l}) - \sum_{i = 1}^{P} Δ L_{h o p}^{l + i - 1} = x_{l} - \sum_{i = 1}^{P} Δ L_{h o p}^{l + i - 1} . \end{matrix}

(22)

As shown in Figure 5(a), when $x_{l} < r_{s}$ , there is no uncovered hole. However, as shown in Figure 5(b), when $x_{l} > r_{s}$ , we have

\begin{matrix} h_{l} = x_{l} - r_{s} . \end{matrix}

(23)

Combing with (20), (22), and (23), the length of the uncovered hole between the leftmost node and the left endpoint of L is

h_{l} = D / 2 - r_{s} + \sum_{i = 1}^{P} Δ L_{h o p}^{l + i - 1}

Similarly, we can prove $h_{r} = m a x (0, D / 2 - r_{s} + \sum_{j = 1}^{Q} Δ L_{h o p}^{r - j + 1})$ .

We have introduced the three types of uncovered holes. From Theorems 2, 3, and 4, we find the following: (i)

The uncovered holes are decided by the neighboring nodes' interval D, the sensing range $r_{s}$ , and the location errors. When we have smaller D or larger $r_{s}$ , the uncovered hole is smaller. However, a smaller D value means deploying more sensor nodes, and a larger $r_{s}$ value means using more expensive sensor. Both of them finally increase the cost of the system.

(ii)

The first type of uncovered hole is decided by the one-hop location error.

(iii)

The second and third types of uncovered holes are decided by the cumulative location errors. Thus, as the network scale gets larger, they can be much more complicated to analyze than the first type of uncovered hole.

(iv)

In an actual network, the three types of uncovered holes are not separated. For example, when $Δ L_{h o p}$ is negative and smaller, the first type of uncovered hole will disappear; however, the second and third type of uncovered holes may become larger. This situation incurs complicated analysis of the uncovered holes.

5. Analysis of Coverage in Frequency Domain

We have introduced the uncovered holes in aforementioned section and find that the uncovered holes are determined by the node location errors. For practical consideration, the location errors are usually not fixed. Each one-hop location error follows a random distribution which can be obtained by theoretical analysis or from numerous experiments. The cumulative location error follows a superimposed distribution, and the probability density function equals the convolution of the probability density functions of the individual one-hop location errors.

Let $Δ L_{h o p}$ denote the one-hop location error in the network. The probability density function of $Δ L_{h o p}$ is denoted by $f_{h o p} (t)$ . Considering Theorems 2, 3, and 4, $Δ L_{h o p}^{q}$ represent the (cumulative) location error part in (7), $\sum_{i = 1 - M}^{K - 1} Δ L_{h o p}^{d + i}$ in (11), $\sum_{i = 1}^{P} Δ L_{h o p}^{l + i - 1}$ in (18), and $\sum_{j = 1}^{Q} Δ L_{h o p}^{r - j + 1}$ in (19), respectively. For the cumulative location errors, we get the following.

We define $Δ L_{t p 1} = Δ L_{h o p}^{q}$ , and its probability density function is denoted by $f_{t p 1} (t)$ . We get

\begin{matrix} f_{t p 1} (t) = f_{h o p}^{q} (t) . \end{matrix}

(24)

Let

Δ L_{t p 2} = \sum_{i = 1 - M}^{K - 1} Δ L_{h o p}^{d + i}

, and its probability density function is denoted by

f_{t p 2} (t)

. We have

\begin{matrix} f_{t p 2} (t) = f_{h o p}^{d - M + 1} (t) \otimes f_{h o p}^{d - M + 2} (t) \dots \otimes f_{h o p}^{d + K - 1} (t) . \end{matrix}

(25)

Let

Δ L_{t p 3 l} = \sum_{i = 1}^{P} Δ L_{h o p}^{l + i - 1}

, and its probability density function is denoted by

f_{t p 3 l} (t)

. Let

Δ L_{t p 3 r} = \sum_{j = 1}^{Q} Δ L_{h o p}^{r - j + 1}

, and its probability density function is denoted by

f_{t p 3 r} (t)

. We have

\begin{matrix} f_{t p 3 l} (t) = f_{h o p}^{l} (t) \otimes f_{h o p}^{l + 1} (t) \dots \otimes f_{h o p}^{l + P} (t), \\ f_{t p 3 r} (t) = f_{h o p}^{r} (t) \otimes f_{h o p}^{r - 1} (t) \dots \otimes f_{h o p}^{r - Q} (t) . \end{matrix}

(26)

Thus, we need to convolute the one-hop location error distributions to get the distributions of the cumulative location errors. When the distributions of the cumulative location errors, that is, $f_{t p 1} (t)$ , $f_{t p 2} (t)$ , $f_{t p 3 l} (t)$ , and $f_{t p 3 r} (t)$ , are obtained, we can analyze the uncovered holes. However, the computation of convolutions in (25) and (26) is extremely high when the network scale is large. Thus, to obtain the lengths of the uncovered holes and guarantee coverage, the key problem is how to calculate the distributions of the cumulative location errors effectively. To solve this problem, we propose an efficient method in frequency domain.

Let $f (t)$ denote the probability density function of the location error which is in time domain. It could be converted into frequency domain by Laplace Transform as follows:

\begin{matrix} F (s) = L [f (t)] = \int_{0}^{\infty} e^{- s t} f (t) d t, \end{matrix}

(27)

where

L

is the operator of Laplace Transform. After the probability density function of the location error is converted to the frequency domain, convolution is converted to multiplication. Thus, the computation complexity becomes much lower. Meanwhile, if we obtained

F (s)

in frequency domain, it could easily get

f (t)

by using Inverse Laplace Transform as follows:

\begin{matrix} f (t) = L^{- 1} [F (s)] = \frac{1}{j 2 π} \int_{σ - j \infty}^{σ + j \infty} e^{s t} F (s) d s . \end{matrix}

(28)

By using Laplace Transform and converting distributions to the frequency domain, we calculate the cumulative location errors for different types of uncovered holes as

\begin{matrix} F_{t p 1} (s) = L [f_{t p 1} (t)] = F_{h o p}^{q} (s); \end{matrix}

(29)

\begin{matrix} F_{t p 2} (s) = L [f_{t p 2} (t)] = \prod_{i = 1 - M}^{K - 1} F_{h o p}^{d + i} (s); \end{matrix}

(30)

\begin{matrix} F_{t p 3 l} (s) = L [f_{t p 3 l} (t)] = \prod_{i = 1}^{P} F_{h o p}^{l + i - 1} (s); \end{matrix}

(31)

\begin{matrix} F_{t p 3 r} (s) = L [f_{t p 3 r} (t)] = \prod_{i = 1}^{Q} F_{h o p}^{r - j + 1} (s) . \end{matrix}

(32)

Let $F (s)$ denote the cumulative location error in frequency domain. We give unit step function as $u (t) = 1$ , if $t \geq 0$ ; $0$ , if $t < 0$ . Step response means the response (output) to a unit step-function input. In control theory, the step response of $F (s)$ equals the probability distribution function of the cumulative location error in time domain. We give the explanations here.

Let $y_{u (t)}$ denote the time response for $u (t)$ . We can get

\begin{matrix} L [y_{u (t)}] = L [u (t)] \cdot F (s) = \frac{1}{s} \cdot F (s) . \end{matrix}

(33)

The step response can be obtained by Inverse Laplace Transform as

\begin{matrix} y_{u (t)} = L^{- 1} [\frac{1}{s} \cdot F (s)] = \int_{0}^{t} f (τ) d τ = F (t), \end{matrix}

(34)

where

F (t)

is the probability distribution function of the cumulative location error in time domain.

Based on the step responses, it is feasible to analyze the uncovered holes.

For the first type of uncovered hole, its length is $h_{t p 1} = m a x (0, D - 2 r_{s} - Δ L_{h o p}^{q}) = m a x (0, D - 2 r_{s} - Δ L_{t p 1})$ . Thus, when there is no uncovered hole, it satisfies $Δ L_{t p 1} \geq D - 2 r_{s}$ . The probability distribution function (i.e., step response) of $Δ L_{t p 1}$ is $F_{t p 1} (t)$ . We have

\begin{matrix} p_{t p 1} = 1 - F_{t p 1} (t \geq D - 2 r_{s}), \end{matrix}

(35)

which means the probability of the first type of uncovered hole is

p_{t p 1}

Similarly, the probability of the second type of uncovered hole existing is

\begin{matrix} p_{t p 2} = 1 - F_{t p 2} (t \leq 2 r_{s} - D) . \end{matrix}

(36)

The probability of the third type of uncovered hole existing at the left endpoint of L is

\begin{matrix} p_{t p 3 l} = 1 - F_{t p 3 l} (t \leq r_{s} - \frac{D}{2}), \end{matrix}

(37)

and the probability of the third type of uncovered hole existing at the right endpoint of L is

\begin{matrix} p_{t p 3 r} = 1 - F_{t p 3 r} (t \leq r_{s} - \frac{D}{2}) . \end{matrix}

(38)

We have developed the theoretical framework to model and analyze the uncovered holes. The procedures are shown in Algorithm 5.

Algorithm 5.

The theoretical framework to model and analyze the uncovered holes is as follows: (1)

Obtain individual one-hop location error distributions of the network and convert them into frequency domain using Laplace Transform.

(2)

Calculate the distributions of the cumulative location errors in frequency domain by multiplications.

(3)

Analyze the step responses to get the probability of having uncovered holes on the barrier.

6. Evaluation

In previous sections, we have introduced our framework of analyzing the uncovered holes. In this section, we give some examples to show how to use the framework. The parameters of the simulations are summarized in Table 1.

Table 1

System constants and simulation parameters.

The length of the region of interest L (m)	2000

The sensing range $r_{s}$ (m)	50, 60, and 70

The number of nodes deployed originally N	21

The number of nodes added $N^{*}$	5, 10, and 15

The number of GPS receivers equipped originally	1

The number of GPS receivers added	1, 2, and 3

The length of the region of interest L is 2000 m and the sensing range $r_{s}$ is 50 m. We deploy $21$ mobile nodes to form a barrier. The designed interval between any two neighboring nodes is $D = L / N = 2000 / 21 = 95 m$ . Obviously, when each node is equipped with a GPS receiver, that is, every node can obtain its accurate location, we can form a perfect barrier.

However, as shown in Figure 6(a), due to high cost, only node $S_{1}$ is equipped with a GPS receiver. The locations of other nodes are obtained by using localization algorithms. Node $S_{i}$ is $S_{i + 1}$ 's beacon node. The results provided by the location algorithms contain location errors. The probability density function $f_{h o p}^{i} (t)$ of any one-hop location error is

\begin{matrix} f_{h o p}^{i} (t) = \{\begin{cases} 2 e^{- 2 t}, & t \geq 0, \\ 0, & t < 0, \end{cases} \end{matrix}

(39)

which follows an exponential distribution.

Figure 6

The example systems: (a) we deploy 21 nodes, and only node $S_{1}$ is equipped with a GPS receiver; (b) we add some nodes into the network; (c) more nodes are equipped with a GPS receiver.

To use the proposed framework, we first use Laplace Transform to covert $f_{h o p}^{i} (t)$ into the frequency domain. We get

\begin{matrix} F_{h o p}^{i} (s) = L [f_{h o p}^{i} (t)] = \frac{2}{s + 2} . \end{matrix}

(40)

Then we calculate the cumulative location errors for different cases of uncovered holes. Obviously, there may exist some first type of uncovered holes and a third type of uncovered hole (at the right endpoint of L) on the barrier. By (29) and (32), we have

\begin{matrix} F_{t p 1} (s) = \frac{2}{s + 2}; \\ F_{t p 3 r} (s) = {(\frac{2}{s + 2})}^{20} . \end{matrix}

(41)

The step response of $F_{t p 1} (s)$ is shown in Figure 7(a). By using (35), the probability of any first type of uncovered hole existing is $p_{t p 1} = 1 - F_{t p 1} (t \geq - 5) = 0$ . The step response of $F_{t p 3 r} (s)$ is shown in Figure 7(b). By using (38), the probability of an uncovered hole existing at the right endpoint of L is $p_{t p 3 r} = 1 - F_{t p 3 r} (t \leq 2.5) = 1$ , which means, due to the location errors, there will be an uncovered hole at the right endpoint of L.

Figure 7

The step responses: (a) step response of $F_{t p 1} (s)$ ; (b) step response of $F_{t p 3 r} (s)$ .

We have obtained the probability of an uncovered hole existing at the right endpoint which is $1$ . It cannot satisfy our requirement. In order to achieve a better coverage performance, we could adaptively enlarge the node's sensing ability (sensing range), deploy more nodes, or equip more GPS receivers.

6.1. Enlarge Sensing Range

We enlarge the sensing range here. Enlarging the sensing range does not affect the location errors. Thus, the step responses of $F_{t p 1} (s)$ and $F_{t p 3 r} (s)$ are the same as in Figure 7.

Using (35) and (38), we find the following: (a) when $r_{s}$ is enlarged to 60 m, the probability of the first type of hole existing is $p_{t p 1} = 1 - F_{t p 1} (t \geq - 25) = 0$ , and the probability of the third type of hole existing is $p_{t p 3 r} = 1 - F_{t p 3 r} (t \leq 12.5) = 0.13$ ; (b) when $r_{s}$ is enlarged to 70 m, we have $p_{t p 1} = 1 - F_{t p 1} (t \geq - 45) = 0$ and $p_{t p 3 r} = 1 - F_{t p 3 r} (t \leq 22.5) = 0$ .

Thus, when the sensing range is enlarged to 70 m, there is no uncovered hole on the barrier. However, in many applications, the sensing range is fixed. In these situations, enlarging the node's sensing ability is not practical.

6.2. Deploy More Nodes

As shown in Figure 6(b), we add more sensor nodes into the network. Obviously, the probability of having the first type of uncovered hole is not affected, which is $0$ .

We add $N^{*}$ nodes into the system. By (32), we calculate the cumulative location error as

\begin{matrix} F_{t p 3 r}^{*} (s) = {(\frac{2}{s + 2})}^{20 + N^{*}} . \end{matrix}

(42)

The step response

F_{t p 3 r}^{*} (s)

is shown in Figure 8.

Figure 8

The step response of $F_{t p 3 r}^{*} (s)$ .

When $N^{*} = 5$ , by (42), we calculate the cumulative location error as $F_{t p 3 r}^{*} (s) = (2 / (s + 2))^{25}$ . The probability of an uncovered hole existing at the right endpoint of L becomes $p_{t p 3 r}^{*} = 1 - F_{t p 3 r}^{*} (t \leq 11.5) = 0.63$ .

When $N^{*} = 10$ , we have $F_{t p 3 r}^{*} (s) = (2 / (s + 2))^{30}$ . The probability of an uncovered hole existing at the right endpoint of L becomes $p_{t p 3 r}^{*} = 1 - F_{t p 3 r}^{*} (t \leq 17.8) = 0.15$ .

When $N^{*} = 15$ , we have $F_{t p 3 r}^{*} (s) = (2 / (s + 2))^{35}$ . The probability of an uncovered hole existing at the right endpoint of L becomes $p_{t p 3 r}^{*} = 1 - F_{t p 3 r}^{*} (t \leq 21.5) = 0.06$ .

Obviously, we can see that the probability of having uncovered holes is reduced by deploying more nodes.

6.3. Equip More GPSs

As shown in Figure 6(c), more nodes are equipped with a GPS receiver. Obviously, the probability of the first type of uncovered hole existing is still $0$ . There may exist the second and third types of uncovered holes. By (30) and (32), we calculate the cumulative location errors: $F_{t p 2}^{+} (s)$ and $F_{t p 3 r}^{+} (s)$ . The step responses of them are shown in Figure 9.

Figure 9

The step responses: (a) step response of $F_{t p 2}^{+} (s)$ ; (b) step response of $F_{t p 3 r}^{+} (s)$ .

When we equip one more GPS receiver (on $S_{11}$ ), we have $F_{t p 2}^{+} (s) = (2 / (s + 2))^{9}$ and $F_{t p 3 r}^{+} (s) = (2 / (s + 2))^{10}$ . By using (36), the probability of a second type of uncovered hole existing is $p_{t p 2}^{+} = 1 - F_{t p 2}^{+} (t \leq 5) = 0.33$ . The probability of an uncovered hole existing at the right endpoint of L becomes $p_{t p 3 r}^{+} = 1 - F_{t p 3 r}^{+} (t \leq 2.5) = 0.97$ .

When we equip two more GPS receivers (on $S_{8}$ and $S_{15}$ ), we have $F_{t p 2}^{+} (s) = (2 / (s + 2))^{6}$ and $F_{t p 3 r}^{+} (s) = (2 / (s + 2))^{6}$ . By using (36), the probability of a second type of uncovered hole existing is $p_{t p 2}^{+} = 1 - F_{t p 2}^{+} (t \leq 5) = 0.06$ . The probability of an uncovered hole existing at the right endpoint of L becomes $p_{t p 3 r}^{+} = 1 - F_{t p 3 r}^{+} (t \leq 2.5) = 0.62$ .

When we equip three more GPS receivers (on $S_{6}$ , $S_{11}$ and $S_{16}$ ), we have $F_{t p 2}^{+} (s) = (2 / (s + 2))^{4}$ and $F_{t p 3 r}^{+} (s) = (2 / (s + 2))^{5}$ . By using (36), the probability of a second type of uncovered hole existing is $p_{t p 2}^{+} = 1 - F_{t p 2}^{+} (t \leq 5) = 0.01$ . The probability of an uncovered hole existing at the right endpoint of L becomes $p_{t p 3 r}^{+} = 1 - F_{t p 3 r}^{+} (t \leq 2.5) = 0.44$ .

Thus, the probability of having uncovered holes is reduced by equipping more GPS receivers.

In general, we have shown how to use our framework by the examples and get the probabilities of the uncovered holes existence. When the probabilities cannot meet our requirement, we adaptively enlarge the node's sensing ability (sensing range), deploy more nodes, or equip more GPS receivers to achieve high quality barrier coverage.

7. Conclusions

In this paper, we study how to efficiently schedule mobile sensor nodes to form a barrier when sensor nodes suffer from location errors. We find that when location errors exist, there may exist uncovered holes on the barrier and the quality of sensing cannot be guaranteed. We give the theoretical relationship between the length of the uncovered holes and the cumulative location errors. To get the cumulative location errors efficiently, we propose a method which calculates them in the frequency domain. We analyze the step responses to get the probabilities of having uncovered holes on the barrier. To guarantee the quality of sensing, we adaptively enlarge the node's sensing ability (sensing range), deploy more nodes, or equip more GPS receivers to reduce the probability of uncovered hole existing. In the future work, we will consider the constraints of the actual systems, like the cost constraints, the battery constraints, and the constraints of the probability of uncovered hole existence, and optimize the systems performance.

Footnotes

Conflict of Interests

The authors declare that there is no conflict of interests regarding the publication of this paper.

Acknowledgments

Project is supported by the National Natural Science Foundation of China (nos. 61273079 and 61502352), Key Laboratory of Wireless Sensor Network and Communication of Chinese Academy of Sciences (no. WSNC2014001), the Open Research Project of the State Key Lab of Industrial Control Technology, Zhejiang University (nos. ICT1541 and ICT1555), the Natural Science Foundation of Hubei Province, China (no. 2015CFB203), and the Natural Science Foundation of Jiangsu Province, China (no. BK20150383).

References

Lewis

F. L.

Wireless sensor networks

Smart Environments: Technologies, Protocols, and Applications 2004 chapter 2

John Wiley & Sons

11 46

10.1002/047168659X.ch2

Stankovic

J. A.

Wireless sensor networks

IEEE Computer 2008 41 10 92 95

10.1109/mc.2008.441

2-s2.0-54949142512

Liu

Chen

Analysis and improvement of send-and-wait automatic repeat-request protocols for wireless sensor networks

Wireless Personal Communications 2015 81 3 923 959

10.1007/s11277-014-2164-6

Jiang

Liu

Chen

Lifetime maximization through dynamic ring-based routing scheme for correlated data collecting in WSNs

Computers and Electrical Engineering 2015 41 191 215

10.1016/j.compeleceng.2014.04.001

2-s2.0-84899036051

Duan

Hou

Cheng

Chen

Multiperiod scheduling for wireless sensor networks: a distributed consensus approach

IEEE Transactions on Signal Processing 2015 63 7 1651 1663

10.1109/TSP.2015.2394507

MR3318489

Cheng

Chen

Shi

Time synchronization for random mobile sensor networks

IEEE Transactions on Vehicular Technology 2014 63 8 3935 3946

10.1109/tvt.2014.2307076

2-s2.0-84908110390

Chen

Jiang

Yau

D. K. Y.

Xing

Sun

Energy provisioning in wireless rechargeable sensor networks

IEEE Transactions on Mobile Computing 2013 12 10 1931 1942

10.1109/TMC.2012.161

2-s2.0-84883113038

Chen

Yau

D. K. Y.

Shao

Sun

Energy-efficient capture of stochastic events under periodic network coverage and coordinated sleep

IEEE Transactions on Parallel and Distributed Systems 2012 23 6 1090 1102

10.1109/TPDS.2011.242

2-s2.0-84860530340

Chen

Shen

Sun

Leveraging prediction to improve the coverage of wireless sensor networks

IEEE Transactions on Parallel and Distributed Systems 2012 23 4 701 712

10.1109/tpds.2011.180

2-s2.0-84862776772

10.

Wang

Liao

Cao

Wang

Achieving k-barrier coverage in hybrid directional sensor networks

IEEE Transactions on Mobile Computing 2014 13 7 1443 1455

10.1109/tmc.2013.118

2-s2.0-84903757919

11.

Saipulla

Liu

Wang

Barrier coverage with airdropped wireless sensors

Proceedings of the IEEE Military Communications Conference (MILCOM ′08)

November 2008

San Diego, Calif, USA

1 7

10.1109/MILCOM.2008.4753650

12.

Dantu

Rahimi

Shah

Babel

Dhariwal

Sukhatme

G. S.

Robomote: enabling mobility in sensor networks

Proceedings of the 4th International Symposium on Information Processing in Sensor Networks (IPSN ′05)

April 2005

Piscataway, NJ, USA

404 409

10.1109/ipsn.2005.1440957

2-s2.0-33744928874

13.

Somasundara

A. A.

Ramamoorthy

Srivastava

M. B.

Mobile element scheduling with dynamic deadlines

IEEE Transactions on Mobile Computing 2007 6 4 395 410

10.1109/tmc.2007.57

2-s2.0-33847756370

14.

Hofmann-Wellenhof

Lichtenegger

Collins

Global Positioning System: Theory and Practice 2012

Springer Science & Business Media

15.

Pirzadeh

Computational geometry with the rotating calipers [M.S. thesis] 1999

Montréal, Canada

McGill University

16.

Zhang

Yin

Feng

Distributed TDOA estimation for wireless sensor networks based on frequency-hopping in multipath environment

Proceedings of the IEEE Vehicular Technology Conference

2010

17.

Zhu

Huang

Node localization algorithm based on AOA for WSNs

Transducer and Microsystem Technologies 2010 1, article 32

18.

Lee

Y. S.

Lee

J.-M.

Park

J. H.

Yeo

S. S.

Barolli

A study on the performance of wireless localization system based on AoA in WSN environment

Proceedings of IEEE 3rd IEEE International Conference on Intelligent Networking and CollaborativeSystems (INCoS ′11)

December 2011

Fukuoka, Japan

184 187

10.1109/incos.2011.42

2-s2.0-84863173446

19.

Awad

Frunzke

Dressler

Adaptive distance estimation and localization in WSN using RSSI measures

Proceedings of the IEEE 10th Euromicro Conference on Digital System Design Architectures, Methods and Tools (DSD ′07)

August 2007

Lubeck, Germany

471 478

10.1109/DSD.2007.4341511

20.

Zanca

Zorzi

Zanella

Zorzi

Experimental comparison of RSSI-based localization algorithms for indoor wireless sensor networks

Proceedings of the ACM Workshop on Real-World Wireless Sensor Networks (REALWSN ′08)

April 2008

Glasgow, Scotland

ACM

1 5

10.1145/1435473.1435475

21.

Shi

Chew

Y. H.

Yuen

Yang

A RSS-EKF localization method using HMM-based LOS/NLOS channel identification

Proceedings of the IEEE International Conference on Communications (ICC ′14)

June 2014

Sydney, Australia

160 165

10.1109/ICC.2014.6883312

22.

Kumar

Lai

T. H.

Arora

Barrier coverage with wireless sensors

Proceedings of the ACM 11th Annual International Conference on Mobile Computing and Networking (MobiCom ′05)

August-September 2005

Cologne, Germany

23.

Liu

Dousse

Wang

Saipulla

Strong barrier coverage of wireless sensor networks

Proceedings of the 9th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc ′08)

May 2008

Hong Kong

ACM

411 420

10.1145/1374618.1374673

24.

Zhang

Shen

Zheng

Yao

A study on the weak barrier coverage problem in wireless sensor networks

Computer Networks 2011 55 3 711 721

10.1016/j.comnet.2010.10.008

2-s2.0-79951513958

25.

Gong

Zhang

Chen

Sun

Curve-based deployment for barrier coverage in wireless sensor networks

IEEE Transactions on Wireless Communications 2014 13 2 724 735

10.1109/twc.2013.121813.130198

2-s2.0-84896396765

26.

Chen

Lai

T. H.

Energy-efficient intrusion detection with a barrier of probabilistic sensors

Proceedings of the IEEE Conference on Computer Communications (INFOCOM ′12)

March 2012

Orlando, Fla, USA

118 126

10.1109/infcom.2012.6195479

2-s2.0-84861587761

27.

Chen

Lai

T. H.

Energy-efficient intrusion detection with a barrier of probabilistic sensors: global and local

IEEE Transactions on Wireless Communications 2013 12 9 4742 4755

10.1109/tw.2013.072313.122083

2-s2.0-84884907077

28.

Chen

Shen

Sun

Cost-effective barrier coverage by mobile sensor networks

Proceedings of the 31st Annual IEEE International Conference on Computer Communications (INFOCOM ′12)

March 2012

Orlando, Fla, USA

IEEE

819 827

10.1109/INFCOM.2012.6195829

29.

Saipulla

Liu

Xing

Wang

Barrier coverage with sensors of limited mobility

Proceedings of the 11th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc ′10)

September 2010

Chicago, Ill, USA

ACM

201 210

10.1145/1860093.1860121

2-s2.0-78649291566

30.

Shen

Cheng

Liao

Peng

Barrier coverage with mobile sensors

Proceedings of the International Symposium on Parallel Architectures, Algorithms, and Networks (I-SPAN ′08)

May 2008

Sydney, Australia

IEEE

99 104

10.1109/I-SPAN.2008.8

31.

Wang

Chen

Cao

Wang

Fault tolerant barrier coverage for wireless sensor networks

Proceedings of the IEEE INFOCOM

May 2014

Toronto, Canada

1869 1877

10.1109/infocom.2014.6848126

2-s2.0-84904437348

32.

Chen

Shen

X. S.

Sun

Mobility and intruder prior information improving the barrier coverage of sparse sensor networks

IEEE Transactions on Mobile Computing 2014 13 6 1268 1282

10.1109/TMC.2013.129

2-s2.0-84902184986