Explicit Sensor Network Localization using Semidefinite Programming and Clique Reductions

Henry Wolkowicz
University of Waterloo, Canada


Friday, October 30, 2009
4:15 - 5:15 PM
Terman 453

Abstract:

The sensor network localization, SNL, problem in embedding dimension r, consists of locating the positions of wireless sensors, given only the distances between sensors that are within radio range and the positions of a subset of the sensors (called anchors). Current solution techniques relax this problem to a weighted, nearest, (positive) semidefinite programming, SDPc completion problem, by using the linear mapping between Euclidean distance matrices, EDMc and semidefinite matrices. The resulting \SDP is solved using primal-dual interior point solvers, yielding an expensive and inexact solution.
This relaxation is highly degenerate in the sense that the feasible set is restricted to a low dimensional face of the SDP cone, implying that the Slater constraint qualification fails. The degeneracy in the SDP arises from cliques in the graph of the SNL problem. 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.

---

Operations Research Colloquia: http://or.stanford.edu/oras_seminars.html