Southern Ontario Numerical Analysis Day



DEPTARMENT: Department of Combinatorics & Optimization

INSTITUTION: University of Waterloo

PHONE: 519 888 4567 x 33922

COAUTHOR(S): Henry Wolkowicz (University of Waterloo)

TITLE: Explicit Sensor Network Localization using Semidefinite
Programming and Clique Reductions
(slides/pdf file)

The sensor network localization, SNL, problem consists of locating the
positions of sensors, given only the distances between sensors that
are within radio range and the positions of some fixed sensors (called
anchors).  Using the theory of Euclidean Distance Matrices, EDMs, we
relax SNL to a semidefinite programming, SDP, problem.  The feasible
set of this SDP is restricted to a low dimensional face of the SDP
cone, causing the Slater constraint qualification to fail.  By finding
explicit representations of the faces of the SDP cone corresponding to
unions of cliques of the SNL problem, we derive a preprocessing
technique that solves the SNL problem, with exact data, by explicitly
solving the corresponding SDP problem.
This is joint work with Henry Wolkowicz, University of Waterloo.

Nathan Krislock
PhD Candidate
Dept. of Combinatorics & Optimization
University of Waterloo, Canada
Phone: (+1) 519 888 4567 ext. 33922