一种快速实时网络时钟MTIE评估算法

王铮 齐昕 陈旭东 王敬

摘要：介绍了一种快速实时的网络时钟最大时间间隔误差（MTIE）评估算法的实现方法和测试结果。MTIE算法是一种通信网络领域重要的时间信号特性评估算法，它可以识别出在给定观测窗口内的最大相位差。描述了快速实时网络时钟MTIE评估算法，实现了MTIE曲线的实时计算，并针对算法效率进行了对比测试。测试结果表明，快速实时MTIE算法可以有效减小运算量，并提高计算效率。

关键词：实时运算；网络时钟测试评估；时钟稳定度

中图分类号：TP212文献标志码：A文章编号：1008-1739（2020）10-64-4

0引言

MTIE算法作为时钟漂移和抖动评估的重要数据处理手段，在通信领域有着广泛的应用，依据通信行业时钟测试与评估标准，部分测试模板测试时间长达120 000 s[1]，传统测试采取先采集数据后处理的方式，测试停止后集中运算对处理要求较高、处理时间长，且无法实时查看测试结果。本文介绍了一种快速实时MTIE算法，在数据采集过程中实时计算MTIE结果，测试人员可及时了解测试情况，缓解数据采集结束后的运算压力，适合网络时钟分析仪使用。

1 MTIE算法

1.1基本定义

时间间隔误差（Time Interval Error，TIE）是指在特定时间周期内，一个给定信号相对于理想信号的时延变化[2]。MTIE是指在一个测量周期内，一个给定窗口内的最大相位变化[2]。MTIE和TIE的定义示意图如图1所示。

如果对于给定的时延误差值以0为取样间隔进行采样，结果形成个等间隔取样{ }，则最大时间间隔误差能够用以下公式估计：

式中，表示时延的抽样数据；表示抽样数据的总数；0表示取样间隔；表示观测时间内的抽样数。

MTIE算法是在通信领域常用的一种重要的时间信号分析方法[3]，依据给定的窗口大小获取窗口内最大时间变化量的算法。MTIE对于一个单个的极值、非定常值或奇异值非常敏感，同时MTIE曲线同样可以反映频率信号的稳定性和准确度[4]。

1.2直接搜索MTIE算法描述

2快速实时法计算MTIE

快速搜索方法是在直接搜索法基础上，通过记录窗口内最大值和最小值位置的方式，避免了在窗口移动过程中的重复求最大值和最小值的方法[6]，在窗口移动过程中，其处理方法如图4所示。

对已给定的窗口值，第一次通过最大值和最小值算法求出最大值和最小值及位置。窗口向右移動时，首先判断上一窗口位置最大值或最小值是否移出窗口。若移出窗口，则重新搜索最大或最小值；若未移出窗口，则比较最新进入窗口的值和原最大值和最小值的大小关系，更新或维持最大值和最小值。

加速算法可以大幅度减少重复运算，提高MTIE运算程序执行速度，在快速搜索的基础上，采用实时方法进一步针对MTIE算法进行改进，将其更改为实时运算，主要应用到的中间量为行3列的矩阵Cache，矩阵行号代表窗口大小、矩阵第一列为窗口最大值坐标、矩阵第二列为窗口最小值坐标、矩阵第三列为窗口的MTIE值，单次实时运算流程如图5所示。

主要程序设计流程如下：

①采集数据；

②复制Cache矩阵第-1列，插入列；

③依次判断各最终窗口最大、最小值是否离开窗口；

④若最大值或最小值离开窗口，则重新搜索当前窗口最大或最小值，作为新的窗口最大和最小值，执行步骤⑥；

⑤若未离开窗口直接执行步骤⑥；

⑥依次比较Cache中的第1列、第2列指向的最大数和最小数进行比较，若新增数据大于最大值或小于最小值，则以新增数据替换该行最大值和最小值，并计算最大值和最小值之差，与Cache矩阵第3列值进行比较，若大于第3列值，则替换该值，否则维持Cache矩阵该行不变；

⑦依次更新Cache矩阵原有各行；

⑧对第行，无需判断窗口最大值和最小值是否离开窗口，直接执行步骤④即可；

⑨等待采集新数据后，重复步骤①～⑧；

⑩直至数据采集数量达到要求后，Cache矩阵第3列记为MTIE曲线坐标值。

Cache矩阵的数据处理流程如图6所示。

3算法效率分析

直接搜索法针对样本数量为的数列进行计算式时，均需要针对数列进行（ -1）次个窗口运算，每个窗口运算需要进行（ - -1）次窗口滑动，每个窗口需要进行次比较以计算最大、最小值，其算法时间复杂度为（2）。快速实时MTIE算法与直接搜索MTIE算法相比，通过记录窗口最大值和最小值的位置，可有效减少搜索窗口最大值和最小值的次数，实现了算法时间复杂度的降低，算法时间复杂度仍为（2）。

为了测试、比较快速实时MTIE算法与直接搜索算法的运算效能，使用Stable32软件生成随机相位噪声数列，并分别使用快速实时MTIE算法和直接搜索MTIE算法同时针对噪声数列求取MTIE曲线，并记录运算时间，测试环境为Windows7系统，使用Matlab2017进行算法仿真运算。其中，采用直接计算法计算1～10 000采样数据时，运算时间—样本数目统计图。采用快速实时算法每次接收到测量数据后，单次实时运算时间—样本个数统计图如图7所示，累积计算用时—样本个数统计图如图8所示。

经比较，快速实时MTIE算法，单次运行时间与样本累积个数具有线性增长关系，总运行时间与样本个数成二次曲线关系。直接搜索法运行时间与样本个数也成二次曲线关系，但由于其重复运算过多算法效率低于快速实时MTIE算法。因此，快速实时MTIE算法可提高MTIE曲线计算效率，并可在数据采集过程中进行实时运算，并实时展示计算结果，可及时发现测试过程中被测时钟故障，及时停止测试并进行维修，适用于应用在网络时钟测试中。

4结束语

通过快速实时MTIE算法，可满足在数据采集过程中实时运算MTIE计算结果的设计要求，使用实时算法缓解了数据采集结束后的运算压力，使得时钟测试结果实时可见，测试人员可随时了解时钟运行状况，及时发现并处理故障。同时快速实时MTIE算法可有效减少运算量、提高计算效率，适合网络时钟分析仪中使用。

参考文献

[1] ITU-T.Definitions and Terminology for Synchronization Networks：ITU-T G.810[S]，1996.

[2]中华人民共和国信息产业部.数字同步网独立型节点从钟设备技术要求及測试方法：YD/T 1011-1999[S].北京：人民邮电出版社，1999.

[3]王亚梅，余学锋.频率源时间量特性表征方法及其分析[J].计量与测试技术，2007（11）：60-61，64.

[4]余学锋，张红清，李培.最大时间间隔误差计算方法及其分析[J].宇航计测技术，2007（3）：39-42，47.

[5] DOBROGOWSKI A， KASZNIA M.Testing of the Methods of Real-time MTIE Calculation[C]//Frequency Control Symposium and Exposition， Proceedings of the 2005 IEEE International，Aug.29-31，2005：397-403.

[6] Dobrogowski A， Kasznia M.Some Concepts of the Real-time MTIE Assessment for Multi-channel Time Error Measurement[C]//IEEE International Frequency Control Symposium Proceedings，2012.