网络关键链路集算法的研究与应用

发布时间：2017-07-14 08:08

  本文关键词：网络关键链路集算法的研究与应用

  更多相关文章： 关键链路集 遗传算法 云计算 网络 鲁棒性

【摘要】：网络的生存性,表征了网络在遭受自然或者蓄意破坏后,能维持网络性能的能力大小,因此研究网络的生存性具有重要意义。研究网络的生存性的一个重要切入口就是关键链路集问题。简单说来,关键链路集是指蓄意攻击者在破坏能力有限的情况下,想要对相关网络实行最大程度的破坏,所选择攻击的一个有限的链路集合。“破坏”和“有限”存在多种不同的定义,本文主要研究了基于连通性点对测度和基于剩余交互流测度的关键链路集问题。本课题的最终目的是希望设计一类能够求解大规模网络的关键链路集的最优化算法,并将算法应用到网络的鲁棒性(生存性的一种)的评估中。文章的主要研究工作和创新点如下:1.从分析最小化连通性点对目标函数下的破坏模型的理论性质着手,获得了关键链路集问题的近似难度理论结果。该理论结果提供了关键链路集问题近似算法解的质量的一个不可能的界,能供作者本人及其他研究者参考来设计关键链路集问题可行的近似算法。2.提出了对中小规模网络有效的整数规划模型求解算法,而在更大规模的网络上提出了基于多轮次删除的线性规划近似算法。此线性规划算法能较快捷地求解出问题的近似解,且经过比较,算法比前人提出的算法更优,与精确解的近似程度更高。3.提出了一个能成批次优化带参数问题的遗传算法新框架,并基于此框架设计了关键链路集问题的遗传算法。经过研究发现,关键链路集问题可以划分到一类带参数的优化问题中。由于参数取不同值时的子问题之间存在着一定的联系,因此可以据此设计新型的遗传算法框架。所提出的遗传算法新框架,能为研究者解决别的带参数优化问题提供了一个有力工具。4.借助亚马逊所提供的云计算环境AWS,将算法应用到了网络的鲁棒性的评估测量中,并取得了良好的结果。大量实验数据表明,网络的鲁棒性能够通过网络的结构分布、流的分布以及两者的耦合情况进行快速估计。此处的工作使评估大规模网络的鲁棒性成为可能。
【关键词】：关键链路集 遗传算法 云计算 网络 鲁棒性
【学位授予单位】：国防科学技术大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O221;TP18
【目录】：

• 摘要9-10
• ABSTRACT10-12
• 符号使用说明12-13
• 第一章 绪论13-18
• 1.1 研究背景与研究意义13-14
• 1.2 研究内容14-17
• 1.2.1 研究问题14-15
• 1.2.2 研究思路15-16
• 1.2.3 研究成果16-17
• 1.3 论文结构介绍17-18
• 第二章 相关概念与相关研究工作18-24
• 2.1 相关概念18-20
• 2.1.1 计算复杂性18-19
• 2.1.2 数学规划19-20
• 2.1.3 元启发式算法20
• 2.2 关键链路集问题的相关研究工作20-22
• 2.3 网络鲁棒性的相关研究工作22-24
• 第三章 基于数学规划的近似算法24-36
• 3.1 关键链路集问题的理论难度24-27
• 3.2 关键链路集问题的整数规划模型27-30
• 3.3 基于线性规划的近似算法30-33
• 3.3.1 预处理阶段31-32
• 3.3.2 多轮次线性规划阶段32-33
• 3.3.3 局部优化阶段33
• 3.4 实验结果33-36
• 第四章 基于新遗传算法框架的近似算法36-53
• 4.1 传统遗传算法框架36
• 4.2 带参数的优化问题36-39
• 4.3 异构种群的遗传算法新框架39-45
• 4.3.1 新框架的伪代码及说明39-42
• 4.3.2 新框架的交叉算子的设计42-45
• 4.3.3 新框架的变异及其它算子的设计45
• 4.4 关键链路集问题的试验结果45-49
• 4.5 新框架下更多的实验和讨论49-53
• 4.5.1 p-中值问题49-50
• 4.5.2 最小顶点覆盖问题50-52
• 4.5.3 进一步讨论和比较52-53
• 第五章 关键链路集算法在网络鲁棒性评估中的应用53-67
• 5.1 网络鲁棒性模型的建立53-56
• 5.2 实验数据的大量生成56-57
• 5.3 云环境计算实验数据57-61
• 5.4 实验结果分析及评价61-67
• 第六章 总结与未来工作67-70
• 致谢70-72
• 参考文献72-76
• 作者在学期间取得的学术成果76

【相似文献】

中国期刊全文数据库 前10条

1 郭庆军;李慧民;赛云秀;;多项目关键链进度优化算法分析[J];工业工程与管理;2008年06期

2 张静文;胡信布;王茉琴;;关键链项目计划调度方法研究[J];科技管理研究;2008年03期

3 王明明;徐磊;贺雅丽;;科技研发项目关键链管理应用研究[J];科学学研究;2008年04期

4 林晶晶;周国华;;基于优先级的关键链多项目管理研究[J];科技管理研究;2009年08期

5 殷莎莎;;关键链技术研究动态评述[J];科技管理研究;2011年08期

6 赵道致,廖华;对关键链法的几个认识误区[J];工业工程;2005年02期

7 田文迪;崔南方;;关键链项目管理中关键链和非关键链的识别[J];工业工程与管理;2009年02期

8 李双辰;王艳春;;基于灰色关联的关键链缓冲设置方法研究[J];科技管理研究;2013年17期

9 张敏;陈荣秋;唐伟勤;;不确定收益下关键链项目缓冲前置分配模型[J];工业工程与管理;2009年04期

10 彭武良;金敏力;徐皓;;基于差分进化的关键链项目调度方法[J];系统管理学报;2013年06期

中国重要会议论文全文数据库 前4条

1 蒋国萍;陈英武;;基于关键链的项目进度问题研究[A];中国运筹学会第七届学术交流会论文集（中卷）[C];2004年

2 徐阳;;试用关键链理论组织预测市场需求[A];上海市烟草专卖局2007年度获奖论文集（经济管理类）[C];2007年

3 周正龙;董雄报;左园;;MIS开发项目进度管理的关键链识别研究[A];第八届（2013）中国管理学年会——管理与决策科学分会场论文集[C];2013年

4 万伟;蔡晨;;在两资源约束项目环境中的关键链管理[A];2003年中国管理科学学术会议论文集[C];2003年

中国重要报纸全文数据库 前1条

1 路长全;速度领先导致资源汇聚[N];中国证券报;2007年

中国博士学位论文全文数据库 前7条

1 林晶晶;考虑资源可替代性的关键链识别与缓冲设置方法研究[D];西南交通大学;2011年

2 郭方铭;基于粒子群优化和关键链的多项目计划管理问题研究[D];华中科技大学;2010年

3 别黎;关键链项目管理中缓冲估计与监控方法研究[D];华中科技大学;2012年

4 金敏力;基于关键链的项目优化调度问题研究[D];哈尔滨工业大学;2013年

5 田文迪;随机DTRTP环境下项目调度策略的比较研究[D];华中科技大学;2011年

6 刘英杰;大型水利工程费用/进度集成控制研究[D];天津大学;2012年

7 赵雁;时间缓冲设置与鲁棒性项目调度[D];华中科技大学;2014年

中国硕士学位论文全文数据库 前10条

1 唐艺轩;基于关键链的工程进度与成本集成管理研究[D];山东建筑大学;2015年

2 刘博;基于多项目优先级的关键链识别和缓冲区设置研究[D];河北工程大学;2015年

3 李力真;空间受限大型复杂项目的关键链管理研究[D];兰州大学;2015年

4 殷蕊;基于关键链技术的多资源多项目进度控制研究与应用[D];沈阳大学;2015年

5 任格叶;关键链的随机性及其应用研究[D];西安建筑科技大学;2015年

6 韩家宁;基于关键链的船舶机舱系泊计划进度研究[D];上海交通大学;2015年

7 李恩成;基于关键链技术的工程建筑项目进度管理方法研究[D];华北电力大学;2015年

8 崔爽;基于关键链技术资源约束下项目调度应用研究[D];华北电力大学;2015年

9 玉树伟;基于关键链法的超高层项目施工进度管理研究[D];广西大学;2015年

10 蒙唐媛怡;基于灰色关键链的项目进度管理研究[D];北京化工大学;2015年

，

本文编号：540276