论文部分内容阅读
最大流是指在网络中从源点至汇点可以传输的最大流量,不确定图的最大流问题是传统最大流问题在不确定图上的自然延伸,主要研究当边的容量存在不确定性时,和图中流量传递能力、传递方案及其可靠性相关的各种问题。鉴于不确定性是系统的固有特性,加之其对于构建可靠性网络、选取最优传输路径以及评估网络关键边等有着深远影响,因而这类问题在研究和应用领域得到了广泛的关注。本文重点研究的最大流可靠性和最大流可靠分布是其中具有代表性的两个问题,考虑到d流的应用更具普遍性,最大流仅是它的特例,故对两种情况予以合并研究。本文首先对最大流/d流可靠性问题进行了研究,最大流/d流可靠性问题是指,网络在源点与汇点之间能够传递最大流量/d流时的概率,反映了网络的流量传递能力,是评估网络性能重要指标。该问题属于NP-hard问题,随着网络规模增大,精确算法的时间开销难以接受,无法适用于大型网络,因而各种近似算法被相继提出,以蒙特卡洛算法最具代表性,然而该近似算法需要计算所有随机样本状态的最大流,导致计算代价相对较高。为此,本文提出基于双重过滤的d流可靠性算法,利用过滤准则避免对部分无效样本状态的最大流计算,提高算法的效率。随之又提出基于最大流快速计算的d流可靠性算法,针对随机样本状态图之间的结构包容性,利用对大量最大流计算中反复用到的路径的缓存和索引,加快了增广路径的查找过程,进一步降低了计算随机状态最大流的时间开销。针对边失效概率较为接近或相等的特定网络系统,又提出基于K重失效模型的d流可靠性算法,利用基于失效边的分层抽样方式代替直接随机抽样,在同样的精确度要求下该算法能够减少采样次数,进一步提升近似算法的性能。其次,对最可靠最大流/d流分布问题进行了研究。不确定图中源点与汇点之间传递最大流量/d流时通常会对应多个流分布,从这些流分布中选择可靠性最高的流分布作为流传输方案是最可靠最大流/d流分布问题研究的主要内容。为了避免现有算法ISDA-d对不存在更可靠d流分布的区间无意义的划分,提出基于区间过滤的空间划分算法SDBA_SF,提升空间划分算法的效率。考虑到在实际网络可能因故障导致拓扑结构发生变化,此时需要快速找到一个替代的流分布,静态环境下的算法因其复杂度过高而不再适用,为此,提出一种动态环境下可靠d流分布的快速求解方案,其主要思想是,预先计算原网络的Top-K最可靠d流分布及缓存所有的简单路径。若网络中的边发生损毁后原分布不可用,但损毁网络仍然可承载d流,则从已有的K-1个分布中快速获取一个仍然有效的d流分布;若不存在仍然有效的d流分布,则利用本文提出的简单路径替换算法对当前分布进行失效路径的替换,快速获取一个较为可靠的d流分布;若损毁网络不满足d流或依靠路径替换算法无法得到有效的d流分布,则利用基于路径替换的最可靠最大流/d流分布近似算法PRAA重新计算一个可靠性较高的最大流/d流分布。最后,本文通过一系列实验验证了本文所提出d流可靠性算法的精确性及其时间性能优势,并通过与现有的ISDA-d算法及SPCAA算法对比验证本文提出的SDBA_SF算法及PRAA算法的性能优势。