Semidefinite programming approaches for sensor network localization with noisy distance measurements
Semidefinite programming approaches for sensor network localization with noisy distance measurements
复制标题
DOI：
10.1109/tase.2006.877401
复制
发表时间：
2006-10-01
影响因子：
5.6
通讯作者：
Wang, Ta-Chung
中科院分区：
文献类型：
--
作者：
Biswas, Pratik;Liang, Tzu-Chen;Wang, Ta-Chung
传感器网络定位问题是在给定不完整且不准确的成对距离测量的情况下确定网络中传感器节点的位置。这样的距离数据可以由传感器节点通过与其邻居通信来获取。我们描述了一种基于通用半定规划（SDP）的方法来解决图实现问题，其中传感器网络定位问题是一个特例。我们研究了该方法在噪声距离数据问题上的性能。误差范围源自 SDP 公式。确定了 SDP 公式中估计误差的来源。 SDP 解决方案的等级通常高于底层物理空间，当投影到较低维空间时，通常会导致较高的估计误差。我们描述了两项改进来缓解这种困难。首先，我们在目标函数中提出了一个正则化项，可以帮助降低 SDP 解的秩。其次，我们使用从 SDP 解估计的点作为梯度下降方法的初始迭代来进一步细化估计点。从最优 SDP 目标值获得的下界可用于检查解的质量。实验结果验证了我们的方法，并表明它们优于现有的 SDP 方法。
A sensor network localization problem is to determine the positions of the sensor nodes in a network given incomplete and inaccurate pairwise distance measurements. Such distance data may be acquired by a sensor node by communicating with its neighbors. We describe a general semidefinite programming (SDP)-based approach for solving the graph realization problem, of which the sensor network localization problems is a special case. We investigate the performance of this method on problems with noisy distance data. Error bounds are derived from the SDP formulation. The sources of estimation error in the SDP formulation are identified. The SDP solution usually has a rank higher than the underlying physical space which, when projected onto the lower dimensional space, generally results in high estimation error. We describe two improvements to ameliorate such a difficulty. First, we propose a regularization term in the objective function that can help to reduce the rank of the SDP solution. Second, we use the points estimated from the SDP solution as, the initial iterate for a gradient-descent method to further refine the estimated points. A lower bound obtained from the optimal SDP objective value can be used to check the solution quality. Experimental results are presented to, validate our methods and show that they outperform existing SDP methods.