基于半正定规划的RSS-TOA联合定位算法

叶凯枫,楼喜中,梁 俊,金小萍

(中国计量大学 信息工程学院,浙江 杭州 310018)

无线传感器网络(wireless sensor network,WSN)在智能机器人、交通规划、海上救援、野火探测等工程和技术领域都有重要的应用,引起了学术界的广泛关注和研究。其中由于传感器节点在空间中是随机布置的,而找出节点的确切位置是必不可少的,所以无线传感器网络中的定位技术成为了研究重点。目前关于传感器节点的定位技术主要分为了以下两大类。

基于非测距手段的算法,诸如,质心、DV-Hop、APIT,PSO等元启发式优化算法[1,2],虽然该类算法对硬件要求不高,且传感器自身成本低、功耗小,但依旧存在定位精度低和根据不同环境而布置特定网络的缺点。

基于测距手段的算法,诸如,接收信号强度(received signal strength,RSS)、到达时间(time of arrival,TOA)、到达时间差(time difference of arrival,TDOA)[3]、到达角度(angle of arrival,AOA)等[4-5],与非测距相比,大多数实用的算法研究都鼓励基于测距的定位技术,因此上述RSS、TOA以及TDOA的定位技术都比较容易实现。其中TOA技术是计算从目标节点到锚节点的所需时间,然后通过三个锚节点相对目标节点测量的时间圆相交,便可以大致得到目标节点所在区域,但其依旧存在短距离定位性能差的缺点[6-8];TDOA是计算目标节点到不同锚节点的时间差从而估算出移动目标节点的位置,在TDOA技术中,如果采用下行链路方案,定位数据需要在目标节点端进行一定的处理并将数据上传给服务器,这也意味着目标节点的硬件系统需要更多数据处理的性能以及存储能力。因此,为了满足估计和同步的技术要求,其硬件成本将会高于TOA节点定位系统;在实际应用中,待测节点和锚节点选用的TOA技术不需要同步,而TDOA技术则需要严格的时间同步,两种技术相比,通常TOA技术的定位精度更高,但其容量低、功耗高,而TDOA技术的定位精度则稍差于TOA,但容量高很多,功耗也要低一些;相较于上诉两种定位方式,RSS技术存在长距离定位性能较差的缺点。文献[9]利用RSS和AOA相结合的方法,根据最小二乘法,建立混合目标函数,为了解决非凸函数不能全局收敛的问题,将混合目标函数转化为广义信赖域子问题进行求解,并通过二分法求解,能得到全局最优解。文献[10]利用TDOA和AOA相结合的方法,通过引入半定松弛法将目标函数松弛为二阶锥规划问题,寻找到全局最优解,能获得较高的定位精度。上述文献中AOA技术更依赖于复杂的天线阵列设计。综合以上定位技术,本文主要研究基于RSS-TOA的联合定位算法,近年来也有许多关于该类算法的研究。文献[6]针对室内环境下的信号衰减模型,对RSS和TOA的估计误差进行了建模,并利用高斯迭代法求解该误差模型,然而,当传感器网络中的节点间距较大时,该方法的定位误差会变大。文献[7]提出了在RSS中加入TOA信息来抑制误差,在极大似然法(ML)的基础上将非线性的等式转化为线性等式,再利用拟牛顿法近似求解目标节点的位置,但利用拟牛顿法求解这类非线性问题本身就存在较大的误差。文献[8]在最小二乘法(LS)的基础上进行了改进,利用泰勒展开构建新的约束条件,提出改进的二步最小二乘法(TSLS)将目标位置的范围逐步缩小,然后估计出目标位置。然而,过度近似将带来误差。以上方法均存在的求解估计问题是非全局最优问题,难以找到待估计目标节点的全局最优点。

基于上述背景,我们提出一种新的联合RSS-TOA信息的SDP定位算法。该算法在RSS和TOA系统模型的基础上构建了一个加权最小二乘问题。然后,利用凸优化技术转化成SDP问题,使得算法可以达到最小二乘估计问题的全局最优点,以此找到更精确的目标节点位置,由此提高了算法的精度。

1 系统模型

在传感器网络中,N个锚节点位置记为si(i=1,…,N),待估计的目标节点的位置记为x,通过测量信号从待测目标节点到锚节点时所经过的时间得到TOA信息,通过测量信号从锚节点到待测目标节点得到RSS信息,对应的RSS信息模型以及TOA信息模型如下:

(1)

(2)

图1 RSS-TOA联合定位示意图Figure 1 A diagram of the RSS-TOA joint localization

2 SDP定位算法的推导

根据以往的方法获取RSS和TOA的信息后,可以通过最小二乘法或者极大似然法近似估计出目标节点的位置,但是这些方法难以找到待估计目标节点的全局最优点,容易造成较大的估计误差。因此,提出了一种基于SDP的联合RSS和TOA信息的定位算法。SDP定位算法的推导包括如下三个步骤。

步骤1:通过使用加权最小二乘法准则(WLS),构建了关于联合的RSS测量信息以及TOA测量信息的目标函数优化方程。

步骤2:利用凸优化技术将目标函数优化方程转化为约束情况下的目标函数优化问题。

步骤3:利用半正定松弛技术将问题转化为SDP问题,最终利用凸优化软件CVX进行求解。

具体的SDP定位算法的推导过程如下。首先分离出RSS信息的噪声测量误差,对式(1)移项可以得到

(3)

对其两边同除以10γ,并取10对数可得:

(4)

令

(5)

最终得到关于RSS信息的噪声测量误差的伪线性表达式:

(6)

针对误差量,关于RSS信息下未知目标节点的LS估计为

(7)

同理,分离出TOA信息噪声测量误差为

(8)

针对该线性表达式,得到TOA信息下未知目标节点的LS估计为

(9)

结合式(7)和式(9),将上述问题转化为如下加权最小二乘问题:

(10)

式(10)的加权最小二乘问题是非凸非线性函数,不能保证全局收敛,故引入两个辅助变量λi,μi,它可等价为约束情况下的目标函数优化问题:

(11)

上述表达式的约束条件是非凸的,因为其未知节点变量x的一次项二次项是非凸的,对x的一次项进行凸松弛,对x的二次项改写为线性表达式,可以松弛变换为

(12)

(13)

其中,

(14)

(15)

基于此,上述两个约束条件改写为

(16)

(17)

最终,通过凸优化技术,式(10)的加权最小二乘问题转化为了一个SDP问题,全局可收敛,能求出全局最优解x:

(18)

这是一个凸优化问题,对比之前的非凸算法,进行凸优化技术后大大降低了算法的复杂度;并且相较于拟牛顿法[7]和两步最小二乘法[8],所提出的SDP算法复杂度也与其相当。式(18)可以使用标准的凸优化问题求解软件CVX求解,并快速得到目标节点x的估计位置。

3 仿真结果与分析

为了验证本文所提出的联合RSS-TOA的SDP定位算法的定位性能,通过MATLAB对其进行仿真,仿真环境设定为二维的正方形区域,并且假定环境中的噪声均为高斯白噪声,路径损耗指数γ=3。设定4个锚节点传感器被放置在四个角,其坐标分别为(0,0),(0,B),(B,B),(B,0),待定位的目标节点随机产生在该区域内,如图2,其中B为边界宽度。

图2 仿真场景布局图Figure 2 Layout of simulation scenario

为了更好的比较,对基于拟牛顿法的RBFR算法[7]和基于改进的最小二乘法的TSLS算法[8]的性能也进行了仿真。此外,分析了SDP算法的联合定位性能,将其与仅使用RSS的算法与仅使用TOA的算法的性能进行比较。本文采用平均定位误差(average location error,ALE)作为定位算法性能的衡量标准。对应的,平均定位误差的公式定义如下:

(19)

3.1 噪声标准差性能仿真

在本组仿真中,考虑传感器网络中的RSS观测值与TOA观测值在受到环境中观测的噪声标准差对定位性能的影响。在这里引入克拉美-罗界(Cramer-Rao Lower Bound,CRLB)[8]的概念,一般CRLB可以用于估算无偏估计中能够获得的最佳精度,因此经常用于衡量算法的性能优劣。理论上来说定位结果标准差一定要大于等于克拉美-罗界。

在仿真中设定的仿真场景如图2。从图3可以看出,当噪声标准差影响因素从1 dB增加到6 dB时,SDP算法的平均定位误差从1.6 m增加到6.6 m,而TSLS算法的平均定位误差从3.8 m增加到7.9 m,RBFT算法的平均定位误差从4.0 m到10.0 m。因此,当噪声标准差数目为6 dB时,SDP算法的平均定位误差相比于TSLS算法低了16.46%左右,而相比于RBFT算法低了34%。这说明随着噪声标准差的变大,三种算法的平均定位误差都会变大,而SDP算法的定位精度始终要优于TSLS算法和RBFT算法。

图3 噪声标准差性能比较Figure 3 Performance comparison of noise standard deviation

3.2 锚节点数目性能仿真

在本组仿真中,考虑传感器网络中锚节点数目对定位性能的影响。在仿真中设定的仿真场景仍为图2,此时,在正方形区域边界上均匀的添加锚节点传感器,数目从4均匀增加到16,噪声标准差的影响因素固定为6 dB。

从图4中可以看出,当边界宽度和噪声标准差一定时,三种算法的平均定位误差均随着锚节点数目的增加而逐渐减小,且在锚节点数目达到16个以上的数量时,平均定位误差的变化趋势逐渐趋于平稳,SDP算法下的未知节点平均定位误差稳定在2.5 m左右。这主要是由于锚节点数的增多使得未知节点能够得到更多的RSS和TOA的定位信息,从而减小定位误差;而当布置的锚节点数目较多的时候,RSS和TOA信息逐渐趋于饱和,误差的变化趋势也会趋于平稳。最后,从整体上来说,不管锚节点数目增加多少,SDP算法的平均定位误差较TSLS算法平均定位误差低25%左右,较RBFT算法平均定位误差低50%左右。

图4 锚节点数目性能比较Figure 4 Performance comparison of the number of anchor nodes

3.3 联合定位算法性能仿真对比

在本组仿真中,同时分析了SDP算法的RSS-TOA联合定位性能,并将其与RSS以及TOA两种算法独立运行的性能进行比较。仿真环境如图2,实验中待测定位点的数目相同,并且锚节点传感器数目设为10个。其中一组噪声标准差的影响因素固定为6 dB,其边界宽度从10 m均匀增加到50 m;另一组条件是其边界宽度固定为40 m不变,噪声标准差的影响因素从1 dB增加到6 dB。

从图5中可以观察到RSS-TOA的联合定位算法的平均定位误差要低于独立使用的RSS或者TOA算法的平均误差。同时还可以得到RSS-TOA的联合定位算法的平均定位误差要低于单独使用RSS的算法以及单独使用TOA的算法。与此同时,随着仿真环境中设定的定位宽度的增加,所有算法的平均定位误差都会变大。此外,值得注意的是,单独使用RSS算法的平均定位误差在定位环境边界宽度较小的情况下与联合RSS-TOA测量的性能更接近,单独使用TOA测量的算法在边界范围较大的情况下与联合RSS-TOA测量的性能更接近,而联合RSS-TOA克服了RSS长距离定位和TOA短距离定位性能较差的缺点,其整体平均定位误差比独立的TOA算法或者独立的RSS算法平均定位误差低了50%左右。从图6可以看出,在边界条件固定,噪声标准差变化时(噪声标准差从1 dB增加到6 dB),可以观察得到,噪声标准差越低,所有定位算法的整体平均定位误差越小,定位性能越好;在各种噪声标准差下,RSS-TOA的联合定位算法的平均定位误差都低于独立使用RSS算法的平均误差和独立使用TOA算法的平均误差,其定位性能更好。

图5 定位的边界宽度性能比较Figure 5 Performance comparison of positioning boundary width

图6 定位的噪声标准差性能比较Figure 6 Performance comparison of positioning noise standard deviation

4 结 语

本文在联合使用RSS信息与TOA信息的情况下提出了一种高精度的SDP定位算法。该算法在加权最小二乘法的准则下构建了目标节点估计方程,最终利用凸优化技术构建了一个SDP算法。相比独立的RSS定位和TOA定位,所提出的联合SDP算法提高了目标节点定位的精度,此外,与基于拟牛顿法的RBFR算法以及最小二乘法的TSLS算法相比也具有更好的定位精度。