[1]褚洪彦.采用节点流守恒求取多状态网络d-最小路集的改进算法[J].华侨大学学报(自然科学版),2016,37(4):511-514.[doi:10.11830/ISSN.1000-5013.201604024]
　CHU Hongyan.Improved Algorithm for d-Minimal Path Set of Multistate Network Using Node Flow Conservation[J].Journal of Huaqiao University(Natural Science),2016,37(4):511-514.[doi:10.11830/ISSN.1000-5013.201604024]
点击复制

采用节点流守恒求取多状态网络d-最小路集的改进算法()
分享到：

《华侨大学学报（自然科学版）》[ISSN:1000-5013/CN:35-1079/N]

卷:
第37卷
期数:
2016年第4期
页码:
511-514
栏目:
出版日期:
2016-07-04

文章信息/Info

Title:
Improved Algorithm for d-Minimal Path Set of Multistate Network Using Node Flow Conservation
文章编号:
1000-5013(2016)04-0511-04
作者:
褚洪彦
南京信息职业技术学院 计算机与软件学院, 江苏 南京 210023
Author(s):
CHU Hongyan
School of Computer and Software, Nanjing College of Infomation Technology, Nanjing 210023, China
关键词:
网络可靠度;  多状态网络;  最小路集;  可行流向量
Keywords:
network reliability;  multistate network;  minimal path set;  feasible flow vector
分类号:
O213.2
DOI:
10.11830/ISSN.1000-5013.201604024
文献标志码:
A
摘要:
针对多状态网络可靠度的计算问题,给出一种求解多状态网络d-最小路集的改进算法.引入可行流向量,并将网络中的双向边等效为单向边,使算法对网络中边的容量取值无特殊要求,且可用于含双向边的网络,适用性更强.通过引入边的容量下确界,并将网络中的反向边等效为单向边,减少求取d-最小路集可行解时需枚举的解数目,降低算法复杂度.以多状态网络为例,进行分析验证.结果表明:该算法可以准确得到多状态网络所有d-最小路集.
Abstract:
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.

参考文献/References:

[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.

备注/Memo

备注/Memo:
收稿日期: 2016-05-05
通信作者: 褚洪彦(1968-),男,副教授,主要从事信息系统、网络体系结构的研究.E-mail:chu_hy@163.com.
基金项目: 国家自然科学基金资助项目(61300122)
更新日期/Last Update: 2016-07-20