基于灰色預(yù)測容錯時鐘同步算法

陸 禹，張 力，張鳳登

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

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

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

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

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

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

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

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

1.1 條件假設(shè)

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

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

(1)

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

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

Td∈[δ-ε，δ+ε]

(2)

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

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

n≥3f+1

(3)

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

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

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

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

(4)

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

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

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

(5)

且

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

(6)

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

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

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

L=k×ng

(7)

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

表1 節(jié)點參數(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ù)測

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

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

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

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

(8)

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

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

(9)

式中

(10)

同時生成一階累加生成序列的緊鄰均值生成序列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由最小二乘法計算得出，求解過程為

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

(16)

式中

(17)

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

(18)

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

(19)

2.2 精度校驗

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

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

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

(20)

再計算相對誤差Δ(k)

(21)

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

(22)

(23)

則方差比C為

(24)

小概率誤差P為

(25)

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

表2 GM(1，1)精度檢驗等級

2.3 算法流程

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

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

3 實驗與結(jié)果分析

3.1 實驗參數(shù)設(shè)置

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

表3 實驗參數(shù)假設(shè)常數(shù)值

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

表4 實驗節(jié)點參數(shù)設(shè)置

3.2 實驗步驟

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

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

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

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

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

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

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

3.3 結(jié)果對比分析

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

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

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

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

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

4 結(jié)束語

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