运用海伦公式的最优化非视距抑制定位算法*

李溯南,华惊宇,*,李佳珉,卢为党,陈芳妮,余旭涛

(1.浙江工业大学通信网应用技术研究省重点实验室,杭州 310023;2.东南大学移动通信国家重点实验室,南京 210096)

自从1996年美国联邦通信委员会公布E-911定位精度的标准以来,无线定位技术与基于位置的服务已经成为研究热点,在目前的无线传感网和物联网应用中具有广泛的应用[1]。在无线传感网中,通常包括3个以上固定节点SN(Static Node)和若干移动节点MN(Mobile Node),而SN的地理位置是已知的,定位主要针对MN。另一方面,三边定位方法从节点的几何关系出发,采用某个定位参量建立方程组并求解获取MN位置估计。其中算法采用的定位参量包括到达时间(TOA)[2]、到达时间差(TDOA)[3-4]、接收信号强度(RSS)[5]、信号到达角(AOA)[6]以及其他一些混合参数[1,7-8]。

在实际的定位应用中,定位算法会受到两类误差的影响。一是测量噪声,通常建模为零均值的高斯变量[9]。在视距LOS(Line of Sight)传输条件下,测量噪声是影响定位精度的主要因素。而在非视距NLOS(Non-Line of Sight)传输环境中,信号传输路径中障碍物阻挡产生的非视距误差是影响定位精度的主要因素。例如,在蜂窝网络中非视距误差可以达到数百米[10]。遗憾的是,非视距误差的概率分布模型往往无法得到,所以很难消除非视距误差对定位精度的影响。

在定位算法中对NLOS误差的处理主要有三类方法。第1类就是对NLOS误差进行参数化建模[11],但是如前所述,实际环境中的NLOS误差多变以致无法精确建立概率模型,因此这一类方法的使用十分受限。第2类方法就是从大量SN中识别出受非视距误差影响的SN并将其剔除,仅使用LOS传输的SN进行定位[12],但是这类方法首先要求SN的数量必须达到要求,同时必须有至少3个SN满足视距内传输的条件,因此在NLOS误差影响比较严重的环境中无法使用。第3类方法就是从SN与MN之间的几何关系出发,对得到的距离测量值进行加权和最优化搜索,之后再根据加权后的距离测量值估计MN位置[13-15]。

本文主要研究第3类最优化方法,利用SN与MN之间的定位几何关系提出了面积残差的定义,进而建立二次规划问题并求解以实现测量距离的有效加权,最终得到MN的位置估计。算法中的面积残差基于海伦公式和两类测量距离构建,最优化的代价函数则同时包含面积残差和圆交点惩罚函数的影响。仿真分析表明,在消除非视距误差对于定位精度的影响上,本文提出的算法优于对比算法,且可以在SN数量较少时工作良好。同时仿真中还发现在NLOS误差较大或者SN数目增加时,本文算法将有更好的性能。

1 非视距传输环境下的测距模型与定位方法

MN与SN之间的距离可以表示为:

(1)

式中:(xi,yi)代表第i个SN的位置,而(x,y)代表需要定位的MN的位置。假设测量距离为di,则有

ri=αidi

(2)

在NLOS传输环境中,αi总落在0和1之间,这是因为信号无论被折射或者反射都会使得测量距离大于真实距离。即使不考虑NLOS影响,在测量距离中还包含测量误差,它一般远小于NLOS误差。

类似于文献[13,15],联合(1)和(2),易得

(3)

对方程组(3)化简得到

(4)

Y=AX

(5)

式中

根据最小二乘原理,可以得到向量X的解为

(6)

通过上面的公式可知,如果距离的加权向量已知,或者可以精确的获取,就可以精确地计算出SN与MN之间的实际距离,进而得到最终的位置估计[15]。

2 最优化定位算法

2.1 面积残差原理

图1中第1个SN(SN1)和第2个SN(SN2)的测距可以得到一个MN坐标估计,它与SN1/SN2构成一个三角形,而真实的MN位置与两个SN同样构成一个三角形。这两个三角形的面积可以由海伦公式计算得到。如果测距是精确的,那么这两个三角形面积应该是相等的,否则面积差值大于零。因此对于N个SN,我们可以将它们分成若干组,每组两个SN。每一组都可以根据图1原理计算面积差值,而所有分组的面积差值之和将与权值向量的精确性有关,可以用于定义面积残差,具体在下一小节论述。

图1 NLOS环境中面积残差原理图

2.2 面积残差与代价函数定义

(7)

以及使用原始测距作为自变量的MN—SN三角形面积表达式

(8)

如2.1所述,如果不存在任何误差这两个面积表达式的结果应该是相同的,即:

(9)

将式(9)两端平方并化简得到

(10)

考虑所有的SN分组,我们可以得到N-1条方程:

(11)

方程组(11)左边减去右边可以等效表征图1中三角形面积表达式的差值,则我们可以构建面积残差代价函数[16]:

(12)

定义权值向量v如下:

(13)

(14)

式中

需要注意加权缩放之后的距离应该保证所有SN的定位圆交于一点,因此需要在上述代价函数中增加惩罚函数,即:

(15)

式中:Xi与‖·‖分别表示第i个SN坐标以及向量模值。则最终的代价函数为

(16)

式中:D为一个足够大的常数,本文中选为1010。

2.3 约束二次规划问题

综合以上2小节,本文定位算法可以归结为一个二次规划问题

(17)

与文献[12,14]类似,向量v的下限vmin为:

(18)

3 仿真结果

3.1 测距噪声与NLOS误差强度的影响

图2给出非视距误差在10 m～35 m上均匀分布时的定位误差累计分布函数(CDF),可以看出即使是表现最好的TOA CLS算法其误差也要大于本文算法。在CDF为0.9时,本文算法的定位误差相比其他算法至少小40%。

图2 NLOS误差服从10 m～35 m均匀分布时的累积分布函数

图3给出NLOS误差最大值不同取值对于定位性能的影响,其中MIN固定为5 m。从图中可以发现本文算法具有最小的平均定位误差,且定位误差差距大于3m。这表明本文算法对于NLOS误差的适应性优于对比算法。

图3 不同MAX值对性能的影响

图4给出测距噪声标准差不同取值对于定位性能的影响,其中MAX=35 m。可以看到所有算法对于测距噪声标准差的敏感性都不强,但是本文算法具有最小的平均定位误差,定位误差的性能优势超过5 m。

图4 不同噪声标准差对性能的影响

3.2 SN数目对定位精度的影响

图5 3个SN时的算法性能对比

图6 7个SN时的算法性能对比

5 结论

非视距误差是无线定位中的一个重要影响因素,它显著降低了定位的准确性。因此本文在传统最优化定位基础上,利用海伦公式构建了面积残差和代价函数,综合运用约束二次规划和最小二乘方法抑制非视距误差的影响。仿真结果表明,在不同强度的非视距误差和测距噪声下,文中所提出的算法都要优于对比算法,且本文算法对于SN数目敏感性较低,可以用于SN数目较少的情形。

[1] Cheung K W,So H C,Ma W K,et al,A Constrained Least Squares Approach to Mobile Positioning:Algorithms and Optimality[J]. EURASIP Journal on Advances in Signal Processing,2006,2006(1):1-23.

[2] Wang X,Wang Z,O’Dea B,A TOA-Based Location Algorithm Reducing the Errors Due to non-Line-of-Sight(NLOS)Propagation[J]. IEEE Trans. Vehicular Technology,2003,52(1):112-116.

[3] Chan Y T,Ho K C,A simple and efficient estimator for hyperbolic location[J]. IEEE Trans Signal Processing,1994,42(8):1905-1915.

[4] Zhang H,Yu M,Cui X,et al,An improved Taylor series based location algorithm for IEEE 802.15.4a channels[C]//Proc 2011 IEEE Pacific Rim Conference on Communications,Computers and Signal Processing,2011:499-503.

[5] Yan Y,Efficient convex optimization method for underwater passive source localization based on RSS with WSN[C]//Proc 2012 IEEE International Conference on Signal Processing,Communication and Computing,2012:171-174.

[6] Lee Y S,A study on the performance of wireless localization system based on AOA in WSN environment[C]//Proc 2011 Third International Conference on Intelligent Networking and Collaborative Systems,2011:184-187.

[7] Zhaounia M,Landolsi M A,Bouallegue R,Hybrid TOA/AOA mobile localization with NLOS mitigation in ring scattering environments[C]//Proc 2008 3rd International Symposium on Wireless Pervasive Computing,2008:370-373.

[8] 严长虹,马静,三维传感网空间RSS与AOA混合测量的精确定位方法[J]. 传感技术学报,2017,30(3):450-455.

[9] Chen P,A Non-Line-of-Sight Error Mitigation Algorithm in Location Estimation[C]//Proc 1999 IEEE Wireless Communications and Networking Conference,1999:316-320.

[10] Silventoinen M,Ranralainen T,Mobile station emergency locating in GSM[C]//Proc 1996 IEEE International Conference on Personal Wireless Communication,1996:232-238.

[11] AL-JAZZAR S,Caffery I,ML and Bayesian TOA location estimators for NLOS environments[C]//Proc 2002 IEEE VTC,2002:856-860.

[12] Chan Y T,Tsui W Y,Time-of-Arrival based localization under NLOS conditions[J]. IEEE Trans. Vehicular technology,2006,55(1):17-24.

[13] Venkatraman S,Caffery J,You H R,A novel TOA location algorithm using LOS range estimation for NLOS environments[J]. IEEE Trans Vehicular technology,2004,53(5):1515-1524.

[14] Hua J Y,Zheng Z L,Jiang B,et al,A study on residual weighting algorithm for mobile localization[J]. Information Technology Journal,2013,12(5):640-647.

[15] 郑志龙,华惊宇,江彬,等,运用最优化原理的新型非视距抑制无线定位算法[J]. 传感技术学报,2013,26(05):722-727.

[16] 龚纯,王正林. 精通MATLAB最优化计算[M]. 北京:电子工业出版社,2009:179-205.