Indoor Localization Based on Weighted Surfacing from Crowdsourced Samples

Junhong Lin, Bang Wang, Guang Yang, Mu ZhouSensors 2018 · OpenReview

TL;DR

This paper tackles the challenge of building accurate indoor localization maps from crowdsourced Wi-Fi data, which is often plagued by location annotation errors and uneven sample distribution. They introduce a novel "weighted surfacing" approach that uses a cross-domain cluster intersection algorithm to assess sample reliability, then fits polynomial surfaces to these weighted samples, leading to more robust and accurate indoor positioning.

What Problem Does This Paper Address?

Traditional indoor localization systems often rely on fingerprinting, where a unique radio signal profile (fingerprint) is associated with each location. Building this "radio map" typically involves a time-consuming and labor-intensive site survey. To overcome this, researchers have explored crowdsourcing, leveraging data collected by everyday users. However, a major hurdle with crowdsourced data is that the location annotations can be inaccurate, and the samples are often not uniformly distributed across the environment. This leads to unreliable radio maps and degraded localization accuracy. This paper aims to address these issues by developing a method to effectively utilize noisy and unevenly distributed crowdsourced Wi-Fi data for building accurate indoor localization models.

Methods

The core of this paper's contribution lies in its two-phase approach: offline training and online positioning.

Offline Training:

  1. Sample Weighting (Cross-Domain Cluster Intersection - CCI): The authors propose a novel algorithm to assign a reliability weight to each crowdsourced sample. This CCI algorithm clusters samples in both their physical (annotated location) and signal (RSSI values) spaces. A sample's reliability is determined by how well its physical and signal clusters overlap with others, indicating its consistency across both domains. Samples that are outliers in either space receive lower weights.
  2. Weighted Surface Fitting: Instead of traditional grid-based fingerprints, the paper fits polynomial radio propagation surfaces for each Access Point (AP). These surfaces model how RSSI changes across a given area. Crucially, the fitting process uses the reliability weights assigned in the previous step, giving more importance to more trustworthy samples. A percentile weight partition (PWP) method is used to select a subset of weighted samples for fitting, balancing computational complexity and accuracy.
  3. Surface Weighting (Entropy-like Measure): After fitting surfaces, the paper assigns two additional weights to each AP's surface. These weights, derived from an entropy-like measure of the RSS distribution, quantify the surface's "subarea consistency" (how well it represents the entire subarea) and "location discrimination capability" (how well it can distinguish between different locations within the subarea). These weights are used in the online phase.
  4. Subarea Fingerprint Construction: Finally, subarea fingerprints are constructed by sampling the weighted AP surfaces at grid points within each subarea.

Online Positioning:

  1. Subarea Determination: A test sample's RSS vector is compared to the constructed subarea fingerprints using a weighted signal distance metric that incorporates the surface weights. This helps determine the most likely subarea the test sample belongs to.
  2. Location Search: Within the identified subarea, a gradient descent search is employed to find the precise location. This search uses the fitted AP surfaces and the location-discriminating surface weights to minimize the signal difference between the test sample and the surfaces. The search is initialized using a simple nearest neighbor approach for faster convergence.

Datasets

The authors conducted field measurements in a lecture building. They collected two main datasets:

  • Ssite: Approximately 13,670 samples collected using a traditional site-survey approach (one sample per grid cell).
  • Swalk: Approximately 13,370 samples extracted from pedestrian movement trajectories.

To emulate annotation errors, they introduced location offsets drawn from a Gaussian distribution with varying standard deviations (σ = 0.6m, 0.9m, 1.2m). A test set (Stest) of 5600 samples was also created. The experiments also considered scenarios with uniformly distributed samples (Ssite U Swalk) and non-uniformly distributed samples (only Swalk).

Key Insights and Ideas

  • The Power of Weighted Crowdsourcing: The core insight is that not all crowdsourced data is equal. By intelligently weighting samples based on their consistency across physical and signal spaces, we can filter out noise and leverage the valuable information from reliable samples.
  • Surfaces Over Grids: Moving from discrete grid fingerprints to continuous radio propagation surfaces offers a more nuanced and potentially more accurate representation of the indoor radio environment.
  • Dual-Purpose Surface Weights: Assigning separate weights to surfaces for subarea determination and location search is a clever way to optimize the two-stage positioning process.
  • Robustness to Real-World Imperfections: The paper demonstrates that the proposed method is not only accurate but also robust to common real-world issues like annotation errors and uneven data distribution, which are significant challenges in practical indoor localization.

Key Results

The proposed "Weighted Surfacing" (SWSample) scheme consistently outperformed other baseline methods (FGrid, SGrid, SRaw, SCluster) in terms of localization accuracy across various scenarios.

  • Uniformly Distributed Samples: SWSample achieved an Average Localization Error (ALE) of 1.373m with 27,040 samples, outperforming FGrid by 36.71% and SRaw by 9.41%.
  • Impact of Annotation Errors: As annotation errors (σ) increased, all methods saw degraded performance. However, SWSample showed the best performance, with a median localization error of 1.51m and a 90% percentile error of 2.64m at σ = 1.2m.
  • Non-Uniformly Distributed Samples: Even when using only the less uniformly distributed Swalk dataset, SWSample maintained strong performance, outperforming FGrid by 36.85% and SRaw by 18.79%. The median and 90% localization errors were 2.04m and 3.24m, respectively, comparable to the uniform density case.
  • Surface Fitting Quality: Visualizations of fitted surfaces showed that SWSample produced smoother and more coherent surfaces, resembling theoretical path loss models more closely than other methods.

Limitations and Future Work

  • Limitations:
    • The paper acknowledges that in the initial stages of sample collection, when the number of samples is small, SWSample might have a slightly higher error than other methods due to its sample selection mechanism.
  • The fitting of surfaces is based on polynomial functions. While effective, other functional forms or stochastic kernels might offer further improvements.
  • Future Work:
    • Investigating more sophisticated primary functions or stochastic kernels for surface fitting.
  • Exploring probabilistic positioning algorithms, especially when radio propagation surfaces are modeled as stochastic processes.
  • Further research into intelligently choosing the most suitable fitting parameters and functions.

Summary updated

Abstract

Fingerprinting-based indoor localization suffers from its time-consuming and labor-intensive site survey. As a promising solution, sample crowdsourcing has been recently promoted to exploit casually collected samples for building offline fingerprint database. However, crowdsourced samples may be annotated with erroneous locations, which raises a serious question about whether they are reliable for database construction. In this paper, we propose a cross-domain cluster intersection algorithm to weight each sample reliability. We then select those samples with higher weight to construct radio propagation surfaces by fitting polynomial functions. Furthermore, we employ an entropy-like measure to weight constructed surfaces for quantifying their different subarea consistencies and location discriminations in online positioning. Field measurements and experiments show that the proposed scheme can achieve high localization accuracy by well dealing with the sample annotation error and nonuniform density challenges.
BibTeX
@inproceedings{lin2018indoor,
  author = {Junhong Lin and Bang Wang and Guang Yang and Mu Zhou},
  title = {{Indoor Localization Based on Weighted Surfacing from Crowdsourced Samples}},
  booktitle = {Sensors},
  year = {2018},
  url = {https://openreview.net/forum?id=DrV3vqfr1w},
}
Figure