Cost-Effective Algorithms to Obtain, Predict and Apply Location Information for Mobile Computing

Advisor: Qiao, Chunming

Location based service (LBS) refers to the applications that depend on a user's location to provide services in various categories including navigation, tracking, advertising, healthcare and billing. With the explosive growing market of mobile phones in recent years, its demand is increasing with new ideas and becoming an irreplaceable part of life. A typical LBS is composed of three parts: a device running positioning software application, the end user's mobile device, and the communication network. The positioning technologies have a major influence on the performance, reliability, and privacy of LBSs, systems, and applications. In this study, their aims are to provide cost-efficient and reliable positioning techniques, and further to address challenges associated with applications in large indoor environments using WiFi instead of GPS signals.

More specifically, indoor localization algorithms can be coarsely classified into two categories: trilateration and fingerprinting. Trilateration estimates the position of an object by measuring its distance from at least three known reference points. However, it is challenging to obtain accurate ranging measurements with commercial-off-the-shelf (COTS) devices. While fingerprinting approaches collect features, e.g., Received Signal Strength Indicator (RSSI) readings from multiple Access Points (APs) at known locations, to establish an RSSI map; and then find a matched location by comparing the RSSI map and an online RSSI measurement. However, it introduces tedious pre-deployment effort and is unscalable especially for large indoor environments.

To address the above challenges, the authors first build the RSSI map by using an RSSI propagation model with only a few training locations. In terms of location searching, the authors take the error from RSSI modeling into consideration, exploit information of unobserved APs and propose a novel density-based clustering method.

To extend these purely RSSI based systems, the authors exploit movement of mobile clients and restrictions added by floor plans to improve the localization accuracy. The authors then utilize recursive Bayesian filtering to fuse such information from multiple resources and infer the posterior distribution of the location. Nevertheless, the challenges remain: first, the sensors from COTS devices are less powerful and can give inaccurate measurements due to interference from surrounding environment (e.g. magnetic sensor); second, grid-based filters have a more accurate approximation of the location distribution compared to particle filters at small scale, they suffer from a significant amount of computing resources caused by high grid resolution, especially for large indoor environments. To address these new challenges, the authors employ a direct filtering technique through Kalman filters to improve the accuracy of heading measurements. In addition, the authors develop a novel asymmetric grid-based filter which discretizes grid approximation with high resolution to capture the uncertainty of motion sensor data, while utilizes relatively coarser grids to represent the RSSI observation model at the same time. The authors evaluate their systems through intensive experiments over two real-world data sets, and the results demonstrate that their system achieves considerable localization accuracy at a low training cost for a large indoor area.

Finally, the authors address two specific topics related to LBS in practice. In the first topic, the authors study how to predict the mobility of client. Particularly, the authors discuss location prediction in terms of WiFi location represented by fingerprints, especially when only a little historical data is available. To solve such problem, the authors develop a graph-coupled location prediction framework considering the connectivity between WiFi locations and a novel mobility model. In the second topic, the authors consider applying the detection of co-location events in epidemics, where droplets from the infectious disease can spread through close proximity interactions (CPIs). Specifically, the authors analyze the Susceptible-Infected-Recovered (SIR) model in complex networks when non-trivial network correlation is present. Contrary to previous numerical solutions, the authors directly characterize the degree correlation through the exponent of conditional degree distribution and derive its impact on the epidemic threshold and prevalence in closed form.