一種快速實時網絡時鐘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.