Advanced
Percolation Theory-Based Exposure-Path Prevention for 3D-Wireless Sensor Networks Coverage
Percolation Theory-Based Exposure-Path Prevention for 3D-Wireless Sensor Networks Coverage
KSII Transactions on Internet and Information Systems (TIIS). 2015. Jan, 9(1): 126-148
Copyright © 2015, Korean Society For Internet Information
  • Received : July 18, 2014
  • Accepted : November 30, 2014
  • Published : January 31, 2015
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
Xiaoshuang Liu
Guixia Kang
Ningbo Zhang

Abstract
Different from the existing works on coverage problems in wireless sensor networks (WSNs), this paper considers the exposure-path 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 percolation-based scheme is proposed to put the exposure-path 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.
Keywords
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 exposure-path 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 artificial-potential approach [4] that designed the minimum-exposure 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 exposure-path 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 sub-units of some arbitrary system, there exists a percolation threshold pt . When p pt , there is no exposure path from one side of the system to the other. There are some researches that lie in the exposure-path problem and percolation theory, and we will introduce the related works in Section 2.
The existing works [2 - 7 , 10] mainly focus on the exposure-path 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 exposure-path 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 exposure-path problem into a 3D uniform lattice and propose a bond percolation-based 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 exposure-path prevention in 3D WSNs. Section 4 highlights the bond-percolation theory to derive and analyze the optimal critical density for exposure-path problem. Moreover, we discuss the mutual dependence among edges of the proposed bond percolation-based 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 exposure-path 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 exposure-path problem belongs to the barrier coverage.
PPT Slide
Lager Image
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 k-barrier 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 sleep-wakeup algorithms to provide near-optimal 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 line-based deployment rather than the Poisson distribution model. They also derived a tight lower-bound 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 full-view 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 cost-effective 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 continuum-percolation theory.
In [31] , for both Poisson and hard-core 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 large-scale 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 concentric-sphere model to address coverage and connectivity in an integrated way. Khanjary et al . [38] introduced aligned-orientation 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 percolation-based schemes apply the common continuum-percolation 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 percolation-based scheme through mapping the exposure path-prevention 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 exposure-path prevention problem is formulated by the continuum-percolation 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 sub-region 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
PPT Slide
Lager Image
- 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 : ( xs , ys , zs ) denotes a node position in space rectangular coordinate o−xyz , a targeted point t : ( xt , yt , zt ) is said to be covered by s when the Euclidean distance | st | =
PPT Slide
Lager Image
is not larger than r .
PPT Slide
Lager Image
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 ,
PPT Slide
Lager Image
, α ), where
PPT Slide
Lager Image
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
PPT Slide
Lager Image
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).
PPT Slide
Lager Image
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 exposure-path 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 exposure-path 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 ,..., mn }, forming a
PPT Slide
Lager Image
lattice as shown in Fig. 4 .
PPT Slide
Lager Image
is used to approximately substitute for
PPT Slide
Lager Image
for the sake of simplicity, which doesn’t affect our final results. The edge between vertex mi and mj is denoted as ei,j , where i , j ∈ [1, n ]. Thus, the edge length of the neighboring vertexes is μ =
PPT Slide
Lager Image
( n vertexes don’t include the ones which lie on the edges of the cube). The following definitions identify the relationship between ei,j and the lower and upper bounds of λC .
PPT Slide
Lager Image
The unit cube region with a virtual lattice.
Definition 2: For edge ei,j , we define
PPT Slide
Lager Image
Then, if L ( ei,j ) = 1, ei,j is defined as L-closed edge; if L ( ei,j ) = 0, ei,j is called as L-open edge.
PPT Slide
Lager Image
Thus, if U ( ei,j ) = 1, ei,j is named as U-closed edge; if U ( ei,j ) = 0, ei,j is denoted as U-open edge.
Definition 3: Let Z 3 be the 3D lattice with vertex set M , edge set E and | M | = n . If ei,j between arbitrary two neighboring is L-closed/L-open, Z 3 is said to be an L-coverage lattice; If it is U-closed or U-open, Z 3 is called a U-coverage 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 L-open/U-open, S is named the L-open/U-open path; if all the edges are L-closed/U-closed, S is called the L-closed/U-closed path.
With the above definitions, we derive that: 1) if edge ei,j is the U-closed edge, then it must be the L-closed edge in terms of coverage; 2) the upper bound λu of the critical density λC could be derived by U-coverage lattice, and the lower bound λl by L-coverage 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 pt ∈ [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 > pt , 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 < pt . To ease presentation, we define PL = p { L ( ei,j ) = 1} , PU = p { U ( ei,j ) = 1} ; and λl = sup{ λ : PL pt }, λu = inf{ λ : PU pt }. Then, we have p {the exposure pathexists} > 0 if PL < pt , and p {the exposure pathexists } = 0 if PU > pt .
- 4.1. Critical Density λC
- 4.1.1. λCof Omnidirectional Sensor Nodes
As shown in Fig. 5 (a), sn is one arbitrary point on edge ei,j of the L-coverage lattice, and we define an operator ‘∪’ : Ai Aj ͸
PPT Slide
Lager Image
An in this paper, where An is the sphere centered at sn with radius r . Then, Ai Aj is a set containing all the coverage spheres centered at the points of ei,j .
PPT Slide
Lager Image
Covered region division of the edge ei,j.
Lemma 1: No sensor node in Ai Aj is a sufficient and necessary condition of all points on ei,j being not covered.
Proof: Based on the definition of Ai Aj , it contains the total coverage space of all points on ei,j . Therefore, it is clear that if there is no sensor nodes in Ai Aj , all points on ei,j aren’t covered by any sensor nodes. The reverse is also true.
Next, we exploit ei,j on y -axis as an example and draw the following conclusion. mi and mj are the two endpoints of edge ei,j .
Theorem 1: In 3D omnidirectional sensor networks, we have
PPT Slide
Lager Image
Proof: Following are three steps to prove the theorem.
1) From (1), we have p { N ( Ai Aj ) = 0} = exp(- λ Ai Aj ║) = exp(- λ
PPT Slide
Lager Image
. Then, PL = 1 - p { L ( ei,j ) = 0} = 1 - exp(- λ
PPT Slide
Lager Image
.
Consequently, PL increases monotonously as λ increases. Since λl = sup{ λ : PL pt }, 1 - exp(- λl
PPT Slide
Lager Image
= pt . Therefore, we can get λl in (4).
2) Based on the above analysis, the probability of all points on ei,j being covered is difficult to derive the explicit expression. As a result, we need to find an approximation of PU . We denote Po as the probability that all points on ei,j are covered by one sensor node. Since PU is the probability that all points on ei,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 ei,j if and only if some sensor node exists in
PPT Slide
Lager Image
. From (1),
PPT Slide
Lager Image
Let A = ║
PPT Slide
Lager Image
║. According to Fig. 5 (a), we can obtain
PPT Slide
Lager Image
where an arbitrary point in
PPT Slide
Lager Image
is ( x ', y ', z ') , R : ( x ') 2 + ( y ') 2 =
PPT Slide
Lager Image
, and = dx ' dy '. It is easy to obtain A =
PPT Slide
Lager Image
.
As a consequence, we choose Po as the approximation of PU . Let λu = inf{ λ : Po pt }. Then we can get λu in (4).
3) Equation (3) is equal to
PPT Slide
Lager Image
If PL < pt , then p { d ( W ) = ∞)} > 0. It is easy to know that λl < λ ' C . From (6), if 1-exp(− λA ) > pt , then PU > pt . In consequence, we can derive that if 1-exp(− λA ) > pt , then p { d ( C ) = ∞)} > 0. According to the definition of λC , we have
PPT Slide
Lager Image
. 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 ( xf , yf , zf ) in Ai Aj . The sphere centered at F with radius r intersects y -axis at F 1 (0, yf -
PPT Slide
Lager Image
, 0) and F 2 (0, yf +
PPT Slide
Lager Image
, 0), using ei,j on y -axis as an example in Fig. 6 (a)-(d). For simplicity, let f 1 = yf -
PPT Slide
Lager Image
, f 2 = yf +
PPT Slide
Lager Image
, and
PPT Slide
Lager Image
be the angle between vector
PPT Slide
Lager Image
and
PPT Slide
Lager Image
. 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 .
PPT Slide
Lager Image
The relative positions of F1, F2, mi and mj.
Theorem 2: In 3D directional sensor networks, we have
PPT Slide
Lager Image
where = dxdydz ,
PPT Slide
Lager Image
Proof: Three steps are needed to verify this theorem.
1) We assume the probability PN that all points on edge ei,j are not covered by a directional sensor node ( F , r ,
PPT Slide
Lager Image
, α ). mi and mj are the two endpoints of edge ei,j . According to the different positions of F 1 , F 2 relative to mi and mj , 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
PPT Slide
Lager Image
in Fig. 6 (a), the node can’t cover any point on ei,j if and only if the angle θ is smaller than the angle of
PPT Slide
Lager Image
minus
PPT Slide
Lager Image
, and is larger than the angle of
PPT Slide
Lager Image
plus
PPT Slide
Lager Image
. θ ͸[0,2 π ]. Therefore,
PPT Slide
Lager Image
Analogously, we have the following conclusions.
2. In Fig. 6 (b), if
PPT Slide
Lager Image
, thus,
PPT Slide
Lager Image
3. In Fig. 6 (c), if
PPT Slide
Lager Image
, then,
PPT Slide
Lager Image
4. In Fig. 6 (d), if
PPT Slide
Lager Image
, hence,
PPT Slide
Lager Image
With the calculus theory, the region Ai Aj is divided into u small enough regions, R 1 , R 2 , …, Ru . The circular cone ψ is divided into g small sectors, ϖ 1 , ϖ 2 , …, ϖg . When u → ∞ and g → ∞, the differential dv = dxdydz of volume equal to ║ Rq ║, 1 ≤ q u . Let Pq be the probability that no sensor node cover ei,j in Rq . Then, from (1) we have
PPT Slide
Lager Image
As u → ∞ and g → ∞,
PPT Slide
Lager Image
Based on (9)-(12), PL increases monotonously with the increase of λ . So, based on the Section 4, we solve
PPT Slide
Lager Image
= pt to get λl .
2) Fig. 5 indicates that all points on ei,j are covered by one sensor node, if and only if the two conditions are satisfied: a. the sensor node locates in
PPT Slide
Lager Image
. Po denotes the probability that all points on ei,j are covered by one sensor node. We consider the probability P ' N that the directional sensor node in
PPT Slide
Lager Image
can’t cover all points on ei,j . It is easy to see that P ' N = 1 when
PPT Slide
Lager Image
, if not, P ' N =
PPT Slide
Lager Image
. Similar to 1), we divide the region
PPT Slide
Lager Image
into u small enough regions whose volume is roughly equal to . From (13)-(14), we have
PPT Slide
Lager Image
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 PN can generate the different bounds. It is obvious that the probabilities of all edges ei,j being open or closed are independent in the bond percolation [2] . However, in this paper, PL ( PU ) 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.,
PPT Slide
Lager Image
where PBC ( b , c ) = p { L ( e 1,2 ) = b , L ( e 2,3 ) = c } , PB ( b ) = p { L ( e 1,2 ) = b } and PC ( 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) = 1-exp(-λl(+πr2μ)).
PPT Slide
Lager Image
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.
PPT Slide
Lager Image
Comparison between I(L(e1,2), L(e2,3)) and I(U(e1,2),U(e2,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 α =
PPT Slide
Lager Image
, 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.
PPT Slide
Lager Image
Comparison between I(L(e1,2), L(e2,3)) and I(U(e1,2),U(e2,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 L-coverage lattice and U-coverage lattice, respectively.
- 5.1. Omnidirectional Sensor Networks
Let r = 10 and pt = 0.5. The number of sensor nodes NV 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 PN . Three different PN corresponding to the continuum percolation, the L-coverage lattice, and the U-coverage 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 Pc = p { ei,j is closed }. As λ increases, Pc increases. According to Definition 2-4 , we get the theoretical values PL and Po which are close to the simulation values PL ' and Po ', respectively. Clearly, PL and PL ' are larger than Po and Po '. Furthermore, we get the value of PU ' by simulation which is slightly larger than Po ' and less than PL '.
PPT Slide
Lager Image
Relationship between λ and Pc.
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 .
PPT Slide
Lager Image
Relationship between PN 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 Multi-Hop Networks) into our proposed 3D omnidirectional network model. Then, we define our proposed scheme as PTEP (Percolation Theory-Based Exposure-Path 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.
PPT Slide
Lager Image
Comparision of λ between PTEP and CDMN with r = 10 and μ = 2.
- 5.2. Directional Sensor Networks
Let r = 10 and α =
PPT Slide
Lager Image
. In the same way, we set that the number of sensor nodes NV 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 ,
PPT Slide
Lager Image
, α ) randomly generated.
In Fig. 12 , it shows the relationship between λ and Pc = p { ei,j is closed }. Pc increases as λ increases. According to (14)-(15) and simulation results, we get the analytical values PL , Po and the simulation values PL ', Po '. From Fig. 12 , PL basically is equal to PL ', and Po is less than Po ' by 1%. Obviously, PL and PL ' are larger than Po and Po ', approximately 0.18. Moreover, the value of PU ' is obtained by simulation which is slightly bigger than Po '.
PPT Slide
Lager Image
Relationship between λ and Pc.
We substitute r = 10 and α =
PPT Slide
Lager Image
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 .
PPT Slide
Lager Image
Relationship between PN and λ with different α.
Similarly, we do the experiments with different r and α . Fig. 13 (b)-(c) show the relationship between PN and λ . In the three figures, P N,C , P N,L and P N,U also increase as λ increases. When r = 10 and α =
PPT Slide
Lager Image
, 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 α =
PPT Slide
Lager Image
, 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 α =
PPT Slide
Lager Image
, 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 3D-network deployment. Conversely, due to the tighter lower and upper bounds of PTEP, it could be implemented to address the exposure-path prevention problem in 3D WSNs.
PPT Slide
Lager Image
Comparision of λ between PTEP and CDMN with r = 10 and α = .
6. Conclusion
In this paper, the exposure-path 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 percolation-based 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.
References
Atzori L. , Iera A. , Morabito G. 2010 “The Internet of Things: A survey,” Comput. Netw. 54 (15) 2787 - 2805    DOI : 10.1016/j.comnet.2010.05.010
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 minimum-exposure 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 (S0305-0041) 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 Springer-Verlag, New York, NY, USA
Liu Liang , Zhang Xi , Ma Huadong 2013 “Percolation Theory-Based Exposure-Path 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 multi-hop 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 “Energy-Efficient 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 20-24 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 Ad-hoc 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 barrier-coverage 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 line-based 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. “Energy-efficient intrusion detection with a barrier of probabilistic sensors,” in Proc. of IEEE INFOCOM 2012 118 - 126
Wang Y. , Cao G. “On Full-View 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. “Cost-effective 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
Penrose M. D. 1997 “The longest edge of the random minimal spanning tree,” Anna. Probab. 7 (2) 340 - 361    DOI : 10.1214/aoap/1034625335
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/S0378-4371(03)00249-8
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 Large-Scale Sensor Networks,” in Proc. of First IEEE Int’l Conf. Mobile Ad-Hoc and Sensor Systems (MASS ’04) 2004 475 - 483
Ammari H.M. , Das S.K. 2009 “Critical Density for Coverage and Connectivity in Three-Dimensional 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 Two-Dimensional Aligned-Orientation 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.
Ma H. , Liu Y. 2007 “Some problems of directional sensor networks,” Int. J. Sensor Netw. 2 (2) 44 - 52    DOI : 10.1504/IJSNET.2007.012981
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