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. Note to Practitioners-Wireless sensor networks consist of a large number of inexpensive wireless sensors deployed in a geographical area with the ability to communicate with their neighbors within a limited radio range. Wireless sensor networks are finding increasing applicability to a range of monitoring applications in civil and military scenarios, such as biodiversity and geographical monitoring, smart homes, industrial control, surveillance, and traffic monitoring. It is often very useful in the applications of sensor networks to know the locations of the sensors. Global positioning systems suffer from many drawbacks in this scenario, such as high cost, line-of-sight issues, etc. Therefore, there is a need to develop robust and efficient algorithms that can estimate or "localize" sensor positions in a network by using only the mutual distance measures (received signal strength, time of arrival) that the wireless sensors receive from their neighbors. This paper describes an algorithm that solves the sensor network localization problem using advanced optimization techniques. We also study the effect of using very noisy measurements and propose Manuscript received May 24, 2005; revised November 9, 2005. This work was supported in part by the Institute for Mathematical Sciences of the National University of Singapore. This paper was recommended for publication by Associate Editor Y. Ding and Editor P. Ferreira upon evaluation of the reviewers' comments. P. Biswas, T.-C. Liang, and Y. Ye are with the Department of Electrical Engineering, Stanford University, Stanford, CA 94305-4026 USA (e-mail: pbiswas@stanford.edu; yyye@stanford.edu). K.-C. Toh is with the Department of Mathematics, National University of Singapore, Singapore 117543, Singapore (e-mail: mattohkc@nus.edu.sg). T.
Instead of using the objective function in Equation (1), REF consider the SDP relaxation of the following penalty function.
Semidefinite Programming Approaches for Sensor Network Localization With Noisy Distance Measurements
IEEE Transactions on Automation Science and Engineering
IEEE Transactions on Automation Science and Engineering
Computer Science