Semidefinite programming approaches for sensor network localization with noisy distance measurements

Abstract

A sensor network localization problem is to determine the positions of the sensor nodes in a network given incomplete and inaccurate pairwise distance measurements. Such distance data may be acquired by a sensor node by communicating with its neighbors. We describe a general semidefinite programming (SDP)-based approach for solving the graph realization problem, of which the sensor network localization problems is a special case. We investigate the performance of this method on problems with noisy distance data. Error bounds are derived from the SDP formulation. The sources of estimation error in the SDP formulation are identified. The SDP solution usually has a rank higher than the underlying physical space which, when projected onto the lower dimensional space, generally results in high estimation error. We describe two improvements to ameliorate such a difficulty. First, we propose a regularization term in the objective function that can help to reduce the rank of the SDP solution. Second, we use the points estimated from the SDP solution as the initial iterate for a gradient-descent method to further refine the estimated points. A lower bound obtained from the optimal SDP objective value can be used to check the solution quality. Experimental results are presented to validate our methods and show that they outperform existing SDP methods. © 2006 IEEE.