基于无效状态空间的多状态网络可靠性评估

doi:10.3969/j.issn.1000-3428.2012.23.023

计算机工程 ›› 2012, Vol. 38 ›› Issue (23): 95-100. doi: 10.3969/j.issn.1000-3428.2012.23.023

基于无效状态空间的多状态网络可靠性评估

李振¹，孙新利¹，姬国勋¹，刘好杰²，刘志勇³

(1. 第二炮兵工程学院一系，西安 710025；2. 第二炮兵士官学院一系，山东青州 262500；3. 第二炮兵装备研究院二所，北京 100085)

收稿日期:2011-10-08 出版日期:2012-12-05 发布日期:2012-12-03
作者简介:李振(1983－)，男，博士，主研方向：网络系统可靠性评估；孙新利，教授、博士生导师；姬国勋，讲师、博士；刘好杰，讲师、硕士；刘志勇，助理研究员、硕士
基金资助:
国家部委基金资助项目；第二炮兵工程学院创新性探索研究基金资助项目(XY2010JJB23)

Reliability Evaluation of Multistate Network Based on Invalid State Spaces

LI Zhen ¹, SUN Xin-li ¹, JI Guo-xun ¹, LIU Hao-jie², LIU Zhi-yong³

(1. The No.1 Department, Second Artillery Engineering University, Xi’an 710025, China; 2. The No.1 Department, Second Artillery Sergeant College, Qingzhou 262500, China; 3. The No.2 Institute, Second Artillery Equipment Academy, Beijing 100085, China)

Received:2011-10-08 Online:2012-12-05 Published:2012-12-03

摘要/Abstract

摘要： 在应用d-最小割(路)集计算多状态网络可靠度精确值算法中，运用容斥原理求解d-最小割(路)集较为复杂。为此，提出一种不需d-最小割(路)集直接计算多状态网络可靠度精确值的算法。该算法按一定规则分割状态空间，在此基础上生成无效状态空间，通过迭代计算直接获得可靠度精确值，同时通过定义边的容量下界及剩余网络。实例分析结果表明，运用该算法可减少计算量，并能精确求解d-最小割(路)集。

关键词: 网络可靠性, 多状态网络, 无效状态空间, 状态空间分割, 容量下届, 剩余网络

Abstract: According to the complexity of obtaining d-minimal cuts(paths) and inclusion-exclusion for calculating exact multistate networks reliability, a direct, exact algorithm for solving multistate networks reliability without requiring a priori d-minimal cuts(paths) is presented. The proposed algorithm generates the invalid state spaces based on dividing state spaces according to given rules, obtains the exact multistate networks reliability by iteration. Moreover, the algorithm defines edge capability lower boundary and residual network. Example analysis shows the algorithm can reduce calculation burden, avoid the solution complexity of d-minimal cuts(paths).

Key words: network reliability, multistate network, invalid state spaces, state spaces dividing, capability lower boundary, residual network

中图分类号:

TP393

李振, 孙新利, 姬国勋, 刘好杰, 刘志勇. 基于无效状态空间的多状态网络可靠性评估[J]. 计算机工程, 2012, 38(23): 95-100.

LI Zhen, SUN Xin-Li, JI Guo-Xun, LIU Hao-Jie, LIU Zhi-Yong. Reliability Evaluation of Multistate Network Based on Invalid State Spaces[J]. Computer Engineering, 2012, 38(23): 95-100.

http://www.ecice06.com/CN/Y2012/V38/I23/95

参考文献

[1] 罗鹏程, 金光, 周经伦, 等. 通信网可靠性研究综述[J]. 小型微型计算机系统, 2000, 21(10): 1073-1077.
[2] 李森, 王洁, 席博闻, 等. 结合网络可靠度不变缩减的蒙特卡洛仿真[J]. 计算机工程, 2011, 37(8): 61-63.
[3] Ramirez J E. Innovative Approaches in Multistate Network Reliability Modeling and Computation[D]. New Brunswick, USA: The State University of New Jersey, 2004.
[4] Jane C C, Laih Y W. A Dynamic Bounding Algorithm for Approximating Multi-state Two-terminal Reliability[J]. European Journal of Operational Research, 2010, 205(3): 625-637.
[5] Liu Wu, Liu Yi, Gu Xueqin. Monte-carlo Simulation for the Reliability Analysis of Multi-status Network System Based on Breadth First Search[C]//Proc. of the 2nd International Conference on Information and Computing Science. [S. 1.]: IEEE Press, 2009:
280-283.
[6] 王芳, 侯朝祯. 一个估计随机流网络可靠性的新方法[J]. 小型微型计算机系统, 2005, 26(5): 783-787.
[7] 刘玲艳, 吴晓平, 田树新. 基于粗糙集和Petri网的随机流网络可靠性评价方法[J]. 控制与决策, 2010, 25(8): 1273-1276.
[8] Zuo M J, Tian Z G, Huang H Z. An Efficient Method for Reliability Evaluation of Multistate Networks Given all Minimal Path Vectors[J]. IEEE Transactions on Reliability, 2007, 39(8): 811-877.
[9] Yan Zou, Qian Meng. Improving Efficiency of Solving d-MC Problem in Stochastic-flow Network[J]. Reliability Engineering and System Safety, 2007, 92(1): 30-39.
[10] Yeh W C. A Greedy Branch-and-bound Inclusion-exclusion Algorithm for Calculating the Exact Multi-state Network Reliability[J]. IEEE Transactions on Reliability, 2008, 57(1): 88-93.
[11] Yeh W C. A Fast Algorithm for Searching All Multi-state Minimal Cuts[J]. IEEE Transactions on Reliability, 2009, 57(4): 581-588.
[12] 孙艳蕊, 张祥德. 利用极小割计算随机流网络可靠度的一种算法[J]. 系统工程学报, 2010, 25(2): 284-288.
[13] Patra S, Misra R B. Reliability Evaluation of Flow Nlements[J]. Micro-electron Reliability, 1993, 33(14): 2161-2164.
[14] Doulliez P, Jamoulle E. Tansportation Networks with Random Arc Capacities[C]//Proc. of RAIRO’72. [S. 1.]: IEEE Press, 1972: 45- 60.
[15] Alexopoulos C. A Note on State-space Decomposition Methods for Analyzing Stochastic Flow Networks[J]. IEEE Transactions on Reliability, 1995, 44(2): 354-357.
[16] 张宪超, 陈国良, 万颖瑜. 网络最大流问题研究进展[J]. 计算机研究与发展, 2003, 40(9): 1281-1292.

选择文件类型/文献管理软件名称

选择包含的内容

基于无效状态空间的多状态网络可靠性评估

Reliability Evaluation of Multistate Network Based on Invalid State Spaces

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 6

编辑推荐

Metrics

本文评价

[1]	高航航, 王翔, 赵尚弘, 彭聪. 面向航空信息网络的控制器可靠性部署方法[J]. 计算机工程, 2020, 46(6): 221-229.
[2]	罗甜甜, 赵礼峰. 包含交叉顶点的最大流改进算法[J]. 计算机工程, 2020, 46(11): 48-52.
[3]	楼俐,范建华,胡永扬,李冉. 军用Ad Hoc网络分层体系架构及安全协议[J]. 计算机工程, 2019, 45(6): 188-192，198.
[4]	赵娟, 郭平, 邓宏钟, 吴俊, 谭跃进, 李建平. 基于非交叉路径的加权网络可靠性模型[J]. 计算机工程, 2011, 37(5): 33-34,37.
[5]	王吉喆, 赵蕴龙, 吴静. WMN中拜占庭容错网络结构及算法[J]. 计算机工程, 2011, 37(20): 83-86.
[6]	何明;裘杭萍;胡爱群;罗晨. 移动Ad Hoc网络的可靠性评价方法[J]. 计算机工程, 2009, 35(20): 126-127.

模态框（Modal）标题

选择文件类型/文献管理软件名称

选择包含的内容

基于无效状态空间的多状态网络可靠性评估

Reliability Evaluation of Multistate Network Based on Invalid State Spaces

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 6

编辑推荐

Metrics

本文评价