Global optimal solutions to general sensor network localization problem

Ning Ruan, David Yang Gao

Research output: Contribution to journalArticleResearchpeer-review

26 Citations (Scopus)

Abstract

Sensor network localization problem is to determine the position of the sensor nodes in a network given pairwise distance measurements. Such problem can be formulated as a quartic polynomial minimization via the least squares method. This paper presents a canonical duality theory for solving this challenging problem. It is shown that the nonconvex minimization problem can be reformulated as a concave maximization dual problem over a convex set in a symmetrical matrix space, and hence can be solved efficiently by combining a general (linear or quadratic) perturbation technique with existing optimization techniques. Applications are illustrated by solving some relatively large-scale problems. Our results show that the general sensor network localization problem is not NP-hard unless its canonical dual problem has no solution in its positive definite domain. Fundamental ideas for solving general NP-hard problems are discussed.

Original languageEnglish
Number of pages16
JournalPerformance Evaluation
Volume75-76
DOIs
Publication statusPublished - 2014
Externally publishedYes

Keywords

  • Canonical duality theory
  • Global optimization
  • NP-Hard problems
  • Perturbation method
  • Sensor network localization

Cite this