Survey: Barrier Coverage with Wireless Sensor Networks.Presentation’s OutlineIntroductionA look back..WSN CharacteristicsGoalsBreach?IPMASMProbingComplexityComparisonBarrier Sensors TopologiesSlide 14ReferencesReferences 2Thank YouSurvey: Barrier Coverage Survey: Barrier Coverage with Wireless Sensor with Wireless Sensor Networks.Networks.Feras BatarsehFeras BatarsehEEL 6788EEL 6788Presentation’s OutlinePresentation’s OutlineIntroductionIntroductionCharacteristicsCharacteristicsAlgorithms/ MethodologiesAlgorithms/ MethodologiesAlgorithms Comparison and Algorithms Comparison and ComplexityComplexityTopologiesTopologiesIntroductionIntroductionWireless network consists of Wireless network consists of spatially distributed spatially distributed autonomous devices using autonomous devices using sensors to monitor physical or sensors to monitor physical or environmental conditions.environmental conditions.The development of wireless The development of wireless sensor networks was sensor networks was originally motivated by originally motivated by military applications such as military applications such as battlefield surveillance.battlefield surveillance.A look back..A look back..•Moats?•Walls?•Landmines?WSN CharacteristicsWSN CharacteristicsMore effective.More effective.More efficient.More efficient.Covers more areas.Covers more areas.Ability to withstand harsh Ability to withstand harsh environmental conditions. environmental conditions. Ability to cope with node failures. Ability to cope with node failures. Mobility of nodes. Mobility of nodes. Dynamic network topology.Dynamic network topology.GoalsGoalsStealthinessStealthiness: A sensor network is said to: A sensor network is said tosatisfy the stealthiness assumption if nosatisfy the stealthiness assumption if nointruder is aware of the locations of theintruder is aware of the locations of thesensors.sensors.k-coverage of a pathk-coverage of a path: A path (i.e. line: A path (i.e. lineor curve) is said to be k-covered if everyor curve) is said to be k-covered if everypoint in it is covered by at least k sensors.point in it is covered by at least k sensors.Breach?Breach?Intersection point method (IPM)Association Sensors Method (ASM) ProbingIPMIPMUsing polygons to cover an area.Using polygons to cover an area.Sensors on polygon edgesSensors on polygon edges Overlapping…Overlapping…badbad Intersecting…Intersecting…badbadTilling…Tilling…goodgoodInside…Inside…multiple protectionmultiple protectionASMASMFOR (each node) {•Check Radius of coverage area•Check all intersection points of area•if diameter is inside other coverage areas of sensors•Sensor go to Sleep }//end of loopOptimization protocol to make sure that the coverage of the entire network will not drop early nor fast.ProbingProbingSleeping nodes wake upSleeping nodes wake upperiodically and broadcast aperiodically and broadcast aprobing signal to detect theprobing signal to detect theactive sensors in their active sensors in their probingprobingrange. If no active sensor isrange. If no active sensor isdetected, the sensor detected, the sensor switches toswitches toactive state, otherwise theactive state, otherwise thesensor resets its sleep timer sensor resets its sleep timer and goes back to sleep.and goes back to sleep.ComplexityComplexityIPM: O (k*m*n*m) log (n*m))IPM: O (k*m*n*m) log (n*m))ASM: O (n*m^2+n)ASM: O (n*m^2+n)Probing: O (n)Probing: O (n)Where: Where: n is average number of neighbors of a n is average number of neighbors of a nodenodem is number of nodesm is number of nodesk average edges involved in the nodek average edges involved in the nodeComparisonComparison1. IPM 1. IPM ComplexComplexslower algorithmslower algorithmefficientefficient2. Probing2. Probing FastFastSimpleSimpleun necessary power wasted!un necessary power wasted!3. ACM 3. ACM SlowSlowAssumes full power of sensor!Assumes full power of sensor!Barrier Sensors TopologiesBarrier Sensors TopologiesDisc-based sensing: Disc-based sensing: where each active where each active sensor has a sensing radius of sensor has a sensing radius of rr; any object ; any object within the disc of radius within the disc of radius r r centered at an centered at an active sensor is reliably detected by it.active sensor is reliably detected by it.RIS scheme: RIS scheme: Time is divided in regular Time is divided in regular intervals and in each interval, eachintervals and in each interval, eachsensor is active.sensor is active.Belt of dimension w X h : Belt of dimension w X h : A rectangular A rectangular region.region.Barrier Sensors TopologiesBarrier Sensors TopologiesDepends on the shape of the barrier/area to cover.ReferencesReferences1- 1- Barrier coverage with wireless sensorsBarrier coverage with wireless sensorsSantosh Kumar, Ten H. Lai, Anish AroraSantosh Kumar, Ten H. Lai, Anish AroraAugust 2005August 2005MobiCom '05: Proceedings of the 11th annual international conference on Mobile computing and MobiCom '05: Proceedings of the 11th annual international conference on Mobile computing and networkingnetworking2- Reliable density estimates for coverage and connectivity in thin strips of finite length2- Reliable density estimates for coverage and connectivity in thin strips of finite lengthPaul Balister, Béla Bollobas, Amites Sarkar, Santosh KumarPaul Balister, Béla Bollobas, Amites Sarkar, Santosh KumarSeptember 2007September 2007MobiCom '07: Proceedings of the 13th annual ACM international conference on Mobile computing and MobiCom '07: Proceedings of the 13th annual ACM international conference on Mobile computing and networkingnetworking3- 3- Coverage breach problems in bandwidth-constrained sensor networksCoverage breach problems in bandwidth-constrained sensor networks Maggie X. Cheng, Lu Ruan, Weili WuMaggie X. Cheng, Lu Ruan, Weili WuJune 2000June 2000ACM Transactions on Sensor Networks (TOSN), E Volume 3 Issue 2ACM Transactions on Sensor Networks (TOSN), E Volume 3 Issue 24- 4- Coverage protocols for detecting fully sponsored sensors in wireless sensor networksCoverage protocols for detecting fully sponsored sensors in wireless sensor networks Azzedine Boukerche, Xin FeiAzzedine Boukerche, Xin FeiOctober 2006October 2006PE-WASUN '06: Proceedings of the 3rd ACM international workshop on Performance evaluation of PE-WASUN '06: Proceedings of the
View Full Document
Unlocking...