Combinatorial measures of rigidity in wireless sensor and robot networks

Abstract

This paper presents a combinatorial rigidity approach to measure rigidity and redundant rigidity for wireless sensor and robot networks. Redundant rigidity is a necessary condition for global rigidity, which is desirable for network localization. Redundant rigidity also provides rigidity robustness in formation control and network localization against structural changes, such as link losses. In 2-space, Laman's Theorem provides us a test to determine whether there are at least 2n - 3 well-distributed edges, which are independent edges. However, we need more than the requirements in Laman's theorem to know whether "all the edges" are well-distributed, including redundant edges. In 3-space, there is no known combinatorial test for rigidity. However, we can still provide a generic redundancy measure. In this work, we evaluate the distribution of redundant edges in 2-space and we examine the challenges to provide a measure of redundancy in 3-space.