- Title
- Global optimal solutions to general sensor network localization problem
- Creator
- Ruan, Ning; Gao, David
- Date
- 2014
- Type
- Text; Journal article
- Identifier
- http://researchonline.federation.edu.au/vital/access/HandleResolver/1959.17/92571
- Identifier
- vital:9626
- Identifier
-
https://doi.org/10.1016/j.peva.2014.02.003
- Identifier
- ISSN:0166-5316
- 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. (C) 2014 Elsevier B.V. All rights reserved.
- Publisher
- Elsevier Ltd
- Relation
- Performance Evaluation Vol. 75-76, no. (2014), p. 1-16
- Rights
- Copyright (C) 2014 Elsevier B.V. All rights reserved.
- Rights
- This metadata is freely available under a CCO license
- Subject
- 01 Mathematical Sciences; 08 Information and Computing Sciences; 10 Technology; Sensor network localization; Canonical duality theory; Perturbation method; Global optimization; NP-Hard problems
- Reviewed
- Hits: 1049
- Visitors: 981
- Downloads: 0