張宇輝，張鳳登，張海濤

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

RTEthernet(Real-Time Ethernet)是新提出的一種實時以太網(wǎng)，該網(wǎng)絡能夠兼容傳統(tǒng)以太網(wǎng)的實時以太網(wǎng)協(xié)議，主要應用于工業(yè)、車載以太網(wǎng)技術應用。這種實時以太網(wǎng)采用總線拓撲結構，在傳統(tǒng)的物理層和數(shù)據(jù)鏈路層之上增加了會話層，并使用 “通信循環(huán)”的概念分時傳輸實時性消息和非實時性消息。

對于時鐘同步技術的研究，國外在該領域的起步較早。1978年，文獻[1]較為全面地闡述了時鐘同步技術的原理、方法以及時鐘同步在分布式系統(tǒng)中的應用。文獻[2]以經(jīng)典的Lamport時鐘同步算法為基礎研究了平均值算法和Berkeley算法，且這兩種類型算法的核心都是平均技術。文獻[3]針對確定全網(wǎng)時鐘的問題提出了一種基于平均場的分布式時鐘同步方法，該算法將節(jié)點間的時鐘偏差映射為團勢能，然后使用能量函數(shù)來描述時鐘同步平均場模型。該方法中，時鐘同步的核心思想仍基于平均場理論，通過節(jié)點間的平均作用來確定全網(wǎng)虛擬時鐘基準。目前多數(shù)關于分布式時鐘同步算法的研究都是針對某一網(wǎng)絡進行適應性改進。基于此，本文通過對RTEthernet協(xié)議通信原理及其基礎時鐘同步算法的研究，考慮最惡劣的拜占庭故障對系統(tǒng)時鐘精密度的影響，分析時鐘同步的條件和經(jīng)典時鐘同步算法，即容錯均值(Fault-Tolerant Average，F(xiàn)TA)算法，逐步提出容錯性更高的時鐘同步算法。

1 RTEthernet基本原理

RTEthernet是一種實時以太網(wǎng)，它保留了傳統(tǒng)Ethernet的物理層和數(shù)據(jù)鏈路層工作模型，并在此基礎上使用了ISO/OSI參考模型的第5層(會話層)進行報文的再封裝。RTEthernet網(wǎng)絡還引入了“全局時間”的概念，這使得其不僅可以兼容傳統(tǒng)以太網(wǎng)，還可以使用時分多路訪問(Time Division Multiple Access，TDMA)的通信方式進行基礎報文的傳輸，從而克服了傳統(tǒng)以太網(wǎng)在負載較高時延遲較大的影響，提高了傳統(tǒng)以太網(wǎng)的實時性和安全性。

1.1 體系結構

國際標準化組織(International Organization for Standardization，ISO)制訂的開放式系統(tǒng)互連(Open System Interconnection，OSI)參考模型共分7層，從低到高依次為物理層、數(shù)據(jù)鏈路層、網(wǎng)絡層、傳輸層、會話層、表示層和應用層[4-5]，如圖1所示。

由圖1可以看出，以太網(wǎng)只定義了ISO/OSI體系結構中的最低兩層，這主要是因為物理層是用來建立實時傳輸網(wǎng)絡中的物理連接，而數(shù)據(jù)鏈路層是用來將數(shù)據(jù)封裝成幀進行傳輸，以此實現(xiàn)真的順序控制、差錯控制以及流控制等功能，使得不可靠的鏈路變成可靠的鏈路，這兩者都是必不可少的部分。然而，RTEthernet要做的是在這兩層的基礎上添加一個協(xié)議層，且不改變Ethernet的物理層和數(shù)據(jù)鏈路層。為此，該協(xié)議修改了OSI/ISO參考模型的會話層。

圖1 ISO/OSI、Ethernet和RTEthernet的體系結構Figure 1. Architecture for ISO/OSI、Ethernet and RTEthernet

1.2 工作原理

RTEthernet協(xié)議是以確定性定時通信為基礎，其通信方法是基于周期性重復的通信循環(huán)，因此需要提前建立通信循環(huán)和時間窗口的大小。如圖2所示，本文類比矩陣行和列的方式，將RTEthernet的整體情況進行展示。圖中的矩陣從宏觀上展現(xiàn)了RTEthernet的一般性工作原理。

圖2形象地展示了RTEthernet的通信原理，其中每個通信循環(huán)中包含了靜態(tài)段、動態(tài)段和網(wǎng)絡空閑時間段。在實際實現(xiàn)中，循環(huán)的個數(shù)是一個常數(shù)，具體會根據(jù)實際應用的需求進行設定。在基本的通信循環(huán)中用于報文傳輸?shù)臅r間只在動態(tài)段和靜態(tài)段，并且所有要通過該網(wǎng)絡進行傳輸?shù)膱笪亩紩唤M織成靜態(tài)段或者動態(tài)段的元素。在靜態(tài)段中進行傳輸?shù)膱笪亩际侵芷谛缘?、具有實時性的報文，其元素所處的位置都是固定的，而動態(tài)段傳輸?shù)氖请S機的、事件觸發(fā)型報文，其中的元素位置是不固定的。因此，這種通信模式定義了時間窗口與使用該網(wǎng)絡進行傳輸?shù)膱笪牡南嚓P性。

圖2 RTEthernet通信原理Figure 2. RTEthernet communication principles

2 時鐘同步

分布式系統(tǒng)[6]由一組處理器組成，它們通過消息交換進行通信，并且不能訪問全局時鐘。盡管如此，越來越多的分布式應用程序，例如過程控制應用程序、事務處理應用程序或通信協(xié)議，都要求同步時鐘能夠擁有近似相同的時間視圖。在此上下文中，時間意味著實際時間的近似值或簡單的整數(shù)值計數(shù)器。確保物理上分散的處理器有共同的時間知識的算法被稱為時鐘同步算法。

2.1 誤差來源及時鐘故障分類

由于分布式系統(tǒng)中的各個節(jié)點對于時間的看法各不相同，因此需要對其進行時鐘同步。造成這一現(xiàn)象的主要因素是溫度和老化，這使得各個節(jié)點的硬件時鐘的晶振頻率發(fā)生漂移。在實際應用中，漂移率的量級通常在10-6s[7]。

在分布式系統(tǒng)中，節(jié)點的故障可以定義為不符合正常行為的表現(xiàn)。節(jié)點中的所有組件，例如處理器、時鐘、通信的鏈路等都可能出現(xiàn)故障。對于各個節(jié)點的時鐘而言，與其相關的故障主要分為7類[8]：其中最著名的是時鐘拜占庭故障[9](Clock Byzantine Failure)。

在分布式系統(tǒng)中，任意節(jié)點都可能會存在上述類型的某一種故障或幾種故障混合，在這種情況下則稱該節(jié)點是故障的，否則是無故障的。同時，在本文主要考慮的就是最惡劣情況(拜占庭故障，如圖3所示)下的兩種情況。如果一個時鐘同步算法能夠使得分布式系統(tǒng)能夠容忍上述最惡劣情況下的故障，則表明該算法是有效的。因此，時鐘同步算法容錯性的重點就體現(xiàn)在系統(tǒng)對拜占庭故障節(jié)點的容忍性上。

圖3 時鐘拜占庭故障Figure 3. The clock Byzantine failure

2.2 時鐘同步的基本表征

為了能夠有效衡量系統(tǒng)中各個時鐘是否達到同步，本文引入了如下衡量指標：時鐘偏差Δ(Offset)、精密度φ(Precision)和準確度ψ(Accuracy)。

偏差Δ為具有相同粒度的兩個時鐘在同一單位微節(jié)拍上的偏差，可用下式表示

(1)

精密度φ為在給定的真實時間間隔[t1，t2]內(nèi)，時鐘集合{1，2，3，…，n}上任意兩個時鐘間的最大偏差，可用下式表示

(2)

式中，i表示微節(jié)拍；a、b表示時鐘編號。一般情況下，有限時間間隔上的最大φi稱為時鐘集合的精密度。衡量一個系統(tǒng)內(nèi)所有節(jié)點間的時鐘是否達到同步就是根據(jù)精密度來判斷的。若精密度小于某個期望值，則表示系統(tǒng)內(nèi)部的各節(jié)點之間相互同步，反之，則未達到同步。

準確度ψ為任意時鐘a相對于參考時鐘r在微節(jié)拍i的偏差，用ψia表示

(3)

此外，時鐘同步算法從不同的角度可以分為不同的類型，從宏觀上可以將時鐘同步算法分為外部時鐘同步算法與內(nèi)部時鐘同步算法[10-12]；從同步時使用的工具角度上可以將時鐘同步算法分為硬件時鐘同步算法與軟件時鐘同步算[13-15]；從容錯性的角度，又可以將時鐘同步算法分為容錯性算法和非容錯性算法。

3 算法模型

3.1 系統(tǒng)模型假設

假設1(時鐘偏移率有界) 存在一個很小的已知常數(shù)ρ，其中0<ρ?1，本文定義一個無故障時鐘Hi(t)在所有的真實時間t上都是ρ有界的，即該時鐘滿足如下特性

(4)

其中，Hk(t)表示節(jié)點k的本地時鐘值；ρ表示本地硬件時鐘的漂移率。

假設2(時鐘初始同步) 設分布式實時系統(tǒng)在真實時間t0時刻開始啟動，邏輯時鐘初始是同步的，即對于某個固定值φint和系統(tǒng)內(nèi)任意兩個無故障節(jié)點p、q在t0時刻滿足下式

|Cpt0)-Cqt0)|≤φint

(5)

式中，Cp(t0)、Cq(t0)分別表示時鐘p、q在真實時間t0時刻的時鐘值；φint表示無故障節(jié)點初始同步時兩者之間的最大偏差。

假設3(故障節(jié)點數(shù)有界) 由文獻[16]可知，當系統(tǒng)中故障節(jié)點數(shù)超過總節(jié)點數(shù)的1/3時，在不使用簽名認證的技術下，將無法維持時鐘同步。因此，假設參與時鐘同步的節(jié)點總數(shù)為n，可能發(fā)生故障的最大節(jié)點數(shù)為f，則n和f滿足式(6)。

n≥3f+1

(6)

RTEthernet定義了一個確定性的多主網(wǎng)絡。為了使它的傳輸速率盡可能地靠近以太網(wǎng)，將RTEthernet系統(tǒng)的基本結構定義為星型拓撲結構。

當進行遠程時鐘讀取和計算時，除故障的情況之外，還會有時間上的延遲。為了方便對下文時鐘同步算法的描述和分析，本文對系統(tǒng)模型做如下假設。

假設4(傳輸延遲有界) 對于某些非負常數(shù)δ和ε，且δ>ε，每條報文的發(fā)送和接收對應真實時間的差值de存在一個已知的上下界，即

de∈[δ-ε，δ+ε]

(7)

式中，δ表示報文傳輸延遲范圍的中值；ε表示讀取其他節(jié)點時鐘值時的讀取誤差。

除了假設傳輸延遲有界外，延遲的長短還與其他因素相關，例如任意一個節(jié)點Ni在分布式系統(tǒng)中接收到報文進行處理、運行算法所需的時間等。

假設5(算法執(zhí)行時間) 本文假設這些時間都可忽略。在實際情況中，造成消息延遲的主要原因是傳輸延遲，而執(zhí)行算法、處理報文等產(chǎn)生的延遲都遠小于傳輸延遲，為簡化起見，將忽略這些延遲。

假設6(重同步周期) 為了保證時鐘同步，非故障節(jié)點p發(fā)送消息時，其余非故障節(jié)點q都與p處于同一輪次，因此要求重同步周期λ滿足下列條件

λ>21+ρ)φint+ε)+1+ρ)max{δ，φint+ε}+ρδ

(8)

且

λ≤φint/4ρ-ε/ρ-ρφint+δ+ε)-2φint-δ-2ε

(9)

式中，δ為可能的消息延遲范圍的中值；ε為消息延遲的不確定度；φint為常數(shù)，表示初始同步程度的上限。

3.2 時鐘同步條件

根據(jù)章節(jié)3.1給出的系統(tǒng)模型，時鐘同步算法需滿足一定的同步判斷條件才能證明算法的收斂性和有效性。

對于所有正確時鐘Ci和Cj，如果在時間Ti+1之前，所有時鐘中除了最多m個時鐘之外都沒有故障，那么時鐘同步算法需滿足以下時鐘同步要求：

(1)R1(收斂性/精密度)。|Ci(t)-Cj(t)|≤φi，其中φi表示時鐘同步算法的精密度；

(2)R2(校正項有界)。每次重新同步時，一個無故障時鐘被改變的大小在數(shù)量上有一個小的限制。

4 FTA算法的分析及改進

目前國內(nèi)外出現(xiàn)了較多的分布式實時系統(tǒng)時鐘同步算法，其中容錯均值(Fault-Tolerant Average，F(xiàn)TA)算法是一種最典型的時鐘同步算法。

FTA算法是一種單輪算法，能夠處理不一致信息，限制由不一致性引入的錯誤。該算法起源于傳統(tǒng)的“平均技術”，引入去極值的思想，從而形成了基礎的時鐘同步算法，實現(xiàn)過程如圖4所示。

圖4 FTA算法同步過程Figure 4. The synchronization process of FTA algorithm

對于由N個節(jié)點組成的系統(tǒng)，要容忍x個拜占庭故障，每個節(jié)點通過交互的方式收集本地時鐘與其他節(jié)點的時鐘之間的時間偏差，得到N-1個時間偏差，加上自身的時間偏差，總共得到了N個時間偏差。然后，將這些時間偏差由大到小排序，去除偏差序列中x個最小值和x個最大值，最后對剩余序列中的N-2x個時間偏差求平均值，以此來獲得本地時鐘的校正項。

由模型假設本文可以得知，系統(tǒng)中各個節(jié)點初始同步到φint內(nèi)，本文引入一個收斂函數(shù)Γ(φint，N，f，ε)，該函數(shù)用于給出瞬時重同步后所有好時鐘的時鐘值的最大差值，即系統(tǒng)的時鐘精密度。

讀取誤差ε是一個附加項，將收斂函數(shù)分解為式(10)。

Γφint，N，f，ε)=Γφint，N，f)+ε

(10)

在最壞的情況下，一個好的“過期”消息被一個節(jié)點接收到，而另一個節(jié)點沒接收到。因此，單個消息的丟失對于平均值的影響是有限的，可由下式計算。

(11)

由上述計算可以計算出，在考慮讀取錯誤和f個故障(報文丟失、拜占庭故障)的情況下，重同步后全局近似時間偏差的最大值為式(12)。

(12)

在重同步周期λ內(nèi)，好的時鐘的最大偏移率為ρ，因此在同步周期內(nèi)，將好時鐘之間的最大偏移量記為ζ，則下式成立。

ξ=2ρλ

(13)

由于任何兩個好的時鐘在同一重同步時間間隔內(nèi)都會偏離，因此對于任何重同步間隔內(nèi)，下列條件必然成立

Γφint，N，f，ε)≤φint-ξ

(14)

由式(12)和式(14)計算出FTA算法的同步精密度最大值計算式。

(15)

由式(15)可以看出，在前文所建立的模型下，在一個由10個時鐘組成的系統(tǒng)中，當只有一個故障的時候，系統(tǒng)會損失14%的同步精密度；當系統(tǒng)中出現(xiàn)兩個任意的故障，雖然系統(tǒng)可以容忍，但是這會導致50%的同步精密度損失。經(jīng)過上述分析可以看出，該算法具有一定的容錯能力，并且其容錯能力體現(xiàn)在去極值的過程。但是在滿足模型假設的情況下，隨著拜占庭故障數(shù)量不斷增多，系統(tǒng)的容錯能力大幅度下滑，因此本文將針對這一問題對FTA算法進行改進。

在上述FTA算法的介紹中可以看出其并不能保證完全將系統(tǒng)中存在的故障濾除，因此之后的“求平均”所得到的結果將會受到拜占庭故障的影響。這降低了系統(tǒng)的容錯能力，因此本文在FTA算法的基礎上采用了“容錯中值”的方法，提出了適用于RTEthernet的容錯中值算法，即RTEthernet容錯中值算法(RTEthernet Fault-Tolerant Midpoint Algorithm， RTE-FTM)算法，這種方法可以避免一個壞的值對中值的扭曲。

RTE-FTM算法沿用了FTA算法中去極值的思想，將每個節(jié)點讀取到的時鐘值集Pi進行去降序排列，再將Pi中最大和最小的f個時鐘值剔除，得到一個新的集合Pif，然后將集合Pif中新序列的中值當做目標值，即全局時基。如果序列中的個數(shù)為偶數(shù)，則用中間兩個數(shù)的平均值(向下取整)來當作全局時基。

根據(jù)上文的模型假設與容錯能力的改進，下面以偽代碼的形式描述第i輪同步中節(jié)點q使用容錯中值時鐘同步算法進行時鐘同步的過程。函數(shù)及符號定義如表1所示。

表1 偽代碼參數(shù)Table 1. Pseud code Parameters

RTEthernet容錯中值算法描述如下：

輸入：重同步時間。

輸出：本地節(jié)點即將應用的校正項。

2.GET[q]=TqNOW//每個節(jié)點記錄當前的時鐘值

4.send(message)；

5. end if

7.ifTqNOW=Tithen

11.end if

12.end while

綜上可以看出，各個節(jié)點進行交互各自的本地時鐘值，然后將獲取到的(包括自己的)時鐘值進行降序排列，隨后去除f個最大值和f個最小值，并使余下值中的中值作為目標值，再進行代數(shù)計算可以得到校正項，最后通過狀態(tài)修正和速率修正算法來進行時鐘的同步。由于RTE-FTM算法是以FTA算法為基礎，用中點值代替平均值的計算方法，因此算法的收斂性和有效性證明與FTA算法相類似，這里不重新進行理論的證明。在下一節(jié)中將通過實驗仿真驗證其收斂性和有效性。

5 實驗結果與分析

本文在章節(jié)4中對FTA算法進行改進，提出了數(shù)學模型，本章節(jié)中將對RTE-FTM算法的收斂性和容錯性進行仿真驗證。采用CANoe平臺進行仿真實驗，CANoe的主要組成部分為：CANdb++、Panel Editor&Panel Designer和編程工具CAPL(CAN Access Programming Language)。

5.1 系統(tǒng)模型的構成

本實驗通過7個節(jié)點構成一個總線型的拓撲結構，網(wǎng)絡中各個節(jié)點通過模擬RTEthernet協(xié)議進行通信。本文將節(jié)點1、節(jié)點2、節(jié)點4、節(jié)點5、節(jié)點7設置為無故障節(jié)點。根據(jù)章節(jié)3中的算法模型，將節(jié)點3和節(jié)點6設置為拜占庭故障節(jié)點，其網(wǎng)絡拓撲結構如圖5所示。

圖5 仿真系統(tǒng)拓撲結構Figure 5. The topology structure of the simulation system

5.2 系統(tǒng)參數(shù)設置

在上述搭建好的系統(tǒng)模型中，需要確定模型參數(shù)值。本節(jié)將對仿真實驗中具體參數(shù)進行確定。根據(jù)文獻[13，17～18]的研究成果及RTEthernet通信模型的約束條件，確定部分參數(shù)為：系統(tǒng)內(nèi)各節(jié)點的最大時鐘漂移率ρ=10-4s，各節(jié)點初始同步的精密度為φint=20×10-6s，并且在系統(tǒng)中的傳輸延遲最大為10×10-6s，最小延遲為5×10-6s。即分布式系統(tǒng)內(nèi)的消息傳輸延遲在[5，10] μs內(nèi)，因此系統(tǒng)的傳輸延遲不確定度為2.5×10-6s，消息延遲范圍的中間值δ=7.5×10-6s。根據(jù)前文的假設和RTEthernet網(wǎng)絡的協(xié)議規(guī)范可知，仿真系統(tǒng)的重同步周期的下限只存在于ST段和NIT段，上限包含了DYN段，本文考慮普通情況下的重同步周期，即每個循環(huán)中包含了ST段和DYN段以及NIT段，故將長度設置為5 ms，循環(huán)編號最大編號(gCycleMax)為200。具體參數(shù)如表2所示。

表2 系統(tǒng)模型參數(shù)Table 2. Parameters of the system model

5.3 仿真結果分析

根據(jù)上述系統(tǒng)拓撲結構和參數(shù)的設置，本文將對存在故障情況下的FTA和RTE-FTM算法進行收斂性和容錯性驗證。

控制f=0與系統(tǒng)初始精密度φint=20×10-6s，根據(jù)表2的參數(shù)來設置每個虛擬節(jié)點時鐘的環(huán)境變量，各個節(jié)點分別執(zhí)行FTA、RTE-FTM兩種算法，并將兩種算法進行對比分析。從圖6可以看出，系統(tǒng)中的各個時鐘經(jīng)過時鐘同步算法進行周期性時間校正后，系統(tǒng)的時鐘精密度大致穩(wěn)定在一定的范圍內(nèi)，在無拜占庭故障時鐘時，RTE-FTM的精度大于FTA的精度。

圖6 無拜占庭故障情況下兩種算法的時鐘同步精密度對比Figure 6. Comparison of clock synchronization precision between two algorithms without Byzantine fault

控制f=1，2和系統(tǒng)初始精密度φint=20×10-6s，對FTA、RTE-FTM算法進行對比分析及收斂性和容錯性驗證。從圖7可看出，當設置節(jié)點3發(fā)生拜占庭故障時，經(jīng)過FTA算法同步后系統(tǒng)的精密度大約為24.47 μs；當有節(jié)點3和6都發(fā)生拜占庭故障時，整個系統(tǒng)的精密度約為26.32 μs。由此可知，在10個節(jié)點的系統(tǒng)中存在兩個拜占庭故障時，F(xiàn)TA算法的容錯能力降低，同步后系統(tǒng)精密度下降13.7%。對于RTE-FTM算法，當有一個節(jié)點發(fā)生拜占庭故障時，整個系統(tǒng)的精密度約為27.92 μs，當有兩個節(jié)點同時發(fā)生拜占庭故障時，整個系統(tǒng)的精密度約為28.34 μs。

圖7 拜占庭故障情況下兩種算法的時鐘同步精密度對比Figure 7. Comparison of clock synchronization precision between two algorithms under Byzantine fault

綜上，在滿足以下兩個條件：(1)分布式系統(tǒng)中各個節(jié)點初始同步；(2)節(jié)點數(shù)不超過總數(shù)1/3的拜占庭故障節(jié)點，可認定RTE-FTM是收斂的。在系統(tǒng)中存在拜占庭故障時，F(xiàn)TA算法的同步精密度損失了13.7%，RTE-FTM算法的同步精密度損失了10.6%。在拜占庭故障數(shù)量相同的情況下，RTE-FTM算法比FTA算法的同步精密度損失率降低了3.1%。

6 結束語

工業(yè)以太網(wǎng)[19]在工業(yè)制造、自動化控制等領域中的應用不斷擴大，但是想要能夠完成無線到有線的“變革”，不可避免地要考慮實時性和可靠性。因此，工業(yè)以太網(wǎng)的時鐘同步問題成了關鍵問題之一。RTEthernet是一種新型的工業(yè)級實時以太網(wǎng)協(xié)議，其便于實現(xiàn)，且可兼顧傳統(tǒng)以太網(wǎng)，但是該協(xié)議的時鐘同步算法存在容錯性低的問題。為此，本文針對FTA算法的容錯策略進行修改，即使用“中點值”策略來代替“平均值”策略，提出了RTE-FTM算法來替代原始的基礎算法。改進后的算法能夠使系統(tǒng)進一步弱化拜占庭故障時鐘值對全局時基的影響。在實際系統(tǒng)中存在更為復雜的通信環(huán)境，會存在很多沒能完全考慮的干擾源，所以在今后的研究中，研究人員將根據(jù)實際情況對本文提出的算法進行優(yōu)化改進。