9/6/05 Jie Gao, CSE590-fall05 1Localization in Sensor NetworksLocalization in Sensor NetworksJie GaoComputer Science DepartmentStony Brook UniversitySome slides are made by Savvides9/6/05 Jie Gao, CSE590-fall05 2Find where the sensor is…Find where the sensor is…• Location information is important.1. Devices need to know where they are.• Sensor tasking: turn on the sensor near the window…2. We want to know where the data is about.• A sensor reading is too hot – where?3. It helps infrastructure establishment, such as geographical routing and sensor coverage.• Intruder detection;• Localized geographical routing.9/6/05 Jie Gao, CSE590-fall05 3GPS is not always goodGPS is not always good• Requires clear sky, doesn’t work indoor.• Too expensive.– A $1 sensor attached with a $100 GPS?Localization:• (optional) Some nodes (anchors or beacons) have GPS or know their locations. • Nodes make local measurements;– Distances between two sensors, angles between two neighbors, etc.• Communicate between each other;• Infer location information from these measurements.9/6/05 Jie Gao, CSE590-fall05 4Model of a sensor networkModel of a sensor network• Sensor networks with omni-directional antennas are usually modeled by unit disk graphs.– Two nodes have a link if and only if their distance is within 1.• Use the graph property (connectivity, local measurements) to deduct the locations.9/6/05 Jie Gao, CSE590-fall05 5Localization problemLocalization problem• Output: nodes’ location.– Global location, e.g., what GPS gives.– Relative location. • Input: – Connectivity, hop count. • Nodes with k hops away are within Euclidean distance k.• Nodes without a link must be at least distance 1 away.– Distance measurement of an incoming link.– Angle measurement of an incoming link.– Combinations of the above.9/6/05 Jie Gao, CSE590-fall05 6MeasurementsMeasurementsDistance estimation: • Received Signal Strength Indicator (RSSI)– The further away, the weaker the received signal.– Mainly used for RF signals.• Time of Arrival (ToA) or Time Difference of Arrival (TDoA)– Signal propagation time translates to distance.– RF, acoustic, infrared and ultrasound.Angle estimation:• Angle of Arrival (AoA)– Determining the direction of propagation of a radio-frequency wave incident on an antenna array.• Directional Antenna• Special hardware, e.g., laser transmitter and receivers.9/6/05 Jie Gao, CSE590-fall05 7LocalizationLocalization• Given distances or angle measurements, find the locations of the sensors.• Anchor-based– Some nodes know their locations, either by a GPS or as pre-specified.• Anchor-free– Relative location only.– A harder problem, need to solve the global structure. Nowhere tostart.• Range-based– Use range information (distance estimation).• Range-free– No distance estimation, use connectivity information such as hopcount.9/6/05 Jie Gao, CSE590-fall05 8Many ways to approach this problemMany ways to approach this problem• Trilateration and triangulation • Fingerprinting and classification• Ad-hoc and range/free• Graph rigidity • Identifying codes • Bayesian Networks • Optimization • Multi-dimensional scaling9/6/05 Jie Gao, CSE590-fall05 9TrilaterationTrilaterationand Triangulationand Triangulation• Use geometry, measure the distances/angles to three anchors. • Trilateration: use distances– Global Positioning System (GPS)• Triangulation: use angles – Cell phone systems.• How to deal with inaccurate measurements?• How to solve for more than 3 (inaccurate) measurements?9/6/05 Jie Gao, CSE590-fall05 10AdAd--hoc approacheshoc approaches• Ad-hoc positioning (APS)– Estimate range to landmarks using hop count or distance summaries• APS:– Count hops between landmarks– Find average distance per hop– Use multi-lateration to compute location9/6/05 Jie Gao, CSE590-fall05 11OptimizationOptimization• View system of nodes, distances and angles as a system of equation with unknowns. • Add inequalities– E.g. radio range is at most 1.• Solve resulting system of inequalities as an optimization problem.9/6/05 Jie Gao, CSE590-fall05 12Multidimensional Scaling (MDS)Multidimensional Scaling (MDS)• MDS is a general method of finding points in a geometric space that preserves the pair-wise distances as much as possible. – It works also for non-metric data.• Given the pairwise distances P, find a set of points X in m-dimensional space. • Take the largest 2 eigenvalues and eigenvectors of X as the best 2D approximations.9/6/05 Jie Gao, CSE590-fall05 13Fingerprinting, classification and scene Fingerprinting, classification and scene analysisanalysis• Offline phase: collect training data (fingerprints): [(x, y), SS]. – E.g., the mean Signal Strength to N landmarks.• Online phase: Match RSS to existing fingerprints probabilistically or by using a distance metric. • Cons: – How to build the map? • Someone walks around and samples? • Automatic? – Sampling rate?– Changes in the scene (people moving around in a building) affect the signal strengths.[-80,-67,-50]RSS(x?,y?)[(x,y),s1,s2,s3][(x,y),s1,s2,s3][(x,y),s1,s2,s3]9/6/05 Jie Gao, CSE590-fall05 14Bayesian NetworksBayesian Networks• View positions as random variables • Build network to describe likely values of these variables given observations • Pros:– Captures any set of observations and priors• Cons:– Computationally expensive – Accuracy9/6/05 Jie Gao, CSE590-fall05 15PapersPapers• Multi-lateration:• [Savvides01] A. Savvides, C.-C. Han, and M. B. Strivastava. Dynamic fine-grained localization in ad-hoc networks of sensors. Proc. MobiCom 2001. • [Savvides03] A. Savvides, H. Park, and M. B. Strivastava. The n-hop multilateration primitive for node localization problems, Mobile Networks and Applications, Volume 8, Issue 4, 443-451, 2003.• Mass-spring model:• [Howard01] A. Howard, M. J. Mataric, and G. Sukhatme, Relaxation on a Mesh: a Formalism for Generalized Localization, IEEE/RSJ Internaltionsl Conference on Intelligent Robots and Systems, October, 2001.9/6/05 Jie Gao, CSE590-fall05 16MultilaterationMultilateration: use plane geometry: use plane geometry9/6/05 Jie Gao, CSE590-fall05 17Base Case: Atomic Base Case: Atomic MultilaterationMultilateration• Base stations advertise their coordinates & transmit a referencesignal• PDA uses the reference signal to estimate distances to each of the