论文部分内容阅读
近年来，多状态网络的可靠性研究成为可靠性研究领域的热点。本文引入具有隐式表达、易操作等特点的决策图技术，对更接近现实的多状态流网络可靠性进行了研究。主要研究内容及研究成果如下： (1)给出了基于现实假设下多状态流网络的形式化模型，该模型适用于节点可靠，边上存在随机独立分布的多个容量状态的多状态流网络的可靠性分析。在此模型上提出了基于有序二叉决策图（OBDD）的MFN_OBDD算法来计算多状态流网络可靠度。算法从网络的可满足界值流向量 flow(d)出发，引入决策图技术构造能够表示满足需求的所有状态向量的决策图；然后通过遍历决策图得到网络的可靠度。在构造决策图的过程中，给出了生成并简化状态决策图、边决策图、流决策图、目标决策图的操作函数，压缩了状态空间，有效地降低了决策图的操作复杂性。理论上证明了算法的正确性，分析了算法复杂度。实验结果及实验分析表明：与J&L的空间分解算法相比，MFN_OBDD算法能够有效地降低空间复杂度和循环次数。 (2)在MFN_OBDD算法基础上，提出了基于多值决策图（MDD）的MFN_MDD算法。相比 MFN_OBDD算法，减少了变量数，降低了算法复杂度。实验表明：MFN_MDD算法中得到的 MDD的层次和节点数远少于 MFN_OBDD算法中得到的OBDD的层次和节点数；MFN_MDD算法比MFN_OBDD算法高效。 (3)提出了基于最小割集和代数决策图（ADD）的MFN_MCADD算法来评估多状态流网络可靠性。算法从网络的最小割集出发，首先构造在需求d约束下每个最小割集的决策图，为此，创建了生成边决策图、割决策图的操作函数。然后利用最大流最小割定理合并所有割决策图，生成了能够表示可满足状态空间的目标决策图。在此基础上，提出了基于多值决策图的MFN_MCMDD算法。理论上证明了算法的正确性并分析了算法复杂度。通过实例分析验证了MFN_MCADD算法和MFN_MCMDD算法的正确性和可行性，且MFN_MCMDD算法中得到的MDD的层次和节点数远少于MFN_MCADD算法中得到的ADD的层次和节点数，进一步验证了MDD在处理多状态系统时的优势。