無線傳感網中基于半定規劃的定位修正算法

匡博 王穎 李杰 熊慶國 王秀芬

摘 要： 無線傳感網絡的定位精度依賴于噪聲電平和非視距連接。為此，提出基于半定規劃的定位修正算法，其以半定規劃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.