3 Science

a) Summary of the state of knowledge in the field

Recently there has been a great deal of interest and research in the area of wireless sensor networks due to the wide range of associated applications such as natural habitat monitoring, earthquake detection, and in disaster relief and military operations.  Typical networks include a large number of sensor nodes which gather data and communicate among themselves to establish approximate distances between some pairs of sensors.  In addition, the location of a subset of the sensors are known; such sensors are called anchors.  The {\em sensor localization problem} is to determine/estimate the location of all the sensors from this partial information on the distances.

In general, the sensor localization problem is hard and computationally intractable, especially in the setting of a large number of sensors.  Therefore, a common approach is to consider a semi-definite relaxation of this problem from which good estimates of the sensor positions can be computed using interior-point methods.



b) Summary of project's main achievements since last Project CV

Semi-definite Optimization: 
In the last couple of years we made notable advances in the following areas: 

Applications: 

The relationship between the Euclidean distance matrix completion problem and the sensor localization problem was studied and a robust interior-point method was implemented for the solution of the semi-definite relaxation. \cite{KPW06}

Considering an alternate semi-definite relaxation, an improved robust interior-point method was implemented, a new problem reduction technique was proposed, and an improved method for extracting the sensor location data from the solution of the semi-definite relaxation was demonstrated. \cite{DKQW06}



c) Statement of project objectives

Semi-definite Optimization: 

2005:
Ð Extend the robust algorithm for linear programming ([GLWW04]) to SDO (both in theory and application). 
Ð Implement and test the extended algorithm, with emphasis on robustness. 
Ð Apply Euclidean distance matrices to solve molecular conformation problems and more generalized sensor detection problems. 

2007:
- Take advantage of the structure of the sensor localization problem in order to be able to compute good approximations of sensor positions for an ever increasing number of sensors.


d) Methodology

Semi-definite Optimization: A strong background in Variational Analysis, Duality Theory, and Conic Programming will be used for this research. When creating new theory and software, special attention will be paid to both the robustness of the problems studied and the algorithms developed. 



e) Description of subprojects

Semi-definite Optimization: Research in SDO examines theory and algorithms of SDO. This includes new methods of modelling problems as semi-definite programs, and implementing new theory and algorithms on problems modeled in SDO form.



f) Significance of results obtained

Semi-definite Optimization: 
In SDO we have made significant impact in: 

Robustness Theory: A growing emphasis on robust algorithms in the industrial sector, has recently prompted significant research into the area. The new studies into round off error from [GLWW04] [RSW02] [TW05] [Wol04] have resulted in several new robust SDO algorithms. 

New Models: New modelling techniques have allowed SDO to be used in MRI design, molecular conformation and protein folding [ASTZ04] [ATW04] [AHW05]. This further developed the analysis of sequential SDO for nonlinear SDOs. The model and techniques developed also appear appropriate to model and create powerful solution techniques for network stability and efficiency of electricity networks. 

Sensor Network Localization: The demand from applications is to estimate sensor positions for an ever increasing number of sensors.  It is for this reason that finding a method of reducing the size of the problem, as was done in \cite{DKQW06}, is of great importance.  In addition, the techniques developed in both \cite{KPW06} and \cite{DKQW06} have demonstrated the ability to obtain sensor positions of very good quality and accuracy from the use of a robust interior-point method together with a new approach for extracting the sensor location information from the solution of the semi-definite relaxation.



\bibitem[KPW06]{KPW06}
N.~Krislock, V.~Piccialli, and H.~Wolkowicz.
\newblock Robust Semidefinite Programming Approaches for Sensor Network Localization with Anchors.
\newblock {\em Technical Report}, CORR, 2006.

\bibitem[DKQW06]{DKQW06}
Y.~Ding, N.~Krislock, J.~Qian, and H.~Wolkowicz.
\newblock Sensor Network Localization, Euclidean Distance Matrix Completions, and Graph Realization.
\newblock {\em Technical Report}, CORR, 2006.