title:
Sensor Network Localization, Euclidean Distance Matrix Completions, and Graph Realization

abstract

Many applications use ad hoc wireless sensor networks for monitoring information, e.g. for earthquake detection, ocean current flows, weather, etc... Typical networks include a large number of sensor nodes which gather data and communicate among themselves. The location of a subset of the sensors is known; these sensor nodes are called anchors. From intercommunication among sensor nodes within a given (radio) range, we are able to establish approximate distances between a subset of the sensors and anchors. The sensor localization problem, SNL, is to determine/estimate the location of all the sensors from this partial information on the distances.

We model the problem by treating it as a nearest Euclidean Distance Matrix, EDM, problem with lower bounds formed using the radio range between pairs of nodes for which no distance exists. We also allow for existing upper bounds. When solving for the sensor locations, the problem is nonconvex and hard to solve exactly.

We study the semidefinite programming, SDP, relaxation of the sensor localization problem. The main point of the talk is to view SNL as a (nearest) EDM completion problem and to show the advantages for using this latter, well studied model.

The existence of anchors in the problem is not special. The set of anchors simply corresponds to a given fixed clique for the graph of the EDM problem. This results in the failure of the Slater constraint qualification for the SDP relaxation. We then show that we can take advantage of this liability. We can find the smallest face of the SDP cone that contains the feasible set and project the problem onto this face.

We next propose a method of projection when a large clique or a dense subgraph is identified in the underlying graph. This projection reduces the size, and improves the stability, of the relaxation.

(This research is in collaboration with: Yichuan Ding, Nathan Krislock, Veronica Piccialli, Jiawei Qian.)