Robust Distributed Cooperative RSS-based Localization for Directed\n Graphs in Mixed LoS/NLoS Environments

Luca Carlino, Di Jin, Michael Muma, Abdelhak M. ZoubirarXiv 2018 · DOI · arXiv

TL;DR

This paper introduces RD-ML, a robust and distributed algorithm for localizing sensors in a wireless network using only Received Signal Strength (RSS). By modeling signal propagation as a two-component Gaussian mixture, the system adaptively handles both Line-of-Sight (LoS) and Non-Line-of-Sight (NLoS) conditions without requiring manual calibration or assuming symmetric communication links.

What Problem Does This Paper Address?

Localization—determining the physical coordinates of "agent" nodes in a Wireless Sensor Network (WSN)—is a foundational task for everything from environmental monitoring to industrial automation. While GPS is an option, it is often too expensive or power-hungry for small sensors. RSS-based localization is a popular low-cost alternative, but it faces three major hurdles:

  1. The NLoS Problem: Obstacles like walls or furniture create Non-Line-of-Sight (NLoS) conditions, which introduce significant bias and errors if the system assumes a clear path.
  2. The Calibration Nightmare: Most algorithms require "nuisance parameters" (like path loss exponents) to be measured manually beforehand. In dynamic environments, these parameters change constantly, making static calibration useless.
  3. Asymmetric Links: In real-world directed graphs, Node A might hear Node B, but Node B might not hear Node A. Many existing algorithms fail if they cannot assume perfectly symmetric "undirected" links.

Methods

The authors propose Robust Distributed Maximum Likelihood (RD-ML). Its key components include:

  • Gaussian Mixture Model (GMM): Instead of trying to explicitly classify a link as LoS or NLoS (which is error-prone), the authors model the RSS measurements as a mixture of two Gaussian distributions. This allows the math to "weight" the probability of each condition automatically.
  • Adaptive Parameter Estimation: The algorithm treats channel parameters (reference power, path loss exponent, and noise variance) as unknown variables. It estimates these "on the fly" alongside the node positions, eliminating the need for prior calibration.
  • Distributed Architecture: Rather than sending all data to a central "fusion center" (which doesn't scale well), each node updates its own position estimate locally. It treats its neighbors' estimated positions as "virtual anchors."
  • Graph Coloring for Convergence: To ensure the distributed updates actually lead to a solution, the authors reformulated the network connectivity requirements as a graph coloring problem. If the "color" (information) can spread from the fixed anchors to all agents, the algorithm is guaranteed to converge.

Datasets

The paper evaluates the algorithm using standard Monte Carlo (MC) simulations rather than a specific static dataset.

  • Scenario: A 100x100m square area with 11 fixed anchors and 10 randomly placed agents.
  • Channel Modeling: Parameters were generated using uniform and normal distributions to simulate varying environmental conditions (e.g., path loss exponents between 2 and 4 for LoS).
  • Noise: Evaluations included both standard Gaussian noise and "heavy-tailed" Student’s t-distributions to test robustness against non-Gaussian interference.

Key Insights and Ideas

  • NLoS as Information, Not Outliers: Most researchers treat NLoS measurements as "bad data" to be discarded. This paper treats them as part of the statistical model, allowing the algorithm to extract useful positioning information even from obstructed signals.
  • The "Cooperative Gain": The paper demonstrates that cooperation allows nodes that cannot "see" any fixed anchors to still localize themselves by talking to other agents that have already established their positions.
  • Directed Graph Compatibility: By designing for directed graphs from the start, the algorithm is naturally more resilient to the "anisotropy" (direction-dependent signal strength) common in real-world radio hardware.

Key Results

  • Accuracy: In mixed LoS/NLoS environments, RD-ML significantly outperformed non-robust distributed algorithms (D-ML). Its performance was remarkably close to the Centralized MLE, which is the theoretical "gold standard" but requires much higher communication overhead.
  • Robustness: The GMM approach proved resilient even when the noise wasn't Gaussian (using Student’s t-distribution), showing very little performance loss compared to the ideal Gaussian case.
  • Efficiency: The communication overhead scales quadratically ($N_u^2$) with the number of nodes, while computational complexity scales linearly ($N_u$), making it viable for large-scale deployments.
  • Sample Size: Performance improved as the number of samples per link ($K$) increased, with the median error dropping significantly as $K$ moved from 4 to 40.

Limitations and Future Work

  • Local Minima: The optimization problem is non-convex. While the authors used the fmincon solver in MATLAB, real-world low-power microcontrollers might struggle with local minima without a very good initial guess.
  • Stationary Assumption: The current model assumes nodes are stationary during the observation window. Extending this to mobile nodes would require integrating filters (like Kalman or Particle filters).
  • Path Loss Model: The work relies on the standard log-distance path loss model. While widely used, it may not capture extremely complex multipath environments (like metallic ship hulls) as accurately as more advanced models.

The authors suggest that future work could involve looking for "possible approximations" to further reduce the computational load for the tiniest of sensor nodes.

Summary updated

Abstract

The accurate and low-cost localization of sensors using a wireless sensor\nnetwork is critically required in a wide range of today's applications. We\npropose a novel, robust maximum likelihood-type method for distributed\ncooperative received signal strength-based localization in wireless sensor\nnetworks. To cope with mixed LoS/NLoS conditions, we model the measurements\nusing a two-component Gaussian mixture model. The relevant channel parameters,\nincluding the reference path loss, the path loss exponent and the variance of\nthe measurement error, for both LoS and NLoS conditions, are assumed to be\nunknown deterministic parameters and are adaptively estimated. Unlike existing\nalgorithms, the proposed method naturally takes into account the (possible)\nasymmetry of links between nodes. The proposed approach has a communication\noverhead upper-bounded by a quadratic function of the number of nodes and\ncomputational complexity scaling linearly with it. The convergence of the\nproposed method is guaranteed for compatible network graphs and compatibility\ncan be tested a priori by restating the problem as a graph coloring problem.\nSimulation results, carried out in comparison to a centralized benchmark\nalgorithm, demonstrate the good overall performance and high robustness in\nmixed LoS/NLoS environments.\n
BibTeX
@misc{carlino2018robust,
  author = {Luca Carlino and Di Jin and Michael Muma and Abdelhak M. Zoubir},
  title = {{Robust Distributed Cooperative RSS-based Localization for Directed\textbackslash\{\}n Graphs in Mixed LoS/NLoS Environments}},
  year = {2018},
  eprint = {1810.08098},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1810.08098},
}
Figure