联合TDOA改进算法和卡尔曼滤波的UWB室内定位研究

张　桀，沈　重

（海南大学 信息科学技术学院，海南 海口　570228）

联合TDOA改进算法和卡尔曼滤波的UWB室内定位研究

张桀，沈重

（海南大学 信息科学技术学院，海南 海口570228）

随着“互联网+”的提出以及物联网技术的不断发展，各行业对人员、货物等进行定位的场景在不断增多；与此同时，安防监控、航空航天、无人工业化操作、海域勘探、数字化旅游等新兴领域对室内定位系统的需求也在日益增强。针对不同需求，学术界和工业界开发了多种定位技术，它们在定位适用性、定位精度等方面存在较大的差异。相比其他定位方式，超宽带（UWB）定位技术在精确度、实时性能和数据可扩展方面具有独特的优势，通过改进基于到达时间差（TDOA）的算法，降低了时钟同步的难度，联合卡尔曼滤波进一步消除了传输过程中的误差干扰，最终使得室内定位更加精确。

到达时间差；卡尔曼滤波；超宽带；室内定位

0　引　言

全球定位系统（Global Positioning System，GPS）是室外定位的通用解决方案，在无辅助的情况下定位精度一般为10 m以上。在室内，基于传统无线电技术的各类定位解决方案仍然是一个未解决的问题，因为室内信号传播环境相比室外更加复杂，很难精确分析信号到达时间或到达角度等参数［1］。射频识别及蓝牙定位具有低功耗、时延小、低成本等特点，但是较低的传输速率使其并不适合大数据传输场景；此技术的另一局限性在于它的定位精度是米级，且易受噪声信号的干扰，传输距离较短。2.4 GHz无线网络频带与蓝牙类似，定位方法同样受环境影响较大，遇到障碍物或者电磁波干扰就会造成数据的不准确。各种定位技术的特性比较，如图1所示。

超宽带（Ultra Wideband，UWB）是射频通信领域国内外长期研究的热点。脉冲超宽带（IR-UWB）技术在1989年被美国国防部确定为UWB技术标准［2］。2007年3月IEEE发布了基于UWB物理层的IEEE 802.15.4a-2007标准，这一标准旨在为无线个域网中使用超低数据速率、超低功耗和超低复杂度的器件进行短距离数据传输提供支持。

图1　各种定位技术的特性比较

相对于其他定位方式，IEEE 802.15.4a UWB在精确度、实时性能和数据带宽等方面具有很好的优势［3］。UWB实时响应频率可达到10～40 Hz，而其他定位技术普遍在1 Hz以下；脉冲无线电超宽带（Impulse Radio Ultra-Wideband，IR-UWB）的脉冲宽度仅为纳秒级或亚纳秒级，响应频率和脉冲宽度决定了UWB的定位精度在理论上可以达到厘米级。UWB技术抗多径能力强，时间分辨率高，具有一定的穿透能力，这些特点有利于在室内复杂多径环境中进行实时定位和动态数据收集。鉴于UWB技术的独特优势，本文研究的室内定位选择IEEE 802.15.4a UWB作为技术标准。

1　UWB室内定位研究的技术路线

围绕UWB实时定位的厘米级精准定位的核心问题，以无线时钟同步为研究基础，在此目标下分别提出到达时间差（Time Difference of Arrival，TDOA）改进算法以降低无线时钟同步的难度，以及为解决传输过程中不可避免的误差干扰的卡尔曼滤波算法，结合两种算法，构造出UWB室内定位的理论基础，并通过Matlab仿真验证其可行性，在现有的Hainan Evk1.0或者后续的硬件评估板上实现，最终研发出UWB多标签室内实时精准定位系统。

2　标准TDOA算法简介

标准TDOA算法是基站在完全同步的前提下，发出UWB脉冲信号，标签通过各个基站发出的UWB信号的到达时间差，再结合基站的位置坐标对标签进行定位的方法。

如图2所示，各个基站的信号在到达标签的过程中，要经过室内各种复杂的信道，而这种信道是多径的且具有非视距误差，因此信号从基站到达标签的时间经常要比一个基站的信号脉冲时间要大很多，如果不加入保护时隙，那么前一个基站的信号会与后一个发生碰撞重叠，导致标签无法对基站进行区分［4］。

图2　标准TDOA下的基站接入

TDOA算法通过比较信号到达时间差，就能作出一组双曲线，如图3所示，双曲线的交点是标签的位置，而双曲线的焦点是基站的位置［5］。

图3　TDOA的双曲线定位

根据到达时间差获得的TDOA方程为：

式中：（xn，yn）是基站的坐标n（n≥2）；（x，y）是标签的坐标；tn是第n个基站到达标签的时间；c是电磁波的速度为3×108m/s。TDOA标准算法可以通过方程组（1）推导出标签的坐标。TDOA标准算法需要基站间保持时钟同步，基站发信号，标签接收。由于基站的绝对完全同步，可以通过数学方法得到最优解，如最小二乘法、线性约束等［6］。标签将根据到达时差、保护时隙和基站的坐标计算自己的位置。

然而，对于TDOA标准算法基站完全同步的高要求，因为晶振频率的不精确，环境温度的影响等，导致基站在初始时间是不可能完全同步的。此外，即使实现初始状态的时钟同步，由于晶振的频率是不同的，随着时间的推移，将会产生时钟漂移，变得又不同步了［7］。标准TDOA传统的实现同步方式是采用网线或其他导线避免不同步，有局限性，容易受限于地理因素，无法大规模部署，也做不到无线时钟同步，方便性很差，无法商业应用，针对这一问题，采用TDOA改进算法实现无线时钟同步。

3　TDOA改进算法

TDOA改进算法不同于标准TDOA算法之处在于，可以采用比标准算法更容易、更方便的方式对基站做初始时钟同步。这就意味着，新算法进一步降低了时钟同步的难度且容易实现无线。

如图4所示，SA1T1，SA2T1，SA3T1，SA4T1是四个基站和标签1的距离，SA1A2，SA1A3，SA1A4是基站1和其他基站的距离。基站1发送一个信号到整个网络，其他基站在收到基站1的信号后立即发射信号给标签1。标签1在接收到基站1的信号后，记录下该信号的到达时间，然后一直等待，直到来自基站2，基站3，基站4的信号到达，记录从所有基站到达标签1的到达时间t1，计算基站2，基站3，基站4，…，基站 n的到达时间差 （t2-t1），（t3-t1），…，（tn-t1）。结合它们的坐标计算自己的坐标。由于标签1通过本地时钟记录下了基站1的到达时间，对于新算法来说，它等价于同一信号从随机选取的基站1出发后经过不同的路径到达标签1，它们的开始时间本质上是一致的，这样就实现了基站的时钟初始化同步。TDOA改进算法在算法层实现了同步，故不需要部署网线或导线实现时钟同步，可以无线方式部署，故而采用此改进TDOA算法做室内定位。

图4　改进的TDOA算法的定位网络模型

TDOA改进算法列出方程组如下：

式中：tn是基站 n抵达标签1的时间；AnT1=；，）是标签1的矩估计量；（xn，yn）是基站n的坐标；AnT1是基站与标签的距离的矩估计。由于基站1和基站n之间的距离可以通过场地测量，因此不需要用矩估计量。在TDOA定位过程中，标签接收到信号，但是它不发送信号，不会产生碰撞干扰，标签1和标签2是相对独立的，故而可以实现多标签的扩展。

在本小节，已经在初始时刻实现了基站的时钟同步，面对室内复杂的环境，信号在传输过程中，不可避免地遇到非视距的障碍物阻挡产生误差，对于这一问题，采用卡尔曼滤波错误检测算法来消除传输误差。

4　卡尔曼滤波消除信号传递过程的干扰

无线时钟同步运用卡尔曼滤波消除信号传递过程中的干扰。把基站分为主基站和从基站，通过一个同步周期的时钟信息去估计下一个同步周期的主从基站时钟间的漂移。

假设一个离散控制过程系统的状态方程为：

式中：xk+1是k+1时刻的系统状态；ωk+1是过程噪声的高斯随机变量；uk+1是k+1时刻对系统的控制量；A和B是系统参数，对于多模系统，它们是矩阵。

对应的观测矩阵为：

式中：Zk+1是k+1时刻的测量值；Hk+1是单位矩阵；vk+1是测量噪声的高斯随机变量。

利用系统的过程模型预测下一个状态。卡尔曼滤波原理的迭代过程如下［8］：

基于系统的前一个状态估计现在的状态：

最小均方误差矩阵为：

式中：Pk|k是估计值 xk|k的最小均方误差矩阵；Pk+1|k是k+1|k的协方差；Q是系统过程的协方差。

卡尔曼增益为：

式中：Rk+1是观测噪声vk+1的协方差矩阵。

K+1状态的最优化估算为：

保持系统的持续性直至结束，更新k+1状态下的xk+1|k+1的协方差：

在式（11）中，如果OM（Outlier Metric，偏离指数）大于一个预设的阈值，就认为当前输入不可信，不更新当前状态，直接丢弃此次数据，从而避免让错误数据包对滤波器造成很大的影响［10］。

通过上述完备的过程，就可以消除时钟偏差以及传输过程中带来的干扰。

定义卡尔曼增益矩阵的一项Y信息矩阵为：

5　Matlab仿真与反馈

5.1标准TDOA与改进TDOA算法的RMSE比较

本文用Matlab对TDOA的标准算法和TDOA改进算法进行比较和仿真，选取RMSE（均方根误差）作为定位精度的测量指标，然后探索两种方法在不同均方差下的RMSE值差异。

MSE（均方误差）的计算公式为：

标准和改进TDOA算法的RMSE比较，如图5所示。

图5　标准和改进TDOA算法的RMSE比较

从图5中可以推断，当所有的基站完全同步（均方差为0.8×10-2m以下），其定位结果准确，标准TDOA和改进TDOA的定位方法的性能非常接近。当均方差较大时，两种定位方法的均方根误差均高于1 m。事实上，由于TDOA改进算法需要发送信号到其他基站最后回到标签，在中转的基站上，由于硬件要实现转发过程，使得它比标准算法性能稍差。但是，改进TDOA算法实现初始时刻时钟同步更容易，也可以实现无线，且标准和改进TDOA算法的RMSE值变化趋势基本是相同的。从这个意义上讲，与标准TDOA算法相比，TDOA的改进算法具有一定的优势。

5.2联合算法的多标签性能仿真

TDOA算法的最大优点是，它不限制标签的数量，标签是相互独立的。在此，通过Matlab仿真，分析多标签下的改进TDOA算法的性能，横坐标代表加入标签的数量，纵坐标代表定位精度。在标准TDOA算法和改进TDOA算法中加入卡尔曼滤波算法，逐渐增加标签数量，测试其定位精度并作比较。

如图6所示，作为一种理想状态，标准TDOA定位联合卡尔曼滤波算法精度可以达到20 cm。这是因为标准TDOA算法使所有的基站做到绝对同步。与标准TDOA联合卡尔曼滤波算法相比，改进的TDOA联合卡尔曼滤波算法的定位精度有一定的波动，但是波动幅度小于5 cm，是可以接受的。考虑到测试的随机性，进行独立重复试验。此前的RMSE比较表明单纯的TDOA算法改进并不能达到厘米级的定位精度，加入卡尔曼滤波算法后，如图7所示，Matlab仿真结果表明测距精度基本稳定在15～25 cm，这个结果证明TDOA改进算法联合卡尔曼滤波算法是有效的。

图6　联合算法的单次试验定位精度

图7　联合算法的多次独立重复试验

5.3联合算法的三维定位仿真结果

采用四个基站定位一个标签，联合算法的三维仿真结果显示，标签的实际位置与估计位置误差为15.9 cm，再次验证了5.2节对于联合算法定位精度的仿真结果的正确性。三维定位仿真结果如图8所示。

图8　联合算法的三维定位仿真结果

6　UWB室内定位评估板套件

本硬件系统Hainan Evk1.0是由团队自主研发，目前这套初期的系统已经做到了单标签10 cm的定位精度。图9（a）是超宽带系统的天线模块，使用市面上成熟的全向天线设计；图9（b）是定位模块和STM32最小系统模块，STM32通过SPI总线控制定位芯片；图9（c）是PC端的上位机，上位机和客户端采用socket TCP进行可靠通信；图9（d）是多节点网络图，中间的标签通过周围的四个基站定位；图9（e）由移动电源给板子供电；图9（f）是iPad客户端实时显示室内的人或者物体的运动轨迹。

图9　UWB实时精准定位系统

7　结　语

本文改进了TDOA算法，使得实现无线时钟同步比原算法更容易，联合卡尔曼滤波进一步消除了传输过程中的误差干扰，Matlab仿真结果表明，定位精度可以达到20 cm左右，验证了联合TDOA改进算法和卡尔曼滤波算法的可行性。后期将基于本文的研究成果深入进行第二代UWB定位系统的研发，开展多标签定位。

［1］曹轶超，方建安，罗贤云.一个基于TDOA的无线定位新算法［J］.电波科学学报，2008（5）：841-846.

［2］SHAH SAADON E I，ABDULLAH J，ISMAIL N.Evaluating the IEEE 802.15.4a UWB physical layer for WSN applications［C］// Proceedings of 2013 IEEE Symposium on Wireless Technology and Applications Proceedings.Kuching：IEEE，2013：68-73.

［3］HIGHTOWER J，BORRIELLO G.A survey and taxonomy of location systems for ubiquitous computing［J］.IEEE computer，2010，34（8）：57-66.

［4］LEE W，PATANAVIJIT V.Performance evaluation of TOA estimation for ultra-wideband system under AWGN and IEEE 802.13a channel model［C］//Proceedings of 2011 Seventh International Conference on Signal-Image Technology and Internet-Based Systems.Dijon：IEEE，2011：237-244.

［5］陈鸿龙，李鸿斌，王智.基于TDoA测距的传感器网络安全定位研究［J］.通信学报，2008，29（8）：11-21.

［6］MCELROY C，NEIRYNCK D，MCLAUGHLIN M.Comparison of wireless clock synchronization algorithms for indoor location systems［C］//Proceedings of 2014 IEEE International Conference on Communications Workshops.Sydney：IEEE，2014：157-162.

［7］YILDIRIM K S，KANTARCI A.Time synchronization based on slow-flooding in wireless sensor networks［J］.IEEE transactions on parallel and distributed systems，2014，25（1）：244-253.

［8］庄晓燕，王厚军.基于卡尔曼滤波的网络精确时钟同步研究［J］.测控技术，2013（9）：107-110.

［9］闫潇，张洪顺，宋琦军，等.扩展卡尔曼滤波算法在UWB定位中的应用［J］.通信对抗，2009（1）：26-28.

［10］刘静，姜恒，石晓原.卡尔曼滤波在目标跟踪中的研究与应用［J］.信息技术，2011（10）：174-177.

［11］ZHANG J，DONG F，FENG G，et al.Analysis of the NLOS channel environment of TDOA multiple algorithms［C］//Proceedings of 2015 IEEE Sensors.Busan：IEEE，2015：1-4.

［12］郝卫峰，陈正阳，田晓振.GPS导航中非线性Kalman滤波的方法分析［J］.测绘信息与工程，2007，32（3）：38-41.

Research on UWB indoor positioning in combination with TDOA improved algorithm and Kalman filtering

ZHANG Jie，SHEN Chong
（College of Information Science&Technology，Hainan University，Haikou 570228，China）

With the presentation of″Internet+″and continuous development of Internet of Things technology，the scenes to locate the staff and goods are increasing.At the same time，the demands of emerging fields（such as security monitoring，aerospace，unmanned industrialization operation，seas exploration，digital tourism）for indoor positioning are growing.To satisfy different requirements，various positioning technologies were developed by the academia and industry，but they have great differences in the aspects of positioning applicability，positioning accuracy，etc.In comparison with other positioning methods，the UWB（ultra wideband）positioning technology has the unique advantages in positioning accuracy，real-time performance and data scalability.In this paper，the algorithm based on TDOA（time difference of arrival）was improved to reduce the difficulty of clock synchronization，and in combination with Kalman filtering，the error interference in transmission process was eliminated. The method can make the indoor positioning more accurately.

TDOA；Kalman filtering；UWB；indoor positioning

TN911-34

A

1004-373X（2016）13-0001-05

10.16652/j.issn.1004-373x.2016.13.001

2015-10-10

国家自然科学基金资助项目（61461017）

张桀（1991—），男，山西怀仁人，硕士。主要研究方向为无线通信、超宽带。

沈重（1981—），男，博士，教授。主要研究方向为无线通信、传感器网络、物联网、超宽带等。