DISTRIBUTED SYS & SENSORS
DISTRIBUTED SYS & SENSORS ECSE 6962
Popular in Course
Popular in ELECTRICAL AND COMPUTER ENGINEERING
This 43 page Class Notes was uploaded by Miss Damien Crooks on Monday October 19, 2015. The Class Notes belongs to ECSE 6962 at Rensselaer Polytechnic Institute taught by Staff in Fall. Since its upload, it has received 10 views. For similar materials see /class/224777/ecse-6962-rensselaer-polytechnic-institute in ELECTRICAL AND COMPUTER ENGINEERING at Rensselaer Polytechnic Institute.
Reviews for DISTRIBUTED SYS & SENSORS
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 10/19/15
verage in Sensor Networks Xiang Luo ECSE 6962 39 139 Coverage problems I Definition the measurement of quality of service surveillance that can be provided by a particular sensor network 39 1 Coverage problems can be classified in three types I Area coverage the main objective is to cover an area I Point coverage the objective is to cover a set of targets I Detectability an objective to determine the maximal supportbreach paths that traverse a sensor field 39 139 Area coverage includes three viewpoints I Statistical coverage of largescale sensor networks I Deterministic coverage of static sensor networks I Dynamic coverage of mobile sensor networks an Structure of my lecture presentation 1 Statistical coverage of largescale sensor networks I Character the followings by studying the fundamental property and limitation of a sensor networks coverage I Area coverage fa the fraction of the geographic area covered by sensors I Node coverage fraction f the fraction of sensors that can be removed without reducing covered area Location model the locations of sensors are a uniformly and independently two dimensional Poisson point process with density parameter A 6 Aquot llIIIY PN A k kl Sensing model 1 Boolean sensing model each sensor has a certain sensing range r and a location is said to be covered if it lies within the sensor s sensing range 2 General sensing model L 5sp dsp 3 0 otherwise 00 1 af ssjpZ 0 i1dsj7 ASdspltB a point is covered if the allsensor field intensity at P is greater than or equal to some threshold 6 11 Results of Boolean sensing model difficult to obtain a closed form I for a twodimensional 39 expression for node coverage infinite plane the area coverage of such a sensor network is a f 1e l7zr2 a r Knode coverage area nois ooveiage 539 0 3 5 1 a a tn 0 an 2L ln1 fawer if Mil 002 I sensor density nu miner of nodes 39 spuare pixel 11 Results of general sensing model the area coverage I In the general sensing f PU 2wa XW model no sensor can be a P a 5 turned off Without for the special case 4 redF39Cing the covered region or fn 0 ital2 32 127230 f1px 735 exPl T 1 1 051213 12 L pxdx1 JFE 46 an Structure of my lecture presentation Topics in deterministic coverage of static sensor networks I aims at energy conversation switch some redundant sensors to sleeping state I how to efficiently select the active node that must maintain both sensing coverage and network connectivity Coverage degree and connectivity degree of a graph or region I Definition of coverage degree a convex region A has a coverage degree of K if every location inside A is covered by at least K nodes l Definition of connectivity degree if a graph is K connected then for any possible k 1 active nodes which fail the sensor network will remain connected Goals in static sensor network I Given a coverage region A and a node coverage degree K the goal of an integrated coverage and connectivity configuration is to maximize the number of nodes that are scheduled to sleep under the constrains that the remaining nodes must guarantee 1 A is at least K covered 2 All active nodes are connected Relationship between degree of coverage and connectivity I Theorem 1 for a set of nodes that at least 1cover a convex region A the communication graph is connected if RC 2 2R3 I Theorem 2 a set of nodes that kcover a convex region A forms a kconnected communication graph if RC 2 212 con nued Theorem 3 determining the coverage degree a convex region A is kcovered by a set of nodes if 1 there exist in region A intersection points between nodes or between nodes and A s boundary 2 all intersection points between any nodes are at kcovered and 3all intersection points between any node and A s boundary are at least K covered KCoverage Eligibility Algorithm Given a requested coverage degree K a node is ineligible if every location within its coverage range is already K covered by other active nodes in its neighborhood 39 1 Coverage configuration protocol CCPxwo5 Each node determines its eligibility using the K coverage eligibility algorithm based on the information about its sensing neighbors and may switch state dynamically when its eligibility changes Key benefits of GOP 1 GOP can configure a network to the specific coverage degree requested by the application 2 It is a decentralized protocol that only depends on local states of sensing neighbors Shortcoming of GOP It does not guarantee the scheduling of sensors is optimal and also does not give the comparison and analysis of the gap between GOP and optimal solution the optimal solution of coverage problem of static sensor networks I Assumption 1 Represent the surveillance field by a 2D rid there are a total of m grid points in the field G glg2gmg 2 Use S to denote the set of n sensor nodes IS I n that have been placed in the sensor field each sensor referred as sk sk 6 51 S k S n 3 dfis the distance between sensor node Skand grid point g 4 Use exponential function to represent the confidence level in the received sensing signal k emf dl g r pi t S 0 otherwise 01 S is the set of nodes that can detect 8 ie vsk e Spdf grs thus the detection probability for grid point g is evaluated by 19Si 1 H 1 19 Sk ES goal I Only nodes in the subset need to be actively performing the sensing task and all grid points are still covered with detection probability no lower than pm I The optimization of this problem is to find such a subset with minimum size ie the minimum number of nodes quot139 Coveragecentric active nodes selection CCANS Definition of CCANS Given the parameterpth 0 3 pm 1 a set S of n sensor nodes a set Gofm grid points find a subset Sa S such that when only nodes in Saare active 1 Vgl EC and S SaplSl 2 pth Sa is minimum 3 VseSa is connected CCANS is NPComplete 2005 CCANS can be solved using integer linear programming Objective minimize C 2 Zn xk k1 Subject to 1 H1 xkafpf2pm1gism xk0 0r xk 2113k31 l afzo 0r af11sism1sksn ZCO5 proposes a distributed heuristic approach for coverage entric active node selection based on the formation of a connected dominating set Comparing the distributed solution to an optimal solution obtained by integer linear programming centralized approach The distributed approach performs almost as well as the centralized approach for large values of the sensing range Distributed 39 o Centralized N Ln r Average Number of Active Nodes 4 m r I V 39 ivF39 v r r a r 9quot39 V 5 Sensing Range m Fig 11 Comparison of the number of active nodes determined using the centralized approach ILP and the distributed approach CCANS an Structure of my lecture presentation Dynamic Coverage Maintenance mobile sensor networks I Migration the process of moving nodes for maintaining coverage I Objective how to compensate the coverage loss by migrating neighbor sensors when the failure of one sensor node leads to coverage loss I Assumption the transmission range is more than twice the sensing range If 0 Live sensor node 0 Dead sensor node Uncovered region Figure 1 Loss of coverage due to a node s death I Rng39mn ofnrdundnnl canng LivL nude 0 Bend nod2 quot39r Figure 2 Determination 0f migrationend point quot139 Formulated as optimization problem I Let the dead nodeX have n neighbors 1417142 and for each neighbor it has a restricted point B 131132 Pnthe initial coverage of node X is Cm XWe need to move the neighbors to new position N1N2Nn towardsX such that the following conditions are satisfied 1 The area CimX CN1UCN2UUCN is maximum 2 71 Ni is minimum the above problem is exponential complex Several heuristic schemes SMOS I Maximum Energy Based MEB prefer the migration of nodes which have a larger available energy I Minmax Distance MMD the neighbor which has to move the minimum of these distances is chosen Minimum DE MDE ordering the neighbors of a node based on the ratio of maximum distance they can move to their available energy I Minimum Distance Lazy MDL moving neighboring nodes so that the uncovered area is the most likely to be covered 39 Cascaded DCM Scheme the four heuristic proposed so far move only the onehop neighbors of the dead node to compensate the lost coverage It is possible that an extension over nhop neighbors may reduce the total expense of energy more efficiently Pn39 nary CDCM dislunm Swuntluly cum L 39lil 1 Ii I Figure 6 Cascaded DCM an Structure of my lecture presentation Target coverage problem I Objective and definition Given m targets with known location and an energy constrained wireless sensor network with n sensors randomly deployed in the closed proximity of the targets schedule the sensor nodes activity such that all the targets are continuously observed and network lifetime is maximized 93 T31 quotH 9 71173 F3 r 9 r39 I39 3 s s L 39L 39 yr r Maximum Set Covers MSC problem I Definition Given a collection C of subsets of a finite set R find a family of set covers Sly35p with time weights Grail in 01 such that to maximize If1 zip and for each subset sin C s appears in SlSp with a total weight of at most 1 where 1 is the life time of each sensor a 39 52 c Sas 53 d 84454 Fig 2 Four cover sets Sn 51 392 fbr 05 time 52 52 53 fbr 05 time S3 ebb3 for 03 time and 5 81 wr time 39 v M80 is NPcompleteCT05 CTO5 proposed two efficient heuristics LP MSC and Greedy NBC heuristic using a linear programming formulation and greedy approach respectively L that l me 25 30 35 4O 45 50 Sensors LPMSC 5 targets LPMSC 15 targets Greedyit lsc 5 targets l GreedyMSG IS targets an Structure of my lecture presentation Detectability problem I A sensor network may need to detect intruders An intruder may start at a point 8 follow an arbitrary trajectory path and stop at some other point T I How to evaluate the vulnerability and efficiency of a sensor network Maximum breach path and maximum support path I Given two points 8 and T two relevant types of trajectories on the plane 1 the maximum breach path measures the vulnerability of sensor network It is trajectory between the start point 8 and the stop point Tthat stays as far away from the sensors as possible 2 The maximum support path measures the efficiency of the network coverage It is trajectory between the start point 8 and the stop point Tthat stays as close to the sensors as possible Formal definition I A maximum breach path from S to Tis a path such that the minimum distance from a point P in the path to the sensor network is maximized And this distance is called the worstcase coverage distance of the network I A maximum support path from S to Tis a path such that the maximum distance of a point P in the path to the sensor network is minimized And the distance is called the bestcase coverage distance of the network Related work I MK01 proposed optimal polynomial tme algorithms for searching the maximum breach path and maximum support path of a sensor network I HWO5 proposed an algorithm to maintain a 1 8 approximation on the best case coverage distance and a J5 8 approximation on the worst case coverage distance of the network for an fixed 8 gt O suppunnwighr Figure 3 Sensor Field with Maximal Breach Path PB And Maximal Support Path P3 1 Conclusion and future work I Conclusion Many coverage problems in sensor network are NPcomplete optimization problems so now we only can propose some heuristic algorithms to solve them I Future work Developing coverage based on realistic assumptions utilizing mobile sensors for achieving differentiated multiple coverage finding some more efficient and resilient algorithm for these NP complete problems are still under study references AK05The holes problem in wireless sensor networks a survey Nadeem Ahmed Salil S Kanhere Sanjay Jha April 2005 ACM SIGMOBILE Mobile Computing and Communications Review Volume 9 Issue 2 HW05Dynamio coverage in adhoc sensor networks Hai Huang Aner Richa Michael Segal February 2005 Mobile Networks and Applications Volume 10 Issue 12 XW05lntegrated coverage and connectivity configuration for energy conservation in sensor networks Guoliang Xing Xiaorui Wang Yuanfang Zhang Chenyang Lu Robert Pless Christopher Gill August 2005 ACM Transactions on Sensor Networks TOSN Volume 1 Issue 1 MKO ICoverage problems in wireless adhoc sensor networks Meguerdichian S Koushanfar F Potkonjak M Srivastava MB INFOCOM 2001 Twentieth Annual Joint Conference of the IEEE Computer and Communications Societies Proceedings IEEE Volume 3 2226 April 2001 Pages1380 1387 vol3 Digital Object Identifier 101109INFCOM2001916633 SM05Dynamic Coverage Maintenance Algorithms for Sensor Networks with Limited Mobility Sekhar A Manoj BS Siva C Murthy R Pervasive Computing and Communications 2005 PerCom 2005 Third IEEE International Conference on 812 March 2005 Pages51 60 Digital Object Identifier 101109PERCOM200515 ZC05A distributed coverage and connectivitycentric technique for selecting active nodes in wireless sensor networks Yi Zou Chakrabarty K Computers IEEE Transactions on Volume 54 Issue 8 Aug 2005 Pages978 991 Digital Object Identifier 101109TC2005123 CT05Energyefficient target coverage in wireless sensor networks Cardei M Thai MT Yingshu Li Weili Wu INFOCOM 2005 24th Annual Joint Conference ofthe IEEE Computer and Communications Societies Proceedings IEEE Volume 3 1317 March 2005 Pages1976 1984 GM05Coverage and holedetection in sensor networks via homology Christ R Muhammad A Information Processing in Sensor Networks 2005 IPSN 2005 Fourth International Symposium on 15 April 2005 Pages254 260