Edge‐based semidefinite programming relaxation of sensor network localization with lower bound constraints

Edge‐based semidefinite programming relaxation of sensor network localization with lower bound constraints

0.00 Avg rating0 Votes
Article ID: iaor20125339
Volume: 53
Issue: 1
Start Page Number: 23
End Page Number: 44
Publication Date: Sep 2012
Journal: Computational Optimization and Applications
Authors:
Keywords: combinatorial optimization, location
Abstract:

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 ESDPlb (ρ‐ESDPlb) 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 ρ‐ESDPlb 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" TargetType="DOI"/> ), 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.

Reviews

Required fields are marked *. Your email address will not be published.