采用節(jié)點流守恒求取多狀態(tài)網(wǎng)絡(luò)d－最小路集的改進算法

褚洪彥（南京信息職業(yè)技術(shù)學(xué)院計算機與軟件學(xué)院，江蘇南京210023）

采用節(jié)點流守恒求取多狀態(tài)網(wǎng)絡(luò)d－最小路集的改進算法

褚洪彥
（南京信息職業(yè)技術(shù)學(xué)院計算機與軟件學(xué)院，江蘇南京210023）

針對多狀態(tài)網(wǎng)絡(luò)可靠度的計算問題，給出一種求解多狀態(tài)網(wǎng)絡(luò)d－最小路集的改進算法.引入可行流向量，并將網(wǎng)絡(luò)中的雙向邊等效為單向邊，使算法對網(wǎng)絡(luò)中邊的容量取值無特殊要求，且可用于含雙向邊的網(wǎng)絡(luò)，適用性更強.通過引入邊的容量下確界，并將網(wǎng)絡(luò)中的反向邊等效為單向邊，減少求取d－最小路集可行解時需枚舉的解數(shù)目，降低算法復(fù)雜度.以多狀態(tài)網(wǎng)絡(luò)為例，進行分析驗證.結(jié)果表明：該算法可以準確得到多狀態(tài)網(wǎng)絡(luò)所有d－最小路集.

網(wǎng)絡(luò)可靠度；多狀態(tài)網(wǎng)絡(luò)；最小路集；可行流向量

學(xué)者對網(wǎng)絡(luò)系統(tǒng)可靠性計算方面進行了大量研究，已經(jīng)給出許多計算方法，如真值表法、全概率分解法、蒙特卡諾圖法、最小路集和最小割集法等［1－2］.真值表法是最原始的計算系統(tǒng)可靠性的方法，只適用于小型網(wǎng)絡(luò).全概率分解法的基本思想是將一個復(fù)雜的網(wǎng)絡(luò)系統(tǒng)分解為若干個相當(dāng)簡單的子系統(tǒng)，當(dāng)網(wǎng)絡(luò)規(guī)模較大時，這種方法也難以實用.對于大型復(fù)雜網(wǎng)絡(luò)系統(tǒng)，基于最小路集和最小割集的方法十分有效，應(yīng)用最為廣泛［3－12］.d－最小路集從成功的角度描述多狀態(tài)網(wǎng)絡(luò)的結(jié)構(gòu)，是眾多可靠度算法的基礎(chǔ).已有的求取d－最小路集的算法一般需要事先求取網(wǎng)絡(luò)所有最小路集，過程復(fù)雜，計算繁瑣.本文提出一種不需網(wǎng)絡(luò)最小路集，直接求取d－最小路集的方法.

1 改進算法

1.1 算法原理

定義｜E｜維向量F＝（f1，f2，…，fi，…，f｜E｜），其中，fi表示網(wǎng)絡(luò)中邊ei中的流量，基于流守恒定律向量，F(xiàn)稱為一個可行流向量，當(dāng)且僅當(dāng)同時滿足式（1）～（3），即

因fi的取值集合不是Bi，而｛0，1，…，bi，ni｝，故滿足上述條件的可行流向量F是存在的.令

則網(wǎng)絡(luò)狀態(tài)向量X即d－最小路集的可行解.

綜合考慮這兩種情況，式（3）可分解為

式（4）變?yōu)?/p>

求取d－最小割集的算法中，邊容量下確界的定義有效降低了算法的復(fù)雜度，文中提出一個計算d－最小割集可行解對應(yīng)的邊的容量下確界In f1（ei）的方法.基于引理1，將邊的容量下確界In f2（ei）引入計算d－最小路集的算法中，增強式（7）～（9）的約束性.

基于引理1，將式（7）～（9）變?yōu)?/p>

1.2 算法步驟

基于上述分析，改進Yeh的算法［6］后，求解d－最小路集有以下6個步驟.

步驟2 若網(wǎng)絡(luò)中存在雙向邊，取任一方向，將其變?yōu)閱蜗蜻?

步驟3 若網(wǎng)絡(luò)中某兩節(jié)點間存在兩條反向邊，將其合并為一條單向邊.

步驟4 基于式（1），（2），式（11）～（13）及式（5），（6），可得所有可行流向量F.

步驟5 基于式（10），可得所有可行流向量F對應(yīng)的d－最小路集可行解X.

步驟6 比較所有的可行解，可行解X如不存在可行解Y滿足Y≤X，則X就是一個d－最小路集.

2 算法分析

網(wǎng)絡(luò)中各邊的取值集合分別為B1＝｛0，1，2，3｝，B2＝B6＝｛0，1，2，3｝，B3＝B4＝B5＝｛0，1｝，d＝3.

步驟1 由引理1，得In f2（e1）＝2，In f2（e2）＝In f2（e6）＝1，In f2（e3）＝In f2（e4）＝In f2（e5）＝0.

步驟2 網(wǎng)絡(luò)中無雙向邊，跳過該步驟.

步驟3 網(wǎng)絡(luò)中節(jié)點v2，v3間存在反向邊e3，e4，將其合并為一條單向邊e7，對應(yīng)網(wǎng)絡(luò)如圖2所示.

圖1 多狀態(tài)網(wǎng)絡(luò)Fig.1 Multistate network

圖2 合并后的多狀態(tài)網(wǎng)絡(luò)Fig.2 Combined multistate network

步驟4 基于式（1）～（2）及式（11）～（13），可得

由此可得F′＝（f1，f2，f5，f6，f7）可能值為（3，2，0，1，1），（2，2，1，1，0），（2，1，1，2，1），基于式（14）得f3＝f7，f4＝0，即可行流向量F＝（f1，f2，f3，f4，f5，f6）所有可能值為（3，2，1，0，0，1），（2，2，0，0，1，1），（2，1，1，0，1，2）.

步驟5 基于式（10），可得所有可行解X為（3，2，1，0，0，1），（2，2，0，0，1，1），（2，1，1，0，1，2）.

步驟6 兩兩比較，可得網(wǎng)絡(luò)所有3－最小路集.與文獻［8］結(jié)果對比，可知算法結(jié)果是正確的.

在橋型網(wǎng)絡(luò)中，若取值集合均為｛0，3，5｝，d＝5.基于引理1，可得In f2（e1）＝0，i＝1，2，…，5.基于式（1）～（2）及式（11），可得

求解式（18）～（21），可得所有可行流向量F.

基于所有可行流向量F，按照式（10）得到對應(yīng)的所有可行解X，如表1所示.通過比較可得該網(wǎng)絡(luò)所有5－最小路集：（5，5，0，0，0），（5，3，3，0，3），（5，0，5，0，5），（3，3，0，3，3），（3，0，3，3，5），（0，0，0，5，5），并未像Yeh［6］及其改進算法一樣遺漏（3，3，0，3，3）

表1 網(wǎng)絡(luò)的所有可行流向量和可行解Tab.1 All feasible flow vectors and feasible solutions of the network

3 結(jié)束語

研究求解多狀態(tài)網(wǎng)絡(luò)d－最小路集的方法，改進后的算法不需要求取網(wǎng)絡(luò)所有最小路集.通過引入可行流向量，并將網(wǎng)絡(luò)中的雙向邊等效為單向邊，使算法對網(wǎng)絡(luò)中邊的容量取值無特殊要求，且可用于含雙向邊的網(wǎng)絡(luò)，適用性更強.通過引入邊的容量下確界，并將網(wǎng)絡(luò)中的反向邊等效為單向邊，減少求取d－最小路集可行解時需枚舉的解數(shù)目，降低算法復(fù)雜度.

［1］ 李東魁.網(wǎng)絡(luò)系統(tǒng)可靠度的BDD算法［J］.通信技術(shù)，2009，42（11）：149－150.

［2］ 駱劍鋒，陳俞強.采用環(huán)加星型網(wǎng)絡(luò)結(jié)構(gòu)負載均衡集群技術(shù)的云平臺設(shè)計［J］.華僑大學(xué)學(xué)報（自然科學(xué)版），2016，37（2）：164－167.

［3］ CHEN Run，MO Yong，PAN Zhan.Performance improvement of edge expansion technique for BDD－based network reliability analysis［J］.Journal of Computers，2013，8（9）：2190－2196.

［4］ PAN Zhan，MO Yong，RING Lin，et al.New insights into breadth－first search edge ordering of regular networks for terminal－pair reliability analysis［J］.Journal of Risk and Reliability，2014，228（1）：83－92.

［5］ YANG Xiaohong，CHEN Guo，SUN Bang，et al.Bus transport network model with ideal n－depth clique network topology［J］.Statistical Mechanics and its Applications，2011，390（23）：4660－4672.

［6］ JAVANBARG M B，SCAWTHORN C，KIYONO J，et al.Reliability analysis of infrastructure and lifeline networks using OBDD［C］∥Proceeding of 10th International Conference on Structural Safety and Reliability.Osaka：IEEE Press，2009：3463－3470.

［7］ YEH W C.A revised layered－network algorithm to search for all d－minpaths of a limited－flow acyclic network［J］.Transations on Reliability，1998，47（4）：436－442.

［8］ 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.

［9］ YEH W C.A simple method to verify all d－minimal path candidates of a limited－flow network and its reliability［J］.Advanced Manufacturing Technology，2002，20（1）：77－81.

［10］ YEH W C.A novel methold for the network reliability in terms of capacitated－minimum－paths without knowing minimum－paths in advance［J］.Jourual Operarioual Research Society，2005，56（10）：1235－1240.

［11］ ZHAO Peixin，ZHANG Xin.A survey on reliability evaluation of stochastic－flow networks in terms of minimal paths［J］.International Conference on Information and Computer Science，2009，18（3）：49－54.

［12］ RAMIREZ－MARQUEZ J E，COIT D.A generalized multistate－based path vector approach to multistate two－terminal reliability［J］.Lie Transations，2006，38（6）：477－488.

（責(zé)任編輯：錢筠 英文審校：吳逢鐵）

Improved Algorithm for d?Minimal Path Set of Multistate Network Using Node Flow Conservation

CHU Hongyan
（School of Computer and Software，Nanjing College of Infomation Technology，Nanjing 210023，China）

To consider the calculation problem of the multistate network reliability，an improved algorithm for multistate network d－minimal path set was proposed.The two－way side of the network is equivalent to one side by introducing feasible flow vector.The capacity of the edge of the network is not special required.And it can be used for a network with two sides.The algorithm is more applicable.By the introduction the capacity of the edge.The reverse side of the network is equivalent to one side.Therefore，it educe the the viable solution enumerated number of the d－minimal path set，and the complexity of the algorithm.To verify the results，it shows that the proposed algorithm can acuurately obtain all d－minimal path set of the multistate network.

network reliability；multistate network；minimal path set；feasible flow vector

O 213.2

A

1000－5013（2016）04－0511－04

10.11830／ISSN.1000－5013.201604024

2016－05－05

褚洪彥（1968－），男，副教授，主要從事信息系統(tǒng)、網(wǎng)絡(luò)體系結(jié)構(gòu)的研究.E－mail：chu＿hy＠163.com.

國家自然科學(xué)基金資助項目（61300122）