Different from the existing works on coverage problems in wireless sensor networks (WSNs), this paper considers the exposurepath prevention problem by using the percolation theory in three dimensional (3D) WSNs, which can be implemented in intruder detecting applications. In this paper, to avoid the loose bounds of critical density, a bond percolationbased scheme is proposed to put the exposurepath problem into a 3D uniform lattice. Within this scheme, the tighter bonds of critical density for omnidirectional and directional sensor networks under random sensor deployment—a 3D Poisson process are derived. Extensive simulation results show that our scheme generates tighter bounds of critical density with no exposure path in 3D WSNs.
1. Introduction
W
ireless sensor networks (WSNs) have a wide area of applications, such as military detection, healthy environment monitoring, and seism surveillance. All of these applications require the intrusions being detected by sensor nodes in the interested region
[1]
. In the area of WSNs, the intrusion detection problem belongs to node coverage issue, which is of paramount importance. Furthermore, coverage of intrusions path has a great impact on the intrusion detection. Most of the previous researches focus on the full coverage models in WSNs. Full coverage means that everywhere in the deployment area is covered by nodes, which is at the cost of resource wastes and high complexity. In fact, many applications of WSNs mainly concentrate on the exposurepath prevention which needs the partial coverage to prevent the exposure paths. In the other words, they don’t need the full coverage, and just need moving detected objects (or intrusions).
Generally, coverage creates collaborations among the nodes in covering a target region for surveying specific phenomena. Firstly, we define a covered region in which each point is covered by at least one sensor node. If an intruder can traverse through the deployment area and the resulting path isn’t covered by nodes, we name the traversed path as the exposure path. It reflects the ability of intrusions moving through the deployed area. In
[2

3]
, the authors proposed an approximation algorithm to address the minimum exposure path problem and guarantee the network performance. S. Ferrari and G. Foderaro presented an artificialpotential approach
[4]
that designed the minimumexposure paths of multiple mobile objects containing sensor nodes in a dynamic network. In addition, this approach could be used in heterogeneous wireless sensor networks (HWSNs). In allusion to the full coverage, network coverage is rather poor if there exists an exposure path in WSNs. Therefore, we consider the exposurepath prevention problem with the percolation theory in 3D WSNs.
Percolation theory was first put forward by Broadbent and Hammersley to simulate the percolation process of immersed rocks
[5]
, which is appropriate for modeling the disordered media. On the one hand, percolation theory deals with clustering, criticality, diffusion, fractals, phase transitions and disordered systems. It also provides a quantitative model for understanding these phenomena. Therefore, percolation theory is a theoretical and statistical background for various physical and natural sciences. In addition, this theory describes emergent properties related to the connectivity of large numbers of objects. Due to some spatial extent of these objects, their spatial relationships are relevant and statistically prescribed. Thus, percolation theory is related to graph and network theories
[6]
, which exists within the intersection of probability theory and topology. For the present purpose, the chief relevance of percolation theory is its ability to deliver global properties from local properties. In
[7]
, the global properties sought to describe flow, conduction and other transport properties of porous media.
According to percolation theory
[8

9]
, if we assume
p
as the average degree of connectivity between various subunits of some arbitrary system, there exists a percolation threshold
p_{t}
. When
p
≥
p_{t}
, there is no exposure path from one side of the system to the other. There are some researches that lie in the exposurepath problem and percolation theory, and we will introduce the related works in Section 2.
The existing works
[2

7
,
10]
mainly focus on the exposurepath problems in two dimensional (2D) networks. Nevertheless, 3D WSNs are more apt for practice in most applications
[11]
, and no more contributions are achieved so far. In this paper, we consider the exposurepath prevention problem with percolation theory in 3D WSN scenarios. In order to address this problem and get the tighter bonds of critical density, we put the exposurepath problem into a 3D uniform lattice and propose a bond percolationbased scheme to calculate the tighter bounds of critical density. The scope of the proposed scheme is to detect intrusions in 3D WSNs, which has important practical implications.
The remainder of this paper is organized as follows. Section 2 introduces the related works of barrier coverage and percolation theory. Section 3 presents the system models and problem formulation about exposurepath prevention in 3D WSNs. Section 4 highlights the bondpercolation theory to derive and analyze the optimal critical density for exposurepath problem. Moreover, we discuss the mutual dependence among edges of the proposed bond percolationbased scheme in this section. The models and schemes we proposed is evaluated by the extensive simulation results in Section 5. Section 6 concludes this paper.
2. Related Work
This section introduces the recent results about barrier coverage and percolation theory in WSNs. The exposurepath prevention problem is one part of barrier coverage.
 2.1. Barrier Coverage
According to the different covered objects, the researchers classify the coverage of static WSNs into three types: area coverage
[12]
, point coverage
[13]
and barrier coverage
[14]
, as shown in
Fig. 1
(a)(c). The area coverage is full coverage, which requires each point within the target area covered by at least one node,. The point coverage considers the coverage of several discrete targets, i.e., the partial coverage. The barrier coverage focuses on the detection ability of moving targets. In this paper, the mentioned exposurepath problem belongs to the barrier coverage.
The coverage problem
The significance of barrier coverage is as follows. For the monitor, it can determine the optimal deployment to make the biggest detection probability. For the intruder, it can choose the most secure path to pass through the monitor area. In
[15]
, Meguerdichian
et al
. firstly introduced the notion and model of barrier coverage in WSNs. They tried to determine the QoS of the optimal or worst coverage, and proposed a centralized algorithm based on Voronoi and Delaunay triangulation partition. The authors of
[16]
defined a
kbarrier coverage
, and proposed its discriminating algorithms after the deployment. They also presented two probabilistic barrier coverage concepts, namely,
weak
and
strong barrier coverage
. Meanwhile, they derived the minimum number of sensor nodes required to ensure weak barrier coverage with high probability. However, strong barrier coverage is still an open issue.
Most aspects of barrier coverage are researched in some literatures
[17

22]
. Due to the globalized nature of barrier coverage, it is very difficult to solve the problem in a decentralized way. To address this challenge, Chen
et al
.
[17]
introduced the concept of local barrier coverage and devised localized sleepwakeup algorithms to provide nearoptimal solutions. In
[18]
, for strong barrier coverage, the authors proposed an efficient distributed algorithm to construct multiple disjoint barriers in a randomly deployed WSN on a long irregular strip region. The algorithm reduced the network delay and communication overhead compared with a centralized solution. In
[19]
, Chen
et al
. studied the quality of barrier coverage and identified where a repair is needed when the barrier performance is less than a predefined value. Saipulla
et al
.
[20]
investigated the barrier coverage of the linebased deployment rather than the Poisson distribution model. They also derived a tight lowerbound probability of the existence of barrier coverage. G. Yang and D. Qiao
[21]
exploited the sensing collaboration between sensor nodes to research the weak barrier coverage. The authors of
[22]
presented an energy efficient scheduling algorithm with a probabilistic sensing model for barrier coverage.
All the above studies are within the scope of omnidirectional and static WSNs. Regarding directional or dynamic WSNs, there are also many studies
[23

27]
. Wang and Cao
[23]
introduced a novel fullview coverage model to camera sensor networks. Further, a novel method to select camera sensor nodes from an arbitrary deployment was suggested in
[24]
to form a camera barrier. Ma
et al
. studied the minimum camera barrier coverage problem in camera sensor networks
[25]
. In
[26]
, the problem of finding appropriate orientations of directional sensor nodes was investigated to provide strong barrier coverage. With the development of mobile sensors, He
et al
.
[27]
investigated the costeffective barrier coverage problem in the circumstances of no sufficient mobile nodes existing, and designed sensor patrolling algorithms to improve barrier coverage.
 2.2. Percolation Theory
In
[28]
, Gilbert firstly raised the concept of continuum percolation to find the critical density of a Poisson point process. An unbounded connected component almost surely appears at this density so as to make the network provide long distance multihop communication. For studying continuum percolation, Gilbert’s model is the foundation of wireless networks. Percolation threshold is adopted to investigate the connectivity of wireless networks. Penrose
[29]
indicated that as the number of nodes goes to infinity, the critical range for the probability of establishing overall connectivity is close to 1. This range leads to each node connecting to neighbors on average. Based on the percolation theory, Gupta and Kumar
[30]
used the correlation 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 restrict the application of continuumpercolation theory.
In
[31]
, for both Poisson and hardcore stationary point processes, the authors demonstrated the existence of site and bond percolation in the Gabriel graph
[32]
. The simulation results showed that the critical bounds correspond to the existence of two paths of open sites and open bonds, respectively. The authors of
[33]
presented different classes of coverage algorithms and determined the critical density of a Poisson point process. Simultaneously, they talked about the almost sure existence of an unbounded connected component based on the ratio of the connectivity range of the base stations to the clients’. In
[34]
, Glauche
et al
. discussed a distributed protocol to guarantee strong connectivity in ad hoc networks. Their proposed problem to find the critical communication range of mobile devices could be interpreted as that of determining the critical node neighborhood degree. Above this range, an ad hoc network graph is almost surely connected. The authors of
[35]
characterized fundamental coverage properties of largescale sensor networks in the consideration of both Boolean and probabilistic sensing models for a variety of network scenarios. For efficient topology control of the network, the concept of monotone percolation was put up in
[36]
based on the local adjustment of the communication radii of the sensor nodes. They also presented some algorithms to guarantee the existence of relatively short paths between any pair of source and destination nodes. Habib
et al
.
[37]
focused on percolation in coverage and connectivity of 3D WSNs. It was an integrated continuum percolation problem due to the dependency between coverage and connectivity. Therefore, the authors proposed an integrated concentricsphere model to address coverage and connectivity in an integrated way. Khanjary
et al
.
[38]
introduced alignedorientation directional sensor networks, and proposed an approach to calculate the density of nodes at critical percolation in such networks by using continuum percolation. In these networks, sensor nodes were deployed based on a Poisson point process and the orientation of all sensor nodes is the same.
However, most existing percolationbased schemes apply the common continuumpercolation theory, enduring the loose lower and upper bounds on the critical density. Thus, these theoretical results may not be directly applied to most application scenarios ofWSNs. To solve this problem, we offer a bond percolationbased scheme through mapping the exposure pathprevention problem into a bond percolation model in 3D WSNs. Depending on the deployment of sensor nodes obeying a 3D Poisson process, we deduce the critical densities for both omnidirectional and directional sensor networks under random sensor deployment.
3. System Models And Problem Formulation
In the beginning, we present the sensing and deployment models of omnidirectional and directional sensor networks. Then, the exposurepath prevention problem is formulated by the continuumpercolation theory
[39]
in 3D WSNs.
In a vast 3D WSN, we deploy sensor nodes randomly and uniformly whose locations can be modeled as a stationary 3D Poisson distribution with an intensity
λ
> 0. In any subregion
V
', the number of sensor nodes
N
(
V
') =
k
follows the Poisson distribution with a parameter
λ
║
V
'║, where ║
V
'║ is the volume of
V
'. Then, the probability intensity function is
 3.1. System Models
 3.1.1. Omnidirectional sensing Model
We adopt the sphere model (Β,
r
,
λ
)
[11]
as the sensing model in omnidirectional sensor networks. In this model, the node sensing range is a spherical region Β with sensing radius
r
, as shown in
Fig. 2
(a), and
λ
is the deployment density of the sensor nodes. If
s
: (
x_{s}
,
y_{s}
,
z_{s}
) denotes a node position in space rectangular coordinate
o−xyz
, a targeted point
t
: (
x_{t}
,
y_{t}
,
z_{t}
) is said to be covered by
s
when the Euclidean distance 
st
 =
is not larger than
r
.
System models.
 3.1.2. Directional sensing Model
Different from the above omnidirectional sensing model, we employ a widely used model —the directional sensing model
[40]
in the actual applications
[41]
,
[42]
. As shown in
Fig. 2
(b), the sensing area is the circular cone (
s
,
r
,
,
α
), where
is the central unit vector termed as sensing direction, and
α
is the offset angle of the field of view (FOV).
t
is said to be covered by
s
if and only if two conditions are satisfied:

1) The Euclidean distance st ≤r;

2) The anglebetweenandis within [0,].
In directional sensor networks, we assume
θ
is the angle of
relative to
xoz
plane, and
θ
is a random variable with the uniform distribution on [0,2
π
], i.e.,
θ
U
[0,2
π
].
 3.2. Problem Formulation
Let
R
^{3}
be the 3D WSN and its volume is
V
. We partition the deployment space into the covered region
C
covered by at least one sensor node, and the vacant region
W
covered by no sensor node. The definition of exposure path in a 3D network is given in the following.
Definition 1:
If a continuous strip
S
(or curve
S
) belongs to any vacant region
W
,
S
from one side to the other side of the deployment region is defined as an exposure path, see
Fig. 3
(a)(b).
Relationship between exposure path S and sensor node density λ_{C}.
Sensor nodes may be spread in an arbitrary pattern, as shown in
Fig. 3
(a)(d). An exposure path exists in the 3D network if
λ
≤
λ_{C}
(
Fig. 3
(a)(b)), and not vice versa (
Fig. 3
(c)(d)).
λ_{C}
is the critical threshold. However, the extortionate density will cause vast redundancy, which leads to high implementation complexity and cost. Therefore,
λ
is the optimal density when there are no exposure paths and no redundancy in 3D networks.
Consequently, the exposurepath prevention problem is formulated as the calculation of the critical density
λ_{C}
in a 3D network. To get the tighter bounds of
λ_{C}
, we apply bond percolation theory for the 3D WSNs in the following sections. On the basis of the theory of limit, strip
S
can be considered as the countless curves superposition. For simplicity, we just choose one curve of strip
S
to discuss, denoted as path
S
.
 3.3. Bond percolation model
To solve the exposurepath prevention problem, we divide the 3D sensor network into a 3D uniform lattice.
d
(
C
,
λ
) and
d
(
W
,
λ
) denote the number of lattices in the regions
C
and
W
, respectively. Let the critical density
[8]
be
λ_{C}
= inf{
λ
:
p
(
d
(
C
,
λ
) = ∞) > 0}. It is simple to derive that there exists an exposure path in the 3D network if
λ
≤
λ_{C}
.
It is assumed that one unit cube region contains
n
vertexes, i.e.,
M
= {
m
_{1}
,
m
_{2}
,...,
m_{n}
}, forming a
lattice as shown in
Fig. 4
.
is used to approximately substitute for
for the sake of simplicity, which doesn’t affect our final results. The edge between vertex
m_{i}
and
m_{j}
is denoted as
e_{i,j}
, where
i
,
j
∈ [1,
n
]. Thus, the edge length of the neighboring vertexes is
μ
=
(
n
vertexes don’t include the ones which lie on the edges of the cube). The following definitions identify the relationship between
e_{i,j}
and the lower and upper bounds of
λ_{C}
.
The unit cube region with a virtual lattice.
Definition 2:
For edge
e_{i,j}
, we define
Then, if
L
(
e_{i,j}
) = 1,
e_{i,j}
is defined as Lclosed edge; if
L
(
e_{i,j}
) = 0,
e_{i,j}
is called as Lopen edge.
Thus, if
U
(
e_{i,j}
) = 1,
e_{i,j}
is named as Uclosed edge; if
U
(
e_{i,j}
) = 0,
e_{i,j}
is denoted as Uopen edge.
Definition 3:
Let
Z
^{3}
be the 3D lattice with vertex set
M
, edge set
E
and 
M
 =
n
. If
e_{i,j}
between arbitrary two neighboring is Lclosed/Lopen,
Z
^{3}
is said to be an Lcoverage lattice; If it is Uclosed or Uopen,
Z
^{3}
is called a Ucoverage lattice.
Definition 4:
A path
S
in
Z
^{3}
goes via a sequence of edges
e
_{1,2}
,
e
_{2,3}
,...,
e
_{i,i+1}
,...
i
≥ 1, if all the edges in
S
are Lopen/Uopen,
S
is named the Lopen/Uopen path; if all the edges are Lclosed/Uclosed,
S
is called the Lclosed/Uclosed path.
With the above definitions, we derive that: 1) if edge
e_{i,j}
is the Uclosed edge, then it must be the Lclosed edge in terms of coverage; 2) the upper bound
λ_{u}
of the critical density
λ_{C}
could be derived by Ucoverage lattice, and the lower bound
λ_{l}
by Lcoverage lattice for 3D sensor networks.
4. Bounds of Critical Density
In this paper, if
p
is the probability of an arbitrary edge being closed in the 3D lattice, a threshold value
p_{t}
∈ [0,1] exists and results in the differences of the global behavior of the system in two regions
C
and
W
. Generally, for all
p
>
p_{t}
, there exists one closed path from one side to the other of the 3D network. On the contrary, there is no closed path for all
p
<
p_{t}
. To ease presentation, we define
P_{L}
=
p
{
L
(
e_{i,j}
) = 1} ,
P_{U}
=
p
{
U
(
e_{i,j}
) = 1} ; and
λ_{l}
= sup{
λ
:
P_{L}
≤
p_{t}
},
λ_{u}
= inf{
λ
:
P_{U}
≥
p_{t}
}. Then, we have
p
{the exposure pathexists} > 0 if
P_{L}
<
p_{t}
, and
p
{the exposure pathexists } = 0 if
P_{U}
>
p_{t}
.
 4.1. Critical Density λC
 4.1.1. λCof Omnidirectional Sensor Nodes
As shown in
Fig. 5
(a),
s_{n}
is one arbitrary point on edge
e_{i,j}
of the Lcoverage lattice, and we define an operator ‘∪’ :
A_{i}
∪
A_{j}
A_{n}
in this paper, where
A_{n}
is the sphere centered at
s_{n}
with radius
r
. Then,
A_{i}
∪
A_{j}
is a set containing all the coverage spheres centered at the points of
e_{i,j}
.
Covered region division of the edge e_{i,j}.
Lemma 1:
No sensor node in
A_{i}
∪
A_{j}
is a sufficient and necessary condition of all points on
e_{i,j}
being not covered.
Proof:
Based on the definition of
A_{i}
∪
A_{j}
, it contains the total coverage space of all points on
e_{i,j}
. Therefore, it is clear that if there is no sensor nodes in
A_{i}
∪
A_{j}
, all points on
e_{i,j}
aren’t covered by any sensor nodes. The reverse is also true.
Next, we exploit
e_{i,j}
on
y
axis as an example and draw the following conclusion.
m_{i}
and
m_{j}
are the two endpoints of edge
e_{i,j}
.
Theorem 1:
In 3D omnidirectional sensor networks, we have
Proof:
Following are three steps to prove the theorem.
1) From (1), we have
p
{
N
(
A_{i}
∪
A_{j}
) = 0} = exp(
λ
║
A_{i}
∪
A_{j}
║) = exp(
λ
. Then,
P_{L}
= 1 
p
{
L
(
e_{i,j}
) = 0} = 1  exp(
λ
.
Consequently,
P_{L}
increases monotonously as
λ
increases. Since
λ_{l}
= sup{
λ
:
P_{L}
≤
p_{t}
}, 1  exp(
λ_{l}
=
p_{t}
. Therefore, we can get
λ_{l}
in (4).
2) Based on the above analysis, the probability of all points on
e_{i,j}
being covered is difficult to derive the explicit expression. As a result, we need to find an approximation of
P_{U}
. We denote
P_{o}
as the probability that all points on
e_{i,j}
are covered by one sensor node. Since
P_{U}
is the probability that all points on
e_{i,j}
are covered by one sensor network, obviously,

PU>P{all points onei,jare covered by one sensor node} =Po.
It is clear that one sensor node covers all points on
e_{i,j}
if and only if some sensor node exists in
. From (1),
Let
A
= ║
║. According to
Fig. 5
(a), we can obtain
where an arbitrary point in
is (
x
',
y
',
z
') ,
R
: (
x
')
^{2}
+ (
y
')
^{2}
=
, and
dσ
=
dx
'
dy
'. It is easy to obtain
A
=
.
As a consequence, we choose
P_{o}
as the approximation of
P_{U}
. Let
λ_{u}
= inf{
λ
:
P_{o}
≥
p_{t}
}. Then we can get
λ_{u}
in (4).
3) Equation (3) is equal to
If
P_{L}
<
p_{t}
, then
p
{
d
(
W
) = ∞)} > 0. It is easy to know that
λ_{l}
<
λ
'
_{C}
. From (6), if 1exp(−
λA
) >
p_{t}
, then
P_{U}
>
p_{t}
. In consequence, we can derive that if 1exp(−
λA
) >
p_{t}
, then
p
{
d
(
C
) = ∞)} > 0. According to the definition of
λ_{C}
, we have
. From 1) and 2), we gain the
Theorem 1
.
 4.1.2. λCof Directional Sensor Nodes
In
Fig. 6
, we assume a directional sensor node locates an arbitrary point
F
(
x_{f}
,
y_{f}
,
z_{f}
) in
A_{i}
∪
A_{j}
. The sphere centered at
F
with radius
r
intersects
y
axis at
F
_{1}
(0,
y_{f}

, 0) and
F
_{2}
(0,
y_{f}
+
, 0), using
e_{i,j}
on
y
axis as an example in
Fig. 6
(a)(d). For simplicity, let
f
_{1}
=
y_{f}

,
f
_{2}
=
y_{f}
+
, and
be the angle between vector
and
. Based on the theory of limit, the circular cone
ψ
is known as the countless sectors superposition. Firstly, one sector
ϖ
is considered in
ψ
. Then, through the countless sectors superposition, we have
Theorem 2
.
The relative positions of F_{1}, F_{2}, m_{i} and m_{j}.
Theorem 2:
In 3D directional sensor networks, we have
where
dν
=
dxdydz
,
Proof:
Three steps are needed to verify this theorem.
1) We assume the probability
P_{N}
that all points on edge
e_{i,j}
are not covered by a directional sensor node (
F
,
r
,
,
α
).
m_{i}
and
m_{j}
are the two endpoints of edge
e_{i,j}
. According to the different positions of
F
_{1}
,
F
_{2}
relative to
m_{i}
and
m_{j}
, the following conditions are obtained in
Fig. 6
(a)(d).
θ
is depicted in this figure. In order to simplify drawing, we just describe
θ
in one side of the vertical dashed line.
1. If
in
Fig. 6
(a), the node can’t cover any point on
e_{i,j}
if and only if the angle
θ
is smaller than the angle of
minus
, and is larger than the angle of
plus
.
θ
[0,2
π
]. Therefore,
Analogously, we have the following conclusions.
2. In
Fig. 6
(b), if
, thus,
3. In
Fig. 6
(c), if
, then,
4. In
Fig. 6
(d), if
, hence,
With the calculus theory, the region
A_{i}
∪
A_{j}
is divided into
u
small enough regions,
R
_{1}
,
R
_{2}
, …,
R_{u}
. The circular cone
ψ
is divided into
g
small sectors,
ϖ
_{1}
,
ϖ
_{2}
, …,
ϖ_{g}
. When
u
→ ∞ and
g
→ ∞, the differential
dv
=
dxdydz
of volume equal to ║
R_{q}
║, 1 ≤
q
≤
u
. Let
P_{q}
be the probability that no sensor node cover
e_{i,j}
in
R_{q}
. Then, from (1) we have
As
u
→ ∞ and
g
→ ∞,
Based on (9)(12),
P_{L}
increases monotonously with the increase of
λ
. So, based on the Section 4, we solve
=
p_{t}
to get
λ_{l}
.
2)
Fig. 5
indicates that all points on
e_{i,j}
are covered by one sensor node, if and only if the two conditions are satisfied: a. the sensor node locates in
.
P_{o}
denotes the probability that all points on
e_{i,j}
are covered by one sensor node. We consider the probability
P
'
_{N}
that the directional sensor node in
can’t cover all points on
e_{i,j}
. It is easy to see that
P
'
_{N}
= 1 when
, if not,
P
'
_{N}
=
. Similar to 1), we divide the region
into
u
small enough regions whose volume is roughly equal to
dν
. From (13)(14), we have
Therefore, we obtain
λ_{u}
in (8).
3) From Section 4.1.2, 1) and 2), we achieve
Theorem 2
.
 4.2. Dependence Among Neighboring Edges
From (4) and (8), different values of
μ
,
r
and
P_{N}
can generate the different bounds. It is obvious that the probabilities of all edges
e_{i,j}
being open or closed are independent in the bond percolation
[2]
. However, in this paper,
P_{L}
(
P_{U}
) of a given edge is dependent on the neighboring edges, but independent on most edges. Consequently, the bond percolation model is used to approximate the coverage percolation.
In this section, the quantitative measure of dependence between
e
_{1,2}
and
e
_{2,3}
is illustrated as an example. We use mutual information in Information Theroy to measure the mutual dependence between
B
=
L
(
e
_{1,2}
) and
C
=
L
(
e
_{2,3}
), i.e.,
where
P_{BC}
(
b
,
c
) =
p
{
L
(
e
_{1,2}
) =
b
,
L
(
e
_{2,3}
) =
c
} ,
P_{B}
(
b
) =
p
{
L
(
e
_{1,2}
) =
b
} and
P_{C}
(
c
) =
p
{
L
(
e
_{2,3}
) =
c
}. Next, we discuss the mutual dependence in omnidirectional sensor networks.
In
Fig. 5
(b),
I
(
B
,
C
) reveals the relationships based on
μ
,
r
and the dependence. From (1), we have

PB(0) =PC(0) = exp(λl(+πr2μ)),

PB(1) =PC(1) = 1exp(λl(+πr2μ)).
Put these above equations into (16), we get
I
(
L
(
e
_{1,2}
),
L
(
e
_{2,3}
)). Given that the case of
I
(U(
e
_{1,2}
),
U
(
e
_{2,3}
)) is similar to the above, and similar conclusions can also be calculated. When
r
= 4,
μ
= 1 or 2, we plot the curves of
I
(
L
(
e
_{1,2}
),
L
(
e
_{2,3}
)) and
I
(
U
(
e
_{1,2}
),
U
(
e
_{2,3}
)) in
Fig.7
. Through the observation, we find that the dependence between neighboring edges is weak. Therefore, the bond percolation model can be used to approximate the coverage percolation.
Comparison between I(L(e_{1,2}), L(e_{2,3})) and I(U(e_{1,2}),U(e_{2,3})) with different μ.
Similarly, after similar calculations and drawing with Matlab, mutual information
I
(
B
,
C
) for directional sensor networks can also be derived, as shown in
Fig. 8
. When
α
=
,
I
(
L
(
e
_{1,2}
),
L
(
e
_{2,3}
)) and
I
(
U
(
e
_{1,2}
),
U
(
e
_{2,3}
) are close to 0. For random
θ
, it is easy to see that any two neighboring edges in directional sensor networks are nearly independent with each other, here no longer expatiatory. To sum up, the coverage percolation can be approximately regarded as a bond percolation model.
Comparison between I(L(e_{1,2}), L(e_{2,3})) and I(U(e_{1,2}),U(e_{2,3}) with different α.
5. Simulation Evaluations
Finally, the effectiveness of our model and theoretical analyses are demonstrated through simulation with Matlab 7.0 in this section. Here, sensor nodes are deployed under the stationary 3D Poisson point process. The deployment region is a 100×100×100m
^{3}
cube. With the simulation results, we analyze the experimental critical densities in Lcoverage lattice and Ucoverage lattice, respectively.
 5.1. Omnidirectional Sensor Networks
Let
r
= 10 and
p_{t}
= 0.5. The number of sensor nodes
N_{V}
varies from 100 to 1000 per 20 steps. Then, the density
λ
varies from 0.0001 to 0.001 per 0.00002 steps. For every
λ
, 50 different (B,
r
,
λ
) are randomly generated. The probability of no exposure path existing is denoted by
P_{N}
. Three different
P_{N}
corresponding to the continuum percolation, the Lcoverage lattice, and the Ucoverage lattice,
P
_{N,C}
,
P
_{N,L}
and
P
_{N,U}
, are obtained for each (B,
r
,
λ
), respectively.
Fig. 9
shows the relationship between
λ
and the probability
P_{c}
=
p
{
e_{i,j} is closed
}. As
λ
increases,
P_{c}
increases. According to
Definition 24
, we get the theoretical values
P_{L}
and
P_{o}
which are close to the simulation values
P_{L}
' and
P_{o}
', respectively. Clearly,
P_{L}
and
P_{L}
' are larger than
P_{o}
and
P_{o}
'. Furthermore, we get the value of
P_{U}
' by simulation which is slightly larger than
P_{o}
' and less than
P_{L}
'.
Relationship between λ and P_{c}.
Substituting
r
= 10 and
μ
= 2 into (4), we obtain 0.00014421 <
λ_{C}
< 0.0001936 . The simulation results are
λ_{l}
' = 0.000137,
λ_{u}
' = 0.000189 and
λ_{C}
' = 0.000176. As shown in
Fig. 10
(a),
P
_{N,C}
,
P
_{N,L}
and
P
_{N,U}
increase with the increase of
λ
, and the simulation result of
λ_{C}
is consistent with the theoretical analysis in
Theorem 1
.
Relationship between P_{N} and λ with different r and μ.
Analogously, we do the experiments with different
r
and
μ
. Then, the corresponding curves of
P
_{N,C}
,
P
_{N,L}
and
P
_{N,U}
are obtained in
Fig. 10
(b)(c).
P
_{N,C}
,
P
_{N,L}
and
P
_{N,U}
also increase with the increase of
λ
. When
r
= 10 and
μ
= 4, we get 0.00012754 <
λ_{C}
< 0.00023388 from (4). The simulation results are
λ_{l}
' = 0.000121,
λ_{u}
' = 0.000227 and
λ_{C}
' = 0.000199, which are consistent with the analytical results in
Theorem 1
, as shown in
Fig. 10
(b).
In
Fig. 10
(c),
P
_{N,C}
,
P
_{N,L}
and
P
_{N,U}
also increase with the increase of
λ
. When
r
= 11 and
μ
= 2, we obtain 0.00010965 <
λ_{C}
< 0.00014318 according to (4). The simulation results
λ_{l}
' = 0.000101,
λ_{u}
' = 0.000137 and
λ_{C}
' = 0.000128, which are consistent with the analytical results in
Theorem 1
.
These results of many experiments imply that:

1) The bonds ofλCbecomes looser asμincreases.

2) The bonds ofλCgets tighter asrincreases.
For the convenience, we first put the scheme
[11]
denoted as CDMN (Critical Density of Wireless MultiHop Networks) into our proposed 3D omnidirectional network model. Then, we define our proposed scheme as PTEP (Percolation TheoryBased ExposurePath Prevention).
Fig. 11
shows the comparison of critical density between CDMN and PTEP when
r
= 10 and
μ
= 2.
λ_{L}
and
λ_{U}
are the lower and upper bounds of PTEP, while
λ
'
_{L}
and
λ
'
_{U}
are the lower and upper bounds of CDMN, respectively. The corresponding curves
P
_{N,L}
,
P
_{N,U}
, and
P
'
_{N,L}
,
P
'
_{N,U}
are obtained from CDMN and PTEP, respectively. From this figure,
λ
'
_{L}
= 0.1 × 10
^{3}
,
λ_{L}
= 0.14421 × 10
^{3}
,
λ_{U}
= 0.1936 × 10
^{3}
, and
λ
'
_{U}
= 0.3 × 10
^{3}
. It can be concluded that the bounds of critical density given by CDMN are very loose such that they can not be applied to determine a practically useful density for sensor nodes deployment process. The lower and upper bounds of PTEP are tighter than CDMN’s, and we could implement PTEP in 3D WSNs coverage to prevent exposure paths.
Comparision of λ between PTEP and CDMN with r = 10 and μ = 2.
 5.2. Directional Sensor Networks
Let
r
= 10 and
α
=
. In the same way, we set that the number of sensor nodes
N_{V}
varies from 500 to 2500 per 50 steps. Thus, the density
λ
varies from 0.0005 to 0.0025 per 0.00005 steps. For each different value of
λ
, we generate 50 different (
s
,
r
,
,
α
) randomly generated.
In
Fig. 12
, it shows the relationship between
λ
and
P_{c}
=
p
{
e_{i,j} is closed
}.
P_{c}
increases as
λ
increases. According to (14)(15) and simulation results, we get the analytical values
P_{L}
,
P_{o}
and the simulation values
P_{L}
',
P_{o}
'. From
Fig. 12
,
P_{L}
basically is equal to
P_{L}
', and
P_{o}
is less than
P_{o}
' by 1%. Obviously,
P_{L}
and
P_{L}
' are larger than
P_{o}
and
P_{o}
', approximately 0.18. Moreover, the value of
P_{U}
' is obtained by simulation which is slightly bigger than
P_{o}
'.
Relationship between λ and P_{c}.
We substitute
r
= 10 and
α
=
into (8), and obtain 0.000712 <
λ_{C}
< 0.00210. The simulation results are
λ_{l}
' = 0.000720,
λ_{u}
' = 0.00202 and
λ_{C}
' = 0.00190. As shown in
Fig. 13
(a),
P
_{N,C}
,
P
_{N,L}
and
P
_{N,U}
also increase as the increase of
λ
. Then, we conclude that the simulation result of
λ_{C}
is consistent with the analytical results in
Theorem 2
.
Relationship between P_{N} and λ with different α.
Similarly, we do the experiments with different
r
and
α
.
Fig. 13
(b)(c) show the relationship between
P_{N}
and
λ
. In the three figures,
P
_{N,C}
,
P
_{N,L}
and
P
_{N,U}
also increase as
λ
increases. When
r
= 10 and
α
=
, we get 0.00052 <
λ_{C}
< 0.0013 from (8) as shown in
Fig. 13
(b). The simulation results are
λ_{l}
' = 0.00051,
λ_{u}
' = 0.00128 and
λ_{C}
' = 0.00122, which are consistent with the analytical results in
Theorem 2
.
In
Fig. 13
(c), when
r
= 15 and
α
=
, we do the calculation from (8), and get 0.000605 <
λ_{C}
< 0.00220. The simulation results
λ_{l}
' = 0.000684,
λ_{u}
' = 0.00223 and
λ_{C}
' = 0.00178 are consistent with the analytical results in
Theorem 2
.
All of the above results imply that:

1) The bonds ofλCbecomes tighter as the increase ofα.

2) The bonds ofλCgets looser asrincreases.
To facilitate discussion, we also put CDMN
[11]
into our proposed 3D directional network model. When
r
= 10 and
α
=
,
Fig. 14
demonstrates the comparison of the lower and upper bounds between CDMN and PEPT. Let
λ_{L}
,
λ_{U}
and
λ
'
_{L}
,
λ
'
_{U}
be the lower and upper bounds of PTEP and CDMN, respectively. In
Fig. 14
,
λ
'
_{L}
= 0.712 × 10
^{3}
,
λ_{L}
= 0.712 × 10
^{3}
,
λ_{U}
= 2.1 × 10
^{3}
,
λ
'
_{U}
= 2.5 × 10
^{3}
. And the corresponding curves
P
_{N,L}
,
P
_{N,U}
, and
P
'
_{N,L}
,
P
'
_{N,U}
are obtained from PTEP and CDMN, respectively. The simulation results show that the lower bound of CDMN is close to the lower bound of PTEP, while its upper bound is larger than PTEP’s. Hence, the bounds of critical density given by CDMN are very loose. So we can not apply them to determine a practically useful density for 3Dnetwork deployment. Conversely, due to the tighter lower and upper bounds of PTEP, it could be implemented to address the exposurepath prevention problem in 3D WSNs.
Comparision of λ between PTEP and CDMN with r = 10 and α = .
6. Conclusion
In this paper, the exposurepath prevention problem with the percolation theory was considered in 3D omnidirectional and directional WSNs, which could be applied in intruder detecting applications. In order to solve this problem, we put it into a 3D uniform lattice and proposed a bond percolationbased scheme to calculate the tighter bounds of critical density. The proposed models and simulation results demonstrated that our scheme generated tighter bounds of critical density and ruled out the exposure path in 3D WSNs. To prevent exposure paths in 3D WSNs is still our future research field.
BIO
Xiaoshuang Liu received the M.S. degree from Hebei Normal University, Hebei, China, in 2012. She is currently working toward the Ph.D. degree in communication and information system at the School of Information and Communication Engineering, Beijing University of Posts and Telecommunications, Beijing, China. Her research interests include optimization, wireless sensor network, et al.
Guixia Kang received the M.S. degree from Tianjin University, Tianjin, China, and the Ph.D. degree in electrical engineering from Beijing University of Posts and Telecommunications (BUPT), Beijing. She was a research scientist in the Future Radio Concept Department of Siemens, Munich, Germany. She is currently a Professor with BUPT. Her interests include the research, development and standardization of 3G and beyond 3G (B3G) wireless communications systems as well as wireless sensor networks.
Ningbo Zhang received his Ph. D. degree from the Beijing University of Posts andTelecommunications, China in 2010. After that, he worked in the Huawei Technology as a senior researcher. From 2010 to 2014, he worked for 3GPP and proposed more than 100 contributions. From 2014 to now, he worked in the Beijing University of Posts and Telecommunicatios. His research interests include M2M communication, D2D communication, advanced channel coding and modulation, cooperative communication and cognitive radio etc.
Djidjev H.
2007
“Efficient computation of minimum exposure paths in a sensor network field,”
inProc. of DCOSS
LNCS 4549
295 
308
Djidjev H.
2010
“Approximation algorithms for computing minimum exposure paths in a sensor field,”
ACM Trans. Sensor Netw.
7
(3)
1 
3
DOI : 10.1145/1807048.1807052
Ferrari S.
,
Foderaro G.
“A Potential field approach to finding minimumexposure paths in wireless sensor networks,”
in Proc. of IEEE Int. Conf. Robot. Autom. Anchorage Conv. District
May 2010
335 
341
Broadbent S R
,
Hammersley J M
1957
“Percolation processes I. Crystals and mazes,”
Proceedings of the Cambridge Philosophical Society (S03050041)
53
(4)
629 
641
DOI : 10.1017/S0305004100032680
Stauffer Dietrich
,
Aharony Amnon
1991
“Introduction to percolation theory,”
Taylor and Francis (519.237.8)
London
2 
5
Hunt A
,
Ewing R
,
Ghanbarian B
2014
“Percolation Theory for Flow in Porous Media Lecture Notes in Physics,” Volume 880
1 
35
Aharony A
,
Stauffer D
2003
“Introduction to percolation theory,”
Taylor & Francis
Grimmett G.
1999
“What is Percolation?”
2nd ed
SpringerVerlag,
New York, NY, USA
Liu Liang
,
Zhang Xi
,
Ma Huadong
2013
“Percolation TheoryBased ExposurePath Prevention for Wireless Sensor Networks Coverage in Internet of Things,”
Sensors Journal, IEEE
13
(10)
3625 
3636
DOI : 10.1109/JSEN.2013.2267554
Ng S C
,
Mao G
,
Anderson B D O
2013
“Critical density for connectivity in 2D and 3D wireless multihop networks,”
Wireless Communications, IEEE Transactions on
12
(4)
1512 
1523
DOI : 10.1109/TWC.2013.021213.112130
Yang Q.
,
He S.
,
Li J.
,
Chen J.
,
Sun Y.
2014
“EnergyEfficient Probabilistic Area Coverage in Wireless Sensor Networks,”
Vehicular Technology, IEEE Transactions on
PP
(99)
1 
1
Ostovari P.
,
Dehghan M.
,
Jie Wu
“Connected Point Coverage in Wireless Sensor Networks Using Robust Spanning Trees,”
in Proc. of Distributed Computing Systems Workshops (ICDCSW), 2011 31st International Conference on
2024 June 2011
vol., no.
287 
293
He Shibo
,
Chen Jiming
,
Li Xu
,
Shen X.S.
,
Sun Youxian
2014
“Mobility and Intruder Prior Information Improving the Barrier Coverage of Sparse Sensor Networks,”
Mobile Computing, IEEE Transactions on
13
(6)
1268 
1282
DOI : 10.1109/TMC.2013.129
Meguerdichian S.
,
Slijepcevic S.
,
Karayan V.
,
Potkonjak M.
“Localized Algorithms in Wireless Adhoc Networks: Location Discovery and Sensor Exposure,”
Proceeding of ACM Mobihoc’01
Long Beach, CA, USA
2001
106 
116
Kumar S.
,
Lai T.
,
Arora A.
“Barrier coverage with wireless sensors,”
in Proc. of Int. Conf. MobiCom
Cologne, Germany
2005
Chen A.
,
Kumar S.
,
Lai T.
“Designing localized algorithms for barrier coverage,”
in Proc. of Int. Conf. MobiCom
Montréal, QC, Canada
2007
Liu B.
,
Dousse O.
,
Wang J.
,
Saipulla A.
“Strong barrier coverage of wireless sensor networks,”
in Proc. of ACM Int. Symp. MobiHoc
Hong Kong, China
2008
Chen A.
,
Lai T.
,
Xuan D.
“Measuring and guaranteeing quality of barriercoverage in wireless sensor networks,”
in Proc. of ACM Int. Symp. MobiHoc
Hong Kong, China
2008
Saipulla A.
,
Westphal C.
,
Liu B.
,
Wang J.
“Barrier coverage of linebased deployed wireless sensor networks,”
in Proc.of IEEE Conf. INFOCOM
Rio de Janeiro, Brazil
2009
Yang G.
,
Qiao D.
“Barrier information coverage with wireless sensors,”
in Proc. of IEEE Conf. INFOCOM
Rio de Janeiro, Brazil
2009
Li J.
,
Chen J.
,
Lai T. H.
“Energyefficient intrusion detection with a barrier of probabilistic sensors,”
in Proc. of IEEE INFOCOM
2012
118 
126
Wang Y.
,
Cao G.
“On FullView Coverage in Camera Sensor Networks,”
in Proc. of IEEE INFOCOM
2011
Wang Y.
,
Cao G.
“Barrier Coverage in Camera Sensor Networks,”
in Proc. of ACM MobiHoc
2011
Ma H.
,
Yang M.
,
Li D.
,
Hong Y.
,
Chen W.
“Minimum Camera Barrier Coverage in Wireless Camera Sensor Networks,”
In Proc. Of IEEE INFOCOM
2012
217 
225
Tao D.
,
Tang S.
,
Zhang H.
,
Mao X.
,
Ma H.
2012
“Strong Barrier Coverage in Directional Sensor Networks,”
Computer Communications
35
(8)
895 
905
DOI : 10.1016/j.comcom.2012.01.022
He S.
,
Chen J.
,
Li X.
,
Shen X.
,
Sun Y.
“Costeffective barrier coverage by mobile sensor networks,”
in Proc. of IEEE INFOCOM
2012
819 
827
Gilbert E.N.
1961
“Random Plane Networks,”
J. SIAM
9
(4)
533 
543
Gupta P.
,
Kumar P. R.
“Critical power for asymptotic connectivity in wireless networks,”
in Proc. of Stochastic Anal., Control, Optim. Appl.
1998
657 
566
Bertin E.
,
Billot J.M.
,
Drouilhet R.
2002
“Continuum Percolation in the Gabriel Graph,”
Advances in Applied Probability
34
(4)
689 
701
DOI : 10.1239/aap/1037990948
Gabriel K.R.
,
Sokal R.R.
1969
“A New Statistical Approach to Geographic Variation Analysis,”
Systematic Zoology
18
(3)
259 
278
DOI : 10.2307/2412323
Booth L.
,
Bruck J.
,
Franceschetti M.
,
Meester R.
2003
“Covering Algorithms, Continuum Percolation and the Geometry ofWireless Networks,”
Annals of Applied Probability
13
(2)
722 
741
DOI : 10.1214/aoap/1050689601
Glauche I.
,
Krause W.
,
Sollacher R.
,
Greiner M.
2003
“Continuum Percolation of Wireless Ad Hoc Communication Networks,”
Physica A
325
577 
600
DOI : 10.1016/S03784371(03)002498
Jiang A.
,
Bruck J.
“Monotone Percolation and the Topology Control of Wireless Networks,”
in Proc. of IEEE INFOCOM ’05
2005
327 
338
Liu B.
,
Towsley D.
“A Study of the Coverage of LargeScale Sensor Networks,”
in Proc. of First IEEE Int’l Conf. Mobile AdHoc and Sensor Systems (MASS ’04)
2004
475 
483
Ammari H.M.
,
Das S.K.
2009
“Critical Density for Coverage and Connectivity in ThreeDimensional Wireless Sensor Networks Using Continuum Percolation,”
Parallel and Distributed Systems, IEEE Transactions on
20
(6)
872 
885
DOI : 10.1109/TPDS.2008.146
Khanjary M.
,
Sabaei M.
,
Meybodi M.R.
2014
“Critical Density for Coverage and Connectivity in TwoDimensional AlignedOrientation Directional Sensor Networks Using Continuum Percolation,”
Sensors Journal, IEEE
14
(8)
2856 
2863
DOI : 10.1109/JSEN.2014.2319451
Meester R.
,
Roy R.
1996
“Continuum Percolation,”
Cambridge University Press
Cambridge, U.K.
Hörster E.
,
Lienhart R.
“Approximating optimal visual sensor placement,”
in Proc. of IEEE Int. Conf. Multimedia Expo
Jul. 2006
1257 
1260
Ram S.
,
Ramakrishnan K. R.
,
Atrey P. K.
,
Singh V. K.
,
Kankanhalli M. S.
“A design methodology for selection and placement of sensors in multimedia surveillance systems,”
in Proc. of 4th ACM Int. Workshop Video Surveill. Sensor Netw.
2006
121 
130