郭曉勇，董榮勝，朱陽陽

(桂林電子科技大學 計算機與信息安全學院，廣西 桂林　541004)

?

基于MDD的多狀態(tài)網絡二端可靠性算法

郭曉勇，董榮勝，朱陽陽

(桂林電子科技大學 計算機與信息安全學院，廣西 桂林541004)

為解決多狀態(tài)網絡二端可靠性問題，提出了多值離散概率模型MDD_WS2TR，基于該模型給出了MFMC_MDD算法。該算法基于最大流最小割思想，對最小割中的邊進行合并，過濾掉稠密網絡中無關緊要的邊，降低了計算量。在構建網絡MDD的過程中，定義了操作算子TBoolean，該算子對MDD進行剪枝，壓縮了最大流的狀態(tài)組合空間，降低了MDD之間進行合并操作的復雜度。在一組隨機流網絡圖上對MFMC_MDD算法進行測試，驗證了MFMC_MDD算法的有效性。

多狀態(tài)；最大流；最小割；MDD；可靠性

在傳統的二狀態(tài)網絡中，系統的組件只有工作和失效2種狀態(tài)，系統的可靠性往往指的是源點s和終點t的連通概率。當組件的狀態(tài)為容量時，也只有0和另外一個正整數作為2種狀態(tài)。但是，在多狀態(tài)網絡中，每個節(jié)點或邊都有若干可能的容量，近幾年來，許多研究者對多狀態(tài)網絡模型做了大量的研究。給定需求水平d，此類具有離散、隨機容量的多狀態(tài)二端網絡的可靠性被定義為：從源點s到終點t，最大流大于等于需求水平d的概率[1]。針對該問題，現有的研究方法主要基于完全枚舉法和分解法。其中，完全枚舉法需要枚舉所有邊的狀態(tài)組合，計算復雜度很高。Doulliez等[2]提出一種著名的分解算法，將狀態(tài)空間不斷地分解，直至找到所有能夠滿足要求的狀態(tài)集合。而Alexopoulos[3]指出這個方法存在錯誤，可能得到一個不正確的答案。針對復雜系統，Ramirez-Marquez 等[4]提出了一個蒙特卡洛仿真的近似方法來計算多狀態(tài)網絡二端可靠性，但該方法的錯誤率達20%。還有一些學者[5-10]基于最小路集(minimal paths,簡稱MPs)或最小割集(minimal cuts,簡稱MCs)提出一種間接的方法尋找多狀態(tài)向量集(d-MPs/d-MCs)，再通過容斥原理計算多狀態(tài)網絡二端可靠性。然而，尋找MPs/MCs、d-MPs/d-MCs以及容斥原理都是NP-hard問題。2008年Jane等[11]首次提出基于d-flows的分解方法，無需預先求出d-MPs/d-MCs。2010年Jane等[1]提出一種基于d-cuts的分解算法，但該算法中的d-flows/d-cuts本質上類似于一個d-MPs/d-MCs，并且需要預先用最大流算法求得所有能夠傳輸d個需求的狀態(tài)向量，以這些狀態(tài)向量作為臨界向量，低于這個臨界向量的集合被繼續(xù)分解，直到篩選出所有滿足要求的狀態(tài)向量，復雜度依然很高。

因此，結合多值決策圖(multi-valued decision diagram，簡稱MDD)技術，提出一種可以更大程度地降低計算復雜度的MFMC_MDD算法。該算法利用MDD固有的特性，實現對狀態(tài)組合空間的隱式表示與搜索，提高了算法的執(zhí)行效率。相比于現存的d-MPs/d-MCs的研究方法，避免了求多狀態(tài)向量集d-MPs/d-MCs，也避免了用容斥原理計算可靠度。為了構建網絡的MDD，基于最大流最小割思想定義了OrSum、AndMin、TBoolean三個操作算子。其中，TBoolean操作算子對MDD進行剪枝，壓縮狀態(tài)空間，有效緩解了狀態(tài)空間爆炸。求解網絡可靠度時，采用遞歸的方法遍歷網絡的MDD，遍歷時間為O(n)，其中n表示生成的MDD的節(jié)點個數。為了檢驗MFMC_MDD算法的可行性，在一組隨機流網絡圖上對算法進行測試，驗證了算法的有效性。這種新的研究方法為多狀態(tài)網絡二端可靠性求解提供了新的思路。

1　多狀態(tài)網絡二端可靠性的多值離散概率模型

1.1多狀態(tài)網絡

定義1多狀態(tài)二端網絡的形式化模型為

其中：N為節(jié)點集合；s為源點；t為終點；E={ei|1≤i≤n}為邊的集合；M={M1,M2,···,Mn},Mi為邊ei的最大容量。

令wi表示邊ei的當前流量，則wi的取值范圍為0=ci0

針對多狀態(tài)二端網絡進行可靠性分析，問題的定義基于如下假設：

1)節(jié)點是可靠的；

2)每條邊的容量以一定的概率隨機分布；

3)每條邊的容量相互獨立；

4)遵循流量守恒定律。

最大流問題是運籌學和網絡分析的一個標準問題，最小割和最大流是一對對偶問題。針對邊上有多種整型容量的多狀態(tài)網絡，為了評估通過該網絡最大流不小于給定的需求水平d的概率，給出如下最大流最小割定理。

定理1若一個多狀態(tài)網絡的最小割集為{K1,K2,…,Kq}，則從源點s到終點t的最大流Fmax等于所有割中的最小流量：

(1)

1.2多值離散概率模型MDD_ WS2TR

MDD是一個多終端的有向無環(huán)圖形化數據結構[12]，表示一個多值輸入與輸出的離散函數F，如式(2)。針對多狀態(tài)網絡G，其離散概率模型MDD_WS2TR用MDD結構表示，如圖1所示。網絡的每條邊都相當于一個多值變量，輸出的值代表每個狀態(tài)下對應的流量。

圖1　MDD_WS2TRFig.1　MDD_WS2TR

(2)

其中：Di={0,1,…,mi}為變量ei的取值范圍；S={0,1,…,m}為函數的輸出集合。

1.2.1操作算子

為了構建網絡的MDD，定義OrSum、AndMin、TBoolean三個操作算子。依據最大流最小割思想，OrSum用于合并最小割內的邊，對最小割內邊上的流量求和；AndMin用于合并最小割，取所有最小割中最小的流量；TBoolean用于將每個最小割的MDD轉換為布爾類型(終節(jié)點只有0或1)，該操作可以簡化MDD結構，將狀態(tài)空間進一步壓縮，減少節(jié)點個數，壓縮了狀態(tài)空間。此外，將該操作用于OrSum之后，在算法執(zhí)行過程中使用，降低了AndMin操作的復雜度，提高了算法的執(zhí)行效率。各操作算子的操作規(guī)則如表1所示。

表1　OrSum、AndMin、 TBoolean操作規(guī)則

1.2.2計算可靠度

通過操作算子構建網絡的MDD，在生成了網絡的MDD結構后，通過遞歸方法：

(3)

遍歷所有的節(jié)點求可靠度P(F)，遍歷過程只需要自頂而下遍歷一次，時間復雜度為O(n)，其中n為生成的MDD節(jié)點個數。

2　算法設計

尋找最小割是一個NP-hard問題[11]，求解最優(yōu)變量序是一個NP-complete問題[13]。所以，預先求出最小割集和變量序，基于此，提出了評估多狀態(tài)網絡二端可靠性的MFMC_MDD算法。假設最小割集為{K1,K2,…,Kq}，算法的執(zhí)行步驟分為2步：

1)將預先求出的最小割集存于鄰接表中，依次訪問最小割Ki中的每一條邊ei，并利用操作算子OrSum合并Ki中的每條邊的MDD，從而構建出最小割Ki的MDD；通過TBoolean算子對Ki的MDD進行剪枝，進而簡化為布爾類型；利用操作算子AndMin合并所有最小割的MDD，進而生成整個網絡的MDD。偽代碼為：

2)自頂而下遞歸遍歷生成的網絡MDD，利用式(3)求網絡的可靠度。偽代碼為：

3　實例分析

為了簡單直觀地闡述MFMC_MDD算法，以圖2作為基準測試網絡對算法進行分析。通過求解該基準網絡的二端可靠性，邊上有若干隨機的整型容量，說明了MFMC_MDD算法的計算過程，驗證了算法的可行性。測試網絡各個邊上的數據如表2所示。

圖2　測試網絡Fig.2　Test network

邊狀態(tài)狀態(tài)概率e101230.05550.100.250.60e2012-0.10000.300.60-e301--0.10000.90--e401--0.10000.90--e501--0.10000.90--e6012-0.05000.250.70-

已知需求水平d=3，最小割集MCs為：

變量序為：

求網絡的最大流不小于3的概率。求解步驟為：

1)利用操作算子OrSum依次構建最小割K1、K2、K3、K4的MDD；通過算子TBoolean對最小割Ki的MDD進行剪枝，進一步縮減狀態(tài)空間；再利用操作算子AndMin合并這些最小割的MDD，生成網絡的最終MDD。圖3為最小割K1的MDD。圖4為最終生成的多狀態(tài)網絡MDD,節(jié)點旁的數字代表可靠度，方框中為計算方法，頂端的節(jié)點可靠度為整個網絡的可靠度。

圖3　K1的MDDFig.3　MDD of K1

圖4　多狀態(tài)網絡的MDDFig.4　MDD of the multi-state network

2)遍歷最終生成的MDD，求得需求水平d=3時的可靠度為0.611 415，與文獻[1]中的可靠度一致。

4　實驗結果及分析

為了驗證MFMC_MDD算法的性能，從精確度、空間、時間3個方面對算法進行了測試。MFMC_MDD算法基于愛荷華州立大學開發(fā)的meddly庫，實現語言為C++。實驗環(huán)境為：Intel Xeon 2.13 GHz CPU,2 GB RAM,CentOS 5.5系統。

文獻[4]對圖2所示網絡的邊賦予了4組不同的概率值測試其可靠性，為了檢驗算法的正確性，同樣使用文獻[4]提供的4組數據對圖2的網絡可靠性進行測試。結果表明，得出的可靠性值與真實值完全一致，說明了MFMC_MDD算法能夠精確計算多狀態(tài)網絡的二端可靠性。

為了檢驗MFMC_MDD算法的時間和空間性能，使用隨機圖生成器生成一組有向的隨機流網絡對算法進行測試，因為研究的是節(jié)點可靠的多狀態(tài)網絡，所以生成的這組網絡均為10個節(jié)點，邊分別為21、23、26、30。假設網絡的邊的容量分別為0、1、3，各個容量對應的概率分別為0.05、0.25、0.70。算法的測試結果如表3所示。實驗結果表明：1)算法的執(zhí)行時間依賴于需求水平d。其中，當狀態(tài)空間達到330，d=1時，算法運行時間小于1 s；d=3時，算法運行時間小于90 s。2)隨著需求水平d的增大，MDD的節(jié)點個數增多，但是與呈指數級的狀態(tài)空間相比，MDD的節(jié)點個數少了很多，節(jié)省了大量的狀態(tài)存儲空間，與完全枚舉法相比，MFMC_MDD算法是快速有效的。

表3　實驗結果

5　結束語

計算多狀態(tài)網絡二端可靠性是一個典型的網絡可靠性問題，針對該問題，提出了求解多狀態(tài)二端可靠性的多值離散概率模型，并給出了MFMC_MDD算法。該算法基于最大流最小割思想來構建網絡的MDD。通過OrSum操作算子對最小割中的邊進行合并，構建最小割的MDD； TBoolean操作算子將最小割的MDD轉換為布爾類型，對MDD進行剪枝，壓縮了狀態(tài)空間；AndMin算子對最小割進行合并，構建出整個網絡的MDD。遍歷網絡的MDD，可以求得網絡的可靠性。實驗結果表明，MFMC_MDD算法可以精確有效地評估多狀態(tài)網絡的二端可靠性。

[1]JANE C C,LAIH Y W.Computing multi-state two-terminal reliability through critical arc states that interrupt demand[J].IEEE Transactions on Reliability, 2010,59(2):338-345.

[2]DOULLIEZ P,JAMOULLE E.Tansportation networks with random arc capacities[J].Recherche Operationnelle, 1972,6(3):45-59.

[3]ALEXOPOULOS C.A note on state-space decomposition methods for analyzing stochastic flow networks[J].IEEE Transactions on Reliability,1995,44(2):354-357.

[4]RAMIREZ-MARQUEZ J E,COIT D W.A Monte-Carlo simulation approach for approximating multi-state two-terminal reliability[J].Reliability Engineering and System Safety,2005,87(2):253-264.

[5]YEH W C.A simple MC-based algorithm for evaluating reliability of stochastic-flow network with unreliable nodes[J].Reliability Engineering and System Safety,2004, 83(1):47-55.

[6]YEH W C.A novel method for the network reliability in terms of capacitated-minimum-paths without knowing minimum-paths in advance[J].Journal of the Operational Research Society,2005,56(10):1235-1240.

[7]LIN Y K.Using minimal cuts to evaluate the system reliability of a stochastic-flow network with failures at nodes and arcs[J].Reliability Engineering and System Safety,2002,75(1):41-46.

[8]LIN Y K.Reliability of a stochastic-flow network with unreliable branches and nodes,under budget constraints[J]. IEEE Transactions on Reliability,2004,53(3):381-387.

[9]LIN Y K.System reliability evaluation for a multistate supply chain network with failure nodes using minimal paths[J].IEEE Transactions on Reliability,2009,58(1): 34-40.

[10]LIN Y K.A simple algorithm for reliability evaluation of a stochastic-flow network with node failure[J].Computers and Operations Research,2001,28(13):1277-1285.

[11]JANE C C,LAIH Y W.A practical algorithm for computing multi-state two-terminal reliability[J].IEEE Transactions on Reliability,2008,57(2):295-302.

[12]SRINIVASAN A,HAM T,MALIK S,et al.Algorithms for discrete function manipulation[C]//IEEE International Conference on Computer-Aided Design,1990:92-95.

[13]BOLLIG B,WEGENER I.Improving the variable ordering of OBDDs is NP-complete[J].IEEE Transactions on Computers,1996,45(9):993-1002.

編輯：梁王歡

An MDD-based algorithm for computing multi-state two-terminal reliability

GUO Xiaoyong, DONG Rongsheng, ZHU Yangyang

(School of Computer and Information Security， Guilin University of Electronic Technology， Guilin 541004, China)

In order to compute the multi-state two-terminal reliability, a multi-valued discrete probability model MDD_WS2TR is defined. MFMC_MDD algorithm based on max-flow min-cut theorem is proposed, which combines the edges in the minimal cuts without considering the insignificant edge in the dense network. Especially, in the process of building MDD of the network, the operator TBoolean is defined to prune the MDD. Then the state space is compressed and the complexity of merging MDD is reduced. Finally MFMC_MDD algorithm is tested on a group of stochastic flow networks. The experimental results show that the proposed algorithm is effective.

multi-state; maximum flow; minimal cut; MDD; reliability

2015-12-29

國家自然科學基金(61363070)

董榮勝(1965-)，男，湖北黃岡人，教授，研究方向為計算思維、網絡可靠性、形式化技術。E-mail:ccrsdong@guet.edu.cn

TP302.7

A

1673-808X(2016)04-0305-06

引文格式：郭曉勇，董榮勝，朱陽陽.基于MDD的多狀態(tài)網絡二端可靠性算法[J].桂林電子科技大學學報，2016,36(4)：305-310.