Can Computational Linguistics Be Used for Wi-Fi-Based Tracking System?

The extensive deployment of wireless infrastructure provides the possibility of locating mobile users in indoor environments using received signal strength (RSS). One approach to localization in this context is the use of Wi-Fi RSS fingerprinting and this formulation has been found to work reasonably well for location recognition of mobile phone users. For such, machine learning techniques such as hidden Markov models (HMMs) and hidden semi-Markov models (HsMM) have been extensively used to study human mobility and movements which permits the inclusion of prior knowledge about the geography of the environment alongside RSS measurements in the estimation process. Conventional HMMs, with their assumption of the Markov property, whose memory length is 1, i.e., dependency only on the last state, offer a simpler and more computationally manageable framework. Movements of typical mobile users through the quantized cells of the building, however, are usually not Markovian. HMM estimates suffer from ambiguity recognition on the movement of a Markov chain between subsets of state spaces. HsMMs outperform HMMs by allowing a semi-Markov chain with a variable sojourn time for each state, however still fail to capture the longer dependency beyond just the previous state. Combinatory Categorial Grammar (CCG) was designed to deal with the long-range dependencies in computational linguistics. In this article, we investigate the feasibility of implementing CCG as an alternative to HMM to formulate the building layout to a category of semantics and construct a walking path by CCG parsing from the RSS observations. The CCG parser allows the construction of the estimated path by recursively combining different path segments, thus building up a longer dependency between locations. The authors believe this is the first application of computational linguistics in the field of localization. Field test results demonstrate the effectiveness and reliability of the grammar-based approach which can achieve a resolution of 87.5% room-level matching accuracy based on crowdsourced fingerprints under a real large-scale university public wireless sensor network. Comparison between HMM, HsMM, and the grammar approach has been made to reveal the fact that both methods show promising performance, while the grammar approach is more reliable as HMM/HsMM can occasionally fail due to ambiguity recognition while the grammar approach consistently maintains good localization accuracy.