FlexRay時(shí)鐘同步拜占庭故障容錯(cuò)算法研究

劉讓 張鳳登

摘 要：為了解決FlexRay分布式實(shí)時(shí)系統(tǒng)中時(shí)鐘同步可能出現(xiàn)拜占庭故障，從而導(dǎo)致系統(tǒng)時(shí)鐘崩潰的問題，提出一種有效的解決算法FlexRayB FT（ FlexRay Byzantine-Fault-Tolerant）。該算法在傳統(tǒng)拜占庭容錯(cuò)算法基礎(chǔ)上引入消息認(rèn)證碼技術(shù)，對(duì)報(bào)文進(jìn)行加密處理，相比指數(shù)型算法，其性能提高了3個(gè)數(shù)量級(jí)。FlexRayBFT執(zhí)行分為準(zhǔn)備階段與回復(fù)執(zhí)行階段，分析不同階段的消息具體通信過程，同時(shí)證明了算法的一致性與正確性。通過使用Truetime工具箱搭建FlexRay線控轉(zhuǎn)向分布式實(shí)時(shí)系統(tǒng)，對(duì)系統(tǒng)使用FlexRayBFT算法前后分別進(jìn)行仿真實(shí)驗(yàn)驗(yàn)證。結(jié)果表明，F(xiàn)lexRayBFT算法可以有效克服FlexRay分布式實(shí)時(shí)系統(tǒng)中時(shí)鐘同步的拜占庭故障，保障時(shí)鐘同步的穩(wěn)定性。

關(guān)鍵詞：FlexRay;分布式實(shí)時(shí)系統(tǒng);時(shí)鐘同步;拜占庭故障

DOI： 10. 11907/rjdk.192422

開放科學(xué)（資源服務(wù)）標(biāo)識(shí)碼（OSID）：

中圖分類號(hào)：TP312

文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1672-7800（2020）001-0068-07

0 引言

隨著汽車電子控制系統(tǒng)的發(fā)展，一種基于FlexRay的分布式實(shí)時(shí)系統(tǒng)逐漸受到關(guān)注。作為新興的汽車電子分布式系統(tǒng)，其對(duì)實(shí)時(shí)性與可靠性有著嚴(yán)格要求，而拜占庭惡性故障對(duì)分布式系統(tǒng)的時(shí)鐘同步會(huì)造成嚴(yán)重威脅，故在系統(tǒng)設(shè)計(jì)中，容忍時(shí)鐘同步中的拜占庭惡性故障，從而保證系統(tǒng)實(shí)時(shí)性與可靠性至關(guān)重要。

目前在時(shí)鐘同步及拜占庭故障方面，國內(nèi)外已進(jìn)行了很多研究。針對(duì)時(shí)鐘同步算法，Lamport在文獻(xiàn)[1]中系統(tǒng)闡述了時(shí)鐘同步技術(shù)原理、方法及其在分布式系統(tǒng)中的應(yīng)用，以及邏輯時(shí)鐘在帶時(shí)序分布式事件處理中的作用，并在文獻(xiàn)[2]、[3]中提出確定性收斂平均時(shí)鐘同步方法;Yamashita等[4]對(duì)高斯分布的時(shí)鐘同步信息傳輸延遲進(jìn)行分析，給出高斯分布下時(shí)鐘同步精度置信區(qū)間表達(dá)式以及時(shí)鐘偏差均值計(jì)算方法，但對(duì)于具體工程應(yīng)用中的時(shí)鐘同步，單純的軟件時(shí)鐘同步算法實(shí)現(xiàn)的同步精度相對(duì)較低;Ramanathan等[5-6]提出一種將軟硬件結(jié)合的同步方式，軟件算法借鑒Lamport的收斂平均算法[2-3]，而硬件部分主要實(shí)現(xiàn)同步信息的發(fā)送與接收，以及記錄同步信息的本地時(shí)間戳。實(shí)驗(yàn)結(jié)果表明，采用軟硬件結(jié)合的同步算法后，可以使系統(tǒng)同步誤差精確到幾十個(gè)微秒級(jí)，比純軟件同步算法提高了2個(gè)數(shù)量級(jí)以上。然而，以上研究僅針對(duì)時(shí)鐘同步，無法解決該過程中出現(xiàn)的一系列故障問題，所以可容忍故障的時(shí)鐘同步方案之后逐漸被提出。其中文獻(xiàn)[7]提出共同投幣技術(shù)，利用該技術(shù)構(gòu)造概率型常數(shù)輪的同步拜占庭一致性協(xié)議。對(duì)于分布式系統(tǒng)中的每一個(gè)節(jié)點(diǎn)，共同投幣技術(shù)的使用讓其在每一輪運(yùn)行中得到一個(gè)事先無法預(yù)測(cè)的隨機(jī)比特值，那些正常節(jié)點(diǎn)通過該共同隨機(jī)比特值達(dá)成一致意見。但該方法是一個(gè)概率性方法，比較容易受到破壞;文獻(xiàn)[8]一[11]提出使用Ouorum和狀態(tài)機(jī)復(fù)制技術(shù)實(shí)現(xiàn)的異步拜占庭故障容忍算法（BFT），該算法在狀態(tài)機(jī)中的執(zhí)行分為5個(gè)階段，分別為：請(qǐng)求階段、預(yù)備階段、準(zhǔn)備階段、回復(fù)階段、執(zhí)行階段，并結(jié)合前攝性恢復(fù)技術(shù)使拜占庭節(jié)點(diǎn)在更新服務(wù)狀態(tài)后可以重用。算法確保了系統(tǒng)在某時(shí)間段內(nèi)可容忍的拜占庭節(jié)點(diǎn)數(shù)小于系統(tǒng)節(jié)點(diǎn)總數(shù)的1/3，而在系統(tǒng)整個(gè)運(yùn)行時(shí)間內(nèi)則可以容忍任意數(shù)量的拜占庭節(jié)點(diǎn)。BFT（ Byzantine Fault Tolerant）算法的良好性能提升了拜占庭容錯(cuò)系統(tǒng)在實(shí)際工程領(lǐng)域的可行性，但該算法執(zhí)行過程相對(duì)復(fù)雜，且僅可以實(shí)現(xiàn)固定組的拜占庭節(jié)點(diǎn)一致，一旦節(jié)點(diǎn)出現(xiàn)物理故障或受到惡意攻擊，性能便會(huì)大大降低。因此，本文提出可容忍該故障的FlexRay-BFT算法，使用加密技術(shù)對(duì)消息進(jìn)行驗(yàn)證。在對(duì)比公鑰簽名體系與消息認(rèn)證碼后，發(fā)現(xiàn)公鑰簽名體系應(yīng)用的是指數(shù)型算法，會(huì)嚴(yán)重影響算法性能，而消息認(rèn)證碼使用對(duì)稱加密方式，算法性能比前者提高了3個(gè)數(shù)量級(jí)。使用消息認(rèn)證碼技術(shù)，當(dāng)出現(xiàn)時(shí)鐘同步中的拜占庭故障時(shí).可在整個(gè)系統(tǒng)網(wǎng)絡(luò)中利用該算法找出系統(tǒng)中的故障節(jié)點(diǎn)，并將其屏蔽掉，在確保達(dá)到時(shí)鐘同步穩(wěn)定性的同時(shí)，消除拜占庭故障的不良影響，進(jìn)而從根本上實(shí)現(xiàn)容忍時(shí)鐘同步中的拜占庭故障。

1 FlexRay時(shí)鐘同步機(jī)制

時(shí)鐘同步的目的在于使物理或邏輯時(shí)鐘維持在一個(gè)全局一致的狀態(tài)，從而令系統(tǒng)中的信息、事件以及節(jié)點(diǎn)中與時(shí)間有關(guān)的行為有一個(gè)全局一致的解釋，保證系統(tǒng)中各節(jié)點(diǎn)的通信在時(shí)間邏輯上是完全正確的。FlexRav協(xié)議的靜態(tài)段采用基于TDMA的工作方式，節(jié)點(diǎn)在發(fā)送報(bào)文前就已知道了報(bào)文的確切發(fā)送時(shí)間，而接收節(jié)點(diǎn)也知道報(bào)文接收時(shí)間。FlexRay協(xié)議之所以能夠提前得知報(bào)文發(fā)送與到達(dá)時(shí)間，并能保證系統(tǒng)的準(zhǔn)確性，關(guān)鍵在于整個(gè)通信簇有一個(gè)共同的時(shí)間標(biāo)準(zhǔn)。因此，每個(gè)節(jié)點(diǎn)都必須保證時(shí)間同步，并且每個(gè)節(jié)點(diǎn)之間的最大偏差必須在限定范圍內(nèi)，這是實(shí)現(xiàn)時(shí)鐘同步的前提，最大偏差也稱為精度。

FlexRay協(xié)議采用分布式時(shí)鐘同步機(jī)制，在該機(jī)制中每個(gè)節(jié)點(diǎn)通過其它節(jié)點(diǎn)發(fā)送的同步幀觀測(cè)它們的時(shí)鐘計(jì)時(shí)，從而使各自與節(jié)點(diǎn)簇同步。FlexRay節(jié)點(diǎn)內(nèi)的時(shí)間表示法是在周期cycle、最大時(shí)鐘節(jié)拍MT（ Macrotick）和最小時(shí)鐘節(jié)拍（ Microtick）基礎(chǔ)上建立的。MT在節(jié)點(diǎn)簇范圍的基礎(chǔ)上進(jìn)行同步。在容忍誤差范圍內(nèi)，節(jié)點(diǎn)簇中所有同步節(jié)點(diǎn)的MT持續(xù)時(shí)間相同。每個(gè)節(jié)點(diǎn)MT包含Microtick的數(shù)量取決于每個(gè)節(jié)點(diǎn)的振蕩器頻率和預(yù)計(jì)數(shù)器，所以雖然各同步節(jié)點(diǎn)的MT時(shí)間相同，但各自MT包含的Microtick數(shù)量可能不同。

FlexRav時(shí)鐘同步主要包含兩個(gè)并發(fā)進(jìn)程：時(shí)鐘同步進(jìn)程（Clock Synchronization Process，簡稱CSP）和宏節(jié)拍生成進(jìn)程（Macrotick Generation Process，簡稱MTC）。CSP主要實(shí)現(xiàn)循環(huán)開始時(shí)的初始化，測(cè)量并存儲(chǔ)偏差值，同時(shí)計(jì)算相位修正值和速率修正值;MTG控制循環(huán)計(jì)數(shù)器和宏節(jié)拍計(jì)數(shù)器，并運(yùn)用相位修正值和速率修正值調(diào)整時(shí)間。具體時(shí)鐘同步過程如圖1所示。

時(shí)鐘同步功能的主要作用是使簇中各節(jié)點(diǎn)之間的時(shí)間偏差保持在精密度范圍之內(nèi)。時(shí)間偏差分為兩種：相位偏差（ Offset Difference）和速率偏差（Rate Difference）。相位偏差是指兩個(gè)時(shí)鐘在某個(gè)特定時(shí)間的絕對(duì)差別;速率偏差是指相位偏差隨著時(shí)間推移的變化，其反映了相位偏差在特定時(shí)間的變化，分別運(yùn)用相位修正（ Offset Correction）和速率修正（Rate Correction）使不同節(jié)點(diǎn)的本地時(shí)基保持同步[12-13]。

2 FlexRay時(shí)鐘同步拜占庭容錯(cuò)算法

2.1 拜占庭時(shí)鐘故障

在分布式實(shí)時(shí)系統(tǒng)中，若有3個(gè)節(jié)點(diǎn)A、B、C，如果A、B是正常節(jié)點(diǎn)，而C是“兩面性”惡性故障節(jié)點(diǎn)，如：C節(jié)點(diǎn)告知A節(jié)點(diǎn)此刻時(shí)間為4：00，卻告知B節(jié)點(diǎn)此刻是4：05。由于C節(jié)點(diǎn)的“叛徒”行為，從而影響了整個(gè)系統(tǒng)時(shí)鐘的準(zhǔn)確性。這種惡性的兩面性行為稱為惡性錯(cuò)誤或拜占庭錯(cuò)誤[14]，如圖2所示。

對(duì)于基于FlexRay總線的分布式實(shí)時(shí)系統(tǒng)，導(dǎo)致拜占庭時(shí)鐘故障的原因可能是由于系統(tǒng)中元器件出現(xiàn)故障，或節(jié)點(diǎn)在信息交換過程中發(fā)生故障，從而隨機(jī)發(fā)送各種錯(cuò)誤消息，使得其它正常節(jié)點(diǎn)收到錯(cuò)誤信息后作出錯(cuò)誤判斷，進(jìn)而影響整個(gè)系統(tǒng)的時(shí)鐘同步。

2.2 拜占庭故障算法充分條件

對(duì)于拜占庭故障可概括為：所有正常節(jié)點(diǎn)都可以讓其余節(jié)點(diǎn)接收到其真實(shí)消息，并且最終會(huì)一致采取正確措施，即拜占庭故障容錯(cuò)算法是一個(gè)關(guān)于一致性與正確性的算法問題。該算法針對(duì)的是正常節(jié)點(diǎn)，因?yàn)榘菡纪ス?jié)點(diǎn)可以采取任何無法預(yù)估的行動(dòng)，所要做的就是在有拜占庭節(jié)點(diǎn)干擾的情況下，研究出抗干擾算法。

下面以拜占庭將軍問題原型為例，為方便描述，給出如下定義：

變量Vi：為i個(gè)將軍發(fā)給其他將軍的命令值，并將其自身判斷記為Vi。

向量（V1，V2，…，Vn）：表示大多數(shù)將軍的意見，將軍們會(huì)通過函數(shù)處理該向量后將處理結(jié)果作為最終采用的意見。

條件1：所有忠誠的將軍們必須擁有相同向量（V1，V2，…，Vn）。

（2）正確性。

條件2：對(duì)于忠誠的將軍i，其余所有忠誠將軍們的Vi必須是將軍i發(fā)送的值。

將問題簡化為司令一副官模型，可得到以下充分條件：

IC1（一致性）：每個(gè)忠誠副官必須遵守同一條命令。

IC2（正確性）：對(duì)于忠誠的司令，所有忠誠的副官們都必須遵守司令發(fā)送的命令。

要簡化成司令一副官模型，只需將司令遍歷各個(gè)將軍，便得到一個(gè)完整的關(guān)于分布式系統(tǒng)中的拜占庭問題，而其采用的算法可以是完全一致的。IC1和IC2構(gòu)成解決拜占庭問題的充分條件。在接下來的工作中，解決拜占庭問題的算法只要能夠滿足上述充分條件，則表明該算法是有效、可行的拜占庭故障容錯(cuò)算法[14]。

2.3 FlexRayBFT算法

在對(duì)口頭協(xié)議算法OM（m）、簽署協(xié)議算法SM（m）、公鑰簽名體系等算法研究基礎(chǔ)上，結(jié)合FlexRay總線通信協(xié)議，并引入消息驗(yàn)證碼對(duì)消息進(jìn)行認(rèn)證，從而改進(jìn)算法性能，提升系統(tǒng)的實(shí)時(shí)性與可靠性，改進(jìn)算法被稱為FlexRay-BFT算法。

通過對(duì)消息或與消息有關(guān)的信息進(jìn)行加密或簽名變換所進(jìn)行的認(rèn)證稱為消息認(rèn)證。消息認(rèn)證的目的主要為了防止消息在傳輸或存儲(chǔ)時(shí)被有意、無意地篡改，其認(rèn)證主要包括消息內(nèi)容認(rèn)證（即消息完整性認(rèn)證）、消息源和宿認(rèn)證（身份認(rèn)證），以及消息序號(hào)和操作時(shí)間認(rèn)證等。將密鑰與需要驗(yàn)證的信息經(jīng)函數(shù)處理后得到消息認(rèn)證碼，當(dāng)消息接收者擁有相應(yīng)密鑰時(shí)，則可判斷出消息內(nèi)容是否被篡改。消息認(rèn)證碼不同于公鑰簽名，消息認(rèn)證碼的生成與驗(yàn)證使用同一個(gè)密鑰，而公鑰簽名采用私鑰簽名、公鑰加密的方式。公鑰簽名使用非對(duì)稱加密方式，且屬于指數(shù)型算法，會(huì)嚴(yán)重影響算法性能，從而使拜占庭算法無法在實(shí)際工程領(lǐng)域得到應(yīng)用。消息認(rèn)證碼使用對(duì)稱加密方式，算法性能相比前者提升了3個(gè)數(shù)量級(jí)，因此相對(duì)而言使用消息認(rèn)證碼的算法更具有可行性。由于消息認(rèn)證碼需要相同密鑰，所以消息發(fā)送方和接收方需要在通信開始前對(duì)密鑰達(dá)成一致。消息認(rèn)證過程如圖3所示。

在使用消息認(rèn)證碼之前，需要保證所有節(jié)點(diǎn)計(jì)算能力是有限的，并且不存在兩條消息經(jīng)消息認(rèn)證碼算法運(yùn)算得到的消息認(rèn)證碼是相同的，即保證消息認(rèn)證碼算法是安全的。在此前提下，發(fā)送節(jié)點(diǎn)將經(jīng)消息認(rèn)證碼算法處理得到的消息認(rèn)證碼與消息發(fā)送給接收節(jié)點(diǎn)，接收節(jié)點(diǎn)在接收這些信息后，使用事先已達(dá)成一致的密鑰和算法得到用于驗(yàn)證的消息認(rèn)證碼，并將其與接收到的認(rèn)證碼進(jìn)行對(duì)比判斷。若相同，則表明消息是完整的，即在傳輸過程中消息沒有被改動(dòng)，且發(fā)送節(jié)點(diǎn)認(rèn)證通過，消息內(nèi)容以及消息源和宿認(rèn)證通過;若不同，則表明消息是不完整的，即消息在傳輸過程中被改動(dòng)，或發(fā)送節(jié)點(diǎn)被冒充等，接收節(jié)點(diǎn)不接收，消息則不會(huì)進(jìn)入下一過程進(jìn)行處理。

2.4 FlexRayBFT算法分析及過程

FlexRay分布式拜占庭容錯(cuò)系統(tǒng)模型如圖4所示。總線傳輸速率為2.5Mbit/s，報(bào)文可在A、B雙通道同時(shí)傳輸，單個(gè)通信周期總長度為Sms。

2.4.1 FlexRayBFT準(zhǔn)備階段

當(dāng)節(jié)點(diǎn)Ni準(zhǔn)備發(fā)送消息m Ni時(shí)，其會(huì)將當(dāng)前循環(huán)的編號(hào)k（0≤k≤63）加入該信息前作為編號(hào)，然后將m-Ni經(jīng)消息認(rèn)證碼算法處理得到的消息摘要d與自己的節(jié)點(diǎn)標(biāo)號(hào)i（即節(jié)點(diǎn)身份ID）加入上述消息m Ni中，形成準(zhǔn)備發(fā)給其余n-l個(gè)節(jié)點(diǎn)的消息，稱為準(zhǔn)備消息Prepare_MshNi。鑒于在FlexRay分布式系統(tǒng)中往往有多個(gè)接收節(jié)點(diǎn)，故進(jìn)一步引入消息認(rèn)證碼向量，表示為（k）ij，1 ≤j≤n，且j≠i。準(zhǔn)備消息Prepare_MshNi格式如圖5所示。

在該階段，所有節(jié)點(diǎn)會(huì)獲得來自其余節(jié)點(diǎn)的準(zhǔn)備消息，當(dāng)某節(jié)點(diǎn)收到2f條與m N、k以及i相匹配的準(zhǔn)備消息，則該節(jié)點(diǎn)獲得了一個(gè)關(guān)于準(zhǔn)備消息的消息集，稱為準(zhǔn)備消息集。準(zhǔn)備階段如圖6所示。

該算法由于加入了循環(huán)編號(hào)k，保證系統(tǒng)不會(huì)受到重放攻擊，即有其它循環(huán)消息或之前執(zhí)行過的消息冒充當(dāng)前循環(huán)消息發(fā)送而擾亂系統(tǒng)。

2.4.2 回復(fù)執(zhí)行階段

在回復(fù)執(zhí)行階段，節(jié)點(diǎn)會(huì)向其余各節(jié)點(diǎn)發(fā)送回復(fù)消息，記為Reply_MsgNi，告知其余節(jié)點(diǎn)其已經(jīng)有了準(zhǔn)備消息集?；貜?fù)消息格式與準(zhǔn)備消息格式類似，包括當(dāng)前循環(huán)編號(hào)k、消息摘要d、自身節(jié)點(diǎn)標(biāo)號(hào)i以及準(zhǔn)備消息集?；貜?fù)消息Reply_MsgNi格式如圖7所示。

每個(gè)節(jié)點(diǎn)都會(huì)接收這條消息，直至節(jié)點(diǎn)獲得一個(gè)關(guān)于回復(fù)消息的消息集，稱為回復(fù)消息集。回復(fù)消息集所具備的條件為：至少應(yīng)包含2f+1條回復(fù)消息（包括節(jié)點(diǎn)本身在內(nèi)），且每條回復(fù)消息的循環(huán)編號(hào)后和d皆需一一對(duì)應(yīng)。當(dāng)節(jié)點(diǎn)擁有回復(fù)消息集時(shí)，則回復(fù)完成，也為算法執(zhí)行作好了準(zhǔn)備?；貜?fù)階段如圖8所示。

算法執(zhí)行階段利用網(wǎng)絡(luò)空閑時(shí)間（NIT），即將對(duì)每個(gè)節(jié)點(diǎn)接收到回復(fù)決議證書的處理放于NIT。各節(jié)點(diǎn)會(huì)利用得到的回復(fù)消息集，通過校驗(yàn)之后得到一個(gè)消息向量表。假設(shè)n節(jié)點(diǎn)是拜占庭故障節(jié)點(diǎn)，對(duì)于節(jié)點(diǎn)1，其向量如表1所示。

綜上可知，所有正常節(jié)點(diǎn)采用的命令都是A，即滿足IC1（一致性），并且通過將主節(jié)點(diǎn)遍歷各個(gè)節(jié)點(diǎn)，發(fā)現(xiàn)與正常主節(jié)點(diǎn)保持一致，即滿足IC.（正確性）。對(duì)于節(jié)點(diǎn)為n時(shí)（對(duì)應(yīng)主節(jié)點(diǎn)為故障節(jié)點(diǎn)）都一致采取R（撤退）命令，即滿足IC，（一致性）。對(duì)應(yīng)FlexRay分布式系統(tǒng)中的執(zhí)行措施即為故障節(jié)點(diǎn)屏蔽措施，即將節(jié)點(diǎn)n屏蔽掉。所謂故障屏蔽技術(shù)，即假設(shè)該錯(cuò)誤節(jié)點(diǎn)之后發(fā)送的所有消息皆為空，或不接受該錯(cuò)誤節(jié)點(diǎn)的消息。

對(duì)于一個(gè)擁有n個(gè)節(jié)點(diǎn)的FlexRay分布式系統(tǒng)，可通過執(zhí)行FlexRayBFT算法確保其各節(jié)點(diǎn)的時(shí)鐘同步。假設(shè)一個(gè)FlexRay分布式系統(tǒng)擁有4個(gè)節(jié)點(diǎn)NodeA、NodeB、NodeC、NodeD，其中NodeB是拜占庭節(jié)點(diǎn)。對(duì)于執(zhí)行時(shí)鐘同步時(shí)，zPrimaryTRP（在時(shí)鐘同步中表示的是同步幀的實(shí)際到達(dá)時(shí)刻）使用的是上一輪保存的值，此處時(shí)鐘同步方法類似于相位修正時(shí)的時(shí)鐘同步方法，則節(jié)點(diǎn)A觀察到的時(shí)鐘消息向量如表2所示。

其中，DevAf表示節(jié)點(diǎn)A與i之間的時(shí)間偏差，且Dev Value= zPrimary TRP - zActionPoint，zActionPoint表示時(shí)鐘同步幀的理想到達(dá)時(shí)刻。

表2中各數(shù)字皆表示時(shí)刻，由表2可知節(jié)點(diǎn)A的時(shí)間偏差序列為：

zlist_A={DevAA，DevAC，DevAD}

（8）

根據(jù)FTM算法會(huì)得到一個(gè)最終的zCorrectValue，即修正值以調(diào)整節(jié)點(diǎn)A的時(shí)鐘，確保A的時(shí)鐘同步?；貜?fù)執(zhí)行階段如圖9所示。

整個(gè)FlexRayBFT算法執(zhí)行過程如圖10所示。

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

基于所搭建的FlexRay線控轉(zhuǎn)向系統(tǒng)模型與Truetime工具箱，將提出的FlexRayBFT算法移人系統(tǒng)中，并對(duì)系統(tǒng)進(jìn)行仿真測(cè)試。首先，在不將FlexRayBFT算法加入系統(tǒng)，即不執(zhí)行FlexRayBFT算法時(shí)，運(yùn)行系統(tǒng)模型。系統(tǒng)受拜占庭節(jié)點(diǎn)干擾后，各節(jié)點(diǎn)FlexRay總線通信信號(hào)及時(shí)鐘運(yùn)行情況分別如圖11、圖12所示。

圖11、圖12中從下往上依次為傳感器的FlexRay總線信號(hào)及時(shí)鐘運(yùn)行情況、控制器的FlexRav總線信號(hào)及時(shí)鐘運(yùn)行情況、執(zhí)行器的FlexRav總線信號(hào)及時(shí)鐘運(yùn)行情況、拜占庭節(jié)點(diǎn)的FlexRay總線信號(hào)及時(shí)鐘運(yùn)行情況。從圖中可以看出，受拜占庭節(jié)點(diǎn)影響，各節(jié)點(diǎn)通信都是雜亂無章的，無法進(jìn)行正常的通信及時(shí)鐘同步。

FlexRay線控轉(zhuǎn)向系統(tǒng)在受拜占庭故障干擾的情況下，控制器、傳感器節(jié)點(diǎn)及執(zhí)行器節(jié)點(diǎn)輸出信號(hào)如圖13所示。

在將FlexRayBFT算法加入系統(tǒng)，即執(zhí)行FlexRayBFT算法后，運(yùn)行系統(tǒng)模型。系統(tǒng)克服拜占庭節(jié)點(diǎn)干擾后，各節(jié)點(diǎn)的FlexRay總線通信信號(hào)及時(shí)鐘運(yùn)行情況分別如圖14、圖15所示。

圖14、圖15中從下往上依次為傳感器的FlexRav總線信號(hào)及時(shí)鐘運(yùn)行情況、控制器的FlexRay總線信號(hào)及時(shí)鐘運(yùn)行情況、執(zhí)行器的FlexRay總線信號(hào)及時(shí)鐘運(yùn)行情況、拜占庭節(jié)點(diǎn)的FlexRay總線信號(hào)及時(shí)鐘運(yùn)行情況。

從兩幅圖中可以清楚看出，在執(zhí)行FlexRayBFT算法后，圖14中的拜占庭節(jié)點(diǎn)信號(hào)消失，成功被算法屏蔽，所以在圖15中，也就不存在拜占庭節(jié)點(diǎn)時(shí)鐘。當(dāng)故障節(jié)點(diǎn)被屏蔽后，剩下的正常節(jié)點(diǎn)傳感器、執(zhí)行器、控制器各節(jié)點(diǎn)則可進(jìn)行正常的通信及時(shí)鐘同步。

FlexRay線控轉(zhuǎn)向系統(tǒng)在克服拜占庭故障后，控制器、傳感器節(jié)點(diǎn)及執(zhí)行器節(jié)點(diǎn)輸出信號(hào)如圖16所示。在克服了故障節(jié)點(diǎn)影響后，各信號(hào)波形趨于穩(wěn)定。

從以上執(zhí)行FlexRayBFT算法的前后仿真圖對(duì)比可知，通過執(zhí)行FlexRayBFT算法可以有效克服FlexRav線控轉(zhuǎn)向系統(tǒng)中時(shí)鐘同步的拜占庭故障。

4 結(jié)語

本文針對(duì)FlexRav時(shí)鐘同步中的拜占庭故障，提出一種有效的解決算法FlexRayBFT。基于所搭建的FlexRav線控轉(zhuǎn)向系統(tǒng)模型與Truetime工具箱，將提出的FlexRay-BFT算法移人系統(tǒng)中并對(duì)系統(tǒng)進(jìn)行仿真測(cè)試。通過對(duì)仿真結(jié)果的分析可知，經(jīng)過FlexRavBFT算法處理后，可以有效克服FlexRay線控轉(zhuǎn)向系統(tǒng)中時(shí)鐘同步的拜占庭故障，并確保FlexRay分布式系統(tǒng)中各節(jié)點(diǎn)的時(shí)鐘同步以及正常運(yùn)行。通過該研究，對(duì)于拜占庭容錯(cuò)算法以及FlexRav協(xié)議的時(shí)鐘同步過程有了更深入的理解。本文在應(yīng)用消息認(rèn)證碼方法的基礎(chǔ)上，成功實(shí)現(xiàn)了對(duì)拜占庭故障的容忍，從而提高了系統(tǒng)性能。在今后的研究中，可以嘗試?yán)^續(xù)提高消息認(rèn)證碼的性能，從而對(duì)時(shí)鐘拜占庭故障容錯(cuò)算法性能作進(jìn)一步優(yōu)化。

參考文獻(xiàn)

[1]LAMPORT L. Time， clock and the ordering of events in a distributed system[J]. Communication of the ACM. 1987（ 21 ） ： 558-565.

[2]LAMPORT L， MELLIAR-SMITH P M. Synchronizing clocks in thepresence of faults[J]. Journal of the ACM. 1985 ， 32 （ I ） ： 52-78.

[3]LAMPORT L. The Byzantine general prohlem [J] . ACM Transactionon Programming Languages and Systems， 1982， 4 （ 3 ） ： 382-401.

[4]YAMASHITA T， ONO S. A statistical time synchronization method forfrequency-synchronized net，vork clocks in distributed systems [ J] . IE -ICE Transactions on information and Systems .2004 （ 7） ： 1878-1886.

[5]RAMANATHAN P， KANDLUR D D， SHIN K C. Hardware-assistedsoftware clock synchronization for homogeneous distributed systems[J]. IEEE Transactions on Computers ， 1990， 39（4） ： 514-524.

[6]SHIN K G， RAMANATHAN P. Transmission delays in hardware clocksynchronization [J] . IEEE Transactions on Computers ， 1988 . 37 （ 1 I ） ：1465-1467.

[7]FELDMAN P. MICALI S. An optimal probabilistic protocol for syn-chronous byzantine Agreement [J].SIAM Journal on Computing，1997，26（4） ： 873-933.

[8]MALKHI D. REITER M. Byzantine quorum system [J]. Journal of Dis-tributed Computing， 1998 ， 11（ 4） ： 203-213.

[9]CASTRO M ， LISKOV B. Proactive recovery in a Byzantine tolerant sys-tem [C]. In Proceedings of the Fourth Symposium on Operating Sys-tems Design and Implementation（ OSDI） . 2000.

[10]CASTRO M . LISKOV B. Practical Byzantine fault tolerance [ C]. InThird Symposium on Operating systems Design and Implementation（ OSDI） . 1999.

[11]CASTRO M. LISKOV B. Practical Byzantine fault tolerance and pro-active recovery [J] . ACM Transactions on Computer Systems ， 2002 ， 20（ 4） ： 398-461.

[12]張鳳登.現(xiàn)場總線技術(shù)用 [ M].北京 ：科學(xué)出版社 ， 2008.

[13] 張鳳登.實(shí)時(shí)傳輸網(wǎng)絡(luò) FlexRay原理與規(guī)范 [ M].北京 ：電 子-工業(yè)出版社 ， 2017.

[14] 張鳳登，分布式實(shí)時(shí)系統(tǒng)[M].北京：科學(xué)出版社，2014.

基金項(xiàng)目：上海市自然科學(xué)基金項(xiàng)目（ 15ZR1429300）

作者簡介：劉讓（1994-），男，上海理工大學(xué)光電信息與計(jì)算機(jī)工程學(xué)院碩士研究生，研究方向?yàn)槠囯娮印F(xiàn)場總線、嵌入式系統(tǒng);張鳳登（1963-），男，博士，上海理工大學(xué)光電信息與計(jì)算機(jī)工程學(xué)院教授、博士生導(dǎo)師，研究方向?yàn)榉植际较到y(tǒng)、過程控制、現(xiàn)場總線。