分布式嵌入系統(tǒng)的交互一致理論

　　許多應(yīng)用與人身安全或設(shè)備安全有密切聯(lián)系，隨著安全性要求的提高，希望設(shè)備或系統(tǒng)在其構(gòu)成的部件與控制裝置發(fā)生故障時仍能保證安全，即故障-安全(failsafe)的特性。系統(tǒng)是由子系統(tǒng)組成的，子系統(tǒng)有故障時有控制地停止工作(failsilent，故障-靜默模式)，對系統(tǒng)而言仍是故障，因為它不再提供原定的服務(wù)了，這有可能引起全系統(tǒng)功能的失效。所以，安全是要從最高層的全局來分析的。例如對一輛汽車，剎車系統(tǒng)整體不能用故障-靜默來達(dá)到安全，而應(yīng)該是故障后仍能工作(failoperatiONal，故障-仍工作模式)，或至少是性能下降一點(diǎn)仍能工作(faildegraded，故障-降格工作模式)。

　　單一部件的架構(gòu)(包括硬件與軟件)有故障而失效時就無法繼續(xù)提供服務(wù)了，它不能滿足故障-仍工作模式或故障-降格工作模式的要求。這就必須采用有備份的冗余架構(gòu)，每一個備份都能完成出故障的原來部件的大部分或全部服務(wù)工作，維持系統(tǒng)正常運(yùn)行。備份工作的交替就要求它們對工作狀態(tài)(系統(tǒng)的輸入、應(yīng)該的輸出和誰不該輸出)有相同的看法。這種相同的看法要通過信息交換并通過協(xié)議才能建立，并稱為交互一致性(interactive consiSTency)。

　　有一部分控制對象存在功能上互為冗余的可能性，例如汽車的4個輪子的剎車，當(dāng)一個輪子的子剎車系統(tǒng)(設(shè)備或控制裝置)有故障時，修正其他輪子的剎車力便可以實現(xiàn)總體剎車系統(tǒng)的故障-仍工作模式或故障-降格工作模式。此時對單個輪子而言，它只要能實現(xiàn)故障-靜默即可。顯然，單個輪子的可信賴性要求被降低，會造成成本的大大降低。在這種情況下，輪子的控制器之間就存在交互一致性問題。

　　來自汽車電子大佬Infineon和Delphi的研究報告[1]比較了基于這種互為冗余的分布式冗余剎車系統(tǒng)與集中式僅控制器冗余的硬件成本，指出成本可大為下降，并稱集中式有控制器冗余的剎車系統(tǒng)將會廢止，這對我國汽車電子業(yè)者有警示意義。不過，該文并未提到用硬件集中方案也可實現(xiàn)對象互為冗余的剎車系統(tǒng)(這二種方案成本差別將不會太大)。此時由于通信有較大不同，交互一致性問題會不一樣，加上其他因素，它們的優(yōu)劣有待研究。但至少分布式互為冗余剎車系統(tǒng)是一個備選方案。參考文獻(xiàn)[1]非常概述地提及了控制方案，并未談及技術(shù)細(xì)節(jié)以及采用的協(xié)議。本文將根據(jù)交互一致性的理論，對實施這類應(yīng)用中可能遇到的問題進(jìn)行分析。

　　1 SM算法

　　對交互一致性的研究已經(jīng)有30年了，它被稱為拜占庭將軍問題算法(Byzentine Generals Problem)。原始文獻(xiàn)有2個版本[23]，1980年的文章引用很多，但是公認(rèn)很難讀懂[4]。原來的討論是針對點(diǎn)對點(diǎn)通信進(jìn)行的，本文根據(jù)對參考文獻(xiàn)[3]的理解，針對總線方式通信加以展開，這會引入作者的看法。參考文獻(xiàn)[3]提出：一個冗余系統(tǒng)的“所有無錯節(jié)點(diǎn)應(yīng)該采用同樣的輸入(這樣才能產(chǎn)生同樣的輸出);如果輸入系統(tǒng)沒錯，就應(yīng)該采用輸入的值(這樣才能產(chǎn)生正確的輸出)”。參考文獻(xiàn)[3]提供了二種解決算法：一是口傳消息算法OM(Oral Message Algorithm)，二是簽名消息算法SM(Signed Message Algorithm)。對容許m個錯而言，OM算法需要3m+1個節(jié)點(diǎn)以及m+1輪消息傳送，SM需要m+2個節(jié)點(diǎn)和m+1輪消息傳送。這是2種原理與性能有很大差別的算法。OM算法依靠消息轉(zhuǎn)述與表決來確定從節(jié)點(diǎn)的輸入，當(dāng)無法進(jìn)行表決時要采取預(yù)定義的缺省輸入。當(dāng)主節(jié)點(diǎn)有拜占庭錯且錯值占多數(shù)時，無錯的從節(jié)點(diǎn)間看法雖是一致的，但是是不正確的。SM算法依靠逐級檢驗與重復(fù)轉(zhuǎn)發(fā)，可以發(fā)現(xiàn)各節(jié)點(diǎn)(包括主節(jié)點(diǎn))的錯，而且只要有一次正確收到就可以了。由于性能好且需要的從節(jié)點(diǎn)數(shù)較少，SM值得進(jìn)一步探究。下面以總線通信時的情況來介紹SM的做法。

　?、?對需要交換數(shù)據(jù)并保證一致的n=m+2個節(jié)點(diǎn)而言，可將問題作分解，每個節(jié)點(diǎn)可輪流作為主節(jié)點(diǎn)對其他節(jié)點(diǎn)傳送消息，實施SM算法。

　　② 每個通信幀含有兩部分內(nèi)容：數(shù)據(jù)d和與d有關(guān)的簽名a。根據(jù)參考文獻(xiàn)[3]，簽名要不被有錯節(jié)點(diǎn)作偽，應(yīng)該各節(jié)點(diǎn)各不相同且每次都不同。筆者認(rèn)為根據(jù)工業(yè)應(yīng)用可以不這樣要求，詳見后文。

　?、?通信各輪的幀內(nèi)容如下：

　　第1輪，主節(jié)點(diǎn)發(fā)自己的數(shù)據(jù)與簽名(d:a0);

　　第2輪，各從節(jié)點(diǎn)轉(zhuǎn)發(fā)由第1輪收到的幀再加自己的簽名((d:a0):aj)，其中 (j=1，…，n-1);

　　以后各輪，各從節(jié)點(diǎn)轉(zhuǎn)發(fā)由上一輪收到的幀再加自己的簽名((…((d:a0):aj)…):ar)，其中 (j,…,r∈{1,…,n-1}; j≠…≠r)，也就是說已經(jīng)經(jīng)過本從節(jié)點(diǎn)轉(zhuǎn)發(fā)的內(nèi)容不再轉(zhuǎn)發(fā)。

　　由于是通過總線廣播而不是點(diǎn)到點(diǎn)通信，通信量只要計算不同的幀的個數(shù)就可以:N=1+(n-1)+(n-1)2+…。總的通信輪數(shù)為m+1。

　?、?每個從節(jié)點(diǎn)保存一個供選擇的集choice，初始化時為空：choice{Φ}。choice的更新可在m+1輪通信結(jié)束之后進(jìn)行。更新時先檢驗簽名的有效性，只有全為有效的才可把該幀的d添加到choice中，如果choice中已有，就不重復(fù)添加。點(diǎn)對點(diǎn)通信按參考文獻(xiàn)[3]的做法，出現(xiàn)主節(jié)點(diǎn)錯時choice會有多個元素，總線通信時主節(jié)點(diǎn)的簽名計算只有一次，按本文做法(見下文)choice只會有一個元素(真值或空)。

　?、?參考文獻(xiàn)[3]證明了在下列假設(shè)得到保證的條件下所有無故障從節(jié)點(diǎn)會得到相同的choice：

　　A1發(fā)送的消息總能正確送達(dá);

　　A2每個節(jié)點(diǎn)知道誰在發(fā)送;

　　A3消息的缺失可以檢測出來;

　　A4簽名不能被作偽，作偽時可檢測出來;

　　任何從節(jié)點(diǎn)能檢測出簽名是否有錯。

　　SM算法的有效性與此有關(guān)，通信時發(fā)生錯幀漏檢的情況相當(dāng)于發(fā)生一次錯，要在容錯的次數(shù)設(shè)計上加以考慮。

　　建議了一個簽名的方法例子，即用密鑰ki對數(shù)據(jù)d求出簽名a: a=(ki·d)mod p，其中p是2的冪，ki是小于p的一個奇數(shù)，接收節(jié)點(diǎn)用另一個密鑰ki-1驗證：d=(ki-1·a)mod p。ki和ki-1有如下關(guān)系：(ki·ki-1)mod p="1"。這樣，有錯節(jié)點(diǎn)能作偽的概率為1/p。這種方案作偽者要不知道加密的辦法才行。參考文獻(xiàn)[3]認(rèn)為要求更嚴(yán)的場合要采用密碼學(xué)的方法。

　　從工業(yè)應(yīng)用來看，有錯節(jié)點(diǎn)的作偽的可能性來源乃是電磁干擾，對人為的黑客攻擊應(yīng)另外采用對抗措施，所以可以采用較為簡單常用的CRC校驗和作為簽名。注意，這個CRC校驗和是應(yīng)用數(shù)據(jù)的校驗和，不要混同于通信幀的校驗和。在冗余系統(tǒng)里關(guān)心的是應(yīng)用數(shù)據(jù)的一致性，而應(yīng)用數(shù)據(jù)在MCU與通信控制器的傳遞過程中可能出錯，通信幀的CRC校驗不能覆蓋這一錯。例如，應(yīng)用通過FlexRay的二個通道傳送同一數(shù)據(jù)時，由于寫入輸出緩沖器的過程是分時的，如果其中一次受到干擾，應(yīng)用數(shù)據(jù)與應(yīng)用CRC(簽名)不再匹配，那么接收方將能發(fā)現(xiàn)應(yīng)用數(shù)據(jù)的傳送錯而加以丟棄。

　　在總線廣播通信中，由于各節(jié)點(diǎn)受干擾請況的不同，它們可能接收到不同的幀，一旦又發(fā)生了錯幀漏檢，那么就會發(fā)生一個節(jié)點(diǎn)給其他節(jié)點(diǎn)送不同值的情況，這與點(diǎn)到點(diǎn)通信的情況一樣，是一種拜占庭錯。同時，轉(zhuǎn)發(fā)過程又涉及MCU與通信控制器的傳遞過程，其中也會發(fā)生錯，所以轉(zhuǎn)發(fā)過程也用數(shù)據(jù)加簽名的方式。例如節(jié)點(diǎn)p在第3輪收到幀(((d:a0):aj):ai)時，檢驗ai的簽名是否正確，如果錯，那么在節(jié)點(diǎn)j到i的轉(zhuǎn)發(fā)通信中有錯。如無錯，繼續(xù)對((d:a0):aj)作aj簽名的檢驗，如果錯，那么在節(jié)點(diǎn)0到j(luò)的轉(zhuǎn)發(fā)通信中有錯。如無錯，再對(d:a0)作a0簽名的檢驗，如果錯，那么在節(jié)點(diǎn)0的MCU與節(jié)點(diǎn)0的通信控制器通信中發(fā)生了錯，或者它在計算簽名時發(fā)生了錯。

　　未通過簽名檢驗的數(shù)據(jù)將不提交到choice，如果主節(jié)點(diǎn)無錯，從節(jié)點(diǎn)有m+1個，那么在第一輪中至少有一個從節(jié)點(diǎn)正確收到，在以后各輪中其他有錯節(jié)點(diǎn)的轉(zhuǎn)發(fā)將不會影響這個節(jié)點(diǎn)的choice?，F(xiàn)在可以發(fā)現(xiàn)SM算法的一個有趣的特性：如果某些從節(jié)點(diǎn)只是發(fā)生了瞬時故障，由于無錯節(jié)點(diǎn)的轉(zhuǎn)發(fā)，它仍然有機(jī)會得到相同的choice。

　　由于采用總線廣播，主節(jié)點(diǎn)可以收到被轉(zhuǎn)發(fā)的自己的幀，因此可以進(jìn)行自檢。若全部轉(zhuǎn)發(fā)結(jié)束后自檢不通過，就可以采取進(jìn)一步的措施，例如本節(jié)點(diǎn)重算簽名并寫通信控制器，或者立即進(jìn)入故障-靜默模式。

　　SM算法假設(shè)幀的丟失可以檢測出來，這要靠另加的超時報警單元。一旦時間窗口關(guān)閉，各節(jié)點(diǎn)就根據(jù)已收到的各幀進(jìn)行choice的更新工作。

　　一次SM算法結(jié)束后就可認(rèn)為將開始新的一次SM算法，也就可以初始化choice。如果將每一個節(jié)點(diǎn)開始發(fā)本節(jié)點(diǎn)數(shù)據(jù)的次序固定下來，并將以前節(jié)點(diǎn)開始發(fā)轉(zhuǎn)發(fā)的時刻來預(yù)置本地定時器，那么在預(yù)定的時間窗口內(nèi)上一節(jié)點(diǎn)因故障而未轉(zhuǎn)發(fā)的錯誤可以被發(fā)現(xiàn)。上一節(jié)點(diǎn)轉(zhuǎn)發(fā)結(jié)束的信號或時限到可用來觸發(fā)本節(jié)點(diǎn)開始轉(zhuǎn)發(fā)。