Robustness to the loss of multiple nodes in the localizability of sensor networks

In the studies on the localization of wireless sensor networks (WSN), it has been shown that a network is in principle uniquely localizable if its underlying graph is globally rigid and there are at least d + 1 non-collinear anchors (in d-space). The high possibility of the loss of nodes or links in a typical WSN, specially mobile WSNs where the localization often needs to be repeated, enforces to not only have localizable network structures but also structures which remain localizable after the loss of multiple nodes/links. The problem of characterizing robustness against the loss of multiple nodes, which is more challenging than the problem of multiple link loss, is being studied here for the first time, though there have been some results on single node loss. We provide some sufficient properties for a network to be robustly localizable. This enables us to answer the problem of how to make a given network robustly localizable. We also derive a lower bound on the number of the links such a network should have. Elaborating it to the case of robustness against the loss of up to 2 nodes, we propose the optimal network structure, in terms of the required number of distance measurements.