（计算机软件与理论专业论文）as的地理分布对internet网络稳定性的影响.pdf

大连理工大学硕十学位论文 摘要 近年来的研究表明，i n t e r a c ta s 层网络是具有无尺度和高聚类等宏观特性的网络。 通过研究这些宏观特性的产生机制，人们可以设计和开发更高效的路由协议、更有效地 制定i n t e m e t 流量控制策略、更好地管理a s 间的组织关系。因此，a s 网络特性的产生 机制得到了广泛的研究，成为网络科学领域研究的热点问题。 实际上，a s 网络的宏观特性受到诸如经济、地理、政治、技术等众多客观因素的 影响。定性和定量的分析各因素对宏观特性的影响机制，并根据这些机制建立a s 网络 拓扑模型是当前研究a s 网络的主要方法。 本文重点尝试去分析地理因素对a s 网络的哪些宏观特性产生影响、影响的形式以及 影响的程度，进而总结出地理因素与a s 网络稳定性的联系。与以往关注a s 网络宏观特 性产生机制的研究不同，本文认为a s 网络不是一个孤立的网络系统，而是一个处在开放 环境中的、和环境中其它多种网络系统相互作用的网络。各种客观因素对a s 网络拓扑宏 观特性的影响是网络系统间相互作用的重要体现。因此，本文首次提出了能够真实刻画 a s 层网络地理分布的超图结构，进而提出了a s 网络和地理超图之间的相互作用机制： 地理超图限定了a s 网络中a s 节点建立连接可选的a s 集合；a s 网络中a s 节点的度值决 定了地理超图中边所包含的节点个数。 基于以上机制，本文建立了a s 网络和地理超图双层拓扑模型，并分别模拟了a s 对 地理区域的随机扩张以及a s 对地理区域的近邻扩张两种情况。实验结果表明：在a s 采 取近邻扩张的前提下，实际a s 网络的平均集聚系数明显受到地理距离因素的影响。具体 表现为：随着建立连接的地理距离减小，网络平均集聚系数呈现出衰减的趋势。最后， 本文讨论了平均集聚系数与网络坚韧度的关系，得出了建立连接的地理距离越小，网络 坚韧度越小，网络稳定性越差的结论。 关键词：a s 网络；地理超图；a s 区域扩张；网络坚韧度；网络稳定性 大连理工人学硕士学位论文 t h ee f f e c to fa s sg e o g r a p h i cl o c a t i o n so ni n t e r n e t ss t a b i l i t y a b s t r a c t r e c e n ts t u d i e ss h o wt h a ti n t e r n e ta s - l e v e li san e t w o r kw i t hm a n ym a c r o s c o p i c a l p r o p e r t i e ss u c ha ss c a l e - f r e ea n dh i g hc l u s t e r i n g b ys t u d y i n gt h em e c h a n i s m st h a tp r o d u c e t h e s em a c r o s c o p i c a lp r o p e r t i e s ，s c i e n t i s t sc o u l dd e s i g na n dd e v e l o pe f f i c i e n tr o u t i n gp r o t o c o l s ， m o d e li n t e r n e tt r a f f i ca n dm a n a g et h eo r g a n i z a t i o nr e l a t i o n s h i pb e t w e e na s e s t h u s ，t h e m e c h a n i s mt h a tp r o d u c et h e s ep r o p e r t i e so fa sn e t w o r kh a v eb e e ns t u d i e dw i d e l y ，w h i c hh a s b e c o m eap o p u l a rp r o b l e mi nn e t w o r ks c i e n c e i nf a c t ，t h ep r o p e r t i e so fa sn e t w o r ka r ei n f l u e n c e db ye c o n o m y ，g e o g r a p h y ，p o l i t i c sa n d t e c h n o l o g y a n a l y z i n gt h e s em e c h a n i s m sa n dm o d e l i n gt h ea sn e t w o r ki st h em a i nm e t h o dt o s t u d yt h ea sn e t w o r k t h i sp a p e rs e e k st ou n d e r s t a n dt h ee f f e c to fg e o g r a p h i cf a c t o ro nt h ei n t e r n e ta s l e v e l n e t w o r k f u r t h e r m o r e ，ar e l a t i o n s h i pb e t w e e ng e o g r a p h i cf a c t o ra n dn e t w o r ks t a b i l i t yi s s h o w n a sn e t w o r ki sb e l i e v e dn o ta ni s o l a t e ds y s t e m ，b u ti si na no p e n i n ge n v i r o n m e n t w h e r em a n ys y s t e m si n t e r a c t t o g e t h e r ah y p e r g r a p hs t r u c t u r et h a t c a nd e s c r i b et h e g e o g r a p h i cl o c a t i o n so fi n t e r n e tr e s o u r c e si sd e f i n e df o rt h ef i r s tt i m e t h em e c h a n i s m st h a t r e f l e c tt h ei n t e r a c t i o n sb e t w e e nt h ea sn e t w o r ka n dt h eh y p e r g r a p hs t r u c t u r eo nt h e g e o g r a p h i cl o c a t i o n sa r ep r e s e n t e d ，t o o t h i sp a p e rm o d e l st h ei n t e r n e ta s l e v e lb ys i m u l a t i n gt h ei n t e r a c t i o nb e t w e e nt h ea c t u a l a sn e t w o r ka n dt h eg e o g r a p h i ch y p e r g r a p h t h ee f f e c to fd i s t a n c eo nt h ee v o l v e m e n to fa s t o p o l o g yi sm e a s u r e di nt w od i f f e r e n tc o n d i t i o n s ，o n ei st h a tt h ea se x p a n d sr a n d o m l yo nt h e z o n e s ；t h eo t h e ri st h a tt h ea ss e l e c t si t sn e i g h b o r i n gz o n e st oe x p a n d t h er e s u l t ss h o wt h a ti f t h ea ss e l e c t si t sn e i g h b o r i n gz o n e st oe x p a n da l lt h et i m e ，t h e nt h ea v e r a g ec l u s t e r i n g c o e f f i c i e n to ft h ea sn e t w o r ki si n f l u e n c e db yt h ed i s t a n c eo b v i o u s l y i tp r e s e n t st h a tt h e a v e r a g ec l u s t e r i n gc o e f f i c i e n td e c r e a s e sw i t ht h ed e c r e a s eo ft h ed i s t a n c e f i n a l l y ，t h i sp a p e r d i s c u s s e st h er e l a t i o n s h i pb e t w e e nt h ea v e r a g ec l u s t e r i n gc o e f f i c i e n ta n dt h en e t w o r k t o u g h n e s s ，o u rs t u d yi n d i c a t e st h a tt h en e t w o r kt o u g h n e s sd e c a y sw i t ht h ed e c r e a s eo ft h e d i s t a n c ew h i c hd e t e r m i n e st h ec o n n e c t i n gb e t w e e na s e s ，a n dt h en e t w o r ks t a b i l i t yd e c a y sa s w e l l k e yw o r d s ：a sn e t w o r k ；h y p e r g r a p hs t r u c t u r eo ng e o g r a p h i cl o c a t i o n ；a s se x p a n d i n go n z o n e s ；n e t w o r kt o u g h n e s s ：n e t w o r ks t a b i l i t y 大连理工大学学位论文独创性声明 作者郑重声明：所呈交的学位论文，是本人在导师的指导下进行研究 工作所取得的成果。尽我所知，除文中已经注明引用内容和致谢的地方外， 本论文不包含其他个人或集体已经发表的研究成果，也不包含其他已申请 学位或其他用途使用过的成果。与我一同工作的同志对本研究所做的贡献 均已在论文中做了明确的说明并表示了谢意。 若有不实之处，本人愿意承担相关法律责任。 学位论文题目：笆鱼丝勤堕盟垒丝丝旦丝锺垒丝塑堕 作者签名：筵羞堡日期：丝堡年垒月二堡日 人连理工人学硕十研究生学位论文 大连理工大学学位论文版权使用授权书 本人完全了解学校有关学位论文知识产权的规定，在校攻读学位期间 论文工作的知识产权属于大连理工大学，允许论文被查阅和借阅。学校有 权保留论文并向国家有关部门或机构送交论文的复印件和电子版，可以将 本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印、或扫描等复制手段保存和汇编本学位论文。 学位论文题目：笸鱼丝蚴壁鱼咝兰圈丝堑丝堂丝鱼 作者签名： 导师签名： 日期：2 皇望壁年兰_ 月竺日 日期：4 年上月上日 大连理： 大学硕十学位论文 己l吉 】-日 i n t e r n e t 是人类历史发展中的一个伟大的里程碑，它是未来信息高速公路的雏形，人 类正由此进入一个前所未有的信息化社会。人们用各种名称来称呼i n t e m e t ，如国际互联 网、因特网、交互网、网际网等等，它正在向全世界各大洲延伸和扩散，不断增添吸收 新的网络成员。目前，i n t e r a c t 已经成为世界上覆盖面最广、规模最大、信息资源最丰富 的计算机信息网络。 针对不同的预测和改善i n t e r n e t 性能的目的，发现和揭示i n t e m e t 网络的宏观特性，并 深入研究这些宏观特性的产生机制具有十分重要的意义。人们可以在自治系统，即a s 层面或路由器层面上来研究i n t e r n e t 的拓扑结构和宏观特性i l 】。在路由器层面上，节点为 路由器，边为路由器之间的物理连接，如光纤；在a s 层面上，每个a s 是由单一行政部 门所管理的子网络，可由高达数以百计的路由器组成。 近年来，人们对i n t e m e t 拓扑特性的研究以及网络模型的构建主要集中在其a s 层面 上。研究表明，i n t e r n e ta s 层网络是具有无尺度和高聚类等宏观特性的网络【l 川。通过研 究这些宏观特性的产生机制，人们可以更加深刻的理解a s 网络的拓扑演化规律，进而制 定网络的结构和性能优化策略。因此，a s 网络特性的产生机制得到了广泛的研究，成为 网络科学领域研究的热点问题1 3 , 5 - 1 5 j 。 实际上，a s 网络的宏观特性受到诸如经济、地理等众多客观因素的影响。不可否认 的是，这些客观因素对决定网络拓扑并最终影响网络性能具有关键的作用。以往的研究 从影响因素的角度考虑，可以归纳为两大类：基于经济因素的研究和基于地理因素的研 究。大多数学者都认为经济因素，即a s 间经济实力分配的不均衡是a s 网络无尺度等宏 观特性产生的原因，并在此基础上提出了众多基于连接度的网络拓扑产生：器r 3 , 7 - 1 4 l 。众所 周知，a s 网络的聚类结构主要是受地理因素的影响l l 引，上述基于经济因素的研究则忽 略了地理因素对网络拓扑演化过程的影响以及对网络宏观特性的作用。而且值得注意的 是，最早的i n t e r n e t 拓扑产生器是基于地理因素构造的1 6 j 。近年来一批学者的研究也表明， 地理因素对网络的宏观特性具有不可替代的重要作用1 5 , 1 5 - 1 7 1 。 以往的研究中，对地理因素的研究大致可以分为以下两个方面。 其一是通过统计的方法，得到a s 网络受到地理因素影响所呈现出的规律。2 0 0 2 年， y o o ksh 、j e o n gh 和b a r a b a s ial 通过统计全球路由器和人e l 密度分布指出，路由器和 a s 域的地理放置构成了一个由人口密度参数决定的分形集，a s 节点问建立连边的概率 随着地理距离增加而线性减小1 5 j 。2 0 0 3 年，l a k h i n aa 、b y e r sjw 、c r o v e l l am 和m a t t ai 对构成i n t e r n e t 资源的地理分布进行了统计和分析【1 6 , 1 7 j ，文章指出，路由器之间建立连边 a s 的地理分布对i n t e m e t 网络稳定性的影响 的概率随着地理距离的增加而呈指数形式的衰减，a s 所横跨区域数的分布服从幂律分布 的形式。但是值得注意的是，上述的研究只是阐述了人口密度对a s 节点的地理分布机制 的影响以及地理距离对a s 节点之间的建连机制的影响，而没有进一步探究地理因素对整 个网络的宏观特性的作用和影响。 其二是通过考虑地理因素建立a s 网络拓扑模型，模拟和再现a s 之间真实商业合作 关系【5 , 1 5 】。但是以往的研究并没有明确指出地理因素对a s 层网络宏观特性的影响形式以 及影响程度如何。只有定量分析地理因素对a s 网络拓扑特性的影响机制，才能通过调节 构成a s 的路由器的地理分布和路由器间建立连接的地理距离等因素，管理和控制a s 网 络的组织关系，使a s 网络拓扑结构达到最优化，而这恰恰是本文研究的目标。本文研究 了路由器间建立连接的地理距离和平均积聚系数等网络特性的联系，进而得出地理因素 影响网络稳定性的结论。此外，以往的建模工作还存在着两个主要缺陷：第一，以往模 型都是将a s 假设为一种原子结构，即将一个a s 视为一个不可分割的独立节点，在此基 础之上把a s 之间的连接分为区域内连接和跨区域连接。实际上，a s 节点是由路由器构 成的域，各个a s 之间是通过其底层的边界路由器进行连接的，而且一个a s 的多个边界 路由器可能分布在不同的地理区域，只有当同一地理区域内具有两个a s 各自的边界路由 器时，这两个a s 才可能建立连边1 1 叭剐。第二，a s 的作用范围被局限到一个很小的固定 区域【l 引。而实际上，构成一个a s 的路由器可能广泛的分布于世界各地，即一个a s 的作 用范围可能横跨多个区域，甚至是全球性的1 1 7 , 1 9 。 为了弥补传统模型和理论的不足，本文旨在定量地分析地理因素对a s 网络的哪些宏 观特性具有影响、影响的形式以及影响的程度如何，进而得出地理因素与a s 网络稳定性 的关系。而且，与以往关注a s 网络宏观特性产生机制的研究不同，本文认为a s 网络不 是一个孤立的网络系统，而是一个处在开放环境中的、和环境中其它多种网络系统相互 作用的网络。各种客观因素对a s 网络拓扑宏观特性的影响是网络系统问的相互作用的重 要体现。比如，地理因素对a s 网络的影响，就可以认为是a s 边界路由器地理分布网络 和a s 服务供求关系网络相互作用的结果。因此，本文首次提出了能够真实刻画a s 层网 络地理分布的超图结构，以下称为“地理超图，进而阐述了a s 网络和地理超图之间的 相互作用机制：地理超图限定了a s 网络中a s 节点建立连接可选的a s 集合；a s 网络中 a s 节点的度值决定了地理超图中边所包含节点个数。 基于以上机制，本文建立了a s 网络和地理超图的双层拓扑模型，并分别模拟了a s 对地理区域的随机扩张以及a s 对地理区域的近邻扩张两种情况，结果表明：在a s 采取 近邻扩张的前提下，实际a s 网络的平均集聚系数明显受到地理距离因素的影响。具体表 现为：随着建立连接的地理距离减小，网络平均集聚系数呈现出衰减的趋势。最后，本 大连理f t 大学硕士学位论文 文讨论了平均集聚系数与网络坚韧度的关系，得出了建立连接的地理距离越小，网络坚 韧度越小，网络稳定性越差的结论。 本文余下部分组织如下：第一章，i n t e r n e t 概述。主要介绍i n t e r n e t 的一些重要拓扑 特性以及近年来针对a s 层面的i n t e m e t 拓扑结构提出的网络拓扑模型。第二章，i n t e m e t a s 层网络地理超图结构。详细阐述了a s 和路由器之间的关系，对作用于a s 网络的地 理因素做以综述，进而提出了地理超图的定义，并在此基础上分析了a s 网络和地理超 图之间的相互作用。第三章，a s 网络和地理超图的双层拓扑模型。给出基于a s 网络 和地理超图互作用机制的双层网络模型的构造算法，并进行模拟实验，分析该模型所表 现出的宏观特性，比如度分布、度和集聚系数相关性等。结合模型中表示地理因素的参 数，对地理因素和网络宏观特性的关系给出结论。第四章，地理因素与网络稳定性。引 入网络稳定性的概念，在第三章得到的实验结果的基础上，简要的分析地理因素和网络 稳定性的关系。 a s 的地理分布对i n t e m e t 网络稳定性的影响 1 in t e r n e t 概述 近几年来，i n t e r a c t 成为不同学科研究者们研究的热点。来自数学、物理学、经济 学、信息学等各个领域的科学家从不同角度对i n t e r n e t 的拓扑结构与功能、建模机制、 动力学特性及各种应用进行了全方位的研究【刎。本章将对i n t e m e t 网络的拓扑特性及建 模方法进行详细的阐述和分析。 1 1 i n t e r n e t 的拓扑特性 1 1 1幂律分布 通过研究1 9 9 7 年1 1 月至1 9 9 8 年1 2 月a s 层面i n t e m e t 的统计数据，f a l o u t s o s 三 兄弟于1 9 9 9 年首次揭示了i n t e m e t 拓扑的一些幂律分布特性，开拓了i n t e m e t 拓扑研究 的新方向【。然后，他们又针对1 9 9 7 年9 月至2 0 0 2 年2 月的a s 层面i n t e r n e t 拓扑演化 情况作了进一步研究，指出a s 层面i n t e m e t 拓扑满足以下四种幂律分布f 2 】： 幂律分布i ： d ，0 c 妒 ( 1 1 ) 其中d ，是节点，的度，是将网络中节点按度降序排列节点y 的序列号，尺是秩指 数常数。 幂律分布i i ： 见0 cd d ( 1 2 ) 其中见表明度大于d 的节点在整个网络中所占的百分比，d 是度指数常数。可以 推得尺一。 幂律分布： a i ( 1 3 ) 其中凡为网络对应的连接矩阵的特征值，f 为将特征值按降序排列时的序列号。特 征值指数占和连接度指数d 间存在近似关系一0 5 d 。 幂律分布i v ： p ( h ) 0 c h n ( j l 0 ，则网络是同配的；若厂 1 ，那么，对于每个m a n ，在m a n 的另外一个节点( 也可能 会再是x ) 和x 已经连接到的彳中的那个节点相距最近的节点间建立边。 第七步，与上述步骤相类似，将l a n 连接到m a n 。 通过以上步骤所建立的网络，具有较大的网络直径，可由图1 1 5 直观表示。 大连理工大学硕+ 学位论文 嚣! 蕊怒揽麓掰珊善骞：溜 图1 1 5 典型的t i e r s 图 f i g 1 1 5t y p i c a lg r a p ho ft i e r s ( 劲t r a n s i t s t u b 产生器 t r a n s i t s t u b 产生器所产生的拓扑具有三个层次：首先生成最上层的结构，t r a n s i t 域，然后是s t u b 域，直至l a n 。每层上的节点都被限制在一个个的矩形空间内，其中 不同层次的限制空间是不同的，最下层的l a n 的空间最小【2 9 1 。 两组参数控制着域的相对大小： 第一，这组参数控制着域的相对大小：所有t r a n s i t 域的个数t 1 ，每个t r a n s i t 域 的平均节点个数坼1 ，每个t r a n s i t 域的平均s t u b 域个数s 乏1 ，每个s t u b 域的平 均节点个数s s 苫1 ，每个t r a n s i t 域的平均l a n 数l 0 ，每个l a n 的平均主机个 数之1 。这些参数决定了三个层次各自的大小。路由器节点和主机的总数分别记 作心和，满足以一t n r ( i + s n s ) ，日一t n r s n s 巩。 第二，这组参数控制着域内和域间的连通性：一个t r a n s i t 域节点和本域其它节点 间边的平均数耳乏2 ，日必须足够大使得t r a n s i t 域是连通的；一个s t u b 节点和本 域内其它节点间边的平均数e s22 ，e s 必须足够大使得s t u b 域是连通的；一个 t r a n s i t 域和其它域之间边的平均数2 ，必须足够大使得t r a n s i t 域和其它 域是连通的；一个s t u b 域和一个t r a n s i t 域间边的平均数e 盯之1 ，每个s t u b 域都必 须至少和一个t r a n s i t 域相连，而多宿主的s t u b 域则至少要和两个t r a n s i t 域相连； 一个l a n 和一个s t u b 域间边的平均数e 。之1 ，每个l a n 都必须至少和一个s t u b 节点相连。 t r a n s i t s t u b 产生器的建模步骤如下： 孽 栅 舢 萋| 薹| 霎 霎| 惭 眦 j 薹 o ；毒：专蔷摹_i孟_鼍霉； a s 的地理分布对i n t e m e t 网络稳定性的影响 第一步，在指定的位置上生成所有的t r a n s i t 域。可出任何一种随机方法，一般用 w a x m a n 方法生成一张随机图，图中每个节点代表一个t r a n s i t 域；在这个过程中，应保 证生成的图是连通的。 第二步，为每一个t r a n s i t 域生成节点，将节点放置在环绕t r a n s i t 域位置的子域内， 使得t r a n s i t 域平均含有坼个节点；在每个t r a n s i t 域内连接边，使得此域连通，满足 r 2 ，岛22 。 第三步，在每一个t r a n s i t 域中随机选取合适的节点作为t r a n s i t 域间连接边的端点。 第四步，为每一个t r a n s i t 节点的s t u b 域选择合适的位置，并在这个位置周围生成 相应s t u b 域的节点，使每个s t u b 域内包含。个节点，并将其连接起来。 第五步，每个s t u b 域都要和t r a n s i t 域相连。如果e 仃 1 ，那么随机增加额外的从 s t u b 域到t r a n s i t 域的边，并从s t u b 域中选择一个节点，在这个节点与相应的t r a n s i t 节点间加一条边。 第六步，生成l a n ，以星形结构设置主机节点。 第七步，把每个l a n 连接到相应的s t u b 节点的中心路由器上：若日1 ，则额外 的添加中心路由器和s t u b 节点间的连接。 通常建模中仅考虑t r a n s i t 域和s t u b 域，而省略步骤六和七，其生成的网络节点度 的频率厶的对数分布图如图1 1 6 所示。 1 图1 1 6t r a n s i t s t u b 的度频率的对数分布图 f i g 1 1 6l o g - l o gp l o to ft h ed e g r e ev e r s u st h ef r e q u e n c yo f t r a n s i t s t u b 人连理 人学硕士学位论文 1 2 3 基于连接度的产生器 自从f a l a t o u s 三兄弟于1 9 9 9 年发表关于i n t e m e t 拓扑的幂律特性的文章以后f l j i n t e m e t 拓扑产生器的研究进入了一个新的阶段。 ( 1 ) i n e t 为了反映i n t e r a c t 的拓扑特性，尤其是连接度的幂律分布特性，2 0 0 0 年美国m i c h i g a n 大学研究人员提出拓扑产生器i n e t1 0 。后来又对此产生器进行改进，推出了i n e t2 0 和 i n e t3 0 。i n e t3 0 的建模过程如下1 7 ： 第一步，从用户那里获得节点个数和个节点中度为1 的节点所占的比例k 。 第二步，根据下式计算i n t e m e t 从1 9 9 7 年1 1 月份的节点个数增长到所需的月份 数t ： n e x p ( 0 0 2 9 8 t + 7 9 8 4 2 ) ( 1 8 ) 第三步，定义k 、，和y ：k 是度为1 的节点的集合，为前三个最大度的节 点的集合，v 为除去v x 、，中节点以外的其它节点。 第四步，代入f ，根据f ( d ) le d 甜+ 6 来计算y 中节点的度分布，其中f ( d ) 一厂( f ) ， a 、b 、c 为已知常数。i n t e m e t 上度为1 的节点所占的比例基本上维持在3 0 左右。根 据度秩指数增长率d a e p t + q 厂r 来计算，中节点的度分布，其中p 、g 为已知常数。 第五步，在度大于1 的节点间构建一个生成树：令g 为所要产生的图，初始为空集； 不在g 中的度大于1 的节点i 与g 中的一个节点j 相连的概率为 叫力2 劳 n 9 ) 怠 其中 岫a x 1 d i 为节点f 的度，厂( 吐) 为度的频率。 第六步，按概率式( 1 1 0 ) ，将k 中的埘个节点连接到g 中的节点上。 ( 1 1 0 ) a s 的地理分布对i n t e m e t 网络稳定性的影响 第七步，从具有最大度的节点开始，连接g 中仍剩余的自由度；在进行这些连接时， 以概率式( 1 1 0 ) 随机的选取有着自由度的节点。 i n e t 可用于产生不少于3 0 3 7 个节点的网络，这是1 9 9 7 年1 1 月i n t e r n e t 上a s 的数 目。 ( 2 ) a b 模型 a b 模型是a l b e r t 和b a r a b a s i 对b a 模型的拓展，将其应用于i n t e m c t 的拓扑建模。 通过增加节点。边及边的重新配置，网络得以增长和扩展。a b 模型的构建过程如下【8 】： 初始有个孤立节点，每一步执行下面三个步骤中的一个。 第一步，以概率p 增加m ( ms ) 条新的内部连接，即在已存在的节点间添加新 的边：随机选取一个节点作为新的边的起始点，边的另一个端点由以下概率决定： 也“。赫 q 1 1 ) 重复此过程m 次。 第二步，以概率留重新配置m 条边。随机选取节点i 和连接到f 的一个边厶，然后 移走此边，以连接节点f 和节点- i 的新边厶，取代。每次根据式( 1 1 1 ) 所示的概率选取 ，来配置一条边，并重复此过程m 次。 第三步，以概率1 一p 一口增加一个新节点。根据式( 1 1 1 ) 所示的概率分别与网络 中已存在的m 个节点相连接。 其中，0 s p 0 时为超线性优先连接。 由于i n t e r a c t 中的对等连接不是相同的，其中9 0 5 是客户供应商之间的关系；而 通常由供应商向客户出售连通性及传递通信，因此要用有向图来刻画这种关系，且可以 在地理范围上将i n t e r a c t 看作5 个主要的区域。基于此考虑，产生了一个与t a n o 模型具 有相似思想的有向地理区域模型g d t a n g 【1 5 】，其具体建模步骤如下： 定义，个不同的地理区域，每一步增加一个新节点和m 条由客户指向供应商的有向 边。根据分布只随机选择一个地理区域，再用一条有向边将新节点 ，与此区域中的一个 节点f 进行相连，其中选择节点f 的概率为 n ( 弗) 。旋y ， ( 1 1 8 ) ，厶o l 这里咒为节点i 的出度，将v 和f 分别看作客户和供应商；在已存节点间建立臃一1 条 边，节点i 被选作客户的概率为 毗) 2 旋七， n 1 9 ，o 、 大连理工大学硕士学位论文 这里t 为节点f 的入度，节点j 被选作供应商的概率由式( 1 1 8 ) 决定，其中这埘一l 条边中无向边的概率为p ，边的两个端点在同地理区域内的概率为口。令p 一0 0 7 ， 口一0 5 ，便可得到在一定程度上与实际i n t e m e t 值相接近的拓扑特性。 ( 8 ) 多局域世界模型 在a s 层面上，可以示意性的将i n t e m e t 的层次分为国际连接、国家主干、区域网络 和局域网。区域网内的节点紧密连接使得此网络内具有很高的聚合系数，而这些高度聚 合的区域网由国际连接或国家主干稀疏的相互联系在一起。当一个新节点加入到一个区 域网络时，它对其它区域网中的节点影响非常小，而它反过来主要受本区域网中的节点 的影响。若将区域网看做一个“局域世界 ，那么整个i n t e m e t 可以看做是由很多的局 域世界组成的。多局域世界m l w ( m u l i t i 1 0 c a l - w o r l d ) 模型主要刻画了以上的特性f 3 1 1 。 m l w 模型的构造过程如下： 初始为m 个孤立的局域世界，在每个局域世界内部均有个节点、条边。每一步 随机的进行如下的一个操作： 第一步，以概率p 增加一个拥有个节点、气条边的局域世界。 第二步，以概率q 将一个新节点加入到一个已存在的局域世界中，它与同一个局域 世界中的节点建立条边。首先随机的选取一个局域世界q ，此局域世界中，新节点。 将要连接的节点由如下概率选取： ( 。赫 q 2 0 ) 重复此过程巩次。 第三步，以概率，增加朋，条边到一个选定的局域世界。首先随机选取一个局域世界， 边的一端随机选取，另一端根据概率式( 1 2 0 ) 选定，重复此过程m ，次。 第四步，为刻画边的消亡，以概率s 在一个选定的局域世界内去掉m ，条边。首先随 机选取一端，另一端由如下概率选定： ( 屯) 2 j 赤( 1 一n ( t ) ) 1 2 1 ) 其中n o ( t ) 为局域世界q 内的节点个数。重复此过程朋，次。 a s 的地理分布对i n t e m e t 网络稳定性的影响 第五步，以概率u 在一个选定的局域世界域其它已存在的局域世界问建立所。条长程 边。首先随机选取一个局域世界，在其内部根据概率式( 1 2 0 ) 选定一个节点，作为边 的一端，边的另一端位于另一个随机选取的局域世界内，其选定概率仍为式( 1 2 0 ) 。 重复此过程历。次。 上述参数满足0 q 1 , o 墨p ，r ，s ，“ 1 , p + 口+ ，+ s + h 一1 。 实验表明，m l w 模型可以得到清晰的幂律度分布。 1 3 各类模型的定性比较 本章主要介绍了复杂网络理论在i n t e m e t 拓扑建模中的应用【捌，阐述了多种基于a s 层面的不同类型的i n t e m e t 拓扑产生器的建模机理。 当i n t e m e t 规模较小时，一般对它用随机图来进行研究，如w a x m a n 产生器，这看 作是i n t e r a c t 拓扑产生器研究的第一代。随着网络规模的不断拓展和人类认识的进步， 发现i n t e m e t 并不是完全随机的，而是具有层次结构的，便出现了第二代拓扑产生器一 基于网络层次建模的拓扑产生器，如t i e r s 和t r a n s i t s t u b 。1 9 9 9 年i n t e m e t 幂律分布 的发现又导致了基于连接度的产生器的出现。基于度的产生器具有与i n t e m e t 相似的稀 疏的拓扑结构，更能反映i n t e r a c t 的无尺度特性，这比过分关注于层次的结构产生器更 优胜1 1 2 3 2 1 。下面对基于连接度的拓扑产生器进行了综合比较。 i n e t 是一个静态模型，不能反映i n t e m e t 的动态变化情况，但是对于特定规模的 i n t e m e t ，在某些拓扑特性上还是比较符合。比如度分布遵循幂律，最大度与i n t e m e t 实 际值较为接近等。 a b 模型中的建连机制可能会导致整个图不连通，且出现自环和重边。但是取其最 大连通子图且去掉自环和重边后加以研究发现，a b 模型的连接度分布呈现幂律，且幂 律指数接近i n t e r a c t 的统计值，但是，在其它特性上，a b 模型与i n t e r a c t 存在较大的偏 差。 b r i t e 尽可能全面的考虑了i n t e r a c t 实际拓扑的多个方面，如层次性、连接度分布 等，并将多个已存在的拓扑产生器的功能融合在一个拓扑产生器中，为广泛使用的仿真 应用提供更好的接口。 g l p 模型产生的度分布服从幂律，且幂律指数、最大连接度均与i n t e r a c t 很接近。 它的特征路径长度和聚类系数均略低于i n t e m e t 的实际值。 p f p 模型是基于新节点和内部边的交互增长、非线性优先连接两个机理构建的，很 好的再现了i n t e m e t 的相关拓扑特性。 大连理t 大学硕十学位论文 d p 模型反映了一定规模的i n t e r n e t 的小世界特性，但是，随着时间的进展，i n t e r n e t 的聚类系数在不断增大，而d p 却不能反映这种变化趋势。 t a n g 产生的幂律指数和叶子节点所占比例均接近i n t e r n e t 统计值，且能一定程度上 反映i n t e r n e t 的聚类特性。 m l w 模型很好的反映了i n t e r n e t 的局域世界特性，且