无线时钟同步算法在UWB定位技术中的研究与应用

罗勃　沈重　朱雨豪

摘 要： 以无线时钟同步为主，提出一种以卡尔曼滤波算法为基础的无线时钟同步算法，同时也分析了无线时钟不同步的情况及原因，并且使用Hainan?EVK 1.0作为硬件平台进行了实验。实验结果表明，以卡尔曼滤波算法为基础的无线时钟同步算法能够满足TDOA定位算法的需求。

关键词： UWB； TDOA； 无线时钟同步算法； 卡尔曼滤波算法

中图分类号： TN915?34； TN919.72 文献标识码： A 文章编号： 1004?373X（2017）06?0031?04

Abstract： Studied for wireless clock synchronization， a wireless clock synchronization algorithm based on Kalman filter algorithm is proposed， and the wireless clock asynchronism and its reason are analyzed. The experiments for the algorithm was carried out with Hainan?EVK1.0. The results show that wireless clock synchronization algorithm based on Kalman filtering algorithm can meet the needs of TDOA location algorithm.

Keywords： UWB； TDOA； wireless clock synchronization algorithm； kalman filtering algorithm

0 引 言

无线定位系统是在指定的空间内通过测量无线电波的物理特性对目标进行实时监控。在室内，基于传统无线电技术的各类定位解决方案仍然是一个未解决的问题；因为室内信号传播环境相比室外更加复杂，很难精确分析信号到达时间或到达角度等参数[1]。2007年3月IEEE发布了基于UWB物理层的IEEE 802.15.4a?2007协议标准，这一标准旨在为无线个域网中使用超低数据速率、超低功耗和超低复杂度的器件进行短距离数据传输提供支持。IEEE 802.15.4a协议是IEEE 802.15.4协议的修订版，有两种物理层实现方式， 即超宽带技术UWB和 Chirp扩频（Chirp Spread Spectrum，CSS）技术。IEEE 802.15.4a超宽带（Ultra Wideband， UWB）基带如果用于定位，其在精确度、实时性能和数据带宽等方面具有绝对的优势。其中，UWB物理层可以工作在1 GHz，3～5 GHz和6～10 GHz这三种频率范围， 工作效率高， 即使在较低的发送功率下仍具有较好的鲁棒性[2]。而本文的实验则采用了爱尔兰Decawave公司生产的DW1000 UWB芯片组，其物理层协议为IEEE 802.15.4a。脉冲无线电超宽带 （Impulse Radio Ultra?Wideband，IR?UWB）的脉冲宽度仅为纳秒级或亚纳秒级，响应频率和脉冲宽度决定了UWB的定位精度在理论上可以达到厘米级。UWB技术实时响应频率可达到10～40 Hz，而其他定位技术普遍在1 Hz以下； UWB技术抗多径能力强，且时间分辨率很高，具有一定的穿透能力，这些特点有利于在室内复杂多径环境中进行实时定位和动态数据收集需求。目前国内UWB技术还主要集中在带宽应用及高速率接入等方向，UWB RTLS（Real Time Location System）定位技术鉴于其硬件起步较晚，无线时钟同步[3]、标签容量模型[4]及网络可扩展[5]通信协议难点，目前还尚未开展。而本文将针对TDOA定位算法中的无线时钟同步问题进行研究，并以Hainan EVK 1.0为实验平台，验证改进后的时钟同步算法的可行性。

1 影响无线时钟同步的因素及研究现状

由于每个基站都有自己独立的时钟源，使得每个基站测量到的标签信号到达时间（Time Of Arrival，TOA）没有一定的联系，并且每个基站的时钟源所用的不同晶振都存在不同的频率偏差，该频率偏差并不是个常数，而是随着温度的变化呈现出非线性变化，所以不同基站的晶振本身存在工艺上的差异和与环境温度之间的关系特性是影响时钟同步的主要原因；每个基站的启动时间不同也会导致标签信号的到达时间存在差异；如果主从基站的坐标摆放有偏差，或主从基站之间有障碍物阻挡就会导致计算出来的飞行时间不精确，从而影响无线时钟同步的性能。以上种种原因使得TDOA算法无法正确使用。因为TDOA定位算法要求所有参与定位的基站都基于相同的时钟基准，使得主从基站之间的时钟同步显得尤其重要。

在各类实时定位系统里，数据采集和实时控制必须具有全网统一的时钟，一旦出现时钟偏差，就会导致数据失效或控制错误。因此系统里各个节点如何保持时钟同步是关键技术问题，国内外文献提出了大量关于时间同步的算法。自校正的时间同步算法[6]中每个节点根据一个参考时钟来调整自己时钟，从而保持時间同步，节点之间无任何信息交换；文献[7]提出一种基于卡尔曼滤波的并行分布算法，每个节点利用其他节点的估计状态，投票选出一个虚拟的全局主时钟，与其保持时间同步；文献[8]通过两种具有自适应性的卡尔曼滤波模型来实现时钟同步，分别为基于最大期望值的递归算法与基于假设校验的自适应多模型算法；文献[9]利用卡尔曼滤波来跟踪时间偏移，从同步时间间隔中获取所需误差界限，再调整同步时钟从而保证系统中节点的时间同步；文献[10]结合传感器网络，对现有的时钟同步协议进行了总结，基于接收者?接收者交换的参考广播同步技术通过双向链路和信息包的交换实现网络中节点的时间同步，但该算法只在单跳网络中才能确保较高的精确度；文献[11]提出了成对报文时间同步协议，采用层次结构，可以实现整个网络节点的时间同步；文献[12]在成对报文时间同步协议基础上进行改进，使网络中传感器节点的能量消耗和平衡时间更加有效；另外，在节点失效、移动及复杂通信环境中，可以使用异步时钟协议[13]，异步时钟协议允许网络中每个节点在任何时间以任何顺序跟它的邻居节点进行时间同步；而洪泛时间同步协议[14]使用广播消息来实现发送节点和接收节点间的时钟同步，具有通信带宽小、精确度高等特点。

本文提出基于卡尔曼滤波的主从基站之间的无线时钟同步算法，同时还提出了判断时钟同步性能的检测指标。当时钟校验包和标签数据包发生碰撞时，此时的检测指标将高于预设的阈值从而通过滤波算法将这个错误排除，有效地增加算法可靠性。

2 改进的无线时钟同步算法

本文提出了一种基于改进的卡尔曼滤波的无线时钟同步算法，指定一个参考“主”基站周期性地向从基站发送时钟校验包（Clock Correct Package， CCP）。时钟校验包是用来跟踪从基站的时钟相对于主基站的时钟是如何随着时间变化。标签向所在标签发送范围内的每个基站节点快速发送数据包，并且每个基站以自己的时间戳记录数据包的到达时间（TOA）。了解基站的时钟相对于主基站的时钟是如何随着时间变化，数据包到达从基站本地时间的修正或转换成以主基站时间为基准的数据包到达时间，需要知道修正的一个重要组成部分是主基站与从基站之间的固定时间偏移和天线延时时间。固定时间偏移实际上是时钟校验包在主基站和从基站之间的飞行时间，这飞行时间可以由已知的主从基站坐标计算得到或是用双向测距方法测得到，天线延时时间包括天线的传播时间和信号的调制解调等时间，如图1所示。

图1由一个主基站、三个从基站以及标签组成。主基站定时向从基站发送时钟校验包，保证主从基站之间的时钟同步，也就是说除了主基站外，其他三个从基站都需要通过时钟同步算法使得自身的时钟与主基站时钟同步，与此同时标签向四个基站发送数据包，其中数据包中包含了标签的发包序号信息、地址信息等。标签通过到达时间差的定位方法确定了其自身在该系统中的位置。

由于主从基站晶振的频率特性、温度和老化效应的不同，导致晶振频率会产生漂移，其中晶振的温度漂移是造成其精确度偏差的主要原因，这使得主从基站的时钟频率之间存在偏差。然而，传输网络中的各种干扰使得主从基站时钟之间的偏差无法进行精确测量。改进后的无线时钟同步算法采用卡尔曼滤波算法能更精确地估算时间偏差，消除时钟以及传输过程中带来的干扰。因此将通过卡尔曼滤波算法来使得从基站的时钟偏移能够与主基站的时钟偏移保持一致。卡尔曼滤波是以最小均方误差为估计的最佳准则，来寻求一套递推估计的算法，其基本思想是：采用信号与噪声的状态空间模型，利用前一时刻的估计值和现时刻的观测值来更新对状态变量的估计，求出现时刻的估计值。

在具体的实现过程中，通过第n个同步周期的从基站CCP接收时间的最优估计值和第n+1的预测值精确地估计第n+1个同步周期主从基站的时钟偏移之间的偏差与漂移。定义T为时钟同步周期，dt为主基站现时刻CCP发送时间与上一周期时刻CCP发送时间的差值，[θn]，[γn]分别为nT时刻从基站节点的最优估算CCP接收时间值和时钟漂移值。[θn+1]，[γn+1]分别为（n+1）T时刻从基站节点修正前的预测CCP接收时间和时钟偏移值。

在（n+1）T时刻，相邻时钟同步周期内时钟偏差与时钟漂移的关系式为：

通过卡尔曼滤波算法，第n+1时钟同步周期修正后的[xn+1=θn+1γn+1T]，相应的设置[un+1=xn+1]，对时间偏差以及时钟漂移进行补偿，从而确保主从基站间的时钟同步。

卡尔曼滤波的计算基于这样的一个假设：所有的测量结果都是由真实信号和可加性高斯噪声组成的。如果上述假设成立，卡尔曼滤波可以有效地从含噪声的测量结果中得到信号信息。但是如果主基站的时钟同步校正包和标签含有TOA的数据包产生了碰撞，那么这个假设将不成立。卡尔曼滤波器会把这个碰撞当作可信的时钟偏差的数据，而以此进行计算。而卡尔曼滤波本身是一种低通滤波器，其反应和修正的速度都较慢。因此，一个由碰撞产生的错误会在较长时间内严重降低时钟同步算法的性能。

因此本研究提出了一种对碰撞产生的错误的监测以及避免办法。

卡爾曼增益公式已经由式（9）给出，定义其中一项Y信息矩阵为：

[Y=（Rn+1+Hn+1Pn+1|n（Hn+1）T）-1] （12）

式中，Y用来表示实际时钟偏差与预测时钟偏差的差值。这个信息可以用来提示当前的输入和当前的滤波器状态的吻合程度：

[OMn+1=（xn+1-xn+1）*Y*（xn+1-xn+1）] （13）

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

3 算法分析

算法的检验中，选取13 m[×]7 m[×]3 m的房间为测试环境，而且室内环境都是可视距的，四个基站分别放置四个角落。四个基站分别标注为M1，S2，S3和S4，选取M1为主基站，其余三个为从基站，其电路板图（四个基站的电路板都一样）如图2所示。经过手工准确测量得到各个基站的坐标：M1（1.1， 1.17，1.93），S2（11.3， 1.17，1.21），S3（11.3，5.37，1.95），S4（1.1，5.37，1.22）。主基站到各个从基站的飞行时间分别标注为TOF12、TOF13和TOF14，可经过三角公式计算分别得到TOF12为0.000 000 034 123 193 s，TOF13为0.000 000 036 806 046 s，TOF14为0.000 000 014 223 998 s。对于测量噪声[vn+1]和过程噪声[ωn]分别给定一个值为[3×10-20]和[5×10-20]，天线延时时间经过精确测量为0.000 000 258 114 s。在实验过程中，主基站每隔150 ms进行一次同步数据包（CCP）广播发送，从基站接收到CCP后，提取CCP包里的CCP发送时间，然后调用卡尔曼滤波算法进行时钟同步。可根据图3提供的方法，比较从基站实际时间偏移量和最佳估计时间偏移量的差值，差值越小说明时钟同步算法的性能越好，如图3所示。

根据图3，利用主从基站回傳的CCP发送时间、CCP接收时间和最佳估计时间等数据，得出从基站时间相对偏移量和最佳估计时间相对偏移量，选取从基站S2的数据用Matlab绘制成图，如图4所示。

根据图4可知，蓝色线条表示从基站相对时间的偏移量，红色线条表示最佳估计时间相对偏移量。经过卡尔曼滤波算法后的时钟同步，红色线条显得更平稳些。而蓝色线条受到一些噪声和温飘的影响显得波动较大。由图4中可知道误差在30 ns左右，但对于光速来说纳秒级别的误差影响也是很大的。所以卡尔曼滤波算法也起到了滤波的作用，使得误差变得平滑平稳。因此，实验表明卡尔曼滤波算法的无线时钟同步可以较好地跟踪主基站的时钟偏移，进而得出最佳的预测使得从基站的时钟和主基站的时钟基本一致，这很有利于提高标签的定位精确度。

4 结 论

无线时钟同步算法通过卡尔曼滤波和递归算法，理论上时钟同步误差可达到0.1 ns级别，优化了所有基站的时钟同步。本文提出的新算法在IEEE 802.15.4a UWB技术基础上，不仅能有效地消除时钟偏差的测量噪声，还能通过测量所得的时钟偏差对时钟偏差、时钟漂移以及时钟漂移变化率进行估计，从而提高系统时钟同步的精度。另一方面，针对低通滤波算法对偶发错误的敏感性，本文提出的检测算法运行状态的环节，可以剔除网络中的碰撞或者接收错误给时钟同步带来的负面影响，从而增加了系统的容量与可靠性。

参考文献

[1] HWANG S S， KWON G R， PYUN J Y， et al. AOA selection algorithm for multiple GPS signals [C]// 2013 Asilomar Conference on Signals， Systems and Computers. [S.l.]： IEEE， 2013： 481?485.

[2] SHAH SAADON E I， ABDULLAH J， ISMAIL N. Evaluating the IEEE 802.15.4a UWB physical layer for WSN applications [C]// 2013 IEEE Symposium on Wireless Technology and Applications （ISWTA）. [S.l.]： IEEE， 2013： 68?73.

[3] MCELROY C， NEIRYNCK D， MCLAUGHLIN M. Comparison of wireless clock synchronization algorithms for indoor location systems [C]// 2014 IEEE International Conference on Communications Workshops （ICC）. [S.l.]： IEEE， 2014： 157?162.

[4] CHEN Y， SHEN Y， JIANG X， et al. Throughput capacity of ALOHA MANETs [C]// 2013 IEEE/CIC International Conference on Communications in China. [S.l.]： IEEE， 2013： 71?75.

[5] SHIN W Y， LUCANI D E， MEDARD M， et al. Multi?hop routing is order?optimal in underwater extended networks [C]// IEEE International Symposium on Information Theory. [S.l.]： Institute of Electrical and Electronics Engineers， 2012： 510 ? 514.

[6] WENTAO J， LIMIN S. A prediction based long?cycle time synchronization algorithm for sensor networks [C]// Global Telecommunications Conference. Miami： [s.n.]， 2010： 1?5.

[7] LIU B， REN F， SHEN J， et al. Advanced self?correcting time synchronization in wireless sensor networks [J]. IEEE communications letters， 2010， 14（4）： 309?311.

[8] KIRSCH F， VOSSIEK M. Distributed Kalman filter for precise and robust clock synchronization in wireless networks [C]// Radio and Wireless Symposium. [S.l.]： IEEE， 2009： 482?485.

[9] LUO Yanfen. Research on adaptive information fusion Kalman filter algorithm [C]// 2012 International Conference on Microwave and Millimeter Wave Technology. [S.l.]： IEEEXplore， 2012， 5： 1?4.

[10] CHE H， CHEN Z. Energy?efficient time synchronization algorithm for wireless sensor networks [J]. Ordnance industry automation， 2010， 39： 530?534.

[11] BO G. Research on clock synchronization mechanism in wireless sensor networks[C]// International Forum on Information Technology and Applications. [S.l.]： IEEE， 2009： 57?60.

[12] LENG M， WU Y C. Distributed clock synchronization for wireless sensor networks using belief propagation [J]. IEEE transactions on signal processing， 2011， 59（11）： 5404?5414.

[13] CHOI B J， LIANG H， SHEN X， et al. DCS： distributed asynchronous clock synchronization in delay tolerant networks [J]. IEEE transactions on parallel & distributed systems， 2012， 23（3）： 491?504.

[14] SINAN Y K， KANTARCI A. Time synchronization based on slow?flooding in wireless sensor networks [J]. IEEE transactions on parallel & distributed systems， 2014， 25（1）： 244?253.