Sensor localization with deterministic accuracy guarantee

Localizability of network or node is an important subproblem in sensor localization. While rigidity theory plays an important role in identifying several localizability conditions, major limitations are that the results are only applicable to generic frameworks and that the distance measurements need to be error-free. These limitations, in addition to the hardness of finding the node locations for a uniquely localizable graph, miss large portions of practical application scenarios that require sensor localization. In this paper, we describe a novel SDP-based formulation for analyzing node localizability and providing a deterministic upper bound of localization error. Unlike other optimization-based formulations for solving localization problem for the whole network, our formulation allows fine-grained evaluation on the localization accuracy per each node. Our formulation gives a sufficient condition for unique node localizability for any frameworks, i.e., not only for generic frameworks. Furthermore, we extend it for the case with measurement errors and for computing directional error bounds. We also design an iterative algorithm for large-scale networks and demonstrate the effectiveness by simulation experiments.