劉婷婷,張長(zhǎng)勝,張 斌,王 鵬

(東北大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院,沈陽(yáng) 110819) E-mail:549715624@qq.com

1 引 言

可靠性作為SBS系統(tǒng)的服務(wù)質(zhì)量最重要的維度之一[1-3].目前SBS系統(tǒng)的可靠性的相關(guān)研究主要分為兩類:基于Markov模型[2,4]的方法與基于Petri網(wǎng)的方法[5,6].SBS系統(tǒng)在運(yùn)行過(guò)程中,系統(tǒng)內(nèi)部服務(wù)之間的共享資源以及系統(tǒng)內(nèi)部信息傳遞的相互依賴關(guān)系的存在,使得系統(tǒng)的成功運(yùn)行在絕大多數(shù)情況下受限于共因失效[2].共因失效泛指的是由于一個(gè)因素的發(fā)生導(dǎo)致系統(tǒng)多個(gè)組件同時(shí)失效這一現(xiàn)象.這種失效的誘因可以歸結(jié)為兩種:外部因素(例如,供電故障、共享服務(wù)器故障以及共享數(shù)據(jù)庫(kù)故障等等)和內(nèi)部因素(由系統(tǒng)內(nèi)部的服務(wù)故障或者傳播途徑的故障導(dǎo)致的傳播失效).目前絕大多數(shù)SBS系統(tǒng)的可靠性的研究[4-6]都假設(shè)服務(wù)之間相互獨(dú)立,并沒(méi)有考慮共因失效.極少數(shù)研究[2]考慮共因失效的研究也僅僅考慮了外部因素.為解決上述問(wèn)題,本文提出一種考慮共因失效的SBS系統(tǒng)的可靠性分析方法.

2 研究背景

2.1 相關(guān)研究

對(duì)于由系統(tǒng)組件之間的共享資源故障引起的外部共因失效,Scott[7]提出了一種基于事件樹(shù)模型的可靠性分析方法;Vieria和Richardson[8]提出了多元偏序集的概念,并在分析可靠性的過(guò)程中表示軟件組件之間的失效相關(guān)性;Dai[9]則在提出的可靠性分析方法中用故障樹(shù)模型合并關(guān)聯(lián)失效事件的組合.Fiondella和Gokhale[10]基于Markov模型提出一種可靠性分析方法,該方法同時(shí)考慮了信息在傳輸過(guò)程中的失效和組件對(duì)故障的自我修復(fù);Popic[11]提出了一種貝葉斯網(wǎng)絡(luò)可靠性分析模型.在SBS系統(tǒng)可靠性的研究中只有少數(shù)考慮共因失效.其中,Zhou等[3]提出了一種基于分層樹(shù)結(jié)構(gòu)的SBS系統(tǒng)可靠性分析模型.樹(shù)結(jié)構(gòu)中的結(jié)點(diǎn)只有一個(gè)父節(jié)點(diǎn),這一性質(zhì)導(dǎo)致Zhou的模型中的服務(wù)只能受限于一個(gè)直接共因失效的誘因.針對(duì)上述問(wèn)題,Peng[2]提出了一種基于Markov的SBS系統(tǒng)可靠性分析模型.近年來(lái),一系列基于二元決策圖(binary decision diagram,BDD)的可靠性分析方法被提出[12-14],并應(yīng)用于多階段系統(tǒng)的可靠性分析.該類可靠性分析方法利用布爾變量表示系統(tǒng)組件的狀態(tài).相比于傳統(tǒng)多階段系統(tǒng)可靠性分析方法[15-17],基于二元決策圖的分析方法有更高效的計(jì)算復(fù)雜度[18,19].因此,本文基于二元決策圖提出了一種考慮內(nèi)部/外部共因失效的SBS系統(tǒng)可靠性分析方法.

2.2 二元決策圖相關(guān)概念

BDD[20]作為一種基于圖的數(shù)據(jù)結(jié)構(gòu),最初的設(shè)計(jì)目的是給離散布爾表達(dá)式提供一種高效、簡(jiǎn)潔的表示形式和操作手段.近年來(lái),BDD已經(jīng)為成為系統(tǒng)可靠性分析一種重要的表示方法.

BDD是一種有根的、有向的、非循環(huán)的基于圖的數(shù)據(jù)結(jié)構(gòu),基于香農(nóng)分解定理[20].結(jié)構(gòu)上,BDD由兩種類型的結(jié)點(diǎn)構(gòu)成:底端結(jié)點(diǎn)和非底端結(jié)點(diǎn).對(duì)每一個(gè)BDD有且僅有一對(duì)0-結(jié)點(diǎn)和1-結(jié)點(diǎn),表示布爾表達(dá)式的最終結(jié)果為0或者為1,底端結(jié)點(diǎn)位于整個(gè)圖結(jié)構(gòu)的末端因此沒(méi)有出邊只有入邊.每一個(gè)非底端結(jié)點(diǎn)都有兩條出邊,分別稱為0-邊(else-邊)和1-邊(then-邊),表示該結(jié)點(diǎn)代表變量的取值情況.其中,1-邊表示結(jié)點(diǎn)所輸入的值為1,同理0-邊表示結(jié)點(diǎn)所輸入的值為0.基于香農(nóng)分解定理,BDD中的任何一個(gè)非底端結(jié)點(diǎn)都能夠?qū)⒃摻Y(jié)點(diǎn)代表的布爾表達(dá)式編碼成if-then-else(ite)格式,

3 考慮內(nèi)部/外部共因失效的SBS系統(tǒng)可靠性分析方法

3.1 SBS系統(tǒng)可靠性

本文研究的是考慮內(nèi)部/外部共因失效SBS系統(tǒng)的可靠性分析方法,以下關(guān)于共因失效的假設(shè)將應(yīng)用于本文:

1)假設(shè)文中研究的系統(tǒng)既受限于內(nèi)部共因失效又受限于外部共因失效;

2)當(dāng)內(nèi)部共因失效發(fā)生的情況下,共因失效組[19](common-cause group,CCG)中的服務(wù)可能導(dǎo)致傳播失效,也可能不導(dǎo)致傳播失效;CCG中服務(wù)失效的發(fā)生以概率εj引起CCG全部服務(wù)的失效,若該服務(wù)不能導(dǎo)致傳播失效,則設(shè)εj=0.

3)當(dāng)外部共因失效發(fā)生的情況下,CCG中的全部服務(wù)失效.CCG中的wj引發(fā)的CCF的發(fā)生概率為εj.并且外部失效因素的失效概率與個(gè)體失效概率相互獨(dú)立.

4)本文涉及的參數(shù)在SBS系統(tǒng)運(yùn)行之前已經(jīng)給定.在本文提出的可靠性分析模型中,假設(shè)SBS系統(tǒng)與系統(tǒng)中的服務(wù)只有兩種狀態(tài):成功運(yùn)行和運(yùn)行失效.

設(shè)SBS系統(tǒng)有n個(gè)服務(wù),xj(j=1,…n)為系統(tǒng)中服務(wù)的狀態(tài)指示變量,其中xj=0表示服務(wù)j在系統(tǒng)運(yùn)行前失效,對(duì)應(yīng)的,xj=1表示服務(wù)j在系統(tǒng)運(yùn)行前成功運(yùn)行,設(shè)x是元素的狀態(tài)向量,x=(x1,…,xn).SBS系統(tǒng)的狀態(tài)可以表達(dá)為n個(gè)獨(dú)立服務(wù)的狀態(tài)指示變量x1,…,xn的二元函數(shù)Q(x).Q(x)是x的二元方程,表達(dá)的是SBS系統(tǒng)結(jié)構(gòu)方程,其中Q(x)=0對(duì)應(yīng)的表示系統(tǒng)失效,Q(x)=1對(duì)應(yīng)的表示系統(tǒng)成功運(yùn)行.SBS系統(tǒng)可靠性分析的目標(biāo)就是得到系統(tǒng)成功運(yùn)行的概率,也就是Pr(Q(x)=1).

而服務(wù)xj的不可靠性為qj=Pr(xj=0),對(duì)應(yīng)的可靠性為pj=1-qj.服務(wù)的失效方程為Qj=qj.在外部共因失效的情況下,εj表示CCGwj的CCF出現(xiàn)概率.在內(nèi)部共因失效情況下,εj表示由服務(wù)xj的失效引起的傳播失效的概率,服務(wù)xj的單獨(dú)失效概率為vj=qj(1-εj).由服務(wù)xj引起的整個(gè)CCGwm的傳播失效的失效概率就為wj=qjεj.

3.2 SBS系統(tǒng)可靠性的二元決策圖表示法

根據(jù)故障樹(shù)構(gòu)造一個(gè)二元決策圖,每一個(gè)二元決策圖的變量代表一個(gè)故障樹(shù)中基本事件,根據(jù)啟發(fā)式算法,決策圖中的基本事件被安排了一個(gè)索引.然后對(duì)故障樹(shù)使用深度優(yōu)先算法,在此過(guò)程中對(duì)應(yīng)的二元決策圖根據(jù)下列規(guī)則,通過(guò)一種自底向上的方法遞歸的構(gòu)建起來(lái),如下,

GF=ite(x′,Gx′=1,Gx′=0)ite(y′,Fy′=1,Fy′=0)

(1)

=ite(x′,G1,G2)ite(y′,F1,F2)

其中G和F代表已經(jīng)遍歷過(guò)的子故障樹(shù)相對(duì)應(yīng)的邏輯表達(dá)式;Gi和Fi對(duì)應(yīng)代表G和F的子表達(dá)式;符號(hào)◇表示邏輯操作AND或者OR中的一種.前面提到的索引表示輸入列表中布爾變量的順序.更準(zhǔn)確的說(shuō),規(guī)則(1)用于合并代表G和F邏輯表達(dá)式的子二元決策圖模型,合并稱為一個(gè)二元決策圖模型.為了應(yīng)用規(guī)則(1),需要將兩個(gè)根節(jié)點(diǎn)的順序被比較,例如,G為x′同時(shí)F為y′.如果x′和y′擁有相同的順序,例如,他們屬于相同的元素,則規(guī)則(1)將被應(yīng)用到他們的子節(jié)點(diǎn);否則,順序更小的變量成為合并二元決策圖的新的根節(jié)點(diǎn),然后規(guī)則(1)應(yīng)用到所有順序比該節(jié)點(diǎn)更小的子結(jié)點(diǎn),其他的子二元決策圖模型則作為一個(gè)整體.直到子表達(dá)式(Gi,Fi)中的一個(gè)變成了常量′1′或者′0′之前,整個(gè)規(guī)則被遞歸的應(yīng)用到子表達(dá)式之間的邏輯操作.

3.3 基于BDD的可靠性分析方法

在內(nèi)部共因失效發(fā)生的情況下,本文定義ej作為SBS系統(tǒng)中服務(wù)j的產(chǎn)生傳播失效事件.據(jù)上小節(jié)的定義,傳播失效事件ej的發(fā)生概率可以給定為:

Pr{ej}=wj=qjεj

在外部共因失效發(fā)生的情況下,本文定義ej用于表示CCG中的wj引發(fā)的外部共因失效事件,該事件的概率可以給定為:

Pr{ej}=εj

給定系統(tǒng)結(jié)構(gòu)方程φh,利用已知信息完成系統(tǒng)結(jié)構(gòu)方程可以得到系統(tǒng)失效的邏輯表達(dá)式.利用故障樹(shù)結(jié)點(diǎn)表示SBS系統(tǒng)中服務(wù),用AND門和OR門表示邏輯關(guān)系中的與關(guān)系和或關(guān)系就可以得到SBS系統(tǒng)可靠性的故障樹(shù)模型.在上述故障樹(shù)模型的基礎(chǔ)上,本文提出的SBS分析法可以由以下三步進(jìn)行分析:

Step1.故障樹(shù)模型的擴(kuò)展

根據(jù)SBS系統(tǒng)所涉及的內(nèi)部/外部共因失效,將基本故障樹(shù)模型擴(kuò)展為包含共因失效關(guān)系的故障樹(shù)模型.擴(kuò)展的基本思想是:利用邏輯OR門將引起共因失效事件和由它引起的失效服務(wù)集合連接到一起.根據(jù)共因失效類型的不同,分為兩種情況討論:

內(nèi)部共因失效情況:對(duì)于CCG內(nèi)的每一個(gè)元素wj,需要在SBS系統(tǒng)的故障樹(shù)模型內(nèi)添加一個(gè)OR門,并且將wj內(nèi)所涉及的所有服務(wù)的原始失效事件和該傳播失效事件都連接到該OR門.對(duì)于上述所有事件,原始失效事件與傳播失效事件之間相互獨(dú)立.

外部共因失效情況:對(duì)于至少出現(xiàn)在一個(gè)CCG內(nèi)的元素,添加一個(gè)OR門連接原始失效事件與所有CCG影響的元素.

Step2.SBS系統(tǒng)的二元決策圖模型的生成

利用傳統(tǒng)方法生成二元決策圖模型,需要注意的是,規(guī)則(1)在這一步驟中被應(yīng)用于從擴(kuò)展的故障樹(shù)模型中生成二元決策圖模型.

Step3.SBS系統(tǒng)的二元決策圖模型的代入求解

4 實(shí)例分析

本小節(jié)將對(duì)一個(gè)包含5個(gè)具體服務(wù)的SBS系統(tǒng)進(jìn)行可靠性分析.首先,對(duì)實(shí)例系統(tǒng)進(jìn)行介紹;然后,對(duì)內(nèi)部/外部共因失效進(jìn)行分情況討論;最后,根據(jù)得到的數(shù)值結(jié)果與傳統(tǒng)BDD可靠性分析方法比較.

4.1 實(shí)例介紹

實(shí)例系統(tǒng)是一個(gè)旅游景點(diǎn)自動(dòng)導(dǎo)航應(yīng)用,各服務(wù)之間的邏輯關(guān)系如圖1所示：

圖1 SBS系統(tǒng)實(shí)例Fig.1 SBS system instance

其中,系統(tǒng)首先要進(jìn)行景點(diǎn)定位,這一步驟可以通過(guò)服務(wù)3提供的GPS定位;也可以通過(guò)服務(wù)1上傳景點(diǎn)照片;根據(jù)上傳的照片,服務(wù)2對(duì)景點(diǎn)進(jìn)行定位;在進(jìn)行完定位操作之后,服務(wù)4將根據(jù)定位結(jié)果將該景點(diǎn)的介紹信息發(fā)送給使用者;最后,服務(wù)5將后續(xù)游覽路線推薦信息發(fā)送給使用者.根據(jù)圖1,該系統(tǒng)可靠性的故障樹(shù)模型如圖2所示.

圖2 SBS系統(tǒng)故障樹(shù)模型實(shí)例Fig.2 SBS system fault tree model instance

在實(shí)際運(yùn)行過(guò)程中,實(shí)例系統(tǒng)存在以下三點(diǎn)可能導(dǎo)致共因失效:服務(wù)2和服務(wù)4共享景點(diǎn)數(shù)據(jù)庫(kù);服務(wù)3和服務(wù)5共享地理數(shù)據(jù)庫(kù);服務(wù)2又依賴于服務(wù)1傳遞的信息.具體情況如圖3所示.

圖3 SBS系統(tǒng)資源共享情況實(shí)例Fig.3 SBS system resource sharing instance

4.2 內(nèi)部共因失效情況

系統(tǒng)中包含了一組內(nèi)部共因失效CCGw1={1,2},其中服務(wù)1到服務(wù)2的傳播失效概率為ε1.剩余服務(wù)不能引起傳播失效,所以有ε2=ε3=ε4=ε5=0.

Step1.擴(kuò)展基本故障樹(shù)模型,使其包含內(nèi)部共因失效事件.添加一個(gè)邏輯OR門連接CCGw1中全部服務(wù)的原始失效事件和傳播失效事件,如圖4所示.

圖4 SBS系統(tǒng)內(nèi)部共因失效故障樹(shù)模型實(shí)例Fig.4 Example of common cause failure tree model in SBS interior

Step2.生成BDD模型.應(yīng)用BDD操作規(guī)則(1),并采用序列5→4→3→2→1→w1,得到BDD如圖5所示.

圖5 SBS系統(tǒng)內(nèi)部共因失效BDD模型實(shí)例Fig.5 Example of common cause failure BDD model in SBS interior

Step3.SBS系統(tǒng)可靠性計(jì)算.根據(jù)上一步生成的BDD模型,易見(jiàn)從根結(jié)點(diǎn)到底端結(jié)點(diǎn)“0”有兩條路徑:

因此,SBS系統(tǒng)的可靠性可以通過(guò)如下公式得到,

4.3 外部共因失效情況

圖6 SBS系統(tǒng)外部共因失效故障樹(shù)模型實(shí)例Fig.6 Example of common fault failure tree model in SBS system external

系統(tǒng)中包含了兩組內(nèi)部共因失效CCGw2={2,5}、w3={3,4},這兩組外部共因失效的發(fā)生概率為ε2,ε3.

Step1.擴(kuò)展基本故障樹(shù)模型,使其包含外部共因失效事件.為CCG中的每一個(gè)服務(wù)添加一個(gè)邏輯OR門,連接該服務(wù)的原始失效事件和共因失效事件,如圖6所示.

Step2.生成BDD模型.應(yīng)用BDD操作規(guī)則,并采用序列e2→e1→5→4→3→2→1,得到BDD如圖7所示.

圖7 實(shí)例SBS系統(tǒng)外部共因失效BDD模型Fig.7 Example of common cause failure BDD model in SBS system external

Step3.SBS系統(tǒng)可靠性計(jì)算.根據(jù)上一步生成的BDD模型,易見(jiàn)從根結(jié)點(diǎn)到底端結(jié)點(diǎn)“0”有兩條路徑:

因此,SBS系統(tǒng)的可靠性可以通過(guò)如下公式得到,

4.4 結(jié)果分析

表1顯示了實(shí)例SBS系統(tǒng)所有服務(wù)的可靠性;

表1 實(shí)例SBS系統(tǒng)服務(wù)可靠性Table 1 SBS system service reliability instance

表2顯示SBS系統(tǒng)所有服務(wù)傳播失效事件的發(fā)生概率;

表2 SBS系統(tǒng)服務(wù)傳播失效事件概率實(shí)例Table 2 SBS system services propagate failure probability instances

表3顯示了2個(gè)共享資源的失效發(fā)生概率;

表3 SBS系統(tǒng)服務(wù)共享資源失效事件概率實(shí)例Table 3 SBS system service shared resource failure event probability instance

根據(jù)表1、表2及表3中的已知數(shù)據(jù)以及故障樹(shù)模型的建立可以求得考慮內(nèi)部/外部共因失效的SBS可靠性分別為95.67%、77.81%.作為對(duì)比,利用傳統(tǒng)BDD方法不考慮共因失效的可靠性為96.35%,考慮共因失效的結(jié)果分別下降了0.71%和19.2%.綜上,在SBS系統(tǒng)可靠性分析中考慮內(nèi)部/外部共因失效對(duì)于求解結(jié)果的精度有著重要的意義;同時(shí),本文提出的算法可有效的計(jì)算受限于共因失效的SBS系統(tǒng)的可靠性.

5 結(jié) 論

針對(duì)現(xiàn)有SBS系統(tǒng)可靠性研究沒(méi)有考慮外部/內(nèi)部共因失效這一問(wèn)題,本文提出了一種基于二元決策圖的SBS可靠性分析方法.通過(guò)對(duì)實(shí)例的分析可知,在研究SBS系統(tǒng)可靠性的過(guò)程中是否考慮內(nèi)部/外部共因失效對(duì)求解精度有著重要的影響,本文提出分析方法可以有效的計(jì)算受限于共因失效的SBS系統(tǒng)的可靠性.