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

• 网络与通信 • 上一篇    下一篇

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

李 振1,孙新利1,姬国勋1,刘好杰2,刘志勇3   

  1. (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 1, SUN Xin-li 1, JI Guo-xun 1, LIU Hao-jie 2, LIU Zhi-yong 3   

  1. (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

摘要: 在应用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

中图分类号: