A Fast Radio Map Construction Method Merging Self-Adaptive Local Linear Embedding (LLE) and Graph-Based Label Propagation in WLAN Fingerprint Localization Systems

Yepeng Ni, Jianping Chai, Yan Wang, Weidong Fang2020 · DOI

TL;DR

This paper introduces a novel, cost-effective method for building WLAN radio maps by merging Self-Adaptive Local Linear Embedding (SLLE) for dimensionality reduction and Graph-Based Label Propagation (GLP) for semi-supervised learning. This approach significantly reduces the effort required for collecting labeled location fingerprints while maintaining high localization accuracy, making indoor positioning systems more practical.

What Problem Does This Paper Address?

Indoor WLAN fingerprint localization systems rely heavily on accurate radio maps, which are essentially databases mapping received signal strength indications (RSSI) to physical locations. Building these maps is a labor-intensive and time-consuming process, requiring extensive data collection at numerous reference points. This high cost severely limits the widespread adoption and development of such systems. The paper aims to address this by proposing a method that drastically reduces the need for labeled data while preserving or even improving localization accuracy.

Methods

The proposed method combines two key techniques:

  • Self-Adaptive Local Linear Embedding (SLLE): This is an extension of the traditional Local Linear Embedding (LLE) algorithm, a manifold learning technique used for dimensionality reduction. The novelty here is the "self-adaptive" aspect, where the algorithm dynamically determines the optimal number of nearest neighbors (k) for each sample point. This is achieved using a genetic algorithm that optimizes 'k' based on local data density, aiming to better preserve the local geometric structure of the high-dimensional RSSI data. This reduced-dimension data is then used for subsequent steps.
  • Graph-Based Label Propagation (GLP): This is a semi-supervised learning algorithm. After dimensionality reduction, the method uses a small set of labeled RSSI samples (with known physical locations) to infer the locations of a much larger set of unlabeled RSSI samples. It constructs a graph where nodes are data points and edge weights represent similarity. Labels (physical locations) are then propagated through this graph, effectively "labeling" the unlabeled data.
  • k Self-Adaptive Neighbor Weights (kSNW) Algorithm: For online positioning, a new algorithm is proposed that leverages the low-dimensional embeddings and neighbor weights derived from SLLE. It uses the known location labels of a few neighbors to estimate the location of a new, unlocalized sample, bypassing the need for full dimensionality reduction and label propagation for every new localization request.

Datasets

The experiments were conducted using two real-world indoor environments:

  • The fourth floor of the YiFu building: This environment featured 13 Access Points (APs) and a radio map built with 48 Reference Points (RPs) at a 2m interval. RSSI fingerprints were 13-dimensional.
  • The DaYueCheng library: This environment had 19 APs and a radio map with 600 RPs at a 2m interval. RSSI fingerprints were 19-dimensional.

The paper also references datasets from previous works ([7-9,15]) for comparative analysis of positioning performance.

Key Insights and Ideas

  • Adaptive k is Crucial for LLE: The paper strongly demonstrates that a fixed 'k' in LLE can lead to suboptimal dimensionality reduction. Dynamically adapting 'k' based on local data density significantly improves the preservation of local geometric structures, leading to better downstream performance.
  • Semi-Supervised Learning Bridges the Gap: GLP effectively leverages a small amount of labeled data to infer locations for a large volume of unlabeled data, directly addressing the core problem of high labeling costs.
  • Reduced Labeling Effort, Maintained Accuracy: The most significant insight is that achieving high localization accuracy (e.g., >88% within 3m) is possible with as little as 25% labeled RSSI samples, a substantial reduction from traditional methods.
  • kSNW for Efficient Online Localization: The proposed kSNW algorithm offers a practical solution for real-time positioning by efficiently using the pre-computed information, avoiding repeated computationally intensive steps.

Key Results

  • Dimensionality Reduction: The SLLE algorithm successfully reduced the dimensionality of RSSI data from 13 to 4 dimensions for the YiFu building and from 19 to 3 dimensions for the library, significantly simplifying subsequent processing.
  • Labeling Efficiency: The proposed method achieved over 88% positioning accuracy within 3 meters using only 25% labeled RSSI samples.
  • Performance Comparison: The proposed approach outperformed existing methods ([7-9,15]) in positioning accuracy, with the proposed radio map achieving 88.30% accuracy within 3m, outperforming others by margins up to 15.30%.
  • Algorithm Efficiency: The kSNW algorithm demonstrated comparable or better accuracy than KNN and PL algorithms, especially in scenarios with incomplete labeled data.
  • Time Savings: The kSWN method was significantly faster than a "merging method," taking approximately 7/8 less time for localization.

Limitations and Future Work

  • Limitations:
    • The paper acknowledges that in complex indoor environments, it can be difficult to observe the RSSI of all APs at every location, requiring the imputation of missing AP RSSI values (e.g., with -99 dBm).
  • While the method aims to cover the entire localization area, achieving a truly sparse but full-coverage sampling for radio map construction can still be challenging.
  • The GLP algorithm assumes that all labels are known and appear in the labeled data, which might be a simplification in some real-world scenarios.
  • Future Work:
    • Optimization of the proposed method.
  • Exploration of novel unsupervised learning methods.
  • Investigating multi-tools fusion approaches.

Summary updated

BibTeX
@misc{ni2020fast,
  author = {Yepeng Ni and Jianping Chai and Yan Wang and Weidong Fang},
  title = {{A Fast Radio Map Construction Method Merging Self-Adaptive Local Linear Embedding (LLE) and Graph-Based Label Propagation in WLAN Fingerprint Localization Systems}},
  year = {2020},
  doi = {10.3390/s20030767},
}
Figure