一種快速實(shí)時(shí)網(wǎng)絡(luò)時(shí)鐘MTIE評(píng)估算法

王錚 齊昕 陳旭東 王敬

摘要：介紹了一種快速實(shí)時(shí)的網(wǎng)絡(luò)時(shí)鐘最大時(shí)間間隔誤差（MTIE）評(píng)估算法的實(shí)現(xiàn)方法和測(cè)試結(jié)果。MTIE算法是一種通信網(wǎng)絡(luò)領(lǐng)域重要的時(shí)間信號(hào)特性評(píng)估算法，它可以識(shí)別出在給定觀測(cè)窗口內(nèi)的最大相位差。描述了快速實(shí)時(shí)網(wǎng)絡(luò)時(shí)鐘MTIE評(píng)估算法，實(shí)現(xiàn)了MTIE曲線的實(shí)時(shí)計(jì)算，并針對(duì)算法效率進(jìn)行了對(duì)比測(cè)試。測(cè)試結(jié)果表明，快速實(shí)時(shí)MTIE算法可以有效減小運(yùn)算量，并提高計(jì)算效率。

關(guān)鍵詞：實(shí)時(shí)運(yùn)算；網(wǎng)絡(luò)時(shí)鐘測(cè)試評(píng)估；時(shí)鐘穩(wěn)定度

中圖分類號(hào)：TP212文獻(xiàn)標(biāo)志碼：A文章編號(hào)：1008-1739（2020）10-64-4

0引言

MTIE算法作為時(shí)鐘漂移和抖動(dòng)評(píng)估的重要數(shù)據(jù)處理手段，在通信領(lǐng)域有著廣泛的應(yīng)用，依據(jù)通信行業(yè)時(shí)鐘測(cè)試與評(píng)估標(biāo)準(zhǔn)，部分測(cè)試模板測(cè)試時(shí)間長(zhǎng)達(dá)120 000 s[1]，傳統(tǒng)測(cè)試采取先采集數(shù)據(jù)后處理的方式，測(cè)試停止后集中運(yùn)算對(duì)處理要求較高、處理時(shí)間長(zhǎng)，且無法實(shí)時(shí)查看測(cè)試結(jié)果。本文介紹了一種快速實(shí)時(shí)MTIE算法，在數(shù)據(jù)采集過程中實(shí)時(shí)計(jì)算MTIE結(jié)果，測(cè)試人員可及時(shí)了解測(cè)試情況，緩解數(shù)據(jù)采集結(jié)束后的運(yùn)算壓力，適合網(wǎng)絡(luò)時(shí)鐘分析儀使用。

1 MTIE算法

1.1基本定義

時(shí)間間隔誤差（Time Interval Error，TIE）是指在特定時(shí)間周期內(nèi)，一個(gè)給定信號(hào)相對(duì)于理想信號(hào)的時(shí)延變化[2]。MTIE是指在一個(gè)測(cè)量周期內(nèi)，一個(gè)給定窗口內(nèi)的最大相位變化[2]。MTIE和TIE的定義示意圖如圖1所示。

如果對(duì)于給定的時(shí)延誤差值以0為取樣間隔進(jìn)行采樣，結(jié)果形成個(gè)等間隔取樣{ }，則最大時(shí)間間隔誤差能夠用以下公式估計(jì)：

式中，表示時(shí)延的抽樣數(shù)據(jù)；表示抽樣數(shù)據(jù)的總數(shù)；0表示取樣間隔；表示觀測(cè)時(shí)間內(nèi)的抽樣數(shù)。

MTIE算法是在通信領(lǐng)域常用的一種重要的時(shí)間信號(hào)分析方法[3]，依據(jù)給定的窗口大小獲取窗口內(nèi)最大時(shí)間變化量的算法。MTIE對(duì)于一個(gè)單個(gè)的極值、非定常值或奇異值非常敏感，同時(shí)MTIE曲線同樣可以反映頻率信號(hào)的穩(wěn)定性和準(zhǔn)確度[4]。

1.2直接搜索MTIE算法描述

2快速實(shí)時(shí)法計(jì)算MTIE

快速搜索方法是在直接搜索法基礎(chǔ)上，通過記錄窗口內(nèi)最大值和最小值位置的方式，避免了在窗口移動(dòng)過程中的重復(fù)求最大值和最小值的方法[6]，在窗口移動(dòng)過程中，其處理方法如圖4所示。

對(duì)已給定的窗口值，第一次通過最大值和最小值算法求出最大值和最小值及位置。窗口向右移動(dòng)時(shí)，首先判斷上一窗口位置最大值或最小值是否移出窗口。若移出窗口，則重新搜索最大或最小值；若未移出窗口，則比較最新進(jìn)入窗口的值和原最大值和最小值的大小關(guān)系，更新或維持最大值和最小值。

加速算法可以大幅度減少重復(fù)運(yùn)算，提高M(jìn)TIE運(yùn)算程序執(zhí)行速度，在快速搜索的基礎(chǔ)上，采用實(shí)時(shí)方法進(jìn)一步針對(duì)MTIE算法進(jìn)行改進(jìn)，將其更改為實(shí)時(shí)運(yùn)算，主要應(yīng)用到的中間量為行3列的矩陣Cache，矩陣行號(hào)代表窗口大小、矩陣第一列為窗口最大值坐標(biāo)、矩陣第二列為窗口最小值坐標(biāo)、矩陣第三列為窗口的MTIE值，單次實(shí)時(shí)運(yùn)算流程如圖5所示。

主要程序設(shè)計(jì)流程如下：

①采集數(shù)據(jù)；

②復(fù)制Cache矩陣第-1列，插入列；

③依次判斷各最終窗口最大、最小值是否離開窗口；

④若最大值或最小值離開窗口，則重新搜索當(dāng)前窗口最大或最小值，作為新的窗口最大和最小值，執(zhí)行步驟⑥；

⑤若未離開窗口直接執(zhí)行步驟⑥；

⑥依次比較Cache中的第1列、第2列指向的最大數(shù)和最小數(shù)進(jìn)行比較，若新增數(shù)據(jù)大于最大值或小于最小值，則以新增數(shù)據(jù)替換該行最大值和最小值，并計(jì)算最大值和最小值之差，與Cache矩陣第3列值進(jìn)行比較，若大于第3列值，則替換該值，否則維持Cache矩陣該行不變；

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

⑧對(duì)第行，無需判斷窗口最大值和最小值是否離開窗口，直接執(zhí)行步驟④即可；

⑨等待采集新數(shù)據(jù)后，重復(fù)步驟①～⑧；

⑩直至數(shù)據(jù)采集數(shù)量達(dá)到要求后，Cache矩陣第3列記為MTIE曲線坐標(biāo)值。

Cache矩陣的數(shù)據(jù)處理流程如圖6所示。

3算法效率分析

直接搜索法針對(duì)樣本數(shù)量為的數(shù)列進(jìn)行計(jì)算式時(shí)，均需要針對(duì)數(shù)列進(jìn)行（ -1）次個(gè)窗口運(yùn)算，每個(gè)窗口運(yùn)算需要進(jìn)行（ - -1）次窗口滑動(dòng)，每個(gè)窗口需要進(jìn)行次比較以計(jì)算最大、最小值，其算法時(shí)間復(fù)雜度為（2）?？焖賹?shí)時(shí)MTIE算法與直接搜索MTIE算法相比，通過記錄窗口最大值和最小值的位置，可有效減少搜索窗口最大值和最小值的次數(shù)，實(shí)現(xiàn)了算法時(shí)間復(fù)雜度的降低，算法時(shí)間復(fù)雜度仍為（2）。

為了測(cè)試、比較快速實(shí)時(shí)MTIE算法與直接搜索算法的運(yùn)算效能，使用Stable32軟件生成隨機(jī)相位噪聲數(shù)列，并分別使用快速實(shí)時(shí)MTIE算法和直接搜索MTIE算法同時(shí)針對(duì)噪聲數(shù)列求取MTIE曲線，并記錄運(yùn)算時(shí)間，測(cè)試環(huán)境為Windows7系統(tǒng)，使用Matlab2017進(jìn)行算法仿真運(yùn)算。其中，采用直接計(jì)算法計(jì)算1～10 000采樣數(shù)據(jù)時(shí)，運(yùn)算時(shí)間—樣本數(shù)目統(tǒng)計(jì)圖。采用快速實(shí)時(shí)算法每次接收到測(cè)量數(shù)據(jù)后，單次實(shí)時(shí)運(yùn)算時(shí)間—樣本個(gè)數(shù)統(tǒng)計(jì)圖如圖7所示，累積計(jì)算用時(shí)—樣本個(gè)數(shù)統(tǒng)計(jì)圖如圖8所示。

經(jīng)比較，快速實(shí)時(shí)MTIE算法，單次運(yùn)行時(shí)間與樣本累積個(gè)數(shù)具有線性增長(zhǎng)關(guān)系，總運(yùn)行時(shí)間與樣本個(gè)數(shù)成二次曲線關(guān)系。直接搜索法運(yùn)行時(shí)間與樣本個(gè)數(shù)也成二次曲線關(guān)系，但由于其重復(fù)運(yùn)算過多算法效率低于快速實(shí)時(shí)MTIE算法。因此，快速實(shí)時(shí)MTIE算法可提高M(jìn)TIE曲線計(jì)算效率，并可在數(shù)據(jù)采集過程中進(jìn)行實(shí)時(shí)運(yùn)算，并實(shí)時(shí)展示計(jì)算結(jié)果，可及時(shí)發(fā)現(xiàn)測(cè)試過程中被測(cè)時(shí)鐘故障，及時(shí)停止測(cè)試并進(jìn)行維修，適用于應(yīng)用在網(wǎng)絡(luò)時(shí)鐘測(cè)試中。

4結(jié)束語

通過快速實(shí)時(shí)MTIE算法，可滿足在數(shù)據(jù)采集過程中實(shí)時(shí)運(yùn)算MTIE計(jì)算結(jié)果的設(shè)計(jì)要求，使用實(shí)時(shí)算法緩解了數(shù)據(jù)采集結(jié)束后的運(yùn)算壓力，使得時(shí)鐘測(cè)試結(jié)果實(shí)時(shí)可見，測(cè)試人員可隨時(shí)了解時(shí)鐘運(yùn)行狀況，及時(shí)發(fā)現(xiàn)并處理故障。同時(shí)快速實(shí)時(shí)MTIE算法可有效減少運(yùn)算量、提高計(jì)算效率，適合網(wǎng)絡(luò)時(shí)鐘分析儀中使用。

參考文獻(xiàn)

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

[2]中華人民共和國(guó)信息產(chǎn)業(yè)部.數(shù)字同步網(wǎng)獨(dú)立型節(jié)點(diǎn)從鐘設(shè)備技術(shù)要求及測(cè)試方法：YD/T 1011-1999[S].北京：人民郵電出版社，1999.

[3]王亞梅，余學(xué)鋒.頻率源時(shí)間量特性表征方法及其分析[J].計(jì)量與測(cè)試技術(shù)，2007（11）：60-61，64.

[4]余學(xué)鋒，張紅清，李培.最大時(shí)間間隔誤差計(jì)算方法及其分析[J].宇航計(jì)測(cè)技術(shù)，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.