动态网络中边关键度的快速评估算法研究

摘要

网络中关键边挖掘因其广泛的应用价值及理论研究意义，受到众多研究人员的关注，各种针对特定应用需求的边关键度评估方案不断被提出。为了更精准地评价不确定动态流网络环境中各边对网络承载能力和容量可靠性的影响程度，本文提出两种混合型关键边评估模型，即基于最大流和最大流可靠性的评估模型及基于d-flow和d-flow可靠性的评估模型，从边损毁后对网络流量及容量可靠的影响角度全面地衡量不同边的重要性。然而，大规模流网络中最大流的计算不是一个简单任务，且容量可靠性的计算更是达到了NP-hard难度，尤其当网络动态变化时，利用传统算法重新计算往往无法满足实时性需求。为此，本论文的研究重点在于如何在动态变化的网络环境中进行最大流和容量可靠性的快速计算，进而获得可以满足不用应用需求的两种边关键度评价方案。
　　在最大流算法中，下一条增广路径的查询过程消耗了算法的大部分时间，为此本文利用损毁网络及原网络的结构包含性，提出了基于简单路径缓存的最大流增量算法MFIA_PC，加快了增广路径的查询过程，提高了算法的效率。然而该算法效率与简单路径数量呈反比，为此，本文提出了增广路径选择树(ART)，用于索引所有有效的增广路径，避免算法遍历包含饱和边的无效路径，并在此基础上提出了基于增广路径选择树的最大流增量算法(MFIA_ART)，进一步加速了增广路径查询过程及最大流计算效率。
　　现有的容量可靠性算法中往往包含大量最大流的重复计算，造成了较大的时间开销，为此本文首先提出一种基于d-flow下界的容量可靠性快速算法DFP_AT，该算法首先获取一个d-flow分布下界X，然后根据X利用流量转移得到网络中所有的d-flow分布下界集L，最后根据L构建接受集树，计算出网络的容量可靠性，算法简单效率高。然后，针对网络动态性提出的实时性要求，本文基于DFP_AT算法提出了DFPIA_AT增量算法，通过数据缓存等方式进一步加速了容量可靠性的计算过程。
　　最后，通过实验检验了本文所提算法的正确性，并通过与经典算法的对比考察本文所提增量算法的性能，同时通过与其他关键边评估方法的对比分析基于最大流和流量可靠性的关键边评估方案的优越性及不足。

目录

声明

摘要

第一章 绪论

1．1 研究背景

1．1．1 网络关键环节的研究

1．1．2 相关工作和研究现状

1．2 研究内容

1．3 本文内容组织

第二章 边关键度的评估方案

2．1 边关键度模型定义

2．1．1 基于最大流和最大流可靠性的评估方案

2．1．2 基于d-flow和d-flow可靠性的评估方案

2．2 边关键度评估算法流程

2．2．1 基于最大流和最大流可靠性的评估算法流程

2．2．2 基于d-flow和a-flow可靠性的评估算法流程

2．3 边关键度算法分析

2．4 本章小结

第三章 最大流的增量计算

3．1 算法思想

3．2 MFIA_PC算法

3．3 MFIA_ART算法

3．3．1 ART树及其构建过程

3．3．2 MFIA_ART算法

3．4 本章小结

第四章 容量可靠性的增量计算

4．1 容量可靠性计算方法

4．1．1 d-flow分布下界

4．1．2 基于d-flow下界的容量可靠性计算方法

4．2 d-flow分布下界获取方法

4．3 基于d-flow下界的容量可靠性计算方法

4．3．1 接受集树(AT)

4．3．2 基于AT的的容量可靠性计算

4．4 容量可靠性的增量计算

4．4．1 增量求解思路

4．4．2 容量可靠性增量求解

4．5 本章小结

第五章 实验结果与分析

5．1 实验数据集

5．2 算法性能

5．2．1 最大流增量算法实验比较

5．2．2 容量可靠性算法实验比较

5．3 关键边评估

5．4 本章小结

第六章 总结与展望

致谢

参考文献