Merging globally rigid graphs and sensor network localization

The sensor network localization problem with distance information is to determine the positions of all sensors in a network, given the positions of some of the sensors and the distances between some pairs of sensors. In sequential localization algorithms were proposed for localizing classes of networks whose sensors possess either a ¿trilateration¿ or ¿bilateration¿ ordering, and graph rigidity theory was used to characterize those networks which can be either localized or efficiently localized by the proposed algorithms. In this work, we consider a decomposition and merging approach for localizing networks which can be applied towards networks whose sensors have neither a trilateration nor a bilateration ordering. We use graph rigidity theory to characterize the necessary graph properties of those subnetworks whose local solutions can be used to obtain a localization solution for the entire network.