计算机科学与技术学院
毕业设计(论文)
论文题目 指导教师 学生姓名 专 业 系 主 任 起止时间
复杂网络结构对信息路由鲁棒性的影响
职 称 学 号 班 级 院 长
讲师
2013年10月11日至2014年5月23日
2014年5月23日
i
南华大学计算机科学与技术学院毕业设计（论文）
目 录
摘要 ........................................................................ i Abstract ................................................................. iii 第一章 绪论 ................................................................ 1
1.1 课题的研究背景和意义 ...................................... 1 1.2 复杂网络上信息路由的鲁棒性概述 ............................ 2 1.3 课题的提出及主要工作 ...................................... 4 第二章 复杂网络的拓扑结构参数............................................ 6
2.1图的基本概念 .............................................. 6 2.2网络的聚类系数 ............................................ 7 2.3网络的度分布 .............................................. 9 2.4实际中的网络拓扑 ......................................... 11
2.4.1 Internet ...................................................... 11 2.4.2 www ........................................................... 12 2.4.3 其他网络阅读概述 .............................................. 13
第三章 复杂网络模型 ...................................................... 14
3.1 随机网络 ................................................. 14 3.2 小世界网络 ............................................... 17 3.3 无标度网络 ............................................... 19 第四章 三种复杂网络模型上的信息路由鲁棒性仿真分析 .................... 21
4.1 MATLAB软件简介 .......................................... 21 4.2基于最短路径路由的级联故障模型 ........................... 22 4.3 随机网络的的信息路由鲁棒性仿真 ........................... 24 4.4小世界网络的信息路由鲁棒性仿真 ........................... 26 4.5无标度网络的信息路由鲁棒性仿真 ........................... 28 4.6 三种网络模型上结果的对比分析 ............................. 30 第五章 总结 ............................................................... 31 参考文献 .................................................................. 32
谢 辞 ...................................................................... 34
复杂网络结构对信息路由鲁棒性的影响
摘要：现在社会越来越依赖于许多大规模网络，如Internet、交通网、物流网等，在这些网络上输送或路由着与人类密切相关的的大量信息流。一个网络的路由鲁棒性的强弱无疑是人们比较关心的问题。研究已表明，网络结构对其上的动力学行为有着重要影响，因此，越来越多的研究者基于典型的复杂网络模型对信息路由的鲁棒性展开研究。
本文首先概述了复杂网络上信息路由的鲁棒性研究现状。其次介绍了复杂网络的基本理论，如拓扑结构参数和典型的网络模型。然后，基于三种典型的复杂网络模型，包括WS小世界网络、BA无标度网络和ER随机网络，利用matlab仿真研究在最短路径路由策略下，网络由随机攻击和蓄意攻击而引发的级联故障行为，详细分析了网络结构对信息路由鲁棒性的影响。仿真结果表明，在随机攻击下，无标度网络的路由鲁棒性强于随机网络，在蓄意攻击下，则正好相反，而小世界网络的路由鲁棒性始终介于随机网络与无标度网络之间，且重连概率对小世界网络的路由鲁棒性产生了影响，本研究为当前网络拓扑和路由的优化和重新设计提供参考。
关键词：复杂网络;信息路由;鲁棒性;级联故障
i
南华大学计算机科学与技术学院毕业设计（论文）
Effect Of Complex Network Structure On Information Routing
Robustness
Abstract：Now the society has become more and more dependent on many large-scale networks, such as Internet, traffic network, logistics network, transportin the network or routing with a lot of information related to human flow. Anetwork routing robustness strength is concerned. Research has shown that，the network structure of the dynamic behavior of it is important,therefore, more and more researchers study the robustness of typical complex network models of information based routing.
This paper outlines the complex networks and complex system, as well as the present situation of information routing robustness. Secondly,introduces the basic theory of complex networks, such as topological structure parameters and the typical network model. Then, three kinds oftypical complex network model based on small world networks, including WS, BA scale-free network and ER network, matlab simulation study onshortest path routing strategy use, cascading failure behavior of network by random attack and intentional attack caused, the influence of network structure on information routing robustness analysis detailed. The simulation results show that, in the random attack, scale-free network routing robustness to random networks, in deliberate attacks, is just the opposite, and routing robustness of small world network always between random networks and scale-free networks, and rewiring probability will affact the small world network routing robustness. In this study, in order to optimize the network topology and routing and to provide the reference for the network design.
Key words：Complex networks; Message routing; robustness; cascading failur
ii
南华大学计算机科学与技术学院毕业设计（论文）
第一章 绪论
1.1 课题的研究背景和意义
现代社会越来越依赖很多的大规模网络，人们的生活和网络紧密相关，通过这些网络我们可以输送和人类有关的大量信息流。这些信息流从发生点经过网络里面边的承载输送和点的路由分配最终达到目的地，这是网络路由信息的一个完整过程。当然整个网络不可能是永久的安全可靠运行，在使用的过程中也会遇到故障，受到来自各方面的影响，例如自然灾害、人为的破坏等等。此时，网络的路由鲁棒性就会受到影响，整个网络里面的信息流会也许会因此而无法到达目的地，人们对网络路由鲁棒性强弱也非常的关系。整个网络科抽象为点和边，边代表在网络里面的传输介质，例如双绞线、光纤等，这些边承载了大量的信息流，为信息从一点到另一点路由提供条件；点就代表网络里面的路由转发设备，例如交换机、路由器等，这些点利用路由算法来选择合适的边进行信息流的分发。
当网络的边受到攻击时，这些边传输信息流的能力也许会下降降低传输能力，也许会失效失去输送信息流的能力。当这些故障发生在这些边上的时候，网络就会发生级联故障，由于一条边受到了影响，它输送信息流的能力和攻击前相比肯定是降低了，里面的信息流无法保证正确的传输到下一个点。因此，会对这些信息流进行重新路由，重新路由后，这些信息流到达了新的边，这些边的输送能力是固定的也许大也许小，当超过了自身的负载能力时就会发生和刚才失效的那些边一样，这样级联故障就进一步的扩大了。由局部到整体，也许会对整个网络造成无法衡量的影响，导致整个网络的失效瘫痪。网络的安全性和可靠性受到影响，依赖于网络的人类因此会深受其影响。
网络为我们的生活带来了极大的便利，为我们工作效率的提高也起到了很大帮助，与此同时也给我们带来了负面的影响，任何的东西总有双面性，我们追求完美的同时会尽量避开它不好的一面。在实际中就发生过类似的例子，美国的电网故障最先是由局部的故障引起的，随着时间的推移故障的进一步恶化，导致了整个电网的瘫痪，严重影响了国民的正常生活。还有因特网的故障，这些故障如
第 1 页，共 34页
复杂网络结构对信息路由鲁棒的影响设计
