基于歸并策略的一致性時鐘同步算法

范純龍，孫強龍，劉海港

（1.沈陽航空航天大學(xué)計算機學(xué)院，沈陽 110136；2.沈陽飛機設(shè)計研究所，沈陽 110035）

0 引言

隨著系統(tǒng)日益龐大復(fù)雜，分布化程度越來越高，諸多領(lǐng)域?qū)W(wǎng)絡(luò)各個節(jié)點的實時性和確定性有了更高要求。對于不同的應(yīng)用場合，時鐘同步的精確度需求有所不同。在工業(yè)領(lǐng)域，傳感器的時鐘同步精度一般要求在ms甚至μs級別；而在航空航天領(lǐng)域，其大規(guī)模信息化系統(tǒng)所要求的時間同步精度要求在μs甚至ns級別；而在一些精密儀器高頻測試領(lǐng)域，時鐘同步精度達(dá)到ns級別。

本文從時鐘同步本質(zhì)需求出發(fā)，在深入研究SPAD邏輯時鐘模型與MTS算法的優(yōu)缺點。在時鐘擬合的過程中上引入歸并策略，優(yōu)化時鐘迭代過程中的調(diào)節(jié)因子σij。仿真結(jié)果也表明改進(jìn)后的MTS算法的同步精度、收斂速度、穩(wěn)定性都得到了顯著提升。

1 時鐘歸并策略

在一個仿真節(jié)點群內(nèi)，每個仿真節(jié)點需要測試與廣播自身與群代表時鐘延遲，以此得到一個有序的群間時鐘延遲序列T{T1，T2，T3，…，Tn}。如圖1所示，提出兩種組合策略。極大極小組合策略所產(chǎn)生的時鐘組合在擬合虛擬時鐘的過程中方差小，但通信代價大；而鄰近組合則是方差大，通信代價小。時鐘歸并擬合的核心是通過少量的局部信息交換實現(xiàn)分布式一致性。

2 時鐘擬合

2.1 時鐘擬合

假定物理時鐘是穩(wěn)定的，可設(shè)計算機物理時鐘的計時模型為：

中，Ti（t）表示仿真節(jié)點i的本地時間計時結(jié)果；ai表示節(jié)點i的計時速度；bi表示仿真節(jié)點i的初始偏移量。

圖1 組合與歸并

圖2 時鐘擬合過程

定義擬合的邏輯時鐘的數(shù)學(xué)模型：

如圖2右邊所示，相鄰的兩個本地時鐘所擬合的邏輯時鐘模型依舊是線性的。我們期望將所有的仿真節(jié)點的本地時鐘信息，都包含至一個虛擬的線性邏輯時鐘模型中。在此，定義該時鐘為Tv（t），數(shù)學(xué)模型為：

式中，av為最終虛擬時鐘頻率；bv為虛擬時鐘的初始偏移量；t為本地時鐘計數(shù)值。通過對本地時鐘進(jìn)行歸并擬合，可以估算出參數(shù)av與bv。

根據(jù)式（2）以初步確定av與bv的計算方法，定義擬合時鐘的遞推計時模型：

式中，Tn表示時鐘計數(shù)值，n=1，2，3，…表示步進(jìn)次數(shù)；?表示邏輯時間間隔；a表示時鐘頻率。

在時鐘同步過程中，用σijn表示節(jié)點i的n次步進(jìn)時相對于節(jié)點j的校準(zhǔn)因子，是所歸并的本地時鐘差值與上一步進(jìn)差值的比值，定義：

2.2 相對頻率估計

節(jié)點i，j會在tn時刻以相同的頻率互相發(fā)送存儲各自本地時鐘計數(shù)值Ti（tn）與Tj（tn），節(jié)點i會在下一步進(jìn)估算自身相對于其鄰居節(jié)點j的相對頻率，記作定義相對頻率估計的遞推公式：

式中， 表示時鐘迭代調(diào)控因子，主要作用一是降噪，二是使aij隨時間自適應(yīng)性自增長。

2.3 頻率補償

每個節(jié)點都會保存自己對全局變量的估計值，并通過相鄰節(jié)點的估計值來更新自身，定義相對速率遞推公式：

式中，avi，n-1表示節(jié)點i在n-1步進(jìn)時對全局時鐘速率的估計值；avj，n-1表示參考節(jié)點j在n-1步進(jìn)時對全局時鐘速率的擬合值。

2.4 偏移量補償

當(dāng)所有的時鐘都完成對時鐘速率的補償，剩下的就是修復(fù)對時鐘初始偏移量的誤差，根據(jù)式（4）與式（5），定義初始偏移量的遞推公式：

3 MTS算法

3.1 物理時鐘模型

MTS算法的核心是通過鄰近時鐘兩兩歸并，使所有仿真節(jié)點時鐘頻率快速收斂到全局虛擬時鐘頻率，以此實現(xiàn)全網(wǎng)時鐘同步。因此時鐘擬合過程的計算代價直接影響同步效果。由時鐘擬合原理可知，每個仿真節(jié)點需要保存少量參數(shù)，計算代價小，在此給出MTS算法偽代碼。

算法1 基于歸并策略的一致性時鐘同步算法

4 仿真實驗分析

實驗測試在Windows 7平臺下，基于Matlab R2018a，采用Intel core i7-3770K 3.7GHz和8GB內(nèi)存配置?？紤]到在實際條件下難以達(dá)到測試的絕對同步性，即很難實現(xiàn)全部測試節(jié)點在相同的物理時刻進(jìn)行時鐘數(shù)據(jù)采樣，本文采用仿真的方式對時間同步方法進(jìn)行測試與分析。本次實驗點仿真節(jié)點數(shù)量是10。仿真步長設(shè)定為0.001s，仿真步數(shù)設(shè)定為100?？紤]到仿真節(jié)點的物理時鐘頻率的實際變動，確保仿真評估的可信性，選取的兩組節(jié)點的本地時鐘計時模型不盡相同，主要測試算法的收斂速度與每個節(jié)點邏輯計數(shù)值與級數(shù)均值的間隙大小。

實驗結(jié)果如下：如圖3與圖4所示，各仿真節(jié)點的大約在17步時達(dá)到全網(wǎng)同步，與時鐘計時均值的偏差也趨于0，算法收斂速度較快；且呈現(xiàn)出一旦同步，便不再失步，穩(wěn)定性高。

圖3 Nodes-10仿真實驗時鐘收斂過程

圖4 Nodes-10仿真實驗時鐘誤差率變化趨勢

在相對穩(wěn)定的分布式仿真網(wǎng)絡(luò)中，MTS算法有著非常高的同步精度，而且其同步精度隨著時間的增長呈現(xiàn)正相關(guān)趨勢。在仿真實驗過程中，30步進(jìn)，時鐘同步精度為10-15s，90至100步進(jìn)時已經(jīng)達(dá)到了10-31s同步精度。

圖5反映MTS、SPAD、ATS算法仿真節(jié)點總數(shù)量對收斂速度的影響情況?？v坐標(biāo)表示達(dá)到時鐘同步所需的仿真步數(shù)，橫坐標(biāo)表示仿真節(jié)點數(shù)量。分別設(shè)定五組不同數(shù)量的仿真節(jié)點N：[5，10，20，50，100]，不同仿真節(jié)點的時鐘更新速度采樣區(qū)間是[0.5，1.5]，仿真周期0.001s。采用歸并策略的MTS算法在不同仿真節(jié)點數(shù)量下，其收斂速度以及穩(wěn)定度相比于ATS、SPAD都有很大的提升。

圖5 不同算法仿真節(jié)點總量對收斂速度的影響

圖6反映不同歸并策略對算法收斂速度的影響情況。仿真節(jié)點數(shù)量為20，不同仿真節(jié)點的時鐘更新速度采樣區(qū)間是[0.5，1.5]，仿真周期為0.001s。采用極大極小策略，時鐘擬合最快，算法收斂速度快，其次是鄰近策略。這兩種相比于原算法在收斂速度方面皆有提升，但需要在這里指出的是，極大極小策略會有較高的延時成本，而鄰近策略網(wǎng)絡(luò)延時代價較低。

圖6 不同歸并策略下的MTS與ATS算法收斂速度影響

5 結(jié)束語

在ATS算法一致性同步的基礎(chǔ)上，結(jié)合SPAD算法的參量差分邏輯時鐘，并針對性地提出了一種基于歸并策略的時鐘同步算法（MTS）。MTS是一種集一致性同步、參量差分、邏輯時鐘、歸并策略等諸多方法于一體的算法。仿真實驗表明，相較于原算法，MTS在同步精度、收斂速度、穩(wěn)定性方面，都有提升。同時，本文也提出了分布式節(jié)點群同步策略的設(shè)想，其準(zhǔn)確性也有待進(jìn)一步的仿真實驗驗證。