基于复杂网络的因特网抗毁性分析毕业设计(论文)(编辑修改稿)

基于复杂网络的因特网抗毁性分析毕业设计(论文)(编辑修改稿)内容摘要：

中在规则网络。 然而随着探索的不断深入，构造较为随意的随机图开始受到科学家的喜爱，这种网络图模型能够 更为简洁明了地实现复杂网络的模拟。 在那个年代，很多研究者都提出了自己独有的模型，而这些模型中最为突出的要数 Erods 和 Renyi 所建立的随机图模型，后人简称为 ER 模型。 根据随机图模型（ ER 模型），以 N 个节点开始以概率连接各节点，创建出约 2/)1( NpN 个随机分布的链路。 网络中度分布的均值为 )1(  Npk ,在平均度 k 固定的情形下，当 N 很大时， )1/(  Nkp 就会变得很小。 所以也将 ER 随机图称作泊松随机图。 如下图所示：黑色圆点表明的是 15k 时的度分布，而实线部分则表示的是与其相似的泊松分布。 同时该图还表明大多数的节点有着近似相同数目的链路。 !! )()( kkekpNekP kkkpN   （泊松分布函数） () 图 ER 随机图的度分布与泊松分布的比较 南华大学计算机科学与技术学院毕业设计（论文） 第 8 页 共 35 页 随机图的连通性有两种极端情况： 0p 时对应 N 个孤立的节点； 1p 时对应全耦合网络。 直观上看来，连边概率 p 增加则所生成的随机图的变数也会随着增加，网络的连通性也就越好。 下图给出了不同的 p 值下所生成的随机图的例子。 粗略地算一下，若 1000N ，则每次生成的 ER 随机图会有边数大约为 pNpNM 50 002/)1(  () 图 不同连接概率的随机图实例 (2)小世界网络 小世界模型 (WS)是由 Watts 和 Strogatz(WS)建立的，描述了一个局部有序的系统是如何转化成为随机网络的。 小世界模型是从包含 N 个节点的一维网络开始的，网络中的节点和距离它最近 和以及次近的邻点连在一起，每个边再根据概率 p 从新进行连接起来。 并且以节点和节点间没有重复的边并且不会自行成环为约束条件。 WS 模型由一个规则网络经过一些演变而成的，经过逐步地一边接一边的重新连接，直到演化为随机网络。 如下图： 南华大学计算机科学与技术学院毕业设计（论文） 第 9 页 共 35 页 当 0p 时，对应的是规则网络图。 两节点的平均距离 L 与节点数目 N 之间是成线性相关的，当 N 增加后 L 也跟着变大，同时集群系数也会跟着变大； 当 1p 时，对应的是随机图，此时 L 与 N 成对数关系，随着 L 的增加而以对数的程度变大，而由于 N 的不断增加，集群系数也会逐渐增大。 当 p 在（ 0,1）之间时，系统表现为小世界特征，此时， L 的值近似和随机网络的相同，网络表现出高度集群性质。 0p 1p随 机 性 增 加规 则 小 世 界 随 机 图 WS 模型中边的随机重连过程 严格来说，即使是在 1p 时 WS 模型与包含同样节点和边数的 ER 模型 还是会有区别的：在 WS 模型中每个节点的度至少是 2/k ,但是在 ER 随机图中，并没有对单个节点的度的最小值进行任何限制。 如果要使得 WS 模型在 1p 时等同于 ER随机图，则要在 WS 的生成算法中完全随机地对选取的每一条边的两个节点进行重新配置。 下图为给定参数 101000  kN ， 的情况下， )(pC 和 )(pL 的变化情况。 图中将 )(pC 和 )(pL 做了归一化处理，即 )0(/)( CpC 和 )0(/)( LpL ，这样就可以使两个变量在 0p 时的最大值都为 1。 其中： )(pC 表示平均聚集系数， )(pL 表示平均最短路径， p 表示重连概率。 南华大学计算机科学与技术学院毕业设计（论文） 第 10 页 共 35 页 1)0(/)( LpL)0(/)( CpCP 图 WS 小世界模型的 )(pC 和 )(pL 随 p 的变化关系 (3)无标度网络 上个世纪九十年代以来，科学技术取得了巨大进步，这就使得研究大规模的实际网络成为一种可能，人们可以借助计算机对真实网络进行模拟。 在先进技术的支持下，人们逐渐意识到真正存在于我们身边的网络多数都存在另外的一些统计特性而并非是彻底随机的并且在构造的过程中它们会遵循某种规律并且具有随机网络模型所不具有的网络动力学特性，而在这些个迥异特性中当属小世界与幂律分布最为独特。 无标度网络模型是由 Barabasi 与 Albert （ BA） 联合建立的，实际网络中的无标度特征来自 2 种普遍的形成机制：第一，由于添加新节点而 使得网络不断扩大；第二，新节点会优先与度最大的节点连接。 受到这两点的启发 BA 模型得到了建立，这网络研究史上最先阐明了节点度分布符合幂律函数的模型，因而意义非凡。 实际网络中的许多信息交换网、社交网、生物网络都遵循幂律分布特性。 南华大学计算机科学与技术学院毕业设计（论文） 第 11 页 共 35 页 第三章 复杂网络抗毁性 网络抗毁性的定义 虽然抗毁性应用极为广泛，但其定义大致可从两个角度进行表述：定性和定量。 这也是人们在研究一个新的特性时常用的定义方法，这样可以让后来者对其有更加清晰的认识。 下面从这两个角度来说明一下什么是抗毁性。 (1)定性的定义 定义 1： Ellision 等人针对信息系统的抗毁性提出：网络的抗毁性是在网络遭受意外事故、故障或者攻击时，系统能够及时提供完成其关键任务的能力。 定义 2。 Louca 等人针对通信网络提出：网络的抗毁性包括两方面内容 : 1)在出现故障情况下，系统还能够维持或恢复到被用户所接受的性能的能力。 2)组织或转移潜在服务故障的能力。 上述定义给出了抗毁性的定性描述，但是并未给出精确地描述，缺乏相应的具体性能指标，难以准确的判定系统的抗毁性。 因此，针对这种情况，又有了定量的抗毁性定义。 (2)定量的定义 定义 3： Knight 和 Sullivan 针对信息系统提出 :如果一个系统满足抗毁性规范，则认为这个系统是抗毁的。 这个抗毁性规范是一个四元 M}P,R,{E,。 1) E 是抗毁系统运行环境的描述。 2) R 是网络提供的、具有可接受服务质量的指标集。 3) P 是遍布指标集 R 的概率分布，并且其概率之和是 1。 4) M 是一个有限状态机，用四元组  TVSS , 0 来表示。 在 M 中， S 表示有限状态的集合； 0S 表示初始状态或者优选状态； V 表示用户值的集合； T 表示转移状态矩阵。 该四元组明确的定义了网络什么时候以及如何从正在提供的一种服务状态转移到另外一种服务状态。 在该定义中，抗毁性可以视为系统在某一环境中可以提供的具体服务的概率。 定义 4:对于分布式网络，抗毁性定义必须包括一下几个方面： 南华大学计算机科学与技术学院毕业设计（论文） 第 12 页 共 35 页 1)系统定位：对于不同的网络系统，抗毁性是不同的。 如果抗毁性定义有变化，那么必须要说明。 例如，在军事网络中，抗毁性定义为：在遭受敌人攻击时，能够保持军事武器或设备或其他 军事力量性能的能力。 而在通信网络系统中，抗毁性定义为：网络容错并持续提供服务的能力。 另外，系统是有界还是无界的也要说明。 2)威胁： 对网络的威胁可能会影响网络（系统）在规定时间内继续为它的用户提供服务。 网络的威胁可以归为偶然的、故意或恶意的和灾害的这三类。 偶然因素包括软件的错误，硬件错误，以及人为失误。 故意或恶意的威胁包括故意毁坏，黑客入侵，以及恐怖袭击。 灾害威胁指的是由于自然灾害（洪水，台风，飓风，雷电，地震，海啸等）、战争行为和停电事故的发生，造成了物理设备的损坏，致使网络没有办法再给用户提供服务。 3)适应性：在系统受到威胁时，系统应该有适应能力和继续提供服务的能力。 例如，电力系统应有能力适应短期内局部过载等突发状况，防止大面积停电事故的发生。 4)服务的持续性：服务对用户应该是可用的，即使在破坏发生时，网络的性 能不应该退化。 5)时效性：服务应该在系统要求的时间内让用户接收到。 网络抗毁性分析 抗毁性度量指标 (1)鲁棒性度量 连通性是网络的重要性能指标之一。 网络鲁棒性用来衡量网络遭受攻击时剩余节点之间仍能保持连通的能力。 由此，网络鲁棒性可定义为移除任意节点后，网络中仍连通的节点对 与网络总节点对的比值。 用 39。 G 来表示受到节点删除后的网络，网络的鲁棒性  有如下表示：  ijGji ijln ,)1(n1 () 南华大学计算机科学与技术学院毕业设计（论文） 第 13 页 共 35 页 ijl 为连通系数，若 i 和 j 之间连通，当节点 iv 和 jv 之间连通时， 1l ij ，否则 ijl =0。 网络鲁棒性  描述了网络在遭受外界干扰或破坏时的连通性，反映了网络结构本身对于攻击的抵御能力，克服了最大连通子图的相对大小不能反映网络受到攻击后子网络的连通情况的缺点。 均存在某种程度上的损坏几率，所以要让鲁棒性高至峰值，纵然网络能够做到全连通也是不可能的。 (2)网络效率度量 有效性度量说明的是网络在某时段内能够正常运转并发挥功效的程度，可以刻画出网络传递 信息的效率。 计算全网效率的方法如下： ijGijGiE dn1)1(n 1  () 上式反映出：信息传递的路程越长，传输距离 ijd 越大传播过程所消耗的时间越多，网络的传输效率就越低。 反之，网络传输效率越高。 实证分析与仿真分析 复杂网络抗毁性研究最早开始于 20xx 年 Albert 等的工作，他们开始关注拓扑结构对复杂网络抗毁性的影响。 他们分别把随机网络（ ER 模型）和无标度网络（ BA 模型）至于两种类型的打击策略之下：一是随机失效，在这种打击中，随机移除网络中的节点，这与网络中的随机故障相对应；二是选择性攻击，按照节点连接度从大到小的顺序移除节点，即仅仅拿掉网络中的活动中心。 Albert 等分别研究了不同网络面对不同打击条件下极大连通片尺寸与网络规模之比 S 、极大联通片平均最短路径 l 与节点移除比例 f 的关系，研究结果如下图 所示。 南华大学计算机科学与技术学院毕业设计（论文） 第 14 页 共 35 页 图 不同网络面对不同打击条件下 S 和 l 与 f 的关系 从上图可以看出， 在第一种打击手段下，无标度网络明显有着更好的抗毁性。 而在第二种方式下，相比于随机网络而言，无标度网络会更加迅速地走向了崩溃，并且一旦删除那些关键节点就会致使网络进入瘫痪状态。 对比之下会发现此时的它异常脆弱。 后来人们在 WWW 和 Inter 上所做的实证分析证实了艾伯特的这一论断。 之后的布罗德等人又通过对 的实证研究得出在目标性的打击下，网络会表现出比平时更为强大的抗毁性。 由于前人的研究使得后来人愈来愈对这方面感兴趣，吸引着他们不断对其进行学习和探讨，并且所得结论与 艾伯特的大体相同。 而仿真研究方面，最为权威的当是以霍姆为首的科研工作者所做的。 他在前人的基础上又进行了移除边的实验，在攻击方法上又新增了这对介数的打击，也取得了可喜的成就，为该领域的研究做出了不小的贡献。 此后，很多学者对其他现实世界中的复杂网络抗毁性问题进行了研究，总体结构几乎均与 Albert 等的结果一致，大多数为了对于随机的节点删除都表现出抗毁性，而面对以最大度节点为目标的选择性攻击就相当脆弱。 例如 Jeong 等的蛋白质网络研究， Dunne 等的食物链网络研究， Newman 等的电子邮件网络研究， Magoni等的 Inter， Samant 等的 P2P 网络研究。 有关攻击策略对复杂网络抗毁性影响的仿真研究中，比较全面的要数 Holme等的研究工作。 他们将攻击策略分为节点攻击与边攻击两种方式。 每种攻击又包括四种不同的策略： ID 移除策略（对初始网络按节点或边的度大小顺序来移除节点南华大学计算机科学与技术学院毕业设计（论文） 第 15 页 共 35 页 或边）、 IB 移除策略 (对初始网络按照节点或边的介数大小顺序来移除节点或边 )、 RD 移除策略（每次移除的节点或边是当前网络中节点或边的度最大的节点）和 RB 移除策略（每次移除的节点或边是当前网络中节点或边介数最大的节点）。 ER 模型对节点的基于度的攻 击比基于介数的攻击效果好，使用重新计算的信息比基于原始信息的危害性更强；而对边的攻击 RB 远比其他策略更具破坏性。 无尺度网络对节点移除比 ER 模型更敏感，在攻击初期四种策略的差异性不明显，随着移除的继续进行，攻击对网络的破坏程度按以下顺序排列： RBRDIDIB；而且对边的攻击情况同节点攻击相似。