Semidefinite programming based algorithms for sensor network localization

作者：Pratik K. Biswas, Tzu-Chen Lian, Ta-Chung Wang, Yinyu Ye · 发表于：ACM Transactions on Sensor Networks · 年份：2006 · DOI：10.1145/1149283.1149286 · 被引用次数：546 · 研究领域：Indoor and Outdoor Localization Technologies、Sparse and Compressive Sensing Techniques、Advanced Optimization Algorithms Research

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.