Topological Hole DetectionPaperMotivationSlide 4Other UsesAssumptionsThe continuous caseDiscrete CaseSlide 9Slide 10AlgorithmsBeacon SelectionDistributed ImplementationApplication: Landmark Selection in GLIDERSlide 15Problems of unaware Landmark-SelectionSlide 17Solution: First AttemptSolution: Second AttemptMore ApplicationsEvaluation: UDG - randomEvaluation: UDG - gridEvaluation: Non-UDGConclusionThank You!Topological Hole DetectionRitesh MaheshwariCSE 590Paper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 networkMotivation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 efficientlyMotivation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 efficientlyOther UsesProvide topology information to Location unaware protocols like GLIDERHelp in Landmark selection for GLIDERBetter Virtual coordinates in absence of Location InformationAssumptionsRegion REvery point in R is covered for sensing by atleast one sensorUsually comm range larger than sensing rangeUnit Disk GraphNo location informationOnly connectivity information availableThe continuous caseA beacon pointConstruct contours of Euclidean distance from beaconObservation: contours usually break at boundaryDiscrete CaseNo ‘points’ – only sensor nodesNo ‘distance’ measurement – only hop-countConnected Components of same hop-count from beacon form contoursDiscrete CaseBeacon – node pdp(v) is hop-count from p to node vI(k) = { v : dp(v) = k} is isoset of level kI(k) may be disconnected, so resulting connected components are called C1(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, one beacon is not enough. They use 4AlgorithmsBeacon 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 beaconDistributed ImplementationTopology exploration done only rarelyThus naïve implementation suitsCan be done by Flooding a constant number of timesApplication: 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 qProblems of unaware Landmark-SelectionProblems of unaware Landmark-SelectionSolution: First AttemptObservation: If 2 landmarks are on same hole boundary, then the hole cannot be totally inside one tileSolution: Second AttemptHole Repulsion and PruningMore ApplicationsTo find Virtual Coordinates in presence of holesMedial-Axis-Based RoutingEvaluation: UDG - randomEvaluation: UDG - gridEvaluation: Non-UDGConclusionSimple protocolOnly Connectivity info requiredHole detection => Event detectionBut useful only for dense networksNot that bad, as they assume cheap sensorsThank