Jana van Greunen - 228a 1Analysis of Localization Algorithms for Sensor NetworksJana van GreunenJana van GreunenJana van Greunen - 228a 2OutlineIntroductionIntroductionAlgorithm overviewAlgorithm overviewComparison & evaluationComparison & evaluationExtensions:Extensions:RealReal--time error estimationtime error estimationLowLow--energy computationenergy computationResultsResultsConclusionConclusionJana van Greunen - 228a 3IntroductionSensor network consists of many small, cheap, Sensor network consists of many small, cheap, selfself--sustaining, densely deployed sensor nodes.sustaining, densely deployed sensor nodes.Applications require that the nodes in the network Applications require that the nodes in the network are aware of their geographic location.are aware of their geographic location.Too expensive to use GPS on every nodeToo expensive to use GPS on every nodeThus need algorithms to compute each nodeThus need algorithms to compute each node’’s s position using nodeposition using node--toto--node range measurements node range measurements and information from a few reference nodesand information from a few reference nodesRange measurements are made between each node Range measurements are made between each node and its neighbors within a circular areaand its neighbors within a circular areaJana van Greunen - 228a 4Introduction cont’Measurements are made using TOA or RSSI Measurements are made using TOA or RSSI ––both methods are error prone both methods are error prone A good localization algorithm should:A good localization algorithm should:Be tolerant to range errors Be tolerant to range errors Scale with networkScale with networkMinimize communication & computation energy spentMinimize communication & computation energy spentConverge rapidly and accuratelyConverge rapidly and accuratelyPerform well across network topologies Perform well across network topologies Provide a measure of errorProvide a measure of errorJana van Greunen - 228a 5Algorithm overviewCentralized LP (Doherty et al.)Centralized LP (Doherty et al.)Key assumption: if two nodes can communicate Key assumption: if two nodes can communicate with each other, they must lie within the with each other, they must lie within the communication radius R of each other. communication radius R of each other. Mathematically = 2Mathematically = 2--norm constraint on the norm constraint on the node positionsnode positionsCombine local connectivityCombine local connectivity--induced constraints induced constraints to solve:to solve:bAxtoSubjectxTcMinimize<: :Jana van Greunen - 228a 6Rectangular intersection (Simič)Partition space into cubes/squares (cells)Partition space into cubes/squares (cells)Communication area is a square (#cells) Communication area is a square (#cells) At every unknown node:At every unknown node:Step A: Step A: Gather positions Gather positions of oneof one--hop neighbors hop neighbors with known positions with known positions Step B: Step B: Compute estimated Compute estimated position via minimumposition via minimumrectangular intersectionrectangular intersectionJana van Greunen - 228a 7Network Coordinate (Capkun)2 phase algorithm2 phase algorithmLocal coordinatesLocal coordinatesEach node Each node j j measures distances to its onemeasures distances to its one--hop hop neighbors and their distances from each other neighbors and their distances from each other Place onePlace one--hop neighbors hop neighbors in local coordinatein local coordinatesystem (trigonometry)system (trigonometry)Global coordinatesGlobal coordinatesAlign local coordinatesAlign local coordinatesJana van Greunen - 228a 8DV-Hop (Niculescu et al.)Use Use ‘‘averageaverage’’distance to prevent error propagation distance to prevent error propagation Known nodes flood Known nodes flood ‘‘hopshops’’and position through networkand position through networkEach unknown node stores the position and hopEach unknown node stores the position and hop--distance distance (# hops*average distance) from all the known nodes (# hops*average distance) from all the known nodes When an unknown node has its hopWhen an unknown node has its hop--distance from more distance from more than three nonthan three non--colinearcolinearknown nodes it can compute its known nodes it can compute its position via triangulation (solve Ax=b) position via triangulation (solve Ax=b) This algorithm works well when topology is regularThis algorithm works well when topology is regularJana van Greunen - 228a 9Start-up & refinement (Savarese)22--phasephaseInitial position estimateInitial position estimateDVDV--HopHopRefinementRefinementNodes try to improve their position estimates by iteratively Nodes try to improve their position estimates by iteratively measuring the distances to onemeasuring the distances to one--hop neighbors and then hop neighbors and then performing weighted maximum likelihood triangulation. performing weighted maximum likelihood triangulation. All unknown nodes start with a weight of 0.1All unknown nodes start with a weight of 0.1Known nodes have weight 1.0Known nodes have weight 1.0After each position update the weight of the node is set to the After each position update the weight of the node is set to the average weight of all its neighborsaverage weight of all its neighborsJana van Greunen - 228a 10ComparisonYesYesMediumMediumMediumMediumYesYesYesYesDVDV--HopHopModeratelyModeratelyNoNoYesYesNoNoTolerant to Tolerant to range errorrange errorMediumMediumDepends on Depends on network sizenetwork sizeFastFastDepends on Depends on network sizenetwork sizeSpeed of Speed of convergenceconvergenceFairFairPoorPoorSpottySpottyGoodGoodAccuracyAccuracyModeratelyModeratelyModeratelyModeratelyYesYesNoNoEnergy Energy efficientefficientYesYesNoNoYesYesNoNoScalableScalableStartStart--up & up & refinementrefinementNetwork Network CoordinateCoordinateRectangular Rectangular intersectionintersectionCetralized Cetralized LPLPNote: no algorithm provides a measure of final position errorJana van Greunen - 228a 11ExtensionsReal time error estimate for centralized algorithm Real time error estimate for centralized algorithm ((PatwariPatwariet
View Full Document
Unlocking...