Optimization Online


Semidefinite Programming Based Algorithms for Sensor Network Localization

Pratik Biswas (pbiswas***at***stanford.edu)
Tzu-Chen Liang (tzuchen***at***stanford.edu)
Ta-Chung Wang (tachung***at***stanford.edu)
Yinyu Ye (yinyu-ye***at***stanford.edu)

Abstract: 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 which can be solved e±ciently. 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. Categories and Subject Descriptors: G.1.6

Keywords: Additional Key Words and Phrases: Semidefinite Programming, Sensor Network Localization,

Category 1: Applications -- Science and Engineering

Category 2: Applications -- Science and Engineering (Multidisciplinary Design Optimization )

Category 3: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Citation: Working Paper posted 9/10/03 and updated 10/3/05; extended abstract appeared in IPSN 2004, full paper to appear in ACM J on Transactions on Sensor Networks 2006.

Download: [PDF]

Entry Submitted: 07/28/2006
Entry Accepted: 07/28/2006
Entry Last Modified: 07/28/2006

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society