PaperlayerView exact revision on arXiv

Source-linked AI summary

CellSense: An Accurate Energy-Efficient GSM Positioning System

Mohamed Ibrahim, Moustafa Youssef

arXiv:1110.3425v1cs.NI

TL;DR

CellSense addresses the challenge of accurate, energy-efficient GSM localization using widely available phone signals. It introduces probabilistic RSSI fingerprinting with gridding and a hybrid deterministic refinement phase. In rural and urban testbeds, the hybrid system improves accuracy over state-of-the-art RSSI-based methods while reducing running time.

  • Problem

    Cell-phone localization is needed for context-aware applications, but GPS, WiFi, and augmented sensors have availability, coverage, hardware, or energy limitations.

  • Method

    CellSense uses probabilistic RSSI-based GSM fingerprinting with gridding, extended by a hybrid technique that adds deterministic estimation.

  • Results

    CellSense-Hybrid achieves at least 108.57% higher accuracy in rural areas and 89.03% in urban areas, with more than 5.4 times running-time savings over state-of-the-art RSSI-based techniques.

  • Takeaways & Limitations

    CellSense-Hybrid maintains comparable accuracy to CellSense with substantially lower computational complexity, and its accuracy remains consistent across grid sizes and testbeds.

Abstract

from arXiv · show

Context-aware applications have been gaining huge interest in the last few years. With cell phones becoming ubiquitous computing devices, cell phone localization has become an important research problem. In this paper, we present CellSense, a prob- abilistic RSSI-based fingerprinting location determi- nation system for GSM phones. We discuss the chal- lenges of implementing a probabilistic fingerprinting localization technique in GSM networks and present the details of the CellSense systemand how it addresses these challenges. We then extend the proposed system using a hybrid technique that combines probabilistic and deterministic estimation to achieve both high ac- curacy and low computational overhead.Moreover, the accuracy of the hybrid technique is robust to changes in its parameter values. To evaluate our proposed system, we implemented CellSense on Android-based phones. Results from two different testbeds, represent- ing urban and rural environments, for three differ- ent cellular providers show that CellSense provides at least 108.57% enhancement in accuracy in rural areas and at least 89.03% in urban areas compared to the current state of the art RSSI-based GSM localization systems. In additional, the proposed hybrid technique provides more than 6 times and 5.4 times reduction in computational requirements compared to the state of the art RSSI-based GSM localization systems for the rural and urban testbeds respectively.We also evaluate the effect of changing the different system parameters on the accuracy-complexity tradeoff and how the cell towers density and fingerprint density affect the system performance.

I. Introduction

CellSense addresses the need for broadly available, energy-efficient GSM localization by introducing probabilistic RSSI fingerprinting and a hybrid extension. It evaluates these techniques across rural and urban testbeds and studies their performance parameters.

  • Motivation: GSM localization is broadly available, worldwide, and energy-efficient compared with GPS, WiFi, and augmented-sensor alternatives.GSM-based localization is available on 80–85% of today’s cell phones and requires minimal additional energy.
  • Contribution: CellSense introduces probabilistic fingerprinting for GSM localization and extends it with a hybrid probabilistic-deterministic technique.The hybrid technique is designed to combine high accuracy with low computational overhead.
  • Contribution: Gridding reduces probabilistic fingerprint-construction overhead by dividing the area into cells and constructing histograms per grid cell.Increasing grid-cell length can reduce fingerprint size and improve scalability.
  • Evaluation: The evaluation compares CellSense with deterministic, model-based, and Google MyLocation systems across rural and urban testbeds and three cellular providers.The study also examines how system parameters affect performance.
  • Related approaches: The paper evaluates multiple GSM localization approaches, including time-based, angle-of-arrival, cell-ID, WiFi, augmented-sensor, and signal-strength systems.These categories frame the comparison with CellSense.

B. Angle-of-Arrival based Systems

Alternative localization systems rely on specialized hardware, infrastructure, or sensors that limit deployment. RSSI-based GSM localization instead uses widely available signals and fingerprint matching, but requires an offline RF fingerprint.

  • Angle-of-Arrival based Systems: Angle-of-arrival systems triangulate transmitter location from estimated signal angles but typically require specialized antenna hardware.This hardware requirement makes large-scale deployment on cell phones less attractive.
  • Cell-ID based Systems: Cell-ID systems use the associated cell tower, usually the one with strongest RSSI, to provide efficient but coarse-grained localization.They require a database of cell-tower locations.
  • WiFi-based Systems: WiFi-based localization is limited by WiFi-chip availability and incomplete city-wide coverage.The passage notes that WiFi chips are unavailable in the majority of cell phones.
  • Augmented Sensors-based localization: Augmented-sensor localization is constrained because accelerometers and compasses are not widely used in cell phones.Sensor-based approaches can also accumulate displacement and direction error.
  • RSSI-based Systems: RSSI-based systems use readily available GSM measurements, work worldwide, and consume minimal additional energy, but require an RF fingerprint.The fingerprint stores RSSI measurements from different base stations at locations in the area of interest.
  • RSSI-based Systems: Deterministic fingerprinting compares an unknown RSSI vector with stored vectors and averages the K nearest fingerprint locations.It requires a larger search database than cell-ID localization but provides higher accuracy.

1) Deterministic Fingerprinting Techniques:

Model-based localization uses a Gaussian process to infer signal-strength behavior from fingerprint data, while other systems emphasize hardware-free probabilistic GSM localization. The model-based approach can densify fingerprints but increases computation and depends on model fit.

  • 2) Modeling-based Techniques:: A Gaussian process estimates posterior distributions over signal-strength functions from fingerprint training data.The covariance between function values depends on input locations through a kernel function.
  • 2) Modeling-based Techniques:: The squared exponential kernel models how correlation between function values decreases with distance between locations.Its length scale determines how strongly the correlation drops off.
  • 2) Modeling-based Techniques:: A Gaussian-process estimator still requires a fingerprint to estimate model parameters and compute predictions at arbitrary locations.The fingerprint is less sparse than in some alternatives but remains necessary.
  • 2) Modeling-based Techniques:: Model-based interpolation can densify a sparse fingerprint, but it substantially increases computational requirements and may lose accuracy when the assumed model mismatches the environment.The training samples must still be collected through war driving, so fingerprinting overhead is not actually saved.
  • Comparison with alternatives: CellSense avoids specialized hardware and is intended to operate across more phones and coverage areas than TOA, AOA, WiFi, and augmented-sensor systems.Its probabilistic approach is presented as more accurate than deterministic fingerprinting, with minimal computational requirements.

III. The CellSense System

CellSense combines offline probabilistic RSSI fingerprint construction with online location estimation for GSM phones. Its gridding approach reduces fingerprinting overhead and improves scalability by representing measurements within grid cells.

  • System overview: CellSense operates through offline fingerprint construction and online tracking phases.The offline phase builds RSSI histograms, while the online phase estimates the user’s most probable fingerprint location.
  • System overview: RSSI samples are collected from the connected tower and up to six neighboring towers through the phone’s GSM modem.The Location API exposes the estimated position to applications.
  • Mathematical model: The system models each location using an RSSI vector containing readings from different cell towers.The signal-strength space is q-dimensional, with one vector entry per tower.
  • Offline phase: Gridding constructs each cell tower’s RSSI histogram from all fingerprint points inside a grid cell rather than from each individual point.The center of mass of the points in a grid cell represents that cell.
  • Offline phase: The gridding approach removes the need to stop at every fingerprint location and allows the fingerprint size to decrease by increasing grid-cell length.This reduces construction overhead while improving scalability.

D. Online Phase

During online tracking, CellSense selects the fingerprint location most probable for the received RSSI samples. It can also combine the K most probable cells through probability-weighted averaging.

  • Online estimation: The online estimator seeks the fingerprint location with maximum probability given the received signal-strength vector.Bayes’ theorem converts the posterior objective into a likelihood calculation when locations are equally probable.
  • Online estimation: The likelihood P(s|l) is computed from the RSSI histograms constructed during the offline phase.The estimator evaluates this likelihood for each candidate location and returns the location with the highest value.
  • Online estimation: Using successive samples from each signal stream can improve location-estimation performance.The formulation represents the jth sample from the ith stream as s_i,j.
  • Online estimation: A weighted average of the K most probable fingerprint cells can provide an alternative location estimate.Each cell is weighted by its probability, and the effect of K is evaluated experimentally.

E. The CellSense-Hybrid Technique

CellSense-Hybrid combines probabilistic rough estimation with deterministic refinement to preserve accuracy while reducing computational requirements. Its design exploits the tradeoff between grid-cell size, accuracy, and complexity.

  • Accuracy-complexity tradeoff: Larger grid cells reduce computational complexity but lower localization accuracy.Increasing cell size places more fingerprint points farther from the cell centroid, increasing estimation error.
  • Hybrid approach: CellSense-Hybrid uses a probabilistic rough-estimation phase followed by deterministic refinement within the selected cell.The refinement phase uses K-nearest neighbors in signal-strength space to identify the closest fingerprint point.
  • Hybrid approach: Using fewer samples lowers computational requirements, while refinement compensates for the resulting accuracy reduction.This enables high accuracy and low computational requirements at low grid-cell lengths.
  • Evaluation: The evaluation compares localization accuracy and running time across rural and urban testbeds using three cellular providers.The experiments use Android phones, separate training and testing datasets, and GPS ground truth.
  • Evaluation: The experiments report calibration times of 22.34 minutes in the rural area and 48.48 minutes in the urban area.The wardriving process visited each point once, and repeated visits did not improve accuracy in the authors’ experience.

B. Effect of Changing Parameters

CellSense performance depends on grid size, sample count, averaged locations, and deployment density. The reported parameter effects expose accuracy–scalability trade-offs and testbed-specific optima.

  • Deployment parameters: Higher cell-tower density improves accuracy, while default parameter values are selected for best performance.The parameter study covers grid length, sample count, averaged locations, provider, tower density, and fingerprint density.
  • Grid cell length: Increasing grid cell length decreases median localization accuracy because points become farther from each cell’s centroid.Cell lengths up to 200 m2 retain accuracy comparable to very small cells in both testbeds.
  • Grid cell length: Urban accuracy exceeds rural accuracy for grid lengths up to 450m, reflecting higher urban cell-tower density.Beyond this range, urban performance drops significantly as some towers no longer cover entire cells.
  • Number of samples: Median-error accuracy rises with Ns until an optimum, reaching N = 8 in rural areas and N = 14 in urban areas, then declining.The decline reflects the opposing effects of additional information and user movement during sampling.
  • Averaged locations: Increasing K improves performance until the estimate saturates, indicating that the most probable location estimate is already accurate.

4) Effect of changing the cell towers density:

Accuracy depends on both cell-tower density and fingerprint density, with provider-specific behavior shaped by the same deployment factors.

  • Cell-tower density: Accuracy increases as cell-tower density increases.The study varies density by dropping a specified percentage of cell towers.
  • Fingerprint density: Retaining more fingerprint samples improves accuracy, and collecting only 8 points per cell provides good accuracy in both testbeds.Reducing fingerprint density has less effect than reducing cell-tower density.
  • Network providers: Provider accuracy is proportional to cell-tower density, with Provider 2 weaker in rural areas at density 1.00 versus 4.83 and 5.63 for the other providers.
  • Network providers: Provider 2 reaches an optimal grid cell length at 600m because larger cells first improve histogram quality and then reduce fingerprint density.This behavior is not observed for higher-density providers, where the density-related decline dominates.

C. Results for the Hybrid Technique

CellSense-Hybrid combines probabilistic and deterministic estimation to trade a small accuracy loss for substantially lower runtime and computational cost. Its runtime has competing grid-size effects, producing an interior minimum.

  • Accuracy and runtime: CellSense accuracy degrades as grid cell length increases, whereas CellSense-Hybrid is evaluated as a refinement-based alternative.
  • Accuracy and runtime: The CellSense-Hybrid runtime is minimized at G = 70 because increasing grid size reduces first-phase cells but increases second-phase fingerprint points.
  • Comparison with other techniques: At least 108.57% rural and 89.30% urban accuracy enhancement is reported over other techniques.CellSense-Hybrid accuracy remains consistent across the two testbeds, while its loss relative to CellSense yields runtime gains.
  • Comparison with other techniques: The proposed techniques achieve at least 506.21% rural and 440.19% urban running-time enhancement over other techniques.CellSense-Hybrid provides about three to five times running-time enhancement compared with CellSense.

3) Complexity Analysis:

The complexity analysis contrasts CellSense, deterministic methods, Gaussian processes, and CellSense-Hybrid across localization-error and runtime comparisons. CellSense-Hybrid reduces work by confining refinement to the most probable cell.

  • Evaluation views: The figures compare localization-error distributions and running time across rural and urban testbeds, including CellSense, CellSense-Hybrid, and competing techniques.Running-time comparisons use a log scale.
  • Complexity formulas: CellSense requires O((qNs + K)Nc) operations per location estimate, matching the stated deterministic technique complexity.
  • Complexity comparison: Gaussian processes require O(tNp) operations per estimate and are much slower because Np is typically far larger than Nc.
  • Complexity formulas: CellSense-Hybrid requires O(qNc +(q +K)N0) operations by combining grid-cell probabilities with K-nearest-neighbor refinement inside the most probable cell.
  • Complexity comparison: CellSense-Hybrid has lower computational overhead at low grid cell lengths because Nc is much larger than the number of fingerprint points in the selected cell.The opposite relationship holds for high grid cell sizes.

E. Summary

CellSense combines probabilistic GSM fingerprinting with a hybrid deterministic refinement to balance localization accuracy and computational complexity. Evaluation shows strong accuracy gains, lower complexity, and robustness across grid sizes and testbeds, while performance depends on tower density and estimation parameters.

  • CellSense-Hybrid achieves comparable accuracy to CellSense with significantly lower computational complexity than other techniques.
  • Accuracy improves with more estimation samples, averaged probable locations, and denser cell towers, while reducing fingerprint density by up to 60% still gives good accuracy.
  • CellSense-Hybrid performance remains consistent across different grid sizes and testbeds because of its estimation refinement phase.
  • The hybrid balances accuracy and complexity by returning an original fingerprint point and using only one sample in its first phase at small grid sizes.
  • At least 108.57% accuracy improvement in rural areas and at least 89.03% in urban areas are reported versus state-of-the-art RSSI-based GSM localization techniques.
  • More than 5.4 times running-time savings are reported for CellSense-Hybrid relative to state-of-the-art RSSI-based GSM localization techniques.
Loading 1110.3425v1…