Edge-based semidefinite programming relaxation of sensor network localization with lower bound constraints
In this paper, we strengthen the edge-based semidefinite programming relaxation (ESDP) recently proposed by Wang, Zheng, Boyd, and Ye (SIAM J. Optim. 19:655–673, 2008 ) by adding lower bound constraints. We show that, when distances are exact, zero individual trace is necessary and sufficient for a sensor to be correctly positioned by an interior solution. To extend this characterization of accurately positioned sensors to the noisy case, we propose a noise-aware version of ESDP lb (ρ-ESDP lb ) and show that, for small noise, a small individual trace is equivalent to the sensor being accurately positioned by a certain analytic center solution. We then propose a postprocessing heuristic based on ρ-ESDP lb and a distributed algorithm to solve it. Our computational results show that, when applied to a solution obtained by solving ρ-ESDP proposed of Pong and Tseng (Math. Program. doi: 10.1007/s10107-009-0338-x ), this heuristics usually improves the RMSD by at least 10%. Furthermore, it provides a certificate for identifying accurately positioned sensors in the refined solution, which is not common for existing refinement heuristics. Copyright Springer Science+Business Media, LLC 2012
Volume (Year): 53 (2012)
Issue (Month): 1 (September)
|Contact details of provider:|| Web page: http://www.springer.com/math/journal/10589|
|Order Information:||Web: http://link.springer.de/orders.htm|
References listed on IDEAS
Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.:
- Jiawang Nie, 2009. "Sum of squares method for sensor network localization," Computational Optimization and Applications, Springer, vol. 43(2), pages 151-179, June.
When requesting a correction, please mention this item's handle: RePEc:spr:coopap:v:53:y:2012:i:1:p:23-44. See general information about how to correct material in RePEc.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Guenther Eichhorn)or (Christopher F Baum)
If references are entirely missing, you can add them using this form.