Fixed Point Iteration Based Algorithm for Asynchronous TOA-Based Source Localization

Huaping Liu(刘华平), Yanbin Zou, Jingna Fan, Liehu Wu, Huaping LiuSensors 2022 · DOI

TL;DR

This paper introduces a novel Fixed Point Iteration (FPI) algorithm for asynchronous Time-of-Arrival (TOA) based source localization. The FPI algorithm offers a computationally efficient and accurate alternative to existing methods, particularly in scenarios with unknown transmission times and potential sensor position errors.

What Problem Does This Paper Address?

Accurate source localization is crucial for many applications, including navigation and monitoring. Time-of-Arrival (TOA) is a common positioning scheme, but it typically requires precise time synchronization between the source and sensors. In asynchronous networks, this synchronization is challenging, leading to unknown start transmission times and corrupted range measurements. This paper tackles the problem of Asynchronous TOA (ATOA)-based source localization, specifically addressing the complexities introduced by unknown transmission times and the potential for sensor position errors, which can significantly degrade localization accuracy. Existing methods often rely on computationally intensive convex optimization techniques (like SDP and SOCP) or suffer from accuracy limitations and threshold phenomena (like 2SWLS).

Methods

The core contribution of this paper is the development of a Fixed Point Iteration (FPI) algorithm. This algorithm is directly derived from the Maximum Likelihood Estimator (MLE) and avoids the pitfalls of existing methods:

  • Direct MLE Derivation: Unlike methods that use approximations or relaxations, FPI is derived directly from the MLE, ensuring a theoretically sound foundation.
  • Computational Efficiency: The algorithm involves only basic arithmetic operations (addition, multiplication, division, square-root) and importantly, avoids matrix inversions. This makes it computationally lighter and more robust to singular matrices compared to some other iterative methods.
  • No Convex Relaxation: Unlike SDP/SOCP-based methods, FPI does not rely on convex relaxation, meaning it doesn't introduce approximations to achieve a globally optimal solution for the relaxed problem.
  • Handling Sensor Position Errors: The FPI algorithm is designed to be easily extended to scenarios where sensor positions are not perfectly known, a common practical challenge.

The paper presents two main algorithms:

  1. Algorithm 1 (Accurate Sensor Positions): This algorithm iteratively refines the source location estimate using the FPI update rule derived from the MLE. It employs multiple initial values and a cost function to select the best estimate, mitigating the risk of converging to a local optimum.
  2. Algorithm 2 (Non-Accurate Sensor Positions): This algorithm extends the FPI approach to handle sensor position uncertainties. It uses a two-stage process: first, it obtains an initial source location estimate using Algorithm 1 with the available (non-accurate) sensor positions, and then it refines both the source and sensor positions using a further FPI update.

Datasets

Not discussed in the paper. The evaluation is based on simulated data.

Key Insights and Ideas

  • FPI as a Sweet Spot: The FPI algorithm appears to strike a good balance between computational complexity and localization accuracy, outperforming some state-of-the-art methods in simulations.
  • Avoiding Matrix Inversions is Key: The avoidance of matrix inversions in the FPI update rule contributes to its robustness and computational efficiency, especially when dealing with potentially ill-conditioned matrices.
  • Multiple Initial Values are Crucial: The paper highlights that using multiple initial values for the FPI algorithm is essential to avoid converging to local optima and to find a better estimate of the true source location.
  • Sensor Position Errors are a Major Challenge: The results clearly demonstrate that sensor position errors significantly impact localization accuracy, and the proposed FPI algorithm shows promise in mitigating these effects.

Key Results

  • Scenario 1 (Accurate Sensor Positions):
    • The proposed "Proposed-Multi" algorithm (FPI with multiple initial values) and the SDP-Zou algorithm can reach the Cramér-Rao Lower Bound (CRLB).
  • "Proposed-Multi" outperforms "Proposed-Mid" (FPI with a single initial value), validating the importance of multiple initial guesses.
  • Gauss-Newton methods show inferior performance due to their first-order approximation.
  • 2SWLS has the worst performance, especially with certain sensor geometries.
  • SDP-Ma also shows poor performance, potentially due to the limited number of sensors.
  • Scenario 2 (Non-Accurate Sensor Positions):
    • The proposed Algorithm 2 (FPI for non-accurate sensors) demonstrates superior performance compared to Gauss-Newton and SDP-Zou.
  • The average running time of the proposed algorithm is significantly less than SDP-Zou but greater than Gauss-Newton.
  • Computational Time: 2SWLS is the fastest, while SDP-based methods are the slowest. The proposed FPI algorithm offers a good trade-off.

Limitations and Future Work

  • Local Optima: While the use of multiple initial values helps, the FPI algorithm, like many iterative methods, can still converge to a stationary point (local maximum, minimum, or saddle point) rather than the global minimum. The paper addresses this by selecting the result that minimizes the cost function.
  • Gauss-Newton Limitations: The paper notes that Gauss-Newton methods can sometimes result in NaN values due to singular matrices during inversion, requiring specific handling.
  • Future Work: The paper suggests that the calculation amount can be further reduced if $u = 2M$. This implies potential for optimization in the stopping criterion or update rule. The code for simulations is available from the authors, which could facilitate further research and validation.

Summary updated

BibTeX
@article{liu2022fixed,
  author = {Huaping Liu(刘华平) and Yanbin Zou and Jingna Fan and Liehu Wu and Huaping Liu},
  title = {{Fixed Point Iteration Based Algorithm for Asynchronous TOA-Based Source Localization}},
  journal = {Sensors},
  year = {2022},
  doi = {10.3390/s22186871},
}
Figure