Theory of Semidefinite Programming for Sensor Network Localization

Anthony So (manchosocs.stanford.edu)
Yinyu Ye (yinyu-yestanford.edu)

Abstract: We analyze the semidefinite programming (SDP) based model and method for the position estimation problem in sensor network localization and other Euclidean distance geometry applications. We use SDP duality and interior--point algorithm theories to prove that the SDP localizes any network or graph that has unique sensor positions to fit given distance measures. Therefore, we show, for the first time, that these networks can be localized in polynomial time. We also give a simple and efficient criterion for checking whether a given instance of the localization problem has a unique realization in $\R^2$ using graph rigidity theory. Finally, we introduce a notion called strong localizability and show that the SDP model will identify all strongly localizable sub--networks in the input network.

Keywords: semidefinite programming, graph realization

Category 1: Applications -- Science and Engineering

Category 2: Applications -- Science and Engineering (Facility Planning and Design )

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

Citation: Working Paper posted April/24/04 and updated 10/10/05; extended abstract appeared in SODA 2005; full paper to appear in Math Programming 2006.

Download: [PDF]

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

Modify/Update this entry