PaperlayerView exact revision on arXiv

Source-linked AI summary

Modern WLAN Fingerprinting Indoor Positioning Methods and Deployment Challenges

Ali Khalajmehrabadi, Nikolaos Gatsis, David Akopian

arXiv:1610.05424v1cs.NIcs.LG

TL;DR

Robust indoor positioning remains an open problem because GPS requires satellite line-of-sight, while WLAN signals face multipath, interference, non-Gaussian variation, and changing coverage. The paper surveys WLAN fingerprinting methods and deployment challenges, then evaluates localization schemes in one real environment, finding improved performance for sparse recovery methods with coarse localization.

  • Problem

    Robust indoor positioning remains an open problem because GPS and similar systems require direct satellite line-of-sight, while WLAN fingerprinting signals are affected by multipath, interference, time variation, and AP failures.

  • Method

    The paper technically surveys conventional WLAN localization, state-of-the-art fingerprinting solutions, and practical deployment challenges, and compares major schemes in one real environment.

  • Results

    Sparse recovery methods show higher localization accuracy, while with coarse localization 80% of CS, LASSO, and GLMNET errors are less than 20 ft using 10 APs.

  • Takeaways & Limitations

    The evaluation provides an illustrative basis for comparing WLAN localization systems and identifies sparse recovery methods and environmental or sensor peculiarities as improvement directions.

  • Takeaways & Limitations

    Large-scale WLAN deployments require labor-intensive RSS surveying, substantial upfront effort, and periodic radio-map calibration as conditions change over time.

Abstract

from arXiv · show

Wireless Local Area Network (WLAN) has become a promising choice for indoor positioning as the only existing and established infrastructure, to localize the mobile and stationary users indoors. However, since WLAN has been initially designed for wireless networking and not positioning, the localization task based on WLAN signals has several challenges. Amongst the WLAN positioning methods, WLAN fingerprinting localization has recently achieved great attention due to its promising results. WLAN fingerprinting faces several challenges and hence, in this paper, our goal is to overview these challenges and the state-of-the-art solutions. This paper consists of three main parts: 1) Conventional localization schemes; 2) State-of-the-art approaches; 3) Practical deployment challenges. Since all the proposed methods in WLAN literature have been conducted and tested in different settings, the reported results are not equally comparable. So, we compare some of the main localization schemes in a single real environment and assess their localization accuracy, positioning error statistics, and complexity. Our results depict illustrative evaluation of WLAN localization systems and guide to future improvement opportunities.

I. INTRODUCTION

Indoor positioning remains difficult because GPS/GNSS require satellite-user line of sight, while WLAN offers established indoor coverage but was designed for networking rather than localization. The paper reviews conventional WLAN schemes, fingerprinting methods, and practical deployment challenges.

  • Conventional Approaches: Conventional WLAN localization methods are categorized as AOA/DOA, TOA/TDOA, and RSS-based fingerprinting approaches.RSS approaches are further divided into model-based path-loss and model-free radio-map techniques.
  • Conventional Approaches: AOA estimates position from intersecting directional lines measured by antenna-equipped access points.At least two APs measure signal angles relative to a reference orientation.
  • Conventional Approaches: TOA and TDOA convert signal timing information into range or hyperbolic location constraints, commonly using trilateration or hyperboloid positioning.TOA trilateration relies on known AP coordinates and is affected by range-measurement noise.
  • Conventional Approaches: AOA, TOA, and related methods require direct AP-user line of sight and known AP locations, limiting their realism in changing indoor networks.Non-line-of-sight enhancements exist, but the cited passage reports high localization errors under NLOS conditions.
  • Motivation: WLAN is attractive for indoor positioning because it is broadly deployed and mobile devices already provide RSS measurements without additional hardware.WLAN networks provide ubiquitous coverage, while receiver NICs capture received signal strength (RSS).
  • Deployment Challenges: Indoor fingerprinting is challenged by multipath, shadowing, interference, time-varying non-Gaussian RSS, and AP failures.These effects arise from walls, objects, people, unlicensed-band interference, and multiple coexisting AP networks.
  • Paper Scope: The paper addresses gaps in earlier surveys through a technical overview spanning conventional approaches, state-of-the-art solutions, and deployment challenges.It organizes varied methods and notations into a unified treatment while discussing practical applicability.

II. WLAN FINGERPRINTING LOCALIZATION: PROBLEM FORMULATION AND CONVENTIONAL APPROACHES

This section formulates WLAN fingerprinting localization and reviews conventional approaches, using radio maps and online RSS measurements to estimate user locations. It then introduces the organization of early WLAN fingerprinting methods.

  • A. Problem Formulation: Reference Points are represented as Cartesian coordinates and need not be separated by equal distances.The RP set is P = {p_j = (x_j, y_j) | j = 1, . . . , N}.
  • A. Problem Formulation: RSS fingerprints are organized by Access Point, Reference Point, and recording time to construct the radio map.Training samples are typically collected with the same count M at each Reference Point.
  • A. Problem Formulation: Time-averaged radio maps summarize RSS sequences across recording instants, while similar Reference Points can be selected as a subset K.The similarity criterion varies across localization methods.
  • A. Problem Formulation: The section defines WLAN fingerprinting localization as estimating a user’s position by comparing online RSS measurements with radio-map fingerprints.Reference Points form the coordinate set, while radio maps collect RSS fingerprints recorded at those points and times.
  • A. Problem Formulation: During online localization, the mobile device receives y and estimates p̂ = (x̂, ŷ) from a rule comparing measurements against the radio-map collection R.Some advanced probability methods use multiple online measurements indexed by time.
  • B. Conventional Localization Approaches: The problem-formulation section leads into three conventional localization approaches based on differing comparisons between online measurements and stored fingerprints.The paper next reviews early WLAN fingerprinting localization approaches and presents a summarizing diagram.
  • B. Conventional Localization Approaches: Figure 7 summarizes the conventional localization approaches discussed in the paper.The figure accompanies a categorization of related works in Table II.

1) Deterministic Approaches:

Deterministic WLAN fingerprinting estimates position by comparing an online RSS vector with representative fingerprints, but accuracy depends on fingerprint variability, distribution assumptions, and practical deployment constraints.

  • Deterministic Approaches: Deterministic methods select reference points whose fingerprints are closest to the online RSS measurement using a distance metric.The nearest-neighbor method selects the RP with minimum Euclidean distance; KNN instead aggregates the closest RPs.
  • Deterministic Approaches: KNN estimates position from a centroid of the K closest RPs, while weighted KNN gives more similar RPs greater influence.Weights may use inverse distance, RSS variance, or cosine similarity; unreliable RPs can be excluded using a variation threshold.
  • Probabilistic Approaches: A single RSS fingerprint may be insufficient because indoor propagation varies over time, so deterministic methods can use all fingerprints instead.Probabilistic methods use the full fingerprint ensemble to characterize the area statistically.
  • Probabilistic Approaches: MAP localization estimates the location maximizing the conditional probability of the location given the online measurement.With a uniform location prior, MAP reduces to maximum-likelihood estimation because the prior and denominator do not affect the maximization.
  • Probabilistic Approaches: RSS fingerprint distributions are often non-Gaussian, left-skewed, multimodal, and time-varying, challenging parametric density assumptions.Non-parametric methods estimate distributions through histogram matching, but require many time samples at each RP.
  • Challenges and Solutions: Conventional fingerprinting faces growing memory and computation demands, correlated or unavailable APs, faulty readings, labor-intensive surveying, and device heterogeneity.RP clustering addresses some scale-related challenges by narrowing localization to a subset of RPs before fine estimation.

III. RP CLUSTERING AND COARSE LOCALIZATION

RP clustering groups reference points with similar RSS characteristics and uses a coarse localization stage to reduce the search space before fine positioning.

  • III. RP CLUSTERING AND COARSE LOCALIZATION: RSS characteristics depend on environmental features and available APs, motivating clustering or spatial filtering of similar RPs.A representative fingerprint value summarizes each cluster for coarse localization.
  • A. Clustering Using AP Coverage: Coverage-based clustering represents each RP and online measurement with AP coverage indicators and compares them using Hamming distance.An AP is treated as reliable for an RP when its RSS exceeds a threshold for most fingerprinting samples.
  • A. Clustering Using AP Coverage: Coverage indicators identify APs whose readings satisfy the threshold criterion for each RP and form RP-specific coverage sets.The criterion can require an AP reading to exceed the threshold for at least 90% of fingerprinting time.
  • A. Clustering Using AP Coverage: Coarse localization selects a subset of RPs whose coverage vectors are sufficiently close to the online coverage vector.The selected subset is then available for finer localization.

B. Affinity Propagation

Affinity propagation and related clustering methods organize RPs around representative cluster heads or centroids, then compare online measurements with those summaries for coarse localization.

  • B. Affinity Propagation: Affinity propagation models RPs as graph nodes and iteratively exchanges messages to identify exemplars and their clusters.Messages are based on negative Euclidean distances between RP fingerprints.
  • B. Affinity Propagation: During online localization, clusters whose heads have the smallest distances to the online measurement are selected as the coarse location.Affinity propagation can include neighboring cluster RPs when clusters share RPs.
  • C. K-means and Splitting-Based Clustering: K-means iteratively updates cluster centroids, while splitting-based clustering recursively divides the area into four subclusters.K-means requires the number of clusters to be specified beforehand; splitting stops when its distinction criterion is no longer satisfied.
  • Similarity-Based Clustering: Similarity-based clustering links spatially close RPs when their fingerprint similarity exceeds a threshold and may assign an RP to multiple cluster heads.A representativity test selects the cluster head with the least fingerprint variance among cluster members.
  • Similarity-Based Clustering: Cluster membership can be defined by a cluster head and its followers, with online measurements selecting the nearest representative cluster.The similarity measure is proportional to the inverse Hamming distance between RPs.

F. Layered Clustering

Layered clustering groups RPs online by their Hamming distance to the measurement and weights all groups during sparse localization, addressing AP availability and redundancy challenges.

  • F. Layered Clustering: Layered clustering computes each RP’s Hamming distance from the online AP coverage vector and partitions the distance range into K groups.The number of groups is defined experimentally or from a training set.
  • F. Layered Clustering: Groups receive weights inversely related to their average Hamming distance from the online measurement.An RP exactly on a group boundary may be assigned randomly to either adjacent group.
  • F. Layered Clustering: Unlike coarse-only clustering, layered clustering lets all groups contribute through weights during group-sparsity localization.The scheme combines coarse and fine localization in a single step.
  • A. Challenges Related to APs: Correlated AP readings can reduce RP distinguishability and introduce biased estimates or overfitting when redundant AP information is included.AP selection can occur offline or online, with online selection adapting to current measurements and radio-map characteristics.
  • A. Challenges Related to APs: AP selection represents the retained AP subset with a selection matrix and applies localization to the reduced measurement vector.This formulation replaces the full online vector with the selected vector before conventional localization methods are performed.

1) Strongest APs (MaxMean):

AP-selection methods aim to retain fingerprints that are discriminative and stable across reference points, while accounting for reliability and computational cost. The surveyed criteria range from independent AP scores to pairwise or joint subset selection.

  • Fisher Criterion: The Fisher criterion scores each AP by discrimination across reference points while accounting for fingerprint stability.It uses statistical properties of the offline radio map.
  • Fisher Criterion: APs with higher variance receive smaller scores because they are considered less reliable.Scores are sorted decreasingly, and the highest-scoring APs are selected.
  • Fisher Criterion: Fisher-based selection is unsuitable when APs are unavailable online or provide faulty online measurements.The criterion relies only on offline fingerprints.
  • Pairwise AP Selection: Pairwise discrimination methods select AP subsets using distances between fingerprint distributions or RSS fingerprints.Bhattacharyya- and kernel-based criteria evaluate AP pairs and select high-scoring combinations.
  • Information-Based Selection: Mutual-information and entropy criteria select APs with high discriminative power or maximum RSS entropy.Entropy selection discretizes the RSS range and chooses a subset with maximum entropy.

7) Group Discrimination (GD):

Group discrimination and advanced fingerprint-comparison methods exploit relationships among APs, reference points, and fingerprint distributions. These methods improve representational comparison but can require exhaustive searches, dimensionality reduction, or multiple online measurements.

  • Group Discrimination: Group discrimination selects an AP subset jointly to maximize discrimination rather than choosing APs independently.The method searches for the subset producing the least score under a kernel-based criterion.
  • Group Discrimination: The group-discrimination search requires L!/(L′!(L−L′)!) AP-subset combinations, making it exhaustive.Its computational burden grows with the number of available APs.
  • Fingerprint Density Estimation: Fingerprint-density methods use kernel density estimation to model empirical RSS distributions without requiring Gaussian assumptions.KDE superposes kernel functions centered on fingerprints, with kernel width estimated from training or analytical solutions.
  • Kernel-Based Weighting: Normalized-inner-product weights compare online measurements with fingerprints through their angles.Correlated AP readings can make the angle small and therefore unrepresentative.
  • Kernel-Based Weighting: A nonlinear mapping can enlarge differences between angles while using a kernel to compute inner products in the mapped space.The mapping itself need not be explicitly defined because the kernel computes the mapped inner product.
  • Principal-Component Methods: Principal-component methods transform measurements, fingerprints, and covariance matrices using eigenvectors ordered by decreasing eigenvalues, then retain the first L′ PCs.The posterior probability is computed in the reduced PC domain.

C. KL-Divergence Method

The paper presents KL divergence as a distribution-based comparison between online measurements and RSS fingerprints, combining it with a kernel to produce localization weights. The broader sparse-recovery formulation represents localization as selecting one reference point, but requires conditions and can be computationally demanding.

  • KL-Divergence Method: KL divergence measures the distance between the probability densities of online measurements and RSS fingerprints.The symmetrized divergence is used for comparing the two distributions.
  • KL-Divergence Method: Estimating the online-measurement density requires the user to remain at the location and collect multiple measurements.This enables distribution-based comparison with the radio-map fingerprints.
  • KL-Divergence Method: A kernel function combines KL divergence with the distribution comparison to generate weights for location estimation.These weights are then used in the localization procedure.
  • Sparse-Recovery Formulation: Sparse recovery reformulates localization as selecting one reference point through a one-sparse location vector.The online RSS vector is related to the radio map through an AP-selection matrix and an error vector.
  • Sparse-Recovery Formulation: Because the measurement dimension is smaller than the location-vector dimension, the resulting model is underdetermined.Compressive sensing uses an ℓ1-norm formulation to seek a sparse solution, under specified conditions.
  • Sparse-Recovery Limitations: Compressive sensing requires properties such as restricted isometry and mutual incoherence, while optimization complexity increases with area size.The paper notes that matrix orthonormalization does not make the product completely orthonormal because it is not square.

C. LASSO-based Localization

LASSO-based localization combines residual minimization with sparse position-vector estimation and can accommodate correlated RSS fingerprints. Group-sparse extensions use all clusters with weights, while auxiliary sensors can assist fingerprinting but may introduce instability.

  • Sparse-Recovery Methods: Recent sparse-recovery methods avoid orthogonalization and special matrix properties while using the measurement model to handle noisy measurements.The paper presents these methods as overcoming shortcomings of conventional compressive-sensing localization.
  • LASSO-based Localization: LASSO minimizes both the residual ℓ2-norm and the location-vector ℓ1-norm.The tuning parameter λ balances measurement fit against sparsity.
  • LASSO-based Localization: LASSO is described as more indifferent to correlated RSS fingerprints than approaches that do not regularize sparsity and residual error jointly.Its formulation incorporates feature and model selection through ℓ1-penalized least squares.
  • Elastic-Net Localization: GLMNET combines ridge shrinkage for correlated predictors with LASSO sparsity through a compromise parameter α.As α increases from 0 to 1, solution sparsity increases from zero toward the LASSO solution's sparsity.
  • Group-Sparse Localization: Sparse-group localization uses all clusters with different weights and promotes sparsity both within and among groups.The group term concentrates nonzero position-vector elements within a single cluster.
  • Auxiliary Sensors: Auxiliary sound and light/color fingerprints can provide location-specific information, but light-based fingerprints may change frequently and floor imagery is reported as more reliable.Ambient sound can distinguish broad areas such as restaurants and shopping malls.

2) RSSI from cellular base stations [122]:

This section describes complementary sensing and assistance strategies for WLAN fingerprinting, including cellular fingerprints, device sensors, landmarks, collaboration, interpolation, and crowdsourcing. These methods aim to enrich location information, reduce search effort, or lower surveying costs, while introducing accuracy or infrastructure trade-offs.

  • Cellular RSSI can supplement Wi-Fi fingerprints in weak-signal or low-density areas and help resolve location ambiguities.
  • Smartphone sensors provide motion signatures used for walking direction, movement detection, step counting, and heading estimation.
  • Landmarks support localization by calibrating dead reckoning and assisting coarse localization.Seed landmarks correspond to physical locations, whereas organic landmarks are area-specific sensory signatures.
  • Collaborative localization uses relative distances between devices as additional constraints, with Bluetooth-based proximity estimation offering accuracies up to 1.5 m.
  • Crowdsourcing distributes fingerprint collection among users, but shorter collection times and uncertain fingerprint locations can reduce accuracy.
  • Radio-map interpolation can reduce the number of surveyed RPs by estimating fingerprints between measured points.

IX. OUTLIER DETECTION

WLAN localization must handle outliers caused by faulty, unavailable, obstructed, or dynamically changing AP signals. The section surveys detection and mitigation methods for both offline and online measurements.

  • AP faults, jamming, outages, attacks, multipath, visibility changes, and adaptive transmit power can produce outlying RSS measurements.
  • Online outliers occur when an AP measurement differs substantially from every fingerprint in the area.
  • Conventional AP selection based on fingerprinting-period performance is poorly suited to online outliers.
  • Offline outliers can be mitigated through beacon authentication, data collection across periods, validation, and attack detection.
  • The surveyed approaches include statistical filters and methods designed to improve conventional localization under outlier conditions.The Hampel filter replaces mean and standard-deviation estimates with the median and median absolute deviation.

B. Modified Distance-based Outlier Detection

Modified distance-based and robust sparse-recovery methods address mismatches between online and fingerprinting AP measurements. They explicitly accommodate AP subsets, multiple outlier causes, and jointly estimated position and corruption vectors.

  • Modified KNN computes distance over APs shared across fingerprinting and online phases while separately accounting for APs visible only online.
  • A comprehensive outlier model represents jamming noise, bogus APs, and AP unavailability as distinct possible components.The model activates one component at a time through binary indicators.
  • The robust localization procedure switches between Euclidean and median distances using average or median fingerprints.
  • Sparse recovery augments the measurement model with an outlier vector that remains sparse when few APs are corrupted.
  • Modified CS, LASSO, GLMNET, and group-sparsity formulations estimate position and outliers jointly through sparsity-promoting optimization.The convex formulations can be efficiently solved; λ and µ weight location and outlier sparsity terms.

A. Localization Error Without Coarse Localization

The paper evaluates representative WLAN fingerprinting methods in a common office environment and shows that performance depends strongly on AP count and coarse localization. Sparse-recovery methods generally perform best, while fair comparison remains limited by differing granularities and data settings.

  • A. Localization Error Without Coarse Localization: Without coarse localization, all evaluated methods show high errors, although error decreases as the number of APs increases.
  • A. Localization Error Without Coarse Localization: With fewer than 10 APs, GS-based localization has the highest accuracy; with more APs, LASSO shows the least localization error.
  • A. Localization Error Without Coarse Localization: At 10 APs without clustering, contour-based localization has the largest errors, while KNN and KDE also perform unsatisfactorily.The contour method relies on path-loss parameters assumed uniform in all directions, which is unsuitable for complex indoor environments.
  • B. Localization Error With Coarse Localization: With clustering, LASSO and GLMNET errors decrease from 10 ft to 2 ft as engaged APs increase from 4 to 29.
  • A. Critical Summary: The evaluation implements representative approaches in one typical office environment because literature results were obtained under different settings.
  • A. Critical Summary: Fair comparison is hindered by the lack of standardized representative data and by differences in localization granularity.
  • B. Recommendations for Future Work: Future work should address multipath effects, richer trajectory fingerprints, and performance under intentional infrastructure faults or emergency conditions.
Loading 1610.05424v1…