EKF–GPR-Based Fingerprint Renovation for Subset-Based Indoor Localization with Adjusted Cosine Similarity

Junhua Yang, Yong Li, Wei Cheng, Yang Liu, Chenxi LiuSensors 2018 · DOI

TL;DR

This paper introduces a novel Fingerprint Renovation System (FRS) that uses a hybrid Extended Kalman Filter (EKF) and Gaussian Process Regression (GPR) approach to efficiently update Wi-Fi fingerprint maps for indoor localization. By leveraging crowdsourced data and a subset-based approach for localization, FRS significantly reduces computational load and improves accuracy compared to traditional methods.

What Problem Does This Paper Address?

Indoor localization, particularly using Wi-Fi Received Signal Strength Indicator (RSSI) fingerprinting, is a popular technique. However, a major bottleneck is the laborious and time-consuming process of collecting and updating the "radio map" – a database of RSSI values at various locations. Environmental changes (e.g., furniture rearrangement, new devices) necessitate frequent updates to maintain accuracy. Manual updates are impractical, and existing methods for automating this process often sacrifice localization accuracy for efficiency. This paper aims to bridge this gap by proposing a system that can effectively renovate the radio map using crowdsourced data while maintaining high localization accuracy and reducing computational demands.

Methods

The proposed Fingerprint Renovation System (FRS) has two main phases:

  • Offline Phase (Radio Map Renovation):
    • EKF-GPR Hybrid: The core of the renovation is a novel combination of Extended Kalman Filter (EKF) and Gaussian Process Regression (GPR). The EKF iteratively estimates the radio map, treating the previous state as the input and crowdsourced signals as observations. GPR is then used to refine the EKF's predictions, leveraging its ability to learn noise and smoothness parameters and provide uncertainty estimates. This hybrid approach aims to overcome the limitations of each method individually, particularly in handling noise and uncertainty in crowdsourced data.
  • Crowdsourcing-Based Signals: Instead of manual data collection, FRS utilizes crowdsourced RSSI measurements from users' mobile devices. These "crowdsourcing-based points" are used to update the existing radio map.
  • Online Phase (Localization):
    • Subset Acquisition: To reduce the computational cost of matching a target device's RSSI to the entire radio map, FRS employs a two-stage subset selection process. First, a random subset (S1) of the radio map is chosen. Then, a more refined subset (S2) is generated around the nearest neighbors identified in S1. This significantly reduces the number of reference points (RPs) that need to be considered for localization.
  • Adjusted Cosine Similarity (ACS): To improve localization accuracy, especially in cases where the target point and reference points might lie on the same line (a weakness of standard Cosine Similarity), the paper proposes an Adjusted Cosine Similarity (ACS) metric. ACS aims to better capture the similarity between RSSI vectors by considering both direction and magnitude differences. This is used in conjunction with a Weighted K-Nearest Neighbor (WKNN) algorithm for the final localization.

Datasets

The experiments were conducted using Wi-Fi data collected in a real indoor environment at the Northwestern Polytechnical University (NWPU) campus library.

  • Database_1: Represents the original, manually collected fingerprint radio map (1030 RPs).
  • Database_2: Represents the renovated radio map using 50 crowdsourcing-based points.
  • Database_3: Another dataset collected for comparison with interpolation/extrapolation methods.
  • Database_4: A renovated version of Database_3.

The paper does not introduce a new benchmark dataset but rather uses its collected data to evaluate its proposed system against existing methods.

Key Insights and Ideas

  • Synergy of EKF and GPR: Combining EKF for its predictive capabilities and GPR for its robust non-parametric regression and uncertainty estimation proves effective for radio map renovation, especially with noisy crowdsourced data.
  • Crowdsourcing as a Practical Update Mechanism: Leveraging everyday users' devices for data collection offers a scalable and cost-effective way to keep indoor localization maps up-to-date, overcoming the limitations of manual surveys.
  • Subset Selection for Computational Efficiency: The two-stage subset acquisition method is crucial for making fingerprinting localization feasible on resource-constrained mobile devices by drastically reducing the search space.
  • ACS for Robust Similarity Measurement: Adjusting Cosine Similarity addresses a key limitation of traditional methods, leading to more accurate localization by better handling vector comparisons.

Key Results

  • Accuracy Improvement: The FRS system achieved a mean localization error of 2.99 m, a significant improvement of 19.6% compared to the un-renovated radio map's mean error of 3.72 m.
  • Reduced Data Collection: The system demonstrated that 50 crowdsourcing-based points could effectively renovate the radio map, replacing the need for 1030 manual fingerprint points.
  • Computational Speedup: The subset acquisition method reduced the online phase computation by approximately 87%, with the number of ACS computations reduced from 1030 to 125 per target point.
  • Comparison with IEM: FRS outperformed interpolation and extrapolation methods (IEM) when a significant percentage (above 15%) of the original fingerprint data was removed.

Limitations and Future Work

  • Localization Deviation with Crowdsourcing Amount: The paper notes that localization deviation decreases as the amount of crowdsourcing-based points increases, with the most significant improvements occurring between 30 and 80 points, after which the trend slows. This suggests an optimal range for crowdsourcing points.
  • Generalizability: While the FRS is presented as an independent and general method applicable to other fingerprinting signals (Bluetooth, NFC, RFID), the experiments were conducted solely with Wi-Fi.
  • Future Work: The authors suggest that FRS can be used with the proposed ACS algorithm to further improve positioning systems, implying potential for integration with other advanced localization techniques. The study also highlights the impact of crowdsourcing point placement, suggesting that strategically placed points can yield better results.

Summary updated

Abstract

Received Signal Strength Indicator (RSSI) localization using fingerprint has become a prevailing approach for indoor localization. However, the fingerprint-collecting work is repetitive and time-consuming. After the original fingerprint radio map is built, it is laborious to upgrade the radio map. In this paper, we describe a Fingerprint Renovation System (FRS) based on crowdsourcing, which avoids the use of manual labour to obtain the up-to-date fingerprint status. Extended Kalman Filter (EKF) and Gaussian Process Regression (GPR) in FRS are combined to calculate the current state based on the original fingerprinting radio map. In this system, a method of subset acquisition also makes an immediate impression to reduce the huge computation caused by too many reference points (RPs). Meanwhile, adjusted cosine similarity (ACS) is employed in the online phase to solve the issue of outliers produced by cosine similarity. Both experiments and analytical simulation in a real Wireless Fidelity (Wi-Fi) environment indicate the usefulness of our system to significant performance improvements. The results show that FRS improves the accuracy by 19.6% in the surveyed area compared to the radio map un-renovated. Moreover, the proposed subset algorithm can bring less computation.
BibTeX
@inproceedings{yang2018ekfgpr,
  author = {Junhua Yang and Yong Li and Wei Cheng and Yang Liu and Chenxi Liu},
  title = {{EKF–GPR-Based Fingerprint Renovation for Subset-Based Indoor Localization with Adjusted Cosine Similarity}},
  booktitle = {Sensors},
  year = {2018},
  doi = {10.3390/s18010318},
}

Loading related content...

Figure