Smartphone Positioning Based on a Hidden Markov Model
March 4, 2011 By: Jingbin Liu, Ruizhi ChenThis paper introduces a Smartphone positioning solution for indoors based on the wireless signal opportunities and the built-in navigation sensors in smart phones. The proposed solution is based on a hidden Markov model solved with a Viterbi algorithm. The solution takes the advantages of the conventional RSSI (Received Signal Strength Indication) fingerprinting solution and the user walking dynamics estimated with the build-in navigation sensor. The user dynamic information is used for estimating the state transition probability in the hidden Markov model. The solution requires no additional hardware components to the smart phones. The test results demonstrated that the hidden Markov model performs much better than the conventional fingerprinting solutions.
The Bayesian-based approaches such as the maximum likelihood (ML) estimation and the maximum a posteriori (MAP) estimation are widely used in WLAN (Wireless Local Area Network) fingerprinting positioning for indoor environment. The principle of the convention fingerprinting solutions is to find such a location from where the RSSI (Received Signal Strength Indication) observations (stored in the database) are matched to the current observed RSSI observations with the maximum probability. User walking dynamics are not considered for conventional fingerprinting approaches. In fact, the walking process of a user can be represented with a hidden Markov model because this process possesses Markov property. Therefore, a Hidden Markov Model (HMM) based solution is proposed in this paper as shown in Figure 1.
Figure 1. The hidden Markov model.
From Figure 1, X(t) is the position (state) vector at observation time t, while O(t) is the RSSI observation vector for the same epoch. The matrix A is the state transition probability from state X(t-1) to state X(t), while P((O(t)|X(t)) is the observation probability in state X(t).
The positioning problem becomes to find a sequence of states that most likely have generated the corresponding observation sets . A Viterbi algorithm has been employed in our case to solve the problem. More details regarding to the Viterbi algorithm can be found in the paper in the resources below. The state transition probability A and the observation probability P((O(t)|X(t)) are the only two parameters that are needed in the Viterbi algorithm. In our solution, the state transition probabilities are estimated with user dynamics derived from the navigation sensors embedded in the smart phone, while the observation probability P((O(t)|X(t)) are obtained from the fingerprinting database.
Estimation of the State Transition Probability
As mentioned above, the state transition probabilities play an important role in the HMM solution. The more precise the state transition probability is, the more reliable positioning solution can be achieved. The built-in navigation sensors in smart phones can provide us with a part or all of the user dynamic information, i.e. the traveled distance and/or heading change from the previous state, depending on the availability of navigation sensors in smart phones (e.g. accelerometer, gyroscope, and digital compass).
The traveled distances or heading changes are important information for calculating the state transition probabilities. In case the traveled distance is available, the state candidates (grid points) that are located within the ring zone (zone I in Figure 2) will have higher state transition probabilities, while the states outside of the ring zone should have small or zero transition probabilities because the next state is most probably located inside the ring zone according to the user traveled distance. Here the center of the ring is the state/position of the previous epoch, the radius of the ring is defined by the traveled distance and the width of the ring is defined by the uncertainty of the estimated traveled distance.
In case the heading change is available, the candidate states with higher state transition probabilities are those states that are located within the sector area (zone II in Figure 2) defined by the angle radiating from the center of the ring. The width of the angle is defined by the uncertainty of heading estimation. In case both the traveled distance and the heading information are available simultaneous, the candidate states with higher state transition probabilities are those candidates that are located within intersection zone of the ring and the sector area (zone III in Figure 2).
For the details of calculating of state transition probability for each candidate state, please refer to the paper in the resources below.
Figure 2. Candidate states (grid points) with higher state transition probabilities. The blue triangle is the location of the previous epoch.
Field Tests
Two test cases have been carried out to evaluate the performance of the HMM solution. The first test case is a static test in indoors, while the second test case is a dynamic test for a scenario of seamless indoor outdoor positioning.
A. Static Indoor Positioning
The objective of this test case is to evaluate the positioning accuracy of the HMM solution in static case. Two data sets (#1 & #2) were collected overnight at two different points at the third floor of the office building of the Finnish Geodetic Institute where a WLAN network is installed. The positioning accuracies are listed in Table 1 for different scenarios. The experiment results show that RMSE (Root Mean Square Error) of the HMM solution is less than 0.7 meters, while that for the conventional fingerprinting positioning solutions (ML and MAP) are more than 2.5 meters.
B. Indoor/Outdoor Seamless Positioning
The objective of this test case is to evaluate the performance of the HMM solution in a dynamic case. This test case (test data set #3) started from outdoor and stayed until the first GPS position fix was available before walking into indoor where a WLAN network was installed. The WLAN positioning was started with the latest GPS solution as the prior position. Different positioning scenarios were calculated as listed in the last column in Table 1. It is obvious that the hidden Markov model approach also performs better than the other two conventional fingerprinting approaches. Fig. 3 shows the cumulative error probability distribution of different positioning methods.
Table 1. Errors of different positioning scenarios.
ML = Maximum Likelihood; MAP = Maximum a Posteriori; HMM = Hidden Markov Model.
| Positioning methods | ||||
| Test #1 | Test #2 | Test #3 | ||
| ML | 4.09 | 3.90 | 5.97 | |
| MAP | 2.94 | 2.76 | 3.72 | |
| HMM | With Accelerometer | 0.67 | 0.68 | 1.42 |
| Without Accelerometer* | 2.73 | |||
*A walking speed of 1.2m/s was applied to this scenario for the purpose of testing.
Figure 3. Cumulative error probability distribution of different positioning methods.
Conclusions
This paper introduced a smartphone-based positioning solution based on hidden Markov model. The solution takes the advantages of both the RF signal opportunity and navigation sensor measurements that are available in smart phones. In addition to utilize the RSSI measurements, the HMM solution also integrates the user dynamics to the estimation of the user positions. The user dynamic information such as traveled distances and heading changes are derived from the measurements of the built-in navigation sensors in smart phones. The performances of the HMM solution has been evaluated with two test cases, one for static case, while the other for dynamic case. The test results demonstrated that the HMM solution performed much better, in both test cases, than the conventional fingerprinting positioning solutions.
Resources
This article is a part of the following paper published in the proceedings of the PLAN 2010 conference: J. Liu, R. Chen, L. Pei, W. Chen, T. Tenhunen, H. Kuusniemi, T. Kroeger, Y. Chen, “Accelerometer Assisted Robust Wireless Signal Positioning Based on a Hidden Markov Model,” in Position Location and Navigation Symposium (IEEE/ION PLANS 2010), California, USA, May 2010.
Jingbin Liu and Ruizhi Chen
Department of Navigation and Positioning
Finnish Geodetic Institute, MASALA, Finland
RSS
Become a Fan
Join our Network
Follow Us
Please send any technical comments or questions to our webmaster.