3-D Distributed Localization With Mixed Local Relative Measurements

Xu Fang, Xiaolei Li, Lihua XieIEEE TSP 2020 · OpenReview

Abstract: This paper studies 3-D distributed network localization using mixed types of local relative measurements. Each node holds a local coordinate frame without a common orientation and can only measure one type of information (relative position, distance, relative bearing, angle, or ratio-of-distance measurements) about its neighboring nodes in its local coordinate frame. A novel rigidity-theory-based distributed localization is developed to overcome the challenge due to the absence of a global coordinate frame. The main idea is to construct displacement constraints for the positions of the nodes by using mixed local relative measurements. Then, a linear distributed localization algorithm is proposed for each free node to estimate its position by solving the displacement constraints. The algebraic condition and graph condition are obtained to guarantee the global convergence of the proposed distributed localization algorithm.

Introduction

In large-scale multi-agent systems, such as drone swarms or underwater sensor networks, precise localization is a prerequisite for effective cooperation. However, global positioning systems (GPS) are often unavailable or cost-prohibitive in many environments. Traditional distributed localization methods frequently rely on two restrictive assumptions: homogeneity in sensor types (e.g., all nodes measuring distances) and the existence of a shared global coordinate frame (a "global North").

This research addresses these limitations by proposing a framework for 3-D network localization where nodes operate within independent local coordinate frames and utilize heterogeneous relative measurements, including positions, distances, bearings, angles, and distance ratios.

Methodology

The proposed approach is grounded in a novel "angle-displacement rigidity theory," extending classical rigidity concepts to accommodate 3-D structures defined by mixed geometric constraints. The localization process involves three primary components:

1. Displacement Constraint Construction

The fundamental mechanism involves translating diverse measurement types into a unified mathematical representation known as a displacement constraint. For distance measurements, Cayley-Menger determinants are employed to derive barycentric coordinates, effectively linearizing the geometric relationships between nodes. Figure 2 illustrates the geometric configurations and directed relationships between nodes under various measurement scenarios, such as angle and distance constraints.

Illustration of mixed local relative measurements and node relationships.

2. Linear Distributed Algorithm

Each "free node" (a node with an unknown position) executes a linear estimation algorithm. By communicating with its neighbors, the node iteratively solves the displacement constraints. The flowchart in Figure 3 details the decision logic for a free node to compute these displacement parameters based on its neighborhood information and the availability of anchor nodes (nodes in set $\mathcal{R}$).

Flowchart of the distributed localization algorithm for a free node.

3. Coordinate Independence

The methodology ensures that nodes do not require aligned local coordinate frames. As long as a node can express the relative positions of its neighbors within its own frame, the global network structure can be reconstructed through the collective variety of measurements across the graph.

Results and Discussion

The efficacy of the algorithm was validated through numerical simulations involving a 3-D network of 4 anchor nodes and 23 free nodes.

  • Convergence: In noise-free environments, position estimation errors for all free nodes converged to zero globally. The authors established that global convergence is guaranteed if a specific information matrix ($M_{ff}$), derived from the graph's rigidity, is nonsingular.
  • Robustness to Noise: Under zero-mean Gaussian noise, the algorithm demonstrated stability, with estimates converging to a neighborhood of the true positions. A formal error bound was derived using the Fermat-Weber location problem to characterize how measurement noise propagates through the network.

Conclusion

The proposed framework successfully linearizes the typically non-linear 3-D localization problem, avoiding local minima and ensuring unique solutions. However, the method requires a minimum graph density, typically requiring four neighbors per free node to construct the necessary 3-D displacement constraints. Future work will explore relaxing these connectivity requirements and investigating the impact of non-Gaussian noise distributions and dynamic network topologies.

Summary updated

Abstract

This paper studies 3-D distributed network localization using mixed types of local relative measurements. Each node holds a local coordinate frame without a common orientation and can only measure one type of information (relative position, distance, relative bearing, angle, or ratio-of-distance measurements) about its neighboring nodes in its local coordinate frame. A novel rigidity-theory-based distributed localization is developed to overcome the challenge due to the absence of a global coordinate frame. The main idea is to construct displacement constraints for the positions of the nodes by using mixed local relative measurements. Then, a linear distributed localization algorithm is proposed for each free node to estimate its position by solving the displacement constraints. The algebraic condition and graph condition are obtained to guarantee the global convergence of the proposed distributed localization algorithm.
BibTeX
@article{fang2020d,
  author = {Xu Fang and Xiaolei Li and Lihua Xie},
  title = {{3-D Distributed Localization With Mixed Local Relative Measurements}},
  journal = {IEEE Trans. Signal Process.},
  year = {2020},
  url = {https://openreview.net/forum?id=Flbmk6CdIH},
}
Figure