2004 MCS Divisional Seminars & Colloquia

Semi-definite programming for ad hoc wireless sensor network localization and other Euclidean geometry problems

   Yinyu Ye

Stanford University

  Hosted by  Steve Benson

10:30 AM, September 7, 2004
Building 21,  Room A261

We describe a distributed and decomposed semi-definite programming (SDP) method for solving localization problems that arise from ad hoc wireless sensor network and other Euclidean distance geometry.

The SDP problem is set up so as to minimize the error in sensor positions to fit distance measures. Observable gauges are developed to check the quality of the point estimation of sensors or to detect erroneous sensors. The performance of this technique is highly satisfactory compared to other techniques. Very few anchor nodes are required to accurately estimate the position of all the unknown nodes in a network. Also the estimation errors are minimal even when the anchor nodes are not suitably placed within the network or the distance measurements are noisy.

We also use the SDP duality and interior-point algorithm theories to prove that SDP localizes any network or graph that has unique sensor positions to fit given distance measures.