05-10-2016, 10:44 AM
1457794366-Sensorcoverageinwirelesssensornetworks.docx (Size: 78.51 KB / Downloads: 4)
Abstract—In order to approach the quality of sensing i.e.,sensor coverage problem,one needs to models of the sensors,the phenomena ,and the environment in which the sensors interact with the phenomena.Furthermore in collaborate settings where multiple distributed sensors participate in the sensing task,the method and computation algorithms used also play in significant roles in the observability of phenomena and thus must also be modelled. Coverage problem is a fundamental issue in wire-less ad hoc and sensor networks.A method based on algebraic topology has been proposed to achieve coverage verification using only connectivity information. On using only connectivity information. In this work, we make the first attempt towards establishing a graph theoretical framework for connectivity-based coverage with configurable coverage granularity. We propose a novel coverage criterion and scheduling method based on cycle partition. Our method is able to construct a sparse coverage set in a distributed manner, using purely connectivity information. Compared with existing methods, our design has a particular advantage, which permits us to configure or adjust the quality of coverage by adequately exploiting diverse sensing ranges and specific requirements of different applications. We formally prove the correctness and evaluate the effectiveness of our approach through extensive simulations and comparisons with the state-of-the-art approaches.
Introduction:
Embedded systems have long been by far the most dominant components in digital electronics in terms of quantity, market share, growth, and deployment.More recently, advances in wireless communication technologies coupled with thecontinuing drop in the cost of silicon, miniaturization, and emerging technologies such as MEMS-based sensors and actuators are enabling the development ofcompletely new classes of large embedded systems that are networked and distributed. Sensor networks are one example of such networked embedded systems where each device is equipped with one or more sensors (potentially of several different types), with the primary goal of observing physical phenomena in the environment. Currently, proposed applications of sensor networks range from environmental monitoring for seismic, weather, natural disaster, contaminant, and habitats, to battlefield surveillance, home and office automation, and even monitoring of other planets such as Mars. In the last two decades, the sustained high pace of technological advances paved the way for the exponential growth of the Internet. We can trace the development of two implementation technologies as prime enablers of this growth:The first was the dramatic reduction in the cost of disks, which meant the rise in availability of massive long-term storage. The second was the huge reduction in the cost of optical communication and its simultaneous capacity increase. Once deployed, sensor nodes begin to observe the environment, communicate with their neighbors (nodes within communication range), collaboratively process
raw sensory inputs, and perform a wide variety of tasks specified by the applica- tions at hand. The key factor that makes wireless sensor networks so unique and promising both in terms of research and economic potentials, is their ability to be deployed in very large scales without the complex pre-planning, architectural engineering, and physical barriers that wired systems have faced in the past. The
term “ad hoc” generally signifies such a deployment scenario where no structure, hierarchy, or network topology is defined a priori. In addition to being ad hoc, the wireless nature of the communication subsystems that rely on radio frequency(RF), infrared (IR), or other technologies, enable usage and deployment scenariosthat were never before possible.
Related work:
The coverage problem, as one of the most fundamental issues, has recently attracted significant research attention in ad hoc and sensor networks. We classify the existing coverage methods into two categories: the location-based and location-free, according to whether dependent on lo- cation information. Location-free methods further can be classified into two types: the range-based and connectivity- based. We here pay more attention on connectivity-based methods as our work is in this category. We first simply introduce the main ideas of connectivity- based method presented by Ghrist et al. [8] [9], and analyze its advantages and shortages. Their method models the network as a 2-simplicial complex. In algebraic topology, simplicial complexes are well-defined blocks for building topological spaces. A k-simplex σ is a set of k +1 size. A simplicial complex K is a collection of simplices that satisfies the following conditions: (1) Any face of a simplex from K is also in K; (2) The intersection of any two simplices σ1 , σ2 ∈ K is a face of both σ1 and σ2 . In this coverage problem, we can simply consider the 0, 1, and 2-simpliecs to be vertices, edges, and triangles in the connectivity graph, respectively. Ghrist et al.’s method mainly explores the observation that if the relationship between sensing range Rs and communication range Rc satisfies a specific condition . Rs ≥ 1/3Rc ,a connectivity triangle guarentees a coverage region without holes. Further, a full coverage can be verified
by the trivial first (relative) homology group of this 2- simplicial complex. A connected simplicial complex having a trivial homology group means that each cycle in the graph can be continuously transformed into a point by moving along faces (edges or triangles) of the simplicial complex without leaving the space.
Problem formulation:
In this section, we present the basic network configura- tion and assumptions, and formulate a connectivity-based coverage as a confine coverage.
A. Network Models
We consider a collection of nodes deployed over a plane region. Each node can sense specified events in its sensing range Rs . The union of sensing region of all nodes is referred as the network sensing area, Anet , and it covers the target region that needs to be monitored by the network, referred to as the target area, Atar , which is typically and significantly larger than the sensing range of a single node. A coverage hole is a connected planar region in the target area that cannot be uncovered by sensing nodes. Each node is only capable of communicating with adjacent nodes in its proximity, within the maximum communication range Rc . Note that we do not force the communication model to be the unit disk graph. Two nodes can or can not communicate with each other if their distance is within the maximum communication range Rc . We assume that the coordinates of nodes are unavailable, in the sense that nodes can determine neither distances nor orientations of other nodes. We use G to denote the connectivity graph of a network communication.
We assume that there is a periphery band of width at least Rc between the boundary of the network sensing area Anet and the edge of the target area Atar . We refer boundary nodes as those that are located in the periphery band and the others as internal nodes. Although the nodes are not aware of their locations, each node can be assumed to know whether it is a boundary or an internal node by using the mechanisms, like location-free boundary recognition [13] [14], or many other ways discussed in [7]. Note that this is a conventional assumption adopted by almost all existing connectivity- based methods [9] [10], and range-based methods [7] [4]. Note that this work indeed does not need to know the boundary cycles explicitly, and only requires that the graph induced by nodes in one boundary is connected and contain a boundary cycle implicitly. By default, the boundaries in this work are found by a modified fine-grained boundary algorithm [13].
Confine Coverage:
Coverage problems have been formulated in different manners in varied applications, including, blanket, point, and barrier coverage, etc. The goal of blanket (or point) coverage focuses on covering all points (or some given points) in an area, while barrier coverage seeks to minimize the probability of undetected network penetrations. Blanket coverage is mainly required in those monitoring applications that need information of all points in the target area or demand immediate response to detected events. Energy efficiency is widely accepted as one of the most critical issues in wireless ad hoc and sensor networks. Always-on full blanket coverage will exhaust network energy rapidly, which is considered to be too expensive in long-duration large-scale applications. Thus, as a practical relaxation of blanket coverage, partial coverage is explored to balance event detection quality and power conservation by many applications, such as, movement target surveillance [15], rare-event detection [16], delay of intrusion detection [17], and trap coverage [18] etc. For example, in the applications like surveillance and target tracking, the metric of quality surveillance is based on the maximum distance that a moving target can travel in the network along a straight line while escaping from detection. In the applications of environment monitoring (such as chemistry pollution of air, water, soil, etc.), the monitoring quality often is measured by the maximum diffusion area of events before detection. Those applications do not pursue zero response time or demand information of all points in the sensing field, and they are tolerant of event detection with moderating delay or small probability of missing to improve the network lifetime. Partial coverage can be regarded as a generalized blanket coverage with permitting adjustable quality of coverage. The quality of coverage (QoC) of partial coverage is measured in different definitions, such as worst-case detection delay and diffusion area of events mentioned previously. This work adapts a universal metric for QoC by the diameter of cov- erage hole. A diameter of a coverage hole is defined as the diameter of the minimum circle circumscribing the coverage hole, which is delicately different from the hole diameter in trap coverage [18]. Clearly, the diameter of a coverage hole sufficiently bounds the maximum straight-line distance of escaping detection in the coverage hole, and also provides an diameter to calculate the upper bound of hole area. The worst-case quality of coverage is defined as the maximum diameter of coverage holes in the network. Blanket coverage can be regarded as a special partial coverage with zero worst-case QoC. Similar to blanket coverage, most existing partial coverage schemes also require location information to schedule nodes to guarantee worst-case QoC [15] [19]. Some schemes focus on deriving the asymptotic node degree of randomly deployed (Poisson distribution) large-scale net- works to probabilistically guarantee the average-case [17] or worst-case QoC [18]. To our best knowledge, there are no current works that are able to achieve determinate partial coverage with guaranteed worst-case QoC in a location-free
manner. In this work, we focus on determinately achieving gen- eralized blanket coverage from full blanket coverage to partial coverage with guaranteed worst-case QoC, using merely connectivity information. We formulate this problem as confine coverage in Definition 1. Apparently, we cannot accurately know the diameter of one coverage hole without node location information. To circumvent this dependence on location measurements, we define the confine coverage based on communication models and their valid embeddings. Given a communication graph, the legitimate location of nodes in the Euclidean plane meeting the communication model is called as a valid embedding or realization of the networks, like UDG or quasi-UDG embeddings [20]. Given all communication links bounded in the distance Rc , we can establish the sufficient condition to bound the hole size for all possible valid network realizations, which enables us to confine the coverage hole based on the connectivity metric Definition 1: (Confine Coverage) Given a subgraph G of connectivity graph G and a positive integer τ , if for any one valid embedding of G, each point in the target area is
surrounded by at least one k-hop cycle in G with k ≤ τ ,
we say G achieves a τ -confine coverage on the target area.
The objective of this work is to select a node subset from the network G to determinately achieve expected confine coverage requirements with using only connectivity information.
Configurability of Coverage Granularity:
, the coverage granularity of confine coverage lies on two parameters: size of cycles and sensing ratio. The sensing ratio γ = Rc /Rs between communication range Rc and sensing range Rs has been one important factor involved in coverage problems.
DISTRIBUTED COVERAGE ALGORITHM
In the previous section, we establish the cycle-partition criterion for confine coverage. The cycle-partition merely provides an emplicit existence result for determining confine coverage. We will need to address two problems to achieve coverage scheduling. First, we need to design an implementable criterion of confine coverage, that is, a computational procedure to decide whether a cycle is τ - partitionable. Second, if a network not only passes the testing of coverage criterion, but also achieves a much over- provisioned confine coverage, we naturally wonder which nodes can be deleted safely without reducing the coverage quality to prolong the network lifetime. In this section, we present a deterministic, polynomial-time and distributed algorithm to achieve cycle-partition criterion and schedule a sparse coverage set using only connectivity information.
Computing Sparse Coverage Set: We next present the distributed scheduling algorithm based on void preserving transformation to discover a sparse coverage set. We formalize this problem as finding a non- redundant coverage set, as described in Definition 6.
Definition 6: (Non-Redundant Coverage Set) A node set
V in G is a non-redundant for τ -confine coverage, if boundary cycles CB of G is τ -partitionable in G[V ], and for any proper subset V ⊂ V , CB fails to be τ -partitionable
in G[V ].
Ideally, we desire that the designed algorithm can be performed in a distributed manner and uses only local connectivity. We next present the details of this scheduling algorithm, which can find a sparse coverage set to achieve
Algorithm:
Find Min and Max sizes of irreducible cycle
Input : A gragh H
Output: Minimum and maximum sizes of irreducible cycles in H :
min and max .
1: C = ∅.
2: for each v ∈ V (H ) do
3: Construct one shortest path tree of H rooted at v, Tv .
4: for each e = (x, y) ∈ E(H )\E(Tv ) do
5: if Least common ancestor of x and y in Tv is root v
then
6: Construct cycle C (v, x, y) and C = C {C (v, x, y)}.
7: Order all cycles in C by non-decreasing length.
8: B = ∅.
9: ν = |E(H )|− |V (H )| + 1.
10: while |B| < ν do
11: Select the shortest cycle C ∈ C\B.
12: Perform Gaussian elimination on C B.
13: if C is linear independent with B then
14: B = C B.
15: Output min = |B | min and max = |B | max .
a confine coverage by using only local connectivity. More- over, our algorithm can guarantee to find a non-redundant coverage set when the connectivity graph follows some graph properties. Similarly, we first consider the simply- connected target region, and then dispose the cases of multiply-connected target region. This procedure conducts a maximal vertex deletion on original connectivity graph G by void preserving transformation. Each internal node gathers its local connectivity and determines whether itself can be deleted. The procedure of vertex deletion terminates until no vertex in G can be deleted, and it outputs the reduced coverage graph Gvd .
The distributed implementation of this procedure is per- formed as follows. Each internal node v only needs to collect the connectivity Γk (v) among its k-hop neighbors, k = τ /2 . (Note that nodes in the boundary do not participate in this procedure and they keep unchanged.) Then node v can locally decide whether it can be deleted through τ -void preserving transformation. To parallelize the deletion procedure, these deletion operations can iteratively
run in rounds. Two nodes that are of m = τ /2 + 1 hops away in the graph can perform the redundancy testing independently. In each round, all nodes that can be locally deleted first form a set of candidate nodes for deletion, then a m-hop maximal independent set (MIS) among these candidate nodes is randomly selected from the networks in a distributed manner. As a result, these MIS nodes can perform the deletion operation simultaneously. This procedure runs until that no nodes can be deleted.
Theorem 5: Given a τ -partitionable boundary Couter in G, Couter is still τ -partitionable in the graph after maximal vertex deletions.
Theorem 6: The found coverage set is non-redundant for τ -confine coverage by our algorithm if the maximum irreducible cycle in G is bounded in τ .
Conclusion:
As a crucial issue in wireless ad hoc and sensor networks, coverage problem is previously addressed either requiring accurate location information, range measurements, or us- ing only connectivity information but forcing centralized computation and critical restriction on sensing and com- munication models. This work presents a practical graph theoretical framework to connectivity-based coverage prob- lem in wireless ad hoc and sensor networks. We take the first attempt towards designing a distributed coverage algorithm to achieve configurable coverage requirements with using merely connectivity information. We formally prove the correctness of this design and evaluate it through extensive simulations and comparisons with the state-of-the- art approach.