Towards an open global Wi-Fi indoor positioning system via implicit crowdsourcing

Location-based Services (LBSs) are important building blocks for a wide spectrum of context-aware applications. The Global Positioning System (GPS) has provided almost ubiquitous positioning services in outdoor environments and enabled many outdoor LBSs such as routing navigation, location check-in and field analysis. However, the indoor LBSs equivalents, e.g., routing the visually-impaired, are not yet pervasively available due to many unaddressed challenges in indoor positioning system deployments. The overarching goal of this project is to develop practical systems to address such challenges and finally build an Open Global Indoor Positioning System (OGIPS). OGIPS is a supplementation to GPS indoors and the combination of OGIPS and GPS is anticipated to provide truly global positioning services to virtually anyone. The Wi-Fi Positioning System (WPS) is a dominant enabling technology of OGIPS for its sheer prevalence in pervasiveness, reliability and performance. This doctoral study project identified three major challenges for building OGIPS based on WPSs and proposed corresponding solutions. The first challenge is how to deploy WPSs with zero cost. WPS deployment requires Radio Map calibration, which, in current industrial practice, relies on high-cost scene analysis. To reduce the deployment cost, it is possible to leverage the free Crowdsourced data. In fact, an enormous amount of Wi-Fi signal measurements could be collected by Implicit Crowdsourcing, that is, collecting unlabeled data in an unobtrusive manner during normal courses of the smartphone users, e.g., strolling around shopping malls. The challenges is then reformulated as how to perform Radio Map calibration via Implicit Crowdsourcing. This project formulates the targeted problem with a novel Hyper-Graph Matching framework, which lends various merits to the system in terms of scalability, extendability and robustness. The elegant problem formulation allows the system to exploit the accomplishments of Graph Matching researches in the past decades, especially in Computer vision. We designed, implemented the system, HyperLoc, and validated it with extensive experiments with both simulated and real-world data. Experimental results indicates that HyperLoc is able to construct zero-cost WPSs in real-world settings. The overall positioning performance of HyperLoc, a zero-cost system, is comparable to high-cost manually-calibrated WPSs . To our knowledge, HyperLoc is the first work to apply Graph Matching techniques to Radio Map calibrations and the first work that develops a practical and scalable zero-cost WPS implementation in real-world settings. The second challenge is how to maintain WPSs performance over time with zero cost. The Radio Map describes the signal environment in relation to the physical environment of a venue. However, the relation often changes substantially upon changes of radio propagation patterns, caused by many factors, e.g., change of the layout of the venue. To maintain consistent and reliable performance, Radio Maps must be versionized and re-calibrated. Here we arrive at the second challenge, that is, how to effectively manage Radio Map versioning with zero cost. This project proposed a novel Radio Map versioning control system, RAEDS, by detecting system anomalous events that degrade indoor positioning performance substantially. The system generalizes arbitrary Radio Map degrading factors as Radio Map anomalous events, which could be modeled and hence detected using state-of-the-art event detection techniques. We designed, implemented and evaluated RAEDS with both synthetic and real-world experiments. The results showed that RAEDS is able to detect anomalous events accurately with a low false alarm rate. To our knowledge, RAEDS is the first work to apply advanced event detection techniques in WPS health monitoring for system versioning control. The combination of HyperLoc and RAEDS is anticipated to enable a practical zero-cost WPS in real-world settings. However, many challenges still present. The OGIPS architecture shall be carefully designed to accommodate the domain-specific requirements of OGIPS in addition to the general requirements of highly-available and scalable systems. Hence the third challenge is how to architect OGIPS to meet the desired requirements. Practical design goals are discussed comprehensively and a proposed design of the architecture and implementations is described in details. Guidelines and recommendations in system implementations were made. More importantly, the proposed OGIPS design is orthogonal to HyperLoc and RAEDS. That means OGIPS is able to flexibly integrate other zero-cost WPSs implementations at high-level. This merit allows other researchers to reuse the proposed architecture with their proprietary zero-cost WPS implementations. The proposed solutions in this work are expected to pave the path towards building OGIPS in real-world settings. Future research efforts will be devoted to improving the adaptiveness and robustness of the proposed systems in terms of device heterogeneity, adaptiveness to user patterns and insufficient data. Finally, the findings of this thesis are expected to contribute to the research communities sharing the same conviction, that is, to make the indoor positioning service accessible to virtually anyone, anytime and anywhere