论文部分内容阅读
网络可靠性分析是网络可靠性研究的基础。目前网络的可靠性分析往往高估了网络的可靠性。约束条件下的网络可靠性分析受计算复杂性的制约,最典型的就是处理较大规模网络时产生的状态组合爆炸问题。决策图理论可以缓减或者从一定程度上避免组合爆炸问题,广泛应用于组合优化、硬件验证、模型检验等领域。代数决策图(Algebraic Decision Diagram, ADD)和多值决策图(Multi-valued Decision Diagram MDD)均是二叉决策图(Binary Decision Diagram, BDD)的扩展形式,能够实现状态空间或者变量组合的隐式表示与搜索,同时它们也具有不交化、高效存储和易操作等特性。本文基于决策图理论,对两状态和多状态加权概率网络可靠性进行了研究。主要成果如下: (1)针对两状态加权概率网络,给出容量和时延约束下可靠性分析的符号ADD算法。本文在基本的网络模型基础上,结合加权概率网络(WPN)的定义,分别构建WPN的两状态和多状态的形式化模型;然后给出容量和时延约束下,两状态加权概率网络可靠性的符号ADD算法;通过与Yeh改进的SDP算法进行实验对比,结果表明符号ADD算法正确有效而且具有更高的执行效率。 (2)针对多状态加权概率网络,给出费用约束下多状态加权概率网络可靠性分析的MDD_Based_Cost算法。引入网络部件的降级状态,给出费用约束下多状态加权概率网络可靠性的定义。从降低多值决策图的复杂度,避免最小路集求解的思路出发,对多值决策图进行结点分类,给出费用约束下,可靠性分析的MDD_Based_Cost算法。最后,将MDD_Based_Cost算法与Roberta算法进行实验对比。实验结果表明, MDD_Based_Cost算法的运行效率优于Roberta算法。 (3)针对多状态加权概率网络,给出容量约束下可靠性分析的MDD_Based_Flow算法。通过分析现有容量约束下多状态网络可靠性分析的Lin算法的缺陷,给出可行路径的定义、可行路径的筛选定理以及适应算法要求的MDD自定义操作,在MDD_Based_Cost算法的基础上,给出容量约束下多状态概率加权网络可靠性的MDD_Based_Flow算法。最后,通过与Lin算法的实验对比,验证了算法的有效性。