范純龍，孫強(qiáng)龍，劉海港

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

0 引言

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

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

1 時(shí)鐘歸并策略

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

2 時(shí)鐘擬合

2.1 時(shí)鐘擬合

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

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

圖1 組合與歸并

圖2 時(shí)鐘擬合過(guò)程

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

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

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

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

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

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

2.2 相對(duì)頻率估計(jì)

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

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

2.3 頻率補(bǔ)償

每個(gè)節(jié)點(diǎn)都會(huì)保存自己對(duì)全局變量的估計(jì)值，并通過(guò)相鄰節(jié)點(diǎn)的估計(jì)值來(lái)更新自身，定義相對(duì)速率遞推公式：

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

2.4 偏移量補(bǔ)償

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

3 MTS算法

3.1 物理時(shí)鐘模型

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

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

4 仿真實(shí)驗(yàn)分析

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

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

圖3 Nodes-10仿真實(shí)驗(yàn)時(shí)鐘收斂過(guò)程

圖4 Nodes-10仿真實(shí)驗(yàn)時(shí)鐘誤差率變化趨勢(shì)

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

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

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

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

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

5 結(jié)束語(yǔ)

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