Robust localization in wireless networks from corrupted signals

Muhammad Osama, Dave Zachariah, Satyam Dwivedi, Petre Stoica

Abstract: We address the problem of timing-based localization in wireless networks, when an unknown fraction of data is corrupted by non-ideal propagation conditions. While timing-based techniques can enable accurate localization, they are sensitive to corrupted data. We develop a robust method that is applicable to a range of localization techniques, including time-of-arrival, time-difference-of-arrival and time-difference in schedule-based transmissions. The method is distribution-free, is computationally efficient and requires only an upper bound on the fraction of corrupted data, thus obviating distributional assumptions on the corrupting noise. The robustness of the method is demonstrated in numerical experiments.

Introduction

In wireless networking, precise device localization is critical, particularly in "GPS-denied" environments such as indoor facilities or dense urban areas. Most contemporary systems utilize the "time of flight" of radio signals to estimate distances. However, these measurements are frequently compromised when signals do not follow a direct Line-of-Sight (LoS) path. Non-Line-of-Sight (NLOS) propagation—caused by reflections off walls, foliage, or moving objects—introduces significant bias, causing standard localization algorithms to fail.

Osama et al. propose a novel framework to mitigate the impact of such corrupted data. Their approach filters out outliers without requiring prior knowledge of the specific noise distribution, offering a robust alternative to traditional least-squares estimation.

Methodology

The core of the proposed solution is a statistically motivated reweighted least-squares method. Unlike standard approaches that treat all measurements equally, this algorithm assigns an individual weight ($\pi_i$) to each data point based on its perceived reliability.

Robust Risk Minimization

The weights are determined through a robust risk minimization framework. The optimization problem minimizes the weighted squared error subject to an "entropy constraint." This constraint acts as a "budget for skepticism": by providing a rough upper bound ($\bar{\epsilon}$) on the expected fraction of corrupted data, the algorithm naturally assigns exponentially decaying weights to measurements that deviate significantly from the consensus of the majority.

Blockwise Coordinate Descent

The solution is implemented via an efficient blockwise coordinate descent algorithm:

  1. Position Update: With weights fixed, the best location estimate is found using weighted nonlinear least squares.
  2. Weight Update: With the position fixed, weights are recalculated based on the residuals of each measurement. This step is computationally lightweight, requiring only a one-dimensional grid search.
  3. Iteration: The process repeats until the position estimate stabilizes.

Experimental Setup

The method's performance was evaluated using synthetic datasets generated via Monte Carlo simulations. The simulated environment consisted of a 2D space with eight anchor nodes. To test robustness, 15% of the data was corrupted by NLOS effects, modeled using an exponential distribution with significant bias, while the remaining data followed a standard LoS distribution. The framework was validated across three protocols: Time-of-Arrival (ToA), Time-Difference-of-Arrival (TDoA), and Time-Difference in Schedule-based Transmissions (T-DST).

Results and Discussion

The proposed method demonstrated significant resilience compared to standard techniques. In ToA simulations, the error remained stable even as corruption levels increased, whereas standard non-linear least squares (NLS) error grew exponentially.

Figure 1: Self-localization of a passive receiving node at (5,5) using eight anchor nodes. Subfigure (b) compares the mean position estimates and dispersion ellipses (99.9% coverage) for the standard (dotted) and proposed robust (solid) methods under 15% NLOS corruption.

As shown in Figure 1, the robust method provides a much more accurate and precise estimate than the standard method when outliers are present. Furthermore, the algorithm proved superior to common Semi-Definite Programming (SDP) approaches in TDoA scenarios, which often failed to find feasible solutions under high corruption.

Key Insights

  • Practical Parameterization: A major advantage is that the exact fraction of corruption ($\epsilon$) need not be known; a conservative upper bound ($\bar{\epsilon}$) is sufficient for high performance.
  • Signal Classification: The generated weights are effective enough to serve as a classification tool, identifying NLOS samples with a low false-alarm rate.
  • Unified Application: The vector-matrix formulation allows this robust "wrapper" to be applied to various timing-based systems without extensive modification.

Conclusion and Future Work

This research provides a computationally efficient, distribution-free method for robust wireless localization. While currently validated on synthetic data, the results suggest high potential for real-world applications where NLOS conditions are prevalent. Future work will focus on incorporating hardware-specific biases and developing uncertainty quantification to provide confidence scores alongside location estimates.

Reference: Osama, M., Zachariah, D., Dwivedi, S. et al. Robust localization in wireless networks from corrupted signals. EURASIP J. Adv. Signal Process. 2021, 79 (2021). https://doi.org/10.1186/s13634-021-00786-8

Summary updated

Abstract

We address the problem of timing-based localization in wireless networks, when an unknown fraction of data is corrupted by non-ideal propagation conditions. While timing-based techniques can enable accurate localization, they are sensitive to corrupted data. We develop a robust method that is applicable to a range of localization techniques, including time-of-arrival, time-difference-of-arrival and time-difference in schedule-based transmissions. The method is distribution-free, is computationally efficient and requires only an upper bound on the fraction of corrupted data, thus obviating distributional assumptions on the corrupting noise. The robustness of the method is demonstrated in numerical experiments.
BibTeX
@article{osama2021robust,
  author = {Muhammad Osama and Dave Zachariah and Satyam Dwivedi and Petre Stoica},
  title = {{Robust localization in wireless networks from corrupted signals}},
  journal = {EURASIP J. Adv. Signal Process.},
  year = {2021},
  url = {https://openreview.net/forum?id=7tFReq3YXft},
}
Figure