Theory of semidefinite programming for Sensor Network Localization |
| |
Authors: | Anthony Man-Cho So Yinyu Ye |
| |
Institution: | (1) Department of Computer Science, Stanford University, Stanford, CA 94305, USA;(2) Department of Management Science and Engineering and, by courtesy, Electrical Engineering, Stanford University, Stanford, CA 94305, USA |
| |
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
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.
A preliminary version of this paper has appeared in the Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2005. |
| |
Keywords: | Euclidean distance geometry Graph realization Sensor network localization Semidefinite programming Rigidity theory |
本文献已被 SpringerLink 等数据库收录! |
|