陸 禹，張 力，張鳳登

(上海理工大學(xué) 光電信息與計(jì)算機(jī)工程學(xué)院，上海 200093)

隨著計(jì)算機(jī)信息化高速發(fā)展，各種網(wǎng)絡(luò)化系統(tǒng)大都可以對(duì)數(shù)據(jù)進(jìn)行自我采集和處理。分布式系統(tǒng)作為典型的網(wǎng)絡(luò)化系統(tǒng)，其研究也受到越來(lái)越廣泛的關(guān)注[1]。隨著分布式系統(tǒng)復(fù)雜度和規(guī)模的增大[2]，為系統(tǒng)分配的節(jié)點(diǎn)數(shù)目也不斷增多，系統(tǒng)發(fā)生故障的概率也越來(lái)越高。面對(duì)目前有嚴(yán)格要求的實(shí)時(shí)系統(tǒng)，確保高精度的時(shí)鐘同步是避免故障且維持系統(tǒng)有效控制和精確運(yùn)行的必要條件之一[3]。在滿足時(shí)鐘同步的前提下，系統(tǒng)還需要具有一定的容錯(cuò)性[4-6]，使得分布式系統(tǒng)在其中幾個(gè)節(jié)點(diǎn)出現(xiàn)斷線時(shí)，仍然可以保持正常節(jié)點(diǎn)的時(shí)鐘同步。

目前，國(guó)內(nèi)外研究人員已經(jīng)提出了許多基于節(jié)點(diǎn)雙向交換各自時(shí)鐘信息的時(shí)鐘參數(shù)估計(jì)算法來(lái)解決時(shí)鐘同步中的精度問(wèn)題，并取得了一定成果[7-11]。文獻(xiàn)[12]通過(guò)將卡爾曼濾波算法和自然選擇粒子群算法結(jié)合，提高了無(wú)線傳感器網(wǎng)絡(luò)的時(shí)鐘同步精度。

本文主要致力于研究經(jīng)典分布式系統(tǒng)內(nèi)部時(shí)鐘同步算法在運(yùn)行過(guò)程中遇到的通信鏈路丟失故障的解決方案，并基于此提出一種可以容忍該故障的灰色預(yù)測(cè)容錯(cuò)時(shí)鐘同步算法。

1 系統(tǒng)模型描述

本文采用廣播式通信網(wǎng)絡(luò)LL(Lundelius Lynch)模型[13]，并將時(shí)鐘狀態(tài)修正和時(shí)鐘速率修正相結(jié)合。該模型在每輪次中重復(fù)執(zhí)行時(shí)鐘同步算法，其節(jié)點(diǎn)僅在特定時(shí)刻發(fā)送與時(shí)間相關(guān)的消息，有效降低了獲取時(shí)間節(jié)點(diǎn)消息的通信成本。

從有關(guān)Cristian和LL模型的研究中可知，基于遠(yuǎn)程時(shí)鐘讀取技術(shù)時(shí)鐘的最大估算誤差為2d(1+2ρ)-2(δ-ε)，而基于初始同步的時(shí)鐘檢測(cè)技術(shù)時(shí)鐘的最大估算誤差為2(ε+β+ρδ)[14]。其中，d表示以A節(jié)點(diǎn)時(shí)鐘為基礎(chǔ)所測(cè)量的A節(jié)點(diǎn)發(fā)送與B節(jié)點(diǎn)回復(fù)過(guò)程的總路程的一半，ρ為時(shí)鐘漂移率，δ為可能存在的通信延遲的中值，ε為通信延遲的一個(gè)細(xì)微不確定度，β為一個(gè)先驗(yàn)的固定值，表示初始時(shí)刻節(jié)點(diǎn)間的同步程度。由于LL模型不需要請(qǐng)求-回復(fù)機(jī)制，所以它的通信開(kāi)銷(xiāo)更小。對(duì)于遠(yuǎn)程時(shí)鐘讀取模型而言，由于節(jié)點(diǎn)之間不是點(diǎn)對(duì)點(diǎn)地發(fā)送消息，所以一定程度上增大了讀取時(shí)鐘的誤差，但是在廣播式網(wǎng)絡(luò)中可避免此類(lèi)問(wèn)題。

該模型對(duì)重同步周期TP及節(jié)點(diǎn)的初始狀態(tài)有一定要求，下面對(duì)模型進(jìn)行條件假設(shè)。

1.1 條件假設(shè)

采用模型分析算法時(shí)，需對(duì)模型進(jìn)行一定條件的假設(shè)，這樣才可以合理地分析算法的性能。本文將分布式系統(tǒng)中所有節(jié)點(diǎn)用集合P表示，每一個(gè)節(jié)點(diǎn)進(jìn)程pi∈P都對(duì)應(yīng)一個(gè)用Hpi表示的本地時(shí)鐘。具體假設(shè)如下文所述：

假設(shè)1假設(shè)本地時(shí)鐘漂移率處在一個(gè)合理范圍內(nèi)，即一個(gè)極小的常數(shù)ρ>0。本文定義在任意真實(shí)時(shí)間t時(shí)，本地時(shí)鐘Hpi(t)與ρ都存在如下關(guān)系

(1)

式中，Hpi(t)表示i節(jié)點(diǎn)在真實(shí)時(shí)間t時(shí)對(duì)應(yīng)的本地時(shí)鐘值；ρ表示i節(jié)點(diǎn)的本地時(shí)鐘漂移率；

假設(shè)2系統(tǒng)內(nèi)節(jié)點(diǎn)間消息通信延遲有界，也就是節(jié)點(diǎn)之間通過(guò)任何鏈接發(fā)送、傳輸、接收任何消息所產(chǎn)生的通信延遲Td在范圍[δ-ε，δ+ε]內(nèi)。即

Td∈[δ-ε，δ+ε]

(2)

當(dāng)該假設(shè)成立時(shí)，時(shí)鐘同步算法保證了系統(tǒng)中各個(gè)節(jié)點(diǎn)之間的最大邏輯時(shí)間偏差值在一定范圍內(nèi)，也就是精密度γ；

假設(shè)3分布式系統(tǒng)中故障節(jié)點(diǎn)有限，設(shè)定系統(tǒng)中故障節(jié)點(diǎn)數(shù)不能超出系統(tǒng)總節(jié)點(diǎn)數(shù)的三分之一

n≥3f+1

(3)

式中，n表示系統(tǒng)中所有節(jié)點(diǎn)的總數(shù)目；f表示系統(tǒng)中拜占庭故障節(jié)點(diǎn)的數(shù)目；

假設(shè)4為了更加容易地分析流程，可以忽略消息處理產(chǎn)生的延遲；

假設(shè)5節(jié)點(diǎn)在系統(tǒng)開(kāi)始工作的初始時(shí)間點(diǎn)為T(mén)0，A節(jié)點(diǎn)在初始時(shí)間點(diǎn)的真實(shí)時(shí)間為CA(T0)，B節(jié)點(diǎn)在初始時(shí)間點(diǎn)的真實(shí)時(shí)間為CB(T0)。系統(tǒng)的正常工作節(jié)點(diǎn)在初始時(shí)間點(diǎn)時(shí)同步在一個(gè)固定先驗(yàn)范圍內(nèi)，表達(dá)式為

|CA(T0)-CB(T0)|≤β

(4)

式中，β為一個(gè)先驗(yàn)的固定值；A和B為系統(tǒng)中可正常工作的節(jié)點(diǎn)。

假設(shè)6時(shí)鐘同步時(shí)，A節(jié)點(diǎn)在發(fā)送自身節(jié)點(diǎn)時(shí)鐘消息時(shí)，其余正常工作節(jié)點(diǎn)和A節(jié)點(diǎn)處在同一輪次中。因?yàn)橄到y(tǒng)需要進(jìn)行重復(fù)的時(shí)鐘同步，因此要對(duì)重同步周期TP做出以下的假設(shè)

TP>2(1+ρ)(β+ε)+(1+ρ)max{δ，β+ε}+ρδ

(5)

且

TP≤β/4ρ-ε/ρ-ρ(β+δ+ε)-2β-δ-2ε

(6)

若沒(méi)有特殊指明，本文的其它假設(shè)與前提條件都與LL模型一致。

1.2 模型具體應(yīng)用

單個(gè)節(jié)點(diǎn)通過(guò)廣播的方式將自己的時(shí)鐘信息發(fā)送給其它各個(gè)節(jié)點(diǎn)[15]。系統(tǒng)的時(shí)鐘同步是一個(gè)重復(fù)的周期性過(guò)程，可以將邏輯時(shí)鐘用輪次的形式表示時(shí)鐘同步過(guò)程。每一輪次中，時(shí)間的總長(zhǎng)度L是恒定不變的，一輪次中有k個(gè)宏時(shí)隙，則表達(dá)式如式(7)所示。

L=k×ng

(7)

式中，ng表示系統(tǒng)全局時(shí)間的一個(gè)宏時(shí)隙長(zhǎng)度。由于時(shí)鐘同步是周期性過(guò)程，因此其長(zhǎng)度同樣要滿足上述重同步周期的條件。每輪要留出固定長(zhǎng)度的時(shí)間作為修正段，例如FlexRay網(wǎng)絡(luò)中通常稱(chēng)為NIT(Network Idle Time)段[16]，節(jié)點(diǎn)的時(shí)鐘邏輯時(shí)間在NIT段內(nèi)進(jìn)行時(shí)鐘狀態(tài)修正和時(shí)鐘速率修正。本文用4個(gè)節(jié)點(diǎn)在完全同步的狀態(tài)下作為示范說(shuō)明第i輪的結(jié)構(gòu)，節(jié)點(diǎn)的相關(guān)參數(shù)如表1所示。

表1 節(jié)點(diǎn)參數(shù)表

圖1 理想狀態(tài)下第i輪狀態(tài)圖Figure 1. State diagram of the i round in an ideal state

2 Grey-FAT算法

2.1 灰色預(yù)測(cè)

GM(1，1)(Grey Model)是使用一階微分方程對(duì)一個(gè)變量建立灰色預(yù)測(cè)的方法，其原理是對(duì)某一數(shù)據(jù)序列用累加的方式，生成一組趨勢(shì)明顯的新數(shù)據(jù)序列，并按照新的數(shù)據(jù)序列的增長(zhǎng)趨勢(shì)建立模型進(jìn)行預(yù)測(cè)，然后再用累減的方法進(jìn)行逆向計(jì)算，恢復(fù)原始數(shù)據(jù)序列，進(jìn)而得到預(yù)測(cè)結(jié)果。

GM(1，1)預(yù)測(cè)過(guò)程具體如下：

當(dāng)A節(jié)點(diǎn)發(fā)生通信鏈路丟失故障時(shí)，設(shè)有一組前n輪未發(fā)生通信鏈路故障時(shí)通過(guò)FTA(Fault Tolerant Average)算法得到的時(shí)間偏差序列，具體如式(8)所示。

X(0)=[x(0)(1)，x(0)(2)，…，x(0)(n)]

(8)

由原始的時(shí)間序列數(shù)據(jù)生成一階累加生成序列為X(1)

X(1)=[x(1)(1)，x(1)(2)，…，x(1)(n)]

(9)

式中

(10)

同時(shí)生成一階累加生成序列的緊鄰均值生成序列Z(1)

Z(1)=[z(1)(2)，z(1)(2)，…，z(1)(n)]

(11)

式中

(12)

建立灰微分方程

x(0)(k)+az(1)(k)=b，k=2，3，…，n

(13)

式中，a、b分別為發(fā)展系數(shù)和灰作用量。其白化方程為

(14)

則GM(1，1)模型的解為

(15)

式中，a和b由最小二乘法計(jì)算得出，求解過(guò)程為

A=(a，b)T=(BTB)-1BTY

(16)

式中

(17)

最終GM(1，1)模型對(duì)原始偏差值序列的模擬值為

(18)

當(dāng)發(fā)生鏈路故障時(shí)，當(dāng)前輪次A節(jié)點(diǎn)的時(shí)鐘偏差值如式(19)所示。

(19)

2.2 精度校驗(yàn)

使用GM(1，1)模型對(duì)時(shí)鐘在出現(xiàn)通信鏈路丟失故障和通信鏈路性能故障時(shí)的修正值進(jìn)行預(yù)測(cè)。

判斷已知修正值序列數(shù)據(jù)是否符合灰色預(yù)測(cè)模型，需要進(jìn)行預(yù)測(cè)模型的精度校驗(yàn)。模型精度的校驗(yàn)通過(guò)方差比C和小概率誤差P來(lái)評(píng)估，計(jì)算流程如下所示。

首先，需要計(jì)算殘差ε(k)

(20)

再計(jì)算相對(duì)誤差Δ(k)

(21)

然后計(jì)算原始序列的標(biāo)準(zhǔn)差S1和殘差序列的標(biāo)準(zhǔn)差S2

(22)

(23)

則方差比C為

(24)

小概率誤差P為

(25)

模型擬合的精確度由C和P共同決定，GM(1，1)精度檢驗(yàn)等級(jí)參照表2。

表2 GM(1，1)精度檢驗(yàn)等級(jí)

2.3 算法流程

該算法在LL模型基礎(chǔ)上，通過(guò)一定的假設(shè)條件，利用初始時(shí)鐘同步的時(shí)鐘檢測(cè)技術(shù)，來(lái)收集到其余節(jié)點(diǎn)的時(shí)鐘值。此外，該方法還在傳統(tǒng)的FTA算法基礎(chǔ)上加入了灰色預(yù)測(cè)，以此來(lái)解決通信鏈丟失故障。Grey-FTA算法的流程圖如圖2所示。

圖2 Grey- FTA算法流程圖Figure 2. Flow chart of Grey- FTA algorithm

3 實(shí)驗(yàn)與結(jié)果分析

3.1 實(shí)驗(yàn)參數(shù)設(shè)置

本文采用了LL通信網(wǎng)絡(luò)模型，故需將模型中各項(xiàng)條件參數(shù)假設(shè)為相應(yīng)常數(shù)值。具體的條件參數(shù)有時(shí)鐘漂移率ρ、遠(yuǎn)程時(shí)鐘讀取最大誤差ζ、節(jié)點(diǎn)通信最大延遲β、同步初始狀態(tài)偏差δinit以及時(shí)鐘重同步周期TP。參考汽車(chē)或航空器中參數(shù)相應(yīng)常見(jiàn)真實(shí)數(shù)值范圍，本文的設(shè)定如表3所示。

表3 實(shí)驗(yàn)參數(shù)假設(shè)常數(shù)值

為了體現(xiàn)Grey-FTA算法對(duì)于通信鏈路故障的容錯(cuò)能力，模擬驗(yàn)證實(shí)驗(yàn)將本文所提算法與原始處理(Native)、水平滑動(dòng)估計(jì)(Moving-Horizon Estimation， MHE)[17]和全局濾波估計(jì)(Overall Filtering Estimation， OFE)[18]這3種處理通信鏈路故障方法進(jìn)行對(duì)比。實(shí)驗(yàn)節(jié)點(diǎn)參數(shù)設(shè)置如表4所示。

表4 實(shí)驗(yàn)節(jié)點(diǎn)參數(shù)設(shè)置

3.2 實(shí)驗(yàn)步驟

實(shí)驗(yàn)中首先構(gòu)建共含5個(gè)模擬驗(yàn)證節(jié)點(diǎn)的CAN總線網(wǎng)絡(luò)，分別為Node1～Node5。真實(shí)情況中總線型網(wǎng)絡(luò)的通信鏈路故障表現(xiàn)為：在通信周期內(nèi)，節(jié)點(diǎn)無(wú)法正常訪問(wèn)通信媒介，即發(fā)送或接收總線報(bào)文失敗[19]。在實(shí)驗(yàn)中為了模擬通信鏈路故障，專(zhuān)門(mén)設(shè)置一條特殊的Blank報(bào)文，當(dāng)某個(gè)節(jié)點(diǎn)發(fā)送該報(bào)文時(shí)，即相當(dāng)于該報(bào)文正常發(fā)送失敗或接收節(jié)點(diǎn)接收異常。對(duì)于所有節(jié)點(diǎn)都以一定的故障概率發(fā)生通信鏈路故障，在模擬驗(yàn)證中以CLFP(Comm -Link Failures Probability)表示，即在一個(gè)通信周期內(nèi)發(fā)生一次報(bào)文通信因鏈路故障而失效的概率。具體步驟如下：

步驟1按照起始時(shí)刻、同步初始狀態(tài)偏差開(kāi)始時(shí)鐘同步，所有節(jié)點(diǎn)內(nèi)部運(yùn)行相應(yīng)容錯(cuò)時(shí)鐘同步算法；

步驟2隨機(jī)生成所有模擬驗(yàn)證節(jié)點(diǎn)的這一輪時(shí)鐘同步周期內(nèi)的偏移值，并且均保存并存儲(chǔ)在節(jié)點(diǎn)的通信列表文件中；

步驟3按照通信鏈路故障概率，隨機(jī)決定這一輪是否發(fā)生通信鏈路故障，即發(fā)送Blank報(bào)文；

步驟4在每個(gè)節(jié)點(diǎn)感知到通信鏈路故障后，分別按照Native、Grey-FTA、MHE-FTA、OFE-FTA4種處理方式或算法得到該輪的時(shí)鐘修正值，并計(jì)算出修正后實(shí)際邏輯時(shí)鐘時(shí)間偏差，從而完成一個(gè)時(shí)鐘同步周期；

步驟5更新每個(gè)節(jié)點(diǎn)保存所需的最近若干輪同步偏差數(shù)據(jù)，存儲(chǔ)深度最大為2 048；

步驟6隨后循環(huán)重復(fù)步驟2～步驟4。

3.3 結(jié)果對(duì)比分析

所有同步算法仿真實(shí)驗(yàn)的記錄數(shù)據(jù)均保存在節(jié)點(diǎn)通信列表文件中，在仿真結(jié)束后可由log文件導(dǎo)出得到。由于數(shù)據(jù)規(guī)模較大，所以這里截取所有算法前50輪時(shí)鐘同步過(guò)程中收集記錄的實(shí)驗(yàn)結(jié)果數(shù)據(jù)，如表5所示。

表5 基于LL模型的容錯(cuò)時(shí)鐘同步算法實(shí)驗(yàn)結(jié)果數(shù)據(jù)

采用Grey-FTA容錯(cuò)時(shí)鐘同步算法的同步過(guò)程與其他算法的對(duì)比如圖3所示，橫坐標(biāo)為進(jìn)行時(shí)鐘同步輪次，縱坐標(biāo)表示邏輯時(shí)鐘偏差。

圖3 容錯(cuò)時(shí)鐘同步算法模擬驗(yàn)證實(shí)驗(yàn)數(shù)據(jù)對(duì)比Figure 3. Comparison of simulation and verification experiment data of fault-tolerant clock synchronization algorithm

從圖中可以發(fā)現(xiàn)，與MHE-FTA以及OFE-FTA容錯(cuò)時(shí)鐘同步算法修正過(guò)程相比，Grey-FTA算法的修正過(guò)程更加主動(dòng)積極，其修正效果也更加顯著。此外，通過(guò)對(duì)比整體的時(shí)鐘同步輪次來(lái)看，Grey-FTA算法同步后邏輯時(shí)鐘時(shí)間偏差量最小，同步狀態(tài)最穩(wěn)定，這從結(jié)果上證明了該算法的正確性、有效性。更重要的是本文所得算法的系統(tǒng)時(shí)鐘同步精密度同比提高了24.3%，證明了Grey-FTA算法的優(yōu)越性。

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

本文提出了一種適用于時(shí)間觸發(fā)實(shí)時(shí)系統(tǒng)的預(yù)測(cè)自適應(yīng)Grey-FTA算法，該算法不僅實(shí)現(xiàn)了對(duì)于時(shí)鐘兩面性故障的容錯(cuò)，還解決了時(shí)鐘節(jié)點(diǎn)出現(xiàn)通信鏈路丟失故障不能進(jìn)行時(shí)鐘偏差的校正的問(wèn)題。同時(shí)，該算法不局限于某一個(gè)具體的網(wǎng)絡(luò)通信系統(tǒng)，對(duì)于網(wǎng)絡(luò)的具體結(jié)構(gòu)沒(méi)有進(jìn)行約束，理論上可用于符合本算法基本模型要求的大多數(shù)時(shí)間觸發(fā)式系統(tǒng)或網(wǎng)絡(luò)的內(nèi)部時(shí)鐘同步。但是，本文的灰色預(yù)測(cè)方法存在精度等級(jí)的限制，對(duì)于大量離散不合理的數(shù)據(jù)所預(yù)測(cè)的值參考意義有限，后續(xù)的研究可以將此算法用于更加完善的預(yù)測(cè)模型中。