advertisement

Using Probabilistic Methods for Localiza

100 %
0 %
advertisement
Information about Using Probabilistic Methods for Localiza
Education

Published on November 26, 2008

Author: aSGuest4000

Source: authorstream.com

advertisement

Using Probabilistic Methods for Localization in Wireless Networks : Using Probabilistic Methods for Localization in Wireless Networks Presented by Adam Kariv May, 2005 Agenda : Agenda Introduction Theory Our Algorithm Preliminary Results Goal : Goal Find the exact location of a wireless, mobile, network device. Possible Applications : Possible Applications Smart Buildings Route incoming calls to the nearest phone-extension. Print documents to the nearest printer. Download slides of the currently presented lecture. Location-based Targeted Advertisement Receive discount information of the store you're standing next to. Our Solution Concept : Our Solution Concept A mobile station may use the received strengths of network signals in order to passively find it's own location. Network Elements : Network Elements Base Stations - Stationary network elements, usually used to connect the wireless network to external networks. Mobile Stations - User agents, whose location is dynamic.  This is the location we aim to find! Assumptions : Assumptions Each mobile station is in the reception range of several base stations. Mobile stations can easily list all base-stations in reception range. Mobile stations know the strength of the received signal from each base-station in its reception range. Examples for Wireless Networks : Examples for Wireless Networks 802.11 Wireless Local Area Networks. GSM Cellular Networks. Drawbacks (1) : Drawbacks (1) Our localization scheme is nearly network-independent - Better results may be obtained by utilizing data available from the network (e.g. cell id) designing a network to be "localization-aware" performing actual localization on the network side, which has access to more data and better resources. Obtaining location using a different technology. Drawbacks (2) : Drawbacks (2) Can't localize when too few base stations are in reception range. May not be a problem in 802.11 WLAN Could be problematic in cellular networks Probably will be a problem in WiMax. Agenda : Agenda Introduction Theory Our Algorithm Preliminary Results Reference Measurement (1) : Reference Measurement (1) Preparation: Measure in selected reference points the exact received signal strength from each base station. Store measurement for each location in the signal strength database. Reference Measurement (2) : Reference Measurement (2) In order to localize: Measure exact signal strength from each base station. Find the best match for the current measurement in the signal-strength database. Accuracy is proportional to reference points density. Problems with Reference Measurement (1) : Problems with Reference Measurement (1) Tedious preparations phase, Low tolerance to changes in the amount or location of base stations, In order to achieve better accuracy, we must have more reference points  even longer preparation overhead. Problems with Reference Measurement (2) : Problems with Reference Measurement (2) Noise in signal strength measurements during localization may cause jitter in resulting location. Doesn't take into account prior knowledge we may have of the physical environment. Using a physical model : Using a physical model In order to avoid the preparations phase, we could deduce the signal strength using a radio propagation model. The model can predict the signal strength in each reference point. Number of possible reference points is unlimited This method allows us to improve accuracy without increasing overheads. But - Is this feasible? Problems with physical model : Problems with physical model Achieving an accurate physical model is very difficult Many "real-world" phenomenon are hard to model: Reflections, Signal decay when passing through obstacles, We have many unknowns, such as: Floor plan of building, exact location and material of obstacles, walls, windows, furniture… Exact location of base-stations, Transmission power of base-stations, Sensitivity and Amplification of receiving mobile-station  Achieving an accurate physical model is very difficult. Simple physical model (1) : Simple physical model (1) [as shown by Wallbaum & Wasch, 2004] Assumptions: Disregards reflections. Floor plan of building is fairly known. Base-station locations are known Base-station and mobile-station properties are known To compute received strength at point X of a signal transmitted from point Y - Count the number of obstacles of each kind on the straight line from X to Y Use the following function: Simple physical model (2) : Simple physical model (2) Object classes and their parameters: Hidden Markov Model : Hidden Markov Model Hidden Markov Model - HMM Defines a set of random variables One “hidden” and one “observable” for each time step. In our case: The hidden variable has the actual location at each time step. The observable has the sampled data at each time step – i.e. the reported signal strength from every base-station. The HMM “tracks” the location of the mobile-station through time. Using HMMs : Using HMMs This method assumes good knowledge of the following probability functions: A(l,l') = P( locationt+1 = l' | locationt = l ) B(l,s) = P( samplet = s | locationt = l ) Using these functions, we can easily compute the exact value of P( locationt = l | sample1 ... samplet ) The probability of being in any of the reference locations at time t, given all the previous samples. Previous Results : Previous Results Castro, Chiu, Kremenek, Muntz (2001) Physical Model Ladd, Bekris, Marceau, Rudys, Wallach Kavraki (IROS 2002) Physical Model + HMM Haeberlen, Flannery, Ladd, Rudys, Wallach, Kavraki (MOBICOM 2004) Reference Measurement + HMM Wallbaum, Wasch (WONS 2004) Physical Model + HMM Agenda : Agenda Introduction Theory Our Algorithm Preliminary Results Tying it all together : Tying it all together Floor plan of Ross Building, Entrance Level: Tying it all together : Tying it all together Use the physical model to fill initial values in the signal strength database. Transition function: A(l,l') = P( locationt+1 = l' | locationt = l ) - ~1 - for staying in the same location <<1 - for moving to an adjacent reference location 0 - otherwise Emission function: B(l,s) = P( samplet = s | locationt = l ) Depends on the distance of s from the lth position in the signal-strength database. Tying it all together : Tying it all together To localize, for each sample, we calculate: maxargl P( locationt = l | sample1 ... samplet ) Previous results already achieve good localization results – how can we do better? The EM Algorithm : The EM Algorithm The EM algorithm is an iterative method used to find the most likely model for a given sample. It has two steps: E - Estimate probabilities for each hidden variable at each time. M - Find new model which maximizes the likelihood of the samples. Using EM to improve the model : Using EM to improve the model Model may include the signal-strength database, the transition function, plus all the physical model's unknowns. E step: Find P( locationt=l ) for each t, l Using signal-strength database and HMM M step: Find new values for signal-strength database DB(l) = St [ P( loct=l )*samplet ] / St P( loct=l ) Problems of EM : Problems of EM EM finds the model which maximizes the likelihood of the sampled data. This does not guarantee correctness… EM has many local maxima Better start close to the correct solution. Agenda : Agenda Introduction Theory Our Algorithm Preliminary Results Performed Simulation (1) : Performed Simulation (1) Mobile-station performs a random-walk along the reference locations. “Measured” signal strength is the sum of: Expected signal strength, according to the Physical Model, Model Error, fixed for each location, modeling inaccuracies in the physical model, Sensor Error, modeling measurement errors. HMM is used to track the mobile-station’s location. Inferred path is compared to actual path. Performed Simulation (2) : Performed Simulation (2) The EM algorithm is used to learn a better model In our case - more accurate values for the signal-strength database. We will see results for two scenarios: Low model and sensor errors (~1dB) High model and sensor errors (~10dB) Measures for Learning Quality : Measures for Learning Quality Location Accuracy Could be misleading – depends on reference-point density. Localization Error Inferred path vs. actual path 1-hop localization error Signal-Strength Database Error Likelihood Could be used as a measure for convergence. Localization Error (1-hop) : Localization Error (1-hop) Signal-Strength Database Error : Signal-Strength Database Error Likelihood : Likelihood Future Plans : Future Plans Use better representations of Model Errors and Sensor Errors Improve EM to Learn more of the physical model unknowns Learn the transition function (A matrix) Use multiple samples concurrently to improve learning quality and speed Perform “field-test” with actual network data. Questions? : Questions?

Add a comment

Related presentations

Related pages

Retinal vessel segmentation using a probabilistic tracking ...

Many vessel extraction methods, using different ... based method using a probabilistic formulation is ... or poor contrast [37] for endpoint localiza ...
Read more

Learning Tractable Probabilistic Models for Fault Localization

We evaluate the fault localiza- ... ous statistical methods or using TARANTULA directly. ... Probabilistic Debugging Methods
Read more

Teaching Localization in Probabilistic Robotics - uml.edu

Teaching Localization in Probabilistic ... riety of methods are ... assignments to introduce students robot localization using probabilistic methods.
Read more

VISUAL OUTDOOR LOCALIZATION USING A PROBABILISTIC MODEL

VISUAL OUTDOOR LOCALIZATION USING A PROBABILISTIC MODEL ... Localiza˘cao em ambientes ... Considering interest point based methods, Lowe and ...
Read more

A Generic Approach for Robust Probabilistic Estimation ...

A Generic Approach for Robust Probabilistic ... Abstract—Probabilistic estimation using ... robust algorithms in this sense are methods that can ...
Read more

Comparing Bayesian and Montecarlo localization for a robot ...

The goal of this paper is to compare two probabilistic localiza-tion methods based on local ... and their behaviour studied in several situations using a ...
Read more

Probabilistic Modeling and Recognition of 3-D Objects

Probabilistic Modeling and Recognition of 3-D ... techniques to solve the object recognition and localiza- ... Probabilistic methods are successfully ...
Read more

Learning Tractable Probabilistic Models for Fault Localization

Learning Tractable Probabilistic Models for Fault Localization ... cal debugging methods generalize over many ... ous statistical methods or using ...
Read more

Probabilistic Localization for Outdoor Wireless Sensor ...

Probabilistic Localization for Outdoor Wireless ... possible locations of the nodes by using a combination ... existing methods and approaches ...
Read more