劉婷婷,張長勝,張 斌,王 鵬

(東北大學(xué) 計算機科學(xué)與工程學(xué)院,沈陽 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)在運行過程中,系統(tǒng)內(nèi)部服務(wù)之間的共享資源以及系統(tǒng)內(nèi)部信息傳遞的相互依賴關(guān)系的存在,使得系統(tǒng)的成功運行在絕大多數(shù)情況下受限于共因失效[2].共因失效泛指的是由于一個因素的發(fā)生導(dǎo)致系統(tǒng)多個組件同時失效這一現(xiàn)象.這種失效的誘因可以歸結(jié)為兩種:外部因素(例如,供電故障、共享服務(wù)器故障以及共享數(shù)據(jù)庫故障等等)和內(nèi)部因素(由系統(tǒng)內(nèi)部的服務(wù)故障或者傳播途徑的故障導(dǎo)致的傳播失效).目前絕大多數(shù)SBS系統(tǒng)的可靠性的研究[4-6]都假設(shè)服務(wù)之間相互獨立,并沒有考慮共因失效.極少數(shù)研究[2]考慮共因失效的研究也僅僅考慮了外部因素.為解決上述問題,本文提出一種考慮共因失效的SBS系統(tǒng)的可靠性分析方法.

2 研究背景

2.1 相關(guān)研究

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

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

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

BDD是一種有根的、有向的、非循環(huán)的基于圖的數(shù)據(jù)結(jié)構(gòu),基于香農(nóng)分解定理[20].結(jié)構(gòu)上,BDD由兩種類型的結(jié)點構(gòu)成:底端結(jié)點和非底端結(jié)點.對每一個BDD有且僅有一對0-結(jié)點和1-結(jié)點,表示布爾表達式的最終結(jié)果為0或者為1,底端結(jié)點位于整個圖結(jié)構(gòu)的末端因此沒有出邊只有入邊.每一個非底端結(jié)點都有兩條出邊,分別稱為0-邊(else-邊)和1-邊(then-邊),表示該結(jié)點代表變量的取值情況.其中,1-邊表示結(jié)點所輸入的值為1,同理0-邊表示結(jié)點所輸入的值為0.基于香農(nóng)分解定理,BDD中的任何一個非底端結(jié)點都能夠?qū)⒃摻Y(jié)點代表的布爾表達式編碼成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.并且外部失效因素的失效概率與個體失效概率相互獨立.

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

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

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

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

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

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

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)失效的邏輯表達式.利用故障樹結(jié)點表示SBS系統(tǒng)中服務(wù),用AND門和OR門表示邏輯關(guān)系中的與關(guān)系和或關(guān)系就可以得到SBS系統(tǒng)可靠性的故障樹模型.在上述故障樹模型的基礎(chǔ)上,本文提出的SBS分析法可以由以下三步進行分析:

Step1.故障樹模型的擴展

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

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

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

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

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

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

4 實例分析

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

4.1 實例介紹

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

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

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

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

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

圖3 SBS系統(tǒng)資源共享情況實例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.擴展基本故障樹模型,使其包含內(nèi)部共因失效事件.添加一個邏輯OR門連接CCGw1中全部服務(wù)的原始失效事件和傳播失效事件,如圖4所示.

圖4 SBS系統(tǒng)內(nèi)部共因失效故障樹模型實例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模型實例Fig.5 Example of common cause failure BDD model in SBS interior

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

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

4.3 外部共因失效情況

圖6 SBS系統(tǒng)外部共因失效故障樹模型實例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.擴展基本故障樹模型,使其包含外部共因失效事件.為CCG中的每一個服務(wù)添加一個邏輯OR門,連接該服務(wù)的原始失效事件和共因失效事件,如圖6所示.

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

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

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

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

4.4 結(jié)果分析

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

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

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

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

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

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

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

5 結(jié) 論

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