非视距环境下基于粒子群的超宽带定位算法

张 然， 宋来亮， 冉龙俊

(北京航空航天大学 仪器科学与光电工程学院，北京 100191)

非视距环境下基于粒子群的超宽带定位算法

张 然， 宋来亮， 冉龙俊

(北京航空航天大学 仪器科学与光电工程学院，北京 100191)

将智能算法应用到无线传感器网络定位技术中是一种全新的尝试，粒子群算法是其中的一种典型算法。根据超宽带(UWB)定位原理，建立基于粒子群算法的定位模型，在非视距(NLOS)环境下，利用NLOS误差导致的附加时延和由信道决定的均方根时延扩展的联合统计特性，进行NLOS误差补偿，在迭代过程中采用线性递减的惯性权重，粒子群通过不断追踪个体极值和局部极值，更新自身的位置与速度，从而找到全局最优解，仿真结果表明正确率达90 %以上。

粒子群算法； 超宽带定位； 非视距； 线性递减； 惯性权重

0 引 言

随着无线电技术的发展，无线定位技术越来越受到人们的关注，在社会各个领域已获得了广泛的应用[1]。超宽带(UWB)信号具有丰富的带宽,在定位方面表现出很强的优势[2]，理论上定位精度可达2 cm，因此,UWB技术在精确定位方面具有广阔的发展前景[3]。常用的UWB定位测距方法有基于到达信号强度(RSSI)、到达信号角度(AOA)、到达信号时间(TOA)和到达时间差(TDOA)等方法[4]。基于TDOA定位算法主要的误差来源主要由2方面组成：系统测量误差，服从均值为零的高斯分布，对定位精度的影响较小；由于室内环境复杂，信号在传播过程中受到障碍物的阻隔，发生反射和折射等现象引起的非视距(non-line of sight,NLOS)误差，NLOS误差引起的附加时延对定位精度影响较大，是算法的主要误差来源。因此，减小NLOS误差的影响是研究UWB室内定位的首要任务。

本文介绍粒子群算法的基本原理及其TDOA模型，并对UWB信号传播信道IEEE 802.15.4a室内居住环境进行仿真，分析NLOS误差对UWB信号传播过程的影响，获得室内NLOS环境下的均方根时延扩展，利用NLOS误差导致的附加时延和由信道决定的均方根时延扩展的联合统计特性，估计附加时延的均值与方差[6]，修正TDOA测量值，根据修正后的数据，利用具有时变权重的粒子群算法进行定位，该算法抑制了NLOS误差的影响，提高了室内定位精度，满足室内定位的要求。

1 粒子群算法

粒子群算法[7]是智能算法中应用较为广泛的算法，它计算量小、收敛速度快，是求解非线性、组合优化问题的有效方法[8]。该算法适用于求解TDOA非线性方程组，将双曲线方程组作为粒子群算法待优化函数，求得的最优解即为目标位置坐标。

1.1 基于粒子群算法的TDOA模型

粒子群算法模仿鸟群的捕食行为，将每个优化问题的解比作搜索空间内的一只鸟，称为“粒子”。每个粒子都有一个由待优化函数决定的适应度值，该适应度值越大越好。每个粒子都有一个决定其飞行方向和距离的速度，粒子追随当前的最优值在解空间中搜索[9]。

UWB室内定位系统采用TDOA算法，不要求基站之间时钟的精确同步。定位原理为先测量出两个不同基站和目标节点之间的传播时间差，该传播时间差对应一个距离差，由此得到一组以这两个基站为焦点的双曲线。在有3个基站的情况下，得到2条双曲线，交点即为目标节点位置，TDOA计算公式为

(1)

式中 (x0,y0)，(xi,yi)为待定位的目标节点和固定已知的基站坐标;c为传播速度;τi,1为目标节点到第i个基站和第1个基站之间的传播时延差。可以利用粒子群算法求解TDOA的非线性方程，假设有4个基站，设

(2)

求解目标节点问题转化为利用粒子群算法求解函数f的最大值问题，个体的适应度值直接取为对应的目标函数值。

1.2 粒子群算法流程

1)初始化种群和设置参数:设定参数的运动范围，最大进化代数G，当前的进化代数kg。在一个D维的搜索空间中，种群规模大小为Size;第i,i=1,2,…,Size个粒子的位置为Xi;速度为Vi;从初始到当前迭代次数产生的个体极值Pi;整个种群目前最优解为BestS。随机产生初始种群的位置矩阵和速度矩阵。

2)个体适应度评价，并求出群体最优位置。

3)更新粒子的速度和位置，产生新群体，并对每个粒子的位置和速度进行越界检查。加入一个调整因子局部自适应变异算子，避免算法陷入局部最优

(3)

(4)

式中 w为惯性权重，本文采用时变权重[10]，即在迭代过程中惯性权重采用从0.90线性递减到0.10的策略;kg=1,2,…,G;i=1,2,…,Size;r1和r2为0～1的随机数;c1为局部学习因子;c2为全局学习因子。

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

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

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

2 UWB传播信道模型

UWB通信是一种利用ns级窄脉冲携带传输数据的技术，其信道特征与传统的窄带通信系统有所不同[11]。IEEE802.15.4a工作小组提出的UWB信道模型，共分为4种环境：居住环境、室内办公环境、户外环境和工业环境，每种环境均分为视距(LOS)情况和NLOS情况[12]。本文主要研究室内居住环境LOS与NLOS情况下UWB信号的传输。图1(a),(b)分别为室内LOS(CM1)和NLOS(CM2)情况下信道的连续时间冲激响应。

图1 CM1信道和CM2信道冲激响应

从图1(a),(b)可以看出:发射机发出一个脉冲信号时，在接收端生成了多个多径分量。在LOS情况下，首径的幅度最大，传递的能量也最高，多径分量的幅度衰减服从指数分布；在NLOS情况下，幅度最大的径不是第一个到达的，多径幅度衰减也较慢，时间弥散性强，这是由于信号在传播过程遇到障碍物发生反射和折射现象引起的。为了分析NLOS误差对信号传输所造成的影响，在CM1和CM2信道下，采用基于脉冲序列最大能量径的到达时间测距算法估计能量最高径的到达时间，算法流程如图2所示。

图2 基于脉冲序列最大能量到达时间测距算法流程

发送信号为二阶微分高斯脉冲，直接序列编码调制，发射信号波形如图3(a)所示，可知产生的随机直接序列码为-1，在无噪无多径的环境下接收端接收到的UWB传播时延波形如图3(b)所示，图中虚线为发射端发射信号，实线为接收端接收到的脉冲信号。

图3 发射端与接收端的单脉冲波形

取发射机与接收机的实际距离为14.142m，基于脉冲序列最大能量的到达时间测距算法能量块仿真结果如图4(a)，(b)所示，通过Matlab软件仿真，测得LOS和NLOS情况下，脉冲序列最大能量值对应的时延分别为t1=4.735×10-8s，t2=5.015×10-8s，测距误差分别为e1=0.062 9m，e2=0.902 9m。可见，NLOS误差对于UWB信号室内传播产生了很大的影响。

图4 基于脉冲序列最大能量到达时间测距算法能量块图

3 NLOS误差的补偿

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

(5)

(6)

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

(7)

(8)

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

Ri,1=cτi,1=Ri-R1,i=2,3,…,M

(9)

(10)

(11)

(12)

可以看出τNLOSi,1服从正均值的高斯分布，使得整体误差均值不为零，即位置的估计是有偏的，使得定位精度受到很大影响，因此，需要对TDOA测量值进行修正

(13)

将修正后的TDOA测量值代入粒子群算法的解析式中，进行目标节点位置估计。

4 仿真实验与分析

4.1 仿真参数设置

本文用Matlab仿真工具进行算法验证，在粒子群算法仿真中，取粒子群个数为Size=50；最大迭代次数G=100；粒子移动的最大速度为Vmax=1.0，即速度范围为[-1.0,1.0]；学习因子取c1=1.3，c2=1.7；采用从0.90线性递减到0.10的惯性权重。信道选取为IEEE 802.15.4a信道模型的CM1和CM2信道，设定在一个20 m×20 m的二维空间中，存在4个基站(BS)和1个目标位置，目标位置真实坐标取(10，10)，其位置信息如图5所示。

图5 基站位置信息

4.2 仿真结果与分析

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

(14)

在室内LOS和NLOS环境下，利用粒子群算法对目标节点进行位置估计，其定位性能对比如图6所示，可见，NLOS对定位性能有较大影响，收敛速度慢，定位精度较低。

图6 粒子群算法在室内LOS与NLOS下定位性能对比

在NLOS环境下，利用式(13)对NLOS误差进行补偿，修正TDOA测量值，将修正值代入粒子群算法的TDOA模型中，对目标节点位置进行估计，NLOS误差补偿前与补偿后的定位性能对比如图7所示，可见，该算法在一定程度上抑制了NLOS误差的影响，提高了定位精度，满足室内定位的要求。

图7 NLOS误差补偿前后定位性能对比

在粒子群算法中，个体的适应度值直接取对应的目标函数值，值越大越好。在粒子群算法的TDOA模型中，修正TDOA测量值，适应度函数F的优化过程如图8所示，由仿真结果可知，在迭代过程中，粒子群通过不断追踪个体极值和局部极值，更新自身的位置与速度，从而找到全局最优解。通过采用线性递减的时变权重和环形领域法，增强了算法的局部搜索能力，有效地避免了陷入局部最优解，仿真结果表明正确率达90 %以上。

图8 适应度函数F的优化过程

5 结 论

本文以粒子群算法求解非线性方程组的理论为基础，结合TDOA定位原理，建立基于粒子群算法的UWB定位模型。根据IEEE 802.15.4a信道仿真，分析NLOS误差对定位精度的影响，用NLOS误差导致的附加时延和信道决定的均方根时延扩展的联合统计特性，修正TDOA测量值。在粒子群算法中，个体的适应度值直接取其对应的目标函数值，在迭代过程中采用线性递减的惯性权重，增强了算法的局部搜索能力，有效地避免了早熟现象，仿真结果表明:该算法容易实现、收敛速度快、定位精度高，适用于NLOS环境下的UWB定位模型中。

[1] 邬春明,耿 强,刘 杰,等.DGPS与UWB混合精确无缝定位技术研究[J].传感器与微系统,2012,31(3):74-77.

[2] Immoreev I Y.Ultrawideband radars:Features and capabilitie-s[J].Journal of Communications Technology and Electrnics,2009,54(1):1-26.

[3] 韩培培,张 申,张永政.超宽带无线传感器网络性能分析[J].传感器与微系统,2009,28(2):31-34.

[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.

[5] Molisch A F.IEEE 802.15.4a channel model subgroup final report[J].IEEE P802,2004,15:943-968.

[6] 段凯宇,张力军.一种在NLOS环境下提高精度的TDOA定位方法[J].南京邮电学院学报,2005,25(5):15-19.

[7] Kennedy J.Encyclopedia of machine learning[M].New York: Springer,2011:760-766.

[8] 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.

[9] 张 伟.基于粒子群优化的三维测向交叉定位算法[J].传感器与微系统,2014,33(5):141-147.

[10] 刘金琨,沈晓蓉,赵 龙.系统辨识理论及Matlab仿真[M].北京:电子工业出版社,2014,215-227.

[11] 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.

[12] Molisch A F,Foerster J R,Pendergrass M.Channel models for ultrawideband personal area networks[J].Wireless Communications,IEEE,2003,10(6):14-21.

[13] 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.

[14] 杨北亚,熊 辉,丁 宏,等.应用NLOS鉴别补偿的无线传感器网络TDOA定位算法[J].重庆理工大学学报,2015,29(10):120-126.

UWB localization algorithm based on particle swarm optimization in NLOS environment

ZHANG Ran， SONG Lai-liang， RAN Long-jun

(School of Instrumentation Science and Opto-electronics Engineering,Beihang University,Beijing 100191,China )

Appling intelligent algorithm to wireless sensor networks(WSNs)positioning technology is a new attempt,particle swarm optimization(PSO)algorithm is one of the typical algorithms.According to the principle of ultra wideband(UWB)localization,positioning model based on PSO algorithm is established,in non-line-of-sight(NLOS)environment,use joint statistical properties of additional time delay caused by NLOS error and the root mean square delay spread decided by channel for NLOS error compensation,in the process of iterative,linear decreasing inertia weight is used,particle swarm update their own position and velocity by continuously tracking individual extremum and local extremum,so as to find the global optimal solution and the simulation results show that the accuracy is above 90 %.

particle swarm optimization(PSO)algorithm; ultra wideband(UWB)localization; non-line-of-sight(NLOS); linear decreasing; inertia weight

10.13873/J.1000—9787(2017)09—0117—04

2016—07—27

TN 929.5

A

1000—9787(2017)09—0117—04

张 然(1990-)，女，硕士研究生，研究方向为基于超宽带的室内定位技术,E-mail：524118920@qq.com。