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[-\mathrm{3}\hspace{0.17em}\mathrm{m},\mathrm{3}\hspace{0.17em}\mathrm{m}]$ ; node C is located relative to node B, and the location error follows $U[-\mathrm{5}\hspace{0.17em}\mathrm{m},\mathrm{5}\hspace{0.17em}\mathrm{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[-\mathrm{3}\hspace{0.17em}\mathrm{m},\mathrm{3}\hspace{0.17em}\mathrm{m}]$ and $U[-5\hspace{0.17em}\mathrm{m},\mathrm{5}\hspace{0.17em}\mathrm{m}]$ . From the error distribution, we could get the probability of location error of any value other than the lower and upper bounds ( $-\mathrm{8}\hspace{0.17em}\mathrm{m}$ and $\mathrm{8}\hspace{0.17em}\mathrm{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>\mathrm{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 $[\mathrm{0}:L]$ , whose line has two endpoints, 0 and $L>\mathrm{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/\mathrm{2}$ , the node to the right end is deployed at location $ND/\mathrm{2}$ , and the interval between any two neighboring nodes is D. To guarantee the overlap of any two neighboring nodes, condition $D\le \mathrm{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{array}{cc}& N_{\min }=\text{ceil}\left(\frac{L}{\mathrm{2}{r}_s}\right).\end{array}$$

(1)

As shown in Figure 2(a), we deploy $N_{\mathrm{m}\mathrm{i}\mathrm{n}}$ nodes on line L. D is set to $\mathrm{2}{r}_s$ , and node $S_i$ is deployed at $(\mathrm{2}i-\mathrm{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 ${\widehat{x}}_a$ . If $S_a$ is equipped with a GPS receiver, then ${\widehat{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 ${\widehat{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{array}{cc}& {\widehat{x}}_b={\widehat{x}}_a-{\widehat{L}}_{a,b};\end{array}$$

(2)

otherwise, the measured location of $S_b$ is

$$\begin{array}{cc}& {\widehat{x}}_b={\widehat{x}}_a+{\widehat{L}}_{a,b}.\end{array}$$

(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{array}{cc}& \Delta L_{\mathrm{h}\mathrm{o}\mathrm{p}}^b={\widehat{L}}_{a,b}-L_{a,b},\end{array}$$

(4)

where ${\widehat{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; $\Delta L_{\mathrm{h}\mathrm{o}\mathrm{p}}^b$ denotes the one-hop location error of node $S_b$ .

Definition 1.

The one-hop location error $L_{\mathrm{h}\mathrm{o}\mathrm{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_{\mathrm{m}\mathrm{i}\mathrm{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 ${\widehat{x}}_i$ . When the sensor node finishes moving, we get

$$\begin{array}{cc}& {\widehat{x}}_i=\left(\mathrm{2}i-\mathrm{1}\right)r_s.\end{array}$$

(5)

However, due to location error, we get

$$\begin{array}{cc}& x_i\ne {\widehat{x}}_i=\left(\mathrm{2}i-\mathrm{1}\right)r_s;\end{array}$$

(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{array}{cc}& h_{tp\mathrm{1}}=\max \left(\mathrm{0},D-\mathrm{2}{r}_s-\Delta L_{hop}^q\right).\end{array}$$

(7)

Proof.

The interval between nodes $S_p$ and $S_q$ is set to D; we get

$$\begin{array}{cc}& {\widehat{x}}_q-{\widehat{x}}_p=D=\widehat{L_{p,q}}.\end{array}$$

(8)

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

$$\begin{array}{cc}& L_{p,q}=\widehat{L_{p,q}}-\Delta L_{\mathrm{h}\mathrm{o}\mathrm{p}}^q=D-\Delta L_{\mathrm{h}\mathrm{o}\mathrm{p}}^q.\end{array}$$

(9)

As shown in Figure 3(a), when $\mathrm{2}{r}_s-L_{p,q}>\mathrm{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}=\mathrm{0}$ . However, as shown in Figure 3(b), when $\mathrm{2}{r}_s-L_{p,q}<\mathrm{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{array}{cc}& h_{p,q}=L_{p,q}-\mathrm{2}{r}_s.\end{array}$$

(10)

Combining with (9) and (10), we get $h_{p,q}=D-\mathrm{2}{r}_s-\Delta L_{\mathrm{h}\mathrm{o}\mathrm{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-\mathrm{1}}$ , and node $S_{d-M}$ is equipped with a GPS receiver. Similarly, node $S_{e+i}$ 's beacon node is $S_{e+i+\mathrm{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=\mathrm{0}$ or $K=\mathrm{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{array}{cc}& h_{tp\mathrm{2}}=\max \left(\mathrm{0},D-\mathrm{2}{r}_s+{\displaystyle \sum }_{i=\mathrm{1}-M}^{K-\mathrm{1}}\Delta L_{hop}^{d+i}\right).\end{array}$$

(11)

Proof.

Since the interval between nodes $S_d$ and $S_e$ is set to D, we get

$$\begin{array}{cc}& {\widehat{x}}_e-{\widehat{x}}_d=D.\end{array}$$

(12)

Obviously, we get

$$\begin{array}{cc}& {\widehat{x}}_d={\widehat{x}}_{d-M}+{\widehat{L}}_{d-M,d-M+\mathrm{1}}+\cdots +{\widehat{L}}_{d-\mathrm{1},d}.\end{array}$$

(13)

Combining with (4), we get

$$\begin{array}{cc}& {\widehat{x}}_d={\widehat{x}}_{d-M}+\left(L_{d-M,d-M+\mathrm{1}}+\cdots +L_{d-\mathrm{1},d}\right)+{\displaystyle \sum }_{i=\mathrm{1}}^M\Delta L_{\mathrm{h}\mathrm{o}\mathrm{p}}^{d-i+\mathrm{1}}.\end{array}$$

(14)

Since $S_{d-M}$ is equipped with GPS receiver, we have ${\widehat{x}}_{d-M}=x_{d-M}$ . Hence, we get

$$\begin{array}{cc}& {\widehat{x}}_d=x_{d-M}+\left(L_{d-M,d-M+\mathrm{1}}+\cdots +L_{d-\mathrm{1},d}\right)+{\displaystyle \sum }_{i=\mathrm{1}}^M\Delta L_{\mathrm{h}\mathrm{o}\mathrm{p}}^{d-i+\mathrm{1}}=x_d+{\displaystyle \sum }_{i=\mathrm{1}}^M\Delta L_{\mathrm{h}\mathrm{o}\mathrm{p}}^{d-i+\mathrm{1}}.\end{array}$$

(15)

Similarly, for $S_e$ , we get

$$\begin{array}{cc}& {\widehat{x}}_e=x_e-{\displaystyle \sum }_{j=\mathrm{1}}^K\Delta L_{\mathrm{h}\mathrm{o}\mathrm{p}}^{e+j-\mathrm{1}}.\end{array}$$

(16)

As shown in Figure 4(a), when $x_e-x_d-\mathrm{2}{r}_s<\mathrm{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-\mathrm{2}{r}_s>\mathrm{0}$ , that is, they have no overlapping area, there is an uncovered hole between them and its length is

$$\begin{array}{cc}& h_{d,e}=x_e-x_d-\mathrm{2}{r}_s.\end{array}$$

(17)

Combining with (12), (15), (16), and (17), we get $h_{d,e}=D-\mathrm{2}{r}_s+{\sum }_{i=\mathrm{1}}^M\Delta L_{\mathrm{h}\mathrm{o}\mathrm{p}}^{d-i+\mathrm{1}}+{\sum }_{j=\mathrm{1}}^K\Delta L_{\mathrm{h}\mathrm{o}\mathrm{p}}^{e+j-\mathrm{1}}$ . Since nodes $S_d$ and $S_e$ are neighboring nodes, we get $e=d+\mathrm{1}$ . Hence, $h_{d,e}=D-\mathrm{2}{r}_s+{\sum }_{i=\mathrm{1}-M}^{K-\mathrm{1}}\Delta L_{\mathrm{h}\mathrm{o}\mathrm{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-\mathrm{1}}$ , and $S_{l+P}$ is equipped with a GPS receiver. Similarly, node $S_{r-j}$ 's beacon node is $S_{r-j-\mathrm{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=\mathrm{0}$ or $Q=\mathrm{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{array}{cc}& h_{tp\mathrm{3}l}=\max \left(\mathrm{0},\frac{D}{\mathrm{2}}-r_s+{\displaystyle \sum }_{i=\mathrm{1}}^P\Delta L_{hop}^{l+i-\mathrm{1}}\right).\end{array}$$

(18)

And the length of the uncovered hole between the rightmost node $S_r$ and the right endpoint of L is

$$\begin{array}{cc}& h_{tp\mathrm{3}r}=\max \left(\mathrm{0},\frac{D}{\mathrm{2}}-r_s+{\displaystyle \sum }_{j=\mathrm{1}}^Q\Delta L_{hop}^{r-j+\mathrm{1}}\right).\end{array}$$

(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/\mathrm{2}$ , we get

$$\begin{array}{cc}& {\widehat{x}}_l=\frac{D}{\mathrm{2}}.\end{array}$$

(20)

Then, we get

$$\begin{array}{cc}& {\widehat{x}}_l={\widehat{x}}_{l+P}-{\widehat{L}}_{l+P-\mathrm{1},l+P}-\cdots -{\widehat{L}}_{l,l+\mathrm{1}}.\end{array}$$

(21)

Since node $S_{l+P}$ is equipped with a GPS receiver, we can get ${\widehat{x}}_{l+P}=x_{l+P}$ . Combining with (4) and (21), we get

$$\begin{array}{cc}& {\widehat{x}}_l=x_{l+P}-\left(L_{l+P-\mathrm{1},l+P}+\cdots +L_{l+\mathrm{1},l}\right)-{\displaystyle \sum }_{i=\mathrm{1}}^P\Delta L_{\mathrm{h}\mathrm{o}\mathrm{p}}^{l+i-\mathrm{1}}=x_l-{\displaystyle \sum }_{i=\mathrm{1}}^P\Delta L_{\mathrm{h}\mathrm{o}\mathrm{p}}^{l+i-\mathrm{1}}.\end{array}$$

(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{array}{cc}& h_l=x_l-r_s.\end{array}$$

(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/\mathrm{2}-r_s+{\sum }_{i=\mathrm{1}}^P\Delta L_{\mathrm{h}\mathrm{o}\mathrm{p}}^{l+i-\mathrm{1}}$ .

Similarly, we can prove $h_r=\mathrm{m}\mathrm{a}\mathrm{x}(\mathrm{0},D/\mathrm{2}-r_s+{\sum }_{j=\mathrm{1}}^Q\Delta L_{\mathrm{h}\mathrm{o}\mathrm{p}}^{r-j+\mathrm{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 $\Delta L_{\mathrm{h}\mathrm{o}\mathrm{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 $\Delta L_{\mathrm{h}\mathrm{o}\mathrm{p}}$ denote the one-hop location error in the network. The probability density function of $\Delta L_{\mathrm{h}\mathrm{o}\mathrm{p}}$ is denoted by $f_{\mathrm{h}\mathrm{o}\mathrm{p}}(t)$ . Considering Theorems 2, 3, and 4, $\Delta L_{\mathrm{h}\mathrm{o}\mathrm{p}}^q$ represent the (cumulative) location error part in (7), ${\sum }_{i=\mathrm{1}-M}^{K-\mathrm{1}}\Delta L_{\mathrm{h}\mathrm{o}\mathrm{p}}^{d+i}$ in (11), ${\sum }_{i=\mathrm{1}}^P\Delta L_{\mathrm{h}\mathrm{o}\mathrm{p}}^{l+i-\mathrm{1}}$ in (18), and ${\sum }_{j=\mathrm{1}}^Q\Delta L_{\mathrm{h}\mathrm{o}\mathrm{p}}^{r-j+\mathrm{1}}$ in (19), respectively. For the cumulative location errors, we get the following.

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

$$\begin{array}{cc}& f_{tp\mathrm{1}}\left(t\right)=f_{\mathrm{h}\mathrm{o}\mathrm{p}}^q\left(t\right).\end{array}$$

(24)

Let $\Delta L_{tp\mathrm{2}}={\sum }_{i=\mathrm{1}-M}^{K-\mathrm{1}}\Delta L_{\mathrm{h}\mathrm{o}\mathrm{p}}^{d+i}$ , and its probability density function is denoted by $f_{tp\mathrm{2}}(t)$ . We have

$$\begin{array}{cc}& f_{tp\mathrm{2}}\left(t\right)=f_{\mathrm{h}\mathrm{o}\mathrm{p}}^{d-M+\mathrm{1}}\left(t\right)\otimes f_{\mathrm{h}\mathrm{o}\mathrm{p}}^{d-M+\mathrm{2}}\left(t\right)\cdots \otimes f_{\mathrm{h}\mathrm{o}\mathrm{p}}^{d+K-\mathrm{1}}\left(t\right).\end{array}$$

(25)

Let $\Delta L_{tp\mathrm{3}l}={\sum }_{i=\mathrm{1}}^P\Delta L_{\mathrm{h}\mathrm{o}\mathrm{p}}^{l+i-\mathrm{1}}$ , and its probability density function is denoted by $f_{tp\mathrm{3}l}(t)$ . Let $\Delta L_{tp\mathrm{3}r}={\sum }_{j=\mathrm{1}}^Q\Delta L_{\mathrm{h}\mathrm{o}\mathrm{p}}^{r-j+\mathrm{1}}$ , and its probability density function is denoted by $f_{tp\mathrm{3}r}(t)$ . We have

$$\begin{array}{cc}& f_{tp\mathrm{3}l}\left(t\right)=f_{\mathrm{h}\mathrm{o}\mathrm{p}}^l\left(t\right)\otimes f_{\mathrm{h}\mathrm{o}\mathrm{p}}^{l+\mathrm{1}}\left(t\right)\cdots \otimes f_{\mathrm{h}\mathrm{o}\mathrm{p}}^{l+P}\left(t\right),\\ f_{tp\mathrm{3}r}\left(t\right)=f_{\mathrm{h}\mathrm{o}\mathrm{p}}^r\left(t\right)\otimes f_{\mathrm{h}\mathrm{o}\mathrm{p}}^{r-\mathrm{1}}\left(t\right)\cdots \otimes f_{\mathrm{h}\mathrm{o}\mathrm{p}}^{r-Q}\left(t\right).\end{array}$$

(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_{tp\mathrm{1}}(t)$ , $f_{tp\mathrm{2}}(t)$ , $f_{tp\mathrm{3}l}(t)$ , and $f_{tp\mathrm{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{array}{cc}& \mathcal{F}\left(s\right)=\mathcal{L}\left[f\left(t\right)\right]={{\displaystyle \int }}_{\mathrm{0}}^{\infty }{e}^{-st}f\left(t\right)dt,\end{array}$$

(27)

where $\mathcal{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 $\mathcal{F}(s)$ in frequency domain, it could easily get $f(t)$ by using Inverse Laplace Transform as follows:

$$\begin{array}{cc}& f\left(t\right)={\mathcal{L}}^{-\mathrm{1}}\left[\mathcal{F}\left(s\right)\right]=\frac{\mathrm{1}}{j\mathrm{2}\pi }{{\displaystyle \int }}_{\sigma -j\infty }^{\sigma +j\infty }{e}^{st}\mathcal{F}\left(s\right)ds.\end{array}$$

(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{array}{cc}& {\mathcal{F}}_{tp\mathrm{1}}\left(s\right)=\mathcal{L}\left[f_{tp\mathrm{1}}\left(t\right)\right]={\mathcal{F}}_{\mathrm{h}\mathrm{o}\mathrm{p}}^q\left(s\right);\end{array}$$

(29)

$\begin{array}{cc}& {\mathcal{F}}_{tp\mathrm{2}}\left(s\right)=\mathcal{L}\left[f_{tp\mathrm{2}}\left(t\right)\right]={\displaystyle \prod }_{i=\mathrm{1}-M}^{K-\mathrm{1}}{\mathcal{F}}_{\mathrm{h}\mathrm{o}\mathrm{p}}^{d+i}\left(s\right);\end{array}$

(30)

$\begin{array}{cc}& {\mathcal{F}}_{tp\mathrm{3}l}\left(s\right)=\mathcal{L}\left[f_{tp\mathrm{3}l}\left(t\right)\right]={\displaystyle \prod }_{i=\mathrm{1}}^P{\mathcal{F}}_{\mathrm{h}\mathrm{o}\mathrm{p}}^{l+i-\mathrm{1}}\left(s\right);\end{array}$

(31)

$\begin{array}{cc}& {\mathcal{F}}_{tp\mathrm{3}r}\left(s\right)=\mathcal{L}\left[f_{tp\mathrm{3}r}\left(t\right)\right]={\displaystyle \prod }_{i=\mathrm{1}}^Q{\mathcal{F}}_{\mathrm{h}\mathrm{o}\mathrm{p}}^{r-j+\mathrm{1}}\left(s\right).\end{array}$

(32)

Let $\mathcal{F}(s)$ denote the cumulative location error in frequency domain. We give unit step function as $u\left(t\right)=1$ , if $t\ge \mathrm{0}$ ; $\mathrm{0}$ , if $t<\mathrm{0}$ . Step response means the response (output) to a unit step-function input. In control theory, the step response of $\mathcal{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{array}{cc}& \mathcal{L}\left[y_{u\left(t\right)}\right]=\mathcal{L}\left[u\left(t\right)\right]·\mathcal{F}\left(s\right)=\frac{\mathrm{1}}{s}·\mathcal{F}\left(s\right).\end{array}$$

(33)

The step response can be obtained by Inverse Laplace Transform as

$$\begin{array}{cc}& y_{u\left(t\right)}={\mathcal{L}}^{-\mathrm{1}}\left[\frac{\mathrm{1}}{s}·\mathcal{F}\left(s\right)\right]={{\displaystyle \int }}_{\mathrm{0}}^{t}f\left(\tau \right)d\tau =F\left(t\right),\end{array}$$

(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_{tp\mathrm{1}}=\mathrm{m}\mathrm{a}\mathrm{x}(\mathrm{0},D-\mathrm{2}{r}_s-\Delta L_{\mathrm{h}\mathrm{o}\mathrm{p}}^q)=\mathrm{m}\mathrm{a}\mathrm{x}(\mathrm{0},D-\mathrm{2}{r}_s-\Delta L_{tp\mathrm{1}})$ . Thus, when there is no uncovered hole, it satisfies $\Delta L_{tp\mathrm{1}}\ge D-\mathrm{2}{r}_s$ . The probability distribution function (i.e., step response) of $\Delta L_{tp\mathrm{1}}$ is $F_{tp\mathrm{1}}(t)$ . We have

$$\begin{array}{cc}& p_{tp\mathrm{1}}=\mathrm{1}-F_{tp\mathrm{1}}\left(t\ge D-\mathrm{2}{r}_s\right),\end{array}$$

(35)

which means the probability of the first type of uncovered hole is $p_{tp\mathrm{1}}$ .

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

$$\begin{array}{cc}& p_{tp\mathrm{2}}=\mathrm{1}-F_{tp\mathrm{2}}\left(t\le \mathrm{2}{r}_s-D\right).\end{array}$$

(36)

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

$$\begin{array}{cc}& p_{tp\mathrm{3}l}=\mathrm{1}-F_{tp\mathrm{3}l}\left(t\le r_s-\frac{D}{\mathrm{2}}\right),\end{array}$$

(37)

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

$$\begin{array}{cc}& p_{tp\mathrm{3}r}=\mathrm{1}-F_{tp\mathrm{3}r}\left(t\le r_s-\frac{D}{\mathrm{2}}\right).\end{array}$$

(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^{\ast }$	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 $\mathrm{21}$ mobile nodes to form a barrier. The designed interval between any two neighboring nodes is $D=L/N=\mathrm{2000}/\mathrm{21}=95\hspace{0.17em}\mathrm{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_{\mathrm{1}}$ is equipped with a GPS receiver. The locations of other nodes are obtained by using localization algorithms. Node $S_i$ is $S_{i+\mathrm{1}}$ 's beacon node. The results provided by the location algorithms contain location errors. The probability density function $f_{\mathrm{h}\mathrm{o}\mathrm{p}}^i(t)$ of any one-hop location error is

$$\begin{array}{cc}& f_{\mathrm{h}\mathrm{o}\mathrm{p}}^i\left(t\right)=\left\{\begin{array}{cc}\mathrm{2}{e}^{-\mathrm{2}t},\hfill & t\ge \mathrm{0},\hfill \\ 0,\hfill & t<\mathrm{0},\hfill \end{array}\right.\end{array}$$

(39)

which follows an exponential distribution.

Figure 6

The example systems: (a) we deploy 21 nodes, and only node $S_{\mathrm{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_{\mathrm{h}\mathrm{o}\mathrm{p}}^i(t)$ into the frequency domain. We get

$$\begin{array}{cc}& {\mathcal{F}}_{\mathrm{h}\mathrm{o}\mathrm{p}}^i\left(s\right)=\mathcal{L}\left[f_{\mathrm{h}\mathrm{o}\mathrm{p}}^i\left(t\right)\right]=\frac{\mathrm{2}}{s+\mathrm{2}}.\end{array}$$

(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{array}{cc}& {\mathcal{F}}_{tp\mathrm{1}}\left(s\right)=\frac{\mathrm{2}}{s+\mathrm{2}};\\ {\mathcal{F}}_{tp\mathrm{3}r}\left(s\right)={\left(\frac{\mathrm{2}}{s+\mathrm{2}}\right)}^{\mathrm{20}}.\end{array}$$

(41)

The step response of ${\mathcal{F}}_{tp\mathrm{1}}(s)$ is shown in Figure 7(a). By using (35), the probability of any first type of uncovered hole existing is $p_{tp\mathrm{1}}=\mathrm{1}-F_{tp\mathrm{1}}\hspace{0.17em}\hspace{0.17em}(t\ge -\mathrm{5})=\mathrm{0}$ . The step response of ${\mathcal{F}}_{tp\mathrm{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_{tp\mathrm{3}r}=\mathrm{1}-F_{tp\mathrm{3}r}\hspace{0.17em}\hspace{0.17em}(t\le \mathrm{2.5})=\mathrm{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 ${\mathcal{F}}_{tp\mathrm{1}}(s)$ ; (b) step response of ${\mathcal{F}}_{tp\mathrm{3}r}(s)$ .

We have obtained the probability of an uncovered hole existing at the right endpoint which is $\mathrm{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 ${\mathcal{F}}_{tp\mathrm{1}}(s)$ and ${\mathcal{F}}_{tp\mathrm{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_{tp\mathrm{1}}=\mathrm{1}-F_{tp\mathrm{1}}\hspace{0.17em}\hspace{0.17em}(t\ge -\mathrm{25})=\mathrm{0}$ , and the probability of the third type of hole existing is $p_{tp\mathrm{3}r}=\mathrm{1}-F_{tp\mathrm{3}r}\hspace{0.17em}\hspace{0.17em}(t\le \mathrm{12.5})=\mathrm{0.13}$ ; (b) when $r_s$ is enlarged to 70 m, we have $p_{tp\mathrm{1}}=\mathrm{1}-F_{tp\mathrm{1}}\hspace{0.17em}\hspace{0.17em}(t\ge -\mathrm{45})=\mathrm{0}$ and $p_{tp\mathrm{3}r}=\mathrm{1}-F_{tp\mathrm{3}r}\hspace{0.17em}\hspace{0.17em}(t\le \mathrm{22.5})=\mathrm{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 $\mathrm{0}$ .

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

$$\begin{array}{cc}& {\mathcal{F}}_{tp\mathrm{3}r}^{\ast }\left(s\right)={\left(\frac{\mathrm{2}}{s+\mathrm{2}}\right)}^{\mathrm{20}+N^{\ast }}.\end{array}$$

(42)

The step response ${\mathcal{F}}_{tp\mathrm{3}r}^{\ast }(s)$ is shown in Figure 8.

Figure 8

The step response of ${\mathcal{F}}_{tp\mathrm{3}r}^{\ast }(s)$ .

When $N^{\ast }=\mathrm{5}$ , by (42), we calculate the cumulative location error as ${\mathcal{F}}_{tp\mathrm{3}r}^{\ast }(s)=(\mathrm{2}/\left(s+\mathrm{2}\right){)}^{\mathrm{25}}$ . The probability of an uncovered hole existing at the right endpoint of L becomes $p_{tp\mathrm{3}r}^{\ast }=\mathrm{1}-F_{tp\mathrm{3}r}^{\ast }\hspace{0.17em}\hspace{0.17em}(t\le \mathrm{11.5})=\mathrm{0.63}$ .

When $N^{\ast }=\mathrm{10}$ , we have ${\mathcal{F}}_{tp\mathrm{3}r}^{\ast }(s)=(\mathrm{2}/\left(s+\mathrm{2}\right){)}^{\mathrm{30}}$ . The probability of an uncovered hole existing at the right endpoint of L becomes $p_{tp\mathrm{3}r}^{\ast }=\mathrm{1}-F_{tp\mathrm{3}r}^{\ast }\hspace{0.17em}\hspace{0.17em}(t\le \mathrm{17.8})=\mathrm{0.15}$ .

When $N^{\ast }=\mathrm{15}$ , we have ${\mathcal{F}}_{tp\mathrm{3}r}^{\ast }(s)=(\mathrm{2}/\left(s+\mathrm{2}\right){)}^{\mathrm{35}}$ . The probability of an uncovered hole existing at the right endpoint of L becomes $p_{tp\mathrm{3}r}^{\ast }=\mathrm{1}-F_{tp\mathrm{3}r}^{\ast }\hspace{0.17em}\hspace{0.17em}(t\le \mathrm{21.5})=\mathrm{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 $\mathrm{0}$ . There may exist the second and third types of uncovered holes. By (30) and (32), we calculate the cumulative location errors: ${\mathcal{F}}_{tp\mathrm{2}}^{+}(s)$ and ${\mathcal{F}}_{tp\mathrm{3}r}^{+}(s)$ . The step responses of them are shown in Figure 9.

Figure 9

The step responses: (a) step response of ${\mathcal{F}}_{tp\mathrm{2}}^{+}(s)$ ; (b) step response of ${\mathcal{F}}_{tp\mathrm{3}r}^{+}(s)$ .

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

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

When we equip three more GPS receivers (on $S_{\mathrm{6}}$ , $S_{\mathrm{11}}$ and $S_{\mathrm{16}}$ ), we have ${\mathcal{F}}_{tp\mathrm{2}}^{+}(s)=(\mathrm{2}/\left(s+\mathrm{2}\right){)}^{\mathrm{4}}$ and ${\mathcal{F}}_{tp\mathrm{3}r}^{+}(s)=(\mathrm{2}/\left(s+\mathrm{2}\right){)}^{\mathrm{5}}$ . By using (36), the probability of a second type of uncovered hole existing is $p_{tp\mathrm{2}}^{+}=\mathrm{1}-F_{tp\mathrm{2}}^{+}\hspace{0.17em}\hspace{0.17em}(t\le \mathrm{5})=\mathrm{0.01}$ . The probability of an uncovered hole existing at the right endpoint of L becomes $p_{tp\mathrm{3}r}^{+}=\mathrm{1}-F_{tp\mathrm{3}r}^{+}\hspace{0.17em}\hspace{0.17em}(t\le \mathrm{2.5})=\mathrm{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.