Angle rigidity links graph shapes to sensor network localization success
Equivalent Graphical Conditions for Angle Rigidity and Angle-Based Network Localization
Information Theory
Summary
Sometimes, knowing only the angles between connections in a network can help figure out the exact shape or layout of that network on a flat surface. The paper shows that certain types of graphs called Laman graphs perfectly describe when this is possible using just angles. The authors also created a new method to locate sensors in a network using angle measurements, which works well under more relaxed conditions than before. This helps make sensor location tasks easier and more reliable.
What this means in practice
- •For sensor network engineers: Use angle-based constraints to localize sensors accurately with fewer restrictions on network structure.
- •For robotics developers: Design robot formations that maintain shape based on angle information to improve coordination and stability.
Authors
Jinpeng Huang, Gangshan Jing, Kai Zhao, Yongduan Song
Abstract
Angle rigidity theory provides a theoretical basis for characterizing the geometric shape of graphs embedded in the plane under angle constraints, and establishing global convergence of angle-based network localization algorithms. The related references, however, are largely restricted to graphs generated by triangulation or bilateration ordering, which are sufficient but not necessary for angle rigidity. This paper addresses this challenge by focusing on establishing the equivalence between angle constraints and bearing constraints. The conditions for cycle compatible frameworks (with possibly non-generic configurations) to be angle fixable are provided. Moreover, it is shown for the first time that Laman graphs equivalently characterize minimally globally angle rigid graphs, implying that a Laman graph is the simplest graph that allows a generic embedding in the plane to be uniquely determined by subtended angles. As an application, a distributed algorithm for angle-based sensor network localization is proposed, which guarantees global convergence under a much milder network topology condition than those in the literature.