A Hidden Markov Model for Localization Using Low-End GSM Cell Phones

Mohamed Ibrahim, Moustafa Youssef

TL;DR

This paper introduces a novel Hidden Markov Model (HMM) approach for localizing low-end GSM cell phones using only the signal strength (RSSI) of the associated cell tower. By leveraging historical RSSI data, their system significantly improves localization accuracy, especially in rural areas with sparse cell tower coverage, outperforming existing methods.

What Problem Does This Paper Address?

Ubiquitous location-based services (LBS) are increasingly desirable, but accurately determining a cell phone's location is challenging, especially for low-end devices. While GPS and Wi-Fi offer good accuracy, they aren't available on all phones or in all locations. GSM-based localization is attractive because it works on virtually all GSM phones and consumes minimal power. However, traditional GSM localization techniques often rely on signal strength from multiple neighboring cell towers, information that is not accessible on many low-end phones. Furthermore, in many regions, cell tower density is low, making it difficult to get reliable location data even with multiple tower signals. This paper tackles the problem of achieving accurate GSM localization using only the RSSI of the single cell tower the phone is currently connected to, a common limitation for many devices and environments.

Methods

The core of the proposed solution is a Hidden Markov Model (HMM). The HMM is designed to work in two phases:

  • Offline Phase: This phase involves constructing the HMM and estimating its parameters. The physical area of interest is divided into a grid of cells, where each grid cell represents a "state" in the HMM. The "observations" are pairs of (associated cell tower ID, RSSI).
  • State Transition Probabilities (A): These are estimated by assuming users move between adjacent grid cells. The probabilities are set uniformly across neighboring cells, reflecting a general assumption of movement.
  • Observation Probabilities (B): To estimate the probability of observing a specific RSSI from the associated cell tower within a given grid cell, the authors use data collected during "war driving" (driving around and recording cell tower information). They build a histogram of RSSI values for the associated cell tower within each grid cell.
  • Initial State Distribution (π): If not known, the steady-state distribution of the states is used as an estimate.
  • Online Phase: During this phase, the HMM uses the sequence of observed (cell tower ID, RSSI) pairs from the associated tower to estimate the most probable sequence of states (locations). The Viterbi algorithm is employed to find this most probable sequence, and the final state in the sequence is taken as the estimated location. The key innovation here is leveraging the history of RSSI readings from the single associated tower to infer location.

Datasets

The authors collected data for two distinct testbeds:

  1. Rural Testbed: The Smart Village in Cairo, Egypt, representing a typical rural area.
  2. Urban Testbed: A 5.5 Km² area in Alexandria, representing a typical urban area.

Data was collected using T-Mobile G1 phones running Android 1.6, equipped with GPS receivers for ground truth. The data included cell tower ID, signal strength (RSSI), GPS location, and timestamps. Importantly, for evaluation, they simulated low-end phones by not using information from neighboring cell towers, relying solely on the associated tower's data. They collected separate training and testing datasets for each testbed.

Key Insights and Ideas

  • Leveraging RSSI History is Crucial: The paper demonstrates that even with limited information (only the associated cell tower's RSSI), the temporal sequence of RSSI readings provides significant clues for localization. This history allows the HMM to smooth out noise and infer location more accurately.
  • HMMs are Well-Suited for Sequential Data: The HMM framework naturally handles the sequential nature of cell tower observations as a user moves, making it an effective choice for this problem.
  • Grid Cell Size Trade-off: The size of the grid cells used to discretize the physical space presents a trade-off between accuracy and computational overhead. Larger cells reduce overhead but can decrease accuracy due to less precise location estimation within a cell.
  • Rural Areas Benefit Most: The proposed HMM approach shows the most dramatic improvements in rural areas, where cell tower density is low and traditional methods struggle. This highlights the system's effectiveness in challenging environments.

Key Results

The paper's HMM-based system achieved significant improvements in localization accuracy compared to other RSSI-based methods:

  • Rural Areas: Achieved a median error of 93.85 meters, representing an enhancement of at least 156% over existing techniques.
  • Urban Areas: Achieved a median error of 50.34 meters, representing an enhancement of at least 68% over existing techniques.

The authors also found that increasing the observation sequence length (T) generally improves accuracy but at the cost of increased latency. They fixed the grid cell size at 400 meters for both testbeds, as this provided the best accuracy.

Limitations and Future Work

  • Limitations:
    • The system's performance is sensitive to the grid cell size, requiring careful tuning.
  • The accuracy is still affected by the density of cell towers and the variability of RSSI signals.
  • The paper notes that the transition matrix could be more sophisticated by incorporating road network information for more realistic movement modeling.
  • Future Work:
    • The authors suggest that incorporating road network information into the transition matrix could further improve accuracy.
  • Exploring other HMM variants or machine learning techniques could also be beneficial.
  • Investigating how to adapt the system to dynamic changes in cell tower configurations or signal characteristics would be valuable.

Summary updated

Abstract

Research in location determination for GSM phones has gained interest recently as it enables a wide set of location based services. RSSI-based techniques have been the preferred method for GSM localization on the handset as RSSI information is available in all cell phones. Although the GSM standard allows for a cell phone to receive signal strength information from up to seven cell towers, many of today's cell phones are low-end phones, with limited API support, that gives only information about the associated cell tower. In addition, in many places in the world, the density of cell towers is very small and therefore, the available cell tower information for localization is very limited. This raises the challenge of accurately determining the cell phone location with very limited information, mainly the RSSI of the associated cell tower. In this paper we propose a Hidden Markov Model based solution that leverages the signal strength history from only the associated cell tower to achieve accurate GSM localization. We discuss the challenges of implementing our system and present the details of our system and how it addresses the challenges. To evaluate our proposed system, we implemented it on Android-based phones. Results for two different testbeds, representing urban and rural environments, show that our system provides at least 156% enhancement in median error in rural areas and at least 68% enhancement in median error in urban areas compared to current RSSI-based GSM localization systems.
BibTeX
@inproceedings{ibrahim2011hidden,
  author = {Mohamed Ibrahim and Moustafa Youssef},
  title = {{A Hidden Markov Model for Localization Using Low-End GSM Cell Phones}},
  booktitle = {ICC},
  year = {2011},
  url = {https://openreview.net/forum?id=IqLh1ZZqGh},
}
Figure