硕士论文 基于半定规划的无线传感器网络节点定位算法研究.pdf

匡博 王颖 李杰 熊庆国 王秀芬

摘 要： 无线传感网络的定位精度依赖于噪声电平和非视距连接。为此，提出基于半定规划的定位修正算法，其以半定规划ESDP算法为基础，且记为ESDP_O算法，旨在提高定位精度和减少在恶劣环境下的定位时间。ESDP_O算法通过引用抖动矩阵，修改了ESDP算法，提高了ESDP_O算法在高测距误差环境的鲁棒性。ESDP_O算法通过寻找低秩解，应对高噪声和非视距偏差。仿真结果表明，在高噪声和多数测距是非视距NLOS环境下， ESDP_O算法的定位精度优于基于同类算法，并且降低了计算复杂度。

关键词： 无线传感网络； 定位修正算法； 半定规划； 非视距连接； 抖动矩阵； 计算复杂度

中图分类号： TN915?34； TPT393 文献标识码： A 文章编号： 1004?373X（2018）16?0084?04

Abstract： As the positioning accuracy of the wireless sensor network （WSN） depends on the noise level and non?line of sight （NLOS） connection， a positioning correction algorithm based on edge semi?definite programming （ESDP） is proposed to improve the positioning accuracy and reduce the positioning time in harsh environments. As the proposed algorithm is based on the ESDP algorithm， it is marked as the ESDP_O algorithm. A perturbation matrix is introduced to the ESDP_O algorithm to modify the ESDP algorithm and improve the robustness of the ESDP_O algorithm in the high range?finding error environment. The ESDP_O algorithm deals with the high noises and NLOS deviation by searching for the low rank solution. The simulation results show that in the environment with high noises and where most measured distances are NLOS， the ESDP_O algorithm has better positioning accuracy than other algorithms of the same type， and can reduce the computational complexity.

Keywords： wireless sensor network； positioning correction algorithm； semi?definite programming； NLOS connection； perturbation matrix； computational complexity

0 引 言

传感节点的位置在无线传感网络应用中扮演了重要的角色[1?3]。为了获取未知节点的位置信息，未知节点利用已知位置的节点（锚节点）与自己的距离，再结合定位算法，进而估计自己的位置。其中测距是传感网络定位问题的关键。然而，现有多数定位算法是面向可视距 （Line of Sight，LOS）环境。如文献[4]提出了一种基于二阶锥规划的时差定位算法，将定位的非凸优问题转化为凸优化问题，然后运用凸优化理论中的二阶锥规划 （Second?Order Cone Programming，SOCP）[5?6]、半定规划 （Semi?Definite Programming，SDP）松驰方法求解节点的位置。而事实上，多数的无线定位环境是非视距 （Non?Line of Sight，NLOS），这给传感节点定位提出了挑战。

为此，本文面向含有噪声的NLOS的恶劣环境，提出基于边半定规划 （Edge?Semi?Definite Programming，ESDP）松驰优化的定位修正算法，记为ESDP_O。ESDP_O算法通过拉动矩阵降低复杂度，并增强了增加在恶劣环境下定位的鲁棒性。

通过对式（20）松驰化，可计算式（1）～式（6）的解。采用抖动矩阵[P]的目的在于获取低秩解，解秩越低，算法收敛越快。

3 性能分析

3.1 仿真环境

本文在3.07 GHz和8 GB RAM电脑上，对ESDP_O算法进行仿真。引用Matlab软件自带的凸优化工具箱CVX[10]求解算法。假定每个节点的最大邻居数为5。为了充分分析ESDP_O定位算法的性能，选用ESDP[7]，EML[11]，SDP?NLOS[8]进行同步仿真，并进行性能比较。并选择采用平均定位误差 （Average Position Error，APE）作为性能指标，如下：

3.2 实验数据分析

3.2.1 实验一

本次实验是基于NLOS环境，并考虑NLOS连接数和[KE]对定位性能的影响。首先分析了平均定位误差随[μN]对平均定位误差和标准误差的影响，如图1所示。

從图1a）可知，[μN]的增加提高了平均定位误差，再次证明NLOS降低了测距准确性。相比于ESDP，DDP?NLOS， 提出的ESDP_O算法的测距性得到较大的提高，原因在于ESDP_O算法正视了NLOS环境存在，并在测距过程充分考虑了NLOS对测距的影响，同时采用抖动矩阵，增强了恶劣环境的能力。各算法的平均标准方差如图1b）所示。与图1a）数据类似，ESDP算法的平均标准方差最高，而ESDP_O算法的平均标准方差最低。然后，再分析了[KE]对定位性能的影响。实验参数为：噪声值[n=100]，[μN]=0.4。5个锚节点、无线传播距离为4 m。实验数据如图2所示。

依据图2a）的数据可知，定位误差随[KE]的增加而上升，但是，提出的ESDP_O算法的定位精度较稳定，并没有受到[KE]很大影响，这说明ESDP_O算法具有很强的抗噪性能。平均标准方差随[KE]的变化曲线如图2b）所示，可知，ESDP_O算法仍获得最低的方差，在[KE]的整个变化空间内，误差波动小，而其他同类算法ESDP，EML和SDP?NLOS随[KE]增加而上升。例如，在[KE=10-1]时，ESDP_O算法的平均标准方差仅为1.9 m，而EML，SDP?NLOS和ESDP算法的方差分别达到2.5 m，2.23 m和3.25 m。

3.2.2 实验二

本实验是基于LOS环境，且无线网络为40 m×40 m，点数为15。此外，本次实验考虑两类参数：一类（Case1）为噪声值[n=100]，[r=6] m，[KE=0.005]；另一类（Case2）为[n=400]，[r=4] m，[KE=0.5]。从参数可知，Case2环境比Case1环境更为恶劣。表1分析了各算法在两类参数下的平均定位误差。从表1可知：ESDP_O算法在Case1环境下的定位性能并没有得到提高，并且略低于EML和SDP?NLOS；但是，当遭遇更为恶劣的环境Case2时，ESDP_O算法的定位误差明显高于其他同类算法。这些数据说明，ESDP_O算法更适用于较恶劣环境。原因在于ESDP_O算法在估计节点位置时充分考虑了恶劣环境。

3.2.3 实验三

本次实验目的在于分析算法的运算量，并利用运行时间表征运算量。运行时间越长，运算量越大，算法越复杂。实验参数为[KE=0.1]，[r=6]，[m=5]。所有连接均在LOS环境，且[n=100]，200，300，400。各算法的运行时间如表2所示。

从表2数据可知，ESDP_O算法相比于其他算法在同等条件下的运行时间最少。这说明ESDP_O算法在提高对恶劣环境抵御能力的同时，并没有提高算法的复杂度。

4 结 语

针对无线传感网络的节点定位问题，提出ESDP_O算法。ESDP_O算法以ESDP算法为基础，通过抖动矩阵增强了对含有噪声的非视距的恶劣环境的鲁棒性。同时通过获取低秩解，降低算法的复杂度。实验数据表明，提出的ESDP_O算法在恶劣环境下的定位精度得到有效地提高。

参考文献

[1] 金家保，张颂，杨景曙.一种基于二阶锥规划的新时差定位算法[J].电讯技术，2012，52（6）：888?892.

JIN Jiabao， ZHANG Song， YANG Jingshu. A new TDOA location algorithm based on second order cone programming [J]. Telecommunication engineering， 2012， 52（6）： 888?892.

[2] BISWAS P， YE Y. Semidefinite programming for ad hoc wireless sensor network localization [C]// Proceedings of 3rd International Symposium on Information Processing in Sensor Networks. Berkeley： IEEE， 2004： 46?54.

[3] JI S， SZE K F， ZHOU Z， et al. Beyond convex relaxation： a polynomial?time non?convex optimization approach to network localization [C]// Proceedings of IEEE INFOCOM. Turin： IEEE， 2013： 2499?2507.

[4] 王其华，郭戈.基于到达时间差的半定松弛规划优化的定位算法[J].大连海事大学学报，2013，39（4）：59?62.

WANG Qihua， GUO Ge. Semi?definite relaxation programming optimization of localization algorithm based on the arrival time difference [J]. Journal of Dalian Maritime University， 2013， 39（4）： 59?62.

[5] SRIRANGARAJAN S， TEWFIK A H， Luo Z Q. Distributed sensor network localization using SOCP relaxation [J]. IEEE transactions on wireless communications， 2008， 7（12）： 4886?4895.

[6] TSENG P. Second?order cone programming relaxation of sensor network localization [J]. SIAM journal on optimization， 2007， 18（1）： 156?185.

[7] WANG Z， ZHENG S， YE Y， et al. Further relaxations of the semidefinite programming approach to sensor network localization [J].SIAM journal on optimization， 2008， 19（2）： 655?673.

[8] VAGHEFI R M， BUEHRER R M. Cooperative localization in NLOS environments using semidefinite programming [J]. IEEE communications letters， 2015， 19（8）： 1382?1385.

[9] BOYD S， VANDENBERGHE L. Convex optimization [M]. Cambridge： Cambridge University Press， 2004.

[10] CVX Research， Inc. CVX： Matlab software for disciplined convex programming （V2.1） [EB/OL]. [2017?12?01]. http：//cvxr.com/cvx/.

[11] SIMONETTO A， LEUS G. Distributed maximum likelihood sensor network localization [J]. IEEE transactions on signal processing， 2014， 62（6）： 1424?1437.

[12] 时洁，杨德森，时胜国.二阶锥规划在噪声源稳健定位识别中的应用[J].哈尔滨工程大学学报，2011，32（12）：1549?1555.

SHI Jie， YANG Desen， SHI Shengguo. A robust localization and identification method of noise sources using second?order cone programming [J]. Journal of Harbin Engineering University， 2011， 32（12）： 1549?1555.

[13] VAGHEFI R M， BUEHRER R M. Cooperative sensor localization with NLOS mitigation using semidefinite programming [C]// Proceedings of 9th Workshop on positioning navigation and communication. Dresden： IEEE， 2012： 13?18.