Detecting Outlier Measurements Based on Graph Rigidity for Wireless Sensor Network Localization

This paper designs a localization approach with outlier detection, which explicitly eliminates ranges with large errors before location computation, and defines verifiable graphs in which all edges are verifiable.

Abstract

A majority of localization approaches for wireless sensor networks rely on the measurements of internode distance. Errors are inevitable in distance measurements, and we observe that a small number of outliers can drastically degrade localization accuracy. To deal with noisy and outlier ranging results, a straightforward method, known as triangle inequality, has often been employed in previous studies. However, triangle inequality has its own limitations that make it far from accurate and reliable. In this paper, we first analyze how much information is needed to identify outlier measurements. Applying the rigidity theory, we propose the concept of verifiable edges and derive the conditions for an edge to be verifiable. On this basis, we design a localization approach with outlier detection, which explicitly eliminates ranges with large errors before location computation. Considering the entire network, we define verifiable graphs in which all edges are verifiable. If a wireless network meets the requirements of graph verifiability, it is not only localizable but outlier resistant as well. Extensive simulations are conducted to examine the effectiveness of the proposed approach. The results show remarkable improvement in location accuracy by sifting outliers.