Numerical methods for large sensor network localization problems

传感器网络定位(SNL)问题在环境监测、交通控制、结构评估等领域有着广泛的应用前景。问题是利用给定的距离估计未知位置的n个传感器的位置，以及在由m个n个传感器组成的传感器网络中估计一些已知位置的m个传感器(称为锚)的位置。众所周知，寻找这个问题的解决方案是NP难的。因此，对这一问题的近似解从多个角度进行了研究。在本项目中，我们研究了基于半定规划松弛的数值方法，半定规划松弛可以提供高精度的近似解，但随着问题规模的增大，用半定规划松弛求解SNL问题的计算代价变得非常昂贵。为了避免这一困难，我们充分利用了大规模SNL问题所涉及的稀疏性，并改进了SDP求解器SDPA的性能。作为最终产品，我们发布了一个能够高速解决大规模传感器网络定位问题的软件包SFSDP。

Sensor network localization (SNL) problems have attracted considerable research interests for a broad spectrum of applications such as environmental monitoring, traffic control and structural assessment. The problem is to estimate the locations of n sensors of unknown positions using given distances and some m sensors of known positions (called anchors) in a sensor network of m+n sensors. Finding the solutions of this problem is known to be NP-hard. Thus, approximating the solution of this problem has been dealt with from many angles. In this project, we have studied numerical methods based on the semidefinite programming (SDP) relaxation．The SDP relaxation can provide approximate solutions with accuracy, but the computational cost of solving SNL problems by the SDP relaxation becomes expensive rapidly as their sizes increase. To avoid this difficulty, we fully exploited the sparsity which were involved in large scale SNL problems and improved the performance of the SDP solver SDPA. As a final product, we released a software package SFSDP that can solve large-scale sensor network localization problems in high speed.