文章快速检索  
  高级检索
一种基于非视距误差补偿的协同定位算法
张然, 宋来亮, 冉龙俊     
北京航空航天大学 仪器科学与光电工程学院, 北京 100083
摘要: 非视距(NLOS)误差对超宽带(UWB)室内定位技术的定位精度有很大影响。针对此问题,根据NLOS环境下附加时延和由信道决定的均方根时延扩展的联合统计特性,估计NLOS误差的均值和方差,对定位算法测量值和系统测量误差协方差进行修正,并采用时变权重的粒子群算法与Chan算法相结合的协同定位算法进行定位计算,具有良好的全局搜索与局部搜索最优解的能力。仿真结果表明,在NLOS环境下,相比于单一算法,协同算法定位精度提高30%左右,在一定程度上抑制了NLOS误差的影响,满足室内定位的要求。
关键词: 超宽带室内定位     非视距误差     Chan算法     粒子群算法     协同定位算法    
A collaborative localization algorithm based on non-line-of-sight error compensation
ZHANG Ran, SONG Lailiang, RAN Longjun     
School of Instrumentation Science and Opto-electronics Engineering, Beijing University of Aeronautics and Astronautics, Beijing 100083, China
Received: 2016-06-29; Accepted: 2016-10-14; Published online: 2016-12-13 15:25
Corresponding author. SONG Lailiang, E-mail:songlailiang@buaa.edu.cn
Abstract: The non-line-of-sight (NLOS) error has great influence on the positioning accuracy of the ultra-wideband (UWB) indoor positioning technology. Aimed at this problem, this paper estimates the mean and variance of NLOS according to the joint statistical properties of the additional time delay in NLOS and the root mean square delay spread decided by the channel, modifies the measurements of the localization algorithm and the covariance of the systematic measurement error, and uses a collaborative localization algorithm, which combines the particle swarm optimization algorithm with time-varying weight and Chan algorithm and has a favorable ability of global search and local search for optimal solutions. The simulation result shows that the collaborative algorithm improves the positioning accuracy by about 30%, compared to a single algorithm. It, to a certain extent, inhibits the effect of NLOS error, and meets the requirements of indoor location.
Key words: ultra-wideband indoor positioning     non-line-of-sight error     Chan algorithm     particle swarm algorithm     collaborative localization algorithm    

近年来,随着人们需求的增加,室内定位技术越来越受到研究人员的关注[1-2]。超宽带(UWB)室内定位技术由于其穿透能力强、功耗低、抗多径能力强和传输速率高等特点,成为当今社会的研究热点[3]。在室内无线定位过程中,到达时间差(TDOA)[4]定位算法是理想的定位方法,其主要的误差来源主要是测量误差和非视距(NLOS)误差[5]。NLOS误差[6]是由于室内障碍物的阻隔,发生反射和折射等现象引起的,由NLOS误差引起的附加时延是定位误差的主要来源[7]。因此NLOS误差的抑制是研究UWB室内定位首要任务。

为了抑制NLOS误差的影响,国内外已提出多种解决方案,Wylie和Holtzman[8]提出了一种重构法,对NLOS误差进行校正,减小NLOS误差的影响,该方法需要利用视距(LOS)情况下的先验信息,在较差的环境中难以实现。Chen[9]提出了一种残差加权法,通过对定位结果进行加权平均以减小NLOS误差影响,该方法需要较多的基站参与定位。文献[10]通过引入校正因子代入最小二乘算法,逐步迭代降低NLOS的影响,主要应用于室外环境,在室内环境中健壮性差、精度低。

本文通过对UWB信道模型IEEE 802.15.4a[11]的仿真,分析了非视距误差对UWB室内定位的影响,利用NLOS环境下信号的传播时延特性,由概率论知识估计附加时延的均值与方差[12],修正测量值,根据修正后的数据,利用Chan算法与粒子群算法相结合的协同定位算法进行定位,该算法在抑制NLOS误差的同时,提高了室内定位精度,满足定位的要求,而且Chan算法与粒子群算法在无线传感器网络定位中都有着广泛的应用,因此协同定位算法适用于实际应用中。

1 定位算法

TDOA定位算法是通过测量2个基站到达目标位置的传播时间差来确定目标位置,由时间差可以得到1条以2个基站为焦点的双曲线,因此只需2组时间差值,得到2条双曲线,其交点就是待测目标位置[13]

1.1 Chan算法

Chan算法[14]是一种具有解析表达式的典型TDOA算法,在测量误差较小的情况下可达到克拉美罗下界(CRLB)。设定位目标位置坐标为(xy),第i个基站坐标为(xiyi),基站到目标位置的距离为di,第1个基站与第i个基站到目标位置的距离差为di, 1,由此可以得到

(1)

式中:Ki=xi2+yi2。由于

(2)
(3)
(4)

式中:xi, 1=xix1; yi, 1=yiy1。非线性方程组就变成了线性方程组,求出方程组中的xy值就求得目标位置坐标。令za=[zpT, R1],zp=[x, y]T,假设za的元素间相互独立,则za的最大似然估计为

(5)

式中:Ψ=E(ψψT)=c2BQB, B=diag{d10, d20, …, dM0},di0di (i=1, 2, …,M)无噪声时的表达式,Q为TDOA的协方差矩阵,c为电磁波在空气中的传播速度。当目标位置距离较远时,di0d0很接近,故Bd0I,式(5) 近似为

(6)

式中:

当目标位置距离较近时,可以利用式(6) 得到一个初始值来计算矩阵B,代入式(5) 即可获得第1次加权最小二乘估计值。

利用上面得到的第1次的估计值,再重新构造误差方程组进行第2次估计得

(7)

式中:

式中:za, 1za, 2分别为目标位置x坐标和y坐标;za, 3为第1个基站到目标位置的距离。通过2次最小二乘法得到目标位置的最终坐标为

(8)

可以看出,以上2次最小二乘估计都是基于系统测量误差服从均值为0的前提下,系统测量误差包含在该算法的加权矩阵内,因此在一定程度上消除了系统误差的影响。

1.2 粒子群算法

粒子群算法[15]模仿鸟类的觅食行为,通过迭代寻优计算,能快速地找到近似解。该算法具有实现简单、精度高、收敛快等优点,在处理非线性优化问题和组合优化问题时有很好的效果[16],因此适用于求解TDOA非线性方程组,将双曲线方程组作为粒子群算法待优化函数,求得的最优解即为目标位置坐标。算法流程如下:

1) 初始化种群和设置参数。设定参数的运动范围,学习因子c1c2,当前的进化代数k。其中第i个粒子(i=1, 2, …, S)的位置表示为Xi、速度表示为Vi,取粒子群当前最优解为B

2) 个体适应度评价。

3) 由式(9) 和式(10) 更新粒子的速度和位置。

(9)
(10)

式中:w为惯性权重; r1r2为0到1的随机数; k=1, 2, …,Gi=1, 2, …, S

4) 计算更新后的粒子的适应度值,比较当前适应值f(Xi)与自身历史最优值pi,如果f(Xi)较好,则置pi为当前值f(Xi),并更新粒子位置。

5) 比较粒子当前适应值f(Xi)与种群最优值B,如果f(Xi)优于B,则更新B的值。

6) 检查终止条件,若满足预设条件,则结束寻优;否则k=k+1,转至3)。

粒子群算法流程图如图 1所示。

图 1 粒子群算法流程图 Fig. 1 Flowchart of particle swarm algorithm
2 超宽带传播信道模型

UWB通信是一种使用非常宽的频带来收发数据的技术,因此其信道特征与传统的窄带通信系统有所不同[17]。IEEE 802.15.4 a[11]工作小组基于诸多信道模型的建议和基于实测数据的归纳,提出了能普遍接受的信道模型,其中包括2~10 GHz的UWB信道模型,共分为4种环境:居住环境、室内办公环境、户外环境和工业环境,每种环境均分为LOS情况和NLOS情况[18]。本文主要研究室内居住环境LOS与NLOS情况下UWB信号的传输。图 2(a)图 2(b)分别为室内LOS(CM1) 和NLOS情况下(CM2) 信道的冲激响应。

图 2 CM1信道和CM2信道冲激响应 Fig. 2 Impulse response of CM1 channel and CM2 channel

图 2可以看出LOS情况下,首径的幅度最大,传递的能量最高,而NLOS情况下,多径幅度衰减较慢,时间弥散性强,幅度最大的径也不是第一个到达,这是由于信号在传播过程遇到障碍物发生反射和折射现象引起的。在CM1和CM2信道下,采用基于脉冲序列最大能量的到达时间测距算法,发送信号为二阶微分高斯脉冲,直接序列编码调制,发射机与接收机的实际距离为14.142 m,基于脉冲序列最大能量的到达时间测距算法能量块仿真结果如图 3所示,通过MATLAB软件仿真,测得LOS和NLOS情况下,脉冲序列最大能量值对应的时延为t1=47.35 ns,t2=50.15 ns,测距误差为e1=0.062 9 m,e2=0.902 9 m,可见,NLOS误差对于UWB信号室内传播产生了很大的影响。

图 3 CM1信道和CM2信道基于脉冲序列最大能量到达时间测距算法的能量块图 Fig. 3 Energy block diagram of maximum energy arrival time ranging algorithm based on pulse sequence of CM1 channel and CM2 channel
3 非视距误差补偿

NLOS误差在不同信道下服从指数分布、均匀分布与Delta分布[19]。本文认为其近似服从指数分布进行分析,概率密度函数为

(11)

式中:τi, rms为信道决定的均方根时延扩展,表示为τi, rms=T1diεξT1τi, rmsdi=1 km时的中值,由IEEE 802.15.4 a[11]信道模型仿真可得,室内NLOS环境下均方根时延扩展T1≈19 ns,ε为0.5~1之间的一个常数, ξ表示服从均值为0、方差σξ=4~6 dB的对数正态分布的随机变量。可知,ln τi, rms~N(ln(T1diε), σξ2),可以得到τNLOSi的概率密度函数为

(12)

由此可计算NLOS误差的均值和方差[20]

(13)
(14)

在TDOA算法中,Ri, 1表示第1个和第i个基站到目标位置的距离差,则有

(15)

式中:, i=1, 2, …, Mτi, 1为基站1和基站i到目标位置的到达时间差[21]。在NLOS情况下

(16)

式中:τi, 10为LOS环境下的TDOA值;ni, 1为系统的测量误差,服从N(0, σni, 12)的高斯分布;τNLOSi, 1为NLOS引起的附加时延误差,均值为μNLOSi, 1,方差为σNLOSi, 12

由式(13) 和式(14) 可得

(17)
(18)

可以看出τNLOSi, 1服从正均值的高斯分布,使得整体误差均值不为0,这使得定位精度受到很大影响,因此,需要对TDOA测量值进行修正:

(19)

其中ni, 1服从N(0, σni, 12+σNLOSi, 12)正态分布,这样就符合Chan算法极大似然估计条件,然后将优化后的TDOA测量值代入Chan算法和粒子群算法中进行定位估计。

4 协同定位算法

在LOS环境下,Chan算法的加权矩阵只考虑了均值为0的测量误差,2次最小二乘估计在一定程度上抵消了系统测量误差带来的影响,而NLOS误差的存在会使总体误差为正均值,也就是说位置的估计是有偏的,会使得Chan算法的定位精度有所下降。而粒子群算法求解非线性方程经过多次迭代受到NLOS误差的影响较小,计算快速准确且鲁棒性好。因此,本文提出一种在NLOS环境下改进的定位算法,即利用Chan算法与粒子群算法相结合的协同定位算法进行定位。

由于在NLOS环境下,粒子群算法优于Chan算法,因此,首先利用粒子群算法获得一个初始位置,用此初始位置修正TDOA测量值τi, 1和系统测量的协方差Q,Chan算法利用修正后的数据进行计算得到N组解,然后将这N组解作为粒子群算法的种群初始位置更新迭代,粒子群在更新速度和位置时,采用线性递减的时变权重[22],这样粒子群算法在开始时具有良好的全局搜索能力,能快速定位到近似全局最优解的区域,随着权重递减,后期具有良好的局部搜索能力,能快速找到最优解,会得到更好的算法性能。算法具体步骤如下:

1) 假设在NLOS环境下,共测得M组TDOA数据,根据基站坐标,利用粒子群算法获得一个初始估计位置。

2) 由以上初始位置计算目标位置与各基站之间的距离di,根据式(17) 计算μNLOSi, 1,由式(19) 计算TDOA修正值τi, 1

3) 根据式(18) 计算σNLOSi, 12,重构系统测量误差的协方差Q

4) 根据重构后的τi, 1Q,用Chan算法计算N组目标位置坐标(N≥100)。

5) 根据修正后的τi, 1作为TDOA测量值,用粒子群算法估计目标位置,将Chan算法得到的N组数据作为粒子群算法的初始种群位置。

6) 更新粒子的位置和速度,惯性权重采用从0.90线性递减到0.10的时变权重,计算更新后的粒子适应度值,寻找最优解。

7) 检查终止条件,若满足,则停止迭代,否则重复第6) 步。

协同定位算法有两大优势:① Chan算法结果作为粒子群算法的初值,缩小了粒子群的搜索范围,加快了收敛速度;② 粒子群在更新速度和位置时,采用线性递减的时变权重,具有较好的全局搜索能力和局部搜索能力,能更快地找到最优解。因此,相比于单一算法,协同定位算法收敛速度快,定位精度高,具有更好的定位能力。

5 仿真实验与分析 5.1 仿真条件设置

本文用MATLAB仿真工具进行算法验证,仿真采用IEEE802.15.4 a[11]信道模型CM1和CM2,设定在一个20 m×20 m的二维空间中,存在4个基站(BS1~BS4) 和1个目标位置,目标位置真实坐标取(14.142,14.142),其位置信息如图 4所示。

图 4 基站位置信息 Fig. 4 Location information of base station

误差累积分布函数(CDF)表示随机变量小于等于某个数值的概率,在此用均方根误差(RMSE)来计算误差累积分布函数,来对定位的结果进行衡量。仿真结果由100次独立估计过程得到, 均方根误差定义如下:

(20)
5.2 仿真结果与分析

5.2.1 定位精度

1) LOS环境下:图 5(a)图 5(b)分别表示Chan算法和粒子群算法在LOS情况下的定位性能对比。TDOA测量值系统测量误差服从均值为0的高斯分布,在此标准差分别取0.15、0.25和0.35 m进行定位估计。从图 5中可以看出,Chan算法和粒子群算法定位精度均受到系统测量误差的影响,而且随着测量误差的增大定位误差也增大。通过图 5(a)图 5(b)对比,可以得出,在LOS环境下,Chan算法和粒子群算法的定位结果曲线趋势大致相同,定位性能并没有很大差距。

图 5 Chan算法和粒子群算法在系统测量误差不同时的定位性能对比 Fig. 5 Comparison of positioning performance between Chan algorithm and particle swarm algorithm with different system measurement errors

2) NLOS环境下:图 6(a)图 6(b)分别表示Chan算法和粒子群算法在相同的系统测量误差标准差(0.35 m)下,LOS环境与NLOS环境定位性能的对比,可以看出,NLOS误差均造成2种算法定位性能下降,且对Chan算法的影响大于粒子群算法,因此,在NLOS环境下,粒子群算法表现出更高的定位优势。

图 6 Chan算法和粒子群算法在LOS环境与NLOS环境定位性能的对比 Fig. 6 Comparison of positioning performance in LOS and NLOS environment between Chan algorithm and particle swarm algorithm

3) NLOS误差补偿后:NLOS误差的存在使得系统误差为正均值,位置的估计有偏,Chan算法的定位精度有所下降,因此协同定位算法适用于NLOS环境下。图 7表示Chan算法和粒子群算法NLOS误差补偿后和协同定位算法之间的定位性能对比。可以看出,NLOS误差补偿后Chan算法定位性能有了很大提高,这是因为TDOA的修正值是无偏的,消除了NLOS附加时延带来的误差,而粒子群算法的定位精度没有得到明显的改善。协同定位算法的定位性能明显优于2种算法补偿后的定位性能,通过计算均方根误差平均值,定位精度提高30%左右,满足室内定位的要求。

图 7 Chan算法和粒子群算法NLOS误差补偿后和协同定位算法之间的定位性能对比 Fig. 7 Comparison of positioning performance among Chan algorithm after NLOS error compensation, particle swarm algorithm after NLOS error compensation, and collaborative localization algorithm

5.2.2 收敛速度

图 8表示在NLOS环境下,单一粒子群算法和协同定位算法的收敛曲线对比,可见,协同定位算法的收敛速度相比于单一粒子群算法较快,这是因为协同定位算法将NLOS误差补偿后的Chan算法结果作为粒子群算法的迭代初值,从而缩小了粒子群的搜索范围,加快了收敛速度,而且协同定位算法在更新速度和位置时,采用线性递减的时变权重,具有较好的全局搜索能力和局部搜索能力,能更快地找到最优解。

图 8 粒子群算法和协同定位算法的收敛曲线对比 Fig. 8 Comparison of convergence curves between particle swarm algorithm and collaborative localization algorithm
6 结论

1) 根据NLOS环境下附加时延和由信道决定的均方根时延扩展的联合统计特性,估计NLOS误差的均值和方差,并对TDOA测量值进行修正。在此基础上,提出了一种在室内NLOS环境下,采用时变权重的粒子群算法与Chan算法相结合的协同定位算法进行UWB室内定位。

2) 在理论分析和仿真的基础上进行了实验验证。实验结果表明:在NLOS环境下,TDOA测量值修正后,协同定位算法相比于单一算法有更好的定位性能,定位精度提高30%左右,满足室内定位要求。

参考文献
[1] TARZIA S P, DINDA P A, DICK R P, et al.Indoor localization without infrastructure using the acoustic background spectrum[C]//Proceedings of the 9th International Conference on Mobile Systems, Applications, and Services.New York:ACM, 2011:155-168.
[2] CIURANA M, BARCELO A F, MARTIN E I. Comparative performance evaluation of IEEE 802.11v for positioning with time of arriva[J]. Computer Standards & Interfaces, 2011, 33 (3): 344–349.
[3] IMMOREEV I Y. Ultrawideband radars:Features and capabilities[J]. Journal of Communications Technology and Electrnics, 2009, 54 (1): 1–26. DOI:10.1134/S106422690901001X
[4] LI C, ZHUANG W H. Hybrid TDOA/AOA mobile user location for wideband CDMA cellular systems[J]. IEEE Transactions on Wireless Communications, 2002, 1 (3): 439–447. DOI:10.1109/TWC.2002.800542
[5] SILVENTOINEN M I, RANTALAINEN T.Mobile station emergency locating in GSM[C]//Proceedings of the 1996 IEEE International Conference on Personal Wireless Communications.Piscataway, NJ:IEEE Press, 1996:232-238.
[6] DAMIEN B, DAVIDE D. Position error bound for UWB location in dense cluttered environments[J]. IEEE Transactions on Aerospace and Electronic Systems, 1998, 44 (2): 613–615.
[7] 张宴龙, 陈卫东, 陈畅. 基于非视距鉴别的室内移动节点跟踪算法[J]. 中国科学技术大学学报, 2014, 44 (10): 828–834.
ZHANG Y L, CHEN W D, CHEN C. Mobile location tracking based on NLOS identification in indoor environments[J]. Journal of University of Science and Technology of China, 2014, 44 (10): 828–834. DOI:10.3969/j.issn.0253-2778.2014.10.005 (in Chinese)
[8] WYLIE M P, HOLTZMAN J.Non-line of sight problem in mobile location estimation[C]//1996 5th IEEE International Conference on Universal Personal Communications.Piscataway, NJ:IEEE Press, 1996, 2:827-831.
[9] CHEN P C.A non-line-of-sight error mitigation algorithm in location estimation[C]//1999 IEEE Wireless Communications and Networking Conference.Piscataway, NJ:IEEE Press, 1999, 1:316-320.
[10] 王洪雁, 兰云飞, 裴炳南, 等. 非视距环境下基于到达时间差的一种定位算法[J]. 计算机仿真, 2007, 24 (9): 116–119.
WANG H Y, LAN Y F, PEI B N, et al. A location algorithm based on time difference of arrival in the non-line-of-sight environment[J]. Journal of Computer Simulation, 2007, 24 (9): 116–119. (in Chinese)
[11] MOLISCH A F, BALAKRISHNAN K, CHONG C C, et al. IEEE 802.15.4a channel model-final report[J]. IEEE P802, 2004, 15 (4): 0662.
[12] 段凯宇, 张力军. 一种在NLOS环境下提高精度的TDOA定位方法[J]. 南京邮电学院学报, 2005, 25 (5): 15–19.
DUAN K Y, ZHANG L J. An accuracy improved location method based on TDOA in NLOS environment[J]. Journal of Nanjing College of Posts and Telecommunications, 2005, 25 (5): 15–19. (in Chinese)
[13] LIN L X, SO H C, CHAN F K W, et al. A new constrained weighted least squares algorithm for TDOA-based localization[J]. Signal Processing, 2013, 93 (11): 2872–2878. DOI:10.1016/j.sigpro.2013.04.004
[14] CHAN Y T, HO K C. A simple and efficient estimator for hyperbolic location[J]. IEEE Transactions on Signal Processing, 1994, 42 (8): 1905–1915. DOI:10.1109/78.301830
[15] POLI R, KENNEDY J, BLACKWELL T. Particle swarm optimization[J]. Swarm Intelligence, 2007, 1 (1): 33–57. DOI:10.1007/s11721-007-0002-0
[16] KULKARNI R V, VENAYAGAMOORTHY G K. Particle swarm optimization in wireless-sensor networks:A brief survey[J]. IEEE Transactions on Systems, Man, and Cybernetics, Part C:Applications and Reviews, 2011, 41 (2): 262–267. DOI:10.1109/TSMCC.2010.2054080
[17] BATRA A, BALAKRISHNAN J, AIELLO G R, et al. Design of a multiband OFDM system for realistic UWB channel environments[J]. IEEE Transactions on Microwave Theory and Techniques, 2004, 52 (9): 2123–2138. DOI:10.1109/TMTT.2004.834184
[18] MOLISCH A F, FOERSTER J R, PENDERGRASS M. Channel models for ultrawideband personal area networks[J]. IEEE Wireless Communications, 2003, 10 (6): 14–21. DOI:10.1109/MWC.2003.1265848
[19] GREENSTEIN L J, ERCEG V, YEH Y S, et al. A new path-gain/delay-spread propagation model for digital cellular channels[J]. IEEE Transactions on Vehicular Technology, 1997, 46 (2): 477–485. DOI:10.1109/25.580786
[20] 杨北亚, 熊辉, 丁宏, 等. 应用NLOS鉴别补偿的无线传感器网络TDOA定位算法[J]. 重庆理工大学学报, 2015, 29 (10): 120–126.
YANG B Y, XIONG H, DING H, et al. TDOA location algorithm based on NLOS error identification and compensation in wireless sensor network[J]. Journal of Chongqing University of Technology, 2015, 29 (10): 120–126. DOI:10.3969/j.issn.1674-8425(z).2015.10.022 (in Chinese)
[21] ALAVI B, PAHLAVAN K. Modeling of the TOA-based distance measurement error using UWB indoor radio measurements[J]. IEEE Communications Letters, 2006, 10 (4): 275–277. DOI:10.1109/LCOMM.2006.1613745
[22] 刘金琨, 沈晓蓉, 赵龙. 系统辨识理论及MATLAB仿真[M]. 北京: 电子工业出版社, 2014: 215-227.
LIU J K, SHEN X R, ZHAO L. System identification theory and MATLAB simulation[M]. Beijing: Publishing House of Electronics Industry, 2014: 215-227. (in Chinese)
http://dx.doi.org/10.13700/j.bh.1001-5965.2016.0557
北京航空航天大学主办。
0

文章信息

张然, 宋来亮, 冉龙俊
ZHANG Ran, SONG Lailiang, RAN Longjun
一种基于非视距误差补偿的协同定位算法
A collaborative localization algorithm based on non-line-of-sight error compensation
北京航空航天大学学报, 2017, 43(7): 1426-1432
Journal of Beijing University of Aeronautics and Astronsutics, 2017, 43(7): 1426-1432
http://dx.doi.org/10.13700/j.bh.1001-5965.2016.0557

文章历史

收稿日期: 2016-06-29
录用日期: 2016-10-14
网络出版时间: 2016-12-13 15:25

相关文章

工作空间