Report

Area Coverage Sensor Deployment and Target Localization in Distributed Sensor Networks Area Coverage 2 Area Coverage Objective 3 Maximize the coverage for a given number of sensors within a wireless sensor networks. Propose a Virtual force algorithm (VFA) Area Coverage Virtual Force Algorithm(VFA) 4 Attractive force Repulsive force Area Coverage Virtual Force Algorithm(VFA) Each sensor behaves as a “source of force” for all other sensors S2 → F12 Attractive force Repulsive force → F13 S3 S1 → F14=0 S4 5 Area Coverage Virtual Force Algorithm(VFA) → Fij: the vector exerted on Si by another sensor Sj Obstacles and areas of preferential coverage also have forces acting on Si → FiA : the total (attractive) force on Si due to preferential coverage areas → FiR : the total (repulsive) force on Si due to obstacles → The total force Fi on Si Fi 6 k F j 1, j i ij FiA FiR Area Coverage Virtual Force Algorithm(VFA) 7 Uses a force-directed approach to improve the coverage after initial random deployment Advantages Negligible computation time Flexibility Area Coverage Movement-Assisted Sensor Deployment Area Coverage Motivation sensor sensing range 9 Area Coverage Deploying more static sensors cannot solve the problem due to wind or obstacles 10 Area Coverage General idea: Detecting coverage hole 11 Move to heal the hole Area Coverage Coverage Hole Detection Only check local Voronoi cell sensing range 12 Area Coverage Coverage hole exists? 13 Calculate the target location (by VEC, VOR or Minimax) Area Coverage The VECtor-Based Algorithm (VEC) Motivated by the attributes of electrical particles Virtual force pushes sensors away from dense area A B C 14 A B C Area Coverage The VORonoi-Based Algorithm (VOR) Move towards the farthest Voronoi vertex Avoid moving oscillation: stop for one round if move backwards M B 15 M B Area Coverage The Minimax Algorithm Move to where the distance to the farthest voronoi vertex is minimized M M B B N 16 N Target Coverage Energy-Efficient Target Coverage in Wireless Sensor Networks Target Coverage Sleep Active Area coverage problem 18 Sensing overall area Minimizing active nodes Maximizing network lifetime Target Coverage Sleep Active Target coverage problem 19 Sensing all targets Minimizing active nodes Maximizing network lifetime Target Target Coverage Disjoint Set Covers Divide sensor nodes into disjoint sets Each set completely monitor all targets One set is active each time until run out of energy Goal: To find the maximum number of disjoint sets This is NP-Complete Disjoint set cover same time interval 20 Non-disjoint set cover different time interval Target Coverage Sensor s1 s2 s3 s4 Target r1 r2 r3 All sensors are active Lifetime = 1 21 s1 r1 s3 s4 r3 r2 s2 Target Coverage Sensor s1 s2 s3 s4 Disjoint sets S1 = {s1, s2} S2 = {s3, s4} Lifetime = 2 22 Target r1 r2 r3 s1 r1 s3 s4 r3 r2 s2 Target Coverage t2 t3 t4 t1 s1 s2 s3 s4 r1 r2 r3 r1 s3 Another Approach: S1 = {s1, s2} with t1 = 0.5 S2 = {s2, s3} with t2 = 0.5 S3 = {s1, s3} with t3 = 0.5 S4 = {s4} with t4 = 1 Lifetime = 2.5 s1 s4 r3 r2 s2 Target Coverage s1 r1 s2 r2 s3 r3 s4 r1 s3 s4 24 Minimum Set element S1 s1 , s2 S2 s1 , s3 S3 s2 , s3 S4 s4 s1 r3 r2 s2 Target Coverage Set active interval = 0.5 choose a available set S1 S2 S3 Minimum Set element S1 s1 , s2 S2 s1 , s3 S3 s2 , s3 S4 s4 S4 S4 remainder life time remainder life time remainder life time remainder life time remainder life time remainder life time s1 1 0.5 0 0 0 0 s2 1 0.5 0.5 0 0 0 s3 1 1 0.5 0 0 0 s4 1 1 1 1 0.5 0 25 This order is not unique, tried all the orders and pick up the order with the maximum life time Target Coverage Maximum Set Covers (MSC) Problem 26 Given: C : set of sensors R : set of targets Goal: Determine a number of set covers S1, …, Sp and t1,…, tp where: Si completely covers R Maximize t1 + … + tp Each sensor is not active more than 1 MSC is NP-Complete Target Coverage Using Linear Programming Approach Given: A set of n sensor nodes: C = {s1, s2, …, sn} A set of m targets: R={r1, r2, …, rm} The relationship between sensors and targets: Ck = {i|sensor si covers target rk} s1 s2 s3 r1 r2 r3 C = {s1, s2, s3}; R = {r1, r2, r3} C1 = {1, 3}; C2 = {1, 2}; C3 = {2, 3} Variables: 27 xij = 1 if si ∈ Sj, otherwise xij = 0 tj ∈[0, 1], represents the time allocated for Sj Target Coverage Maxim ize t1 ... t p p subject to x t ij j j 1 x iC k ij 1 si C 1 rk R, j 1,.., p where xij 0,1 ( xij 1 iff si S j ) 28 maximize network lifetime sensor’s lifetime constraint all targets must be covered Barrier Coverage Strong Barrier Coverage of Wireless Sensor Networks Barrier Coverage USA MEXICO 33 Barrier Coverage How to define a belt region? 34 Parallel curves Region between two parallel curves Barrier Coverage Two special belt region Rectangular: Donut-shaped: 35 Barrier Coverage Crossing paths A crossing path is a path that crosses the complete width of the belt region. Crossing paths 36 Not crossing paths Barrier Coverage Weak barrier coverage Strong barrier coverage 37 Barrier Coverage k-covered A crossing path is said to be k-covered if it intersects the sensing disks of at least k sensors. 3-covered 38 1-covered 0-covered Barrier Coverage k-barrier covered A belt region is k-barrier covered if all crossing paths are kcovered. Not barrier coverage 1-barrier coverage 39 Barrier Coverage Reduced to k-connectivity problem Given a sensor network over a belt region Construct a coverage graph G(V, E) V: sensor nodes, plus two dummy nodes L, R E: edge (u,v) if their sensing disks overlap Region is k-barrier covered if L and R are k-connected in G. L 40 R Barrier Coverage 3-barrier 3-barrier 41 Barrier Coverage Characteristics Improved robustness of the barrier coverage Lower communication overhead and computation costs Strengthened local barrier coverage failure without vertical strip 42 failure with vertical strip Surface Coverage in Wireless Sensor Networks IEEE INFOCOM 2009 Ming-Chen Zhao, Jiayin Lei, Min-You Wu, Yunhuai Liu, Wei Shu Shanghai Jiao Tong Univ., Shanghai 43 Motivation Existing studies on Wireless Sensor Networks (WSNs) focus on 2D ideal plane coverage and 3D full space coverage. The 3D surface of a targeted Field of Interest is complex in many real world applications. Existing studies on coverage do not produce practical results. 44 Motivation In surface coverage, the targeted Field of Interest is a complex surface in 3D space and sensors can be deployed only on the surface. Existing 2D plane coverage is merely a special case of surface coverage. Simulations point out that existing sensor deployment schemes for a 2D plane cannot be directly applied to surface coverage cases. 45 Introduction volcano monitoring 46 Introduction Surface Coverage 47 use triangularization to partition a surface Models Sensor models sensing radius r in 3D Euclid space statically deployed Surface models z = f(x, y) z= 48 c, ax + by + c, if the surface is a plane if the surface is a slant Problem Statement Problems in WSN surface coverage: 1. The number of sensors that are needed to reach a certain expected coverage ratio under stochastic deployment. 49 Problem Statement Problems in WSN surface coverage: 2. The optimal deployment strategy with guaranteed full coverage and the least number of sensors when sensor deployment is pre-determined. 50 Optimum Partition Coverage Problem (OPCP) Convert optimum surface coverage problem to a discrete problem and then relate those results back to the original continuous problem. 51 Optimum Partition Coverage Problem (OPCP) S: P = {SA, SB, SC, SD, SE, SF} h*(Lα)=h(1)∪h(3)∪h(4)∪h(5) 1 6 A B F 5 Lα = {1, 3, 4, 5} 2 C 7 E D 4 |Lα| = 4 3 Lβ = {3, 6, 7} |Lβ| = 3 53 minimum Optimum Partition Coverage Problem (OPCP) Algorithm 1: Greedy algorithm 1 6 A B F 5 C 7 E D 4 54 2 3 Optimum Partition Coverage Problem (OPCP) Greedy algorithm Time complexity 55 selects a position that can increase the covered region the most O(|P|2) log (|P|) approximation algorithm Trap Coverage 56 Motivation Tracking of movements such as that of people, animals, vehicles, or of phenomena such as ﬁre can be achieved by deploying a wireless sensor network. Real-life deployments, will be at large scale and achieving this scale will become prohibitively expensive if we require every point in the region to be covered (i.e., full coverage), as has been the case in prototype deployments. 57 Motivation Trap Coverage scales well with large deployment regions. A sensor network providing Trap Coverage guarantees any moving object can move at most a displacement before it is guaranteed to be detected by the network. Trap Coverage generalizes the real model of full coverage by allowing holes of a given maximum diameter. 58 Trap Coverage: Allowing Coverage Holes of Bounded Diameter in Wireless Sensor Networks Paul Balister, Santosh Kumar, Zizhan Zheng, and Prasun Sinha IEEE INFOCOM 2009 59 Introduction Real-life deployments, will be at large scale and achieving this scale will become prohibitively expensive if we require every point in the region to be covered (i.e., full coverage), as has been the case in prototype deployments. 60 Introduction Trap Coverage Guarantees that any moving object or phenomena can move at most a (known) displacement before it is guaranteed to be detected by the network. Hole Diameter 61 Introduction Trap Coverage 62 d is the diameter of the largest hole Full Coverage: d is set to 0 Introduction Define a Coverage Hole in a target region of deployment A to be a connected component1 of the set of uncovered points of A. Trap Coverage with diameter d to A if the diameter of any Coverage Hole in A is at most d. 63 Estimating the Density for Random Deployments Example of Poisson deployment 64 holes of larger diameters are typically long and thin Computing the Trap Coverage Diameter Discovering Hole Boundary Diameter Computation Coping with Sensing Region Uncertainty 65 Computing the Trap Coverage Diameter Discovering Hole Boundary Boundary node S1 S2 Boundary node 66 Computing the Trap Coverage Diameter Discovering Hole Boundary Hole Boundary: hole loop–outermost curves diamH 67 Computing the Trap Coverage Diameter Diameter Computation Crossing: intersection point of perimeters diamXH 68 Computing the Trap Coverage Diameter Diameter Computation Crossing: intersection point of perimeters diamXH +2D 69 Computing the Trap Coverage Diameter Diameter Computation H : denote a hole loop XH : denote the set of crossings on the loop Crossing: an intersection point of either two sensing perimeters D : the maximum diameter of all sensing regions Lemma 5.1: diamXH ≤ diamH ≤ diamXH +2D 70 Adaptive k-Coverage Contour Evaluation and Deployment in Wireless Sensor Networks 71 This paper, considers two sub-problems: k-coverage contour evaluation and k-coverage rate deployment. The former aims to evaluate the coverage level of any location inside a monitored area, while the latter aims to determine the locations of a given set of sensors to guarantee the maximum increment of k-coverage rate when they are deployed into the area. k-Fully covered and k-partially covered An area A’ is called to be fully covered by a sensor s if each point in A’ is covered by s. A’ is called to be partially covered by s if some points in A’ are covered by s and some are not. If A’ is not fully covered or partially covered by any sensor, then A’ is uncovered. For simplicity, an area fully covered by exactly k distinct sensors is called to be exactly k-fully and an area partially covered by exactly k distinct sensors is called to be exactly k-partially covered. 72 g4 g2 s2 g3 g1 g5 s3 s1 Zero-Partially Covered Non-Zero Partially Covered An example of fully covered, partially covered, and uncovered grids. Each grid has side length r/2. 73 k-COVERAGE CONTOUR EVALUATION SCHEME (K-CCE) When a grid g is partially covered by s, evaluating what percentage of g is covered by s requires complex computation. The matter goes worse as grids are partially covered by more than one sensor. Instead of applying complex computation, we can divide the grid into sub-grids to obtain more precise coverage information. 74 s2 a b c d Zero - Partially Covered Grid s3 s1 2-Fully Covered Grid Uncertain Grid An example of each grid with side length r/4. 75 K-CCE Besides, for k-coverage contour evaluation, grids which are fully covered by at least k sensors do not need any more division. Hence, division shall be performed on those grids which are partially covered by at least one sensor and fully covered by less than k distinct sensors. 76 s2 Zero - Partially Covered Grid s3 s1 2-Fully Covered Grid Uncertain Grid An example of non-uniform-sized grids. 77 Maximum Tolerable Evaluation Error (MTEE) Maximum Evaluation Error (MEE) is the ratio of uncertainly covered area relative to whole monitored area, i.e., MEE = ∑g U |g|/|A|, where U denotes the set of uncertain grids, and |g| and |A| denote the area size of g and A, respectively. Maximum Tolerable Evaluation Error (MTEE) is the maximum evaluation error that is permitted for a target application. 78 An example of grid division. 79 k-COVERAGE RATE DEPLOYMENT SCHEME (K-CRD) The basic idea of this scheme is to deploy sensors to locations that increase the total area of k-fully covered grids most economically Given a grid g, we define a deployment region with respect to g, denoted by DR(g), as an area within which a sensor is deployed can fully cover g. 80 The original deployment region with respect to grid g. The dashed circle is a simplified deployment region with respect to grid g. 81 Two Heuristics We employ the following two heuristics to deploy the sensors economically (in terms of the number of sensors used). First, consider λ = {max i | there exists some grid g that is i-fully covered and i < k}. It is clear that deploying sensors to fully cover the λ-fully covered grids improves the kcoverage rate Second, define a candidate grid to be a λ -fully covered grid. Among all candidate grids, deploying sensors to fully cover the ones with the largest area is an even more economic way. 82 Intersection of deployment regions. (a) Intersection of DR(g1) and DR(g2); (b) Points Pb Pc, and Pe are best_fits. 83 k-CRD1 Define grid-weight of grid g, GW(g), to be |g| if g is a candidate grid and 0 otherwise. The main idea is based on the observation that there is a high possibility that a best_fit is a fit with respect to a higher-grid-weight grid. 84 The first three candidate grids are at left-up, right-up, and left-down corner. 85 k-CRD1 Clearly, fits with respect to grids at left-up, right-up, and left-down corner are in I1, I2, and I3, respectively. Besides, fit with respect to the grid at left-down corner has the highest weight. So, we deploy a sensor in fit with respect to grid at left-down corner. 86 k-CRD2 In order to further reduce the computation cost, the main motivation of scheme k-CRD2 is to avoid high computation cost of determining fits. In k-CRD2, only highest-grid-weight candidate grids are considered. Let C1 denote the set of highest-grid-weight candidate grids. Randomly choose a candidate grid g from C1. Deploy k sensors at a point p satisfying that 87 (1) p is located in DR(g); and (2) maximal number of grids in C1 can be fully covered. Randomly choose a grid from C1, say g6. Then deploy (4-3) sensor at point u because maximum number of grids (i.e., g5 and g6) in C1 can be fully covered. 88 An example of 4-CRD2. C1={g1, g2, … , g8 }.