Robust Localization From Incomplete Local Information.

Amin Karbasi, Sewoong OhIEEE/ACM Trans. Networking 2013 · OpenReview

TL;DR

This paper tackles the challenging problem of pinpointing the locations of wireless devices when only partial and unreliable connectivity information is available. The authors provide theoretical guarantees for two localization algorithms, MDS-MAP and HOP-TERRAIN, showing that they can achieve bounded localization errors even with significant data limitations and detection failures. This work is crucial for robust and scalable wireless sensor network applications.

What Problem Does This Paper Address?

Accurately determining the positions of wireless devices is fundamental for many applications, from environmental monitoring to efficient routing in wireless sensor networks. However, in real-world scenarios, obtaining precise distance measurements between all devices is often impossible due to factors like limited communication range, power constraints, and signal interference. This paper focuses on the extreme case where only "connectivity information" is available – essentially, whether two devices can detect each other within a certain range, but not how far apart they are. Furthermore, they account for the realistic scenario of "detection failures," where devices within range might not detect each other with a certain probability. The core challenge is to localize devices reliably under these incomplete and noisy conditions.

Methods

The paper analyzes two localization algorithms:

  • MDS-MAP (Multidimensional Scaling - Map): A centralized algorithm that uses shortest path distances as a proxy for missing pairwise distances and then applies Multidimensional Scaling (MDS) to estimate node positions. The novelty here lies in applying MDS to connectivity information rather than full distance matrices.
  • HOP-TERRAIN: A distributed algorithm that can be viewed as a distributed version of MDS-MAP. It leverages anchors (nodes with known positions) and a distributed shortest path computation to estimate distances, followed by triangulation to determine individual node positions.

The authors' key methodological contribution is providing theoretical bounds on the localization error for these algorithms under the specified challenging conditions. They define a specific metric for distance between estimated and true configurations that is invariant to rigid transformations (rotations, translations).

Datasets

Not discussed in the paper. The authors focus on theoretical analysis and simulations, rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Connectivity is surprisingly powerful: Even with only binary connectivity information (detected or not detected), and accounting for detection failures, it's possible to achieve bounded localization accuracy. This challenges the intuition that precise distance measurements are always necessary.
  • Shortest paths as a robust proxy: Using shortest path distances in the network graph as an estimate for missing pairwise distances is an effective strategy for MDS-MAP, allowing it to work with incomplete information.
  • Distributed localization can match centralized performance: HOP-TERRAIN demonstrates that a distributed approach can achieve similar theoretical error bounds to a centralized algorithm like MDS-MAP, which is crucial for scalability in large sensor networks.
  • Detection probability matters: The probability of detection, which depends on distance, directly influences the localization error. The error decreases as this probability increases (or as the detection range R increases relative to a critical range).

Key Results

The paper presents theoretical bounds on the localization error for both algorithms:

  • MDS-MAP: The error is bounded and decreases proportionally to $R_{critical}/R$, where $R_{critical}$ is the range at which the network becomes connected and $R$ is the device's detection range. For the connectivity-based model, the error is bounded by $R_{RMDS}/R + 20R$, where $R_{RMDS}$ depends on the number of nodes and dimension.
  • HOP-TERRAIN: Achieves a similar bounded error, given by $R_{RHOP}/R + 24R$, where $R_{RHOP}$ depends on the number of nodes and anchors. This bound holds even with only connectivity information and a limited number of anchors (e.g., $d+1$ in a $d$-dimensional space).

These results show that under realistic assumptions of incomplete and noisy data, both algorithms can localize nodes within a bounded error, and this error can be made arbitrarily small by increasing the radio range $R$ or the number of nodes/anchors.

Limitations and Future Work

  • Dimensionality: The theoretical analysis is primarily focused on bounded dimensions ($d=2$ or $d=3$), although the authors mention the analysis can be extended to general $d=O(1)$.
  • Model Assumptions: The analysis relies on specific models for connectivity probability and random node placement. Real-world network topologies and communication patterns might differ.
  • Anchor Placement: While the paper shows that with a sufficient number of anchors, their specific positions don't drastically alter the bounds, the initial placement of anchors can still influence the conditioning of the triangulation step.
  • Future Work: The authors suggest exploring the fundamental limits of localization and developing algorithms with proven guarantees in noisy scenarios. They also highlight the importance of understanding the trade-offs between localization accuracy, computational complexity, and energy efficiency in practical deployments.

Summary updated

Abstract

We consider the problem of localizing wireless devices in an ad hoc network embedded in a d-dimensional Euclidean space. Obtaining a good estimate of where wireless devices are located is crucial in wireless network applications including environment monitoring, geographic routing, and topology control. When the positions of the devices are unknown and only local distance information is given, we need to infer the positions from these local distance measurements. This problem is particularly challenging when we only have access to measurements that have limited accuracy and are incomplete. We consider the extreme case of this limitation on the available information, namely only the connectivity information is available, i.e., we only know whether a pair of nodes is within a fixed detection range of each other or not, and no information is known about how far apart they are. Furthermore, to account for detection failures, we assume that even if a pair of devices are within the detection range, they fail to detect the presence of one another with some probability, and this probability of failure depends on how far apart those devices are. Given this limited information, we investigate the performance of a centralized positioning algorithm MDS-MAP introduced by Shang and a distributed positioning algorithm HOP-TERRAIN introduced by Savarese In particular, for a network consisting of n devices positioned randomly, we provide a bound on the resulting error for both algorithms. We show that the error is bounded, decreasing at a rate that is proportional to RCritical/R, where RCritical is the critical detection range when the resulting random network starts to be connected, and R is the detection range of each device.
BibTeX
@article{karbasi2013robust,
  author = {Amin Karbasi and Sewoong Oh},
  title = {{Robust Localization From Incomplete Local Information.}},
  journal = {IEEE/ACM Trans. Networking},
  year = {2013},
  url = {https://openreview.net/forum?id=YknuSEeQapU},
}
Figure