# Critical Density for Exposure-Path Prevention in Three-Dimensional Wireless Sensor Networks Using Percolation Theory

Authors: Guixia Kang; Xiaoshuang Liu; Ningbo Zhang; Yanyan Guo; Fabrice Labeau
Journal: International Journal of Distributed Sensor Networks
 (2015)

---

## Abstract

To derive the critical density for exposure-path prevention in three-dimensional wireless sensor networks (3D WSNs), a bond-percolation-based scheme is proposed, which can generate the tighter lower and upper bounds of critical density. Firstly, the exposure-path prevention problem and system models based on Gaussian distribution are introduced in this paper. Then, according to percolation theory, we present a bond-percolation model to put this problem into a 3D uniform lattice. With this model, the lower and upper bounds of critical density for 3D WSNs are derived in the light of our scheme. Extensive simulations and contrast experiments also validate our developed models and evaluate the performance of the proposed schemes. Therefore, our scheme can be applied to determine a practically reliable density and detect intruders in sensor networks.


---

## Body

## 1. Introduction

Over the past decades, wireless sensor networks (WSNs) have represented one of the most outstanding technologies, and several research disciplines, such as communication protocols, and hardware platforms, have appeared to cover the special requirements of these systems. Many applications of WSNs need the intrusions being detected by sensor nodes in the interested region [1], like military applications, healthy environment monitoring, seism surveillance, and so on. The intrusion detection problem belongs to node coverage issue that is vital in the area of WSNs. Moreover, if nodes detect intrusion paths, the intrusions can be detected. Namely, coverage of intrusion paths has important influence in detecting intrusions.Generally, coverage reflects QoS (quality of service) provided by sensor nodes of networks [2]. It creates collaborations among the nodes in covering an interested region for monitoring specific information. The researchers have studied the coverage problem from many different perspectives based on different requirements [3, 4]. As shown in the majority of references [2–4], if each point in the region is sensed by at least one sensor node, this region is defined as covered region. However, if the objective of coverage is to detect moving targets or phenomena, the traditional full coverage model [2–4] may be unnecessary. Full coverage means that everywhere in the deployment area is covered by nodes, which is at the cost of resource wastes and high complexity [5]. But coverage for intrusion detection only needs partial coverage ensuring that no moving targets or phenomena can pass through the interested region without being detected [6]. If an intruder can traverse through the deployment area and the resulting path is not covered by nodes, we name the traversed path as the exposure path. It reflects the ability of intrusions moving through the deployed area [7]. Preventing the exposure paths belongs to the exposure-path prevention problem. On account of the full coverage, network coverage is rather poor if there exists an exposure path in WSNs [8]. Hence, this paper considers the problem of no exposure path in 3D WSNs.To address the exposure-path problem, this paper adopts percolation theory [9–11] to compute the optimal density in order to make the probability of an exposure path existing converge to 0 and satisfy the minimum density of sensor nodes. In [12], Broadbent and Hammersley first introduced percolation theory to model the disordered media and simulate the percolation process of immersed rocks. Since this theory reveals the vital relationships between probabilistic and topological characteristics of graphs, it is attractive to researchers [13] and has been used to study connectivity of WSNs [14–16]. In this paper, we exploit the percolation theory to obtain the optimal density for coverage inomnidirectional sensor networks.On the basis of percolation theory [10, 13], if p is the average degree of connectivity between various subunits of some arbitrary system, there exists a percolation threshold, denoted by pt. When p≥pt, there is no exposure path from one side to the other side of this system, and not vice versa. Deriving the critical density to achieve regional coverage for random network deployment process is a fundamentally important problem in the area of WSNs. Based on percolation theory, most existing studies [14–16] apply the continuum-percolation theory to derive the optimal density for coverage. However, the studies suffer from the loose lower and upper bounds of critical density and cannot be applied to determine a practically useful density for network deployment. In this paper, a bond-percolation scheme is proposed in 3D WSNs to conquer the above problem and make percolation theory more suitable for the exposure-path problem. We assume sensor nodes deployed under a 3D Gaussian process, and the rigorous derivation analyses and simulation results indicate that the proposed method can generate much tighter upper and lower bounds of critical density.The remainder of our paper is structured as follows. Section2 introduces the related works, and based on Gaussian distribution, Section 3 presents the system models and problem formulation about exposure-path prevention in 3D WSNs. Section 4 describes the bond-percolation theory to derive and analyze the optimal critical density for exposure-path problem. In addition, the mutual dependence among edges of the proposed scheme is dealt with in this section. In Section 5, extensive simulation results evaluate the models and schemes we proposed, and the last section concludes this paper.


## 2. Related Works

In this section, we introduce the related works of percolation theory and exposure-path problem in WSNs. Due to coverage of exposure paths belonging to barrier coverage, this section also presents recent results about barrier coverage.The coverage of WSNs can be classified into three types: area coverage, barrier coverage, and point coverage in terms of the different covered objects [17]. Area coverage is full coverage, while barrier coverage and point coverage are partial coverage. Area coverage needs every point within the target area covered by at least one node [18]; barrier coverage measures the detection ability [19]; point coverage requires the coverage of several discrete targets [20]. In this paper, barrier coverage contains the mentioned exposure-path problem. Next, we introduce the related researches on exposure-path problem.In [21], the authors provided formal yet intuitive formulations, established the complexity of the exposure-path problem and developed practical algorithms for exposure calculation. They also investigated the relationship and interplay of exposure problem with other fundamental wireless sensor network tasks and in particular with location discovery and deployment. After elucidating the importance of the exposure problem, Megerian et al. [22] formally defined exposure paths and studied exposure-path properties. Meanwhile, they developed an efficient-effective algorithm for exposure calculations in sensor networks, specifically for finding minimum exposure paths. Veltri et al. [23] proposed an efficient localized algorithm enabling a sensor network to determine its minimum exposure path. Theoretical highlight of this reference is the closed-form solution for minimum exposure in the presence of a single sensor node. Moreover, they introduced a new coverage problem, the maximum exposure path, which was proved NP-hard and could be resolved by heuristics to generate approximate solutions. The concept of information exposure was came up in [24], and an approximation algorithm was presented to solve the problem of finding the worst (best) information exposure path in WSNs. In [25, 26], an approximation algorithm was suggested by Djidjev to solve the minimum exposure-path problem and guaranteed the network performance. Ferrari and Foderaro [27] introduced an artificial-potential approach that designed the minimum exposure paths of multiple mobile objects (including sensor nodes) in dynamic networks. In addition, this approach can be used in heterogeneous wireless sensor networks (HWSNs). The authors of [28] exploited a new optimization algorithm, the physarum optimization, for solving the shortest path problem. This algorithm is with low complexity and high parallelism. Liu et al. [29] applied the percolation theory to solve the exposure-path problem with a two-dimensional (2D) Poisson process in Internet of Things (IoT).Using percolation theory to find the critical density of networks could date back to 1961. Gilbert [30] firstly raised the concept of continuum percolation to find the critical density of a Poisson point process. This model is the foundation of wireless networks with continuum percolation. Percolation threshold is also applied to investigate the connectivity of wireless networks. In [31], Penrose indicated that the critical range for the probability of establishing overall connectivity is close to 1, as the number of nodes goes to infinity. This range results in every node connecting to its neighbors on average. Gupta and Kumar of [32] adopted the correlation percolation results to derive the sufficient condition on communication distance for asymptotic connectivity in wireless networks. However, the loose lower and upper bounds on the critical density impose restrictions on the applications of continuum-percolation theory.Bertin et al. [33] put forward the existence of site and bond percolation for both Poisson and hard-core stationary point processes in the Gabriel graph. Besides, the simulation results demonstrated the critical bounds corresponding to the existence of two paths—open sites and open bounds, respectively. In [34], the authors determined the critical densities of a Poisson point process in different classes of coverage algorithms. Furthermore, based on the ratio of the connectivity range of base stations to the clients, they showed the almost sure existence of an unbounded connected component. Glauche et al. [35] raised a distributed protocol to guarantee strong connectivity and find the critical communication range of mobile devices in ad hoc networks. An ad hoc network graph could be surely connected above this range. For efficient topology control of wireless networks, Liu and Towsley [36] recommended the concept of monotone percolation based on the local adjustment of communication radii of sensor nodes. Simultaneously, they illuminated some algorithms to guarantee the existence of relatively short paths between any pairs of source and destination nodes. The authors considered both Boolean and probabilistic sensing models to characterize fundamental coverage properties of large-scale sensor networks in [37]. Due to the dependency between coverage and connectivity, Ammari and Das [38] proposed an integrated concentric-sphere model to address coverage and connectivity of 3D WSNs in an integrated way. In [39], through some assumptions and simplifications, Deng et al. gave a simple formula to estimate the minimum number of sensor nodes that the system needed to ensure opportunistic encounter between nodes and made the data forwarded. Khanjary et al. [40] proposed an approach to calculate the density of nodes at critical percolation by using continuum percolation in aligned-orientation directional sensor networks.However, from the above pieces of literature, we can conclude that most existing percolation-based schemes [34–40] apply the common continuum-percolation theory, enduring the loose lower and upper bounds on the critical density. The tight asymptotic expressions for individual and system outage probabilities are presented in closed form through investigating the performance of time division broadcast (TDBC) protocol in bidirectional cloud networks in the presence of channel estimation errors (CEEs) [41, 42]. To obtain the tighter lower and upper bounds of critical density and make percolation theory more apt to 3D WSNs, we propose a bond-percolation-based scheme that maps the exposure-path prevention problem into a bond-percolation model in a 3D WSN. Depending on the deployment of sensor nodes obeying a 3D Gaussian process, the lower and upper bounds of critical density for 3D omnidirectional WSNs are derived.


## 3. System Models

Firstly, this section introduces the deployment and sensing models of 3D omnidirectional sensor networks. Then, we adopt the continuum-percolation theory [43] to formulate exposure-path prevention problem. Meanwhile, a bond-percolation scheme is proposed to map the proposed problem into a bond-percolation model.


### 3.1. System Models

#### 3.1.1. Deployment Model

In a vast 3D WSN, sensor nodes are deployed randomly and their locations are uniformly and independently distributed, modeled as a stationary 3D Gaussian distribution [44] with a random variable X and X~N(μ,σ2). μ is the mathematical expectation, that is, the average value. σ represents the standard deviation, and σ2 denotes the covariance. Then, from [45], we have the probability density function of X; namely, (1)pX=12πσ23exp⁡-X-μ22σ2.In any subregionV, the number of sensor nodes N(V)=k follows the Gaussian distribution with mean value μ=λV, where V is the volume of V. We assume that σ is the standard deviation and σ2 is the covariance. Therefore, the probability intensity function of N(V′)is(2)pNV=k=12πσ23exp⁡-k-λV22σ2.


#### 3.1.2. Sensing Model

In this paper, we adopt the sphere model(Β,r,λ) [16] as the sensing model in a 3D omnidirectional sensor network, as shown in Figure 1. Β denotes the node sensing range, a spherical region, and its sensing radius is r. λ is the deployment density of sensor nodes in the 3D WSN. If s: (xs,ys,zs) denote the location of one sensor node, a target point t: (xt,yt,zt) is covered when the Euclidean distance st satisfies [38] (3)st=xs-xt2+ys-yt2+zs-zt2≤r.Figure 1
Omnidirectional sensing model.This paper just considers the omnidirectional sensing model other than the directional sensing model [40]. The directional sensing model in 3D WSNs is the circular cone with one offset angle. Future works of our research focus on the study of the directional sensor network that is more commonly in practice.


### 3.2. Problem Formulation

In a 3D WSNR3, the deployment space is divided into two parts, the vacant region W covered by no sensor node and the covered region C covered by at least one sensor node. The exposure path in a 3D network is defined in the following.Definition 1 (exposure path).
A continuous stripS (or curve S) from one side to the other side of the deployment region is said to be an exposure path if it belongs to any vacant region W; see Figure 2(a).Figure 2
Relationship between exposure pathS and sensor node density λC.
(a)
(b)Sensor nodes may be spread in an arbitrary pattern, such as certain sensor deployment strategies, airdropped or launched via artillery in battlefields or unfriendly environments. As shown in Figure2(a), there exists an exposure path in the 3D network if λ is not larger than the critical threshold λC, whereas, in Figure 2(b), if λ>λC, no exposure path exists in this network. Additionally, the exorbitant density will cause vast redundancy, high implementation complexity and cost. In conclusion, λ of no exposure paths and no redundancy existing in the network is the optimal density.As a result, we formulate the exposure-path prevention problem as the calculation of the critical densityλC in a 3D network. In [46], if the lower and upper bounds of λC are very loose, they cannot be applied to determine a practically useful density for nodes deploying process. Concurrently, we summarize from [43] that the bounds on λC are very loose, and this scheme of [43] is suitable only for the Poisson model. To get the tighter bounds of λC and make the appropriate model in this paper, a bond-percolation model is proposed for the 3D sensor networks based on the bond-percolation theory. We will introduce it in Section 3.3. According to the Limit theory, strip S can be seen as the countless lines superposition. Then, we just consider the condition of lines for simplicity.


### 3.3. Bond-Percolation Model

In this section, to resolve the exposure-path prevention problem, the 3D sensor network is partitioned into a 3D uniform lattice, as shown in Figure3. Then, we define the number of lattices in the regions C and W as the sizes of C and W, d(C,λ) and d(W,λ), respectively. To formulate this problem, the critical densities [13] are defined as λC=inf⁡{λ:p(d(C,λ)=∞)>0}. From the above discussion, it is clear that if λ≤λC, there exists an exposure path in the network.Figure 3
The unit cube region with a virtual lattice.For simplicity, in Figure3, let one unit cube region contain n vertexes, M={m1,m2,…,mn}, and form a n3×n3×n3 lattice. n vertexes do not contain the ones that lie on the edges of this cube. ei,j, i,j∈[1,n] denotes the edge between vertex mi and vertex mj. Therefore, the length of edge ei,j between neighbor vertexes is κ=1/n3. We give the following definitions to identify the relationship between edge ei,j and the bounds of λC.Definition 2 (closed/open edge).
For edgeei,j, we define two different indicator functions as follows: (4)Lei,j=1,if  at  least  one  point  onei,jis  covered;0,if  all  points  onei,jare  not  covered,(5)Uei,j=1,if  all  points  onei,jare  covered;0,if  at  least  one  point  onei,jis  not  covered.
Then,(1) if L(ei,j)=1, ei,j is defined as L-closed edge; if L(ei,j)=0, ei,j is called L-open edge; (2)  ei,j is named as U-closed edge if U(ei,j)=1; ei,j is denoted as U-open edge if U(ei,j)=0.Definition 3 (coverage lattice).
In a 3D latticeZ3 with its vertex set M (M=n) and edge set E, if an arbitrary edge ei,j between two neighbor vertexes is L-open/L-closed edge, Z3 is an L-coverage lattice; if ei,j is U-open/U-closed edge, Z3 is a U-coverage lattice.Definition 4 (closed/open path).
In a 3D latticeZ3 with its vertex set M (M=n) and edge set E, a path S passes via a sequence of edges e1,2,e2,3,…,ei,i+1,…, i≥1. If all the edges (ei,i+1, i≥1) of path S are L-open/U-open, S is named as the L-open/U-open path; if all the edges are L-closed/U-closed, S is called the L-closed/U-closed path.According to Definitions2–4, it is simple to conclude that (a) if edge ei,j is the U-closed edge, it must be the L-closed edge in terms of coverage, and not vice versa; (b) the lower bound λL of the critical density λC could be derived by L-coverage lattice and the upper bound λU by U-coverage lattice for 3D sensor networks.


## 3.1. System Models

### 3.1.1. Deployment Model

In a vast 3D WSN, sensor nodes are deployed randomly and their locations are uniformly and independently distributed, modeled as a stationary 3D Gaussian distribution [44] with a random variable X and X~N(μ,σ2). μ is the mathematical expectation, that is, the average value. σ represents the standard deviation, and σ2 denotes the covariance. Then, from [45], we have the probability density function of X; namely, (1)pX=12πσ23exp⁡-X-μ22σ2.In any subregionV, the number of sensor nodes N(V)=k follows the Gaussian distribution with mean value μ=λV, where V is the volume of V. We assume that σ is the standard deviation and σ2 is the covariance. Therefore, the probability intensity function of N(V′)is(2)pNV=k=12πσ23exp⁡-k-λV22σ2.


### 3.1.2. Sensing Model

In this paper, we adopt the sphere model(Β,r,λ) [16] as the sensing model in a 3D omnidirectional sensor network, as shown in Figure 1. Β denotes the node sensing range, a spherical region, and its sensing radius is r. λ is the deployment density of sensor nodes in the 3D WSN. If s: (xs,ys,zs) denote the location of one sensor node, a target point t: (xt,yt,zt) is covered when the Euclidean distance st satisfies [38] (3)st=xs-xt2+ys-yt2+zs-zt2≤r.Figure 1
Omnidirectional sensing model.This paper just considers the omnidirectional sensing model other than the directional sensing model [40]. The directional sensing model in 3D WSNs is the circular cone with one offset angle. Future works of our research focus on the study of the directional sensor network that is more commonly in practice.


## 3.1.1. Deployment Model

In a vast 3D WSN, sensor nodes are deployed randomly and their locations are uniformly and independently distributed, modeled as a stationary 3D Gaussian distribution [44] with a random variable X and X~N(μ,σ2). μ is the mathematical expectation, that is, the average value. σ represents the standard deviation, and σ2 denotes the covariance. Then, from [45], we have the probability density function of X; namely, (1)pX=12πσ23exp⁡-X-μ22σ2.In any subregionV, the number of sensor nodes N(V)=k follows the Gaussian distribution with mean value μ=λV, where V is the volume of V. We assume that σ is the standard deviation and σ2 is the covariance. Therefore, the probability intensity function of N(V′)is(2)pNV=k=12πσ23exp⁡-k-λV22σ2.


## 3.1.2. Sensing Model

In this paper, we adopt the sphere model(Β,r,λ) [16] as the sensing model in a 3D omnidirectional sensor network, as shown in Figure 1. Β denotes the node sensing range, a spherical region, and its sensing radius is r. λ is the deployment density of sensor nodes in the 3D WSN. If s: (xs,ys,zs) denote the location of one sensor node, a target point t: (xt,yt,zt) is covered when the Euclidean distance st satisfies [38] (3)st=xs-xt2+ys-yt2+zs-zt2≤r.Figure 1
Omnidirectional sensing model.This paper just considers the omnidirectional sensing model other than the directional sensing model [40]. The directional sensing model in 3D WSNs is the circular cone with one offset angle. Future works of our research focus on the study of the directional sensor network that is more commonly in practice.


## 3.2. Problem Formulation

In a 3D WSNR3, the deployment space is divided into two parts, the vacant region W covered by no sensor node and the covered region C covered by at least one sensor node. The exposure path in a 3D network is defined in the following.Definition 1 (exposure path).
A continuous stripS (or curve S) from one side to the other side of the deployment region is said to be an exposure path if it belongs to any vacant region W; see Figure 2(a).Figure 2
Relationship between exposure pathS and sensor node density λC.
(a)
(b)Sensor nodes may be spread in an arbitrary pattern, such as certain sensor deployment strategies, airdropped or launched via artillery in battlefields or unfriendly environments. As shown in Figure2(a), there exists an exposure path in the 3D network if λ is not larger than the critical threshold λC, whereas, in Figure 2(b), if λ>λC, no exposure path exists in this network. Additionally, the exorbitant density will cause vast redundancy, high implementation complexity and cost. In conclusion, λ of no exposure paths and no redundancy existing in the network is the optimal density.As a result, we formulate the exposure-path prevention problem as the calculation of the critical densityλC in a 3D network. In [46], if the lower and upper bounds of λC are very loose, they cannot be applied to determine a practically useful density for nodes deploying process. Concurrently, we summarize from [43] that the bounds on λC are very loose, and this scheme of [43] is suitable only for the Poisson model. To get the tighter bounds of λC and make the appropriate model in this paper, a bond-percolation model is proposed for the 3D sensor networks based on the bond-percolation theory. We will introduce it in Section 3.3. According to the Limit theory, strip S can be seen as the countless lines superposition. Then, we just consider the condition of lines for simplicity.


## 3.3. Bond-Percolation Model

In this section, to resolve the exposure-path prevention problem, the 3D sensor network is partitioned into a 3D uniform lattice, as shown in Figure3. Then, we define the number of lattices in the regions C and W as the sizes of C and W, d(C,λ) and d(W,λ), respectively. To formulate this problem, the critical densities [13] are defined as λC=inf⁡{λ:p(d(C,λ)=∞)>0}. From the above discussion, it is clear that if λ≤λC, there exists an exposure path in the network.Figure 3
The unit cube region with a virtual lattice.For simplicity, in Figure3, let one unit cube region contain n vertexes, M={m1,m2,…,mn}, and form a n3×n3×n3 lattice. n vertexes do not contain the ones that lie on the edges of this cube. ei,j, i,j∈[1,n] denotes the edge between vertex mi and vertex mj. Therefore, the length of edge ei,j between neighbor vertexes is κ=1/n3. We give the following definitions to identify the relationship between edge ei,j and the bounds of λC.Definition 2 (closed/open edge).
For edgeei,j, we define two different indicator functions as follows: (4)Lei,j=1,if  at  least  one  point  onei,jis  covered;0,if  all  points  onei,jare  not  covered,(5)Uei,j=1,if  all  points  onei,jare  covered;0,if  at  least  one  point  onei,jis  not  covered.
Then,(1) if L(ei,j)=1, ei,j is defined as L-closed edge; if L(ei,j)=0, ei,j is called L-open edge; (2)  ei,j is named as U-closed edge if U(ei,j)=1; ei,j is denoted as U-open edge if U(ei,j)=0.Definition 3 (coverage lattice).
In a 3D latticeZ3 with its vertex set M (M=n) and edge set E, if an arbitrary edge ei,j between two neighbor vertexes is L-open/L-closed edge, Z3 is an L-coverage lattice; if ei,j is U-open/U-closed edge, Z3 is a U-coverage lattice.Definition 4 (closed/open path).
In a 3D latticeZ3 with its vertex set M (M=n) and edge set E, a path S passes via a sequence of edges e1,2,e2,3,…,ei,i+1,…, i≥1. If all the edges (ei,i+1, i≥1) of path S are L-open/U-open, S is named as the L-open/U-open path; if all the edges are L-closed/U-closed, S is called the L-closed/U-closed path.According to Definitions2–4, it is simple to conclude that (a) if edge ei,j is the U-closed edge, it must be the L-closed edge in terms of coverage, and not vice versa; (b) the lower bound λL of the critical density λC could be derived by L-coverage lattice and the upper bound λU by U-coverage lattice for 3D sensor networks.


## 4. Bounds of Critical Density

In this section, since the probabilityp of an arbitrary edge in the 3D lattice is closed, there exists a threshold value pt∈[0,1] resulting in the differences of the global behavior of the system in two regions C and W. Generally speaking, one closed path from one side to the other of the 3D network exists for all p>pt [47]. Conversely, no closed path exists for all p<pt. For the sake of clearness, we define PL=p{L(ei,j)=1}, PU=p{U(ei,j)=1}; and λL=sup⁡{λ:PL≤pt}, λU=inf⁡{λ:PU≥pt}. Thus, p{the exposure path exists}>0 if PL<pt, and p{the exposure path exists}=0 if PU>pt. From [47], we can see that the probabilities of all edges being open or closed are independent in the bond-percolation theory. In Section 4.2, the dependence of PL (PU) on neighbor edges will be discussed in 3D omnidirectional sensor networks in detail.


### 4.1. Critical DensityλC

Firstly, a new operationAi∪Aj=⋃∀sn∈ei,jAn is defined in this section, where sn is an arbitrary point on edge ei,j of the L-coverage lattice, and An is the sphere centered at sn with radius r, as shown in Figure 4(a). In the 3D coordinate system, we adopt edge ei,j on y-axis as an example and draw some conclusions. In this figure, mi and mj are the two endpoints of edge ei,j. Therefore, Ai∪Aj is a set that contains all the coverage spheres centered at the points of edge ei,j. Based on the definition of Ai∪Aj, it is easy to have the following theorem.Figure 4
Covered region division of the edgeei,j.
(a)
(b)Theorem 5.
No sensor node withinAi∪Aj is a sufficient and necessary condition of all points on edge ei,j being not covered by any sensor nodes in the network.Proof.
There are two steps to prove the theorem as follows.(1)
From the concept ofAi∪Aj at the start of this section, we know that Ai∪Aj contains the overall coverage space of all points on ei,j. Consequently, it is obvious that if no sensor nodes exist in Ai∪Aj, all points on ei,j are not covered by any sensor nodes.(2)
On the contrary, if one point on edgeei,j is covered by a sensor node in the network, this sensor node locates within Ai∪Aj on account of the definition of Ai∪Aj. So, obviously, if all points on edge ei,j are not covered by any sensor nodes in the network, there is no sensor node within Ai∪Aj.
To sum up, the proof of Theorem5 is finished.Theorem 6.
In a 3D omnidirectional sensor network, we have(6)-2σ2ln⁡2πσ23/21-pt1/24/3πr3+πr2κ<λC<-2σ2ln⁡2πσ23/21-pt1/22π/32r+κ/2r-κ/22,where κ=1/n3.Proof.
There are three processes to demonstrate this theorem.
(
1
) Based on (2), we have (7)pNAi∪Aj=0=12πσ23exp⁡-λV22σ2=12πσ23exp⁡-λ24/3πr3+πr2κ22σ2,where V is the volume of the 3D omnidirectional sensor network, λ is the deployment density of sensor nodes in this network, and κ=1/n3. σ2 is the covariance of the Gaussian distribution, and r is the sensing radius of sensor nodes.
Then,(8)PL=1-pLei,j=0=1-12πσ23exp⁡-λ24/3πr3+πr2κ22σ2.
Therefore, it is clear thatPL increases monotonously as λ increases. Because λL=sup⁡{λ:PL≤pt}, 1-(1/2πσ23)exp⁡(-λ2(4/3πr3+πr2κ)2/2σ2)=pt. As a result, we can get λL={-2σ2ln⁡[2πσ23/2(1-pt)]}1/2/(4/3πr3+πr2κ) in (6).
(
2
) By the above analysis, we can know that it is difficult to compute the explicit expression of the probability that all points on edge ei,j are covered. Consequently, finding an approximation of PU is necessary in this paper. We assume Po is the probability of all points on ei,j being covered by one sensor node, and PO is the probability of all points on ei,j being covered by one sensor network. According to the definition of PU and PO, we have PU=PO>Po. Namely, (9)PU>Pall  points  onei,jare  covered  by  one  sensor  node.
Clearly, one sensor node covers all points onei,j if and only if some sensor node exists in Ai⋂Aj. From (2),(10)pNAi⋂Aj>0=1-12πσ23exp⁡-λ2Ai⋂Aj22σ2.
Let the volume ofAi⋂Aj be Ai⋂Aj=V′; then in Figure 4(a), we have(11)PU>1-12πσ23×exp⁡-λ2∬R4r2-x′2-y′-κ/22dδ22σ2,where (x′,y′,z′) denotes an arbitrary point within Ai⋂Aj, R:(x′)2+y′2=(r-κ/2)2, and dσ=dx′dy′. It is simple to obtain V′=2π/3(2r+κ/2)(r-κ/2)2.
In conclusion, we choosePo as the approximation of PU in this paper. Let λU=inf⁡{λ:Po≥pt}; then λU={-2σ2ln⁡[(2πσ2)3/2(1-pt)]}1/2/2π/3(2r+κ/2)(r-κ/2)2 can be achieved in (6).
(
3
) Equation (5) can be turned into(12)Uei,j=1,ifei,jis  covered  by  one  sensor  node;0,otherwise.
IfPL<pt, p{d(W)=∞}>0. Let λC′=sup⁡{λ:p{d(W)=∞}>0}; then it is easy to have λL<λC′. From (10), if 1-(1/(2πσ2)3)exp⁡(-(λV′)2/2σ2)>pt, PU>pt. Consequently, p{d(C)=∞}>0. According to the concept of λC, ({-2σ2ln⁡[(2πσ2)3(1-pt)]}1/2/V′)>λC. From (1) and (2), we obtain Theorem 6.


### 4.2. Dependence among Neighbor Edges

On the basis of (6) and Gaussian distribution, the different values of κ and r can generate the different bounds. The probabilities of all edges ei,j being open or closed are independent in the bond-percolation theory [47]. However, PL (PU) of a given edge is dependent on the neighbor edges but independent of most edges in this paper. As a consequence, we can use the bond-percolation model to approximate the coverage percolation in this paper.In this section, we illustrate the quantitative measure of the dependence betweene1,2 and e2,3 as an example.(
1
) Firstly, the mutual information in information theory [48] is employed to measure the mutual dependence between A=L(e1,2) and B=L(e2,3); that is, (13)IA,B=∑a∈0,1∑b∈0,1PABa,blog⁡PABa,bPAaPBb,where PAB(a,b)=p{L(e1,2)=a,L(e2,3)=b}, PA(a)=p{L(e1,2)=a}, and PB(b)=p{L(e2,3)=b}.In 3D omnidirectional sensor networks, we discuss the mutual dependence betweene1,2 and e2,3, shown in Figure 4(b). I(A,B) reveals the relationships among κ, r and the mutual dependence in this section. From (2), we have(14)PA0=PB0=12πσ23exp⁡-λL24/3πr3+πr2κ22σ2,(15)PA1=PB1=1-12πσ23exp⁡-λL24/3πr3+πr2κ22σ2.What is more,(16)PAB0,0=pNA1∪A3=0=12πσ23exp⁡-λL24/3πr3+2πr2κ22σ2,(17)PAB1,0=PAB0,1=PA0-PAB0,0=12πσ23×exp⁡-λL24/3πr3+πr2κ22σ2-exp-λL24/3πr3+2πr2κ22σ2,(18)PAB1,1=1-PAB0,1-PAB1,0-PAB0,0=1+12πσ23×exp⁡-λL24/3πr3+2πr2κ22σ2-2exp⁡-λL24/3πr3+πr2κ22σ2.Putting these above equations (14)–(18) into (13), we can obtain I(L(e1,2),L(e2,3)).(
2
) Similarly, the case of I(U(e1,2),U(e2,3)) can be achieved in this section. We also adopt the mutual information [48] to measure the mutual dependence between C=U(e1,2) and D=U(e2,3); namely, (19)IC,D=∑c∈0,1∑d∈0,1PCDc,dlog⁡⁡PCDc,dPCcPDd,where PCD(c,d)=p{U(e1,2)=c,U(e2,3)=d}, PC(c)=p{U(e1,2)=c}, and PD(d)=p{U(e2,3)=d}.In Figure4(b), we use I(C,D) to indicate the relationships among the mutual dependence, κ, and r. Based on formula (2), we have (20)PC0=PD0=1-12πσ23×exp⁡-λU22π/32r+κ/2r-κ/2222σ2,(21)PC1=PD1=12πσ23×exp⁡-λU22π/32r+κ/2r-κ/2222σ2.Moreover, (22)PCD1,1=pNA1∩A3=0=12πσ23×exp⁡-λU22π/32r+κr-κ222σ2,(23)PCD1,0=PCD0,1=PC1-PCD1,1=12πσ23×exp⁡-λU22π/32r+κ/2r-κ/2222σ2-exp-λU22π/32r+κr-κ222σ2,(24)PCD0,0=1-PCD0,1-PCD1,0-PCD1,1=1+12πσ23exp⁡-λU22π/32r+κr-κ222σ2-212πσ23×exp⁡-λU22π/32r+κ/2r-κ/2222σ2.Putting the formulas (20)–(24) into formula (19), I(U(e1,2),U(e2,3)) can be obtained.(
3
) Finally, when r=4, κ=1 or 2, the curves of I(L(e1,2),L(e2,3)) and I(U(e1,2),U(e2,3)) are depicted in Figure 5. As λ increases, the mutual dependence between neighbor edges decreases and it gets more close to 0. When λ>0.03, I(L(e1,2),L(e2,3)) and I(U(e1,2),U(e2,3)) are equal to 0 in this figure. I(A,B)=0 and I(C,D)=0 mean that the two edges are independent of each other [48]. From the observation of this figure, it is tempting to infer that the dependence between neighbor edges is so weak that it can be ignored in this paper. Therefore, we can use the bond-percolation model to approximate the coverage percolation.Figure 5
Comparison betweenI(L(e1,2),L(e2,3)) and I(U(e1,2),U(e2,3)) with different κ.


## 4.1. Critical DensityλC

Firstly, a new operationAi∪Aj=⋃∀sn∈ei,jAn is defined in this section, where sn is an arbitrary point on edge ei,j of the L-coverage lattice, and An is the sphere centered at sn with radius r, as shown in Figure 4(a). In the 3D coordinate system, we adopt edge ei,j on y-axis as an example and draw some conclusions. In this figure, mi and mj are the two endpoints of edge ei,j. Therefore, Ai∪Aj is a set that contains all the coverage spheres centered at the points of edge ei,j. Based on the definition of Ai∪Aj, it is easy to have the following theorem.Figure 4
Covered region division of the edgeei,j.
(a)
(b)Theorem 5.
No sensor node withinAi∪Aj is a sufficient and necessary condition of all points on edge ei,j being not covered by any sensor nodes in the network.Proof.
There are two steps to prove the theorem as follows.(1)
From the concept ofAi∪Aj at the start of this section, we know that Ai∪Aj contains the overall coverage space of all points on ei,j. Consequently, it is obvious that if no sensor nodes exist in Ai∪Aj, all points on ei,j are not covered by any sensor nodes.(2)
On the contrary, if one point on edgeei,j is covered by a sensor node in the network, this sensor node locates within Ai∪Aj on account of the definition of Ai∪Aj. So, obviously, if all points on edge ei,j are not covered by any sensor nodes in the network, there is no sensor node within Ai∪Aj.
To sum up, the proof of Theorem5 is finished.Theorem 6.
In a 3D omnidirectional sensor network, we have(6)-2σ2ln⁡2πσ23/21-pt1/24/3πr3+πr2κ<λC<-2σ2ln⁡2πσ23/21-pt1/22π/32r+κ/2r-κ/22,where κ=1/n3.Proof.
There are three processes to demonstrate this theorem.
(
1
) Based on (2), we have (7)pNAi∪Aj=0=12πσ23exp⁡-λV22σ2=12πσ23exp⁡-λ24/3πr3+πr2κ22σ2,where V is the volume of the 3D omnidirectional sensor network, λ is the deployment density of sensor nodes in this network, and κ=1/n3. σ2 is the covariance of the Gaussian distribution, and r is the sensing radius of sensor nodes.
Then,(8)PL=1-pLei,j=0=1-12πσ23exp⁡-λ24/3πr3+πr2κ22σ2.
Therefore, it is clear thatPL increases monotonously as λ increases. Because λL=sup⁡{λ:PL≤pt}, 1-(1/2πσ23)exp⁡(-λ2(4/3πr3+πr2κ)2/2σ2)=pt. As a result, we can get λL={-2σ2ln⁡[2πσ23/2(1-pt)]}1/2/(4/3πr3+πr2κ) in (6).
(
2
) By the above analysis, we can know that it is difficult to compute the explicit expression of the probability that all points on edge ei,j are covered. Consequently, finding an approximation of PU is necessary in this paper. We assume Po is the probability of all points on ei,j being covered by one sensor node, and PO is the probability of all points on ei,j being covered by one sensor network. According to the definition of PU and PO, we have PU=PO>Po. Namely, (9)PU>Pall  points  onei,jare  covered  by  one  sensor  node.
Clearly, one sensor node covers all points onei,j if and only if some sensor node exists in Ai⋂Aj. From (2),(10)pNAi⋂Aj>0=1-12πσ23exp⁡-λ2Ai⋂Aj22σ2.
Let the volume ofAi⋂Aj be Ai⋂Aj=V′; then in Figure 4(a), we have(11)PU>1-12πσ23×exp⁡-λ2∬R4r2-x′2-y′-κ/22dδ22σ2,where (x′,y′,z′) denotes an arbitrary point within Ai⋂Aj, R:(x′)2+y′2=(r-κ/2)2, and dσ=dx′dy′. It is simple to obtain V′=2π/3(2r+κ/2)(r-κ/2)2.
In conclusion, we choosePo as the approximation of PU in this paper. Let λU=inf⁡{λ:Po≥pt}; then λU={-2σ2ln⁡[(2πσ2)3/2(1-pt)]}1/2/2π/3(2r+κ/2)(r-κ/2)2 can be achieved in (6).
(
3
) Equation (5) can be turned into(12)Uei,j=1,ifei,jis  covered  by  one  sensor  node;0,otherwise.
IfPL<pt, p{d(W)=∞}>0. Let λC′=sup⁡{λ:p{d(W)=∞}>0}; then it is easy to have λL<λC′. From (10), if 1-(1/(2πσ2)3)exp⁡(-(λV′)2/2σ2)>pt, PU>pt. Consequently, p{d(C)=∞}>0. According to the concept of λC, ({-2σ2ln⁡[(2πσ2)3(1-pt)]}1/2/V′)>λC. From (1) and (2), we obtain Theorem 6.


## 4.2. Dependence among Neighbor Edges

On the basis of (6) and Gaussian distribution, the different values of κ and r can generate the different bounds. The probabilities of all edges ei,j being open or closed are independent in the bond-percolation theory [47]. However, PL (PU) of a given edge is dependent on the neighbor edges but independent of most edges in this paper. As a consequence, we can use the bond-percolation model to approximate the coverage percolation in this paper.In this section, we illustrate the quantitative measure of the dependence betweene1,2 and e2,3 as an example.(
1
) Firstly, the mutual information in information theory [48] is employed to measure the mutual dependence between A=L(e1,2) and B=L(e2,3); that is, (13)IA,B=∑a∈0,1∑b∈0,1PABa,blog⁡PABa,bPAaPBb,where PAB(a,b)=p{L(e1,2)=a,L(e2,3)=b}, PA(a)=p{L(e1,2)=a}, and PB(b)=p{L(e2,3)=b}.In 3D omnidirectional sensor networks, we discuss the mutual dependence betweene1,2 and e2,3, shown in Figure 4(b). I(A,B) reveals the relationships among κ, r and the mutual dependence in this section. From (2), we have(14)PA0=PB0=12πσ23exp⁡-λL24/3πr3+πr2κ22σ2,(15)PA1=PB1=1-12πσ23exp⁡-λL24/3πr3+πr2κ22σ2.What is more,(16)PAB0,0=pNA1∪A3=0=12πσ23exp⁡-λL24/3πr3+2πr2κ22σ2,(17)PAB1,0=PAB0,1=PA0-PAB0,0=12πσ23×exp⁡-λL24/3πr3+πr2κ22σ2-exp-λL24/3πr3+2πr2κ22σ2,(18)PAB1,1=1-PAB0,1-PAB1,0-PAB0,0=1+12πσ23×exp⁡-λL24/3πr3+2πr2κ22σ2-2exp⁡-λL24/3πr3+πr2κ22σ2.Putting these above equations (14)–(18) into (13), we can obtain I(L(e1,2),L(e2,3)).(
2
) Similarly, the case of I(U(e1,2),U(e2,3)) can be achieved in this section. We also adopt the mutual information [48] to measure the mutual dependence between C=U(e1,2) and D=U(e2,3); namely, (19)IC,D=∑c∈0,1∑d∈0,1PCDc,dlog⁡⁡PCDc,dPCcPDd,where PCD(c,d)=p{U(e1,2)=c,U(e2,3)=d}, PC(c)=p{U(e1,2)=c}, and PD(d)=p{U(e2,3)=d}.In Figure4(b), we use I(C,D) to indicate the relationships among the mutual dependence, κ, and r. Based on formula (2), we have (20)PC0=PD0=1-12πσ23×exp⁡-λU22π/32r+κ/2r-κ/2222σ2,(21)PC1=PD1=12πσ23×exp⁡-λU22π/32r+κ/2r-κ/2222σ2.Moreover, (22)PCD1,1=pNA1∩A3=0=12πσ23×exp⁡-λU22π/32r+κr-κ222σ2,(23)PCD1,0=PCD0,1=PC1-PCD1,1=12πσ23×exp⁡-λU22π/32r+κ/2r-κ/2222σ2-exp-λU22π/32r+κr-κ222σ2,(24)PCD0,0=1-PCD0,1-PCD1,0-PCD1,1=1+12πσ23exp⁡-λU22π/32r+κr-κ222σ2-212πσ23×exp⁡-λU22π/32r+κ/2r-κ/2222σ2.Putting the formulas (20)–(24) into formula (19), I(U(e1,2),U(e2,3)) can be obtained.(
3
) Finally, when r=4, κ=1 or 2, the curves of I(L(e1,2),L(e2,3)) and I(U(e1,2),U(e2,3)) are depicted in Figure 5. As λ increases, the mutual dependence between neighbor edges decreases and it gets more close to 0. When λ>0.03, I(L(e1,2),L(e2,3)) and I(U(e1,2),U(e2,3)) are equal to 0 in this figure. I(A,B)=0 and I(C,D)=0 mean that the two edges are independent of each other [48]. From the observation of this figure, it is tempting to infer that the dependence between neighbor edges is so weak that it can be ignored in this paper. Therefore, we can use the bond-percolation model to approximate the coverage percolation.Figure 5
Comparison betweenI(L(e1,2),L(e2,3)) and I(U(e1,2),U(e2,3)) with different κ.


## 5. Simulation Evaluations

In this paper, plentiful simulations are conducted to evaluate the effectiveness and characterize the performance of our models and analytical analyses by MATLAB (version 7.7). In a 3D omnidirectional sensor network, we set the deployment space as a 100 × 100 × 100 m3 cube and deploy all the homogeneous sensor nodes under a stationary 3D Gaussian process. Based on the covered space of sensor nodes, L-coverage lattice and U-coverage lattice are built, and we analyze the experimental critical densities in the two kinds of lattice, respectively.Letr=10 and pt=0.5. The number of sensor nodes that we deploy in this network varies from 100 to 1000 per 20 steps. That is to say, the deployment density λ varies from 0.0001 to 0.001 per 0.00002 steps. 50 different (Β,r,λ) are randomly generated with each different λ. Let the probability of no exposure path existing be PN. Then, we obtain three different PN’s of the continuum percolation, the L-coverage lattice, and the U-coverage lattice for each (Β,r,λ), that is, PN,C, PN,L, and PN,U, respectively.In the experiments, we calculate the ratioN(closed  edges)/N(all  edges) for each (Β,r,λ), where N(closed  edges) means the number of closed edges and N(all  edges) denotes the number of all edges. As a result, 50 ratios for each different λ are obtained, which mean the probability Pc of any edge ei,j in the lattice being closed. In Figure 6, we plot the relationship between λ and the probability Pc=p{ei,jis  closed}. PL=p{L(ei,j)=1}, and Po=p{all points on ei,j are covered by one sensor node} is an approximation of PU=p{U(ei,j)=1}. PL and Po are the analytical values based on Definitions 2–4. PL′, Po′, and PU′ are the simulation values in this figure. As λ increases, the analytical values PL and Po are more close to the simulation values PL′ and Po′, respectively. It is clear that PL and PL′ are larger than Po and Po′. Besides, the simulation value PU′ is slightly larger than Po′ and less than PL′. In consequence, the results of the analytical values very close to the simulation values indicate that our scheme is very effective. Furthermore, we can choose Po as the approximation of PU in this paper.Figure 6
Relationship betweenλ and Pc.Letr=10 and κ=2. To get the analytical values, we put the known parameters into formula (6) and obtain the bound 0.00020743<λC<0.00065816. Meanwhile, the simulation results are λL′=0.00020, λU′=0.000580, and λC′=0.000470. The theoretical values are very close to the simulation values. As shown in Figure 7(a), PN,C, PN,L, and PN,U increase with the increase of λ, respectively. In conclusion, the simulation results of λC are consistent with the analytical results given by Theorem 6.Figure 7
Relationship betweenPN and λ with different r and κ.
(a)
r
=
10 and κ=2
(b)
r
=
10 and κ=4
(c)
r
=
15 and κ=2Similarly, we conduct the experiments with differentr and κ and get the corresponding curves of PN,C, PN,L, and PN,U as shown in Figures 7(b)-7(c). In Figure 7(b), when r=10 and κ=4, we also substitute the known parameters in formula (6) and get the range 0.00014618<λC<0.00074137. In the meantime, the simulation results are λL′=0.000140, λU′=0.0006310, and λC′=0.000580, which are consistent with the analytical results shown in Theorem 6. As λ increases, PN,C, PN,L, and PN,U increase, as shown in this figure.In Figure7(c), we set r=15, κ=2 and put these parameters into formula (6). Then, the bound 0.00015974<λC<0.00037121 of λC is derived based on the theoretical analysis. Simultaneously, the simulation results λL′=0.0001490, λU′=0.000370, and λC′=0.000320 are consistent with the analytical results derived from Theorem 6. What is more, as λ get larger, PN,C, PN,L, and PN,U also are in the rising trend.If the lower and upper bounds of critical densityλC are very loose, we cannot use them to determine a practically useful density for the network deployment [29]. Generally speaking, all of these above results imply that(1)
the lower and upper bounds ofλC become looser as κ increases; that is, the difference between λL and λU is enhanced as κ increases;(2)
the lower and upper bounds ofλC get tighter as r increases; namely, the difference between λL and λU decreases with the increase of r.Furthermore, in order to demonstrate the effectiveness of our scheme, we compare the proposed scheme with the existing scheme [16]. For simplicity, we adopt the scheme of [16] into our proposed 3D omnidirectional network model and denote it by CDWMN (critical density of wireless multihop networks). Our scheme is abbreviated to CDEPWSN (critical density for exposure-path prevention in wireless sensor networks). When r=10 and κ=2, Figure 8 compares the lower and upper bounds of critical density between CDWMN and CDEPWSN. In this figure, λL and λU are the lower and upper bounds of CDEPWSN, while the lower and upper bounds of CDWMN are λl and λu, respectively. Thus, the corresponding curves are PN,L, PN,U and PN,l, PN,u of CDEPWSN and CDWMN, respectively.Figure 8
Comparison ofλ between CDEPWSN and CDWMN with r=10 and κ=2.In Figure8, we have λL=0.20743×10-3, λU=0.65816×10-3, λl=0.1×10-3, and λu=0.8×10-3. As λ increases, PN,L, PN,U and PN,l, PN,u increase. It can be concluded that the lower and upper bounds of critical density, λl and λu, given by CDWMN are very loose such that we cannot use them to determine a practically useful density for the network deployment. However, the bounds of CDEPWSN are tighter than CDWMN and could be applied to determine a practically useful density for sensor nodes deployment process in 3D WSNs.


## 6. Conclusions and Future Works

In this paper, we consider the exposure-path problem that an intruder traverses through a deployment region and the resulting path is not covered by sensor nodes. The network coverage is rather poor if there exists an exposure path in WSNs. To address this problem, we put exposure path into a 3D uniform lattice and propose a bond-percolation-based scheme to calculate the lower and upper bounds of critical density. The proposed models and simulation results show that our scheme can generate reliable and tighter bounds of critical density in 3D wireless sensor networks.In a practical application, the sensing model of sensor nodes is not omnidirectional but directional. Consequently, our research is still in relatively ideal circumstances. In 3D directional sensor networks, the sensing area of a sensor node is a circular cone, which can be available for consultation in literature [49]. There are lots of difficulties to study the exposure-path prevention in a directional sensing model, such as the setting conditions, distributions, and multifarious calculation. However, this study has a practical significance. Based on the existing works, our future work is to solve the exposure-path prevention in 3D directional sensor networks.



---

*Source: 738974-2015-05-11.xml*