關(guān)博文，朱長(zhǎng)昊，張鳳登

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

0 引言

隨著計(jì)算機(jī)系統(tǒng)以及大規(guī)模集成電路的不斷發(fā)展，分布式系統(tǒng)越來(lái)越多地應(yīng)用在人們的日常生活及工業(yè)生產(chǎn)中［1-2］。分布式系統(tǒng)從網(wǎng)絡(luò)類(lèi)型上可分為時(shí)間觸發(fā)（Time Trigger，TT）系統(tǒng)和事件觸發(fā)（Event Trigger，ET）系統(tǒng)［3］。事件觸發(fā)系統(tǒng)基于事件的發(fā)生觸發(fā)動(dòng)作，時(shí)間觸發(fā)系統(tǒng)基于既定的時(shí)刻表或事件調(diào)度器的調(diào)度，在某個(gè)精確時(shí)刻觸發(fā)動(dòng)作。為保證系統(tǒng)的實(shí)時(shí)性以及應(yīng)對(duì)突發(fā)事件的魯棒性，通常會(huì)同時(shí)采用這兩種結(jié)構(gòu)，如FlexRay 與Ethernet 網(wǎng)絡(luò)等。從時(shí)域上分布式系統(tǒng)又可分為實(shí)時(shí)系統(tǒng)與非實(shí)時(shí)系統(tǒng)，實(shí)時(shí)系統(tǒng)又可進(jìn)一步分為強(qiáng)實(shí)時(shí)系統(tǒng)和弱實(shí)時(shí)系統(tǒng)［4］。本文所研究的是在時(shí)間觸發(fā)分布式實(shí)時(shí)系統(tǒng)環(huán)境下的時(shí)鐘同步算法。

在時(shí)間觸發(fā)分布式實(shí)時(shí)系統(tǒng)中，各個(gè)節(jié)點(diǎn)通常需要大致同時(shí)執(zhí)行某些動(dòng)作。在這樣的系統(tǒng)中，每個(gè)處理器通常都擁有自己的獨(dú)立物理時(shí)鐘，它們相對(duì)于實(shí)時(shí)都具有一定的偏移率［5-6］。即使讓所有節(jié)點(diǎn)的物理時(shí)鐘同時(shí)啟動(dòng)，隨著時(shí)間的推移，這些節(jié)點(diǎn)上的物理時(shí)鐘也會(huì)偏移實(shí)時(shí)時(shí)間。因此，時(shí)鐘必須定期重新同步。在進(jìn)行設(shè)計(jì)時(shí)鐘同步算法時(shí)，不僅要考慮因時(shí)鐘老化等物理因素引起的時(shí)鐘不同步問(wèn)題，還要考慮節(jié)點(diǎn)的時(shí)鐘出現(xiàn)故障或者節(jié)點(diǎn)本身出現(xiàn)故障的問(wèn)題。本文將節(jié)點(diǎn)和鏈路故障進(jìn)行簡(jiǎn)化，統(tǒng)一假設(shè)為節(jié)點(diǎn)的時(shí)鐘故障問(wèn)題［7］。此外，還要容忍系統(tǒng)中的節(jié)點(diǎn)為拜占庭將軍問(wèn)題時(shí)的情況。

過(guò)去研究中最為經(jīng)典的是Lamport 等［8］的交互式算法——CNV 算法和交互式一致性算法——COM、CSM 算法。這兩類(lèi)算法可在任意時(shí)鐘故障情況下工作，其中包括出現(xiàn)時(shí)鐘拜占庭故障。但是CNV 算法要求出現(xiàn)故障的進(jìn)程數(shù)量不能超過(guò)分布式系統(tǒng)總數(shù)量的1/3；COM 和CSM 算法雖然能夠在故障節(jié)點(diǎn)數(shù)量少于總結(jié)點(diǎn)數(shù)一半的情況下保持時(shí)鐘同步，但是需要額外的硬件來(lái)提供消息的數(shù)字簽名。維也納大學(xué)的Kopetz 等［9］分析了CNV 算法并在硬件上測(cè)試了該算法；Ramanathan 等［10］、Shin 等［11］提出一種硬件輔助軟件時(shí)鐘同步的方法，其軟件同步算法部分借鑒了Lamport 的交互式收斂算法，硬件部分主要實(shí)現(xiàn)同步消息的發(fā)送和接收，以及記錄同步信息的本地時(shí)間戳。最終實(shí)驗(yàn)表明，采用這種軟硬件結(jié)合的方法比純軟件同步算法效果更好，精度提高2 個(gè)數(shù)量級(jí)以上，但是增加了經(jīng)濟(jì)上的開(kāi)銷(xiāo)。在大型分布式系統(tǒng)中，其硬件開(kāi)銷(xiāo)會(huì)成倍增長(zhǎng)。

本文提出一種收斂性軟件時(shí)鐘同步算法，該算法不需要額外增加硬件開(kāi)銷(xiāo)，并且它的修正效果相比于容錯(cuò)中值時(shí)鐘同步算法更為明顯。

1 模型設(shè)計(jì)

1.1 時(shí)鐘同步模型建立

在描述本文的容錯(cuò)性?xún)?nèi)部時(shí)鐘同步算法之前，首先建立一個(gè)系統(tǒng)模型，該模型遵循一個(gè)寬泛的通用范例［12］，具體就是讀取遠(yuǎn)程時(shí)鐘技術(shù)。讀取遠(yuǎn)程時(shí)鐘技術(shù)分為兩大類(lèi)：①基于請(qǐng)求回復(fù)機(jī)制的遠(yuǎn)程時(shí)鐘讀取技術(shù)（Remote clock reading，RCR）［13］，其大體步驟如下：進(jìn)程pj估算遠(yuǎn)程進(jìn)程pi的時(shí)鐘，向pi發(fā)送一個(gè)請(qǐng)求消息，并等待一段確定的時(shí)間來(lái)獲取pi的回復(fù)；②基于初始同步的時(shí)鐘檢測(cè)技術(shù)（Time Transmission，TT），每輪重復(fù)執(zhí)行同步算法。節(jié)點(diǎn)在某個(gè)設(shè)定的時(shí)刻發(fā)送包含其時(shí)間信息的消息，而不需要先發(fā)送時(shí)間請(qǐng)求［14］，其代表模型由Lundelius 和Lynch 提出，故通常稱(chēng)為L(zhǎng)L 模型。

由上述文獻(xiàn)可知，基于第一種技術(shù)的模型存在的最大估計(jì)誤差為2D(1+2ρ)-2(δ-ε)，基于第二種技術(shù)的模型最大估計(jì)誤差為2(ε+β+ρδ)，其中D 以pj的發(fā)送與pi回復(fù)這一過(guò)程用時(shí)的一半為值；ρ是時(shí)鐘漂移率；δ是可能的消息延遲范圍中值；ε是消息延遲的不確定度；β是初始時(shí)刻節(jié)點(diǎn)間的同步程度。

由于時(shí)間觸發(fā)分布式實(shí)時(shí)系統(tǒng)是基于時(shí)間觸發(fā)來(lái)發(fā)送節(jié)點(diǎn)的時(shí)間信息，不需要請(qǐng)求回復(fù)，因此相較于第一種模型，LL 模型的通信開(kāi)銷(xiāo)更小。但是相比于第一種模型，因?yàn)楣?jié)點(diǎn)不知道下一條時(shí)間消息將由哪個(gè)節(jié)點(diǎn)發(fā)出，所以增加了讀取誤差。但若在非點(diǎn)對(duì)點(diǎn)網(wǎng)絡(luò)，如廣播式網(wǎng)絡(luò)中就不存在該問(wèn)題。因此，本文采用廣播式通信的LL 模型。LL 模型對(duì)重同步周期TP 及節(jié)點(diǎn)的初始狀態(tài)有一定要求。

1.1.1 基本假設(shè)與前提條件

在建立模型并分析算法前，需要對(duì)模型做相應(yīng)假設(shè)，同時(shí)應(yīng)用相應(yīng)的定理以簡(jiǎn)化算法的性能分析。

令P 表示系統(tǒng)中節(jié)點(diǎn)的集合，由前文可知，其中每一個(gè)節(jié)點(diǎn)pi∈P 都有一個(gè)對(duì)應(yīng)的本地硬件時(shí)鐘，用Hpi表示。該時(shí)鐘通常由一個(gè)晶振和不斷計(jì)數(shù)增加晶振器節(jié)拍的計(jì)數(shù)器組成。雖然時(shí)鐘是離散的，但所有算法都假設(shè)時(shí)鐘連續(xù)運(yùn)行，如Hpi是一段實(shí)時(shí)間隔的連續(xù)函數(shù)。此外，雖然硬件時(shí)鐘由于溫度改變和老化會(huì)偏離真實(shí)時(shí)鐘，但通常假設(shè)其與真實(shí)時(shí)間的偏移量在一個(gè)很小的范圍內(nèi)，因此本文做如下假設(shè)：

假設(shè)1 本地硬件時(shí)鐘漂移率假設(shè)：存在一個(gè)極小的常數(shù)ρ >0，定義對(duì)任意時(shí)刻t，所有硬件時(shí)鐘Hpi(t)與ρ的關(guān)系如下：

其中，Hpi(t)表示處理器pi 在真實(shí)時(shí)間t時(shí)的本地硬件時(shí)鐘值，ρ稱(chēng)為硬件時(shí)鐘的漂移率。該假設(shè)表示任一節(jié)點(diǎn)的本地硬件時(shí)鐘與真實(shí)時(shí)間的偏差存在一個(gè)極小范圍，其上限是ρ，即硬件時(shí)鐘的漂移率存在一個(gè)合理范圍，若超過(guò)該范圍，可能沒(méi)有算法能夠?qū)r(shí)鐘同步回來(lái)。

假設(shè)2 通信鏈路全鏈接：節(jié)點(diǎn)間通過(guò)廣播的方式進(jìn)行通信，且任一節(jié)點(diǎn)pi∈P 在網(wǎng)絡(luò)中發(fā)送的消息最終都能到達(dá)其目的節(jié)點(diǎn)，即模型不存在鏈路丟失故障。

在分布式系統(tǒng)中，根據(jù)不同的網(wǎng)絡(luò)類(lèi)型以及對(duì)網(wǎng)絡(luò)負(fù)載所作的假設(shè)，消息延遲可能或多或少是可預(yù)測(cè)的［15］。本文假定存在的傳輸（如發(fā)送、傳播、接收）延遲的上下限已知。

假設(shè)3 傳輸延遲有界：通過(guò)任何鏈接發(fā)送、傳輸與接收任何消息與真實(shí)時(shí)間的通信延遲Td存在一個(gè)已知的邊界。即：

其中：δ為消息可能延遲范圍的中值，ε為消息延遲的不確定度。當(dāng)上述假設(shè)成立時(shí)，時(shí)鐘同步算法保證了所有正確的邏輯時(shí)鐘間的最大差值在一個(gè)范圍內(nèi)，即精密度γ。這也是確定性算法的顯著特征——通過(guò)對(duì)通信延遲的上下限做出假設(shè)來(lái)得到一個(gè)定量的精密度值。

假設(shè)4 故障節(jié)點(diǎn)數(shù)有限：時(shí)鐘同步算法執(zhí)行過(guò)程中最多存在n個(gè)故障節(jié)點(diǎn)，其中n是一個(gè)正整數(shù)。由文獻(xiàn)［16］可知，當(dāng)系統(tǒng)中故障節(jié)點(diǎn)數(shù)超過(guò)總節(jié)點(diǎn)數(shù)的1/3 時(shí)，在不使用外部數(shù)字簽名的技術(shù)下，將無(wú)法維持時(shí)鐘同步。因此，對(duì)假設(shè)4 進(jìn)一步假設(shè)：系統(tǒng)由m個(gè)節(jié)點(diǎn)組成，其中的故障節(jié)點(diǎn)數(shù)為n，它們的關(guān)系是：

假設(shè)5 算法執(zhí)行時(shí)間：消息延遲除了假設(shè)3 中所提的傳輸延遲外，還存在一系列延遲，如任一節(jié)點(diǎn)pi∈P在網(wǎng)絡(luò)中發(fā)送的消息前生成消息所需時(shí)間，接收消息后解析消息所需的時(shí)間，以及執(zhí)行同步算法所需的時(shí)間。本文假設(shè)這些時(shí)間都可忽略。通常情況下，造成消息延遲的主要原因是傳輸延遲，而上述的延遲都與節(jié)點(diǎn)的處理器有關(guān)，簡(jiǎn)化起見(jiàn)，將忽略這些延遲。

假設(shè)6 初始同步：設(shè)T0表示節(jié)點(diǎn)時(shí)鐘時(shí)間的初始時(shí)刻表示p節(jié)點(diǎn)在初始時(shí)刻的真實(shí)時(shí)間，那么系統(tǒng)中的非故障節(jié)點(diǎn)在一開(kāi)始時(shí)是同步在某個(gè)固定先驗(yàn)范圍內(nèi)的。即：

其中為一個(gè)定值，p和q為非故障進(jìn)程。

假設(shè)7 同步周期限制條件：為了使同步中非故障節(jié)點(diǎn)p發(fā)送消息時(shí)其余的非故障節(jié)點(diǎn)q都與p處于同一輪次，重同步周期TP要滿(mǎn)足以下條件：

其中，ρ為時(shí)鐘漂移率；δ為可能的消息延遲范圍中值，ε為消息延遲的不確定度。β為一先驗(yàn)常數(shù)，表示初始同步程度的上限。

假設(shè)8 初始化同步程度限制條件：

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

1.1.2 模型描述

如上述假設(shè)及條件所述，系統(tǒng)內(nèi)節(jié)點(diǎn)全鏈接，即可以通過(guò)廣播的方式發(fā)送消息。算法將在一系列輪次中進(jìn)行，也就是說(shuō)，將邏輯時(shí)鐘以輪次的形式表示。每輪的時(shí)間長(zhǎng)度恒定，用L表示，由k個(gè)宏時(shí)隙組成，其中k＞0。即：

因?yàn)槊恳惠喍歼M(jìn)行一次時(shí)鐘同步，因此其長(zhǎng)度也要滿(mǎn)足上述重同步周期條件。每輪要留出固定長(zhǎng)度的時(shí)間作為修正段，通常稱(chēng)為NIT 段。在NIT 段內(nèi)節(jié)點(diǎn)執(zhí)行邏輯時(shí)間狀態(tài)修正與速率修正，因此在該時(shí)間段內(nèi)通常不執(zhí)行任何事件。以4 個(gè)節(jié)點(diǎn)在理想狀態(tài)（即完全同步）下為例說(shuō)明第i輪結(jié)構(gòu)，節(jié)點(diǎn)的相關(guān)參數(shù)如表1 所示。

系統(tǒng)包含一類(lèi)特殊消息：同步消息Mp，其中p為系統(tǒng)內(nèi)任一節(jié)點(diǎn)。因?yàn)椴捎昧松衔乃龅南鬏敿夹g(shù)（TT），因此系統(tǒng)的時(shí)鐘同步通過(guò)時(shí)間觸發(fā)的方式進(jìn)行。在輪次i中，i≥0i，每個(gè)節(jié)點(diǎn)都存在一個(gè)互不相同的同步時(shí)刻。當(dāng)本地硬件時(shí)鐘達(dá)到時(shí)就發(fā)送同步消息Mp，節(jié)點(diǎn)q一旦收到Mp就記下本地時(shí)鐘觀測(cè)的該時(shí)刻

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

根據(jù)表1，各節(jié)點(diǎn)第i輪情況如圖1 所示。其中mtj表示節(jié)點(diǎn)第j次宏節(jié)拍，也就是相應(yīng)邏輯時(shí)鐘的第j個(gè)節(jié)拍。TNIT表示系統(tǒng)進(jìn)入NIT 段時(shí)的時(shí)鐘時(shí)刻。系統(tǒng)內(nèi)各節(jié)點(diǎn)的同步時(shí)刻都是可知的，即根據(jù)不同的網(wǎng)絡(luò)和應(yīng)用需求通過(guò)離線設(shè)定所得。由可得出在第i輪同步中，節(jié)點(diǎn)q觀測(cè)的p與q的本地時(shí)鐘狀態(tài)差，而根據(jù)便可得出節(jié)點(diǎn)q觀測(cè)的p與q的速率差。在得出與各節(jié)點(diǎn)的狀態(tài)與速率差后，即可應(yīng)用收斂算法得出修正值，并在NIT 段應(yīng)用該修正值，完成修正。

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

值得注意的是，該結(jié)構(gòu)與FlexRay 十分相似，其原因是FlexRay 同樣也是基于LL 模型，所以準(zhǔn)確來(lái)說(shuō)，基于LL 模型的協(xié)議都具有相似的結(jié)構(gòu)。同時(shí)，F(xiàn)lexRay 分為動(dòng)態(tài)段與靜態(tài)段。在靜態(tài)段內(nèi)，節(jié)點(diǎn)只能在相應(yīng)的時(shí)隙內(nèi)發(fā)送消息，而本模型則不存在該規(guī)則，節(jié)點(diǎn)可以在任何時(shí)刻發(fā)送同步消息。此外，關(guān)于為何要將邏輯時(shí)間分為輪次的形式也是一個(gè)值得探討的問(wèn)題。究其原因，主要是為了與外部時(shí)基進(jìn)行統(tǒng)一，換言之，系統(tǒng)總是為用戶(hù)服務(wù)的。而分輪次類(lèi)似于日常生活中將時(shí)間分為年、月、日、分、秒的做法，便于用戶(hù)的時(shí)間與系統(tǒng)的時(shí)間相對(duì)應(yīng)。其次，輪次的結(jié)構(gòu)也便于進(jìn)行節(jié)點(diǎn)間的周期測(cè)量，使得節(jié)點(diǎn)可以獲得與其它節(jié)點(diǎn)的速率差，從而進(jìn)行速率修正。

1.2 容錯(cuò)性最值算法

1.2.1 算法提出

基于LL 模型的容錯(cuò)最值算法思路與LL 模型原始的容錯(cuò)均值算法類(lèi)似，不同之處在于容錯(cuò)最值算法能夠更快完成收斂，使得時(shí)鐘間能夠更快達(dá)成一致。相應(yīng)地，其代價(jià)是實(shí)現(xiàn)的最壞情況下精密度略低于容錯(cuò)中值算法。

如上文所述，利用收斂函數(shù)計(jì)算修正項(xiàng)進(jìn)行容錯(cuò)時(shí)鐘同步的算法，其容錯(cuò)性的保證實(shí)質(zhì)上在于對(duì)修正值的限制。不論是容錯(cuò)中值算法直觀地對(duì)修正項(xiàng)大小進(jìn)行限制，還是容錯(cuò)均值算法隱性地在計(jì)算過(guò)程內(nèi)部進(jìn)行限制，都是如此。同樣，容錯(cuò)最值采用與容錯(cuò)中值算法類(lèi)似的對(duì)修正值大小進(jìn)行隱性限制，以保證算法的容錯(cuò)性，即在故障節(jié)點(diǎn)不超過(guò)總節(jié)點(diǎn)數(shù)1/3 的情況下，使得非故障節(jié)點(diǎn)的時(shí)鐘仍維持在某個(gè)精密度下的同步。

1.2.2 算法過(guò)程

下面以偽代碼的形式描述第i輪同步中節(jié)點(diǎn)q的容錯(cuò)最值時(shí)鐘同步算法過(guò)程。

（1）函數(shù)及符號(hào)定義（見(jiàn)表2）。

Table 2 Pseudocode parameter表2 偽代碼參數(shù)

（2）算法描述。

算法：容錯(cuò)最值算法

輸入：重同步時(shí)間

輸出：修正后的節(jié)點(diǎn)時(shí)鐘值

綜上，通過(guò)舍棄掉q節(jié)點(diǎn)與其它節(jié)點(diǎn)時(shí)鐘差值的f個(gè)最大值與f個(gè)最小值，將余下值中的最大值作為修正值，然后通過(guò)修正，實(shí)現(xiàn)容錯(cuò)性?xún)?nèi)部時(shí)鐘同步。容錯(cuò)最值算法比容錯(cuò)均值算法少了一個(gè)排序的過(guò)程，在節(jié)點(diǎn)數(shù)目較多的情況下可以有效節(jié)省計(jì)算時(shí)間。同時(shí)，其收斂速度將快于容錯(cuò)均值算法與容錯(cuò)中值算法，這是該算法的顯著特點(diǎn)，但其代價(jià)是精密度降低。相對(duì)而言，本同步算提供了一種新的思路，在不同場(chǎng)景下使得分布式系統(tǒng)的設(shè)計(jì)者能夠多一種選擇。

2 實(shí)驗(yàn)驗(yàn)證

2.1 仿真系統(tǒng)構(gòu)成

對(duì)基于LL 模型的容錯(cuò)中值時(shí)鐘同步算法及容錯(cuò)最值時(shí)鐘同步算法進(jìn)行仿真實(shí)驗(yàn)，采用專(zhuān)業(yè)的現(xiàn)場(chǎng)總線仿真測(cè)試工具CANoe 軟件進(jìn)行仿真測(cè)試，從實(shí)驗(yàn)的角度驗(yàn)證算法理論的正確性。將4 個(gè)節(jié)點(diǎn)構(gòu)成一個(gè)總線型網(wǎng)絡(luò)，網(wǎng)絡(luò)中各節(jié)點(diǎn)通過(guò)廣播方式進(jìn)行通信。節(jié)點(diǎn)1、2、4 為正常節(jié)點(diǎn)，節(jié)點(diǎn)3 為拜占庭故障節(jié)點(diǎn)，即兩面性時(shí)鐘節(jié)點(diǎn)，其網(wǎng)絡(luò)結(jié)構(gòu)如圖2 所示。

Fig.2 Simulation system network structure圖2 仿真系統(tǒng)網(wǎng)絡(luò)結(jié)構(gòu)

實(shí)驗(yàn)中一共有7 條消息，其中4 條是算法相應(yīng)節(jié)點(diǎn)必須發(fā)送的同步消息，余下3 條消息用于軟件觀測(cè)同步后節(jié)點(diǎn)時(shí)間差，并非算法所需。同時(shí)建立相應(yīng)的環(huán)境變量來(lái)表示定時(shí)器模擬的節(jié)點(diǎn)邏輯時(shí)鐘。算法相應(yīng)的發(fā)送接收關(guān)系及消息ID 等關(guān)系定義見(jiàn)表3。

2.2 仿真系統(tǒng)參數(shù)

在搭建好實(shí)驗(yàn)系統(tǒng)網(wǎng)絡(luò)框架后，需要確定具體參數(shù)。根據(jù)之前的研究成果［17-18］及LL 模型的基本約束條件，確定部分系統(tǒng)參數(shù)如下：系統(tǒng)容忍的最大漂移率ρ=10-4s，系統(tǒng)內(nèi)傳輸延遲最大為10×10-6s，最小延遲為5×10-6s，即系統(tǒng)的消息延遲在μs 內(nèi)［19］。系統(tǒng)內(nèi)消息延遲不確定度ε=2.5×10-6s，消息延遲范圍的中值δ=7.5×10-6s。根據(jù)LL 模型初始同步的基本約束條件式（3），忽略量級(jí)過(guò)小的參數(shù)，在上述條件下系統(tǒng)內(nèi)初始同步程度βs，因此設(shè)系統(tǒng)內(nèi)初始同步程度β=12×10-6s。再根據(jù)LL 模型同步周期的約束條件式（5）及式（6），忽略量級(jí)過(guò)小的參數(shù)，得出系統(tǒng)同步周期TP 的下限量級(jí)微秒級(jí)，而上限為T(mén)Ps，即5ms。設(shè)系統(tǒng)內(nèi)每輪同步長(zhǎng)度即同步周期TP=0.22ms=220μs，參數(shù)如表4 所示。

Table 3 Algorithm and message description表3 算法及報(bào)文說(shuō)明

Table 4 System parameter表4 系統(tǒng)參數(shù)

根據(jù)文獻(xiàn)［20］及前述結(jié)論，將表4 中的參數(shù)代入精密度計(jì)算公式，可得在上述配置下基于LL 模型的容錯(cuò)中值時(shí)鐘同步算法的精密度為：0.014 512 4ms，即14.512 4μs；本文提出的容錯(cuò)最值時(shí)鐘同步算法精密度為0.020 512 4ms，即20.512 4μs。同時(shí)根據(jù)表4 得節(jié)點(diǎn)間的具體參數(shù)配置如表5 所示。

Table 5 Node parameter configuration表5 節(jié)點(diǎn)參數(shù)配置

2.3 基于LL 模型的容錯(cuò)中值算法（FTM）仿真結(jié)果

根據(jù)上述配置搭建系統(tǒng)并運(yùn)行，使e1、e2、e3、e4 表示節(jié)點(diǎn)1 計(jì)算的與相應(yīng)節(jié)點(diǎn)的邏輯時(shí)鐘差值，而mid為據(jù)此得出的中值，Mtick為修正后的單位宏時(shí)隙長(zhǎng)度，其中節(jié)點(diǎn)3為拜占庭故障節(jié)點(diǎn)，故e3 的值為隨機(jī)值。e12、e13、e14 分別為修正后節(jié)點(diǎn)1 與相應(yīng)節(jié)點(diǎn)的邏輯時(shí)間差值。而上一輪修正后的理論差值e12、e13、e14 不一定等于本輪測(cè)量的實(shí)際時(shí)鐘差值e2、e3、e4，其原因在于通信延遲的存在。具體修正過(guò)程如圖3 所示。

Fig.3 Fault-Tolerant Median（FTM）algorithm correction process圖3 容錯(cuò)中值算法（FTM）修正過(guò)程

詳細(xì)結(jié)果如圖4（彩圖掃OSID 碼可見(jiàn)，下同）所示，其中兩條紅線分別為以微秒和邏輯時(shí)鐘個(gè)數(shù)為單位表示的FTM 容錯(cuò)中值算法理論精密度。

Fig.4 Fault-Tolerant Median（FTM）algorithm result圖4 容錯(cuò)中值算法（FTM）結(jié)果

藍(lán)色三角實(shí)線表示仿真實(shí)驗(yàn)過(guò)程中，每輪同步節(jié)點(diǎn)1與其它節(jié)點(diǎn)邏輯時(shí)鐘差值的最大值，單位為微秒；黑色三角虛線表示理論邏輯時(shí)鐘差值最大值與實(shí)驗(yàn)邏輯時(shí)鐘差值最大值的殘差，單位是微秒；藍(lán)色圓點(diǎn)實(shí)線表示仿真實(shí)驗(yàn)過(guò)程中每輪同步節(jié)點(diǎn)1 與其它節(jié)點(diǎn)邏輯時(shí)鐘差值的最大值，單位為邏輯時(shí)鐘的個(gè)數(shù)；黑色圓點(diǎn)虛線表示理論邏輯時(shí)鐘差值最大值與實(shí)驗(yàn)邏輯時(shí)鐘差值最大值的殘差，單位為邏輯時(shí)鐘的個(gè)數(shù)。

2.4 基于LL 模型的容錯(cuò)最值算法仿真結(jié)果

同理，根前述配置搭建系統(tǒng)并運(yùn)行，在注入容錯(cuò)最值時(shí)鐘同步算法到系統(tǒng)中之后，系統(tǒng)節(jié)點(diǎn)的邏輯時(shí)鐘在任一時(shí)間段內(nèi)的修正過(guò)程如圖5 所示。

Fig.5 Fault-tolerant maximum value clock synchronization algorithm correction process圖5 容錯(cuò)最值時(shí)鐘同步算法修正過(guò)程

其中e1、e2、e3、e4 表示節(jié)點(diǎn)1 計(jì)算的與相應(yīng)節(jié)點(diǎn)的邏輯時(shí)鐘差值，而Maxv 為據(jù)此得出的最大值，Mtick為修正后的單位宏時(shí)隙長(zhǎng)度，其中節(jié)點(diǎn)3 為拜占庭故障節(jié)點(diǎn)，故e3 的值為隨機(jī)值。e12、e13、e14 分別為修正后節(jié)點(diǎn)1 與相應(yīng)節(jié)點(diǎn)的邏輯時(shí)間差值。而上一輪修正后理論上的差值e12、e13、e14 不一定等于本輪測(cè)量的實(shí)際時(shí)鐘差值e2、e3、e4，原因在于通信延遲的存在。

詳細(xì)結(jié)果如圖6 所示，其中兩條紅線分別為以微秒和邏輯時(shí)鐘個(gè)數(shù)為單位表示的FTM 容錯(cuò)中值算法理論精密度。藍(lán)色三角實(shí)線表示仿真實(shí)驗(yàn)過(guò)程中每輪同步節(jié)點(diǎn)1 與其它節(jié)點(diǎn)邏輯時(shí)鐘差值的最大值，單位為微秒；黑色三角虛線表示理論邏輯時(shí)鐘差值最大值與實(shí)驗(yàn)邏輯時(shí)鐘差值最大值的殘差，單位是微秒；藍(lán)色圓點(diǎn)實(shí)線表示仿真實(shí)驗(yàn)過(guò)程中，每輪同步節(jié)點(diǎn)1 與其它節(jié)點(diǎn)邏輯時(shí)鐘差值的最大值，單位為邏輯時(shí)鐘的個(gè)數(shù)；黑色圓點(diǎn)虛線表示理論邏輯時(shí)鐘差值最大值與實(shí)驗(yàn)差值最大值的殘差，單位為邏輯時(shí)鐘的個(gè)數(shù)。

2.5 仿真結(jié)果分析

（1）根據(jù)容錯(cuò)中值時(shí)鐘同步算法的結(jié)果圖可知，本實(shí)驗(yàn)所搭建的系統(tǒng)模型滿(mǎn)足LL 模型的基本條件，其實(shí)驗(yàn)結(jié)果完全符合理論結(jié)論。容錯(cuò)中值時(shí)鐘同步算法的結(jié)果圖符合本文提出的容錯(cuò)最值時(shí)鐘同步算法理論結(jié)果，從實(shí)驗(yàn)上證明了本算法的有效性與正確性。

（2）根據(jù)容錯(cuò)中值時(shí)鐘同步算法（FTM）修正過(guò)程圖與容錯(cuò)最值時(shí)鐘同步算法修正過(guò)程圖可知，容錯(cuò)最值時(shí)鐘同步算法的修正過(guò)程相比容錯(cuò)中值時(shí)鐘同步算法更為激進(jìn)，其修正效果更為明顯。同時(shí)根據(jù)結(jié)果圖可知其后果就是精密度的下降。

Fig.6 Fault-tolerant maximum value clock synchronization algorithm results圖6 容錯(cuò)最值時(shí)鐘同步算法結(jié)果

（3）根據(jù)實(shí)驗(yàn)數(shù)據(jù)分析發(fā)現(xiàn)本文的實(shí)驗(yàn)數(shù)據(jù)均為整數(shù)，究其原因是因?yàn)楸疚膶?shí)驗(yàn)計(jì)算的結(jié)果以邏輯時(shí)鐘為單位來(lái)表示，因此其最小粒度就是單位邏輯時(shí)鐘長(zhǎng)度，初始設(shè)為4μs。而邏輯時(shí)鐘則是用軟件的定時(shí)器進(jìn)行模擬，而軟件定時(shí)器用到的最小粒度同樣是整數(shù)。由于同一實(shí)時(shí)時(shí)刻不同節(jié)點(diǎn)間的時(shí)間差就是單位邏輯時(shí)鐘長(zhǎng)度乘以邏輯時(shí)間差值，而單位邏輯時(shí)間長(zhǎng)度與邏輯時(shí)間差都為整數(shù)，因此差值也以整數(shù)的形式呈現(xiàn)。如果從絕對(duì)的完美和嚴(yán)謹(jǐn)出發(fā)，由于仿真工具及仿真限制的原因，實(shí)驗(yàn)數(shù)據(jù)結(jié)果相當(dāng)于省去了小數(shù)部分，因此并不完全精確。但即便對(duì)數(shù)據(jù)進(jìn)行向上取整處理，結(jié)果仍表明系統(tǒng)中非故障節(jié)點(diǎn)的邏輯時(shí)鐘差值最大值低于理論精密度，因此該數(shù)據(jù)仍能證明本算法及觀點(diǎn)的正確性，并不影響得出的結(jié)論。

3 結(jié)語(yǔ)

本文針對(duì)時(shí)間觸發(fā)分布式系統(tǒng)中的時(shí)鐘同步問(wèn)題，提出了容錯(cuò)最值算法?；趯?zhuān)業(yè)的現(xiàn)場(chǎng)總線仿真測(cè)試工具CANoe 軟件進(jìn)行仿真測(cè)試，結(jié)果表明，容錯(cuò)最值算法能有效地同步系統(tǒng)中的故障節(jié)點(diǎn)，包括惡劣情況下的拜占庭故障。通過(guò)對(duì)既往的FTM 算法和本文的容錯(cuò)最值算法比較可以看出，容錯(cuò)最值算法的修正效果更為明顯，但代價(jià)是同步后的精確度有所下降。本文提供了一種新的思路，使在不同場(chǎng)景下進(jìn)行分布式系統(tǒng)的設(shè)計(jì)者能夠多一種選擇。