無(wú)線傳感網(wǎng)中基于半定規(guī)劃的定位修正算法

匡博 王穎 李杰 熊慶國(guó) 王秀芬

摘 要： 無(wú)線傳感網(wǎng)絡(luò)的定位精度依賴于噪聲電平和非視距連接。為此，提出基于半定規(guī)劃的定位修正算法，其以半定規(guī)劃ESDP算法為基礎(chǔ)，且記為ESDP_O算法，旨在提高定位精度和減少在惡劣環(huán)境下的定位時(shí)間。ESDP_O算法通過(guò)引用抖動(dòng)矩陣，修改了ESDP算法，提高了ESDP_O算法在高測(cè)距誤差環(huán)境的魯棒性。ESDP_O算法通過(guò)尋找低秩解，應(yīng)對(duì)高噪聲和非視距偏差。仿真結(jié)果表明，在高噪聲和多數(shù)測(cè)距是非視距NLOS環(huán)境下， ESDP_O算法的定位精度優(yōu)于基于同類算法，并且降低了計(jì)算復(fù)雜度。

關(guān)鍵詞： 無(wú)線傳感網(wǎng)絡(luò)； 定位修正算法； 半定規(guī)劃； 非視距連接； 抖動(dòng)矩陣； 計(jì)算復(fù)雜度

中圖分類號(hào)： TN915?34； TPT393 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 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 引 言

傳感節(jié)點(diǎn)的位置在無(wú)線傳感網(wǎng)絡(luò)應(yīng)用中扮演了重要的角色[1?3]。為了獲取未知節(jié)點(diǎn)的位置信息，未知節(jié)點(diǎn)利用已知位置的節(jié)點(diǎn)（錨節(jié)點(diǎn)）與自己的距離，再結(jié)合定位算法，進(jìn)而估計(jì)自己的位置。其中測(cè)距是傳感網(wǎng)絡(luò)定位問(wèn)題的關(guān)鍵。然而，現(xiàn)有多數(shù)定位算法是面向可視距 （Line of Sight，LOS）環(huán)境。如文獻(xiàn)[4]提出了一種基于二階錐規(guī)劃的時(shí)差定位算法，將定位的非凸優(yōu)問(wèn)題轉(zhuǎn)化為凸優(yōu)化問(wèn)題，然后運(yùn)用凸優(yōu)化理論中的二階錐規(guī)劃 （Second?Order Cone Programming，SOCP）[5?6]、半定規(guī)劃 （Semi?Definite Programming，SDP）松馳方法求解節(jié)點(diǎn)的位置。而事實(shí)上，多數(shù)的無(wú)線定位環(huán)境是非視距 （Non?Line of Sight，NLOS），這給傳感節(jié)點(diǎn)定位提出了挑戰(zhàn)。

為此，本文面向含有噪聲的NLOS的惡劣環(huán)境，提出基于邊半定規(guī)劃 （Edge?Semi?Definite Programming，ESDP）松馳優(yōu)化的定位修正算法，記為ESDP_O。ESDP_O算法通過(guò)拉動(dòng)矩陣降低復(fù)雜度，并增強(qiáng)了增加在惡劣環(huán)境下定位的魯棒性。

通過(guò)對(duì)式（20）松馳化，可計(jì)算式（1）～式（6）的解。采用抖動(dòng)矩陣[P]的目的在于獲取低秩解，解秩越低，算法收斂越快。

3 性能分析

3.1 仿真環(huán)境

本文在3.07 GHz和8 GB RAM電腦上，對(duì)ESDP_O算法進(jìn)行仿真。引用Matlab軟件自帶的凸優(yōu)化工具箱CVX[10]求解算法。假定每個(gè)節(jié)點(diǎn)的最大鄰居數(shù)為5。為了充分分析ESDP_O定位算法的性能，選用ESDP[7]，EML[11]，SDP?NLOS[8]進(jìn)行同步仿真，并進(jìn)行性能比較。并選擇采用平均定位誤差 （Average Position Error，APE）作為性能指標(biāo)，如下：

3.2 實(shí)驗(yàn)數(shù)據(jù)分析

3.2.1 實(shí)驗(yàn)一

本次實(shí)驗(yàn)是基于NLOS環(huán)境，并考慮NLOS連接數(shù)和[KE]對(duì)定位性能的影響。首先分析了平均定位誤差隨[μN(yùn)]對(duì)平均定位誤差和標(biāo)準(zhǔn)誤差的影響，如圖1所示。

從圖1a）可知，[μN(yùn)]的增加提高了平均定位誤差，再次證明NLOS降低了測(cè)距準(zhǔn)確性。相比于ESDP，DDP?NLOS， 提出的ESDP_O算法的測(cè)距性得到較大的提高，原因在于ESDP_O算法正視了NLOS環(huán)境存在，并在測(cè)距過(guò)程充分考慮了NLOS對(duì)測(cè)距的影響，同時(shí)采用抖動(dòng)矩陣，增強(qiáng)了惡劣環(huán)境的能力。各算法的平均標(biāo)準(zhǔn)方差如圖1b）所示。與圖1a）數(shù)據(jù)類似，ESDP算法的平均標(biāo)準(zhǔn)方差最高，而ESDP_O算法的平均標(biāo)準(zhǔn)方差最低。然后，再分析了[KE]對(duì)定位性能的影響。實(shí)驗(yàn)參數(shù)為：噪聲值[n=100]，[μN(yùn)]=0.4。5個(gè)錨節(jié)點(diǎn)、無(wú)線傳播距離為4 m。實(shí)驗(yàn)數(shù)據(jù)如圖2所示。

依據(jù)圖2a）的數(shù)據(jù)可知，定位誤差隨[KE]的增加而上升，但是，提出的ESDP_O算法的定位精度較穩(wěn)定，并沒有受到[KE]很大影響，這說(shuō)明ESDP_O算法具有很強(qiáng)的抗噪性能。平均標(biāo)準(zhǔn)方差隨[KE]的變化曲線如圖2b）所示，可知，ESDP_O算法仍獲得最低的方差，在[KE]的整個(gè)變化空間內(nèi)，誤差波動(dòng)小，而其他同類算法ESDP，EML和SDP?NLOS隨[KE]增加而上升。例如，在[KE=10-1]時(shí)，ESDP_O算法的平均標(biāo)準(zhǔn)方差僅為1.9 m，而EML，SDP?NLOS和ESDP算法的方差分別達(dá)到2.5 m，2.23 m和3.25 m。

3.2.2 實(shí)驗(yàn)二

本實(shí)驗(yàn)是基于LOS環(huán)境，且無(wú)線網(wǎng)絡(luò)為40 m×40 m，點(diǎn)數(shù)為15。此外，本次實(shí)驗(yàn)考慮兩類參數(shù)：一類（Case1）為噪聲值[n=100]，[r=6] m，[KE=0.005]；另一類（Case2）為[n=400]，[r=4] m，[KE=0.5]。從參數(shù)可知，Case2環(huán)境比Case1環(huán)境更為惡劣。表1分析了各算法在兩類參數(shù)下的平均定位誤差。從表1可知：ESDP_O算法在Case1環(huán)境下的定位性能并沒有得到提高，并且略低于EML和SDP?NLOS；但是，當(dāng)遭遇更為惡劣的環(huán)境Case2時(shí)，ESDP_O算法的定位誤差明顯高于其他同類算法。這些數(shù)據(jù)說(shuō)明，ESDP_O算法更適用于較惡劣環(huán)境。原因在于ESDP_O算法在估計(jì)節(jié)點(diǎn)位置時(shí)充分考慮了惡劣環(huán)境。

3.2.3 實(shí)驗(yàn)三

本次實(shí)驗(yàn)?zāi)康脑谟诜治鏊惴ǖ倪\(yùn)算量，并利用運(yùn)行時(shí)間表征運(yùn)算量。運(yùn)行時(shí)間越長(zhǎng)，運(yùn)算量越大，算法越復(fù)雜。實(shí)驗(yàn)參數(shù)為[KE=0.1]，[r=6]，[m=5]。所有連接均在LOS環(huán)境，且[n=100]，200，300，400。各算法的運(yùn)行時(shí)間如表2所示。

從表2數(shù)據(jù)可知，ESDP_O算法相比于其他算法在同等條件下的運(yùn)行時(shí)間最少。這說(shuō)明ESDP_O算法在提高對(duì)惡劣環(huán)境抵御能力的同時(shí)，并沒有提高算法的復(fù)雜度。

4 結(jié) 語(yǔ)

針對(duì)無(wú)線傳感網(wǎng)絡(luò)的節(jié)點(diǎn)定位問(wèn)題，提出ESDP_O算法。ESDP_O算法以ESDP算法為基礎(chǔ)，通過(guò)抖動(dòng)矩陣增強(qiáng)了對(duì)含有噪聲的非視距的惡劣環(huán)境的魯棒性。同時(shí)通過(guò)獲取低秩解，降低算法的復(fù)雜度。實(shí)驗(yàn)數(shù)據(jù)表明，提出的ESDP_O算法在惡劣環(huán)境下的定位精度得到有效地提高。

參考文獻(xiàn)

[1] 金家保，張頌，楊景曙.一種基于二階錐規(guī)劃的新時(shí)差定位算法[J].電訊技術(shù)，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] 王其華，郭戈.基于到達(dá)時(shí)間差的半定松弛規(guī)劃優(yōu)化的定位算法[J].大連海事大學(xué)學(xué)報(bào)，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] 時(shí)潔，楊德森，時(shí)勝國(guó).二階錐規(guī)劃在噪聲源穩(wěn)健定位識(shí)別中的應(yīng)用[J].哈爾濱工程大學(xué)學(xué)報(bào)，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.