RSS Fingerprint Based Indoor Localization Using Sparse Representation with Spatio-Temporal Constraint

Xinglin Piao, Yong Zhang, Tingshu Li, Yongli Hu, Hao Liu, Ke Zhang, Yun Ge

TL;DR

This paper introduces a novel indoor localization method that leverages sparse representation enhanced with spatio-temporal constraints. By incorporating the inherent spatial relationships within Wi-Fi signal strength fingerprints and the temporal continuity of user movement, the proposed method significantly improves localization accuracy and robustness compared to existing techniques.

What Problem Does This Paper Address?

Indoor localization, particularly using Received Signal Strength (RSS) fingerprints from Wi-Fi, is a crucial area for Location-Based Services (LBS). While RSS fingerprinting is cost-effective as it utilizes existing infrastructure, current methods often overlook the valuable spatio-temporal correlations present in the data. This oversight leads to limitations such as susceptibility to noise, reduced accuracy, and instability. The paper aims to bridge this gap by developing a localization method that explicitly models and utilizes these correlations to achieve more precise and reliable indoor positioning.

Methods

The core of the proposed method is a Spatio-Temporal Sparse Representation (ST-SR) model. This model builds upon the existing Sparse Representation (SR) framework for localization.

Here's a breakdown of the approach:

  • Sparse Representation (SR) Foundation: The paper starts with the basic SR model, where an unknown RSS measurement is represented as a sparse linear combination of known RSS samples from a fingerprint map. This is formulated as an optimization problem aiming to minimize the L1 norm of the representation coefficients.
  • Spatio-Temporal Constraints: The novelty lies in integrating two key constraints:
  • Temporal Continuity: The RSS measurements collected over time as a user moves are assumed to be continuous and smooth. This is incorporated by adding a penalty term that encourages adjacent columns in the sparse representation matrix (corresponding to consecutive measurements) to be similar. This is achieved using a temporal constraint matrix D.
  • Spatial Correlation: RSS samples in close proximity within the fingerprint map are expected to be similar. This is modeled by introducing a spatial constraint matrix S that penalizes differences in coefficients corresponding to spatially correlated RSS samples.
  • Spatio-Temporal Sparse Representation (ST-SR) Model: The final ST-SR model combines the L1 norm minimization for sparsity, the temporal constraint, the spatial constraint, and a reconstruction error term. This results in a more comprehensive optimization problem.
  • Optimization Solution: To solve this complex optimization problem, the authors employ the Alternating Direction Method of Multipliers (ADMM). This iterative approach breaks down the problem into smaller, manageable subproblems that can be solved efficiently, leading to the final estimated location.

Datasets

The paper evaluates the proposed method using two types of data:

  • Simulated Data: A 30m x 30m square area was simulated with 15 Access Points (APs). The RSS distribution was generated using a wireless signal attenuation model. Various walking paths (line, "8", snake, circle) were simulated to test the localization performance.
  • Real Scene Data: Experiments were conducted in a real-world environment, specifically the third layer of a teaching building. This area measured 67m x 15m and featured 30 detected APs. RSS measurements were collected at 573 uniformly distributed positions. Four walking paths (large quadrangle, Quadrangle 1, Quadrangle 2, and "∞") were used for testing.

Key Insights and Ideas

  • The Power of Context: The paper strongly emphasizes that simply using RSS fingerprints isn't enough. The real value comes from understanding the context in which these fingerprints are collected and used – specifically, how they relate to each other spatially and how measurements change over time.
  • Sparsity as a Foundation, Constraints as Enhancers: Sparse representation provides a robust mathematical framework for matching measurements to fingerprints. However, it's the addition of spatio-temporal constraints that truly elevates the performance, making the system more resilient and accurate.
  • Bridging the Gap Between Ideal and Real: The comparison between simulated and real-world results highlights a critical challenge: real environments are noisy and complex. The fact that the proposed method still outperforms others in the real scene, despite these challenges, is a testament to the effectiveness of the spatio-temporal constraints in mitigating interference.
  • Unified Optimization: The ADMM approach effectively handles the multi-faceted optimization problem, allowing for the simultaneous consideration of sparsity, temporal continuity, spatial correlation, and reconstruction error.

Key Results

The proposed ST-SR method consistently demonstrated superior performance across various scenarios:

  • Improved Accuracy: In both simulated and real-world experiments, the ST-SR method achieved the lowest localization errors compared to baseline methods like KNN, B-SR, CS, T-SR, and S-SR. For instance, in the simulated scene, the average error for ST-SR was 0.710m, significantly lower than the next best (CS at 0.786m). In the real scene, the average error for ST-SR was 1.595m, again outperforming others.
  • Enhanced Robustness: The Cumulative Distribution Function (CDF) curves clearly show that ST-SR achieves a higher probability of low localization errors, indicating greater robustness to noise and environmental variations.
  • Smooth Trajectories: Visualizations of the estimated paths (red lines) closely followed the ground truth paths (blue lines) with less jitter and smoother transitions compared to other methods, especially in the real-world tests.

Limitations and Future Work

The authors acknowledge several limitations and suggest future research directions:

  • Planar Assumption: The current work assumes a planar localization area. For more practical applications, especially in multi-floor buildings, extending the method to handle complex 3D environments is crucial.
  • Data Preprocessing: The paper notes that no sophisticated preprocessing was applied to clean the RSS measurements. Developing more effective data preprocessing techniques could further mitigate the impact of environmental interference and noise, leading to even better localization performance.
  • Complex Environments: Future work could focus on localizing within more complex indoor environments that exhibit intricate structures and significant signal interference.

Summary updated

Abstract

The Received Signal Strength (RSS) fingerprint-based indoor localization is an important research topic in wireless network communications. Most current RSS fingerprint-based indoor localization methods do not explore and utilize the spatial or temporal correlation existing in fingerprint data and measurement data, which is helpful for improving localization accuracy. In this paper, we propose an RSS fingerprint-based indoor localization method by integrating the spatio-temporal constraints into the sparse representation model. The proposed model utilizes the inherent spatial correlation of fingerprint data in the fingerprint matching and uses the temporal continuity of the RSS measurement data in the localization phase. Experiments on the simulated data and the localization tests in the real scenes show that the proposed method improves the localization accuracy and stability effectively compared with state-of-the-art indoor localization methods.
BibTeX
@inproceedings{piao2016rss,
  author = {Xinglin Piao and Yong Zhang and Tingshu Li and Yongli Hu and Hao Liu and Ke Zhang and Yun Ge},
  title = {{RSS Fingerprint Based Indoor Localization Using Sparse Representation with Spatio-Temporal Constraint}},
  booktitle = {Sensors},
  year = {2016},
  url = {https://openreview.net/forum?id=Ko9-NDQpwigx},
}
Figure