最快路径问题下的网络可靠度OBDD算法

发布时间：2017-10-08 15:07

本文关键词：最快路径问题下的网络可靠度OBDD算法

【摘要】：针对Theologou等给出的求解网络可靠度的factoring算法,分析该算法存在的冗余计算问题,给出DTN_OBDD算法。基于边排序策略的邻接终点矩阵方法,有效计算最小路集,将边失效特性引入网络可靠度分析中;基于最快路径求解公式,提高容量和时延约束下可行路径的筛选效率;构建所有可行路径的符号OBDD表示,遍历OBDD计算网络可靠度。以Python的igraph包生成的5组随机网络图为例,验证了DTN_OBDD算法的有效性,其中50个节点、201条边、状态空间为250的网络可靠度求解时间不超过80s。
【作者单位】：桂林电子科技大学计算机科学与工程学院;
【关键词】： 网络可靠度 有序二叉决策图 最快路径问题 容量时延
【基金】：国家自然科学基金项目(61363070) 广西高等学校高水平创新团队及卓越学者计划基金项目桂林电子科技大学创新团队基金项目
【分类号】：TP393.02
【正文快照】： 0引言网络可靠度是网络设计、验证和维护阶段的重要参考指标,网络中某些组件的故障可能会导致灾难性的后果,通过分析网络的可靠度,相关工作人员能设计出可靠的网络系统,减少网络的故障概率等,研究网络可靠度有着重大的实用价值和理论意义。Chen等[1]提出的最快路径问题(quicke

【相似文献】

中国期刊全文数据库前8条

1 孙艳蕊,张祥德,车文;具有不可靠结点网络可靠度的计算[J];东北大学学报;1999年05期

2 刘金林;董荣胜;万芷君;;权为费用的多状态网络可靠度算法[J];桂林电子科技大学学报;2013年06期

3 孙伟平;周敬利;余胜生;;流网络可靠度的计算算法综述[J];计算机科学;2003年10期

4 孙艳蕊,陈永川,张祥德;一个计算无圈有向网络可靠度的新算法[J];通信学报;2002年12期

5 李东魁;;3-状态设备网络系统可靠度计算的简化技术[J];福建电脑;2007年11期

6 肖宇峰;;基于同构子网判定的结点不可靠网络可靠度计算方法[J];科技导报;2014年16期

7 赵虎;卢文;;边失效概率不同情况下网络全终端可靠度的近似计算[J];电子设计工程;2011年05期

8 ;[J];;年期

中国重要会议论文全文数据库前1条

1 李东魁;;3—状态多桥设备网络系统可靠度计算的一个新算法[A];2006全国复杂网络学术会议论文集[C];2006年