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

Authors: Jie Shen; Zhibo Wang; Zhi Wang
Journal: International Journal of Distributed Sensor Networks
 (2015)

---

## 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.


---

## Body

## 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[-3m,3m]; node C is located relative to node B, and the location error follows U[-5m,5m]. 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[-3m,3m] and U[-5m,5m]. From the error distribution, we could get the probability of location error of any value other than the lower and upper bounds (-8m and 8m). 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. Section2 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 denoteSi 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 rs. 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 rs, such as intruder B. The communication range is denoted as rc, which is larger than the sensing range rs. We assume that rc>2rs.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 ND/2, and the interval between any two neighboring nodes is D. To guarantee the overlap of any two neighboring nodes, condition D≤2rs 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 coverL is(1)Nmin⁡=ceilL2rs.As shown in Figure2(a), we deploy Nmin nodes on line L. D is set to 2rs, and node Si is deployed at (2i-1)rs. 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.
(a)
(b)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 nodeSa, with its true location being xa, and the corresponding measured location is denoted by x^a. If Sa is equipped with a GPS receiver, then x^a=xa. If there is a node Sb neighboring node Sa which needs to be located, using the above-mentioned localization algorithms, we can get the measured location of Sb and the distance L^a,b between Sa and Sb. When Sb is on the left of Sa, the measured location of Sb is(2)x^b=x^a-L^a,b;otherwise, the measured location of Sb is(3)x^b=x^a+L^a,b.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(4)ΔLhopb=L^a,b-La,b,where L^a,b denotes the measured distance between node Sa and node Sb and La,b denotes the actual distance between these two nodes; ΔLhopb denotes the one-hop location error of node Sb.Definition 1.
The one-hop location errorLhop 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 Figure2(b), we utilize Nmin 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 x^i. When the sensor node finishes moving, we get(5)x^i=2i-1rs. However, due to location error, we get(6)xi≠x^i=2i-1rs; that is, its actual location xi 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 Figure3. There are two neighboring nodes, nodes Sp and Sq, in the network. Node Sp is the beacon node of Sq. Due to the location error, an uncovered hole may exist between the locations of them. We get the following.Figure 3
NodeSp is the beacon of node Sq: (a) nodes overlap with each other and no uncovered hole exists; (b) nodes do not overlap with each other and an uncovered hole exists.
(a)
(b)Theorem 2.
For two neighboring nodes, nodesSp and Sq in the network, when node Sp is the beacon node of node Sq, the length of the uncovered hole between them is(7)htp1=max⁡0,D-2rs-ΔLhopq.Proof.
The interval between nodesSp and Sq is set to D; we get(8)x^q-x^p=D=Lp,q^.Combining with (4) and (8), we get(9)Lp,q=Lp,q^-ΔLhopq=D-ΔLhopq.As shown in Figure 3(a), when 2rs-Lp,q>0, nodes Sp and Sq overlap with each other. Thus, there is no uncovered hole between these two locations; that is, hp,q=0. However, as shown in Figure 3(b), when 2rs-Lp,q<0, nodes Sp and Sq do not overlap with each other. There is an uncovered hole between them, and its corresponding length is(10)hp,q=Lp,q-2rs.Combining with (9) and (10), we get hp,q=D-2rs-ΔLhopq.


### 4.2. The Second Type of the Uncovered Hole

The second type of uncovered hole is shown as in Figure4. There are two neighboring nodes, nodes Sd and Se, in the network. Node Sd-i’s beacon node is node Sd-i-1, and node Sd-M is equipped with a GPS receiver. Similarly, node Se+i’s beacon node is Se+i+1, and node Se+K is equipped with a GPS receiver. M is defined as the hops from node Sd to its nearest GPS node. K is defined as the hops from node Se to its nearest GPS node. When M=0 or K=0, there is a GPS receiver equipped on Sd or Se, respectively. We get the following.Figure 4
S
d and Se are not located based on the other: (a) no uncovered hole exists; (b) an uncovered hole exists.
(a)
(b)Theorem 3.
For two neighboring nodes, nodesSd and Se in the network, where the two nodes are not located based on one another,(11)htp2=max⁡0,D-2rs+∑i=1-MK-1ΔLhopd+i.Proof.
Since the interval between nodesSd and Se is set to D, we get(12)x^e-x^d=D.Obviously, we get(13)x^d=x^d-M+L^d-M,d-M+1+⋯+L^d-1,d. Combining with (4), we get(14)x^d=x^d-M+Ld-M,d-M+1+⋯+Ld-1,d+∑i=1MΔLhopd-i+1. Since Sd-M is equipped with GPS receiver, we have x^d-M=xd-M. Hence, we get(15)x^d=xd-M+Ld-M,d-M+1+⋯+Ld-1,d+∑i=1MΔLhopd-i+1=xd+∑i=1MΔLhopd-i+1.
Similarly, forSe, we get(16)x^e=xe-∑j=1KΔLhope+j-1.
As shown in Figure4(a), when xe-xd-2rs<0, that is, nodes Sd and Se overlap with each other, there is no uncovered hole between these two locations. However, as shown in Figure 4(b), when xe-xd-2rs>0, that is, they have no overlapping area, there is an uncovered hole between them and its length is(17)hd,e=xe-xd-2rs.Combining with (12), (15), (16), and (17), we get hd,e=D-2rs+∑i=1MΔLhopd-i+1+∑j=1KΔLhope+j-1. Since nodes Sd and Se are neighboring nodes, we get e=d+1. Hence, hd,e=D-2rs+∑i=1-MK-1ΔLhopd+i.


### 4.3. The Third Type of the Uncovered Hole

The third type of uncovered hole is shown as in Figure5. Node Sl is the leftmost node of the network, and node Sr is the rightmost node of the network. Node Sl+i’s beacon node is Sl+i-1, and Sl+P is equipped with a GPS receiver. Similarly, node Sr-j’s beacon node is Sr-j-1, and Sr-Q is equipped with a GPS receiver. P is defined as the hops from node Sl to its nearest GPS node. Q is defined as the hops from node Sr to its nearest GPS node. When P=0 or Q=0, GPS receivers are equipped on Sl or Sr, respectively.Figure 5
The uncovered hole between the leftmost (rightmost) node and the left (right) endpoint ofL: (a) uncovered holes do not exist; (b) uncovered holes exist.
(a)
(b)Theorem 4.
The length of the uncovered hole between the leftmost nodeSl and the left endpoint of L is(18)htp3l=max⁡0,D2-rs+∑i=1PΔLhopl+i-1.And the length of the uncovered hole between the rightmost node Sr and the right endpoint of L is(19)htp3r=max⁡0,D2-rs+∑j=1QΔLhopr-j+1.Proof.
For the uncovered hole between the leftmost node and the left endpoint ofL, since the leftmost node is set to be deployed at D/2, we get(20)x^l=D2.Then, we get(21)x^l=x^l+P-L^l+P-1,l+P-⋯-L^l,l+1.Since node Sl+P is equipped with a GPS receiver, we can get x^l+P=xl+P. Combining with (4) and (21), we get(22)x^l=xl+P-Ll+P-1,l+P+⋯+Ll+1,l-∑i=1PΔLhopl+i-1=xl-∑i=1PΔLhopl+i-1.
As shown in Figure5(a), when xl<rs, there is no uncovered hole. However, as shown in Figure 5(b), when xl>rs, we have(23)hl=xl-rs.Combing with (20), (22), and (23), the length of the uncovered hole between the leftmost node and the left endpoint of L is hl=D/2-rs+∑i=1PΔLhopl+i-1.
Similarly, we can provehr=max(0,D/2-rs+∑j=1QΔLhopr-j+1).We have introduced the three types of uncovered holes. From Theorems2, 3, and 4, we find the following:(i)
The uncovered holes are decided by the neighboring nodes’ intervalD, the sensing range rs, and the location errors. When we have smaller D or larger rs, the uncovered hole is smaller. However, a smaller D value means deploying more sensor nodes, and a larger rs 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ΔLhop 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.


## 4.1. The First Type of the Uncovered Hole

The first type of uncovered hole is shown as in Figure3. There are two neighboring nodes, nodes Sp and Sq, in the network. Node Sp is the beacon node of Sq. Due to the location error, an uncovered hole may exist between the locations of them. We get the following.Figure 3
NodeSp is the beacon of node Sq: (a) nodes overlap with each other and no uncovered hole exists; (b) nodes do not overlap with each other and an uncovered hole exists.
(a)
(b)Theorem 2.
For two neighboring nodes, nodesSp and Sq in the network, when node Sp is the beacon node of node Sq, the length of the uncovered hole between them is(7)htp1=max⁡0,D-2rs-ΔLhopq.Proof.
The interval between nodesSp and Sq is set to D; we get(8)x^q-x^p=D=Lp,q^.Combining with (4) and (8), we get(9)Lp,q=Lp,q^-ΔLhopq=D-ΔLhopq.As shown in Figure 3(a), when 2rs-Lp,q>0, nodes Sp and Sq overlap with each other. Thus, there is no uncovered hole between these two locations; that is, hp,q=0. However, as shown in Figure 3(b), when 2rs-Lp,q<0, nodes Sp and Sq do not overlap with each other. There is an uncovered hole between them, and its corresponding length is(10)hp,q=Lp,q-2rs.Combining with (9) and (10), we get hp,q=D-2rs-ΔLhopq.


## 4.2. The Second Type of the Uncovered Hole

The second type of uncovered hole is shown as in Figure4. There are two neighboring nodes, nodes Sd and Se, in the network. Node Sd-i’s beacon node is node Sd-i-1, and node Sd-M is equipped with a GPS receiver. Similarly, node Se+i’s beacon node is Se+i+1, and node Se+K is equipped with a GPS receiver. M is defined as the hops from node Sd to its nearest GPS node. K is defined as the hops from node Se to its nearest GPS node. When M=0 or K=0, there is a GPS receiver equipped on Sd or Se, respectively. We get the following.Figure 4
S
d and Se are not located based on the other: (a) no uncovered hole exists; (b) an uncovered hole exists.
(a)
(b)Theorem 3.
For two neighboring nodes, nodesSd and Se in the network, where the two nodes are not located based on one another,(11)htp2=max⁡0,D-2rs+∑i=1-MK-1ΔLhopd+i.Proof.
Since the interval between nodesSd and Se is set to D, we get(12)x^e-x^d=D.Obviously, we get(13)x^d=x^d-M+L^d-M,d-M+1+⋯+L^d-1,d. Combining with (4), we get(14)x^d=x^d-M+Ld-M,d-M+1+⋯+Ld-1,d+∑i=1MΔLhopd-i+1. Since Sd-M is equipped with GPS receiver, we have x^d-M=xd-M. Hence, we get(15)x^d=xd-M+Ld-M,d-M+1+⋯+Ld-1,d+∑i=1MΔLhopd-i+1=xd+∑i=1MΔLhopd-i+1.
Similarly, forSe, we get(16)x^e=xe-∑j=1KΔLhope+j-1.
As shown in Figure4(a), when xe-xd-2rs<0, that is, nodes Sd and Se overlap with each other, there is no uncovered hole between these two locations. However, as shown in Figure 4(b), when xe-xd-2rs>0, that is, they have no overlapping area, there is an uncovered hole between them and its length is(17)hd,e=xe-xd-2rs.Combining with (12), (15), (16), and (17), we get hd,e=D-2rs+∑i=1MΔLhopd-i+1+∑j=1KΔLhope+j-1. Since nodes Sd and Se are neighboring nodes, we get e=d+1. Hence, hd,e=D-2rs+∑i=1-MK-1ΔLhopd+i.


## 4.3. The Third Type of the Uncovered Hole

The third type of uncovered hole is shown as in Figure5. Node Sl is the leftmost node of the network, and node Sr is the rightmost node of the network. Node Sl+i’s beacon node is Sl+i-1, and Sl+P is equipped with a GPS receiver. Similarly, node Sr-j’s beacon node is Sr-j-1, and Sr-Q is equipped with a GPS receiver. P is defined as the hops from node Sl to its nearest GPS node. Q is defined as the hops from node Sr to its nearest GPS node. When P=0 or Q=0, GPS receivers are equipped on Sl or Sr, respectively.Figure 5
The uncovered hole between the leftmost (rightmost) node and the left (right) endpoint ofL: (a) uncovered holes do not exist; (b) uncovered holes exist.
(a)
(b)Theorem 4.
The length of the uncovered hole between the leftmost nodeSl and the left endpoint of L is(18)htp3l=max⁡0,D2-rs+∑i=1PΔLhopl+i-1.And the length of the uncovered hole between the rightmost node Sr and the right endpoint of L is(19)htp3r=max⁡0,D2-rs+∑j=1QΔLhopr-j+1.Proof.
For the uncovered hole between the leftmost node and the left endpoint ofL, since the leftmost node is set to be deployed at D/2, we get(20)x^l=D2.Then, we get(21)x^l=x^l+P-L^l+P-1,l+P-⋯-L^l,l+1.Since node Sl+P is equipped with a GPS receiver, we can get x^l+P=xl+P. Combining with (4) and (21), we get(22)x^l=xl+P-Ll+P-1,l+P+⋯+Ll+1,l-∑i=1PΔLhopl+i-1=xl-∑i=1PΔLhopl+i-1.
As shown in Figure5(a), when xl<rs, there is no uncovered hole. However, as shown in Figure 5(b), when xl>rs, we have(23)hl=xl-rs.Combing with (20), (22), and (23), the length of the uncovered hole between the leftmost node and the left endpoint of L is hl=D/2-rs+∑i=1PΔLhopl+i-1.
Similarly, we can provehr=max(0,D/2-rs+∑j=1QΔLhopr-j+1).We have introduced the three types of uncovered holes. From Theorems2, 3, and 4, we find the following:(i)
The uncovered holes are decided by the neighboring nodes’ intervalD, the sensing range rs, and the location errors. When we have smaller D or larger rs, the uncovered hole is smaller. However, a smaller D value means deploying more sensor nodes, and a larger rs 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ΔLhop 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ΔLhop denote the one-hop location error in the network. The probability density function of ΔLhop is denoted by fhop(t). Considering Theorems 2, 3, and 4, ΔLhopq represent the (cumulative) location error part in (7), ∑i=1-MK-1ΔLhopd+i in (11), ∑i=1PΔLhopl+i-1 in (18), and ∑j=1QΔLhopr-j+1 in (19), respectively. For the cumulative location errors, we get the following.We defineΔLtp1=ΔLhopq, and its probability density function is denoted by ftp1(t). We get(24)ftp1t=fhopqt.Let ΔLtp2=∑i=1-MK-1ΔLhopd+i, and its probability density function is denoted by ftp2(t). We have(25)ftp2t=fhopd-M+1t⊗fhopd-M+2t⋯⊗fhopd+K-1t.Let ΔLtp3l=∑i=1PΔLhopl+i-1, and its probability density function is denoted by ftp3l(t). Let ΔLtp3r=∑j=1QΔLhopr-j+1, and its probability density function is denoted by ftp3r(t). We have(26)ftp3lt=fhoplt⊗fhopl+1t⋯⊗fhopl+Pt,ftp3rt=fhoprt⊗fhopr-1t⋯⊗fhopr-Qt.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,ftp1(t), ftp2(t), ftp3l(t), and ftp3r(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.Letf(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:(27)Fs=Lft=∫0∞e-stftdt,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 usingInverse Laplace Transform as follows:(28)ft=L-1Fs=1j2π∫σ-j∞σ+j∞estFsds.By using Laplace Transform and converting distributions to the frequency domain, we calculate the cumulative location errors for different types of uncovered holes as(29)Ftp1s=Lftp1t=Fhopqs;(30)Ftp2s=Lftp2t=∏i=1-MK-1Fhopd+is;(31)Ftp3ls=Lftp3lt=∏i=1PFhopl+i-1s;(32)Ftp3rs=Lftp3rt=∏i=1QFhopr-j+1s.LetF(s) denote the cumulative location error in frequency domain. We give unit step function as ut=1, if t≥0; 0, if t<0. Step response means the response (output) to a unit step-function input. In control theory,the step response ofF(s)equals the probability distribution function of the cumulative location error in time domain. We give the explanations here.Letyu(t) denote the time response for u(t). We can get(33)Lyut=Lut·Fs=1s·Fs.The step response can be obtained by Inverse Laplace Transform as(34)yut=L-11s·Fs=∫0tfτdτ=Ft, 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 ishtp1=max(0,D-2rs-ΔLhopq)=max(0,D-2rs-ΔLtp1). Thus, when there is no uncovered hole, it satisfies ΔLtp1≥D-2rs. The probability distribution function (i.e., step response) of ΔLtp1 is Ftp1(t). We have(35)ptp1=1-Ftp1t≥D-2rs,which means the probability of the first type of uncovered hole is ptp1.Similarly, the probability of the second type of uncovered hole existing is(36)ptp2=1-Ftp2t≤2rs-D.The probability of the third type of uncovered hole existing at the left endpoint of L is(37)ptp3l=1-Ftp3lt≤rs-D2,and the probability of the third type of uncovered hole existing at the right endpoint of L is(38)ptp3r=1-Ftp3rt≤rs-D2.We have developed the theoretical framework to model and analyze the uncovered holes. The procedures are shown in Algorithm5.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 Table1.Table 1
System constants and simulation parameters.
The length of the region of interestL (m)
2000
The sensing rangers (m)
50, 60, and 70
The number of nodes deployed originallyN
21
The number of nodes addedN∗
5, 10, and 15
The number of GPS receivers equipped originally
1
The number of GPS receivers added
1, 2, and 3The length of the region of interestL is 2000 m and the sensing range rs 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=95m. 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 Figure6(a), due to high cost, only node S1 is equipped with a GPS receiver. The locations of other nodes are obtained by using localization algorithms. Node Si is Si+1’s beacon node. The results provided by the location algorithms contain location errors. The probability density function fhopi(t) of any one-hop location error is(39)fhopit=2e-2t,t≥0,0,t<0, which follows an exponential distribution.Figure 6
The example systems: (a) we deploy 21 nodes, and only nodeS1 is equipped with a GPS receiver; (b) we add some nodes into the network; (c) more nodes are equipped with a GPS receiver.
(a)
(b)
(c)To use the proposed framework, we first use Laplace Transform to covertfhopi(t) into the frequency domain. We get(40)Fhopis=Lfhopit=2s+2.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 ofL) on the barrier. By (29) and (32), we have(41)Ftp1s=2s+2;Ftp3rs=2s+220.The step response ofFtp1(s) is shown in Figure 7(a). By using (35), the probability of any first type of uncovered hole existing is ptp1=1-Ftp1(t≥-5)=0. The step response of Ftp3r(s) is shown in Figure 7(b). By using (38), the probability of an uncovered hole existing at the right endpoint of L is ptp3r=1-Ftp3r(t≤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 ofFtp1(s); (b) step response of Ftp3r(s).
(a)
(b)We have obtained the probability of an uncovered hole existing at the right endpoint which is1. 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 ofFtp1(s) and Ftp3r(s) are the same as in Figure 7.Using (35) and (38), we find the following: (a) when rs is enlarged to 60m, the probability of the first type of hole existing is ptp1=1-Ftp1(t≥-25)=0, and the probability of the third type of hole existing is ptp3r=1-Ftp3r(t≤12.5)=0.13; (b) when rs is enlarged to 70m, we have ptp1=1-Ftp1(t≥-45)=0 and ptp3r=1-Ftp3r(t≤22.5)=0.Thus, when the sensing range is enlarged to70m, 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 Figure6(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 addN∗ nodes into the system. By (32), we calculate the cumulative location error as(42)Ftp3r∗s=2s+220+N∗.The step response Ftp3r∗(s) is shown in Figure 8.Figure 8
The step response ofFtp3r∗(s).WhenN∗=5, by (42), we calculate the cumulative location error as Ftp3r∗(s)=(2/s+2)25. The probability of an uncovered hole existing at the right endpoint of L becomes ptp3r∗=1-Ftp3r∗(t≤11.5)=0.63.WhenN∗=10, we have Ftp3r∗(s)=(2/s+2)30. The probability of an uncovered hole existing at the right endpoint of L becomes ptp3r∗=1-Ftp3r∗(t≤17.8)=0.15.WhenN∗=15, we have Ftp3r∗(s)=(2/s+2)35. The probability of an uncovered hole existing at the right endpoint of L becomes ptp3r∗=1-Ftp3r∗(t≤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 Figure6(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: Ftp2+(s) and Ftp3r+(s). The step responses of them are shown in Figure 9.Figure 9
The step responses: (a) step response ofFtp2+(s); (b) step response of Ftp3r+(s).
(a)
(b)When we equip one more GPS receiver (onS11), we have Ftp2+(s)=(2/s+2)9 and Ftp3r+(s)=(2/s+2)10. By using (36), the probability of a second type of uncovered hole existing is ptp2+=1-Ftp2+(t≤5)=0.33. The probability of an uncovered hole existing at the right endpoint of L becomes ptp3r+=1-Ftp3r+(t≤2.5)=0.97.When we equip two more GPS receivers (onS8 and S15), we have Ftp2+(s)=(2/s+2)6 and Ftp3r+(s)=(2/s+2)6. By using (36), the probability of a second type of uncovered hole existing is ptp2+=1-Ftp2+(t≤5)=0.06. The probability of an uncovered hole existing at the right endpoint of L becomes ptp3r+=1-Ftp3r+(t≤2.5)=0.62.When we equip three more GPS receivers (onS6, S11 and S16), we have Ftp2+(s)=(2/s+2)4 and Ftp3r+(s)=(2/s+2)5. By using (36), the probability of a second type of uncovered hole existing is ptp2+=1-Ftp2+(t≤5)=0.01. The probability of an uncovered hole existing at the right endpoint of L becomes ptp3r+=1-Ftp3r+(t≤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.


## 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 ofFtp1(s) and Ftp3r(s) are the same as in Figure 7.Using (35) and (38), we find the following: (a) when rs is enlarged to 60m, the probability of the first type of hole existing is ptp1=1-Ftp1(t≥-25)=0, and the probability of the third type of hole existing is ptp3r=1-Ftp3r(t≤12.5)=0.13; (b) when rs is enlarged to 70m, we have ptp1=1-Ftp1(t≥-45)=0 and ptp3r=1-Ftp3r(t≤22.5)=0.Thus, when the sensing range is enlarged to70m, 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 Figure6(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 addN∗ nodes into the system. By (32), we calculate the cumulative location error as(42)Ftp3r∗s=2s+220+N∗.The step response Ftp3r∗(s) is shown in Figure 8.Figure 8
The step response ofFtp3r∗(s).WhenN∗=5, by (42), we calculate the cumulative location error as Ftp3r∗(s)=(2/s+2)25. The probability of an uncovered hole existing at the right endpoint of L becomes ptp3r∗=1-Ftp3r∗(t≤11.5)=0.63.WhenN∗=10, we have Ftp3r∗(s)=(2/s+2)30. The probability of an uncovered hole existing at the right endpoint of L becomes ptp3r∗=1-Ftp3r∗(t≤17.8)=0.15.WhenN∗=15, we have Ftp3r∗(s)=(2/s+2)35. The probability of an uncovered hole existing at the right endpoint of L becomes ptp3r∗=1-Ftp3r∗(t≤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 Figure6(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: Ftp2+(s) and Ftp3r+(s). The step responses of them are shown in Figure 9.Figure 9
The step responses: (a) step response ofFtp2+(s); (b) step response of Ftp3r+(s).
(a)
(b)When we equip one more GPS receiver (onS11), we have Ftp2+(s)=(2/s+2)9 and Ftp3r+(s)=(2/s+2)10. By using (36), the probability of a second type of uncovered hole existing is ptp2+=1-Ftp2+(t≤5)=0.33. The probability of an uncovered hole existing at the right endpoint of L becomes ptp3r+=1-Ftp3r+(t≤2.5)=0.97.When we equip two more GPS receivers (onS8 and S15), we have Ftp2+(s)=(2/s+2)6 and Ftp3r+(s)=(2/s+2)6. By using (36), the probability of a second type of uncovered hole existing is ptp2+=1-Ftp2+(t≤5)=0.06. The probability of an uncovered hole existing at the right endpoint of L becomes ptp3r+=1-Ftp3r+(t≤2.5)=0.62.When we equip three more GPS receivers (onS6, S11 and S16), we have Ftp2+(s)=(2/s+2)4 and Ftp3r+(s)=(2/s+2)5. By using (36), the probability of a second type of uncovered hole existing is ptp2+=1-Ftp2+(t≤5)=0.01. The probability of an uncovered hole existing at the right endpoint of L becomes ptp3r+=1-Ftp3r+(t≤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.



---

*Source: 930585-2015-10-04.xml*