Project topics and materials
Get Complete Project Material File(s) Now! »
Smartphone-based indoor positioning using Wi-Fi Fine Timing Measurement protocol
Sami Huilla used the Wi-Fi RTT Android API to implement an IPS using the FTM protocol in his master’s thesis, published in 2019 [5]. In this thesis, the accuracy of the technology, as well as the implemented IPS, is evaluated at different environmental conditions. The author mentions that ranging measurement with the technology indicated a need for calibration, as large offsets in distance measurements were observed. The calibration was performed according to the Android Open Source Project Wi-Fi RTT calibration guide [10]. Two APs was set up in an indoor corridor and a robot was driven with constant speed from one AP to the other. The robot completed a round-trip six times to investigate if the phone’s orientation influenced the ranging measurements. After the calibration procedure, Huilla concludes that the ranging is mostly accurate within the tolerance stated in the calibration guide (< 2m 90th percentile absolute error). The results did, however, show that the orientation of the phone does influence the ranging accuracy, with a higher accuracy achieved when the top of the phone faced the AP.
Using ranging results from the Android API and multiple FTM responders (APs), two different methods for position estimation were implemented and compared; a Non-linear Least Squares (NLS) algorithm and an Unscented Kalman Filter approach (UKF). The two methods were evaluated in two different environments. One ideal site providing LoS to all APs and one more realistic office site with multiple NLoS conditions. The UKF achieved a mean positioning error of 0.72m and a 90th percentile error of 1.17m on the ideal site. NLS achieved a mean error of 1.01m and a 90th percentile error of 1.89m on the same site. On the second site, UKF achieved a mean error of 4.65m a 7.57m 90th percentile. This was, however, improved by assuming all measurements above 10m were subject to NLoS conditions and using a simple correction formula to mitigate the overestimated distances. With this correction method, the UKF instead achieved a mean error of 2.41m and a 4.49m 90th percentile error in the same site.
SmartPDR: Smartphone-based pedestrian dead reckoning for indoor localization
Kang et al. proposed SmartPDR; a service for indoor localization which does not require any infrastructure, but instead utilizing only inertial sensors of the smartphone [11]. In this paper, the authors argued that a practical IPS is one that should consider the absence of infrastructure or pre-trained databases. The proposed system adopted a pedestrian dead-reckoning approach, utilizing multiple inertial sensors of the smartphone such as accelerometer, magnetometer, and gyroscope. Through the use of these sensors, solutions for step event detection, heading direction estimation, and step length estimation were proposed.
To accomplish step detection, the accelerometer sensor was used. This sensor measures the inertial force acting upon the device in three different axes. Steps taken by the user were detected by reading the inertial force, with a periodical pattern triggering the step detection. The inertial forces acting upon the device along the vertical axis relative to the ground was used as the strongest indication of a step taken. Using raw sensor data to accomplish step detection was however non-trivial. One problem that arose with this approach is that the device orientation affected the measured forces along the different axes. This problem was accounted for by multiplying the acceleration vector for the local coordinate system (LCS) with the rotation matrix of the device, projecting the acceleration to a global coordinate system (GCS).
The acceleration was also filtered to remove the influence of gravity on the measurements. This was done by subtracting the gravity contribution which was identified using a high pass filter on the z-axis of and modeling all acceleration along this axis as noise. Using the filtered acceleration measurement, a step was then identified through peaks in the acceleration of the z-axis.
The authors also proposed a method for heading estimation. When holding a smartphone in the hand, the placement is unstable, and the tilt of the local coordinate system axes are normally under continuous change. The tilt of the phone affects the magnetometer reading and was compensated for by once again using the rotation matrix to transform the phone’s local coordinate system to th e global. Both magnetometer and gyroscope data were then considered to find a good estimate of heading direction, by making sure that both data sources supported new estimations. If a change in heading direction was suggested only by one of the sources, a previous estimate was used until a change was supported by both sensors.
The final method proposed is a technique for step length estimation. To accomplish this task, the authors used an earlier proposed approach that uses accelerometer data to estimate step length. More specifically, the vertical impact , defined as the difference between the current peak and the previous valley of the step acceleration, was used. According to the earlier proposed method, the step length is linearly related to the fourth square root of the vertical impact as: = β4√ , + γ
The authors, however, considered using the logarithm instead of the fourth square root. Using simulations, they found the estimation error between the two models to be nearly identical in most situations, except for the logarithmic approach performing slightly better for small reference steps and slightly worse as the reference step becomes larger. Therefore, they used a combination of the two approaches as: β4√ , + γ, for , < astep = { βlog( ) + γ, for , ≥ for some acceleration threshold (since a larger acceleration impact indicates a longer step).
Using these three techniques based on data from inertial sensors, the authors proposed the indoor localization system SmartPDR. In the testing environment, SmartPDR achieved an average location error of 1.35m, never exceeding 2m during the whole period of the experiment. Their results show that SmartPDR outperforms dead reckoning approaches only using either gyroscope or magnetometer which had location errors of up to 12m in the same testing environment . In all results, however, the starting position was assumed to be known exactly.
Non-line-of-sight identification and mitigation using received signal strength
Xiao et al. have performed extensive research on how to identify and mitigate non – line-of-sight signals for use in smartphone-based indoor positioning [12]. In this paper, three different algorithms designed to separate LoS and NLoS measurements using the received signal strength are presented. The performance of the algorithms are then compared. The authors explore several different features that can be extracted from samples of RSS measurements collected over a short period. Examples of such features are mean, standard deviation, kurtosis, skewness, Rician K factor, and χ2 goodness of fit. Mean ( ) and standard deviation ( ) are well-known features of probability distributions and are used to derive the other features.
Kurtosis is a measure of the peakedness of the probability distribution and is used with the idea that RSS measurements done in LoS generally have a more centralized distribution than samples collected in NLoS. Skewness measures the asymmetry of the probability distribution. NLoS measurements are expected to have a higher degree of asymmetry as different NLoS propagation effects can greatly affect RSS measurements. Rician K factor is defined as the ratio between the power in the direct path and the power in other scattered paths [12]. The goodness of fit (χ2) is a measure of the distance from the measured received signal strength and the underlying Rician distribution. Rician fading is a stochastic model for radio propagation in multipath conditions which models RSS values as Rice distributed. Compared to scattered signals, a signal in LoS conditions reacts significantly less to the environment which leads to different distributions of RSS and, therefore in theory, also different χ2.
The authors collected RSSI values in the experiment site using hardware which allowed querying AP RSSI values as frequently as 1000 times per second. Using the data sets collected, samples were created and the features described above were extracted. Using these features, three classifiers were developed. Two were based on supervised machine learning and one was based on hypothesis testing . The first algorithm is a Least Squares Support Vector Machine Classifier (LS-SVMC). The authors motivate this choice through ease of training and quality of generalization. Next, a Gaussian Processes Classifier (GPC) was chosen for its proven capabilities, despite a low computational complexity. This is a quality of interest especially for mobile applications. The last algorithm is based on Hypothesis Testing Classification (HTC) using a likelihood ratio test where the two hypotheses are defined as: h ≤ ℎ > ℎ
In Equation 1.4, ( ( )| ) is the probability distribution function of feature ( ) in condition c. With this approach ℎ is set to 1. They remark that the joint distribution of the features would have been optimal but would require calculating convolutions of probability distribution functions which comes with an extraordinarily high computational cost. However, according to empirical tests conducted, only 2.02% of the classifications made by the sub-optimal solution differ from that of the optimal approach which implies that the trade-off between computational costs and analytical accuracy is not very high.
For NLoS mitigation, the method is very similar for the machine learning approaches, but instead of a binary classification problem, it becomes a problem of determining a distance given a sample of RSS measurements. The data sets used for training were collected at specific locations in the test site, where the distance to each AP could be calculated and then be used as training data together with the RSS values at each position. For the hypothesis testing approach, mitigation was instead accomplished by using two different propagation models to estimate the distance from RSS values depending on the determined LoS/NLoS condition.
The classification algorithms were tested in an office environment on two different occasions. One on a weekend when there were no other people in the building (static) and one under more normal, busy circumstances (dynamic). Quite anticipated, all algorithms showed a much higher misclassification error in the dynamic environment.
LS-SVMC achieved a best (lowest) misclassification error of 0.0648 using only μ and Rician K factor as features. GPC achieved a best misclassification error of 0.0599 using , Rician K factor, and χ2 goodness of fit as features. HTC had the worst accuracy and achieved a best misclassification error of 0.1568 using , Rician K factor, and kurtosis as features. In the dynamic environment, the best misclassification rates achieved were instead 0.1401, 0.1301, and 0.3744 for the three algorithms respectively. Mitigation wise, the machine learning algorithms also outperformed the approach based on hypothesis testing. Both such algorithms were shown to improve distance estimation accuracy to around 0.86m as opposed to over 6.6m using conventional propagation models. In comparison, the hypothesis testing-based mitigation approach could achieve an accuracy of 3.5m.
Method
This section aims to describe the method used to achieve the purpose of the thesis. The thesis is an empirical study on possible improvements to smartphone -based indoor localization using Wi-Fi RTT. The empirical investigation method used to answer the research questions posed was a controlled experiment. Earlier research has established the possibility of using FTM for indoor localization with good accuracy, but their results have shown that there is still room for performance enhancements in situations when a direct line of sight does not exist between the smartphone and one or multiple FTM responders [5]. Two methods to potentially further improve the robustness and accuracy of Wi-Fi RTT based IPSs in such situations have been identified in previously published work. First, a method for detecting NLoS conditions and adjusting such measurements accordingly, has earlier managed to improve the performance of a Wi-Fi-based IPS [12]. Second, supplying the localization algorithm with motion sensor data through sensor fusion, such as when and in which direction a step is taken, has also been found to have a positive impact on positioning performance [8], [11]. This type of relative positioning technique is called dead reckoning. Both techniques have individually been proven to work well in other indoor localization systems, but how they affect the performance of a Wi-Fi RTT based IPS when used together has at the time of writing, to the best of the author’s knowledge, yet not been investigated.
Pre-study informal literature review
Before any design and implementation, an informal literature review was performed within a wide range of different topics. These topics include existing methods for indoor positioning, the accuracy of Wi-Fi RTT, filtering within control theory, as well as signal theory and LoS/NLoS detection. In addition to literature specific to the topic of indoor localization, literature on research methodology within the field of software engineering was also reviewed. The status of related research shows that the field of indoor positioning has been a popular area of research for many years, but that the Wi – Fi RTT technology is a relatively new topic within the field that still has room for innovation.
Pre-study experiments
To understand the characteristics of Wi-Fi RTT and how the technology behaves in different situations, a more practical pre-study was performed. In this phase, different explorative experiments using the technology were conducted to get a better understanding of the ranging accuracy and the difficulties that arise with NLoS conditions.
Localization performance metrics
Many systems for indoor positioning have been proposed, and with them, different methods for measuring and evaluating relevant performance metrics. To determine the quality of an IPS, several different metrics can be used. Al-Ammar et al. list and describe the most common metrics used to evaluate the performance of an IPS [13]. Some of these include accuracy, availability, coverage area, scalability, cost, and privacy. While many of these metrics are very interesting for commercial systems, only accuracy will be measured and used in the evaluation method of this thesis as the other metrics are irrelevant to the research questions posed. Accuracy (or location error) measures how close the estimated position of the IPS user is compared to the actual position [14]. Therefore, the accuracy of an IPS is the average Euclidean distance between the estimated position and the true position. Liu et al. also argues that precision is an important metric to look at when evaluating an IPS [14]. Precision in the context of indoor positioning is a measurement of the variation of performance (or robustness) and is often presented using the Cumulative Distribution Function (CDF) of the distance errors [14]. Instead of just considering the mean, precision considers the variation in distance errors expressed in the percentile format. Accuracy and precision according to the stated definitions above are the IPS performance metrics considered in this thesis.
Ground truth determination
To determine the positioning error of an IPS along a certain path, a ground truth must be determined, meaning a trace of true positions of the IPS device at each measurement time point. This can be achieved in multiple ways. A common method is to use another IPS known to have very high accuracy. Huilla used a remote-controlled robot with a known starting position that generated a true path using a lidar sensor [5]. In this work the ground truth was provided by an application developed by Senion. A mobile application was used to record sensor data along predefined paths. In a post -processing step the positions of the RTT measurements were computed with high accuracy by utilizing the motion sensor data and knowledge about the predefined path. This result has been used as ground truth and contains the RangeResult objects (see Section 6.1.1 for a detailed description of the properties of this object), together with the two additional properties: – logTimeMs1970: Timestamp of when the ranging result was received in Unix Timestamp format (milliseconds since Jan 01, 1970). This is collected for interpolation purposes and for having an absolute timestamp in addition to the timestamp natively provided by the RangeResult object which is relative to the device boot time.
– position: Object composed of the local x and y coordinates corresponding to the ground truth at the time of measurement.
Main content and organization of the thesis
The remainder of the thesis is structured as follows. First, a theoretical background relevant to the field of indoor positioning is presented in Chapter 2. In Chapter 3, the characteristics of Wi-Fi RTT as a ranging technology are investigated and the results from the pre-study experiments are presented. Next, the requirements of the implemented system are stated in Chapter 4. In Chapter 5, the high-level design of the implemented system is presented. Chapter 6 describes the details of the system implementation and the testing procedure. Chapter 7 presents the results of the system evaluation, which are also further discussed in Chapter 8. In chapter 9, the resulting conclusions of the thesis are presented.
Table of contents :
ABSTRACT
GLOSSARY
TABLE OF FIGURES
CHAPTER 1 INTRODUCTION
1.1 BACKGROUND
1.2 THE PURPOSE OF THE PROJECT
1.3 RESEARCH QUESTIONS
1.4 THE STATUS OF RELATED RESEARCH
1.4.1 Fusion of Wi-Fi, smartphone sensors and landmarks using the Kalman filter for indoor localization
1.4.2 Smartphone-based indoor positioning using Wi-Fi Fine Timing Measurement protocol
1.4.3 SmartPDR: Smartphone-based pedestrian dead reckoning for indoor localization
1.4.4 Non-line-of-sight identification and mitigation using received signal strength 8
1.5 METHOD
1.5.1 Pre-study informal literature review
1.5.2 Pre-study experiments
1.5.3 Localization performance metrics
1.5.4 Ground truth determination
1.6 MAIN CONTENT AND ORGANIZATION OF THE THESIS
CHAPTER 2 THEORY
2.1 NON-LINE-OF-SIGHT PROPAGATION
2.2 RANGING TECHNIQUES
2.2.1 Received Signal Strength
2.2.2 Time difference of arrival
2.2.3 Time of flight
2.2.4 Wi-Fi RTT
2.3 POSITION ESTIMATION TECHNIQUES
2.3.1 Trilateration
2.3.2 Triangulation
2.3.3 Kalman filter
2.3.4 Fingerprinting
2.4 EMPIRICAL RESEARCH IN SOFTWARE ENGINEERING
CHAPTER 3 WI-FI RTT CHARACTERISTICS
3.1 STATIONARY MEASUREMENTS
3.1.1 LoS measurements
3.1.2 NLoS measurements
3.2 MOBILE MEASUREMENTS
3.2.1 LoS measurements
3.2.2 NLoS measurements
3.3 CONCLUSIONS
CHAPTER 4 SYSTEM REQUIREMENT ANALYSIS
4.1 THE GOAL OF THE SYSTEM
4.2 THE FUNCTIONAL REQUIREMENTS
4.2.1 Logging
4.2.2 Wi-Fi RTT
4.2.3 Device inertial sensor information
4.2.4 NLoS/LoS detection
4.2.5 Offline processing of data
4.2.6 Position estimation
4.2.7 User interface
4.3 THE NON-FUNCTIONAL REQUIREMENTS
4.4 BRIEF SUMMARY
CHAPTER 5 SYSTEM DESIGN
5.1 MOBILE APPLICATION DESIGN
5.2 POST-PROCESSING APPLICATION DESIGN
CHAPTER 6 SYSTEM IMPLEMENTATION AND TESTING
6.1 SOFTWARE AND HARDWARE
6.1.1 Android Wi-Fi RTT API
6.1.2 Smartphone
6.1.3 Wi-Fi RTT access points
6.2 LOCALIZATION IMPLEMENTATION
6.2.1 Baseline implementation
6.2.2 First extension: Sensor fusion with dead reckoning
6.2.3 Second extension: LoS/NLoS detection
6.2.4 Implementation overview
6.3 KEY PROGRAM FLOW CHARTS
6.3.1 Diagram of localization procedure
6.3.2 Ranging process
6.4 KEY INTERFACES OF THE SOFTWARE SYSTEM
6.5 SYSTEM EVALUATION
6.5.1 Measurement calibrations
6.5.2 Evaluation environments
6.5.3 Evaluation hypotheses
6.6 BRIEF SUMMARY
CHAPTER 7 RESULTS
7.1 PATH A
7.2 PATH B
CHAPTER 8 DISCUSSION
8.1 WI-FI RTT RANGING
8.2 SYSTEM EVALUATION
8.3 METHOD AND IMPLEMENTATION
8.4 ETHICAL ASPECTS OF INDOOR POSITIONING
CHAPTER 9 CONCLUSION
9.1 FUTURE WORK
REFERENCES
