基于卡尔曼滤波的Ad Hoc网络节点间时间同步算法研究

孙力，邹德财，韩涛

基于卡尔曼滤波的Ad Hoc网络节点间时间同步算法研究

孙力1,2,3，邹德财1,2,4，韩涛5

（1. 中国科学院 国家授时中心，西安 710600；2. 中国科学院 精密导航定位与定时技术重点实验室，西安 710600；3. 中国科学院大学，北京 100049；4. 中国科学院大学 天文与空间科学学院，北京 101048；5.西安理工大学 理学院，西安 713300）

本文建立了Ad Hoc网络节点的时钟模型，设计了适用于网络节点时钟模型的Kalman滤波算法，利用时差噪声的分形特征估计Kalman滤波的协方差矩阵，并对时钟噪声序列特征进行分析。仿真结果表明，该算法不仅提高了滤波算法效率，同时能明显降低网络节点间的时钟偏差，实现了Ad Hoc网络节点间的高精度时间同步，同步精度优于25ns。

Ad Hoc；网络节点；分形特性；Kalman滤波

0 引言

近年来，无线通信技术取得了快速发展，传统的无线移动通信网络已不能满足某些特殊场合，如军事、救灾抢险等对自主定位的需求。在这一背景下，Ad Hoc网络[1]应运而生，在网络部署方面比较灵活，可以在一些没有通信基础设施的地区自由组网。Ad Hoc网络所有节点都可以随意进入或退出，各节点之间的地位和功能是平等的[2]。但由于缺少标准时钟为网络中的节点提供时间参考，各个网络节点时钟不同步，其时间差异很有可能导致整个网络架构不能正常运行，自主定位功能无法实现。因此，网络节点间的时间同步是整个网络系统有效运行的重要保证。

Ad Hoc网络架构如图1所示。Ad Hoc网络不依赖基础网络设施的建立，避免了基础设施网络的故障影响到整个网络系统通信的问题，它是一个没有中心的网络节点，所有的网络节点都是平等的，没有优先级之分。在网络系统结构中，采用分布式的组网特征，网络节点之间自由组网，具有自主对等的特性，具有良好的抗毁性和健壮性。

图1 Ad Hoc网络架构图

1 Ad Hoc网络时间同步算法

当前，许多学者在无线自组织网络时间同步方面开展了研究并提出了各种算法。在这些不同的网络节点时间同步算法中，S. Ganeriwal等人[3]提出的传感器网络定时同步算法（TPSN）、J. Elson等专家[4-5]提出的参考广播同步算法（RBS）、B. Kesy等人[6]提出的防洪时间同步算法（FTSP）和Pings等人提出的延时测量时间同步算法（DMTS）[7]是比较典型的几个方法。传统网络节点时间同步算法的特点如表1所示。

表1 网络时间同步算法

在Ad Hoc网络中节点具有多跳的特征。据此FTSP算法采用层级的网络结构，这种网络结构在大规模的网络节点下是比较适用的，多个接收者与根节点发送的广播信息进行同步。对于网络结构的动态变化以及一些网络节点的异常情况，FTSP算法的容错性都是比较好的。在时间同步的过程中利用线性回归的方式不断精确地计算偏移量，补偿了网络节点的时间偏差，从而获得更高的同步精度。对比之下，FTSP算法更适合Ad Hoc网络节点间的时间同步。

2 Ad Hoc网络时钟模型

式（5）中

那么，离散的时钟模型可以表示为

3 Ad Hoc网络时钟模型的Kalman滤波方法

Kalman滤波广泛应用于导航、传感器数据融合、雷达系统以及导弹追踪等。近来更被应用于人脸识别、图像分割等计算机图像的处理。它也是一种经常用来描述网络节点时钟差的方法，可以用来描述节点时钟的噪声状态。预测与更新是在使用卡尔曼滤波进行的两个过程[15]。首先想要对当前时刻的状态做出估计，就需要使用上一时刻的状态对它进行预测估计，这个就是预测过程。然后想要优化预测操作中预测的这个估计值，那就需要当前时刻的观测状态量来对其进行优化，这个就是更新过程。整个卡尔曼滤波过程即：先预测，做出先验估计。之后计算卡尔曼增益，再得到估计值，这个后验估计值就与真值更为接近[16]。

假设在Ad Hoc网络中，两个节点的频率是相同的。这个假设与整个网络架构的实际情况是不相符的，但是通过时钟模型的Kalman滤波方法可以改进频率不同的情况。则基于上述的假设条件，网络节点间时差的Kalman滤波的数学表达式为

状态转移矩阵和噪声的协方差矩阵分别表示为：

则：

由上述可以知道，对协方差矩阵的估计、节点时钟谱密度的估计以及时钟漂移率谱密度的估计是使用Kalman滤波算法处理节点时钟偏差的关键，可以参考系统时钟噪声序列特征对这些数值进行估计。

3.1 时钟噪声序列特征分析

对时钟噪声序列进行特征分析，可以使得节点时钟模型能够通过数学方法更准确的描述，是建立更精确的时钟模型、提高网络间时间同步精度和效率的前提。

3.1.1 时差序列获取

为了更加准确地利用数学方法描述节点时钟模型，必须对其数据特征进行描述。为此，本文基于中国科学院国家授时中心的1 PPS时间基准对3个网络节点晶振的时间求取时差序列，分析其噪声特性。由式（8）可知，对这3个观测量进行线性拟合，其拟合残差描述了它们各自的噪声情况。残差序列的数字特征如表2所示。

表2 节点时钟偏差残差序列数字特征 单位：s

3.1.2 噪声序列的非正态性

对噪声序列的分析是建立更精确的时钟模型的前提，是提高网络间时间同步精度和效率的必要前提。从它们的频数直方图（图2）中很难看出它们是否服从正态分布。

图2 3个网络节点晶振时差序列频数统计直方图

本节将通过雅各-贝拉检验（Jarque-Bera）来验证本文所采用的网络节点时钟数据是否具有符合正态分布的偏度和峰度的拟合优度的检验。

构造JB统计量[13]：

本文的3个网络时间节点时差噪声序列的JB统计结果如表3所示。其中是判断该检验是否接受原假设的值，当=0时，认为数据服从正态分布，接收原假设；当=1时，则拒绝原假设，认为数据不服从正态分布。，JBSTAT和CV分别指检验的概率值、检验统计量的值和判断是否拒绝原假设的关键值。由于各个残差序列的JB统计结果均在显著性水平0.05时拒绝正态分布假设，因此，网络节点时钟的噪声是非正态的，需要进一步讨论和分析。

表3 节点时钟偏差残差JB统计量检验结果（显著性水平α = 0.05）

3.2 时差噪声的分形特征

① 计算均值：

图3 网络节点时钟偏差的分析结果

其中，3个网络节点时钟晶振噪声的Hurst指数线性拟合表达式为

式（27）的计算结果表明，3个网络节点时钟晶振噪声序列的Hurst指数均大于0.5，具有分形特性，是分形序列。

由式（10）可知，这3个噪声序列的傅里叶频谱指数分别为：2.984 0、2.997 2和2.984 6。将这些计算结果代入式（15），即可对Kalman滤波的协方差矩阵进行估计。

通过上述分析，得到了网络节点时钟模型、Kalman滤波算法以及分形特征参数。其中，分形特性可以用来估计Kalman滤波的协方差矩阵，从而提高滤波算法效率。

4 仿真分析

本文通过软件Matlab来进行移动自组织网络的时间同步算法的仿真验证，网络节点时钟的本振频率为10 MHz，仿真时间为180 s，同步周期设置为1 s[19]。通过仿真可以得到卡尔曼滤波前的时钟偏差情况，其结果如图4所示。

图4 卡尔曼滤波前的时钟偏差

从图4可以看到卡尔曼滤波前的时钟偏差是随机抖动的，通过分析可知，时钟偏差的均值和方差分别为5.051 4×10-6s和1.229 6×10-13s。卡尔曼滤波后的时钟偏差情况，其结果如图5所示。

图5 卡尔曼滤波后的时钟偏差

从图5可以看到卡尔曼滤波后的时钟偏差也是随机的，对仿真数据进行分析可知，时钟偏差的均值和方差分别为2.375 7×10-8s和1.363 8×10-13s。

通过仿真分析与计算，可以看出使用卡尔曼滤波使得节点的时钟偏差得到了明显的改善，对时钟系统状态模型进行调整，使得节点间实现时间同步。

5 结语

本文对建立的Ad Hoc网络的节点时钟模型进行了数学描述，利用分形方法对网络节点时钟噪声进行分析和研究。为了对节点时钟的噪声状态进行描述，采用Kalman滤波方法对时钟噪声序列特征进行分析，其中包括了时差序列获取和噪声序列的非正态性分析。基于分形特征分析结果，估计Kalman滤波的协方差矩阵，从而提高了滤波算法效率。通过Matlab对文中的基于Kalman滤波算法对Ad Hoc网络节点间同步精度进行仿真，结果表明该算法能明显降低网络节点间的时钟偏差，基于该模型实现了Ad Hoc网络节点间的高精度时间同步，同步精度优于25 ns。

[1] ZHENG S R, WANG H T, ZHAO Z F, et al. Ad Hoc networks technology[M]. Beijing: Posts & Telecom Press, 2005.

[2] 杨海东, 邓勇.Ad Hoc网络时间同步技术研究[J]. 计算机工程与设计, 2008, 29(21): 5447-5450.

[3] GANERIWAL S, KUMAR R, SRIVASTAVA M B. Timing-syncprotocol for sensor networks[C] // SenSys’03: Proceedings of the1st International Conference on Embedded Networked Sensor Systems, New York: ACM, 2003: 138-149.

[4] 李文锋, 王汝传, 孙力娟. 基于RBS的无线传感器网络时间同步算法[J]. 通信学报, 2008, 29(6): 82-86.

[5] 叶玲, 李太华, 代学武. 无线传感器网络环境下基于卡尔曼滤波的PTP协议[J]. 智能系统学报, 2012, 7(6): 518-524.

[6] ELSON J, GIROD L, ESTRIN D. Fine-grained network time synchronization using reference broadcasts[J]. ACM SIGOPS Operating Systems Review, 2002, 36(1): 147-163.

[7] CHEN L, LENEUTRE J. Toward secure and scalable time synchronization in Ad Hoc networks[M]. Elsevier Science Publishers B: Computer Communications, 2007.

[8] 宋晓雪. 无线自组织网络时间同步技术研究[D]. 成都: 电子科技大学, 2018.

[9] 袁海波, 武福平, 董绍武. 原子钟信号主要噪声类别的判定与分析[J]. 仪器仪表学报, 2008, 29(8): 187-191.

[10] 郭海荣, 郭树人, 焦文海, 等. 原子钟时域频率稳定性计算方法[J]. 飞行器测控学报, 2007, 26(2): 47-52.

[11] 张敏. 原子钟噪声类型和频率稳定度估计的自由度分析与探讨[D]. 西安: 中国科学院国家授时中心, 2008.

[12] 陈伊卿. 无线传感器网络时间同步算法研究[D]. 西安: 西安电子科技大学, 2011.

[13] HUANG G, ZOMAYA A Y, DELICATO F C. An accurate on-demand time synchronization protocol for wireless sensor networks[J]. Journal of Parallel & Distributed Computing, 2012, 72(10): 1332-1346.

[14] MAKARAVA N, HOLSCHNEIDER M. Estimation of the Hurst exponent from noisy data: a Bayesian approach[J]. The European Physical Journal B, 2012, 85(8): 272-471.

[15] 顾仁财, 刘飞. 自适应Kalman滤波的战术数据链自主时间同步算法[J]. 火力与指挥控制, 2019, 44(2): 76-79.

[16] 庄晓燕, 王厚军. 基于卡尔曼滤波器的IEEE 1588时钟同步算法[J]. 电子测量与仪器学报, 2012, 26(9): 747-751.

[17] SARANN L, CATHERINE C, AURORE D. Different methods for spatial interpolation of rainfall data for operational hydrology and hydrological modeling at watershed scale. A review[J]. Biotechnology Agronomy Society & Environment, 2013, 17(2): 392-406.

[18] HASAN M K, SAEED R A, HASHIM A H A, et al. Femtocell network time synchronization protocols and schemes[J]. Research Journal of Applied Science, Engineering and Technology, 2012, 4(23): 5136-5143.

[19] 胡爱华, 邓中亮, 张耀. 基于改进TPSN和卡尔曼滤波的时间同步算法[J]. 现代电子技术, 2018, 41(13): 5-9.

Study on time synchronization algorithm of Ad Hoc networks based on Kalman filter

SUN Li1,2,3, ZOU De-cai1,2,4, HAN Tao5

(1. National Time Service Center, Chinese Academy of Sciences, Xi’an 710600, China;2. Key Laboratory of Precise Positioning and Timing Technology, Chinese Academy of Sciences, Xi’an 710600, China;3. University of Chinese Academy of Sciences, Beijing 100049, China;4. School of Astronomy and Space Science, University of Chinese Academy of Sciences, Beijing 101048, China；5.Faculty of Sciences, Xi’an University of Technology, Xi’an 713300, China)

In this study, the clock model of the Ad Hoc network node is established, the Kalman filter algorithm which suitable for the network node clock model is designed, the covariance matrix of the Kalman filter is estimated using the fractal characteristics of the time difference noise, and the characteristics of the clock noise sequence are analyzed. The simulation results shown that the filtering algorithm not only can improve the efficiency, but also can significantly reduce the clock deviation between network nodes, and achieveshigh-precision time synchronization between Ad Hoc network nodes. The accuracy of synchronization is better than 25 ns.

Ad Hoc; network node; fractal characteristics; Kalman filter

10.13875/j.issn.1674-0637.2020-04-0279-09

孙力, 邹德财, 韩涛. 基于卡尔曼滤波的Ad Hoc网络节点间时间同步算法研究[J]. 时间频率学报, 2020, 43(4): 279-287.

2020-04-17；

2020-05-06

载人航天创新性预研资助项目（17680601）