李 莉,劉翠杰,王 政,任逸飛

(北京電子科技學(xué)院 電子信息工程系,北京 100070)

1 引言

隨著信息時(shí)代的進(jìn)步,科學(xué)技術(shù)尤其是電子技術(shù)、計(jì)算機(jī)技術(shù)的飛速發(fā)展,各種系統(tǒng)及設(shè)備的性能大大提高,其結(jié)構(gòu)也變得越來(lái)越復(fù)雜,導(dǎo)致系統(tǒng)呈現(xiàn)出多種失效模式,給系統(tǒng)的可靠性分析帶來(lái)了新的問(wèn)題.

故障樹分析方法 (Fault Tree Analysis,FTA)在六十年代初由美國(guó)貝爾研究所提出,并用于民兵導(dǎo)彈的控制系統(tǒng)設(shè)計(jì),為預(yù)測(cè)導(dǎo)彈發(fā)射的隨機(jī)失效概率做出了貢獻(xiàn).目前,FTA已廣泛應(yīng)用于電子、電力、化工、機(jī)械、交通乃至土木建筑領(lǐng)域的關(guān)鍵系統(tǒng)定量或定性失效分析中.FTA通過(guò)分析系統(tǒng)潛在的薄弱環(huán)節(jié),建立故障樹模型,為那些能夠?qū)е孪到y(tǒng)失效的事件組合提供了數(shù)學(xué)和圖表的表達(dá)方法.但隨著容錯(cuò)系統(tǒng)的大量應(yīng)用,動(dòng)態(tài)邏輯門的引入,傳統(tǒng)的基于最小割集(Minimal Cut Set,MCS)的故障樹可靠性理論和方法必須加以修正才能全面描述和反映動(dòng)態(tài)故障樹的特性[1,2].越來(lái)越多的系統(tǒng),例如計(jì)算機(jī)服務(wù)器系統(tǒng)、電信系統(tǒng)、水、氣以及配電系統(tǒng)等都要求有容錯(cuò)功能,即在發(fā)生故障時(shí),這些系統(tǒng)仍保持在可接受的或性能下降一級(jí)開展工作.近年來(lái),人們逐漸將決策圖引入故障樹分析和復(fù)雜系統(tǒng)容錯(cuò)功能的分析與設(shè)計(jì)中[3,4].

本文通過(guò)對(duì)邊值多值決策圖和其相關(guān)決策圖的介紹,以及邊值多值決策圖在動(dòng)態(tài)故障樹分析中的應(yīng)用,對(duì)邊值多值決策圖進(jìn)行了全面深入的分析闡述.本文組織結(jié)構(gòu)如下:第2節(jié)介紹了二叉決策圖、多比特函數(shù)二叉決策圖和多比特邊值二叉決策圖的基本知識(shí)并列舉了實(shí)例進(jìn)行分析;第3節(jié)通過(guò)具體實(shí)例對(duì)多值函數(shù)、多值決策圖和邊值多值決策圖進(jìn)行了介紹;第4節(jié)以網(wǎng)絡(luò)計(jì)算系統(tǒng)為例說(shuō)明了邊值多值決策圖在動(dòng)態(tài)故障樹分析中的應(yīng)用,并分析了其性能;第5節(jié)對(duì)邊值多值決策圖進(jìn)行了總結(jié).

2 邊值二叉決策圖

2.1 二叉決策圖

二叉決策圖(Binary Decision Diagram,BDD)采用有向無(wú)環(huán)圖表示從{0,1}n到{0,1}映射的布爾函數(shù)f(x1,x2,···,xn)[5–9].

二叉決策圖可以根據(jù)香農(nóng)展開定理,對(duì)布爾函數(shù)f(x1,x2,···,xn)中的變量逐次進(jìn)行香農(nóng)展開獲得:根節(jié)點(diǎn)表示布爾函數(shù)f(x1,x2,···,xn)自身,從根節(jié)點(diǎn)引出兩個(gè)分支,分別表示某個(gè)變量xi取0和1值時(shí)進(jìn)行第一次香農(nóng)展開后的布爾函數(shù)f(x1,···,xi-1,0,xi+1,···,xn)和f(x1,···,xi-1,1,xi+1,···,xn);布爾函數(shù)f(x1,···,xi-1,0,xi+1,···,xn)和f(x1,···,xi-1,1,xi+1,···,xn)可進(jìn)一步進(jìn)行香農(nóng)展開,并將它們和各自的0-分量和1-分量連接;直至所有的變量均展開后得到最后的函數(shù)結(jié)果0或1,獲得布爾函數(shù)的二叉決策圖表示[5].也可以直觀的采用布爾函數(shù)的真值表獲得二叉決策圖.

例如:對(duì)于布爾函數(shù)f=(x1+x2)×x3

二叉決策圖(b)中0、1兩個(gè)終節(jié)點(diǎn)分別代表f的0和1兩個(gè)取值;xi下方的兩條分支分別表示xi取值為0的0-邊和xi取值為1的1-邊 .

二叉決策圖適用于具有兩個(gè)對(duì)立狀態(tài)的系統(tǒng)性能的判斷[10].例如圖1中的終點(diǎn)0和1分別表示系統(tǒng)無(wú)故障和有故障.

2.2 多比特函數(shù)二叉決策圖

多比特函數(shù)二叉決策圖是對(duì)二叉決策功能的擴(kuò)展,多比特函數(shù)的每個(gè)變量由多位二進(jìn)制數(shù)表示,而布爾函數(shù)的每個(gè)變量都是用一位二進(jìn)制數(shù)來(lái)表示.下面對(duì)多比特函數(shù)的二叉決策圖進(jìn)行舉例說(shuō)明.

圖1 布爾函數(shù)f和f的二叉決策圖

表1(a)為sinX函數(shù)值表,假設(shè)我們選擇3 bit的二進(jìn)制數(shù)來(lái)表示X和sinX,則取遞增單位為1/23=0.125,采用就近取整原則,可得二值化后的函數(shù)如表1(b)所示.

表1 sinX函數(shù)

表1(b)的二叉決策圖如圖2所示.節(jié)點(diǎn)X0、X1和X2分別表示變量X的3個(gè)bit位,X0是最低位,X2是最高位.虛線邊表示Xi的 0-邊,即Xi取值為 0;實(shí)線邊表示Xi的1-邊,即Xi取值為1.終節(jié)點(diǎn)表示函數(shù)的輸出結(jié)果.

多比特函數(shù)的輸出結(jié)果是由多位二進(jìn)制數(shù)表示[11],即有多種輸出結(jié)果.多比特函數(shù)二叉決策圖適用于對(duì)多狀態(tài)且每個(gè)系統(tǒng)組件只有兩個(gè)狀態(tài)的系統(tǒng)進(jìn)行表示.例如圖2中的7個(gè)終節(jié)點(diǎn)對(duì)應(yīng)系統(tǒng)的7種不同運(yùn)行狀態(tài),而系統(tǒng)內(nèi)各組件只有0和1兩個(gè)狀態(tài),對(duì)應(yīng)組件的有故障和無(wú)故障狀態(tài).

2.3 多比特函數(shù)邊值二叉決策圖

邊值二叉決策圖(Edge-Value Binary Decision Diagram,EVBDD)是 BDD 的變體,表示整數(shù)值函數(shù).EVBDD僅由一個(gè)表示0的終節(jié)點(diǎn)和具有整數(shù)權(quán)重邊的內(nèi)部節(jié)點(diǎn)組成.EVBDD邊值求解規(guī)則如下:

(1)所有節(jié)點(diǎn) 0-邊總是具有零權(quán)重,即 0-邊的邊值為0.

(2)節(jié)點(diǎn)1-邊的邊值為當(dāng)其子節(jié)點(diǎn)取值為0且其它節(jié)點(diǎn)取值相同,該節(jié)點(diǎn)取值為1時(shí)的函數(shù)值與取值為0時(shí)的函數(shù)值之差.即節(jié)點(diǎn)xi的1-邊的邊值e為:

根據(jù)邊值求解規(guī)則,圖2的邊值二叉決策圖如圖3.

圖2 二叉決策圖BDD

圖3 sinX的邊值二叉決策圖EVBDD

邊值相加即可得到函數(shù)的最終輸出結(jié)果.例如X21-邊的邊值,可以用X2X1X0=100時(shí)的輸出100減去X2X1X0=000 的輸出 000,結(jié)果等于 4,即X2的 1-邊的邊值為4.

為便于系統(tǒng)狀態(tài)的計(jì)算,可以對(duì)邊值二叉決策圖進(jìn)行縮減,去掉冗余節(jié)點(diǎn),簡(jiǎn)化搜索路徑.冗余節(jié)點(diǎn)的定義如下:若邊值二叉決策圖的兩個(gè)或兩個(gè)以上同名節(jié)點(diǎn)的0-邊或1-邊均指向相同的分支子節(jié)點(diǎn),或均指向終節(jié)點(diǎn),且1-邊的邊值相同,則此同名節(jié)點(diǎn)存在冗余.縮減規(guī)則:

(1)對(duì)邊值二叉決策圖由下至上進(jìn)行遞歸判斷,判斷是否存在冗余節(jié)點(diǎn);

(2)對(duì)存在冗余的同名節(jié)點(diǎn),保留一個(gè)節(jié)點(diǎn)即可,直至邊值二叉決策圖中不再存有冗余節(jié)點(diǎn).

縮減后的二叉決策圖的函數(shù)輸出結(jié)果由邊值的和計(jì)算獲得,所以終節(jié)點(diǎn)由0來(lái)表示[11].圖3的縮減邊值二叉決策圖如圖4所示.圖3中四個(gè)X0的1-邊的邊值完全相同,且均指向終節(jié)點(diǎn),所以可以刪除其它三個(gè)X0節(jié)點(diǎn).

多比特函數(shù)邊值二叉決策圖的應(yīng)用類似于多比特二叉決策圖,區(qū)別在于系統(tǒng)最終狀態(tài)由邊值的和來(lái)表示.

圖4 縮減后的邊值二叉決策圖EVBDD

3 邊值多值決策圖

3.1 多值決策圖

如前所述,當(dāng)系統(tǒng)的狀態(tài)多于2個(gè)時(shí),我們稱系統(tǒng)為多態(tài)系統(tǒng).若系統(tǒng)中的各個(gè)組件也具有多個(gè)狀態(tài)時(shí),我們稱系統(tǒng)為具有多狀態(tài)組件的多態(tài)系統(tǒng),簡(jiǎn)稱為多態(tài)系統(tǒng).文獻(xiàn)[3]指出多態(tài)系統(tǒng)的性能、容量或系統(tǒng)的狀態(tài)可靠性級(jí)別都可以用系統(tǒng)的狀態(tài)來(lái)表示.

多態(tài)系統(tǒng)的狀態(tài)僅僅依賴系統(tǒng)組件的狀態(tài).含有n個(gè)組件的系統(tǒng)可以被認(rèn)為是一個(gè)多值函數(shù)f(x1,x2,···,xn)的映射:R1×R2×···×Rn→M,其中每一個(gè)xi代表Ri狀態(tài)的一個(gè)元組,Ri={0,1,···,ri-1}是組件的狀態(tài)集,M={0,1,···,m-1}表示系統(tǒng)的狀態(tài)集.此時(shí)多值函數(shù)被稱為多態(tài)系統(tǒng)的結(jié)構(gòu)函數(shù).在許多應(yīng)用中,一個(gè)系統(tǒng)的狀態(tài)及其組件是完全有序的,并且該系統(tǒng)組件的運(yùn)行狀態(tài)會(huì)影響整個(gè)系統(tǒng)的運(yùn)行狀態(tài).因此,通過(guò)以升序的方式將值分配給每個(gè)狀態(tài),結(jié)構(gòu)函數(shù)通常會(huì)變成單調(diào)遞增函數(shù).即多值函數(shù)f(x1,x2,···,xn)當(dāng)且僅當(dāng)對(duì)于任意的xi是單調(diào)遞增函數(shù),即,

可以定義當(dāng)xi取值為0時(shí),為組件的最壞狀態(tài)即組件完全故障,當(dāng)xi取值為ri–1時(shí),為組件的最佳狀態(tài)即組件完全無(wú)故障;當(dāng)f的值為0時(shí),為系統(tǒng)的最壞狀態(tài)即系統(tǒng)完全故障,當(dāng)f的值為m–1時(shí),為系統(tǒng)的最佳狀態(tài)即系統(tǒng)完全無(wú)故障.隨著組件狀態(tài)值的增加,系統(tǒng)的狀態(tài)值也增加,即組件的故障越少,系統(tǒng)的故障就越少,運(yùn)行狀態(tài)就越好.

多值決策圖(Multiple-valued Decision Diagrams,MDD)是反映部件狀態(tài)與系統(tǒng)狀態(tài)之間關(guān)系的有向無(wú)環(huán)圖.MDD的獲得與BDD的獲得類似,通過(guò)香農(nóng)展開定理,重復(fù)應(yīng)用于多值函數(shù)的各個(gè)組件獲得.MDD的內(nèi)部節(jié)點(diǎn)表示通過(guò)向某些組件賦值從而獲得的f的子函數(shù),每個(gè)內(nèi)部節(jié)點(diǎn)具有對(duì)應(yīng)于組件值的多個(gè)輸出邊[3].例如對(duì)于多值函數(shù)

由以上的多值函數(shù)f得到的取值表如表2所示,圖5為其決策圖,圖中的終節(jié)點(diǎn) 0,1,2,3 分別表示多值函數(shù)f的取值.

表2 多值函數(shù)f的取值表

3.2 邊值多值決策圖

邊值多值決策圖(Edge-Value Multiple-valued Decision Diagram,EVMDD)是多值決策圖的擴(kuò)展,它包括表示0的一個(gè)終節(jié)點(diǎn)和具有整數(shù)權(quán)重邊值的內(nèi)部節(jié)點(diǎn);0-邊總是具有零權(quán)重.在 EVMDD 中,函數(shù)值被表示為從根節(jié)點(diǎn)遍歷到終節(jié)點(diǎn)的邊值的和[3,12,13].

以圖5為例,使用與邊值二叉決策圖相同的邊值求解和縮減規(guī)則得到的多值函數(shù)f的邊值多值決策圖如圖6所示.因?yàn)閤2的分支子節(jié)點(diǎn)x31-邊的邊值完全相同,所以可以合并.x1的0-邊的分支子節(jié)點(diǎn)x2和2-邊的分支子節(jié)點(diǎn)x2的邊值相同,所以進(jìn)行合并.x1的1-邊分支子節(jié)點(diǎn)x2與其它邊的分支子節(jié)點(diǎn)x2的邊值不相同,所以不能縮減.

經(jīng)過(guò)比較,發(fā)現(xiàn)MDD有7個(gè)節(jié)點(diǎn),而EVMDD只有4個(gè)節(jié)點(diǎn),減少了3/7.文獻(xiàn)[3]中提到計(jì)算的時(shí)間復(fù)雜度與決策圖中的節(jié)點(diǎn)數(shù)量成正比,所以在計(jì)算的時(shí)間復(fù)雜度方面,EVMDD比MDD更有優(yōu)勢(shì).

圖5 多值函數(shù)f的 MDD

圖6 多值函數(shù)f的 EVMDD

4 案例研究

4.1 高度可靠的網(wǎng)絡(luò)計(jì)算系統(tǒng)

以文獻(xiàn)[14]中提到的高度可靠的網(wǎng)絡(luò)計(jì)算系統(tǒng)為例,系統(tǒng)架構(gòu)如圖7所示,通過(guò)兩個(gè)不同的數(shù)據(jù)進(jìn)程提供網(wǎng)絡(luò)計(jì)算服務(wù).系統(tǒng)分為兩個(gè)部分,Complex A 和Complex B.每個(gè)子系統(tǒng)包含一個(gè)服務(wù)器(SVR)、一個(gè)存儲(chǔ)子系統(tǒng)(STO)及一個(gè)網(wǎng)絡(luò)子系統(tǒng)(NET).存儲(chǔ)子系統(tǒng)采用鏡像存儲(chǔ)方式,包含一個(gè)存儲(chǔ)控制器及兩個(gè)存儲(chǔ)空間.當(dāng)存儲(chǔ)控制器故障時(shí),該存儲(chǔ)控制器故障.備用服務(wù)器SVR_C作為失效備援,SVR_C和兩個(gè)服務(wù)器SVR_A、SVR_B間采用心跳連接.根據(jù)該系統(tǒng)的動(dòng)態(tài)故障樹DFT模型可以得到文獻(xiàn)[10]中的系統(tǒng)性能初始MDD,如圖8所示.

圖7 高可靠性網(wǎng)絡(luò)計(jì)算系統(tǒng)

圖8 高可靠性網(wǎng)絡(luò)計(jì)算系統(tǒng)的初始MDD

下面用文中給出的邊值多值決策圖的構(gòu)造方法來(lái)獲得其EVMDD.將SP的4個(gè)分支分別用0到3的4個(gè)狀態(tài)值代替.即000,001,010,100,110用狀態(tài)0代替;101用狀態(tài)1代替;111用狀態(tài)2代替;011用狀態(tài)3代替.

圖9所示的系統(tǒng)動(dòng)態(tài)門的MDD,按照本文所述的邊值求解規(guī)則和縮減規(guī)則得到圖10所示的EVBDD.

圖9 高可靠性網(wǎng)絡(luò)計(jì)算系統(tǒng)動(dòng)態(tài)門的MDD

由于此系統(tǒng)比較簡(jiǎn)單,所以EVMDD在節(jié)點(diǎn)和分支的數(shù)量上減少的優(yōu)勢(shì)沒有顯現(xiàn).但依據(jù)圖6可見,相對(duì)于MDD來(lái)說(shuō),EVMDD在節(jié)點(diǎn)和分支的數(shù)量上都有所減少,系統(tǒng)越復(fù)雜,邊值多值決策圖在節(jié)點(diǎn)數(shù)量上的優(yōu)勢(shì)越明顯.

4.2 環(huán)境檢測(cè)物聯(lián)網(wǎng)絡(luò)

我國(guó)空氣污染形勢(shì)嚴(yán)峻,部分城市面臨霧霾、沙塵暴等環(huán)境問(wèn)題.環(huán)保部門積極開展大氣污染治理,其核心是對(duì)污染源的精準(zhǔn)監(jiān)測(cè)和對(duì)污染數(shù)據(jù)的精準(zhǔn)分析.隨著物聯(lián)網(wǎng)技術(shù)的發(fā)展,多功能、智能化、小型化的微觀站監(jiān)測(cè)設(shè)備得到廣泛使用.研究環(huán)境檢測(cè)物聯(lián)網(wǎng)絡(luò)故障樹的邊值多值決策圖模型,假設(shè)環(huán)境參數(shù)主要有溫度、濕度和氣體濃度,分別用X2、X1、X0來(lái)表示,設(shè)備的最終檢測(cè)狀態(tài)用f來(lái)表示,每一個(gè)參數(shù)的測(cè)量都有一個(gè)備份電路.因此用狀態(tài)0表示完全無(wú)故障,狀態(tài)1表示部分故障,狀態(tài)2表示完全故障.得到多值函數(shù)f的取值表如表3所示,環(huán)境監(jiān)測(cè)物聯(lián)網(wǎng)絡(luò)MDD如圖11所示.

圖10 高可靠性網(wǎng)絡(luò)計(jì)算系統(tǒng)動(dòng)態(tài)門的EVMDD

表3 多值函數(shù)f的取值表

按照本文所述的邊值求解規(guī)則和縮減規(guī)則得到如圖12所示的環(huán)境檢測(cè)物聯(lián)網(wǎng)絡(luò)的EVMDD.

圖11 環(huán)境檢測(cè)物聯(lián)網(wǎng)絡(luò)的 MDD

圖12 環(huán)境檢測(cè)物聯(lián)網(wǎng)絡(luò)的 EVMDD

通過(guò)對(duì)環(huán)境檢測(cè)物聯(lián)網(wǎng)絡(luò)的MDD和EVMDD的比較,用EVMDD用更少的節(jié)點(diǎn)來(lái)表示環(huán)境檢測(cè)物聯(lián)網(wǎng)絡(luò).而計(jì)算的時(shí)間復(fù)雜度與決策圖中的節(jié)點(diǎn)數(shù)量成正比,即節(jié)點(diǎn)數(shù)越少時(shí)間復(fù)雜度越低,因此EVMDD在系統(tǒng)的故障樹分析方面更有優(yōu)勢(shì).特別地,隨著狀態(tài)數(shù)的變大,EVMDD的節(jié)點(diǎn)數(shù)遠(yuǎn)小于MDD的節(jié)點(diǎn)數(shù).我們預(yù)計(jì)系統(tǒng)將在未來(lái)變得更加復(fù)雜,并且狀態(tài)數(shù)將變得更大,因此,EVMDD比MDD更有發(fā)展前景[15,16].

5 結(jié)束語(yǔ)

本文對(duì)邊值二叉決策圖EVBDD和邊值多值決策圖EVMDD進(jìn)行了系統(tǒng)的介紹和分析,特別提出了邊值多值決策圖在動(dòng)態(tài)故障樹方面的應(yīng)用.EVMDD可以更加緊湊的表示整個(gè)系統(tǒng),綜合運(yùn)用組合方法和狀態(tài)空間方法,這不僅使得狀態(tài)空間爆炸問(wèn)題得到緩解,也使得計(jì)算速度得到提升,可以廣泛應(yīng)用于現(xiàn)實(shí)生活中的多狀態(tài)系統(tǒng)和多功能動(dòng)態(tài)軟件的性能分析等方面[17,18].