覆盖型网络的关键设施识别问题研究

论文摘要

随着经济与科技的快速发展，电信通讯网络、电力系统网络、交通运输网络等网络系统已经渗透到了人们生活、社会经济、国防安全的方方面面。网络中的一些非常重要的服务设施，一旦遭到破坏不能正常运行，对整个网络造成的影响是最具破坏性的，甚至会引起整个网络的级联故障，从而导致整个网络系统的大面积瘫痪，这些设施就被视为网络关键设施。通过识别网络关键设施，采取有针对性的防御措施，对保障基础设施安全及网络正常运行具有十分重要的意义。本文首先对国内外扩展覆盖问题以及设施中断问题相关研究进行了综述，主要介绍了包括集覆盖问题模型、最大覆盖问题等传统的覆盖问题；包括渐进覆盖问题模型、组合覆盖问题模型等扩展性覆盖问题；以及设施中断问题的研究。针对通讯类设施提供的服务渐进衰减和信号组合覆盖的特点，在渐进覆盖模型和组合覆盖模型的基础上，建立比传统的P-中位问题和最大覆盖问题更符合实际情况且更具有普遍意义的渐进覆盖和组合覆盖的中断问题模型，并分别设计了拉格朗日松弛算法和遗传算法，针对具体算例对模型进行了分析与求解。为检验算法的有效性，将遗传算法求得的结果与精确解进行比较，结果表明两个算法是有效的。渐进覆盖和组合覆盖中断问题模型的建立和求解，为准确识别网络关键基础设施提供理论和实际指导。最后对全文内容进行了总结，并对本文有待于深入研究的地方进行了展望。

论文目录

• 摘要
• Abstract
• 1 绪论
• 1.1 研究背景及意义
• 1.2 国内外研究概况
• 1.3 本文的研究思路
• 2 覆盖选址及设施中断问题模型介绍
• 2.1 基本覆盖设施选址问题回顾
• 2.2 扩展覆盖选址问题
• 2.3 网络设施中断问题的研究
• 2.4 本章小结
• 3 渐进覆盖设施中断问题
• 3.1 问题描述与模型建立
• 3.2 拉格朗日松弛算法设计
• 3.3 算法测试与分析
• 3.4 本章小结
• 4 组合覆盖设施中断问题
• 4.1 问题描述与模型建立
• 4.2 算法设计
• 4.3 算法测试与分析
• 4.4 本章小结
• 5 总结与展望
• 5.1 全文总结
• 5.2 研究展望
• 致谢
• 参考文献
• 附录 1 拉格朗日算法程序实现
• 附录 2 遗传算法程序