﻿ 一种基于非视距误差补偿的协同定位算法<sup>*</sup>
 文章快速检索 高级检索

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 定位算法

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

1.1 Chan算法

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

 (1)

 (2)
 (3)
 (4)

 (5)

 (6)

 (7)

 (8)

1.2 粒子群算法

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

2) 个体适应度评价。

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

 (9)
 (10)

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

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

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

 图 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

 图 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)

 (12)

 (13)
 (14)

 (15)

 (16)

 (17)
 (18)

 (19)

4 协同定位算法

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) 步。

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

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

 (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 粒子群算法和协同定位算法的收敛曲线对比 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)

#### 文章信息

ZHANG Ran, SONG Lailiang, RAN Longjun

A collaborative localization algorithm based on non-line-of-sight error compensation

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