Correlating mobility with social encounters: Distributed localization in sparse mobile networks

Most existing connectivity-based localization algorithms require high node density which is unavailable in many large-scale sparse mobile networks. By analyzing large datasets of real user traces from Dartmouth and MIT, we observe that user mobility exhibits high spatiotemporal regularity and, more importantly, that user mobility is strongly correlated with the user's social encounters (including so called Familiar Strangers). Motivated by these important observations, we propose a distributed localization scheme called SOMA that is particularly suitable for sparse mobile networks. To exploit the correlation between mobility and social encounters, we formulate the localization process as an optimization problem with the objective of maximizing the probability of visiting a sequence of locations when the user witnesses the given social encounters at different time. Employing the Hidden Markov Model (HMM), we design an efficient algorithm based on dynamic programming for solving the optimization problem. SOMA is fully distributed, in which each user only makes use of the connectivity information with other users. Experimental results based on large-scale real traces demonstrate that SOMA achieves much smaller localization error than many state-of-the-art localization schemes, but requires minimal running time.