Semidefinite programming based algorithms for sensor network localization

Pratik Biswas, Tzu Chen Lian, Ta Chung Wang, Yinyu Ye

研究成果: Review article同行評審

408 引文 斯高帕斯(Scopus)


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.

頁(從 - 到)188-220
期刊ACM Transactions on Sensor Networks
出版狀態Published - 2006

All Science Journal Classification (ASJC) codes

  • 電腦網路與通信


深入研究「Semidefinite programming based algorithms for sensor network localization」主題。共同形成了獨特的指紋。