基于RTEthernet改進的時鐘同步算法

陳佳佳，張鳳登，張宇輝

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

0 引言

RTEthernet(Real-Time Ethernet)是一種可以兼容傳統(tǒng)以太網(wǎng)協(xié)議的實時以太網(wǎng)。RTEthernet在以往的物理層和數(shù)據(jù)鏈路層之上增添了會話層，并且使用了“通信循環(huán)”的概念來分時傳輸實時性消息和非實時性消息。

國外在時鐘同步理論研究的起步是比較早的。1978年，Leslie Lamport在文獻[1]中提出了邏輯時鐘的概念，邏輯時鐘這一概念的提出給內(nèi)部時鐘同步技術(shù)的發(fā)展提供了前提條件，通過在分布式實時系統(tǒng)內(nèi)部建立一個虛擬的全局時間來實現(xiàn)各個節(jié)點之間的時間同步。

2004年，Kopetz等人在其著作[2]中提出了將狀態(tài)同步與速率同步相結(jié)合的方法，并對主從式，非主從式同步進行了實驗。實驗表明，將狀態(tài)同步與速率同步相結(jié)合能有效提高同步的精密度。對于不同的系統(tǒng)模型、同步精密度要求和容錯能力等方面，衍生出了各種各樣的時鐘同步算法。綜合遠程時鐘讀取技術(shù)、算法容忍故障類型、系統(tǒng)通信模型等方面，可將算法大致分成了三類[3-4]：確定性、概率型和統(tǒng)計型。

通過對RTEthernet協(xié)議通信原理及其基礎時鐘同步算法進行了研究，并且考慮拜占庭故障對系統(tǒng)時鐘精密度的影響，引入了滑動窗口技術(shù)來提升時鐘同步算法容錯性，提出了具有更高容錯性的時鐘同步算法——滑動窗口時鐘同步算法。

1 系統(tǒng)結(jié)構(gòu)及原理

1.1 RTEthernet體系結(jié)構(gòu)

RTEthernet是保留了傳統(tǒng)Ethernet的物理層和數(shù)據(jù)鏈路層的實時以太網(wǎng)。在這個基礎上引進了“全局時間”的概念，同時還用了ISO/OSI參考模型的會話層進行報文的再封裝。RTEthernet不僅可以兼容傳統(tǒng)以太網(wǎng)，而且可以通過用時分多路訪問(TDMA,time division multiple access)的通信方式進行基礎報文的傳送，提高了傳統(tǒng)以太網(wǎng)的實時性和安全性。ISO/OSI、Ethernet和RTEthernet的體系結(jié)構(gòu)如圖1所示。

圖1 ISO/OSI、Ethernet和RTEthernet的體系結(jié)構(gòu)

1.2 RTEthernet通信結(jié)構(gòu)

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

圖2 RTEthernet通信原理

2 同步時鐘的概念及FTA算法

2.1 時鐘同步

時鐘同步算法的主要目標是要保證處理器的時鐘差異不超過某個定值。在保證一定時鐘同步精度的前提下，降低節(jié)點在時鐘同步過程中的能量消耗，延長節(jié)點的生命周期是設計時鐘同步算法的首要考慮。保證分布式系統(tǒng)中各個節(jié)點的時鐘彼此同步成為保證分布式系統(tǒng)實時性的基礎。

2.2 誤差來源

分布式實時系統(tǒng)中的節(jié)點需要交換各自的時鐘信息來實現(xiàn)建立全局時間。它們通過通信網(wǎng)絡連接，在發(fā)送和接受各自本地時鐘時都需要一個真實存在的處理時間。因此在時鐘同步中需要考慮通信延遲的存在，不然將會直接影響到最終算法的性能。而且節(jié)點中的處理器、時鐘、通信的鏈路等組件都有可能發(fā)生故障。故障主要可以分成七類，其中最重要的是時鐘拜占庭故障。分布式系統(tǒng)中的任意節(jié)點都有可能遭遇某一種故障或幾種故障混合，這時我們稱該節(jié)點為故障節(jié)點，否則稱之為無故障節(jié)點。文中考慮的是一般性故障和最惡劣情況(拜占庭故障，如圖3所示)下的情況。若分布式系統(tǒng)可以通過某時鐘同步算法容忍最惡劣情況下的故障，則說明這個算法是有效的。時鐘同步算法的容錯性主要體現(xiàn)在系統(tǒng)對拜占庭故障節(jié)點的容忍性這方面。

圖3 時鐘拜占庭故障

2.3 時鐘同步的衡量指標

為了衡量系統(tǒng)中各個時鐘的行為是否達到同步，引入了準確度Ψ、時鐘偏差Δ和精密度φ這幾個指標來衡量。偏差Δ：具有相同分辨率的兩個時鐘在同一單位微節(jié)拍上的偏移，即兩個時鐘速率的相對差，表示為：

(1)

(2)

把有限時間間隔上的最大φi稱為時鐘集合的精密度。如果精密度φi小于某個期望值，就表示系統(tǒng)的內(nèi)部各個節(jié)點之間相互同步，反之，就沒有達到同步。

(3)

2.4 FTA算法

傳統(tǒng)的容錯算法FTA容錯均值算法是通過對修正項進行篩除提高修正項的準確性。FTA算法是一種單輪算法，能夠?qū)Σ灰恢碌男畔⑦M行處理，避免因為信息不一致引入的錯誤。該算法是從傳統(tǒng)的“平均技術(shù)”發(fā)展而來的，并且在其中融入了去除極值的思想，于是形成了基礎的時鐘同步算法，F(xiàn)TA算法在一定基礎上提高了分布式系統(tǒng)時鐘同步的容錯性，算法過程如圖4所示。

圖4 FTA算法同步過程

3 滑動窗口時鐘同步算法

3.1 滑動窗口技術(shù)

滑動窗口是一種流量控制技術(shù)。在早期的網(wǎng)絡通信中，通信雙方?jīng)]有考慮網(wǎng)絡的擁堵情況而直接發(fā)送數(shù)據(jù)導致了中間結(jié)點阻塞丟包，雙方都不能發(fā)送數(shù)據(jù)，所以就有了滑動窗口機制來解決此問題[5]。后來，由這一技術(shù)衍化而來的滑動窗口算法不僅大量運用到了通信領域，在其他各個領域之中也得到了廣泛地應用，例如圖像處理，軌跡預測及其他進行數(shù)據(jù)預測、優(yōu)化的領域。滑動窗口算法和滑動窗口技術(shù)是一樣的，只是應用的場景不一樣，可以根據(jù)需要調(diào)整窗口的大小，也可以固定窗口的大小[6]。

滑動窗口技術(shù)是在給定的特定窗口大小的數(shù)組或字符串上執(zhí)行要求的操作。該技術(shù)可以將一部分問題中的嵌套循環(huán)轉(zhuǎn)變?yōu)橐粋€單一循環(huán)，因此它可以減少時間復雜度。下面舉例簡單說明滑動窗口技術(shù)的原理。如圖5所示，我們假定有一組數(shù)：-2,3,1,5,4,0,7,1,-1,求出波動最小相鄰的4個元素。因此，我們將窗口大小設定為4，當滑動窗口每次劃過數(shù)組時，計算當前滑動窗口中所有元素的方差。圖5可以方便看出滑動窗口技術(shù)可以用來解決一些滿足一定條件的連續(xù)區(qū)間的問題。由于區(qū)間的連續(xù)性，當區(qū)間發(fā)生變化時，可以通過既有的計算結(jié)果對搜索空間進行裁剪，從而減少了重復計算，節(jié)省了時間。

圖5 滑動窗口示例

3.2 容錯滑動窗口算法的描述

根據(jù)文中對容錯能力的改進，下面以為偽代碼的形式描述第i輪同步中節(jié)點k使用容錯滑動窗口算法進行時鐘同步的過程：

1)函數(shù)及符號的定義，見表1：

表1 偽代碼參數(shù)

2)算法描述

算法：容錯滑動窗口算法

輸入：重同步時間

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

1.WhileTkNOW=Tido/*當任一節(jié)點當前的邏輯時鐘進入第i輪的循環(huán)時開始準備時鐘同步*/

2.ARRki(k)=TkNOW //每個節(jié)點記錄當前的時鐘值

3. ifTkNOW=Tkithen /*如果任一節(jié)點的時鐘值等于重同步時間，則將自己的時鐘值發(fā)送給其他所有節(jié)點*/

4.send(message);

5.Pki[k]= ARRki(q)

6.end if

7.ifTkNOW=TNITithen

8.Qki[k]=discard(descend(Pki[k]))//將獲取到的時鐘值進行降序排列，然后去掉f/2個最大和最小的值

9.whilej≤n-2f+1then//獲取所有窗口內(nèi)的方差

10.Wj[k]= SWAj(Qki[k])

11. S[j]=variance(Wj[k])

12.end

13.MED=median(rest(Qki[k],Smax))//獲取方差最大集合的補集，然后求得該補集的中值

14.ADJki=Tki-MED+δ//計算校正項

15.return(ADJki)

16.end if

17.end while

上述過程概括的來說，可將算法分為4個階段：時鐘值收集階段、去極值階段、滑動窗口階段和求中值階段。分布式實時以太網(wǎng)將通信的循環(huán)劃分為了靜態(tài)段、動態(tài)段和NIT段。每個節(jié)點在通信循環(huán)中NIT的開始時刻執(zhí)行FTSW算法，如圖6所示。

圖6 NIT段的FTSW算法

下面將分別介紹FTSW算法的各個階段。

1)時鐘值收集階段：所有要參與時鐘同步的節(jié)點在通信循環(huán)的靜態(tài)段時隙的開始處，通過通信幀幀頭的第4位，向時鐘集合中的所有其他參與者表明它將發(fā)送是同步幀，該同步幀的作用是參與網(wǎng)絡的同步[7]。然后利用靜態(tài)段發(fā)送的同步幀測量時間偏差來得到每個節(jié)點的時鐘估計值，并存儲在一個數(shù)列中，然后將數(shù)列中的時鐘值按照降序排列，如圖7所示。

圖7 時鐘值收集階段

每個節(jié)點時鐘在第r輪的重同步，可將得到的時鐘值構(gòu)造成一個時鐘值矩陣，我們以節(jié)點k為例，節(jié)點k保存該矩陣的列和對角線上的元素。

(4)

對于無故障時鐘有：

(5)

圖8 去極值階段

3)滑動窗口階段：滑動窗口的大小為f，并且f為該系統(tǒng)能夠容忍的故障節(jié)點數(shù)。該窗口從去極值后的時鐘值序列的最左端開始，也就是第一個窗口是由第f/2+1個元素至第3f/2個元素組成的。然后，將窗口逐元素的向右滑動，直至窗口的最右邊元素為第n-f/2個元素，即去極值后序列中的最右邊元素。在這個過程中，一共得到了n-2f+1個窗口的數(shù)據(jù)集。最后，從這n-2f+1個數(shù)據(jù)集中找到方差最大的窗口，如圖9所示。

圖9 滑動窗口階段

4)求中值階段：利用滑動窗口階段得出了方差最大的時鐘值集，然后將這些時鐘值剔除，最后對剩余的時鐘值進行求中值，從而減輕時鐘拜占庭故障對最終校正項的影響。

上述算法概括的來說，先將遠程讀取到的時鐘值進行降序排列，然后去除f個極端值(f/2個最大值和最小值)，當f是奇數(shù)時將去除的極大值個數(shù)向上取整，去除的極小值個數(shù)向下取整。然后，對剩余的時鐘值利用滑動窗口的思想求出方差最大的窗口，然后得到其補集。最后求取該補集的中值，若此時補集為偶數(shù)時求取中間兩個值的均值，然后對該中值向下取整。最終，利用簡單的代數(shù)運算就可以求得本地時鐘的校正項。

從算法的實現(xiàn)上來講，容錯滑動窗口算法在FTA算法的基礎上采用了容錯中值的思想并且增加了求最大方差窗口的過程，這一過程有效地提高了系統(tǒng)的容錯能力，這是該算法的顯著特點。

4 算法仿真驗證

4.1 系統(tǒng)模型的構(gòu)成

實驗用7個節(jié)點組成一個總線型的拓撲結(jié)構(gòu)，該網(wǎng)絡中的各個節(jié)點模擬RTEthernet協(xié)議進行通信。將節(jié)點3和6設置成拜占庭故障節(jié)點，把1,2,4,5,7節(jié)點設置成無故障節(jié)點，如圖10所示為仿真系統(tǒng)拓撲結(jié)構(gòu)。

圖10 仿真系統(tǒng)拓撲結(jié)構(gòu)

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

根據(jù)文獻[8-10]研究成果和RTEthernet通信模型對局部參數(shù)進行設置：系統(tǒng)中各節(jié)點初始同步的精密度設置為φint=20×10-6s，各個節(jié)點的最大時鐘漂移率為ρ=10-4s，系統(tǒng)中傳輸延遲最小的為5×10-6s，延遲最多的為10×10-6s。即設置分布式系統(tǒng)內(nèi)的消息傳輸延遲范圍為[5,10] μs，因此該系統(tǒng)傳輸延遲的不確定度為2.5×10-6s，消息延遲范圍的中間值為δ=7.5×10-6s。然后，考慮每個循環(huán)中包含了ST段和DYN段以及NIT段，將重同步周期長度設置為5 ms。節(jié)點參數(shù)設置如表2所示。

表2 系統(tǒng)節(jié)點參數(shù)

4.3 仿真結(jié)果分析

根據(jù)上述系統(tǒng)拓撲結(jié)構(gòu)和參數(shù)的設置，本文將實驗分為兩部分，第一部分是無拜占庭時鐘故障情況下對FTA和FTSW算法進行收斂性驗證，第二部分是存在拜占庭故障情況下對FTA和FTSW算法進行容錯性驗證，運行結(jié)果如下：

1)當f=0與系統(tǒng)初始精密度φint=20 μs時，系統(tǒng)中的各個節(jié)點分別執(zhí)行FTA算法和FTSW算法，最終將每次同步后系統(tǒng)的精密度繪制為如圖11所示。

圖11 無拜占庭故障情況下兩種算法的時鐘同步精密度對比

從圖11可以看出，該系統(tǒng)中的各個時鐘通過時鐘同步算法進行過周期性的時間校正后，系統(tǒng)的時鐘精密度會趨于穩(wěn)定，并且當無拜占庭故障時鐘的時候FTA算法大于FTSW算法。當考慮到傳輸延遲的誤差后， FTSW算法的平均精密度約為22.28 μs，F(xiàn)TA算法的平均精密度約為23.15 μs。由此可以看出，在此系統(tǒng)中無拜占庭故障的情況下，原始算法的精密度還是比較優(yōu)異的。

2)當f=1,2和系統(tǒng)初始精密度φint=20 μs時，系統(tǒng)中的各個節(jié)點分別執(zhí)行FTA算法和FTSW算法，對FTA算法和FTSW算法進行比較分析和容錯性驗證。

由圖12可以看出，當系統(tǒng)中節(jié)點3發(fā)生拜占庭故障時，經(jīng)過FTA算法同步后該系統(tǒng)精密度為24.47 μs，當系統(tǒng)中的節(jié)點3和6同時發(fā)生拜占庭故障時，該系統(tǒng)的精密度為26.32 μs。由此可以發(fā)現(xiàn)，在一個由7個節(jié)點組成的系統(tǒng)中，當系統(tǒng)中存在兩個拜占庭故障的時候，F(xiàn)TA算法的容錯能力大大降低，系統(tǒng)的精密度下降了13.7%。

圖12 出現(xiàn)拜占庭故障情況下兩種算法的時間同步精密度對比

此實驗是在時鐘同步過程中通過環(huán)境變量控制一個節(jié)點(節(jié)點3)或者兩個節(jié)點(節(jié)點3和6)，使其產(chǎn)生[0,200]之間的隨機數(shù)(單位為μs)作為該節(jié)點的本地時間信息封裝到同步幀并發(fā)送到網(wǎng)絡，試圖干擾其他節(jié)點的時間同步，但該節(jié)點自身真實的本地時間還是保持原來微節(jié)拍計數(shù)器的正常計數(shù)值。從圖12可以看出，當一個節(jié)點發(fā)生拜占庭故障時，該系統(tǒng)的精密度為22.15 μs,當系統(tǒng)中兩個節(jié)點同時發(fā)生拜占庭故障的時候，該系統(tǒng)的精密度為23.75 μs。

綜上，在分布式系統(tǒng)中各個節(jié)點初始同步的情況下，存在最多不超過節(jié)點總數(shù)1/3的拜占庭故障節(jié)點的情況下，F(xiàn)TSW算法是收斂的，并且在無故障情況下，F(xiàn)TSW算法的同步精密度較高；當系統(tǒng)中存在拜占庭故障的時候，F(xiàn)TA算法的同步精密度損失了13.7%，F(xiàn)TSW算法的同步精密度損失了6.6%，F(xiàn)TSW算法的同步精密度比FTA算法的精密度提高了7.1%。

5 結(jié)束語

隨著工業(yè)以太網(wǎng)的不斷發(fā)展，電力、鋼鐵、工業(yè)制造、自動化工業(yè)等領域在以非常迅猛的速度往前發(fā)展。如果要實現(xiàn)從無線到有線的巨大變化，需要考慮到實時性和可靠性。隨著分布式系統(tǒng)的應用越來越廣泛，系統(tǒng)需要分配的節(jié)點也更多，因此發(fā)生故障的概率也越高。對于其中具有嚴格時間要求的系統(tǒng)中，時間同步變得越來越重要。工業(yè)以太網(wǎng)的時鐘同步問題是一個比較關鍵的問題。在滿足時鐘同步的前提下，系統(tǒng)還需要具有一定的容錯能力。RTEthernet是可以同時兼顧傳統(tǒng)以太網(wǎng)的新型工業(yè)級的實時以太網(wǎng)協(xié)議，但是該協(xié)議的時鐘同步算法容錯性較低。文中引入了滑動窗口技術(shù)，得到了一種具有較強容錯能力的算法，即FTSW算法。文中研究主要集中在確定性時鐘同步算法，在后續(xù)的研究中可以考慮能否將統(tǒng)計型和概率型算法的思想引入到RTEthernet的時鐘同步過程中。