非视距环境下的超宽带室内定位算法

，

(河海大学 能源与电气学院，南京 211100)

0 引言

近年来，随着人们需求的增长，不论是在工业领域还以日常生活中，越来越重视室内的精确定位与导航。为了满足人们日益增长的需求，国内外研究人员将多种技术应用到室内定位领域中，例如红外传播技术、超声波技术、射频识别技术(FRID)、Wi-Fi技术、低功耗蓝牙技术以及超宽带技术[1]。超宽带技术(UWB)是近年来新兴的无线通信技术，无需用到传统通信中的载波，利用纳秒级的极窄脉冲传输信息，具有多径分辨能力强、功耗低、穿透能力强等特点[2]，这些优势使得超宽带技术在室内定位领域有较好的发展前景。UWB定位中基于测距常用的算法有基于信号到达强度(RSSI)、到达信号角(AOA)、到达信号时间(TOA)、到达时间差(TDOA)等方法[3]。其中最常见的是TDOA算法，在该算法中有两个主要的误差来源：一是系统测量值误差，包括随机测量误差和时钟漂移引起的误差两部分，相对而言对定位结果精度的影响不大；另一个影响较大的误差是由于信号在复杂的室内环境下传播时，遇到多种障碍物发生反射、折射、衍射甚至穿墙而过，从而引起的非视距(non-line of sight，NLOS)误差[4]，由于该误差导致的额外时延对最终的定位结果影响较大，是影响定位精度的主要来源。因此，减弱非视距误差对定位精度的影响是研究超宽带室内定位技术的重要问题。

根据特定NLOS环境中的参数建立均方根时延扩展模型，通过额外时延和均方根时延扩展的关系计算出额外时延的参数，用估计出的额外时延参数来调整TDOA定位模型。再将重构后的TDOA模型转化为粒子群算法中的适应度函数，从而可利用粒子群算法估计出精确的目标位置。本文提出的优化算法可以有效抑制NLOS对测量值的影响，提高室内定位的精度和算法收敛速度。

1 系统模型建立

1.1 TDOA定位模型的建立与重构

(1)

(2)

γ(t)=(1+e)t+ψ

其中，t为理想时间，e为频率漂移，ψ为频率偏差，假设各基站和目标节点的时钟漂移速率保持一致，则基站i和基站1到目标节点的信号传播时间差由于时钟漂移引起的误差表示为：

μei,1=E(τei-τe1)=μei-μe1

(3)

(4)

因此，由以上分析可知式(2)可进一步改写为：

(5)

由此，实现了对TDOA定位模型的重构，为了得出τi,1的值，还需要计算出超宽带信号在NLOS环境中传播的误差τei值。

1.2 延迟拓展参数的求解

NLOS误差在不同的信道环境下服从指数分布、均匀分布以及Delta分布[6]。选择延迟拓展按照其中的指数分布模型来分析非视距误差，其概率密度函数为：

(6)

(7)

(8)

(9)

根据概率论的知识，结合式(6)和式(9)可得延迟拓展误差τei的概率密度函数 ，其中τi,rms≥0：

由此可得τei的均值和方差分别为：

(10)

(11)

由式(10)、(11)进一步可得TDOA测量模型中的式(3)和式(4)中的参数：

(12)

(13)

1.3 目标函数的建立

(14)

其中:λ=σ2σ3…σM-1

λ2=σ3σ4…σM-1

λM-1=σ2σ3…σM-2

求解使式(14)的似然函数值最大的解，相当于求解满足下式最小的解：

(x0,y0)=arg{min[(A-B+C-U)T(A-B+C-U)]}

为了求出此函数的最小值，用一般的解析法解此类非线性函数比较困难，且有较大误差，为解决这一难题，本文将一种群智能优化算法——粒子群优化算法应用到最优解的求解中，将上式函数作为粒子群算法中的适应度函数，从而可通过迭代估计出目标节点的坐标值。

2 基于LS-PSO优化的NLOS定位算法

2.1 初始位置的估计

根据TDOA数学模型式(1)并将其进行线性化处理可得：

(15)

(16)

其中:Ri,1=Ri-R1

将上式(15)、(16)相减，得：

(17)

xi,1=xk-x1；yi,1=yk-y1

在式(17)中，将x0，y0，R1当作未知变量，那么该式则成为线性方程租，此线性方程组的解则作为目标节点的初始估计位置。将TDOA测量值看作实际值代入到下列式子，采用最小二乘法[8]估计出的目标节点初始粗略位置为：

其中:

2.2 基于粒子群算法的NLOS定位

粒子群优化算法(particle swarm optimization，PSO)是一种群体仿生智能算法，起源于对鸟群觅食过程中迁徙和聚集的模拟[9]。算法描述为：在一个给定的D维区域中，有N个粒子组成的群体x=[x1,x2,…,xN]，每一个粒子都视为潜在解且有自身的位置和速度信息，每个粒子的位置坐标为xi=[xi1,xi2,…,xiD]，速度表示为vi=[vi1,vi2,…,viD]。PSO经典算法是在D维空间中随机初始化一群粒子，此时的每个粒子都视为潜在解，将每个粒子的位置坐标代入适应度函数中，通过适应度函数值反映每个粒子的优劣情况；在每一次的迭代中，粒子根据局部最优解和全局最优解来更新当前的位置和速度，从而在给定区域内运动，在迭代过程中群体里的所有粒子会向着适应度值最佳的粒子的方向运动，直到经过若干次迭代后找到最优解；局部最优解是指每个粒子在经过目前的迭代次数后所找到的自身的最优解，可以表示Pbesti=[pi1,pi2,…,piD]，全局最优解是指全部粒子在经过目前的迭代次数后所找到的整个离子群的最优解，可以表示为Gbest=[g1,g2,…,gD]；在经过一次自身最优解和群体最优解的更新过后，每个粒子再将自身目前的速度和位置代入下面两个公式更新速度和位置：

vi(t+1)=ω*vi(t)+c1*rand()*(Pbesti-xi(t))+

c2*rand()*(Gbest-xi(t))

xi(t+1)=xi(t)+vi(t+1)

式中，t为当前迭代次数；ω为惯性权重，其值表示粒子对目前速度、状态的依赖程度；c1，c2为学习因子，取值为2；rand()为服从均匀分布的随机数[9]。

由于粒子群算法随机初始化一群粒子，导致其初始收敛速度慢的缺陷[7]，在本文2.1节通过最小二乘法得出目标节点的初始估计位置可以有效解决该问题，较少了收敛时间，则粒子群算法的初始位置可表示为：

xi1=Za(1)+rand()

xi2=Za(2)+rand()

其中:rand()的作用是产生分布在[0，1]内的随机数，可以使粒子群算法的初始粒子在最小二乘法估计出的位置附近开始搜索，达到了提高收敛速度的目的。本文中使粒子群算法停止的条件是最大迭代次数，设置的最大迭代次数设置为itermax=100。

对于算法中的惯性权重ω，一般情况下按照线性递减的方式变化，若函数一旦进入局部极值点就很难跳出，从而陷入局部最优[9]。文献[10]指出，当惯性权重ω服从正态分布时，算法的全局搜索能力较传统的线性递减时有明显提高，可避免陷入局部最优，能够有效协调全局和局部搜索在算法中的权重。高斯函数服从正太分布，因此本文使惯性权重按照高斯函数递减，表示为：

其中:κ为一常数，κ的大小影响了曲线的变化率，本文选取κ=0.2。

基于改进粒子群算法的NLOS定位算法流程为：

3)将TDOA定位模型转化为粒子群算法中的适应度函数，把修正后的TDOA参数代入到适应度函数中；

4)利用改进惯性权重的粒子群算法进行迭代求解目标节点的精确位置。

3 仿真结果与分析

本文采用MATLAB对上述的理论进行验证，模拟的仿真环境如下：假设室内环境比较复杂，有多种障碍物和人员的走动，无法检测到LOS信号，只能得到NLOS信号；在50 m×50 m室内二维平面中，有3个基站和一个目标节点，基站坐标已知且所有基站和目标节点位于同一个平面中。将本文提出的LS-POS算法与两步最小二乘法(2LS)和文献[11]提出的Chan-Taylor算法进行比较，采用均方根误差作为评价定位精度的指标：

由图1可以看出随着测量噪声误差的增大，3种算法的均方根误差都相应增大，但本文提出的LS-PSO算法定位性能要优于2LS和Chan-Taylor算法。最小二乘法是一种非迭代定位算法，无法在迭代的过程中逐渐减小误差，因此两步最小二乘法的定位性能较差。

图1 测量噪声标准差和均方根误差的关系

图2所示为在非视距环境下，改变均方根时延拓展中的参数T1使其逐渐增加，代表着非视距误差也相应的增加，由图可以看出随着非视距误差的增加，3种算法的均方根误差都受到了较大影响，出现了较大的上升幅度，但相比如另外两种算法，本文提出的LS-PSO算法受到的影响最小。Chan-Taylor算法受到的影响较大，定位结果与2LS相当，这是因为Chan算法能够精确定位的前提是TDOA误差的均值要尽量小，否则定位结果将会受到很大影响[12]，在存在非视距误差的环境中TDOA误差服从的是正均值的高斯分布，且此均值较大，因此Chan定位精度明显下降，Taylor又是以Chan算法的定位结果为初始值，从而导致该算法在非视距环境下性能的降低。

图2 非视距误差和均方根误差的关系

图3为本文提出的基于LS初值估计的POS算法和经典PSO算法在收敛能力上的比较，横轴表示算法的迭代次数，纵轴表示粒子群算法中的适应度值。由图可以看出，LS-PSO算法在第23次迭代即可收敛，达到了最佳的适应度值，而经典PSO算法在41步才达到最佳适应度值，因此LS-PSO算法相对于经典PSO算法提高了收敛速度。

图3 LS-PSO和经典PSO算法收敛速度的比较

图4展示了粒子群算法中惯性权重的改进对定位结果的优化作用，当惯性权重按照高斯函数变化，定位结果明显优于按照线性递减的策略，改善了粒子群算法易陷于局部最优的缺点，从而提高了定位精度。图5为惯性权重按照两种策略变化时收敛速度的比较，当惯性权重按照高斯函数变化时，经过23步迭代即可收敛，而当惯性权重按照线性递减策略变化时，需要经过37步迭代才收敛。因此，对粒子群算法中的惯性权重参数进行调整，使其按照高斯函数变化，可以显著改善算法易陷入局部最优的缺陷、提高定位精度，并且可以加快算法的收敛速度，优化了算法的性能。

图4 两种策略定位精度的比较

图5 两种策略收敛速度的比较

4 结语

本文研究了非视距环境下超宽带室内定位算法。首先对NLOS室内环境中的TDOA定位模型重构；然后由均方根时延拓展估计出NLOS误差的均值和方差，对重构后的TDOA模型参数作调整，建立适应度函数；最后通过LS-PSO算法估计出目标节点的位置坐标，并与2LS和Chan-Taylor算法进行定位性能的比较。仿真结果显示，本文提出的LS-PSO算法可以较好的抑制非视距误差，提高非视距环境下的定位精度，且可以有效提高算法的收敛速度。此外，除了在超宽带室内定位中，本文提出的算法也可应用在非视距环境下的其他无线定位技术中，提高其定位精度，因此具有一定的实际意义。