Analysis of Localization Algorithms for Sensor NetworksOutlineIntroductionIntroduction cont’Algorithm overviewRectangular intersection (Simič)Network Coordinate (Capkun)DV-Hop (Niculescu et al.)Start-up & refinement (Savarese)ComparisonExtensionsCramer-Rao bound cont’Low-power computationResultsResults cont’Future workConclusionJana van Greunen - 228a 1Analysis of Localization Algorithms for Sensor Networks Jana van GreunenJana van GreunenJana van Greunen - 228a 2OutlineIntroductionIntroductionAlgorithm overviewAlgorithm overviewComparison & evaluationComparison & evaluationExtensions:Extensions:Real-time error estimationReal-time error estimationLow-energy computationLow-energy computationResultsResultsConclusionConclusionJana van Greunen - 228a 3IntroductionSensor network consists of many small, cheap, self-Sensor network consists of many small, cheap, self-sustaining, densely deployed sensor nodes.sustaining, densely deployed sensor nodes.Applications require that the nodes in the network are Applications require that the nodes in the network are aware of their geographic location.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 node’s Thus need algorithms to compute each node’s position using node-to-node range measurements and position using node-to-node range measurements and information from a few reference nodesinformation 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 = 2-norm constraint on the node Mathematically = 2-norm constraint on the node positionspositions Combine local connectivity-induced constraints Combine local connectivity-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 one-hop neighbors of one-hop neighbors with known positions with known positions Step B: Step B: Compute estimated Compute estimated position via minimumposition via minimum rectangular intersectionrectangular intersectionJana van Greunen - 228a 7Network Coordinate (Capkun)2 phase algorithm2 phase algorithmLocal coordinatesLocal coordinates Each node Each node j j measures distances to its one-hop measures distances to its one-hop neighbors and their distances from each other neighbors and their distances from each other Place one-hop neighbors Place one-hop neighbors in local coordinatein local coordinate system (trigonometry)system (trigonometry)Global coordinatesGlobal coordinates Align local coordinatesAlign local coordinatesJana van Greunen - 228a 8DV-Hop (Niculescu et al.)Use ‘average’ distance to prevent error propagation Use ‘average’ distance to prevent error propagation Known nodes flood ‘hops’ and position through networkKnown nodes flood ‘hops’ and position through networkEach unknown node stores the position and hop-distance Each unknown node stores the position and hop-distance (# hops*average distance) from all the known nodes (# hops*average distance) from all the known nodes When an unknown node has its hop-distance from more When an unknown node has its hop-distance from more than three non-colinear known nodes it can compute its than three non-colinear 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)2-phase2-phaseInitial position estimateInitial position estimateDV-HopDV-HopRefinementRefinementNodes try to improve their position estimates by iteratively Nodes try to improve their position estimates by iteratively measuring the distances to one-hop neighbors and then measuring the distances to one-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 10ComparisonCetralized Cetralized LPLPRectangular Rectangular intersectionintersectionNetwork Network CoordinateCoordinateDV-HopDV-HopStart-up & Start-up & refinementrefinementScalableScalableNoNoYesYesNoNoYesYesYesYesEnergy Energy efficientefficientNoNoYesYesModeratelyModeratelyYesYesModeratelyModeratelyAccuracyAccuracyGoodGoodSpottySpottyPoorPoorMediumMediumFairFairSpeed of Speed of convergenceconvergenceDepends on Depends on network sizenetwork sizeFastFastDepends on Depends on network
View Full Document
Unlocking...