ＮＭＲ及ＮＶＰ系統(tǒng)中表決算法分析與研究

（解放軍信息工程大學(xué) 電子技術(shù)學(xué)院， 鄭州 450004）



摘要：在N模冗余（NMR）及N版本編程技術(shù)（NVP）系統(tǒng)中，通過對冗余模塊的輸出執(zhí)行表決可以屏蔽子系統(tǒng)或部件產(chǎn)生的錯(cuò)誤，處理分布式計(jì)算系統(tǒng)中出現(xiàn)的Byzantine故障、同步多個(gè)計(jì)算進(jìn)程以及維護(hù)數(shù)據(jù)復(fù)制品一致性等；表決算法還可以用做某些容忍入侵應(yīng)用的觸發(fā)策略，發(fā)現(xiàn)故障并觸發(fā)故障部件的狀態(tài)恢復(fù)。在經(jīng)過對大量的表決算法分析與研究后，對其進(jìn)行歸類，并對每種類型中具有代表性的算法進(jìn)行了描述，指出它們的應(yīng)用領(lǐng)域，同時(shí)從復(fù)雜度及可靠性等方面對這些算法進(jìn)行橫向比較。

關(guān)鍵詞：容錯(cuò)；表決算法；N模冗余；N版本編程技術(shù)；三模冗余

中圖分類號(hào)：TP311文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001-3695(2008)11-3463-05



Research on voting algorithm in NMR and NVP system



YUAN Shun，GUO Yuan-bo，LIU Wei

(Institute of Electronic Technology， PLA Information Engineering University， Zhengzhou 450004， China)

Abstract:In N-modular redundant(NMR) and N-version programming(NVP)system， the fault of the subsystem (component)， the Byzantine failures of the distributed computing systems， clock synchronization between computing processors and the consistency of the replicated data objects could be handled by voting on the output of the redundant modules (versions). Moreover， the voting algorithm could be used as the trigger of some intrusion tolerance applications to find the fault component and drive it return to the normal state. Having surveyed a large number of references， the voting algorithms were classified， the typical algorithms of each category were described， application areas were proposed and the comparison of algorithm behavior were also survey based on the complexity and reliability.

Key words:fault-tolerant；voting algorithm；NMR；NVP；TMR

容錯(cuò)已經(jīng)在許多領(lǐng)域的高可靠控制中得到應(yīng)用，N模冗余（NMR）及N版本編程技術(shù)（NVP）是實(shí)現(xiàn)容錯(cuò)的兩個(gè)基本手段^[1，2]。在以往的文獻(xiàn)中已經(jīng)定義了許多表決算法，這些算法在屏蔽惡意子系統(tǒng)或部件錯(cuò)誤或Byzantine故障時(shí)都有各自的優(yōu)勢與不足。經(jīng)過對大量用于NMR及NVP系統(tǒng)的表決算法研究之后，分別從表決的相關(guān)概念、表決算法的執(zhí)行方式、應(yīng)用、分類及比較五個(gè)方面對其進(jìn)行了分析與研究。

1表決的相關(guān)概念

表決器是表決算法的執(zhí)行部件，具體實(shí)現(xiàn)表決算法規(guī)定的功能。通常表決器有多個(gè)冗余輸入，表決器從收到的多個(gè)冗余輸入中根據(jù)設(shè)定的表決條件（如表決門限值）產(chǎn)生一個(gè)結(jié)果作為表決輸出，該過程稱為表決。產(chǎn)生結(jié)果輸出的方式（融合或選擇）由具體的表決算法確定。

一致性協(xié)商(agreement)是指表決器的輸入即各冗余模塊（N版本程序或N個(gè)模塊）向表決器傳送的消息序列，設(shè)為{x1，x2，x3，…，xn}；又設(shè)任意兩個(gè)冗余模塊i和j向表決器輸入的值為xi，xj，門限值為t，若xi-xj≤t則冗余模塊i和j滿足一致性，否則為不滿足。表決器的門限值是表決過程中判斷任意兩個(gè)冗余模塊輸入值是否滿足一致性協(xié)商的基礎(chǔ)。

2表決算法的執(zhí)行方式

表決算法的執(zhí)行方式可以分為集中式與分布式兩種。集中式表決執(zhí)行方式如圖1所示，三個(gè)（重）數(shù)據(jù)處理模塊針對同樣的輸入執(zhí)行相同的功能，并將操作結(jié)果傳送到表決器，表決器在收到的結(jié)果中產(chǎn)生惟一輸出。集中式表決相對簡單，通信量小，執(zhí)行效率高。但是由于結(jié)構(gòu)中僅有一個(gè)表決部件，易形成單點(diǎn)故障，因而可靠性較差。

簡單的分布式表決結(jié)構(gòu)如圖2所示。系統(tǒng)中含有多個(gè)表決器。其中一個(gè)表決器作為主表決器，其余為備份表決器。各表決器均對冗余模塊的輸出執(zhí)行表決，系統(tǒng)將主表決器的輸出作為系統(tǒng)輸出。當(dāng)主表決器出現(xiàn)故障時(shí)，系統(tǒng)將切換到備份表決器。圖2中所示結(jié)構(gòu)的不足之處是：系統(tǒng)不能對表決器的運(yùn)行實(shí)施監(jiān)控，只有在主表決器出現(xiàn)顯式錯(cuò)誤時(shí)，系統(tǒng)才能執(zhí)行主—備表決器的切換，因此可靠性有所欠缺。

如圖3所示，為了提高系統(tǒng)可靠性，有的設(shè)計(jì)采用多級(jí)表決器結(jié)構(gòu)。在這種結(jié)構(gòu)中，后一級(jí)表決器對前一級(jí)表決器的輸出執(zhí)行表決，并最終產(chǎn)生輸出結(jié)果，同時(shí)對前一級(jí)表決器運(yùn)行期的可靠性實(shí)施監(jiān)控。

從圖2和3不難看出，分布式表決方式增加了系統(tǒng)結(jié)構(gòu)的復(fù)雜性及系統(tǒng)通信的復(fù)雜度，因而系統(tǒng)整體性能有所下降；另外由于在結(jié)構(gòu)中具備多個(gè)備份表決部件，相比集中式表決，分布式表決不易形成單點(diǎn)故障，可靠性更高。

3表決算法的應(yīng)用

表決是從多個(gè)不同版本程序或硬件模塊的不太可靠的冗余輸出中獲取高可靠或更精確的數(shù)據(jù)作為系統(tǒng)輸出的一種手段，因而它的應(yīng)用范圍比較廣泛。例如，在某些硬件系統(tǒng)的傳感器層，用于融合不同的傳感器傳送過來的數(shù)據(jù)產(chǎn)生一個(gè)輸出^[3~5]；在存儲(chǔ)系統(tǒng)的設(shè)計(jì)中，用于提高數(shù)據(jù)存儲(chǔ)及信息提取的可靠性^[6]；在某些高可靠系統(tǒng)的控制層（如機(jī)器人控制、導(dǎo)彈控制、航天飛控），用于目標(biāo)檢測^[7，8]、模式識(shí)別^[9]、數(shù)據(jù)校驗(yàn)^[10]等；在分布式系統(tǒng)中，用于多個(gè)數(shù)據(jù)復(fù)制品的一致性維護(hù)^[11~13]、處理Byzantine失效^[14]等問題；在容忍入侵系統(tǒng)中，用于故障部件的檢測，作為觸發(fā)器驅(qū)動(dòng)故障部件的狀態(tài)恢復(fù)^[15~18]；在復(fù)雜的數(shù)據(jù)圖像處理中，用于圖像數(shù)據(jù)的過濾、分割及其他的復(fù)雜計(jì)算^[19，20]；在帶有數(shù)字簽名機(jī)制的系統(tǒng)中，用于提高數(shù)字簽名的正確驗(yàn)證能力^[21]。

4表決算法的分類

1）硬件的或是軟件的表決算法可以基于軟件實(shí)現(xiàn)也可以基于硬件實(shí)現(xiàn)，兩者各有優(yōu)缺點(diǎn)。具體采用哪種實(shí)現(xiàn)方式取決于容錯(cuò)系統(tǒng)的結(jié)構(gòu)和特性，如表決器輸入的數(shù)據(jù)量大小、輸入的頻度等。在底層應(yīng)用中，如果需要高速地執(zhí)行逐位（bit-wise）表決（如針對冗余傳感器輸入的表決），那么就適合采用硬件方式。帶有硬件表決器的容錯(cuò)系統(tǒng)有HIFT、SIMIS、航天飛控系統(tǒng)及RaFt系統(tǒng)。硬件表決器的優(yōu)勢是處理速度快。如果在應(yīng)用的高層需要對一些復(fù)雜運(yùn)算的結(jié)果進(jìn)行處理，宜采用軟件方式實(shí)現(xiàn)表決功能。使用軟件表決器的有SIFT和VOTRICS。其靈活性在于：可以整合其他冗余處理技術(shù)，進(jìn)一步提高系統(tǒng)輸出的可靠性，缺點(diǎn)是需要更長的執(zhí)行時(shí)間。

2）精確的或是非精確的根據(jù)表決算法的協(xié)商類型，可以將其分為精確的或非精確的表決算法。在執(zhí)行精確的表決算法時(shí)，一致意味著冗余模塊的輸出必須完全一致時(shí)（即門限值t＝0），表決器才能輸出結(jié)果，如全體一致表決算法（unani-mity voting）；而在執(zhí)行非精確表決算法時(shí)，一致則意味著冗余模塊的輸出可以不完全相同，只要輸出之間的差別小于預(yù)定的門限值t，表決器就會(huì)有輸出，如n取m表決算法（m-out-of-n voting）、大數(shù)表決算法（majority voting）。在很多實(shí)際應(yīng)用中，冗余模塊的輸出并不一定完全相同，即使沒有故障發(fā)生時(shí)也是如此。因此非精確表決算法的應(yīng)用較為普遍，但其表決門限值的選擇較為困難，因?yàn)楹茈y有精確的數(shù)學(xué)方法來定義這個(gè)值，絕大多數(shù)設(shè)計(jì)者只能根據(jù)系統(tǒng)需求憑經(jīng)驗(yàn)來選擇。如果把門限值定得太小表決器會(huì)產(chǎn)生誤警甚至有可能不輸出結(jié)果；但是如果把門限值定得太大往往又會(huì)漏掉一些真正的故障信息，從而降低故障偵測范圍。同時(shí)非精確表決算法的執(zhí)行比精確表決算法的執(zhí)行更為復(fù)雜。

3）輸出集的大小表決算法的輸入集的勢可以很大也可以很小，如在NVP系統(tǒng)中，N版本冗余程序僅執(zhí)行正確或錯(cuò)誤判斷，那么其輸出集的勢為2。但是在其他一些NMR系統(tǒng)中，冗余模塊也可以產(chǎn)生很大的輸出集，如執(zhí)行圖像過濾處理的系統(tǒng)，其冗余模塊輸出集的勢就很大。上述兩種情況，其中每一種都必須采用有專門的表決算法，因?yàn)檫m合于小的輸出集的表決算法并不一定適合對大的或無限的輸出集進(jìn)行表決。

4）異步或是同步表決算法可以采用同步或異步方式執(zhí)行。在擁有全局共同時(shí)鐘的運(yùn)行環(huán)境中，表決器可以對冗余模塊的輸出直接進(jìn)行比較，因此表決算法的復(fù)雜性相對較低。然而，當(dāng)各冗余模塊使用本地時(shí)鐘時(shí)就需要采用異步的表決算法。這種算法較為復(fù)雜，因?yàn)楦魅哂嗄K的輸出存在時(shí)間偏差，需要額外的機(jī)制對此進(jìn)行協(xié)調(diào)處理，如循環(huán)等待、時(shí)序檢查等。

5）門限值預(yù)定或是動(dòng)態(tài)調(diào)整根據(jù)表決算法門限值的選定方式，可以將表決算法分成門限值固定的表決算法和自適應(yīng)的表決算法。有些表決算法的門限值在設(shè)計(jì)時(shí)就已經(jīng)定義，并在以后的運(yùn)行期間不再更改，這類算法多應(yīng)用于冗余輸入值變化幅度不大的應(yīng)用中。另外一些表決算法的門限值根據(jù)運(yùn)行環(huán)境的變化可以自適應(yīng)調(diào)整，這類算法在冗余輸入值變化較大時(shí)可以輸出更為可靠的結(jié)果。

6）標(biāo)準(zhǔn)、混合或特定本文根據(jù)表決算法執(zhí)行的特點(diǎn)可以將表決算法分成以下三個(gè)類別，并對每種類別中典型的算法作簡要敘述，當(dāng)然還有一些其他表決算法，限于篇幅在此不作討論。

（1）標(biāo)準(zhǔn)的表決算法如果僅從各個(gè)冗余模塊的輸出中產(chǎn)生（選擇或融合）一個(gè)作為系統(tǒng)輸出，則可將其歸類為標(biāo)準(zhǔn)型表決算法。屬于此類表決算法的有全體一致表決算法、大數(shù)表決算法、復(fù)數(shù)表決算法、中值表決算法、平均值表決算法。

a)結(jié)果選擇表決算法

(a)全體一致表決算法。要求所有的冗余輸入全部一致時(shí)才會(huì)有輸出結(jié)果。這種算法要求的條件比較苛刻，適用于那些嚴(yán)格要求所有的結(jié)果必須一致才可以產(chǎn)生輸出的應(yīng)用中。該表決算法不能屏蔽任何故障。

（b）大數(shù)表決算法。在n個(gè)冗余輸入中，僅當(dāng)至少「(n+1)/2個(gè)滿足一致性協(xié)商時(shí)才能從中選擇一個(gè)作為系統(tǒng)輸出；否則，大數(shù)表決器將產(chǎn)生一個(gè)異常代碼使系統(tǒng)處于fail-stop狀態(tài)，并輸出no-result 代表未達(dá)成一致性。

（c）復(fù)數(shù)表決算法。它是一種不太嚴(yán)格的大數(shù)表決算法，執(zhí)行的是n取m表決，即當(dāng)n個(gè)冗余輸入中有超過m個(gè)一致時(shí)，表決器才能產(chǎn)生一個(gè)輸出，這里m并不是一個(gè)嚴(yán)格的多數(shù)。當(dāng)n取3時(shí)大數(shù)表決算法及復(fù)數(shù)表決算法相同。

（d）中值表決算法。從冗余輸入中選取中間值作為輸出。這種算法的主要特點(diǎn)是：除了執(zhí)行速度快，還能處理存在多個(gè)不同且正確的輸入值作為系統(tǒng)輸出的情況。大數(shù)及復(fù)數(shù)表決算法則不能處理這種情況。例如給定一個(gè)輸入使其滿足方程x2-5x+6=0，易得x=2或x=3。假定這時(shí)表決器的冗余輸入集合是（1，2，3），顯然2和3都可以作為正確值輸入。但是大數(shù)及復(fù)數(shù)表決算法此時(shí)不能從這個(gè)集合中產(chǎn)生輸出，只是拋出一個(gè)異常碼；但中值表決算法則會(huì)選擇2作為輸出，顯然這是正確的。中值表決算法同樣不具備故障檢測功能，因此該算法不適宜用在安全關(guān)鍵的控制應(yīng)用中，除非附加額外的故障檢測機(jī)制。

b)結(jié)果融合表決算法

平均值表決算法，其輸出是冗余輸入的平均值。此表決算法通常應(yīng)用于擴(kuò)展的TMR系統(tǒng)的輸出表決器中。在這種系統(tǒng)中，表決器不會(huì)產(chǎn)生單點(diǎn)故障，因?yàn)槊總€(gè)冗余模塊都有自己的表決器，每個(gè)表決器表決出來的值在進(jìn)一步平均后才交給其他裝置。帶權(quán)重平均值表決算法是對平均表決算法的一種擴(kuò)展，是在其基礎(chǔ)上加入權(quán)重參數(shù)。該算法進(jìn)一步計(jì)算各種冗余輸入的帶權(quán)重平均值，權(quán)重可以預(yù)先確定也可以動(dòng)態(tài)調(diào)整。平均值表決算法同樣沒有內(nèi)在的故障檢測功能。

（2）混合型表決算法大數(shù)表決算法及復(fù)數(shù)表決算法有一個(gè)共同缺點(diǎn)，如它們有可能將一些相同的但不正確的冗余輸入作為正確結(jié)果輸出。為了解決這一問題而提高表決器的輸出可靠性，混合型表決算法往往在標(biāo)準(zhǔn)的表決算法的基礎(chǔ)上加入一些額外的信息，諸如冗余輸入的可靠性、實(shí)時(shí)的模塊自診斷信息或各種用于提高表決性能的概率信息、歷史信息。這類算法概括起來主要有以下幾種：

a)使用概率及歷史信息。這類算法使用了冗余輸入的正確性概率信息，以往冗余模塊產(chǎn)生正確輸出的次數(shù)及其他一些歷史信息用于提高表決輸出的可靠性。

文獻(xiàn)[22]介紹一種最大近似表決(maximum likelihood voting，MLV)算法。該算法用于輸出空間有限的多版程序系統(tǒng)，并且假定系統(tǒng)中各冗余版本失效是獨(dú)立的。MLV使用了各個(gè)冗余程序版本的可靠性信息，并確定最大可能正確的冗余版本輸出結(jié)果。該文同時(shí)介紹了這種表決算法的增強(qiáng)型，用于表決器不能同時(shí)接收所有冗余版本輸出的情況。

文獻(xiàn)[23]討論了兩組帶有不同重要級(jí)別的冗余模塊失效概率信息及權(quán)重值的表決算法。對于表決器的輸入，如果是由較高重要級(jí)別冗余模塊產(chǎn)生則被分配一個(gè)較高的權(quán)重；如果是由重要性較低級(jí)別冗余模塊產(chǎn)生則被分配一個(gè)較低的權(quán)重。但是該文沒有討論怎樣去分配權(quán)重。

文獻(xiàn)[24]提出了一種新的使用各冗余模塊的歷史信息的帶權(quán)重表決算法，并為這種算法設(shè)計(jì)了兩種版本。第一種是為每個(gè)具有較高歷史記錄的冗余模塊輸出分配一個(gè)較高的權(quán)重值；相反為每個(gè)具有較低歷史記錄的冗余模塊輸出分配一個(gè)較低的權(quán)重值。第二種版本是為那些歷史記錄值低于平均值的冗余模塊分配一個(gè)值為0的權(quán)重并將其輸出移除。文章還進(jìn)一步提出了模塊產(chǎn)生歷史記錄值的方法。

文獻(xiàn)[25]提出了一種基于歷史信息的自適應(yīng)大數(shù)表決算法（adaptive majority voting algorithm），其思想是：表決的輸出選擇機(jī)制以歷史記錄為基礎(chǔ)，每進(jìn)行一輪表決，累計(jì)一次歷史記錄值。表決器根據(jù)前一輪表決的歷史記錄并在滿足一致性協(xié)商的前提下，選擇其中的一個(gè)輸入值也就是當(dāng)前最大的歷史記錄值作為表決器的輸出，最大的歷史記錄值代表最為可靠的輸出，歷史記錄值在自適應(yīng)大數(shù)表決器中單獨(dú)由一個(gè)歷史記錄模塊來實(shí)現(xiàn)。這個(gè)歷史記錄值不但可以提高表決器輸出的可靠性，而且可以識(shí)別出系統(tǒng)中的故障最有可能出錯(cuò)的部件，并以此驅(qū)使系統(tǒng)實(shí)現(xiàn)重配置。雖然這種算法初步考慮了錯(cuò)誤的原因及其分布， 但由于一個(gè)周期任務(wù)的執(zhí)行時(shí)間遠(yuǎn)遠(yuǎn)超過瞬時(shí)錯(cuò)誤的持續(xù)時(shí)間而不能容忍部件的瞬時(shí)錯(cuò)誤。

b)使用預(yù)測及過濾技術(shù)。在有些系統(tǒng)中，冗余模塊在一個(gè)周期產(chǎn)生的輸出與下一個(gè)周期產(chǎn)生的輸出存在某種關(guān)聯(lián)。這種關(guān)聯(lián)信息可以被用于預(yù)測表決算法（predictor voting algorithm）中。當(dāng)檢測到冗余輸入不一致時(shí)，表決算法可以根據(jù)以往輸出的歷史信息預(yù)測一個(gè)輸出值，并將其與每一個(gè)冗余輸出作比較。任何冗余輸出只要與預(yù)測輸出的差值小于預(yù)定的預(yù)測門限值就可以作為表決的最終輸出，預(yù)測門限值與專門的應(yīng)用有關(guān)^[26]。線性預(yù)測表決算法(linear predictor voting algorithm)使用以前的兩個(gè)表決輸出來預(yù)測下一個(gè)結(jié)果值；預(yù)測—校正表決算法(predictor-correct voting algorithm)（第一順序預(yù)測），雖然耗費(fèi)更多的執(zhí)行時(shí)間但提供了更為精確的預(yù)測值^[27]；三域預(yù)測表決算法 (three domain voting algorithm)是對預(yù)測—校正表決算法的擴(kuò)展，該算法使用了故障歷史記錄，用于在冗余輸入不一致的情況下避免從不可靠的冗余輸入中選擇輸出。每當(dāng)有冗余輸入與多數(shù)冗余輸入不一致時(shí)故障記錄便會(huì)增加，如果是一致的，那么非故障記錄就會(huì)增加。如果表決算法輸出結(jié)果由一個(gè)較低于平均故障記錄值的冗余輸入產(chǎn)生，那么它就被認(rèn)定為正確的值；否則，該結(jié)果就不會(huì)被選擇。

過濾表決算法(smoothing voting algorithm)^[28]是對大數(shù)表決算法的一種擴(kuò)展，在大數(shù)表決中加入了接受測試。它基于這樣的一個(gè)假定：在連續(xù)的冗余輸入值之間如果存在不連續(xù)性那么說明該冗余模塊可能產(chǎn)生了錯(cuò)誤的輸出。這個(gè)假定在許多實(shí)時(shí)嵌入式控制應(yīng)用中都是正確的，在這些應(yīng)用中有一個(gè)控制反饋及周期性的計(jì)算操作。在過濾表決算法中，當(dāng)冗余輸入不一致時(shí)，與先前表決算法的輸出結(jié)果最接近的值將被選擇作為本周期可能的輸出值。如果測量的誤差小于預(yù)定義的值（稱為過濾門限值），那么這個(gè)結(jié)果將作為表決算法的輸出；否則，表決算法將不能產(chǎn)生應(yīng)答。表決算法“過濾門限值”參數(shù)的選取非常關(guān)鍵，盡管也可以用任意的值，但是如果能夠獲得關(guān)鍵時(shí)期連續(xù)冗余輸入中可能不連續(xù)的輸入值的數(shù)量等相關(guān)信息將會(huì)提高系統(tǒng)性能。

c)使用自檢測及糾錯(cuò)碼機(jī)制。如果在表決算法中合理地利用自診斷信息及糾錯(cuò)碼機(jī)制，能夠使這種表決算法比那些僅僅利用冗余輸入值的表決算法獲得更為準(zhǔn)確的輸出結(jié)果，另外還可以提高應(yīng)用的故障屏蔽、故障檢測及隔離功能，并降低系統(tǒng)通信的復(fù)雜度。

文獻(xiàn)[29]提出了一種基于自檢測的多數(shù)一致表決算法。該算法通過分散于任務(wù)代碼中的檢測代碼實(shí)時(shí)地收集瞬時(shí)錯(cuò)誤信息作為表決的輔助信息。設(shè)計(jì)了一個(gè)能收集內(nèi)存(RAM)和算術(shù)邏輯單元(ALU)錯(cuò)誤信息的檢測序列，構(gòu)造了一個(gè)簡單的代碼解釋器， 從機(jī)理上仿真了檢測密度、錯(cuò)誤持續(xù)時(shí)間、單個(gè)模塊可靠性等因素對該表決算法的影響，解決了多數(shù)一致表決算法在不一致情況下沒有輸出的問題及更好地應(yīng)對瞬時(shí)錯(cuò)誤情況。

文獻(xiàn)[30]提出了一種利用差錯(cuò)控制碼進(jìn)行多數(shù)一致表決的機(jī)制，其基本思想為：每個(gè)模塊利用預(yù)先定好的檢錯(cuò)碼對本地的計(jì)算數(shù)據(jù)結(jié)果進(jìn)行編碼，然后傳送該編碼的一部分代碼。由于檢錯(cuò)碼的作用，各結(jié)果之間的不同可以以某種概率被發(fā)現(xiàn)，通過對完整局部結(jié)果的重傳即可得出表決結(jié)果。利用這種機(jī)制可大幅度降低用于通信的開銷。

文獻(xiàn)[31]針對文獻(xiàn)[30]算法的缺點(diǎn)：有可能漏掉一些數(shù)據(jù)間的差異，從而會(huì)得到一個(gè)錯(cuò)誤的表決結(jié)果，即它也是非確定性的；另外，這種機(jī)制只利用了編碼的檢錯(cuò)能力，未能充分發(fā)揮它的全部效用，提出一種用于由N個(gè)冗余模塊(NMR) 組成的分布式系統(tǒng)中的多數(shù)表決策略。該算法利用糾錯(cuò)碼來大幅度降低平均通信復(fù)雜度， 通過選擇與計(jì)算錯(cuò)誤概率相匹配的糾錯(cuò)碼及其參數(shù)以進(jìn)一步提高算法的性能。

（3）特定的表決算法第三類表決算法是為特殊應(yīng)用構(gòu)建、設(shè)計(jì)的表決算法。如在SIFT系統(tǒng)中用于飛控的高可靠系統(tǒng)，其中三路（3-way）大數(shù)表決器對三個(gè)冗余處理器的輸出進(jìn)行表決。一旦輸出不一致系統(tǒng)將產(chǎn)生一個(gè)錯(cuò)誤信號(hào)，該信號(hào)由執(zhí)行程序來檢測、隔離并且重配系統(tǒng)。

文獻(xiàn)[32]描述了在航天飛機(jī)中，五個(gè)計(jì)算機(jī)中的四個(gè)負(fù)責(zé)導(dǎo)航、飛行、飛前校驗(yàn)，第五個(gè)作為備份系統(tǒng)。四臺(tái)計(jì)算機(jī)的輸出通過四路軟件大數(shù)表決器進(jìn)行表決并產(chǎn)生一個(gè)輸出到控制裝置。此外每個(gè)計(jì)算機(jī)獲取其他計(jì)算機(jī)的輸出，并且將其輸出與自己的相比較。如果是一致的則產(chǎn)生一個(gè)一致信號(hào)，相反則產(chǎn)生一個(gè)不一致信號(hào)。每一個(gè)計(jì)算機(jī)產(chǎn)生的一致和不一致信號(hào)由該計(jì)算機(jī)的冗余管理電路進(jìn)行處理（表決）。如果表決（如（不一致情況的數(shù)量）-（一致情況的數(shù)量））是正確的意味著這臺(tái)計(jì)算機(jī)是有故障的，并且冗余管理單元會(huì)從服務(wù)中除去這臺(tái)計(jì)算機(jī)。這里最多能夠容忍兩臺(tái)計(jì)算機(jī)失效，如果第三臺(tái)計(jì)算機(jī)出現(xiàn)故障，那么多數(shù)表決器的輸出將不能產(chǎn)生一個(gè)結(jié)果。在這種情況下，第五個(gè)計(jì)算機(jī)將會(huì)接管系統(tǒng)的控制權(quán)。

文獻(xiàn)[33]所描述的快速表決算法(expedient voting algorithm)用于改善N版本、多階段軟件系統(tǒng)的時(shí)間性能。在這樣的系統(tǒng)中，快速表決器在每個(gè)階段只要獲得有足夠數(shù)量的并且可用的冗余版本程序輸出就會(huì)執(zhí)行表決并產(chǎn)生輸出。因此執(zhí)行時(shí)間要比等待所有版本都產(chǎn)生輸出才開始表決的情況少得多。該文同時(shí)描述了一種修改的快速表決器，其中最快的程序版本被允許比其他程序版本超前運(yùn)行一個(gè)或者多個(gè)階段，如果出現(xiàn)失效事件則通過同步方式重啟，這種方式更節(jié)省了系統(tǒng)的執(zhí)行時(shí)間。如果版本很可靠，版本交互失效可能性小，另外執(zhí)行速度最快與最慢的程序版本之間的差別又很大的話，這種通過使用快速表決器來獲得執(zhí)行加速是最合適的。

5表決算法的比較

文獻(xiàn)[34]對大數(shù)、復(fù)數(shù)、中值、帶權(quán)重及預(yù)測表決算法的輸出可靠性進(jìn)行了比較。其中，中值表決算法在測試的這些算法中產(chǎn)生最大數(shù)量的正確輸出，但同時(shí)也產(chǎn)生最大數(shù)量的災(zāi)難性輸出，帶權(quán)重表決算法的輸出同其相似；大數(shù)表決算法則相反，其產(chǎn)生較少數(shù)量的災(zāi)難性輸出，但是也產(chǎn)生較少數(shù)量的正確輸出，復(fù)數(shù)表決算法同大數(shù)表決算法較相似；三域表決算法的輸出介于大數(shù)、復(fù)數(shù)同中值表決算法之間；線性及第一順序預(yù)測表決算法產(chǎn)生正確的輸出數(shù)量要少于中值及帶權(quán)重表決算法，但它們產(chǎn)生的災(zāi)難性輸出要多于大數(shù)表決及復(fù)數(shù)算法。

文獻(xiàn)[35]討論了在最壞情況下各種帶權(quán)重表決算法的復(fù)雜性，并驗(yàn)證了在表決門限t不是十分小的情況下，帶權(quán)重t-out-of-ΣVi的門限表決算法要比復(fù)數(shù)表決算法簡單得多。同時(shí)研究結(jié)果還表明，對于無序的輸入?yún)^(qū)間，n輸入復(fù)數(shù)表決算法（帶權(quán)重表決算法或不帶權(quán)重表決算法）的時(shí)間復(fù)雜度為O(n2)；帶權(quán)重t-out-of-Vi表決算法的時(shí)間復(fù)雜度為O(np)，這里p=V′it。此外，非權(quán)重及權(quán)重大數(shù)表決算法能以O(shè)(n)的時(shí)間復(fù)雜度執(zhí)行，非權(quán)重m-out-of-n表決算法以O(shè)(n2/m)的時(shí)間復(fù)雜度執(zhí)行。（非權(quán)重）3輸入大數(shù)及復(fù)數(shù)表決算法是一種3取2（2-out-of-3）表決策略。在實(shí)際應(yīng)用中，從時(shí)間（空間）復(fù)雜度來說，3輸入大數(shù)表決算法比3輸入復(fù)數(shù)表決算法更普遍。具有O(n)時(shí)間復(fù)雜度的大數(shù)表決算法比具有O（n2）時(shí)間復(fù)雜度的復(fù)數(shù)表決算法更簡單、更迅速。

文獻(xiàn)[36]討論了五種用于N版本編程技術(shù)的表決算法的比較，分別是合成或版本、帶權(quán)重的合成或版本、基于歷史信息、接受測試。結(jié)論是：使用3版本編程技術(shù)在單個(gè)版本高于平均失效概率的情況下可靠性有所提高，即使假定版本失效在統(tǒng)計(jì)上獨(dú)立不成立，并且如果在沒有大多數(shù)一致的情況下強(qiáng)制表決器產(chǎn)生輸出系統(tǒng)的可靠性還會(huì)進(jìn)一步得到改善。文獻(xiàn)[37]給出了安全關(guān)鍵應(yīng)用中一系列通過軟件執(zhí)行的表決算法性能分析。文獻(xiàn)[38]概括介紹了用于模式識(shí)別的表決算法，并給出了這些算法的性能比較。

6結(jié)束語

本文從表決算法的實(shí)現(xiàn)方式、協(xié)商類型、輸出集勢的大小、運(yùn)行環(huán)境的特點(diǎn)、表決算法執(zhí)行的特點(diǎn)對已有表決算法進(jìn)行了分類；著重討論了基于特點(diǎn)的分類，對于每一類中有代表性的表決算法都作了簡要的陳述，如它們的優(yōu)缺點(diǎn)、應(yīng)用領(lǐng)域；最后給出了關(guān)于這些算法的性能及復(fù)雜度比較。

參考文獻(xiàn)：

［1］

楊孟飛. 空間容錯(cuò)計(jì)算機(jī)的基本問題及對策[J].航天控制，1994，12（2）:25-29.

[2]龐海洋，李新明.軟件容錯(cuò)[C]//第十屆全國容錯(cuò)計(jì)算機(jī)學(xué)術(shù)會(huì)議論文集.2003：160-163.

[3]HOSEINNEZHAD R，BAB-HADIASHAR A.Fusion of redundant information in brake-by-wire systems，using a fuzzy voter[J].Journal of Advances in Information Fusion，2006，1(1):35-45. 

[4]KACELENGA R，ERICKSON D，PALMER D.Voting fusion adaptation for landmine detection[C]//Proc of the 5th International Confe-rence on Information Fusion.2002:333-340.

[5]郭文普，孫繼銀，任俊.一種基于數(shù)據(jù)融合的分布式入侵檢測系統(tǒng)[J].計(jì)算機(jī)技術(shù)與發(fā)展，2006，16(2):217-219.

[6]MU Xiao-yan，WATTA P，HASSOUN M H.A weighted voting model of associative memory[J].IEEE Trans on Neural Networks，2007，18(3):756-777.

[7]GAO Gui，KUANG Gang-yao，JIANG Yong-mei，et al.Fast detecting target group in SAR images[J].Journal of Electronics(China)，2006，23(5):781-782.

[8]楊衛(wèi)平，李吉成，沈振康.分層投票表決目標(biāo)檢測方法及其性能分析[J].紅外技術(shù)，2003，25(6):10-13. 

[9]ERP M van，VUURPIJL L，SCHOMAKER L.An overview and comparison of voting methods for pattern recognition[C]//Proc of the 8th International Workshop on Frontiers in Handwriting Recognition.Washington DC:IEEE Computer Society，2002:195-200.

[10]陳禾，毛志剛.一種具有TSC功能的TMR系統(tǒng)表決器設(shè)計(jì)方法[J].電子學(xué)報(bào)，1997，25(9):86-88.

[11]PARHAMI B.A taxonomy of voting schemes for data fusion and dependable computation[J].Reliability Engineering andSystem Safety，1996，52(2):139-151.

[12]陳珉，喻丹丹.分布式數(shù)據(jù)庫系統(tǒng)中數(shù)據(jù)一致性維護(hù)方法研究[J].國防科技大學(xué)學(xué)報(bào)，2004， 24(3):76-80.

[13]郭淵博，馬建峰.容忍入侵的國內(nèi)外研究現(xiàn)狀及所存在的問題分析[C]//第九屆保密通信與信息安全現(xiàn)狀研討會(huì)論文集.2005:337-341.

[14]閔應(yīng)驊.網(wǎng)絡(luò)容錯(cuò)與安全研究述評[J].計(jì)算機(jī)學(xué)報(bào)，2003，26(9):1035-1041.

[15]俞艷蘋，郭淵博，馬建峰.基于自適應(yīng)大數(shù)表決機(jī)制的容忍入侵模型[J].系統(tǒng)工程與電子技術(shù)，2005，27(6):1098-1101.

[16]郭淵博，馬建峰.面向服務(wù)的容忍入侵方法與設(shè)計(jì)[J].鄭州大學(xué)學(xué)報(bào):理學(xué)版，2004，36(3): 62-66.

[17]VERISSIMO P，NEVES N F，CORREIA M.Intrusion-tolerant architectures:concepts and design，DI/FCUL TR03-5[R].Lisbon:University of Lisboa，2003.

[18]TANARAKSIRITAVORN S，MISHRA S.Flexible intrusion tolerant voting architecture[C]//Proc of ACM Workshop on Scalable Trusted Computing.New York:ACM Press，2007:71-74.

[19]TAO Lin-mi，MURINO V，MEDIONI G.A tensor voting approach for the hierarchical segmentation of 3-D acoustic images[C]//Proc of the 1st International Symposium on 3D Data Processing Visualization and Transmission.2002:126-137. 

[20]KIM T，LEE T Y，LIM Y J，et al.The use of voting strategy for buil-ding extraction from high resolution satellite images[C]//Proc ofIEEE International Geoscience and Remote Sensing Symposium.2005:1269-1272.

[21]ALLGROVE C，F(xiàn)AIRHURST M C.Majority voting for improved signature verification[C]//Proc of IEE Colloquium on Visual Biometrics.2000:1-4.

[22]LEUNG Y W.Maximum likelihood voting for fault-tolerant software with finte output-space[J].IEEE Trans on Reliability，1995，44(3):419-427.

[23]PARHAMI B.Optimal algorithms for exact， inexact， and approval voting[C]//Proc of the 22nd International Symposium on Fault-Tole-rant Computing Systems.1992:444-451.

[24]LATIF-SHABGAHI G，BASS J M.BENNETT S.History-based weighted average voter:a novel software voting algorithm for fault-tolerant computer systems[C]//Proc of Euromicro Conference on Parallel and Distributed Processing.2001:402-409.

[25]LATIF-SHABGAHI G，BENNETT S.Adaptive majority voter:a novel voting algorithm for real-time fault-tolerant control systems[C]//Proc of the 25th EUROMICRO Conference.Washington DC:IEEE Compu-ter Society，1999:2113-2120.

[26]LALA J H，HARPER R E.Architectural principles for safety critical real-time applications[J].Proc of IEEE，1994，82(1): 25-39.

[27]LATIF-SHABGAHI G，BASS J M，BENNETT S.Component-oriented voter model for dependable control applications[J].Microprocessors Microsystems，2001，25(3):167-176.

[28]LATIF-SHABGAHI G，BASS J M，BENNETT S.Complete disagreementin redundant real-time control applications[C]//Proc of the 5th IFAC Workshop on Algorithms and Architectures for Real-time Control.1998:259-264.

[29]周海濤， 朱紀(jì)洪.基于自檢測的多數(shù)一致表決算法[J].清華大學(xué)學(xué)報(bào):自然科學(xué)版，2005，45(4):488-491.

[30]PARHAMI B.Voting algorithms[J].IEEE Trans on Reliability，1994，43(4):617-629.

[31]李亦凡，張煥國.利用糾錯(cuò)碼的確定性分布式表決策略[J].武漢大學(xué)學(xué)報(bào):自然科學(xué)版，2000，46(3):322-326.

[32]SKLAROFF J R.Redundancy management technique for space shuttle computers [J].IBM Journal of Research and Development，1976，20(1):20-28. 

[33]VOUK M A，PARADKAR A M，McALLISTER D F.Modeling execution time of multi-stage N-version fault-tolerant software[C]//Proc of IEEE Computer Software and Application Conference.1990:505-511.

[34]BASS J M，LATIF-SHABGAHI G，BENNETT S.Experimental comparison of voting algorithms in cases of disagreement[C]//Proc of the 23rd Euromicro Conference on New Frontiers of Information Technology.Washington DC:IEEE Computer Society，1997:516-523.

[35]PARHAMI B.Threshold voting is fundamentally simpler than plurality voting [J].International Journal on Reliability， Quality，and Safety Engineering，1994，1(1):95-102.

[36]GERSTING J L，NISTR L，ROBERTS D B，et al.A comparison of vo-ting algorithms for N-version programming[C]//Proc of the 24th Annual Hawaii International Conference on System Sciences.1991:253-262.

[37]LATIF-SHABGAHI G.Performance analysis of software implemented inexact voting algorithms[D].Sheffield:University of Sheffield，1999.

[38]ERP M van，VUURPIJL L，SCHOMAKER L.An overview and comparison of voting methods for pattern recognition[C]//Proc of the 8th International Workshop on Frontiers in Handwriting Recognition.Washington DC:IEEE Computer Society.2002:195-200.