Second-Order Cone Programming Relaxation of Sensor Network Localization
Second-Order Cone Programming Relaxation of Sensor Network Localization
复制标题
DOI：
10.1137/050640308
复制
发表时间：
2007-02
期刊：
影响因子：
--
通讯作者：
P. Tseng
中科院分区：
文献类型：
--
作者：
P. Tseng
传感器网络定位问题已经得到了大量研究。最近，比斯瓦斯（Biswas）和叶（Ye）提出了该问题的一个半定规划（SDP）松弛形式，它具有多种良好的性质，并且已经有许多求解方法被提出。在此，我们研究该问题的一个二阶锥规划（SOCP）松弛形式，其动机是它结构更简单，并且有可能比SDP更快地被求解。我们表明，尽管SOCP松弛形式比SDP松弛形式弱，但它具有良好的性质，使其可用作问题预处理器。特别是，在SOCP松弛形式的内部解中具有唯一位置的传感器，其精度可达距离误差的平方根。因此，这些容易识别的传感器能够被准确定位。在我们的数值模拟中，所找到的内部解能够准确定位80 - 90%的传感器。我们还提出了一种平滑坐标梯度下降方法来寻找内部解，该方法比内点法更快。
The sensor network localization problem has been much studied. Recently Biswas and Ye proposed a semidefinite programming (SDP) relaxation of this problem which has various nice properties and for which a number of solution methods have been proposed. Here, we study a second-order cone programming (SOCP) relaxation of this problem, motivated by its simpler structure and its potential to be solved faster than SDP. We show that the SOCP relaxation, though weaker than the SDP relaxation, has nice properties that make it useful as a problem preprocessor. In particular, sensors that are uniquely positioned among interior solutions of the SOCP relaxation are accurate up to the square root of the distance error. Thus, these sensors, which are easily identified, are accurately positioned. In our numerical simulation, the interior solution found can accurately position up to 80-90p of the sensors. We also propose a smoothing coordinate gradient descent method for finding an interior solution that is faster than an interior-point method.