面向最短路的网络阻断问题研究

发布时间：2020-07-17 20:08

【摘要】：重要网络的攻击和防护问题通常可以用网络阻断模型来建模。经典的网络阻断问题是单一目标的,面向单层网络的,可能导致在达到阻断效果最大化时资源的消耗不是最优,突出表现在存在多组解的情况下,模型并不能自动给出资源消耗更少的解。现实世界中的网络系统越来越呈现出多层重叠(Overlay Networks)特性即多个网络系统相互耦合,之前的研究大多将网络分开来建模或者仅仅考虑网络之间很少的可认知的相互关系,如地理重叠关系;目前的网络模型都不能很好的描述存在相互依赖关系的多层网络。在本研究中,我们首先基于最短路阻断问题提出了一个新的阻断问题变种—MINIR,即在限制对手网络能力达到我方满意的阈值的情况下,阻断资源的消耗最少的问题。我们首先基于单层网络构建了基本模型;按照对偶和分解两种求解思路,分别提出了基于拉格朗日松弛的基本对偶算法和基于Benders分解的基本分解算法,并分别对两种算法分别进行了拓展。然后尝试研究了多层网络阻断问题的研究思路,对于层间关系我们选取了具有代表性的反馈关系,并给出了双层网络阈值最短路的阻断模型,然后进行了求解。最后我们利用构建的不同类型的测试网络对算法本身的性质和效率进行了测试,并在实际路网上对算法进行了模拟。对于大型的多层网络,即便是存在求解模型,也是极为复杂难以在有效的时间内求解和分析的。目前对于层间关系的描述方法大多数采用的是复杂网络的方法,不能给出军事行动中所需求的准确的、清晰的阻断方案。文章采用运筹学优化的方法清晰的表示出网络间相互依赖关系,在此基础上完成面向网络的最短路阻断问题建模和求解。
【学位授予单位】：国防科学技术大学
【学位级别】：硕士
【学位授予年份】：2014
【分类号】：E11
【图文】：

图 1.1 基础设施网络之间的相互依赖关系于公众利益的国家基础设施网络以外，在军事上也存在着军事基础设施；另一方面军事网络有着其本身所特有的军中心将军事行动所处的环境描述为多层网络系统[3]，如图 1图 1.2 作战环境的系统透视图

第 2 页图 1.2 作战环境的系统透视图是可以被选作行动目标的有形元素，可以包括人员，物资节点之间的物理上或者功能上的关系。连接确定了节点之形成系统完成功能。基于这种构架，军事行动的决策者制定的行动流程(COA)。之前的决策大多将不同网络层次的行动图 1.2 所提供的视图来看，这些行动对于整个系统的影响是

国防科学技术大学研究生院硕士学位论文系统的目标选取能力，对于作战资源的合理分配和高效利用有较强的应用价值。1.2 相关领域及国内外研究现状网络阻断问题是一种广为研究的网络问题，是作战对抗问题中的一个典型问题，基本含义对网络中的边进行攻击使其完全破坏或者增加其有效长度，降低其能力，阻断目标是如何最有效的利用有限的资源达成最大的作战效果，如最大化最短路（MXSP）[5]、最小化最大流（MIFI）[6]等问题。最初网络阻断的研究开始于军事领域，冷战时期兰德公司给出了苏联在东欧的铁路网如图 1.4 所示，分析家们研究了如何消耗更少的资源来限制苏联在东欧的铁路运输能力[7]。自二十世纪六七十年代以来，网络阻断的研究方兴未艾，各种各样的关于网络阻断问题的学术文献纷纷涌现。

【相似文献】

相关期刊论文 前2条

1 高虹霓,杨建军,曹泽阳;军用物资供应道路选择最优算法研究[J];系统工程与电子技术;2002年03期

2 ;[J];;年期

相关会议论文 前4条

1 袁二明;李莹;李彪;;基于交通拥堵预测的交通网络最短路问题的研究[A];“两型社会”建设与管理创新——第十五届中国管理科学学术年会论文集（上）[C];2013年

2 施欣;;随机运输网络最短路分布研究[A];复杂巨系统理论·方法·应用——中国系统工程学会第八届学术年会论文集[C];1994年

3 朱建明;沙丹;;时变网络中任意等待时间最短路问题的一个对偶算法(英文)[A];第四届中国智能计算大会论文集[C];2010年

4 牛宏睿;李平;史天运;;应急资源调度中最短路边权不确定性问题的建模与仿真[A];2009年中国智能自动化会议论文集（第七分册）[南京理工大学学报（增刊）][C];2009年

相关博士学位论文 前2条

1 吴六三;基于网络熵的网络可靠性研究[D];南京航空航天大学;2014年

2 高原;不确定图与不确定网络[D];清华大学;2013年

相关硕士学位论文 前9条

1 魏翔宇;面向最短路的网络阻断问题研究[D];国防科学技术大学;2014年

2 苏健;自动波方法求解TSP问题[D];西安电子科技大学;2004年

3 雷芬;随机网络中的动态最短路研究[D];中央民族大学;2009年

4 张振抻;网络最短路的解集结构及有关问题[D];郑州大学;2002年

5 张美玲;最短路问题的一个改进蚁群算法[D];兰州大学;2008年

6 陶娜娜;模糊随机多属性最短路问题[D];南京理工大学;2006年

7 台伟英;几类网络改进问题的算法及复杂性[D];中国计量学院;2012年

8 刘桂枝;带二次参数赋权多阶段网络的最短路问题研究[D];山西大学;2007年

9 张建勇;网络的K最短路分析与应用[D];山东科技大学;2006年

本文编号：2759885