Semidefinite programming approaches for sensor network localization with noisy distance measurements

Pratik Biswas, Tzu Chen Liang, Kim Chuan Toh, Yinyu Ye, Ta Chung Wang

Research output: Contribution to journalArticlepeer-review

319 Citations (Scopus)

Abstract

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.

Original languageEnglish
Article number1707954
Pages (from-to)360-371
Number of pages12
JournalIEEE Transactions on Automation Science and Engineering
Volume3
Issue number4
DOIs
Publication statusPublished - 2006 Oct

All Science Journal Classification (ASJC) codes

  • Control and Systems Engineering
  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'Semidefinite programming approaches for sensor network localization with noisy distance measurements'. Together they form a unique fingerprint.

Cite this