多状态不交化路径可靠性分析的符号算法

Reliability Analysis Algorithm for Multi-State Two Separate Minimal Paths Based on Multi-Valued Decision Diagram

传统算法计算两条不交化路径传输的随机流网络可靠性,是通过获取系统最小容量向量的方法,需要存储整个网络的边以及移除冗余向量,运算非常复杂。因此提出基于MDD的多状态两条不交化路径可靠性分析算法MDD_2SMPs,利用MDD能够双向反映组件状态与系统状态关系的特点,通过定义MDD操作算子,在无需对路径进行流量分配的情况下获取路径容量,并在组合过程中引入约束剪枝策略对无效容量过滤,提高算法效率。针对路径失效问题,提出基于MDD的备用路径选择算法MDD_BMPs,通过将各路径转换为决策图多值变量形式,降低了计算备用路径可靠性的复杂性。实例结果表明,算法MDD_2SMPs比传统算法减少了计算可靠性的运算量,并能精确选择网络备用路径。

Traditional methods apply system minimum capacity vectors to calculate the reliability of stochastic-flow network with two separate minimal paths(2SMPs),which needs to store the arc of entire network and the process of removing redundant vectors is complex.In view of this,based on multi-valued decision diagram(MDD)for 2SMPs,we propose a reliability analysis algorithm,called MDD_2SMPs.The main idea of this algorithm is using MDD to reflect the relationship between components status and system status,by defining MDD operators,the path capacity can be obtained without the need for flow distribution.Besides,the constraint pruning strategy is introduced in the process of combination to filter many unnecessary combinations.Furthermore,aiming at the problem of path failure,all paths are converted into MDD variables by using the proposed algorithm MDD_BMPs,resulting a great reduction of the computational complexity.Example analysis shows that the proposed algorithm based on MDD has less calculation burden than traditional methods and can select the network backup paths accurately.