Applications of graph theory in sensor network localization

The sensor network localization problem with distance information is to determine the positions of all the sensors in a network given the positions of some sensors and the distances between some pairs of sensors. This problem has been shown to be NP-hard, and the characterization of networks which can be efficiently localized, and the algorithms which can localize them, are far from fully understood. Our interest lies in devising localization algorithms, and characterizing using graphs those networks that can be provably correctly localized by the proposed algorithms. Towards this end, we introduce the notion of "sequential" localization, and propose a sequential localization algorithm whereby the sensors in a network are processed in a specified ordering. Using this approach, a particularly simple graphical characterization of networks which can be localized by the algorithm can be given. We then identify the graph properties of some classes of networks which can be efficiently localized by exploiting the sequential nature of the proposed algorithm.;We also study the approach of localizing a network by decomposition and merging where the network is assumed to have been decomposed into subnetworks, and each subnetwork is localized in some local coordinate system. We present two linear algebra based algorithms for merging local solutions of subnetworks to obtain a solution for the entire network, and we use graph rigidity theory to characterize collections of subnetworks for which the proposed algorithms are applicable. In the process, we provide further graphical characterizations of networks which are efficiently localizable.;Lastly, we consider the problem of estimating sensor positions when only inaccurate inter-sensor distance measurements are known. We introduce the notion of "correctly oriented" position estimates, and we show that correctly oriented position estimates can be used to deduce properties of the geometric configuration of the actual sensor positions. We propose a position estimation algorithm which computes an error bound for each estimated position, and we give sufficient conditions under which position estimates with error bounds can be guaranteed to be correctly oriented.