非视距环境中的无线网络残差加权定位算法*

尹烨佳,华惊宇,李 枫,张 昱,余旭涛

(1. 浙江工业大学信息工程学院,杭州 310023;2.浙江工商大学信息与电子工程学院,杭州 310018;3.东南大学移动通信国家重点实验室,南京 210096)

近十几年以来,无线通信网络中目标节点的精确定位已成为人们关注的热点。目前,主要的定位技术可以分为基于卫星定位以及基于地面无线定位两大类。前者主要用于户外环境中,例如基于GPS的导航,其中非军用用户可以实现大约几十米的定位误差。但是GPS很难应用于室内定位以及那些无法获取GPS位置的环境中。因此,我们的研究将关注于地面无线定位问题,例如基于WSN的无线定位。

地面无线定位按照是否基于测距又可分为range-free和range-based两大类。前者往往需要高密度的节点分布作为条件[1],但是,现实环境中网络规模和节点密度差异性非常大,因此,本文主要研究基于range-based的定位方法,这类方法主要取决于选择何种定位参数。现有定位技术中主要有基于到达时间(TOA)估计[2-3],基于到达时间差(TDOA)估计[4-5],基于信号场强(RSSI)估计[6],基于到达方向(AOA)估计[7],以及基于混合参量估计,比如TOA/AOA,TDOA/AOA和RSS/AOA[8-9]。此外,这类range-based的定位方法存在两种非理想因素,一种是测量误差,另一种是由信号传播过程中折射和反射等现象引起的非视距NLOS(Non-Line Of Sight)误差。前者一般被定义为均值为零的高斯变量,相对而言,这种误差的标准差一般很小[10];而后者NLOS误差则是无线定位中最为主要的误差,NLOS传播会导致较大的时延和角度偏差,因此会大大降低无线定位算法的精度。在实际的无线网络中,它的误差值可以到达通信半径的20%～50%[11],而且由于实际环境中无线网络的复杂性无法对其进行精确建模,所以NLOS误差的抑制和消除已成为无线定位算法能否实际应用的关键。

为提高非视距环境下的定位精度,目前主要存在以下几类误差抑制的算法:第一类叫模型法,就是利用类似训练的方法对非视距误差先进行精确建模,然后根据建立的模型来估计目标节点的位置[12-13]。但是由于实际环境的复杂性和动态性很难得到一个精确的模型,因此该类算法很难得到广泛应用。第二类叫检测法,首先利用LOS节点与NLOS节点的参数差异,识别出基于视距传输的静态节点(LOS-SN),剔除非视距传输的静态节点(NLOS-SN),最后只利用LOS传输的静态节点进行位置估计[14-15]。如果能够正确识别出所有的视距传输的静态节点,且LOS-SN节点数足够多的条件下,那么该算法的定位精度将会非常高,但是由于虚警率的存在很难做到检测的正确性,因此该类算法的实际定位精度往往很难满足实际需求。第三类算法是应用所有的SN信息,包括LOS节点和NLOS节点,然后利用优化算法得到目标节点位置,这种方法虽然能得到较高的定位精度,但是计算复杂度比较高[3-4],如半正定规划SDP算法,其利用的是半正定规划的内点法,这类方法属于多项式时间算法,迭代复杂性较高。第四类算法叫权重法,就是对节点进行分组,并给每一组的临时位置估计分配合适的权重并求和以提高目标节点位置的估计精度。我们往往利用几何关系和代数关系,最典型的就是利用残差参数构建加权函数[16-18]。这类算法的优点是能区别利用LOS及NLOS节点的信息,对于LOS节点的信息给予比较大的权重值,对于NLOS节点就给予较小的权重值,最终科学充分地利用LOS节点信息,提高定位精度。传统权重类定位算法的缺点是权重的选择设计不够科学,往往不能充分利用LOS节点信息,所以本文提出了一种改进的权重定位算法。

本文在传统的权重算法上进行改进,主要方法如下,首先对所有静态节点(SN)进行分组,由于选用的参数不同,每组都可得到3个目标节点估计位置。同时因为存在测距误差和NLOS误差,得到的目标位置估计之间必然存在位置差,将该差值定义为临时定位残差。区别于传统的残差加权定位算法,本文根据所选残差特点,提出用残差的高次幂作为加权函数,并通过仿真寻找最优的加权函数。最后给每个目标估计位置分配相应的权值并加权求和得到最终的TN估计位置。主要贡献有①采用了一种新的残差定义,即临时定位残差;②结合该残差值的特点提出了新的权重函数,并根据残差值对权重函数做了优化搜索。计算机仿真结果表明本文提出的算法要优于其他对比的抗NLOS定位算法,尤其是对比传统的残差加权定位算法,定位精度得到了较大的提高。同时本文提出的算法属于线性类算法,其计算复杂度与输入的数据规模成正比,计算复杂度较优化类算法低。

1 基于临时定位的残差定义

图1 定位几何模型

假设目标节点TN的坐标为(x,y),静态节点SN的坐标为(xi,yi),那么TN和SN之间的距离可以表示成:

(1)

θi=arctan[(y-yi)/(x-xi)]

(2)

利用静态节点SN1和SN2所得的测距,可以得到如下方程组:

(3)

(4)

(5)

类似地,点B坐标的求解方程为:

(6)

如用矩阵形式表示,以点A为例:

Y=AXA

(7)

如果传输环境中不存在NLOS,那么目标节点TN的位置即可通过最小二乘算法求解,即

(8)

同样地,点B的坐标也是可以通过解类似于(8)的方程组得到。因此可以定义点A和B之间距离即为临时定位残差:

(9)

从图1中我们可知,两个定位圆的交点有2个,为简便,我们可以简单地将残差定义为

(10)

那么临时定位残差就可以表示成:

(11)

上式中的C′表示在C,F两点中找出距离A点或B点更近的点,将其记为C′。从上述残差的定义中我们可以看出,如果仅存在测距噪声,那么上述得到的三个TN位置估计都是相对较精确的,那么所对应的临时残差值也很小。如果存在NLOS传输的静态节点,那么由于利用的定位参数本身存在很大偏差,据此得到的估计位置就会远远偏离真实位置,而且偏离的趋势也会有所不同,这就导致了残差值的上升。据上图1所示,虽然理论上F点也可作为目标节点的临时估计位置,但是所有的临时估计位置应该集中在一个小范围内,由于F点距离其余的几个临时估计位置较远,所以本文抛弃了F点。

2 临时定位残差加权算法

图2 算法流程图

得到每个分组的TN临时位置估计以及相应的权重值后,确定最终目标位置估计,如下所示:

(12)

式中:Wi(Δ)表示和临时定位残差相关的加权函数,ETNi表示第i个静态节点组对TN的估计位置,它可以表示为

(13)

经过分析可知,临时定位残差较小的静态节点组得到的中间位置估计应当获取较大的权重,这就说明选择的权重函数应该是一个减函数。在传统RWGH算法中,直接利用残差的倒数作为权值,这就可能导致在静态节点数目较少的情况下对NLOS误差的抑制不足,我们的仿真结果也印证了这一点。分析造成上述现象的原因,主要还是因为RWGH这种算法的加权函数选择过于平庸,以及所采用的残差定义对于NLOS误差也不够敏感,因此我们考虑使用函数值变动更加剧烈的高幂次方作为加权函数,并通过实际仿真验证我们的假设。

Wi(Δ)=(1/Δ)n,n≥2

(14)

如图3所示,对比各条曲线可知,权重函数(即临时定位残差的n次方)的n值越大,其对应曲线越陡,表示对应的权重函数越灵敏。如此一来,我们就可充分利用LOS-SN的信息,大大提高了最终的定位估计精度。另外,对比n=5和n=10的曲线可知两者趋于重合,所以不再研究n>5的权重函数。

图3 不同权重函数的数值变化

3 计算机仿真与分析

本文的仿真全都是在MATLAB中完成,其中静态节点坐标如下:(0,0),(100,100),(-100,100),(-100,-100),(100,-100),单位是米。并且假设测距和AOA测量值的误差均为零均值的高斯变量,假设NLOS传输对距离测量带来的误差为0和max之间服从均匀分布的变量[16],而AOA的NLOS误差则为零均值的高斯变量,但其标准差相对较大[19]。

3.1 加权函数的确定

假设测量距离标准差MDSD(Measuring Distance Standard Deviation)为1 m,测量角度标准差MASD(Measuring Angle Standard Deviation)为1°,NLOS的最大值max为40 m。

通过对比图3中的1次方,2次方和5次方加权函数的曲线,可知残差的幂次方所对应的数值对定位精度的影响非常显著,为进一步提高定位精度,接下来我们以5次方加权为基准对幂次方进行小数搜索。

从图4可知,幂指数值选在5附近时性能差别不大,从仿真结果看,我们选取最优值n=4.8。

图4 不同幂指数的CDF图

接下来我们选取不同的算法残差进行比较。其中posWk代表以临时定位残差倒数的k次方作为加权系数,同时我们引入最小二乘方法作为对比算法。

图5显示的是选择不同权重函数时的CDF图,从图5(a)和图5(b)可以发现,posW1的定位误差小于10 m的概率在2个LOS-SN条件下达到了87%,当LOS-SN数量达到3个时,概率更是达到了100%,而且其RMSE曲线在2个LOS-SN以及3个LOS-SN的情况下均要明显优于传统的LS算法,但是和posW4.8相比,后者的定位误差即使是在2个LOS-SN的条件下,定位误差值小于5 m的概率也高达94%,在3个LOS-SN的条件下误差值小于5 m的概率更是达到了99%,其定位性能显然要优于posW1算法。这就表明,对于利用定位残差的加权定位算法而言,要根据选择的残差定义,选择函数值变化较为剧烈的函数作为加权函数,从而使LOS估计位置可以得到充分的加权。

图5 选择不同权重函数的CDF图

图6 选择不同权重函数的RMSE图

3.2 不同算法的综合比较

接下来我们将分别研究测量距离标准差MDSD,测量距离标准差MASD,以及非视距NLOS误差对以下不同算法精度的影响,仿真条件为:在 2个LOS静态节点和3个LOS静态节点的环境中进行,其中NLOS误差在0～max之间均匀分布。

表1 对比算法描述

①测量距离标准差的影响

图7给出的是MDSD对各算法精度的影响。从图中可以看出,CLS,opt-LLOP,RWG以及HFOP这四种算法产生的估计误差较大,相比而言,SDP的定位性能较前四者有了显著的改进,特别是当环境中只有2个LOS-SN的条件下,但是跟本文提出的算法相比还是存在明显的差距。显然,我们可以发现本文提出的算法的定位性能要明显优于其他几种对比算法。虽然随着MDSD的增加,该算法的定位误差有所上升,但依然低于其他的对比算法。这是因为随着MDSD的增加,利用LOS-SN求得的目标估计位置所获得的权重值也随之降低,从而造成定位性能有所下降。此外从仿真结果可以看出,随着LOS-SN数量的增加posW4.8曲线接近于克拉美罗下界,也就是说本文提出的算法随着LOS-SN数量的增多,定位性能更好。

图7 MDSD对算法精度的影响

②测量角度标准差的影响

如图8所示是测量角度标准差MASD与定位均方根误差之间的关系,我们可以发现,随着横坐标MASD值的变大,除TOA/AOA-LS算法外,其余对比算法所对应的曲线基本持平,这是因为这些算法定位过程中没有利用角度信息。但是观之本文提出的posW4.8和对比算法TOA/AOA-LS,其对应的曲线随着横坐标的增大有明显的上升趋势,这是因为测角误差的增加造成了分配给精度较高的临时位置估计的权值下降了,使得定位精度也随之降低。图8表明本文提出的算法其定位精度远高于TOA/AOA-LS算法,这主要得益于新的权重函数和残差的良好适配,同时对比其他算法,本文所提算法的性能保持着明显的优势。

③不同max值的影响

图9 NLOS误差最大值max对各算法定位精度影响

图9的横坐标表示测量距离的NLOS误差最大值,纵坐标是定位均方根误差(RMSE)。对比图中各曲线可知,传统的残差权重算法(RWGH),线性最优化算法(opt-LLOP),约束最小二乘算法(CLS)以及运用海伦公式最优化算法(HFOP)的定位误差随着max的增加上升趋势都很明显。观之SDP算法,随着max值的增加,其上升幅度虽然没有前四者明显,但还是高于本文提出的posW4.8算法。从图中可知本文提出算法的精度随着NLOS误差的增大只是略有起伏,基本呈平缓趋势,也就是说本文提出的算法即使在NLOS误差较大的恶劣环境下也能具有较高的定位精度。

④角度域NLOS误差的影响

图10是非视距传输的角度测量误差值与定位均方根误差之间的关系。观察图中的曲线可知,随着角度NLOS误差的增加,各算法的RMSE值的变化并不显著。因为所有的对比算法都未利用到测角信息。而对于posW4.8算法,虽然从理论上分析,角度误差的增大会降低该算法的定位性能。但是从上述仿真结果可知,本文提出的算法的定位精度随着角度误差的增加基本趋于平缓,特别是在LOS静态节点数目为3时。这是因为随着角度NLOS误差的增加,虽然使得目标临时位置估计的定位误差值变大,但是由于其对应的权重函数值较小,所以最终对定位性能影响并不大。

图10 AOA的NLOS误差对各算法精度的影响

4 结论

为提高非视距环境下的定位精度,本文提出用目标临时位置估计之间的差值构建新的权重函数,并以临时位置估计加权和改善了定位性能。对比RWGH算法,本文算法不仅在定位精度上有了很大的提高,而且还降低了对LOS静态节点数目的要求。对比SDP类优化算法,本文提出的算法大大降低了计算复杂度同时也依然保持了性能优势。