ABSTRACT:
The sensor network localization, \SNL, problem in embedding dimension
$r$, consists of locating
the positions of ad hoc wireless sensors, given only the
distances between sensors that are within
radio range and the positions of a subset of the sensors (called anchors).
\index{radio range, $R$}
There are advantages for formulating this problem as a Euclidean distance matrix
completion, \EDMCc problem, and ignoring the distinction between anchors and
sensors.
Current solution techniques relax this problem
to a weighted, nearest, (positive) semidefinite
programming, \SDP, completion problem, by
using the linear mapping between \EDMs and \SDP matrices.
The relaxation consists in ignoring the rank $r$ for the \SDP matrices.
The resulting \SDP is solved using primal-dual interior point solvers,
yielding an expensive and inexact solution.
Moreover, the relaxation is ill-conditioned in two ways. First, it is implicitly highly degenerate in the sense that the feasble set is restricted to a low dimensional face of the \SDP cone. This means that the Slater constraint qualification fails. Second, nonuniqueness of the optimal solution results in large sensitivity to small perturbations in the data.
The degeneracy in the \SDP arises from cliques in the graph of the \SNL problem. These cliques implicitly restrict the dimension of the face containing the feasible \SDP matrices. In this paper, we take advantage of the absence of the Slater constraint qualification and derive a technique for the \SNL problem, with exact data, that explicitly solves the corresponding rank restricted \SDP problem. No \SDP solvers are used. We are able to efficiently solve this NP-hard problem with high probability, by finding a representation of the minimal face of the \SDP cone that contains the \SDP matrix representation of the \EDM. The main work of our algorithm consists in repeatedly finding the intersection of subspaces that represent the faces of the \SDP cone that correspond to cliques of the \SNL problem.