Topological Hole Detection Ritesh Maheshwari CSE 590 Paper S Funke Topological Hole Detection and its Applications DIALM POMC 2005 Basically aim is to identify which nodes form the boundary outer or inner of holes in a wireless sensor network Motivation Imagine a remote nature preserve Long summer drought resulting in Wildfires Airplanes dropping thousands of cheap sensor nodes so that the sensor network Organizes itself routes messages Identifies current firefront Answers Queries efficiently Motivation Imagine a remote nature preserve Long summer drought resulting in Wildfires Airplanes dropping thousands of cheap sensor nodes so that the sensor network Organizes itself routes messages Identifies current firefront Hole Detection Answers Queries efficiently Other Uses Provide topology information to Location unaware protocols like GLIDER Help in Landmark selection for GLIDER Better Virtual coordinates in absence of Location Information Assumptions Region R Every point in R is covered for sensing by atleast one sensor Usually Unit comm range larger than sensing range Disk Graph No location information Only connectivity information available The continuous case A beacon point Construct contours of Euclidean distance from beacon Observation contours usually break at boundary Discrete Case No points only sensor nodes No distance measurement only hop count Connected Components of same hop count from beacon form contours Discrete Case Beacon node p dp v is hop count from p to node v I k I k v dp v k is isoset of level k may be disconnected so resulting connected components are called C 1 k C2 k C3 k Discrete Case Boundary nodes are now the end nodes of the Connected Components C1 k C2 k etc Pick random node r in Ci k and find nodes in Ci k with highest hop count from r Usually use 4 one beacon is not enough They Algorithms Beacon Selection The 4 beacons should be as far away as possible Choose 1st beacon randomly Other 3 chosen on the basis of their distance from the 1st beacon Distributed Implementation Topology Thus Can exploration done only rarely na ve implementation suits be done by Flooding a constant number of times Application Landmark Selection in GLIDER Landmarks divide the network into tiles using Voronoi diagrams Local coordinate system constructed within each tile When p in tilep wants to send packet to q in tileq Inter tile Packet is routed to a neighboring tile which is nearer to tileq than tilep and so on Intra tile When reaching tileq local coordinate system used to route to q Problems of unaware Landmark Selection Problems of unaware Landmark Selection Solution First Attempt Observation If 2 landmarks are on same hole boundary then the hole cannot be totally inside one tile Solution Second Attempt Hole Repulsion and Pruning More Applications To find Virtual Coordinates in presence of holes Medial Axis Based Routing Evaluation UDG random Evaluation UDG grid Evaluation Non UDG Conclusion Simple protocol Only Connectivity info required Hole detection Event detection But useful only for dense networks Not that bad as they assume cheap sensors Thank You
View Full Document
Unlocking...