Research And Implementation Of A Compressive Sensing-Based Indoor Positioning System Using RSS

ABSTRACT:Nowadays, there is a growing interest in providing indoor location-based services in various applications on mobile smart devices. Accurate and real-time indoor localization technique has become one of the foundamental and most challenging problems.Received Signal Strength (RSS)-based localization techniques have been extensively studied as an inexpensive solution for indoor positioning systems in recent years. Compared with other costly measurement-based techniques, RSS can be easily obtained by any Wi-Fi intergrated mobile device, without any hardware modification. RSS-based localization technique estimates the user's location by only using the existing WLAN infrastructure, which covers most of the indoor environments. Thus, this dissertation focuses on the RSS-based indoor localization techqnue due to its advantage of low cost and easy to be implemented. However, due to the RSS variation that comes from the radio propataion channel, the building layout and its materials, the body absorption, and the weather, etc., there is a great challenge in obtaining location information by only using the RSS. On the other hand, the current outdoor localization techniques always cannot provide a satisfactory level of accuracy in most indoor applications.This dissertation proposes a set of novel RSS-based localization schemes in WLAN for indoor environments based on the latest technologies in signal processing, and implements the whole system on resource limited smart devices. The goal is to design an indoor localization, tracking and navigation system that performs far much better localization accuracy, and to implement the whole system on both PDA and smart phones, providing location-based services for the visually impaired in CNIB.1) The theory of Compressive Sensing (CS) and affinity propagation is applied for the indoor localization successfully.The intuition behind this technique is that location finding can be formulated as a sparse problem, thus the location can be estimated accurately from only a small number of noisy RSS measurements by only solving an l1 minimization problem based on the theory of compressive sensing. Specifically, the proposed system consists of two phases:an offline phase which collects the RSS radio map database and performs clustering using affinity propagation; and an online phase which performs the localization. During the online phase, the system consists of two stages:the coarse localization using cluster matching and the fine localization using compressive sensing. Different coarse localization approaches and AP selection schemes are further induced to mitigate the effects of RSS variations, and thus increase the reliability and robustness of the system. Experimental results indicate that the proposed system achieves an Average Root Mean Square Error (ARMSE) of 2.1m, and leads to improvements of 17.3% and 12.5% on the localization accuracy over the widely used traditional KNN and Gaussian Kernel fingerprinting methods, when 5 APs are used. The accuracy of the positioning system within 95% of the time leads to improvements of 28.4% and 10.2% over the KNN and the Gaussian Kernel methods. This dissertation further analyzes the recoverability and the reliability of the proposed localization scheme under incomplete or inaccurate RSS sampling, giving the theoretical explanation for the orthogonalization procedure that is used for the fine localization. The number of APs needed for accurate location recovery obeys M= O(log N), where N is the number of selected reference points. The complexities of different positioning schemes are further anaylized, and the proposed positioning system is implemented on resource-limited mobile devices.2) This dissertation further proposes a tracking technique that is largely different from the converntional method based on Kalman Filter (KF). This newly developed system provides indoor location-based tracking services simply and successfully, though an Information Fusion Filter, which integrates map information, and handheld device functionalities, including accelerometer and compass. By integrating the current RSS observation, the history location information and the motion model further mitigates the RSS variation and thus improves the accuracy for the coarse localzation. Kalman filter is also applied in the linear traces to smooth the current location estimation that comes from the fine localization scheme, and it is reset at the turning points. Experimental results indicate that the tracking system achieves an ARMSE of 1.2m and a maximum error of 4.2m, when 11 APs are used. The accuracy of the tracking system within 95% of the time leads to improvements of 29.4%,44.7% and 18.8% over the proposed CS stationary positioning system, the KNN plus KF tracking system, and the CS plus KF tracking system. Finally, a real-time navigation system is further developed on the devices, and relative routing schemes are proposed for the visually impaired.3) This dissertation further proposes that the same compressive sensing technique can be used to reconstruct the overall RSS radio map based on measurements at a small number of fingerprints. The spatial RSS radio map in the offline phase is considered as a 2D image. Due to the near sparse nature of the Fourier coefficient of the corresponding RSS in the frequency domain, this spatial radio map can be well recovered by only collecting RSS samples on a small number of random reference points, through a Total Variation-minimization algorithm based on the theory of compressive sensing. This provides better performance in terms of the accuracy compared with the traditional interpolation scheme. Significant reduction in the number of measured reference points can be expected.4) Finally, the whole localization, tracking and navigation system is implemented on a PDA (HP iPAQ hx4700) and a windows mobile smart phone (SamsungOMINIA-â…¡) using C#, providing location-based services for the visually impaired in CNIB to evaluate the performance. The whole system takes the gesture and speech as the human-machine interaction. The system has been tested in different indoor environments, including the Bahen building in University of Toronto, the Bayview Village shopping mall in Toronto, and the CNIB building. From the implementation, we have shown that the proposed system is able to update the location accurately in real-time on smart phones, and leads the user to the indoor destination they have choosen successfully and conveniently.