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 robust methods to deal with high noise. Finally, simulation results for the algorithms are presented to demonstrate their performance in terms of computational effort and accuracy.

An SDP relaxation based method is developed to solve the localization problem in sensor networks using incomplete and inaccurate distance information. The problem is set up to find a set of sensor positions such that given distance constraints are satisfied. The nonconvex constraints in the formulation are then relaxed in order to yield a semidefinite program that can be solved efficiently.The basic model is extended in order to account for noisy distance information. In particular, a maximum likelihood based formulation and an interval based formulation are discussed. The SDP solution can then also be used as a starting point for steepest descent based local optimization techniques that can further refine the SDP solution.We also describe the extension of the basic method to develop an iterative distributed SDP method for solving very large scale semidefinite programs that arise out of localization problems for large dense networks and are intractable using centralized methods.The performance evaluation of the technique with regard to estimation accuracy and computation time is also presented by the means of extensive simulations.Our SDP scheme also seems to be applicable to solving other Euclidean geometry problems where points are locally connected.

We describe an SDP relaxation based method for the position estimation problem in wireless sensor networks. The optimization problem is set up so as to minimize the error in sensor positions to fit distance measures. Observable gauges are developed to check the quality of the point estimation of sensors or to detect erroneous sensors. The performance of this technique is highly satisfactory compared to other techniques. Very few anchor nodes are required to accurately estimate the position of all the unknown nodes in a network. Also the estimation errors are minimal even when the anchor nodes are not suitably placed within the network or the distance measurements are noisy.