  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 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.
