您的位置:山东大学 -> 科技期刊社 -> 《山东大学学报(工学版)》

山东大学学报(工学版) ›› 2015, Vol. 45 ›› Issue (2): 27-32.doi: 10.6040/j.issn.1672-3961.1.2014.024

• 机器学习与数据挖掘 • 上一篇    下一篇

工程网络可靠性分析的网络简化方法

刘轩, 潘竹生, 钟发荣, 莫毓昌, 陈中育   

  1. 浙江师范大学数理与信息工程学院, 浙江 金华 321004
  • 收稿日期:2014-03-26 修回日期:2015-03-17 出版日期:2015-04-20 发布日期:2014-03-26
  • 作者简介:刘轩(1990-),男,湖北仙桃人,硕士研究生,主要研究方向为网络可信计算.E-mail:liuxuansure@gmail.com
  • 基金资助:
    国家自然科学基金资助项目(61272130);浙江省自然科学基金资助项目(Y1100689);浙江省教育厅一般科研资助项目(Y201328072,Y201328293);浙江省计算机软件与理论重中之重学科开放课题资助项目(ZSDZZZZXK24)

Network simplification method for reliability analysis of infrastructure networks

LIU Xuan, PAN Zhusheng, ZHONG Farong, MO Yuchang, CHEN Zhongyu   

  1. College of Mathematics, Physics and Information Engineering, Zhejiang Normal University, Jinhua 321004, Zhejiang, China
  • Received:2014-03-26 Revised:2015-03-17 Online:2015-04-20 Published:2014-03-26

摘要: 针对含关节点的工程网络可靠性分析,提出了1种冗余子网消除技术。这种简化技术利用关节点进行冗余子网识别和删除,因此网络可靠性可以在精简网络上快速计算。选取USAir97数据集的部分网络进行试验。试验结果表明,利用冗余子网消除技术,可大量降低网络可靠性的计算时间,从而提高网络可靠性分析算法的性能。

关键词: 冗余子网, 关节点, 网络简化, 网络可靠性, 工程网络

Abstract: A redundant subnetwork reducing technique was presented for the reliability analysis of infrastructure networks containning articulate nodes. This simplification technique could identify and delete the redundant subnetwork based on articulate nodes, and thus the network reliability could be calculated very quickly based on a reduced network. According to the experimental results on some selected networks from USAir97 benchmark, the redundant subnetwork reducing method could achieve a great reduction on computing time for reliability calculation. Thus the performance of infrastructure networks reliability analysis could be greatly enhanced.

Key words: network simplification, network reliability, infrastructure networks, redundant subnetwork, articulate nodes

中图分类号: 

  • TB114
[1] AKERS S B. Binary decision diagrams[J]. IEEE Transactions on Computers, 1978, 100(6):509-516.
[2] YEH F M, KUO S Y. OBDD-based network reliability calculation[J]. Electronics Letters, 1997, 33(9):759-760.
[3] KUO S Y, LU S K, YEH F M. Determining terminal-pair reliability based on edge expansion diagrams using OBDD[J]. IEEE Transactions on Reliability, 1999, 48(3):234-246.
[4] YEH F M, LU S K, KUO S Y. OBDD-based evaluation of k-terminal network reliability[J]. IEEE Transactions on Reliability, 2002, 51(4):443-451.
[5] HARDY G, LUCET C, LIMNIOS N. Computing all-terminal reliability of stochastic networks with binary decision diagrams[C]//Proceedings of 11th International Symposium on Applied Stochastic Models. Brest, France:IEEE, 2005:1468-1473.
[6] HARDY G, LUCET C, LIMNIOS N. K-terminal network reliability measures with binary decision diagrams[J]. IEEE Transactions on Reliability, 2007, 56(3): 506-515.
[7] 潘竹生, 莫毓昌. 冗余可修系统的可靠性分析[J]. 浙江大学学报:工学版,2013, 47(4):644-649. PAN Zhusheng, MO Yuchang. Reliability analysis of redundant and repairable systems[J]. Journal of Zhejiang University: Engineering Science, 2013, 47(4): 644-649.
[8] CHEN R, MO Y, PAN Z. Performance improvement of edge expansion technique for BDD-based network reliability analysis[J]. Journal of Computers, 2013, 8(9): 2190-2196.
[9] PAN Z, MO Y, XING L, et al. New insights into breadth-first search edge ordering of regular networks for terminal-pair reliability analysis[J]. Proceedings of the Institution of Mechanical Engineers, Part O: Journal of Risk and Reliability, 2014, 228(1):83-92.
[10] STROGATZ S H. Exploring complex networks[J]. Nature, 2001, 410(6825):268-276.
[11] ALBERT R, ALBERT I, NAKARADO G L. Structural vulnerability of the North American power grid[J]. Physical Review E, 2004, 69(2):101-107.
[12] KINNEY R, CRUCITTI P, ALBERT R, et al. Modeling cascading failures in the North American power grid[J]. The European Physical Journal B-Condensed Matter and Complex Systems, 2005, 46(1):101-107.
[13] YANG X H, CHEN G, SUN B, et al. Bus transport network model with ideal n-depth clique network topology[J]. Physica A: Statistical Mechanics and its Applications, 2011, 390(23):4660-4672.
[14] YANG X H, WANG B, CHEN S Y, et al. Epidemic dynamics behavior in some bus transport networks[J]. Physica A: Statistical Mechanics and its Applications, 2012, 391(3):917-924.
[15] JAVANBARG M B, TAKADA S. Seismic reliability assessment of water supply systems[C]//Proceedings of 10th International Conference on Structural Safety and Reliability. Osaka, Japan: IEEE, 2009:3455-3462.
[16] JAVANBARG M B, SCAWTHORN C, KIYONO J, et al. Reliability analysis of infrastructure and lifeline networks using OBDD[C]// Proceedings of 10th International Conference on Structural Safety and Reliability. Osaka, Janpan: IEEE, 2009:3463-3470.
[17] TARJAN R. Depth-first search and linear graph algorithms[J]. SIAM Journal on Computing, 1972, 1(2):146-160.
[1] 伍欢, 钟发荣, 莫毓昌, 潘竹生, 曾令国. 网络可靠性分析中BFS策略与POS策略的性能比较[J]. 山东大学学报(工学版), 2015, 45(2): 43-48.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!