基于TL-LFL的UWB室内定位算法

刘 文，赵 旭，李连鹏，刘福朝，褚昕悦，代 牮

(北京信息科技大学，高动态导航技术北京市重点实验室，北京 100192)

0 引言

随着人工智能技术的快速发展，物联网系统信息化程度不断提高，其对室内高精度定位的需求也在持续上升。目前室内定位技术有WiFi、射频技术、ZigBee、超宽带(ultra wide band，UWB)等[1]，UWB技术中信号频谱由多个子频带组成，目的是提高无线通信的数据速率和穿墙的传播能力[2],超宽带具有高时间分辨率(ns级)，有助于精确的距离测量，超宽带以其优良的性能在通信领域具有较广阔的应用。

传统的三边定位算法原理简单，计算量较小，具有运算速度快的优点[3]，被广泛研究。游小荣等通过设定优化目标函数求解的方法找到定位目标[4]；高莉等提出一种改进的三边定位算法，通过求解利用加权最小二乘算法和损失定位信息构建的模型实现定位[5]；周杰等采用Eddyst-one技术优化后的质心算法解决三边测量算法的不足，并选择10个定位节点进行验证[6]。位置指纹是另一种广泛应用的UWB定位技术，通常包括2个阶段：离线阶段包括位置或与位置有关的相关信号参数(如信号飞行时间、接收信号强度)建立一个具有位置特征的指纹数据库；在线阶段目标节点与存储在指纹数据库中的指纹点进行比较得到目标节点估计位置[7]。李世银等提出了一种MeanShift与加权K近邻相结合的指纹定位方法，平均定位误差在0.5 m左右[8]；孙建强等在指纹算法中引入了模糊推理和加权KNN处理的方法，定位误差在10 cm左右[9]；指纹定位算法中数据匹配算法一般都是使用欧氏距离进行相似度计算，找出K值，虽然欧氏距离能直观反映信号的差异性，但信号的波动也会导致欧氏距离的改变，而且容易出现2个点欧氏距离较近而物理距离较远的情况。

本文结合三边定位和指纹定位的优点加以改进，提出了一种基于TL-LFL (trilateral location and location fingerprint location)的室内定位算法。主要分为2个阶段：离线阶段通过克里金插值法构建离线数据库；在线定位分为两步：粗定位和精定位，粗定位采用三边定位来约束目标区域，得到初次定位坐标和定位区域S；精定位结合指纹定位算法，采用K-Means算法对区域S内指纹点聚类，找出与在线实测距离信息最近的聚类中心，最后结合粗定位坐标根据其离散度进行加权计算得到最终定位坐标。既可以降低最终定位结果的误差，又可以降低指纹定位的复杂计算量。

1 指纹定位算法

指纹定位算法主要分为2个阶段：离线阶段构建指纹数据库；在线阶段进行数据匹配、实时定位。基本流程如图1所示。

图1 指纹定位原理示意图

离线阶段：使用采集设备获取定位区域中基站与标签之间的距离信息，将其作为该参考节点的指纹量存储到指纹数据库中[10]。在线匹配阶段：将标签实时获取的各个基站的距离信息与指纹数据库内指纹点距离信息进行匹配，找到相似度最高的一个或多个指纹量，根据一定的匹配算法得出标签的估计坐标。常用的匹配算法主要有K最近邻算法、加权K最近邻算法、神经网络和支持向量机等。

2 TL-LFL定位算法

TL-LFL算法主要包括建立离线数据库；进行在线数据匹配，采用粗精定位结合。

2.1 建立指纹数据库

建立指纹数据库由采样和插值2个阶段构成。其中采样阶段主要完成采样点的选取、指纹信息采集以及指纹信息处理3个功能[11]。根据UWB信号分辨率高、测距值精确且波动性小的优点，提出选取UWB测距信息作为指纹量。

插值阶段实现对未采样区域的指纹量估计，包括插值点选取、变异函数拟合和克里金插值估计3个部分[11]。最后，将采样的测距信息和插值估计的测距信息存储到指纹数据库中以实现在现阶段数据匹配。

2.1.1 定位信息采样

采用双边双向测距方法得到基站和标签之间的距离，需要标签和基站单独进行通信，其中A代表标签，B代表基站，测距流程图如图2所示。

图2 双边双向测距流程图

(1)标签发送Poll包，记录发送时间T1，打开接收。

(2)基站要提前打开接收，在接收到Poll包后，记录到达时间T2。

(3)基站在T3(T3=T1+T2)时刻发送Reply包，完成后等待数据接收。

(4) 标签收到Reply包，记录时间T4。

(5)标签在T5(T5=T3+T4)时刻发送Finally包。

(6)基站接收到Finally包，记录时间T6，然后计算出4个时间差，可推出信号飞行时间，如式(1)所示：

(1)

式中：T1为标签发出Poll包到接收基站的Reply包的时间；T2为基站发送Reply包到接收标签的Finally包的时间；T3为基站接收标签的Poll包到发送Reply包的时间；T4为标签接收基站的Reply包到发送Finally包的时间。

距离计算公式为

d=Tp×c

(2)

式中c为光速。

为了保证数据的有效性来验证算法的定位精度，本文先采用限幅滤波再采用滑动滤波来对数据进行预处理，确定每个采样点对应一组距离信息，并保存数据。

在实验场地内布置一定数目的UWB基站，将实验范围均匀划分为若干网格，每个网格的中心作为距离信息采样点，将该采样点的物理位置及经预处理后的各个基站的测距信息共同构成一个位置指纹。

(3)

2.1.2 插值数据估算

使用指纹定位方法时，如果手动确定地面真实坐标，在大规模环境中需要大量时间。这一问题在基于UWB的定位中更严重，在这种情况下，密集的指纹数据库是实现高精度定位的关键。为了减少数据采样的工作量，本文采用克里金插值法从稀疏收集的测距信息中构建完整的指纹数据库[12]。

克里金插值算法是有限区域内对区域变量的一种无偏最优估计，在空间插值的地理统计原理中得到了广泛的应用，但在无线网络领域中应用并不广泛。与传统的插值方法相比，克里金插值法在数据网格化的过程中，考虑到了描述对象的空间相关性结果更能真实地表示实际情况[13]，克里金插值的计算公式为

(4)

首先构建稀疏的采集指纹数据库，建立克里金插值算法模型，完成变异函数拟合。然后利用构建的算法模型和采集指纹数据库对预测点的3个距离值进行估算，最后将估算值与预测点实际物理坐标进行组合存储到指纹数据库，因此构建指纹数据库的离线工作量可以显著减少。

2.2 在线定位阶段

2.2.1 粗定位阶段

粗定位阶段采用三边定位算法，估计和确定邻近的参考点，减少了指纹定位阶段在距离误差下需要计算的参考点。这一步将筛选和过滤距离目标节点较远的参考点。

三边定位算法是一种坐标变换的定位算法，原理和实现比较简单，以每个基站为圆心，标签到基站的距离为半径，3个圆相交的点即为标签坐标。4个坐标关系为

(5)

在实际定位中，由于非视距、噪声、多径等因素的影响，实际测量一般存在误差，如图3所示，动态相交区域记为S，三边定位结果记为T。

di=ri+ei

(6)

式中：di为标签到基站的测量距离；ri为实际距离；ei为测距误差。

图3 三边定位算法原理图

2.2.2 精定位阶段

在粗定位结果的基础上结合指纹定位算法，在S1区域存在分布较远的指纹点时，直接在S1区域内取均值或者通过加权方法估计坐标会容易受到干扰，得到的估计坐标与实际的物理位置会有较大偏差，对属于S1区域内的指纹点采用K-Means聚类方法进行区域划分，由于S1区域内指纹点较少，根据S1区域特征，设置聚类总数为3，相对于对所有指纹点进行聚类加权计算减少了计算量，也使区域划分更加精确。K-Means聚类效果如图4所示。

最后结合粗定位坐标T进行加权计算得到最终估计坐标，精定位阶段流程如图5所示。

图4 S区域内K-Means聚类后效果

图5 精定位阶段流程图

图5中本文采用基于参考位置指纹离散程度的WKNN定位算法discrete degree WKNN，DD-WKNN)计算权重系数，依据指纹点离散程度对位置估算的参考权重进行权值设定，离散程度用变异系数表示，如式(8)所示。权重系数的大小与离散程度成反比。利用位置指纹的变异系数来表示在K个指纹数据中的离散程度，位置指纹的离散程度越小具有的参考价值越高[14]。

(7)

(8)

根据得到的权重系数，对K个指纹点加权求和估算位置坐标。

TL-LFL算法整体流程如图6所示，图6(a)粗定位阶段；图6(b)精定位阶段中使用K-Means聚类进行区域划分；图6(c)选取与在线实测距离信息最相似的聚类中心；图6(d)结合坐标T加权得到估计坐标。

图6 TL-LFL算法步骤

3 实验仿真与结果分析

3.1 实验环境

为了验证本文算法的s有效性，设计了如图7所示的模拟测试方案，数据采集定位区域选择8 m×6 m的实验室会议室，可以看到室内有较多的桌椅，符合一般室内环境的静态干扰条件[15]。其内部结构和采样点分布如下：会议室内每隔1.2 m设置一个采样点，共计34个采样点，各采样点与基站之间通过UWB进行通信。对采样点和基站之间的距离信息进行采样。本次实验采用2个标签共采集19次以获取实验场地UWB距离数据，为保证每个采样点数据的稳定性，采集数据时基站和标签摆放好静置5 s，并采用限幅-滑动滤波处理每个采样点的数据，然后读取出现频次最高的100组数据求均值作为采样点最终的距离值，将各个采样点的数据录入采样指纹数据库。

(a)实物图

(b)平面图图7 室内采样点分布平面图

3.2 实验分析

采用python为仿真工具,根据克里金插值算法进行插值估计，为了验证插值算法的可行性，在采样指纹数据库中取12个采样点作为已知点指纹集，对剩余的23个采样点用克里金插值算法估计距离信息，计算3个基站的均值误差，如图8所示。可以看出克里金插值方法建立指纹数据库大约有91%的指纹点距离误差小于1 m。

图8 克里金插值距离估计误差图

本文根据采样的34个指纹点采用插值算法将间距缩短为0.3 m，得到覆盖整个会议室的指纹信息，节省了大部分工作量，所有指纹点测距误差均值如图9所示，可以看出大约99%的指纹点误差均值在0.8 m内，因此采用克里金插值估计性能较好，具有一定的有效性。

图9 指纹点测距误差均值

为了验证提出的TL-LFL算法的可行性和有效性，利用同一组数据分别用三边定位、KNN、DD-WKNN和TL-LFL算法估算标签的位置坐标，对比最终的定位结果。

常用的定位性能评价指标有几何精度因子、均方误差和方均根误差、克拉美罗下界、累积概率分布函数等[16]。本文采用均方误差和累积概率分布函数验证算法的精准性，对测试样本100组数据进行多次实验取均值，结果如图10、图11所示。

图10 4种算法定位均方误差示意图

从图10可以看出，TL-LFL算法定位均方误差比三边定位、KNN和DD-WKNN算法小，定位精度最高；从图11来看，本文算法误差在0.35 m内概率达到87%，优于其他2种算法。表明在一定程度上改善了信号不稳定带来的定位误差问题。

图11 3种算法定位误差累积概率分布图

4种定位方法误差对比如表1所示，TL-LFL算法的定位误差在0.7 m内，平均定位误差为0.2 m，定位效果优于其他3种算法。本文算法具有良好的稳定性，相比DD-WKNN算法精度提升了约30%，对比三边定位算法精度改善了约47%。

表1 4种定位方法误差对比 m

根据以上实验结果可以得出，本文提出的TL-LFL算法的最小定位误差、最大误差、平均误差都小于其他3种算法，定位效果和定位稳定性均有提升，更适用于复杂环境中使用。

4 结论

本文提出了一种基于TL-LFL的室内定位方法，该算法在采样点UWB距离信息的基础上采用克里金插值法构建离线指纹数据库，在指纹定位算法的基础上引入了三边定位算法，通过三边定位算法获得初始定位坐标和定位区域；精定位结合指纹定位算法，采用K-Means算法对区域S内指纹点聚类，找出与在线实测距离信息最近的聚类中心，最后结合粗定位坐标根据其离散度进行加权计算得到最终定位坐标。实验表明，该算法定位误差小于0.7 m，相比DD-WKNN算法精度提升了约30%，对比三边定位算法精度改善了约47%。该算法减少工作量的同时又具有较好的稳定性和精准度。