多狀態(tài)不交化路徑可靠性分析的符號算法

李鳳英，何志偉，董榮勝

(桂林電子科技大學(xué)廣西可信軟件重點(diǎn)實驗室 廣西 桂林 541004)

隨著網(wǎng)絡(luò)技術(shù)的不斷發(fā)展，網(wǎng)絡(luò)已融入生活的各個方面，如運(yùn)輸網(wǎng)絡(luò)、移動自組網(wǎng)絡(luò)、計算機(jī)和通信網(wǎng)絡(luò)等[1-3]。對于上述網(wǎng)絡(luò)系統(tǒng)，常借助于隨機(jī)流網(wǎng)絡(luò)(stochastic-flow network, SFN)進(jìn)行刻畫描述，有關(guān)隨機(jī)流網(wǎng)絡(luò)的理論和應(yīng)用研究越來越受到人們關(guān)注。其中對于隨機(jī)流網(wǎng)絡(luò)的可靠性，既可通過蒙特卡洛方法[4]計算網(wǎng)絡(luò)可靠性的近似值，也可通過空間分解[5]、多值決策圖[6]、最小割集[7]或最小路集[8]等方法計算網(wǎng)絡(luò)可靠性的精確值。在最小路集基礎(chǔ)上，文獻(xiàn)[8]對單條路徑傳輸?shù)木W(wǎng)絡(luò)可靠性進(jìn)行了分析。為了縮短流量傳輸時間，文獻(xiàn)[9]將隨機(jī)流網(wǎng)絡(luò)流量從單路徑傳輸擴(kuò)展到兩條及多條不交化路徑(separate minimalpaths, SMPs)傳輸?shù)那闆r，并提出選擇一組可靠性最高的路徑作為網(wǎng)絡(luò)備用路徑，來保障工作路徑失效后網(wǎng)絡(luò)的順利傳輸。在2SMPs傳輸流量前提下，文獻(xiàn)[10-12]加入預(yù)算約束條件，基于最小路集的方法求解了隨機(jī)流網(wǎng)絡(luò)可靠性。文獻(xiàn)[13-14]定義了錯誤率和時間約束的多狀態(tài)網(wǎng)絡(luò)可靠性，并考慮到工作路徑失效后啟用備用路徑來保障網(wǎng)絡(luò)傳輸，提出基于路集的方法對狀態(tài)空間過濾獲取系統(tǒng)最小容量向量，運(yùn)用容斥原理求解隨機(jī)流網(wǎng)絡(luò)可靠性。文獻(xiàn)[15]則認(rèn)為路徑還有可能一條一條地失效，通過枚舉單路徑失效情況，證實了單條備用路徑可以提高網(wǎng)絡(luò)傳輸可靠性。

對于一個包含2SMPs的復(fù)雜網(wǎng)絡(luò)系統(tǒng)，一方面獲取系統(tǒng)最小容量向量計算網(wǎng)絡(luò)可靠性需要存儲整個網(wǎng)絡(luò)的邊，并且包含了許多冗余路徑容量組合，尋找一種更加有效的方式對于該類問題求解有著實際的意義；另一方面，通過枚舉網(wǎng)絡(luò)各路徑最小容量向量的方式計算備用路徑可靠性，運(yùn)算量非常龐大，故需要一種簡潔的解決方法選擇網(wǎng)絡(luò)可靠的備用路徑。為此，本文首先針對算法(d, T, B, (Pi,Pj))-LBPs[15]計算2SMPs可靠性需要存儲整個網(wǎng)絡(luò)的邊以及存在冗余路徑容量的問題，提出基于多值決策圖(multi-valued decision diagram, MDD)的可靠性分析算法MDD_2SMPs。該算法利用MDD能夠雙向反映組件狀態(tài)與系統(tǒng)狀態(tài)關(guān)系的特點(diǎn)，通過自定義MDD操作算子，實現(xiàn)狀態(tài)空間、變量組合的隱式表示和搜索，減少路徑不相關(guān)邊的存儲；并在組合過程中引入約束剪枝策略過濾許多不必要的路徑，從而提高算法效率；同時給出了基于MDD的概率計算模型，使得可靠性計算更加直觀。其次，針對工作路徑失效后選擇網(wǎng)絡(luò)可靠備用路徑的問題，提出算法MDD_BMPs，該算法通過將網(wǎng)絡(luò)各路徑轉(zhuǎn)換為決策圖多值變量形式，降低了計算的復(fù)雜性。最后，通過基準(zhǔn)網(wǎng)絡(luò)實例，驗證了本文所提方法的正確性和有效性。

1 模型描述與假設(shè)

本文中，網(wǎng)絡(luò)邊上存在3種屬性：容量、時延和成本。容量表示單位時間內(nèi)邊上通過的最大數(shù)據(jù)量；時延表示數(shù)據(jù)在邊上傳輸花費(fèi)的固定時間；成本表示數(shù)據(jù)在邊上傳輸需要的費(fèi)用。綜上，SFN模型可以形式化為G=(N, E, M, L, B)，其中：

1) N表示網(wǎng)絡(luò)節(jié)點(diǎn)的集合，用節(jié)點(diǎn)s表示源點(diǎn)，t表示目標(biāo)節(jié)點(diǎn)；

2) E={ei|1≤i≤n}表示網(wǎng)絡(luò)邊的集合；

3) M= (M1,M2,…,Mn)，表示邊的狀態(tài)集，Mi={0,1,…,mi}表示邊ei所有互斥的狀態(tài)集，0表示完全失效，mi表示完全工作；

4) L=(l1, l2,…,ln)，li表示邊ei的傳輸時延；

5) B=(b1, b2,…,bn)，bi表示邊ei的傳輸成本。

本文分析過程基于如下假設(shè)[11,15]：

1) 節(jié)點(diǎn)完全可靠；2) 每條邊上的容量狀態(tài)相互獨(dú)立，并以一定概率隨機(jī)分布；3) 數(shù)據(jù)通過2SMPs傳輸；4) 網(wǎng)絡(luò)G遵循流量守恒定律。

2 方法與問題定義

2.1 多值決策圖(MDD)

MDD是一種基于香農(nóng)分解用于表示和操作多值邏輯函數(shù)的有向無環(huán)圖[16]。文獻(xiàn)[17]的結(jié)論表明，在多態(tài)網(wǎng)絡(luò)的可靠性分析中，MDD比OBDD具有較少的變量和較高的效率。在MDD中，用圓圈表示非終節(jié)點(diǎn)，代表結(jié)構(gòu)函數(shù)的一個變量；方框表示終節(jié)點(diǎn)，代表多狀態(tài)系統(tǒng)的狀態(tài)，系統(tǒng)有多少個可能的狀態(tài)，對應(yīng)的MDD就存在多少個終節(jié)點(diǎn)；單向箭線表示非終節(jié)點(diǎn)的外向分支，每個非終節(jié)點(diǎn)有多少種狀態(tài)就存在多少條外向分支。假設(shè)網(wǎng)絡(luò)中某條邊存在m個可能的狀態(tài)，則MDD終節(jié)點(diǎn)從左到右依次表示為最劣狀態(tài)到最優(yōu)狀態(tài)。MDD能夠表示組件與系統(tǒng)狀態(tài)之間的關(guān)系，便于計算系統(tǒng)部分或整體處于某種狀態(tài)的概率。

圖1 邊ei的MDD結(jié)構(gòu)

圖1 給出了網(wǎng)絡(luò)中某條邊的MDD結(jié)構(gòu)，可以觀察到邊ei存在m+1條外向分支，代表了該邊存在的m+1個獨(dú)立狀態(tài)，分別用0,1,…,mi表示。其中，終節(jié)點(diǎn)0表示該邊完全失效，mi表示該邊處于最優(yōu)狀態(tài)。

2.2 邏輯操作

根據(jù)MDD變量排序，按照順序?qū)⒙窂街忻織l邊轉(zhuǎn)換為決策圖的多值變量Xi，該路徑中各邊的MDD結(jié)構(gòu)同圖1。

定義 1 假設(shè)A和B分別代表了兩個子MDD的邏輯表達(dá)式，并且A和B的邏輯表達(dá)式均為case格式：A=case(x, A0,…,Am-1)和B=case(x, B0,…,Bm-1)。通過定義相應(yīng)MDD操作算子可以得到連接A和B兩個子MDD的結(jié)構(gòu)，按照相同規(guī)則遞歸所有的邊或路徑則可以得到相應(yīng)路徑或系統(tǒng)的MDD結(jié)構(gòu)，為：

2.3 可靠性概率計算

MDD中根節(jié)點(diǎn)到達(dá)某個終節(jié)點(diǎn)的所有路徑概率之和表示系統(tǒng)處于該種狀態(tài)的概率。為了降低MDD概率計算復(fù)雜度，使用布爾操作進(jìn)一步簡化MDD結(jié)構(gòu)(根節(jié)點(diǎn)到達(dá)某個終節(jié)點(diǎn)滿足需求條件時，將終節(jié)點(diǎn)的值由實數(shù)類型置為布爾類型)。根據(jù)MDD性質(zhì)，計算系統(tǒng)處于非失效狀態(tài)下的概率時，從MDD根節(jié)點(diǎn)出發(fā)，尋找終節(jié)點(diǎn)非0的路徑，遞歸調(diào)用概率計算函數(shù)即可。

定義 2 多狀態(tài)系統(tǒng)G處于非失效狀態(tài)下的概率P(G)通過遞歸調(diào)用概率計算函數(shù)，自頂向下遍歷MDD結(jié)構(gòu)得出，有：

式中，Pyi=j表示標(biāo)識變量為yi的邊處于狀態(tài)j時的概率。終節(jié)點(diǎn)取值為0時，P(G)=0；終節(jié)點(diǎn)取值大于0時，P(G)=1。P(G)表示系統(tǒng)處于非失效狀態(tài)下的概率，對應(yīng)可靠性的值。

2.4 問題定義

本文中，網(wǎng)絡(luò)通過2SMPs傳輸?shù)目煽啃远x為：系統(tǒng)G在時間T和預(yù)算B約束條件下通過2SMPs從源點(diǎn)s到目標(biāo)節(jié)點(diǎn)t傳輸d單位數(shù)據(jù)的概率。不失一般性，假設(shè)路徑P1={e1, e2,…,ev}和P2={ev+1,ev+2,…,eu}為系統(tǒng)給定的2SMPs，d1和d2分別表示路徑P1和P2傳輸?shù)膯挝粩?shù)據(jù)量并且滿足d=d1+d2。相應(yīng)的，路徑P1和P2的傳輸時間和傳輸成本分別表示為LP1=le1+le2+…+lev，LP2=lev+1+lev+2+…+leu以及CP1=Ce1+Ce2+…+Cev，CP2=Cev+1+Cev+2+…+Ceu。

定義 3 任意一條路徑Pe，其單位時間內(nèi)傳輸?shù)臄?shù)據(jù)為minei∈Pewi，則路徑Pe的傳輸能力表示為：

推論 1 Pe在時間和預(yù)算約束下傳輸?shù)淖畲髷?shù)據(jù)量表達(dá)式，且A和B的邏輯表達(dá)式均為case格式：KPe，表示Pe在時間約束T下數(shù)據(jù)傳輸能力、預(yù)算約束B下數(shù)據(jù)傳輸能力dB和指定傳輸單位數(shù)據(jù)量d中的最小值。

2.5 備用路徑

假設(shè)Pi和Pj分別為網(wǎng)絡(luò)傳輸給定單位數(shù)據(jù)時預(yù)先給定的兩條工作路徑，備用路徑定義為：工作路徑Pi或Pj出現(xiàn)失效情況時，用來替換失效工作路徑Pi或Pj后完成數(shù)據(jù)傳輸可靠性最高的路徑。

根據(jù)文獻(xiàn)[15]定義的傳輸規(guī)則，備用路徑會在第一條工作路徑失效后立即觸發(fā)，其可靠性Pr(PiPj,Pk)(i, j, k=1, 2,…,n, i≠j≠k)計算為：

同理，第二條工作路徑失效后的可靠性Pr(PiPj,PkPkk)(i, j, k, kk=1, 2,…,m, i≠j≠k≠kk)計算為：

2.6 預(yù)算判斷

定義 4 網(wǎng)絡(luò)中任意一條路徑Pe，其傳輸de單位數(shù)據(jù)的預(yù)算F(de,Pe)等于路徑傳輸代價與傳輸單位數(shù)據(jù)量的乘積。

推論 2 已知P1和P2分別表示網(wǎng)絡(luò)中傳輸d單位數(shù)據(jù)的兩條工作路徑。如果CP1=CP2，則路徑P1和P2傳輸d單位數(shù)據(jù)的預(yù)算為固定值；如果CP1＜CP2，則路徑P1和P2傳輸d單位數(shù)據(jù)的預(yù)算隨著路徑P1傳輸數(shù)據(jù)的增加而逐漸減小。

證明：當(dāng)CP1=CP2時，預(yù)算F(d)=CP1d1+CP2(dd1)=CP1d；當(dāng)CP1＜CP2時，預(yù)算F(d)=CP1d1+CP2(dd1)。假設(shè)存在一個任意小的正整數(shù)θ使得路徑P1傳輸?shù)膯挝粩?shù)據(jù)為d1+θ，則路徑P2傳輸?shù)膯挝粩?shù)據(jù)為d-d1-θ，使得預(yù)算滿足Fθ(d)≥F(d)，而Fθ(d)=CP1(d1+θ)+CP2(d-d1θ)=F(d)-(CP2-CP1)θ，根據(jù)CP1＜CP2可知，(CP2-CP1)θ＞0，推出Fθ(d)＜F(d)，故假設(shè)不成立。

推論2說明網(wǎng)絡(luò)通過2SMPs傳輸d單位數(shù)據(jù)的預(yù)算情況。

3 基于MDD的可靠性分析算法

利用MDD能夠雙向反映組件狀態(tài)與系統(tǒng)狀態(tài)關(guān)系的特點(diǎn)，給出算法MDD_2SMPs計算2SMPs傳輸?shù)目煽啃砸约八惴∕DD_BMPs選擇網(wǎng)絡(luò)備用路徑。

3.1 算法MDD_2SMPs

算法MDD_2SMPs以網(wǎng)絡(luò)的2SMPs作為算法輸入，輸出結(jié)果表示網(wǎng)絡(luò)滿足傳輸需求的概率，對應(yīng)可靠性的值。該算法主要由4個步驟構(gòu)成：1) 判斷2SMPs是否滿足傳輸需求并計算傳輸成本CP1和CP2；2) 通過定義的And_Min操作，按照式(1)中的合成規(guī)則得到2SMPs的MDD結(jié)構(gòu)(MDD_P1和MDD_P2)；3) 根據(jù)MDD結(jié)構(gòu)中終節(jié)點(diǎn)值有序表示的路徑容量進(jìn)行相應(yīng)約束剪枝，通過執(zhí)行定義的Or_MDD操作合并MDD_P1和MDD_P2得到結(jié)構(gòu)MDD_result；4) 遍歷MDD_result中終節(jié)點(diǎn)非0的路徑，遞歸調(diào)用概率計算函數(shù)得到隨機(jī)流網(wǎng)絡(luò)(d, T, B,P1, P2)的可靠性REL_(d, T, B, P1, P2)。算法偽代碼如下：

Input: A stochastic-flow network (d, T, B, P1, P2)with two separate minimal paths, demand level d, time limitation T, and budget constraint B.

Output: The reliability of (d, T, B, P1, P2), that is REL_(d, T, B, P1, P2)

Step0 Initialization MDD_P1=0, MDD_P2=0,MDD_result=0, reliability=0

Step1 for j=1, 2, Compute KPj(M), CPj. Sort the two given SMPs in an ascending order

Step2 if KP1*CP1+(d-KP1)*CP2≤B

Construct MDD_P1, MDD_P2

MDD_P1←MDD_MPSet[1][1]

MDD_P2←MDD_MPSet[2][1]

LP1←0, LP2←0

for i←2 to length[MPSet[1]], length[MPSet [2]]do

LP1←LP1+li, LP2←LP2+li

MDD_P1←And_Min(MDD_P1, MDD_ei)

MDD_P2←And_Min(MDD_P2, MDD_ei)

end for

Step3 Get MDD_result

MDD_result←Or_MDD(MDD_P1,MDD_P2)

Step4 Compute Reliability (MDD_result)

if (MDD_result =0) then

return 0

else if (MDD_result is terminal node) then

if (MDD_result =1) then

return 1

else return 0

else (MDD_result is not terminal node)

for j←0 to mido

reliability←reliability+pj*Compute Reliability(MDD_result)

end for

REL_(d, T, B, P1, P2) ←reliability

return REL_(d, T, B, P1, P2)

end if

else return “over budget”

3.2 算法MDD_BMPs

算法MDD_BMPs以網(wǎng)絡(luò)的MPs作為算法輸入，輸出結(jié)果為選擇的備用路徑。算法相關(guān)背景工作同文獻(xiàn)[11,15]，假設(shè)網(wǎng)絡(luò)中MPs={P1,P2,…,Pn}已知。在得到網(wǎng)絡(luò)中各路徑以不同容量傳輸?shù)膯挝粩?shù)據(jù)信息后，該算法主要由3個步驟構(gòu)成：1) 執(zhí)行定義的And_Min操作，按照式(1)中的合成規(guī)則得到網(wǎng)絡(luò)各路徑的決策圖多值變量形式MDD_Pi；2) 遍歷MPs中所有與工作路徑都不相交的路徑，計算概率值；3) 選擇概率值最高的路徑作為網(wǎng)絡(luò)備用路徑。算法偽代碼表示如下：

Input: A stochastic flow network with all the minimal paths, demand level d, time limitation T, and budget constraint B.

Output: The optimal minimal path

Step0 Initialization MDD_P=0, reliability=0,MDD_result1=0, MDD_result2=0, S=0

Step1 Construct MDD_Pi, for i=1, 2, 3,…, n

MDD_Pi←MDD_MPSet[i]

end of for

Step2 Compute reliability

for j←3 to n do

MDD_result1←Or_MDD(MDD_P1,MDD_Pj)

MDD_result2←Or_MDD(MDD_P2,MDD_Pj)

end for

use (5) to get reliability

Step3 Return optimal minimal path

reliability=Rel_(d, T, B, (P3))

if Rel_(d, T, B, (Pj))＞probability then let Rel_(d, T, B, (Pj))=probability, and S=Pj

return S

3.3 復(fù)雜度分析

對于任意一個存在2SMPs的隨機(jī)流網(wǎng)絡(luò)，算法MDD_2SMPs的時間復(fù)雜度分析過程如下：1) 確定KP1和KP2花費(fèi)的時間最多為O(n)，因為每條路徑所含邊的數(shù)量不會超過n條。2) 假設(shè)m表示路徑邊上存在的最大狀態(tài)數(shù)，則生成MDD_ei的耗時最多為O(m)；已知MDD執(zhí)行邏輯與和邏輯或操作的耗時為O(n1n2)(n1和n2分別表示參與操作的兩個MDD的節(jié)點(diǎn)數(shù))，得到構(gòu)建MDD_Pi和MDD_Pj過程的耗時為O(nm)。3) 對路徑容量進(jìn)行約束剪枝耗時為O(nR1R2)(R1和R2分別表示參與操作的兩個MDD的終節(jié)點(diǎn)數(shù)量)，因為MDD_Pi和MDD_Pj終節(jié)點(diǎn)表示的路徑容量是唯一有序的，故只需訪問對應(yīng)的終節(jié)點(diǎn)值；在工作路徑合并過程中，定義的Or_MDD操作同樣是一種邏輯或操作，該過程耗時為O(n1n2)。4) 文獻(xiàn)[6]定理1關(guān)于MDD概率計算的復(fù)雜度分析過程可知，遍歷MDD_result計算可靠性的耗時為O(mn/n)。綜合以上分析，算法MDD_2SMPs復(fù)雜度可以表示為O(n2+nC+mn)。

4 實例分析

本節(jié)以文獻(xiàn)[11,15]使用的基準(zhǔn)網(wǎng)絡(luò)為例，說明可靠性分析算法MDD_2SMPs和備用路徑選擇算法MDD_BMPs具體執(zhí)行過程。網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)如圖2所示，圖中s表示源點(diǎn)，t表示目標(biāo)節(jié)點(diǎn)，a1～a22表示有22條邊，各邊的詳細(xì)信息在表1給出。實例中，網(wǎng)絡(luò)額定傳輸?shù)膯挝粩?shù)據(jù)d為200 Gb，時間T不超過13 s，預(yù)算B不高于2000元。網(wǎng)絡(luò)MPs已知條件下，假設(shè)工作路徑分別由P1={a1, a2, a3}和P2={a4, a5, a6}組成，網(wǎng)絡(luò)中與工作路徑P1和P2都不相交的路徑為：P3={a8, a9, a10}、P4={a11, a12, a13}、P5={a15, a16, a17}、P6={a18, a19, a20}、P7={a10, a11, a14}、P8={a15, a22}、P9={a18, a21, a22}及P10={a16, a17, a18, a21}。

4.1 可靠性計算

通過前文條件及表1信息，計算KP1=200、KP2=120、CP1=10、CP2=7。

1) 按照傳輸規(guī)則，路徑(P1, P2)滿足傳輸條件；已知CP2＜CP1，確定參照路徑P2。

2) 根據(jù)給出的變量順序，將路徑(P1, P2)中每條邊轉(zhuǎn)換為圖1所示的決策圖多值變量形式，并按照公式(1)中的合成規(guī)則，執(zhí)行定義的And_Min操作，分別得到圖3所示路徑P1的MDD結(jié)構(gòu)MDD_P1和圖4所示路徑P2的MDD結(jié)構(gòu)MDD_P2。

3) 利用MDD_P1和MDD_P2結(jié)構(gòu)中終節(jié)點(diǎn)值有序表示的路徑容量進(jìn)行約束剪枝，執(zhí)行Or_MDD操作合并路徑(P1, P2)。

①已知步驟1)選取的參照路徑為P2，觀察其終節(jié)點(diǎn)值從左至右依次為0、10、20、30、40，對應(yīng)路徑P2的5種容量情況。終節(jié)點(diǎn)值為0表示路徑P2完全失效，按照傳輸規(guī)則，計算P1滿足傳輸條件的路徑容量為40；并根據(jù)推論2可知預(yù)算取得最大值，終止預(yù)算判斷過程。

②路徑P2容量為10時，其傳輸?shù)膯挝粩?shù)據(jù)最多不超過30 Gb，按照傳輸規(guī)則，計算P1滿足傳輸條件的路徑容量至少為30。

同理，可以分別得到路徑P2容量為20、30和40時，P1上滿足傳輸條件的路徑容量。

③根據(jù)MDD原理及運(yùn)算規(guī)則，規(guī)約化簡得到圖5所示的結(jié)構(gòu)。

圖2 基準(zhǔn)網(wǎng)絡(luò)實例

圖3 路徑P1的MDD結(jié)構(gòu)

圖4 路徑P2的MDD結(jié)構(gòu)

圖5 MDD_result

表1 圖2中各邊數(shù)據(jù)信息

(續(xù)表)

表2 兩種算法獲取(d,T,B)下路徑所需容量的操作數(shù)

4) 自頂向下遍歷生成的結(jié)構(gòu)MDD_result，遞歸調(diào)用Compute Reliability函數(shù)，計算網(wǎng)絡(luò)可靠性值為REL_(200, 13, 2000, P1, P2)=0.700 624。

針對該網(wǎng)絡(luò)，表2給出了算法MDD_2SMPs與算法(d, T, B, (Pi, Pj))-LBPs計算2SMPs可靠性時，獲取(d, T, B)下路徑所需容量的操作數(shù)情況。以工作路徑P1={a1, a2, a3}和P2={a4, a5, a6}為例，本文算法通過定義And_Min操作算子，直接得到唯一且有序的路徑容量，只需根據(jù)MDD中終節(jié)點(diǎn)的值進(jìn)行約束剪枝，并且只需存儲工作路徑所含邊的信息(6條)。因此，算法MDD_2SMPs獲取(d, T, B)下工作路徑所需容量的操作數(shù)為6×5×5=150次。而文獻(xiàn)[15]中算法(d,T, B, (Pi, Pj))-LBPs根據(jù)路徑P1和P2存在的流量分配情況計算，通常會得到相同的路徑容量，如路徑(P1,P2)通過的流量為(80,120)、(90,110)或(100,100)時，得到的路徑容量均為(20,40)。為便于計算可靠性的值，還需構(gòu)建系統(tǒng)狀態(tài)空間向量(即文獻(xiàn)[15]中X向量)過濾重復(fù)的以及非最小的解，這些系統(tǒng)狀態(tài)空間向量存儲了整個網(wǎng)絡(luò)的邊(22條)，合計需要22×13+22×(13×12)=3 718次移除操作。對于網(wǎng)絡(luò)可靠性概率值，本文算法基于節(jié)點(diǎn)概率迭代計算；算法(d, T, B, (Pi, Pj))-LBPs獲取系統(tǒng)最小容量向量后，還需借助容斥原理等方法進(jìn)行計算。

表3 各路徑可能傳輸?shù)膯挝粩?shù)據(jù)

4.2 備用路徑選擇

利用MDD能夠雙向反映組件狀態(tài)與系統(tǒng)狀態(tài)的特點(diǎn)，算法MDD_BMPs通過將表3中各路徑傳輸?shù)膯挝粩?shù)據(jù)轉(zhuǎn)換為相應(yīng)的多狀態(tài)變量，大大簡化了計算的復(fù)雜性，具體過程如下。

1) 根據(jù)表3信息構(gòu)建各路徑的決策圖多值變量形式MDD_Pi。

2) 遍歷MPs中與路徑(P1,P2)都不相交的路徑(P3, P4, P5, P6, P7, P8, P9和P10)，計算可靠性值。

① 以路徑P3為例，由步驟1)得到圖6所示的決策圖多值變量形式MDD_P3。

② 計算CP1=10、CP2=7、CP3=9，確定路徑(P1,P3)和(P2, P3)變量序分別為P3＜P1和P2＜P3。

③ 由得到的變量序選取參照路徑，運(yùn)用推論2獲取對應(yīng)路徑的終節(jié)點(diǎn)狀態(tài)。

④ 最后，根據(jù)MDD概率計算函數(shù)及式(5)定義的傳輸規(guī)則，計算備用路徑為P3時的可靠性值Pr(P1P2, P3)=0.183 823 96。

3) 根據(jù)各路徑取值情況返回可靠性最高的路徑。

圖7為第一條工作路徑失效后，各路徑的可靠性取值情況，由此選擇備用路徑為P4，可靠性值Pr(P1P2,P4)=0.227 665。

圖6 路徑P3的MDD結(jié)構(gòu)

同理，第二條工作路徑失效后，根據(jù)圖8選擇備用路徑為P5，可靠性值Pr(P1P2,(P4P5))=0.068 328。

對于圖2所示網(wǎng)絡(luò)，算法MDD_BMPs的計算結(jié)果與文獻(xiàn)[15]算法(d, T, B, (Pk))-LBPs的計算結(jié)果一致。不同的是，算法MDD_BMPs通過將網(wǎng)絡(luò)各路徑轉(zhuǎn)換為決策圖多值變量形式，大大降低了計算的復(fù)雜性。以路徑P3執(zhí)行過程為例，算法MDD_BMPs判斷路徑(P1, P3)和(P2, P3)終節(jié)點(diǎn)狀態(tài)需要的操作數(shù)為50+50=100次；算法(d, T, B, (Pk))-LBPs則將路徑(P1,P2)分別與路徑P3組合獲取系統(tǒng)最小容量向量，該過程所需操作數(shù)為6 358+3 718=10 076次。

圖7 第一條路徑失效后各路徑的可靠性取值情況

圖8 第二條路徑失效后各路徑的可靠性取值情況

5 結(jié) 束 語

2SMPs傳輸?shù)碾S機(jī)流網(wǎng)絡(luò)可靠性分析，通常是求取系統(tǒng)最小容量向量，運(yùn)用容斥原理計算可靠性值。本文根據(jù)MDD能夠雙向反映組件狀態(tài)與系統(tǒng)狀態(tài)關(guān)系的特點(diǎn)，提出算法MDD_2SMPs，實例結(jié)果表明，相比獲取系統(tǒng)最小容量向量方法，本文算法主要有以下特點(diǎn)：1) 通過定義MDD操作算子，得到路徑容量是唯一有序的，減少了路徑容量的約束判斷；2) 在系統(tǒng)結(jié)構(gòu)不變情況下，可用于不同參數(shù)的可靠性分析，避免了存儲整個網(wǎng)絡(luò)的邊以及運(yùn)用容斥原理計算的繁瑣。此外，針對網(wǎng)絡(luò)工作路徑失效的問題，算法MDD_BMPs通過將網(wǎng)絡(luò)各路徑轉(zhuǎn)換為決策圖多值變量形式，大大降低了選擇可靠備用路徑的計算復(fù)雜性。