Distributed Maximum Likelihood for Simultaneous Self-Localization and Tracking in Sensor Networks

Nikolaos Kantas, Sumeetpal S. Singh, Arnaud DoucetIEEE TSP 2012 · DOI

TL;DR

This paper presents a novel distributed approach for sensor networks to simultaneously track a moving target and determine their own positions without relying on GPS or pre-defined anchor nodes. By formulating the problem as a static parameter estimation task within a Hidden Markov Model framework, the authors develop decentralized algorithms that enable sensors to learn their relative locations and track targets collaboratively.

What Problem Does This Paper Address?

In many sensor network applications, such as surveillance or environmental monitoring, sensors need to track moving targets. Traditionally, this involves a centralized architecture where all sensor data is sent to a single fusion node. This approach has limitations in terms of communication overhead, scalability, and single points of failure. A crucial prerequisite for effective distributed tracking is that each sensor knows its own position and the positions of its neighbors. This is the "self-localization" problem. Existing self-localization methods often rely on direct distance measurements (e.g., from signal strength), GPS, or pre-placed "beacon" nodes, and are frequently performed offline. This paper tackles the challenge of performing simultaneous self-localization and target tracking in a fully decentralized and on-line manner, meaning sensors learn their positions and track targets as data arrives, without external positioning aids.

Methods

The core innovation lies in framing the self-localization problem as a static parameter estimation problem for Hidden Markov Models (HMMs). The authors propose two fully decentralized, on-line Maximum Likelihood (ML) estimation techniques:

  • Recursive Maximum Likelihood (RML): This method updates parameter estimates iteratively as new data arrives, using a gradient-based approach.
  • On-line Expectation-Maximization (EM): This algorithm iteratively refines parameter estimates by alternating between estimating the expected values of hidden variables (E-step) and maximizing the expected log-likelihood (M-step).

Both algorithms are implemented using a message-passing scheme. Sensors exchange summary statistics with their neighbors, allowing them to compute local updates to their position estimates and contribute to the overall network's localization and tracking. For non-linear systems, they employ a linearization approach, similar to the Extended Kalman Filter (EKF).

Datasets

Not discussed in the paper. The paper focuses on simulated numerical examples to evaluate the proposed algorithms.

Key Insights and Ideas

  • Self-localization as parameter estimation: Reframing self-localization as a static parameter estimation problem within an HMM framework is a key conceptual shift.
  • Leveraging collaborative tracking for localization: The paper demonstrates that the act of collaboratively tracking a common target inherently provides the necessary information for sensors to infer their relative positions. This is a crucial insight that bypasses the need for explicit distance measurements or external anchors.
  • Decentralized message passing for ML: The development of distributed RML and EM algorithms that rely on local message passing of summary statistics is a significant contribution, enabling scalable and efficient on-line learning.
  • On-line and distributed nature: The algorithms are designed to work in real-time and without a central coordinator, making them suitable for dynamic and large-scale sensor networks.

Key Results

The paper presents numerical examples demonstrating the effectiveness of the proposed distributed RML and EM algorithms.

  • Convergence: In both linear Gaussian and non-linear bearing-only models, the algorithms consistently converge to accurate estimates of the localization parameters.
  • Performance: The distributed RML and EM algorithms show comparable convergence rates, with RML often being slightly faster. The performance is robust across different network topologies (trees and networks with cycles) and initializations.
  • Scalability: The message-passing approach is designed to be scalable with the network size, with communication limited to neighboring nodes.
  • Benefit of collaboration: Figure 1(b) illustrates that increasing the number of nodes in a collaborative tracking scenario leads to a significant reduction in tracking error, highlighting the advantage of the proposed distributed approach.

Limitations and Future Work

  • Theoretical guarantees: While empirical evidence suggests stability and accuracy, the paper acknowledges that a theoretical investigation into the properties of the proposed schemes would be beneficial.
  • Consensus algorithms: The authors suggest that developing consensus versions of their message-passing algorithm, inspired by gossip algorithms, could be a valuable extension, particularly for networks with cycles.
  • Non-linear models: While the paper proposes an EKF-based approach for non-linear systems, more advanced non-linear filtering techniques (like Particle Filters) could be explored for higher accuracy, albeit at increased computational cost.
  • Initialization: The paper mentions that for on-line EM, it can be beneficial to skip the M-step for initial epochs to allow summary statistics to converge, suggesting that initialization strategies could be further investigated.

Summary updated

BibTeX
@article{kantas2012distributed,
  author = {Nikolaos Kantas and Sumeetpal S. Singh and Arnaud Doucet},
  title = {{Distributed Maximum Likelihood for Simultaneous Self-Localization and Tracking in Sensor Networks}},
  journal = {IEEE Trans. Signal Process.},
  year = {2012},
  doi = {10.1109/tsp.2012.2205923},
}
Figure