基于RTEthernet改進(jìn)的時(shí)鐘同步算法

陳佳佳，張鳳登，張宇輝

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

0 引言

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

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

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

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

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

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

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

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

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

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

圖2 RTEthernet通信原理

2 同步時(shí)鐘的概念及FTA算法

2.1 時(shí)鐘同步

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

2.2 誤差來源

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

圖3 時(shí)鐘拜占庭故障

2.3 時(shí)鐘同步的衡量指標(biāo)

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

(1)

(2)

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

(3)

2.4 FTA算法

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

圖4 FTA算法同步過程

3 滑動(dòng)窗口時(shí)鐘同步算法

3.1 滑動(dòng)窗口技術(shù)

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

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

圖5 滑動(dòng)窗口示例

3.2 容錯(cuò)滑動(dòng)窗口算法的描述

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

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

表1 偽代碼參數(shù)

2)算法描述

算法：容錯(cuò)滑動(dòng)窗口算法

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

輸出：本地節(jié)點(diǎn)即將應(yīng)用的校正項(xiàng)

1.WhileTkNOW=Tido/*當(dāng)任一節(jié)點(diǎn)當(dāng)前的邏輯時(shí)鐘進(jìn)入第i輪的循環(huán)時(shí)開始準(zhǔn)備時(shí)鐘同步*/

2.ARRki(k)=TkNOW //每個(gè)節(jié)點(diǎn)記錄當(dāng)前的時(shí)鐘值

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

4.send(message);

5.Pki[k]= ARRki(q)

6.end if

7.ifTkNOW=TNITithen

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

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))//獲取方差最大集合的補(bǔ)集，然后求得該補(bǔ)集的中值

14.ADJki=Tki-MED+δ//計(jì)算校正項(xiàng)

15.return(ADJki)

16.end if

17.end while

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

圖6 NIT段的FTSW算法

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

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

圖7 時(shí)鐘值收集階段

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

(4)

對(duì)于無故障時(shí)鐘有：

(5)

圖8 去極值階段

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

圖9 滑動(dòng)窗口階段

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

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

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

4 算法仿真驗(yàn)證

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

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

圖10 仿真系統(tǒng)拓?fù)浣Y(jié)構(gòu)

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

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

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

4.3 仿真結(jié)果分析

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

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

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

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

2)當(dāng)f=1,2和系統(tǒng)初始精密度φint=20 μs時(shí)，系統(tǒng)中的各個(gè)節(jié)點(diǎn)分別執(zhí)行FTA算法和FTSW算法，對(duì)FTA算法和FTSW算法進(jìn)行比較分析和容錯(cuò)性驗(yàn)證。

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

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

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

綜上，在分布式系統(tǒng)中各個(gè)節(jié)點(diǎn)初始同步的情況下，存在最多不超過節(jié)點(diǎn)總數(shù)1/3的拜占庭故障節(jié)點(diǎn)的情況下，F(xiàn)TSW算法是收斂的，并且在無故障情況下，F(xiàn)TSW算法的同步精密度較高；當(dāng)系統(tǒng)中存在拜占庭故障的時(shí)候，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è)制造、自動(dòng)化工業(yè)等領(lǐng)域在以非常迅猛的速度往前發(fā)展。如果要實(shí)現(xiàn)從無線到有線的巨大變化，需要考慮到實(shí)時(shí)性和可靠性。隨著分布式系統(tǒng)的應(yīng)用越來越廣泛，系統(tǒng)需要分配的節(jié)點(diǎn)也更多，因此發(fā)生故障的概率也越高。對(duì)于其中具有嚴(yán)格時(shí)間要求的系統(tǒng)中，時(shí)間同步變得越來越重要。工業(yè)以太網(wǎng)的時(shí)鐘同步問題是一個(gè)比較關(guān)鍵的問題。在滿足時(shí)鐘同步的前提下，系統(tǒng)還需要具有一定的容錯(cuò)能力。RTEthernet是可以同時(shí)兼顧傳統(tǒng)以太網(wǎng)的新型工業(yè)級(jí)的實(shí)時(shí)以太網(wǎng)協(xié)議，但是該協(xié)議的時(shí)鐘同步算法容錯(cuò)性較低。文中引入了滑動(dòng)窗口技術(shù)，得到了一種具有較強(qiáng)容錯(cuò)能力的算法，即FTSW算法。文中研究主要集中在確定性時(shí)鐘同步算法，在后續(xù)的研究中可以考慮能否將統(tǒng)計(jì)型和概率型算法的思想引入到RTEthernet的時(shí)鐘同步過程中。