Comprehensive Investigation on Principle Component Large-Scale Wi-Fi Indoor Localization

Ahmed H. Salamah, Mohamed Tamazin, Maha A. Sharkas, Mohamed Essam Khedr, Mohamed MahmoudSensors 2019 · OpenReview

TL;DR

This paper tackles the challenge of accurate and efficient Wi-Fi indoor localization by proposing a novel approach that leverages Principal Component Analysis (PCA) to reduce the dimensionality of Wi-Fi signal data. By applying PCA, the authors demonstrate a significant reduction in computational complexity and radio map size while maintaining or even improving localization accuracy across various machine learning algorithms.

What Problem Does This Paper Address?

Global Positioning Systems (GPS) are notoriously unreliable indoors due to signal blockage and multipath interference. This limitation creates a need for robust indoor positioning solutions. Wi-Fi fingerprinting, which relies on matching received signal strength indicator (RSSI) readings from Wi-Fi access points (APs) to a pre-constructed radio map, is a popular low-cost alternative. However, traditional Wi-Fi fingerprinting methods face challenges with high computational complexity, large storage requirements, and potential accuracy degradation due to the sheer number of APs and the inherent noise in RSSI measurements. This paper aims to address these issues by developing a more efficient and accurate Wi-Fi indoor localization system.

Methods

The core innovation of this paper lies in the application of Principal Component Analysis (PCA) to the Wi-Fi RSSI data. PCA is a dimensionality reduction technique that transforms the original, potentially correlated, features (RSSI from each AP) into a smaller set of uncorrelated components (principal components or PCs) that capture the most significant variance in the data.

The proposed method involves two stages:

  • Offline Stage:
    • Radio Map Construction: RSSI fingerprints are collected from numerous grid points within the indoor environment.
  • PCA Application: PCA is applied to the collected RSSI data to identify redundant information and reduce the dimensionality of the radio map. This involves calculating the covariance matrix, eigenvalues, and eigenvectors. The number of principal components to retain is determined based on the cumulative percentage of eigenvalues, aiming to capture a significant portion of the data's variance (e.g., 85%).
  • Eigenspace Projection: The original radio map is projected onto the reduced eigenspace defined by the selected principal components. This creates a new, lower-dimensional radio map.
  • Machine Learning Model Training: Various machine learning classifiers (K-Nearest Neighbor (KNN), Support Vector Machine (SVM), and Decision Trees (DT)) are trained on this reduced radio map.
  • Online Stage:
    • RSSI Collection: Real-time RSSI measurements are collected from the user's device.
  • Projection: These measurements are projected onto the same eigenspace created during the offline stage.
  • Classification: The projected measurements are then compared with the trained machine learning models to estimate the user's location.

The paper also explores different machine learning approaches, including one-versus-all and one-versus-one strategies for SVM, and various kernel functions.

Datasets

The experiments were conducted in a real-world indoor environment at the International Transport and Logistics College building at the Arab Academy for Science, Technology, and Maritime Transport (AASTMT) in Alexandria, Egypt. This environment covered a large-scale area of 960 m².

  • Training Data: Collected during February 2018, consisting of RSSI measurements from 70 grid points. The training data was collected over five separate days to account for varying environmental conditions. Each grid point was sampled for 20 seconds, yielding nine RSSI readings per sample. The total number of training samples was 350, with each sample originally having 161 features (corresponding to the number of reachable APs).
  • Testing Data: Collected during the same period, following a regular walk through all 70 grid points.

The paper does not explicitly mention using publicly available benchmark datasets but rather focuses on data collected from their specific experimental setup.

Key Insights and Ideas

  • PCA as a powerful dimensionality reduction tool for Wi-Fi localization: The paper convincingly demonstrates that PCA can effectively reduce the feature space (number of APs) without significant loss of crucial information, leading to more efficient processing.
  • Balancing accuracy and complexity: The core idea is to achieve a better trade-off between localization accuracy and computational complexity. PCA allows for a significant reduction in the latter while aiming to maintain or improve the former.
  • Information reorganization over AP selection: The authors emphasize that their PCA approach is not merely selecting a subset of APs but rather reorganizing the information by creating new, uncorrelated features (principal components).
  • Impact of PCA on machine learning performance: The study shows that applying PCA can enhance the performance of various machine learning algorithms, particularly in terms of reducing computational load and potentially improving accuracy by mitigating noise.
  • Linear kernel with one-versus-one SVM as a strong performer: Among the tested machine learning approaches, the linear kernel with a one-versus-one SVM strategy showed promising results, especially when combined with PCA.

Key Results

  • Significant reduction in radio map size and feature complexity: After applying PCA, the radio map size was reduced to 11.8% of the original, and the feature complexity per location was reduced from 161 APs to 18 principal components.
  • Improved localization accuracy: The proposed PCA-enhanced method generally outperformed conventional machine learning techniques. For instance, the mean error for KNN with PCA was comparable to or better than without PCA, and the decision tree performance showed reasonable improvement.
  • Reduced computational complexity: The dimensionality reduction achieved by PCA directly translates to lower computational demands for the localization system.
  • Specific performance metrics:
    • The paper reports a mean error of 1.22 m for the linear kernel with one-versus-one SVM using 18 PCs, with a cumulated error of 98.6% at 5 m.
  • Table 1 shows that with PCA, the CDF error within 3 m for KNN, Linear SVM, and Random Forest remained at 98.5%, while for Decision Tree it improved to 98.5% from 88.57%.
  • Table 2 indicates that at 100% cumulated error, KNN (k=1) and Random Forest achieved 7 m and 9.95 m respectively, with PCA showing slight variations. Linear SVM's performance degraded significantly with PCA (21.6 m vs. 9.95 m without PCA), while Decision Tree improved (13.26 m vs. 24.62 m).

Limitations and Future Work

  • Limitations:
    • The paper acknowledges that PCA might not be optimal if highly nonlinear effects exist between RSSI measurements, which could obscure the principal components' ability to extract valuable information.
  • While PCA improved performance for most classifiers, the linear SVM showed a significant performance degradation in some metrics after PCA application.
  • The study was conducted in a single, large-scale indoor environment.
  • Future Work:
    • The authors suggest a possible future extension of applying the proposed method to a multi-floor radio map.
  • Further investigation into the optimal number of principal components and the impact of different PCA thresholds could be explored.
  • Exploring more advanced machine learning techniques or hybrid approaches in conjunction with PCA could yield further improvements.

Summary updated

Abstract

The smartphone market is rapidly spreading, coupled with several services and applications. Some of these services require the knowledge of the exact location of their handsets. The Global Positioning System (GPS) suffers from accuracy deterioration and outages in indoor environments. The Wi-Fi Fingerprinting approach has been widely used in indoor positioning systems. In this paper, Principal Component Analysis (PCA) is utilized to improve the performance and to reduce the computation complexity of the Wi-Fi indoor localization systems based on a machine learning approach. The experimental setup and performance of the proposed method were tested in real indoor environments at a large-scale environment of 960 m2 to analyze the performance of different machine learning approaches. The results show that the performance of the proposed method outperforms conventional indoor localization techniques based on machine learning techniques.
BibTeX
@inproceedings{salamah2019comprehensive,
  author = {Ahmed H. Salamah and Mohamed Tamazin and Maha A. Sharkas and Mohamed Essam Khedr and Mohamed Mahmoud},
  title = {{Comprehensive Investigation on Principle Component Large-Scale Wi-Fi Indoor Localization}},
  booktitle = {Sensors},
  year = {2019},
  url = {https://openreview.net/forum?id=8Ym_0H-U2X},
}
Figure