Semidefinite Programming Based Algorithms for Sensor Network Localization

被引：28

作者：

Biswas, Pratik ^{[1
]}

Lian, Tzu-Chen ^{[1
]}

Wang, Ta-Chung ^{[1
]}

Ye, Yinyu ^{[1
]}

机构：

[1] Stanford Univ, Terman Engn Ctr 316, Dept Management Sci & Engn, Sch Engn, Stanford, CA 94305 USA

来源：

ACM TRANSACTIONS ON SENSOR NETWORKS | 2006年 / 2卷 / 02期

关键词：

Algorithms; Semidefinite programming; sensor network localization; distributed methods;

D O I：

暂无

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

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.

引用

页数：33