基于半定规划的恶劣环境下定位修正算法*

2017-05-24刘直良

传感技术学报 2017年5期

关键词：测距传感噪声

刘栓,刘直良

(黄淮学院信息工程学院,河南驻马店 463000)

基于半定规划的恶劣环境下定位修正算法*

刘栓*,刘直良

(黄淮学院信息工程学院,河南驻马店 463000)

无线传感网络WSNs(Wireless Sensor Networks)的定位精度严重受到环境的影响,尤其是高噪声电平和非视距连接的恶劣环境,定位精度急剧下降。为此,提出基于半定规划的恶劣环境下定位修正算法,记为ESDP_O算法。该修正算法以半定规划 ESDP(Edge-Semi-Definite Programming)算法为基础,旨在提高定位精度,并降低算法复杂性,进而减少定位时间。ESDP_O算法通过引用抖动矩阵,对ESDP算法进行修改,提高了算法在恶劣环境的健壮性。同时,ESDP_O算法通过寻找低秩解,减少高噪声和非视距偏差。仿真结果表明,在高噪声和非视距NLOS(Non Line of Sight)的恶劣环境下,ESDP_O算法的定位精度优于基于同类算法,并且降低了定位的复杂度。

无线传感网络;定位;半定规划;非视距;抖动矩阵

传感节点的位置在无线传感网络应用中扮演了重要的作用[-3],如异常事件检测、火灾感应、目标跟踪等,这些应用均需要获取节点的位置信息[4-5]。为了获取未知节点的位置信息,未知节点利用已知位置的节点(锚节点)与自己距离,再结合定位算法,进而估计自己的位置,其中测距是传感网络定位问题的关键。

针对传感网络定位问题,研究人员提出了许多不同方案[6-7]。文献[6]中,作者提出了一种基于二阶锥规划的时差定位算法,该算法将位置估计转化为二阶锥规划问题,再利用泰勒级数展开法估计节点位置。不少的研究人员也引用基于凸优松弛技术,将定位的非凸优问题转化为凸优化问题,然后运用凸优化理论中的二阶锥规划SOCP(Second Order Cone Programming)[8-9]、半定规划SDP(Semi-Definite Programming)松驰方法求解节点的位置。

然而,这些定位算法均假设测距是可视距LOS(Line Of Sight)环境,即节点间通信路径为LOS连接。但是,在多数实际环境中,这个假设难以成立。由于障碍物的影响,多数连接是属非视距NLOS(Non Line Of Sight)环境,并且也无法估计哪些连接是NLOS,哪些是LOS,这给传感节点定位提出了挑战。

为此,针对噪声和存在NLOS的恶劣环境,提出基于边半定规划ESDP(Edge-Semi-Definite Programming)松驰优化的定位修正算法ESDP_O。ESDP_O算法以ESDP算法为基础,再引用拉动矩阵,求解低秩解,提高了在恶劣环境下定位的鲁棒性,并降低算法的复杂度。仿真数据表明,提出的ESDP_O算法在恶劣的环境下,能够较准确地估计节点的位置,并降低定位复杂度。

1 定位模型及问题描述

假定传感网络由一系列的锚节点和普通传感节点组成,其中n个传感节点,它们的位置未知,且分别表示为x1,…,xn;m个锚节点,它们的位置已知,且分别表示为a1,…,am。传感节点xi与xj间的距离表示为ds,ij,类似地,传感节点xj与锚节点ak间欧式距离表示为da,jk。

无线传感网络二维定位问题可简化为:

FindX∈R2×n

(1a)

(1b)

(1c)

Y=XTX

(1d)

式中:X=[x1,…,xn]、Ns={(j,i)|‖xj-xi‖

凸松弛技术是解决传感网络定位问题的有效方法。文献[4]提出了半定规划SDP松弛算法,将式(1)的非凸问题转化为凸问题。为了获取低秩(low rank)解,文献[5]修改SDP。但是,与SDP相比,它并不能改善定位的准确性。这些方案是将受限的式(1d)转发为线性不等式LMI(Linear Matrix Inequality),如式(2)所示:

(2)

式中:In表示单位矩阵。

此外,与SDP相比,基于边半定规划ESDP松弛算法的复杂度下降,并且具有与SDP相同的定位准确性[10]。利用ESDP松驰算法可解决式(1),因此可将式(1)转化为式(3):

(3a)

s.t.Z(1,2),(1,2)=I2

(3b)

(3c)

(3d)

Z(1,2,i,j),(1,2,i,j)>0, ∀(j,i)∈Ns

(3e)

α+,α-,β+,β-≥0

(3f)

式中:α+,α-,β+,β-分别为平方距离误差。

Z(1,2,i,j),(1,2,i,j)是Z是子矩阵。文献[11]提出基于边的最大似然EML(Edge-based Maximum Likelihood)松驰算法,提高了ESDP松驰算法的性能。然而,文献[4-11]所提出的方案均是基于所有节点均有可视距离LOS(Line of Sight)连接。然而,特别是室内网络的连接,多数是非视线距离NLOS(Non LOS)。

文献[12-13]采用了基于SDP方案对传感节点进行定位。文献[12]采用了SDP-M方案解决NLOS连接下的节点定位问题,也提高了定位的准确性。但是,它是以假定NLOS连接是可识别的为前提。而这个假设在文献[13]所提的情况是不合理的。文献[13]针对无NLOS先前信息的情况下,提出了定位算法,并且不区分NLOS和LOS连接。文献[13]采用式(4)所示的含有误差的距离测量模型:

(4)

为此,本文针对高噪声和NLOS偏差的环境下,提出基于ESDP的优化鲁棒定位算法ESDP_O。ESDP_O能够获取低秩解,并且引用新的基于SDP松驰算法,提高算法的鲁棒性。同时,ESDP_O算法是假定NLOS连接是未知的,并且考虑{bij}的统计也是未知,这更符合真实环境,旨在拓展ESDP_O算法的应用场景,提高在恶劣环境下的定位精度。

2 ESDP_O算法

ESDP_O算法整合了SDP松驰技术,旨在提高基于SDP定位方案在恶劣环境下的定位性能。测距是定位算法的关键。首先假定无误差测距:

(5a)

(5b)

式中:Z(true)表示矩阵Z中无误差的矩阵,ei为零列向量。

若存在测距噪声的环境中,结合式(3c)和(3d),将式(5a)和(5b)转换成式(6)所示:

(6a)

(6b)

(6c)

(6d)

式中:nij、δjk分别表示与ds,ij、da,jk相对应的噪声。Z(n)为Z的噪声矩阵。

(7a)

(7b)

依据式(5)～式(7)可知,测距误差容易引起矩阵Z的抖动,降低了定位的准确性。因此,矩阵Z可表述为:

Z(n)=Z(true)+Δ

(8)

将式(7a)和(7b)求解式(3),可得:

(9a)

(9b)

ωs,ij≤0,∀(j,i)∈NLs,ωa,jk≤0,∀(j,k)∈NLa

(9c)

(9d)

(9e)

式中:S、u和ω分别表示式(3)问题的变量。NLs和NLa包含满足式(7)的所有节点对。据于抖动和灵敏性分析,依据文献[14],可得:

(10)

(11a)

s.t. (3b),(3c),(3d),(3f),(7a),(7b)

(11b)

Z(1,2,i,j),(1,2,i,j)+P(1,2,i,j),(1,2,i,j)>0

∀(i,j)∈Ns∪NLs

(11c)

注意到式(11)的对偶问题的约束与式(9)的约束相同。那么目标函数如式(12)所示:

(12)

对式(11c)进行松驰化,就能获取式(3)的解,抵御Z(n)中的抖动。注意到Z中的特征值是正数,而式(11)中Z(1,2,i,j),(1,2,i,j)特征值是负数。扩展定位问题的求解空间是为了获取低秩解。

WSN定位所耗的时间取决于Z的秩。而低秩解有助于降低求解时间。因此,建立抖动矩阵P的目的就是获取低秩解。假定Z和{S(i,j)}是式(11)的解,且呈对偶性。据此可得:

(13)

式(13)的证明过程如下:

(14)

然后,构建舒尔补(Schur complement)矩阵:

(15)

引用引理[12]:给定矩阵U∈Rm×n,且rank(U)≤q,有且只存在矩阵V=VT∈Rm×m、W=WT∈Rn×n,则:

(16)

证明完毕。

P(1,2,i,j),(1,2,i,j)=pijI4,∀(j,i)∈Ns∪NLs

(17)

因此,式(12)可转变为:

(18)

显然,正确地选择规范项是ESDP_O算法的关键。如果规范项过小,ESDP的解不受抖动矩阵的影响。反之,若过大,tr(Y-XTX)的值也随之增大,致使定位准确度下降。因此,应结合网络尺寸和噪声等级信息优化参数pij的选择。仿真结果表明,在测距存在误差的环境下,规范项的选择随测距误差变化,同时,定位准确度不随节点数的变化而变化。

3 性能分析

3.1 仿真环境

本节,通过仿真分析ESDP_O定位算法的性能,并利用MATLAB软件内凸优化工具箱CVX[15]求解定位问题(式11)。采用3.07GHz的处理器、8GRAM的计算机实施仿真。

采用平均定位误差APE(Average Position Error)衡量算法的定位性能,定义如式(19)所示。

(19)

(20)

为了充分分析ESDP_O定位算法的性能,选用ESDP[10]、EML[11]、SDP-NLOS[12]进行同步仿真,并进行性能比较。

3.2 仿真结果分析

仿真过程中考虑不同的应用场景,其中场景一、二考虑了NLOS环境,场景三、四考虑LOS环境。

3.2.1 场景1

本次仿真主要考查NLOS连接数占总的测距数的比率μN对定位误差和误差的标准方差影响。仿真参数KE、无线传输半径以及NLOS偏差的均值分别为0.1、6.0m以及5.0m。仿真结果如图1所示。

图1 μN对定位性能的影响

由图1(a)可知,平均定位误差随μN的增加而上升,进一步表明NLOS对测距存在负面影响。NLOS连接的存在,降低了测距的准确性,进而影响了定位的精度。与ESDP、EML和SDP-NLOS算法相比,ESDP_O算法的平均定位误差得到明显的下降,原因在于ESDP_O算法充分考虑了NLOS环境的存在,并且引用抖动矩阵,提高算法应对恶劣环境的能力。图1(b)反映了各算法的平均标准方差,与图1(a)数据相似,ESDP_O算法的平均标准方差最低,ESDP算法的平均标准方差最高。

3.2.2 场景2

本次仿真考查KE对定位误差和误差的标准方差影响。如式(4)所示,KE决定了测距误差。噪声值n=100,μN=0.4。5个锚节点、无线传播距离为4m,仿真结果如图2所示。

由图2(a)可知,KE的增加,降低定位精度。然而,与ESDP、EML和SDP-NLOS算法相比,ESDP_O算法受KE的波动甚少,这也进一步说明KE能够应对NLOS和大噪声环境,具有鲁棒性。图2(b)描绘了平均标准方差随KE的变化曲线。ESDP_O算法的平均标准方差最低,且在KE变化范围内,波动甚小。而ESDP、EML和SDP-NLOS算法随KE呈增加趋势,均高于ESDP_O算法。例如,在KE=10-1时,ESDP算法的平均标准方差高达3.25m,EML、SDP-NLOS算法的平均标准方差分别2.5m、2.23m,而ESDP_O算法的平均标准方差仅为1.9m。

图2 KE对定位性能的影响

3.2.3 场景3

本次场景是针对LOS环境,仿真区域为40m×40m,锚节点数为15,本次仿真考虑两类环境:一类(Case1)为噪声值n=100、无线传播距离r=6m、KE=0.005;另一类(Case2)为n=400、r=4 m、KE=0.5。Case2比Case1环境恶劣。各类算法的定位误差如表1所示。

表1 LOS环境下的平均定位误差

由表1可知,在Case1环境下,与ESDP、EML和SDP-NLOS相比,ESDP_O算法的定位性能并没有得到改善,甚至略高于EML和SDP-NLOS。而在Case2环境下,ESDP_O算法的定位误差低于ESDP、EML和SDP-NLOS算法。这些数据表明,提出的ESDP_O算法更适应于恶劣环境。

3.2.4 场景4

本次实验旨在分析各类算法的复杂度,用算法的运行时间表述。实验参数:KE、r=6分别为0.1 m、6 m。锚节点数为5,所有连接均在LOS环境下,在n=100、200、300、400时,各算法的运行时间如表2所示。

表2 算法的运行时间

由表2可知,在n从100变化至400区间,提出的ESDP_O算法的运行时间最少,说明其复杂度比其他算法的低。换而言之,ESDP_O算法在提高恶劣环境下的定位精度的同时,并没有增加算法的复杂度。此外,由表2可知,n的增加提高了算法的运行时间,增加定位的难度。

4 总结

针对无线传感网络的节点定位问题,提出了基于边半定规划ESDP(Edge-Semi-Definite Programming)松驰优化的定位修正算法ESDP_O。ESDP_O算法着重考虑了非视距和噪声的恶劣环境,以ESDP定位算法为基础,通过构建抖动矩阵,获取低秩解,降低算法的复杂度,提高在恶劣环境下的定位精度,增强算法的鲁棒性。针对不同的场景仿真,仿真结果表明,在恶劣环境下,提出的ESDP_O算法的复杂度和定位精度优于SDP-NLOS、ESDP算法。

[1] 金家保,张颂,杨景曙. 一种基于二阶锥规划的新时差定位算法[J]. 电讯技术,2012,52(6):887-893.

[2] 陶为戈,朱昳华,贾子彦. 基于RSSI混合滤波和最小二乘参数估计的测距算法[J]. 传感技术学报,2012,25(12):1748-1753.

[3] 程秀芝,朱达荣,张申,等. 基于RSSI差分校正的最小二乘法-拟牛顿定位算法[J]. 传感技术学报,2014,27(1):123-128.

[4] Biswas P,Ye Y.Semidefinite Programming for ad hoc Wireless Sensor Network Localization[C]//Proc 3rd Int Symp Inf Process Sens Netw(ITPN’04),Apr. 2004:46-54.

[5] Ji S,Sze K F,Zhou Z,et al. Beyond Convex Relaxation:A Polynomial-Time Non-Convex Optimization Approach to Network Localization[C]//Proc IEEE INFOCOM,Apr. 2013:2499-2507.

[6] 王其华,郭戈. 基于到达时间差的半定松驰规划优化的定位算法[J]. 大连海事大学学报,2013,39(4):59-64.

[7] 时洁,杨德森,时胜国. 二阶锥规划在噪声源健定位识别中的应用[J]. 哈尔滨工程大学学报,2011,32(12):1549-1558.

[8] Srirangarajan S,Tewfik A,Luo Z Q. Distributed Sensor Network Localization Using SOCP Relaxation[J]. IEEE Trans Wireless Commun,2008,7(12):4886-4895.

[9] Tseng P. Second-Order Cone Programming Relaxation of Sensor Network Localization[J]. SIAM J Optimization,2007,18(1):156-185.

[10] Wang Z,Zheng S,Ye Y,et al. Further Relaxations of the Semidefinite Programming Approach to sensor Network Localization[J]. SIAM J Optim,2008,19(2):655-673.

[11] Simonetto A,Leus G. Distributed Maximum Likelihood Sensor Network Localization[J]. IEEE Trans Signal Process,2014,62(6):1424-1437.

[12] Vaghefi R,Buehrer R. Cooperative Sensor Localization with NLOS Mitigation Using Semidefinite Programming[C]//Proc 9th Workshop Position Navigat Commun(WPNC’12),2012:13-18.

[13] Monir Vaghefi R,Buehrer M. Cooperative Localization in NLOS Environments Using Semidefinite Programming[J]. IEEE Commun Lett,2015,19(8):1382-1385.

[14] Boyd S,Vandenberghe L.Convex Optimization[M]. Cambridge,UK:Cambridge Univ Press,2004.

[15] Grant M,Boyd S,Ye Y. CVX:MATLAB Software for Disciplined Convex Programming[online]. Available:http://www.stanford.edu/～boyd/cvx. 2009.

Research on Semidefinite Programming Localization Enhancement in Complex NLOS Wireless Sensor Network Environment*

LIU Shuan*,LIU zhiliang

(College of Information Engineering,Huanghuai University,Zhumadian He’nan 463000,China)

The accuracy of localization in wireless sensor networks(WSNs)depends on noise level and the presence of nonline of sight(NLOS)connections. In this letter,a novel Edge semidefinite programming(ESDP)Robust localization algorithm is proposed and its goal is to improve the accuracy and reduce the algorithm complexity,and it reduce the required time for wireless sensor network localization in harsh environments,which is marked as ESDP_O. We modified ESDP relaxation by a perturbation matrix in order to make it robust against large errors in distance measurements. ESDP_O algorithm modified ESDP in order to find a low rank solution,and introduced a new class of ESDP-based relaxation that is robust against high level noise and NLOS biases. Simulation results confirm that our proposed method outperforms others when the majority of connections are NLOS,noise level is high,and the proposed ESDP_O algorithm can effectively reduce the computational complexity.

wireless sensor network;localization;semi-definite programming;nonline of sight;perturbation matrix