采用节点流守恒求取多状态网络d－最小路集的改进算法

褚洪彦（南京信息职业技术学院计算机与软件学院，江苏南京210023）

采用节点流守恒求取多状态网络d－最小路集的改进算法

褚洪彦
（南京信息职业技术学院计算机与软件学院，江苏南京210023）

针对多状态网络可靠度的计算问题，给出一种求解多状态网络d－最小路集的改进算法.引入可行流向量，并将网络中的双向边等效为单向边，使算法对网络中边的容量取值无特殊要求，且可用于含双向边的网络，适用性更强.通过引入边的容量下确界，并将网络中的反向边等效为单向边，减少求取d－最小路集可行解时需枚举的解数目，降低算法复杂度.以多状态网络为例，进行分析验证.结果表明：该算法可以准确得到多状态网络所有d－最小路集.

网络可靠度；多状态网络；最小路集；可行流向量

学者对网络系统可靠性计算方面进行了大量研究，已经给出许多计算方法，如真值表法、全概率分解法、蒙特卡诺图法、最小路集和最小割集法等［1－2］.真值表法是最原始的计算系统可靠性的方法，只适用于小型网络.全概率分解法的基本思想是将一个复杂的网络系统分解为若干个相当简单的子系统，当网络规模较大时，这种方法也难以实用.对于大型复杂网络系统，基于最小路集和最小割集的方法十分有效，应用最为广泛［3－12］.d－最小路集从成功的角度描述多状态网络的结构，是众多可靠度算法的基础.已有的求取d－最小路集的算法一般需要事先求取网络所有最小路集，过程复杂，计算繁琐.本文提出一种不需网络最小路集，直接求取d－最小路集的方法.

1 改进算法

1.1 算法原理

定义｜E｜维向量F＝（f1，f2，…，fi，…，f｜E｜），其中，fi表示网络中边ei中的流量，基于流守恒定律向量，F称为一个可行流向量，当且仅当同时满足式（1）～（3），即

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

则网络状态向量X即d－最小路集的可行解.

综合考虑这两种情况，式（3）可分解为

式（4）变为

求取d－最小割集的算法中，边容量下确界的定义有效降低了算法的复杂度，文中提出一个计算d－最小割集可行解对应的边的容量下确界In f1（ei）的方法.基于引理1，将边的容量下确界In f2（ei）引入计算d－最小路集的算法中，增强式（7）～（9）的约束性.

基于引理1，将式（7）～（9）变为

1.2 算法步骤

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

步骤2 若网络中存在双向边，取任一方向，将其变为单向边.

步骤3 若网络中某两节点间存在两条反向边，将其合并为一条单向边.

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

步骤5 基于式（10），可得所有可行流向量F对应的d－最小路集可行解X.

步骤6 比较所有的可行解，可行解X如不存在可行解Y满足Y≤X，则X就是一个d－最小路集.

2 算法分析

网络中各边的取值集合分别为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 网络中无双向边，跳过该步骤.

步骤3 网络中节点v2，v3间存在反向边e3，e4，将其合并为一条单向边e7，对应网络如图2所示.

图1 多状态网络Fig.1 Multistate network

图2 合并后的多状态网络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 两两比较，可得网络所有3－最小路集.与文献［8］结果对比，可知算法结果是正确的.

在桥型网络中，若取值集合均为｛0，3，5｝，d＝5.基于引理1，可得In f2（e1）＝0，i＝1，2，…，5.基于式（1）～（2）及式（11），可得

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

基于所有可行流向量F，按照式（10）得到对应的所有可行解X，如表1所示.通过比较可得该网络所有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 网络的所有可行流向量和可行解Tab.1 All feasible flow vectors and feasible solutions of the network

3 结束语

研究求解多状态网络d－最小路集的方法，改进后的算法不需要求取网络所有最小路集.通过引入可行流向量，并将网络中的双向边等效为单向边，使算法对网络中边的容量取值无特殊要求，且可用于含双向边的网络，适用性更强.通过引入边的容量下确界，并将网络中的反向边等效为单向边，减少求取d－最小路集可行解时需枚举的解数目，降低算法复杂度.

［1］ 李东魁.网络系统可靠度的BDD算法［J］.通信技术，2009，42（11）：149－150.

［2］ 骆剑锋，陈俞强.采用环加星型网络结构负载均衡集群技术的云平台设计［J］.华侨大学学报（自然科学版），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.

（责任编辑：钱筠 英文审校：吴逢铁）

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－），男，副教授，主要从事信息系统、网络体系结构的研究.E－mail：chu＿hy＠163.com.

国家自然科学基金资助项目（61300122）