基于最小路集和最小割集的网络可靠性符号算法研究

摘要

网络可靠性评估的一个关键任务是枚举出所有的最小路集或最小割集，从这些集合的不交化形式中可以计算得到可靠度。基于最小路集或最小割集的算法效率比传统的网络可靠度算法提高了很多，但是随着网络规模的增长，集合中的元素急剧增长，进而出现严重的组合爆炸问题，算法的效率仍需进一步提高。 有序二叉决策图(Ordered Binary Decision Diagrams，OBDD)适用于描述二状态变量，能够实现状态空间或者变量组合的隐式表示与搜索，极大的缓解了状态空间组合爆炸问题。本文在保留原有算法优势的基础上，将求解最小路集的算法进行扩展，使其适用于节点和边都不可靠的网络，另外也对求解最小割集的算法进行扩展，使其能同时计算无向图和有向图的三种可靠度指标，最后得到的最小路集和最小割集作为决策图的变量输入，通过OBDD高效的布尔操作进行不交化处理，消除冗余计算，降低算法的复杂度。本文研究的主要成果如下： (1)针对最快路径问题(Quickest Path Problem，QPP)下的网络，给出网络的形式化模型和可靠度定义，基于最小路集给出评估节点和边都失效网络可靠度的DTN_OBDD算法。通过对评估不可靠节点网络可靠度的Theologou算法进行分析，指出因子分解方法无法有效识别同构子网，产生大量冗余计算，这是影响Theologou算法计算效率的主要因素。针对这个问题，提出基于边排序策略的邻接终点矩阵方法，有效的计算出最小路集；其次，利用最快路径求解公式，提高容量和时延约束下可行路径的筛选效率；最后引入OBDD评估QPP下网络的可靠性。在五组不同规模的随机网络图基础上，与Theologou算法进行对比，验证了DTN_OBDD算法的有效性。 (2)针对Rajesh算法在评估网络可靠性过程中存在的运行效率和应用范围问题，给出统一割集框架下网络的形式化模型和可靠度定义，基于最小割集提出评估有向、无向图的二端、K端和全端可靠度的CSI_OBDD算法。Rajesh算法使用不交积和方法(Sum of Disjoint product，SDP)进行不交化处理，产生大量冗余项，严重影响算法效率。针对这一问题，利用简化的最小割集判定规则，有效的计算出最小割集，然后引入OBDD评估网络可靠性，结合OBDD的And和Or算子得到网络失效布尔函数，最后遍历OBDD计算网络可靠度。实例分析以及实验结果表明，CSI_OBDD算法能够精确计算有向图和无向图的三种网络可靠度指标，与Rajesh算法相比，CSI_OBDD算法具有较好的时间效率。