拓扑图生成器（精选3篇）
拓扑图生成器 篇1
摘要：现在全球上网的人数与日俱增, 计算机网络的安全令人担忧, 如何解决计算机网络安全问题, 是研究网络安全的学者的一个新课题, 本论文主要研究如何设计一种拓扑图生成器, 解决网络安全问题, 希望本论文的研究, 能为计算机网络安全问题的解决, 提供一些理论依据。
关键词：TCP/IP协议,拓扑图生成器,设计
0 引言
进入新世纪以后, 计算机技术与计算机网络技术发展迅速, Internet技术得到广泛应用, 同时计算机网络越来越不安全, 计算机的网络安全越来越重要, 拓扑图生成器的研究就是解决计算机网络安全问题的, 拓扑图生成器的应用, 解决了计算机网络安全的一些问题, 其应用领域比较广泛。
1 拓扑图简介
计算机网络的拓扑结构主要分总线型、星型、环形、树形等结构。每种拓扑结构有各自的优缺点。网络在实际设计的过程中, 主要根据实际情况, 结合各种拓扑结构的特点, 一般都选择多种结构相结合的模式, 发挥拓扑结构在网络设计过程中的优势。
2 拓扑图生成器简介
对于计算机网络而言, 网络管理和安全问题已经变得越来越重要。网络安全主要是指网络自身安全和网络业务安全。那么如何保证网络的安全呢?首先要有一个可靠的网络, 其次就是要有强有力的网络管理和网络安全管理。目前许多网络管理员凭借自己的学识和经验进行网络管理和安全管理, 但随着网络规模的日益壮大, 这种管理方法已经不能适应当前的网络需求。因此, 我们必须借助一些工具和软件来管理整个网络。
网络拓扑图生成器就是这样一种软件。它能够自动发现设备, 生成拓扑图, 可以模拟真实的网络布局。并且根据设备之间的连接关系, 绘制设备连接拓扑图, 设备拓扑结构可以分组管理, 形成树形拓扑结构, 这样如果设备较多, 连接复杂的情况下, 很容易对设备进行拓扑描述, 方便设备查找和管理。
3 扑图生成器的总体设计
3.1 设计目标
这次课题的设计目的是为了生成网络拓扑图, 设计环境是寝室里的局域网, 整个设计的大背景是学校的局域网, 所要做的只是通过在计算上运行设计的程序, 得到寝室局域网的拓扑图。生成拓扑图的目的, 是为了快速实时地发现当前开机和使用网络的局域网内部用户, 并且提供给用户一系列的操作和节点的信息。
因为所完成的课题的实现思路是通过建立套接字, 完成计算机之间的通信, 最后通过IP地址画出拓扑图。所以, 这个程序同时还具备一些别的功能。这个程序可以接收和发送消息。也可以向一个指定IP地址的机器发送和接收UDP数据报信息。这个程序既可以作为一个服务器程序, 同时接收多个机器的连接并作出回应, 同时还可以作为一个客户机程序连接其他指定IP地址的机器。
3.2 操作系统和应用环境
所采用的操作系统软件可以是Windows XP, 也可以是Windows 7, 因为它们都支持Windows Sockets API, 在此次课程设计中, 将以在Windows XP环境下的开发为例。
所采用的网络通信协议一般是TCP / IP。Windows 98和Windows NT都带有该协议。但是, 所开发的网络通信应用程序并不能直接与TCP / IP核心打交道, 而是与网络应用编程界面Windows Sockets API打交道。Windows Sockets API则可直接与TCP/IP核心进行沟通。TCP / IP核心协议连同网络物理介质 (如网卡) 一起, 都是提供网络应用程序间相互通信的设施。
3.3 实现工具
本次课题设计的是网络底层的实现, 与TCP/IP协议密切相关, 而且要求要有较好的实时性和较高的效率, 因此选择了VISUAL C++作为开发工具。
C++语言具有高效、灵活、面向对象的特点。在Visual C++里可以创建和设计对话框, 首先, 要创建对话框模板, 然后在此基础上添加和定位各种控件, 最后组织对话框控件。对话框和控件的具体使用这里就不做详细地讲解了。我们最终利用Visual C++做成一个界面, 并且用这个界面实现了拓扑的生成。
4 主要功能模块的设计
4.1 拓扑图的发现
对于拓扑图的发现, 又可以细分为主干拓扑图和子网拓扑图。
主干拓扑图就是我们这次课题的大背景, 也就是整个学校局域网。关于主干拓扑图的发现, 有两种方法:
(1) 利用现有的网络拓扑图, 其将各子网和交换机的信息存储在程序
的配置文件里, 程序启动时根据配置文件的信息构造生成主拓扑图, 用户可以在程序中或在配置文件中添加、删除子网或修改子网和交换机的信息, 不过此种方法不能自动随着网络结构的变化而变化。
(2) 利用SNMP协议取得网络中主干交换机中存储的关于虚拟子网的信
息, 用来分析网络主干的拓扑情况, 当网络中的拓扑结构发生变化时, 即改变了VLAN的划分时, 程序可以根据主干交换机中的信息而自动的改变拓扑图。
子网拓扑图正是这次课题所要研究的内容。对于子网拓扑图, 我们可以通过创建套接字, 并通过套接字发送消息来确定计算机的IP地址。并且能根据消息来确定所连接的计算机是否开机或连在网络上。对于连在网络上的计算机, 通过其IP地址来确定此计算机拓扑图中的节点, 从而生成拓扑图。
4.2 拓扑图的保存
我们要想把网络中各主机的位置以图的形式显示出来, 那就必须知道网络中各主机的有关信息, 再把这些信息作为拓扑图中节点的信息保存起来, 最后在节点之间添线从而完成拓扑图。这个工作可以分两步来完成。
首先, 就是确定拓扑图中的节点。当我们确定了网络中各主机的IP地址后, 可以把这个信息当作拓扑图中节点的一个属性保存起来。当然, 节点对象要存储的信息不仅仅是IP地址, 还包括名字、坐标、子网掩码、MAC等信息。然后对这些节点进行相关的操作和设置, 最后在屏幕上显示出该节点。
其次, 就是要把各节点连线才能完成一个完整的拓扑图。对于连线的方式, 可以根据动态连接和静态连接来考虑。对于静态的拓扑图, 用折线比较好, 因为折线看起来要比直线的拓扑图更美观一些, 不过折线的实现方法比较复杂。而对于动态的, 各节点都是动态生成的, 要用折线正确清晰的实现拓扑图比较困难, 所以最好选择直线, 并且节点之间的连线也随着节点位置的变化而变化。采用直线连接, 在一个星型拓扑图的显示中, 只需要知道中心点的坐标和其余各个节点的坐标, 然后依次把中心点和其他节点连接起来, 因此只要用一个数组存储各节点的坐标就可以最终完成拓扑图的生成。
总之, 网络拓扑图生成器的设计, 主要是解决网络安全问题, 网络安全是当今网络上最大的问题, 也是最重要的问题, 全世界的人们都希望自己的网络安全, 密码不被盗用, 本论文提出拓扑图生成器的设计, 目的是解决网络安全问题, 其实际的应用, 在一定意思上解决了网络的安全问题。
参考文献
[1]王大东, 王洪君, 王瑞军, 高远.一种基于AS的Internet拓扑模型[J].计算机工程.2011 (04)
[2]尹春华, 陈雷.网络涌现现象对网络安全的影响研究[J].计算机工程与应用.2005 (06)
拓扑图生成器 篇2
由于无线环境的复杂性、时变性以及授权网络的异构性和授权用户业务的多样性, 认知无线电用户通信时使用的信道、信道的数量、使用的时间长短以及在信道上的发射功率等都是动态变化的。同时, 认知无线电设备本身的移动性导致系统的拓扑动态变化, 这不仅体现在拓扑结构的变化, 而且体现在拓扑形式的变化。本文对认知无线电系统中拓扑可变的拓扑生成算法进行研究, 采用基于图论的拓扑生成算法, 包括核心树算法和最小连通支配集 ( MCDS) 算法。
核心树算法是生成拓扑的典型算法, 但在认知无线电系统中的应用还比较少见, 该算法在认知无线电中的应用研究具有一定的探索意义。
MCDS的求解是NP难问题[1,2], 因此, 在实际应用中, 通常采用近似算法求解。目前的研究也主要集中在近似算法上, 算法的主要目标是在多项式时间内得到更好的近似解[3], 所以求MCDS的难点就是得出的近似连通支配集尽可能最小, 尽量不含冗余支配点。网络图中的连通支配集 ( CDS) 可以作为虚拟骨干的有效结构[4], 而较小的CDS意味着用更少的骨干节点参与消息转发, 有利于降低能耗, 延长网络寿命, 这两点对 于认知系 统来说极 其重要[4,5]。因此认知无线电系统中, 对于MCDS问题的研究有着重要意义。
1核心树算法
核心树是所有节点通过相互间的父子关系所形成的树形逻辑拓扑。核心树算法全称是核心树组网路由算法 ( Kernel Tree Routing Algorithm, KTRA) , 是一种新的Ad Hoc组网和路由算法, 设计思想是在Ad Hoc网络自然拓扑结构中, 利用节点间信息交互, 设计树的构造算法和通信协议, 重构形成一种逻辑上的树形拓扑结构[6]。本文通过核心树算法进行认知无线电系统中的拓扑生成。
核心树构造算法的基本思想是从树根开始向上生长, 逐渐生成整棵树。所有节点按照到根的距离最短准则加入到树上, 节点间所有通信, 包括业务流量和拓扑结构维护等, 都限制在这棵树上流动[6,7]。
为了避免因核心树级数过大而影响实际通信效果, 限制核心树的级数最大为6级。核心树生成算法步骤如下:
1根节点启动, 产生仅有一个节点的一级核心树。根节点级别固定为1。
2将能够与根节点直接通信的节点加入核心树, 设置其级别为2。此时的核心树是一个2级核心树。
3未加入核心树的其他节点找出能与自身直接通信的已加入核心树节点, 选择其中级别最小的节点作为父节点加入核心树, 设置级别为父节点级别加1。
4未加入核心树的节点重复步骤3, 直至所有的节点加入核心树。
2 NC-MCDS算法
2. 1基本概念
支配集[1,8]: 设D是V的一个子集, 如果集合D - V中的任何一个节点与D中的某个节点可直接通信, 则称D是V的一个支配集, D中的节点称为V的支配节点。
连通图: 如果2个节点之间存在一条直接或间接的 ( 即通过其他节点中转的) 通信路径, 则称这2个节点是连通的, 如果某图中任意2个节点是联通的, 则称该图为连通图。
CDS[9]: 给定一个图G = ( V, E) , 图G的节点集DV为满足如下条件的节点集合: 由D导出的子图是连通图, 且D是图G的一个支配集, 则称D为连通支配集。若D为满足上述条件的最小节点集合, 则称D为最小连通支配集。
相邻接节点: 若p, q为图G = ( V, E) 中的任意2个节点, 即p, q∈V, 若存在E中的一条边连接节点p, q, 则称节点p和节点q相邻。
一级邻接节点: 节点x的直接邻接节点。
二级邻接节点: 节点x的一级邻接节点的一级邻接节点 ( x除外) 。
节点状态: 每个节点有2种状态, 分别用 - 1, 0, 1表示。节点x = - 1为初始状态, 节点x = 0为被支配状态, 节点x = 1为支配状态。
节点连通度: 可与某节点直接进行通信的节点的总数目称为该节点的节点连通度。选取具有最大节点连通度的节点充当支配点, 可以获得更小的CDS, 而且MCDS的建立时间也会加快。这样就可以减少非支配点之间冗余的无线通信链路, 大大减少通信开销。
2. 2算法原理
参考Ivan Stojmenovic等学者提出的Ivan算法[10]、文献[11]中的集中式算法以及文献[12]中的EB-MCDS算法, 将MCDS算法与基于连通度的思想相结合, 提出NC-MCDS算法。算法基于若可与一个节点相连的节点数越多, 则可认为这个节点越重要的思想, 将其作为支配节点的优先级就应越高, 进而使最终的支配集趋向于最小化。
采用最小连通支配集算法生成树状网, 首先计算网络的最小连通支配集, 如果最小连通支配集是树, 并且满足系统的要求, 则在其基础上添加分支, 将剩余的节点接入; 如果最小连通支配集不是树, 则继续计算该网络的最小连通支配集, 递归得出树状网。
2. 3算法步骤
下面介绍NC-MCDS算法的具体步骤。首先初始化所有节点, 设从节点u开始, 步骤如下:
1将节点u赋值为1;
2将u的一级邻接节点 ( 处于初始状态的) 赋值为0, 暂时成为被支配点;
3比较u的二级节点 ( 非支配节点) 的可连接数值, 选择值最大的二级节点v赋值为1, 成为支配节点 ( 若连通度相同, 则可选择编号较小者, 下同) ;
4在节点u与节点v之间的u的一级邻接节点 ( 非支配节点) 中, 选连通度最大的节点的作为支配节点, 赋值为1;
5相关节点重复步骤2 ~ 步骤4, 直到网络中没有初始节点;
6排除终端节点被赋值为支配节点以及终端三角环路等情况, 以尽量保证支配集最小;
7 NC-MCDS算法构造结束。
至此, 得出最小连通支配集, 在其基础上添加叶节点, 即可生成树状网。
3仿真结果及分析
下面通过Matlab对核心树算法和NC-MCDS算法进行仿真分析。在100 m×100 m的区域中随机分布有16个认知设备节点。认知设备的通信半径为40 m, 各节点可以探测到通信距离范围内的邻接节点, 并可以通过预留的公共控制信道进行邻接节点间信息的交互。
同一分布情况下, 最小连通支配集算法 ( NCMCDS) 与核心树算法生成拓扑的对比情况如图1所示。为了便于区分, NC-MCDS算法没有添加终端节点, 只显示最小支配集的节点, 且用虚线标出了各节点的可达情况; 核心树算法则完整的标出了各父子节点的连接情况。
认知无线电设备在100 m×100 m范围内, 分布情况变化50次过程中, NC-MCDS算法与核心树算法的核心节点 数的对比 情况如图2所示。NCMCDS核心节点数少于核心树的有22次, 多于核心树的有14次, 相等的有14次, 即NC-MCDS算法占优的比例为44% , 核心树算法仅为28% , 二者比例超过3∶2。
图3中, 随着通信半径的增大, 节点数总体呈现下降趋势。对于核心树算法与NC-MCDS算法核心节点数均有起伏变化。图3中50% 的情况下, 最小连通支配集算法NC-MCDS的节点数少于核心树算法的节点数; 44 % 的情况下, 最小连通支配集算法节点数等于核心树算法的节点数; 6% 的情况下, 核心树节点数少于NC-MCDS的节点数, 这是由于NCMCDS算法为最小连通支配集近似算法, 可能不可避免地存在冗余节点。
进行10次试验, 每次试验进行50次随机拓扑生成, NC-MCDS的支配节点数不多于核心树的核心节点数的情况所占的比例如图4所示。从图中可以看出, NC-MCDS算法优于核心树算法的比例不小于64% , 甚至可达到80% 。单从图4看, NC-MCDS算法要优于核心树算法。
4结束语
将核心树算法、最小支配集算法与认知无线电的拓扑生成相结合, 根据拓扑图的生成特性, 可以为实际认知网络的组建提供理论依据。在很大的概率上 ( 多次仿真, 基本上不小于60% ) , NC-MCDS算法所得的核心节点数比生成树算法计算出的核心节点数要少, 从这一点来说, NC-MCDS算法要优于核心树算法; 然而, MCDS的计算是NP难问题, NCMCDS算法的复杂度也要高于核心树算法。针对认知无线电特定的应用环境及技术要求, 权衡二者的其他技术指标, 选择合适的算法则是一个关键问题, 将针对此问题进行进一步的研究。
摘要：针对认知无线电系统本身的时变特性, 将核心树算法与最小连通支配集算法应用于认知无线电系统的拓扑生成中。对于最小连通支配集算法, 提出了一种适用于认知无线电系统的基于节点连通度的最小连通支配集算法 (NCMCDS) , 并对核心树算法与NC-MCDS算法进行了Matlab仿真。通过仿真结果中不同情况下核心节点数与最小连通支配集中的元素个数的对比, 比较并分析了核心树算法与NC-MCDS算法的性能。
关键词：认知无线电,最小连通支配集,核心树,NC-MCDS算法
参考文献
[1]路纲, 周明天, 唐勇, 等.任意图支配集精确算法回顾[J].计算机学报, 2010, 33 (6) :1 073-1 087.
[2]LABRADOR M A, WIGHTMAN P M.Topology Control in Wireless Sensor Networks[M].Berlin:Springer, 2009:61-68.
[3]WU J.Extended Dominating-Set-Based Routing in Ad Hoc Wireless Networks with Unidirection-nal Links[J].IEEE Trans on Paralleland Distribu-ted Systems, 2002, 13 (9) :866-881.
[4]BLUM J, DING M, THAELER A, et al.Connected Dominating Set in Sensor Networks and MANETs[M].Handbook of Combinatorial Optimization New York:Kluwer Academic Publishers, 2004:329-369.
[5]张亮, 赵林靖, 胡婧, 等.基于认知无线电技术的802.22标准[J].无线电程, 2007, 37 (1) :9-11.
[6]毛玉明, 杨宁, 段景山.移动Ad Hoc网的一种新的自组织组网和路山算法[J].电子学报, 2004, 32 (12) :161-164.
[7]万倩倩, 白勇.基于邻居节点的拓扑控制算法研究与仿真[J].无线电通信技术, 2012, 38 (3) :12-13.
[8]路纲, 周明天, 唐勇, 等.任意图支配集精确算法回顾[J].计算学报, 2010, 33 (6) :1 073-1 087.
[9]HAYNES T W, HEDETNIEMI S T, SLATER P J.Fundamentals of Domination in Graphs[M].New York:Marcel Dekker Inc., 1998.
[10]STOJMENOVICL I, SEDDIGHET AL M.Internal Nodes Based Broadcasting in Wireless Network[C]∥34th Annual Hawaii International Conference on System Sciences.Hawaii, USA, 2001:9 001-9 005.
[11]GUHA S, KHULLER S.Approximation Algorithms for Connected Dominating Sets[J].Algorithmica, 1998, 20 (4) :374-387.
拓扑图生成器 篇3
如今,在拓扑建模的研究中,Internet作为一个大型网络的应用实例,已成为研究热点,受到了广泛的关注[1]。从1995年开始的大规模Internet拓扑测量工作已经逐步展开[2],采集到了大量的拓扑数据(BGP)。最近的一些研究表明,层次性特征和幂率分布是大型网络拓扑结构的两个固有的性质。其中,层次性质是从宏观的角度反映了网络的结构特性,而幂率则是从微观的角度,反映了网络中节点的分布规律。Zegura、Doar等人通过大量的观察、研究,发现网络中的节点存在着等级差异,于是他们分别提出了Tiers[3]、Transit-Stub[4]拓扑模型,这些模型都能很好地抓住网络中的层次性特征。但是,这些层次型拓扑模型没能很好地抓住网络中的幂率特征。事实上,在这些层次型的拓扑生成算法中,每一层内的节点都是按照完全随机方式分布的。
1999年,Faloutsos等人在对大量的拓扑数据进行了分析之后,提出了幂率规则[5]。
幂率1(等级指数R)节点的出度dv与该节点等级rv的R次幂成比例(rv是节点按出度降序排列序列中的索引值),表示为:
幂率2(出度指数O)出度频率fd与该出度d的O次幂成比例(Fd={v|v∈V且dv=d},其中V表示网络中全体节点v的集合),表示为:
幂率3(hop-plot指数H)在跳数h远小于网络直径δ时,h跳内节点对的数量与h的H次幂成比例(P(h)是节点对的总数),表示为:
幂率4(特征指数E)特征值λi与其次序i的E次幂成比例(i为特征值按降序排列的序号),表示为:
在幂率规则被Faloutsos等人发现之后,研究人员开发出了许多遵循幂率分布规则的拓扑生成算法(BRITE[6]、PLRG[7]、Inet[8]等),虽然这些拓扑生成模型能够很好地抓住网络中的幂率规则,但是它们没能容入层次性建模方法。本文的目的是将幂率融入到层次型网络拓扑生成算法中去,从而获得与实际网络更大的相似度。
2 基于幂率的层次型拓扑生成算法HIPL
2.1 HIPL算法思想
在进行网络仿真实验时,计算机网络可以表示为一个连通的无向图G=(V,E),其中V代表网络的节点集,E代表网络中边的集合,每条边为连接网络节点的通信链路。在原先Doar等人提出的层次型拓扑模型中,每一层的节点都是随机分布的,经对大量的实际拓扑数据进行分析,这样生成的网络拓扑图与实际网络拓扑结构差距较大。HIPL的基本思想是在层次型拓扑生成算法中,每一层的节点生成过程力图使之满足幂率分布(而不是随机分布)。如今生成满足幂率分布的拓扑图的方法主要有以下两种:
(1)分析网络模型的参数与幂率的关系,并将其设置为幂的函数:
其中,fx代表出度达到x的节点的个数,β、α为常数。
(2)模拟实际网络的生成过程,通过向初始网络中添加节点和连接的方式进行拓扑图的生成。在新的节点加入的时候,满足优先连接规则。即一个新加入节点与图中已存在节点v相连接的概率L与该节点出度dv的大小线性相关(即优先附着)。
其中,j属于图中已存在节点集合;c为常数,其值越小,优先附着性越弱。
第2种方法生成的网络拓扑能较好地符合幂率分布规则,是当前主要的生成方法。本文也使用这种生成方法。第2种方法实际是一个迭代生成的过程,在一个迭代周期中规定了下面三种操作:加入一个度为1的新节点;加入一个度为2的新节点;在存在的节点集中添加一条连接。
定义1以概率δ1∈[0,1]加入一个度为1的新节点:在第n层中加入一个度为1的新节点p,在n-1层中根据概率L选出一个已经存在的节点v,将p与v相连接。
定义2以概率δ2∈[0,1-δ1]加入一个度为2的新节点:在第n层中加入一个度为2的新节点q,其中至少有一条边根据线性优先概率L和第n-1层中的节点连接,还有一条随机选择和第n层或第n-1层中的节点连接。
定义3以概率1-δ1-δ2在现有的节点集中添加一条连接:在第n层中随机选取一个已经存在的节点m,将它与本层内的节点或者与第n-1层的节点(甚至第n-2层的节点)根据线性优先概率L连接。
2.2 算法步骤
根据HIPL的算法思想,算法的具体步骤如下:
step 1确定网络拓扑图的节点规模V,并确定网络拓扑中的层次结构(即确定网络拓扑分成的层次数N)。实际的网络拓扑图的生成过程中,节点的规模和层次结构都是由具体的拓扑测量数据来确定的。
step 2随机生成m1(m1<=100)个节点,并将它们完全连接,将这m1个节点作为顶层节点(因为幂率是反映大型网络的节点的分布规律的,所以顶层的m1个节点并不满足幂率)。顶层的节点的个数在整个拓扑生成的过程中都是保持固定不变的。
step 3依次确定各层的节点规模mn,n=2,3,…,从第二层开始反复地执行HIPL算法思想中介绍的迭代周期中的a、b、c三个操作(δ1=0.3,δ2=0.1),每次执行完一次周期后判断当前的节点规模是否达到mn,若是达到了mn则转入下一层执行拓扑生成算法,若是没有达到mn则继续执行迭代周期中的操作,直到当前层的节点规模达到设定值mn。值得注意的是,对于每个节点v,它属于哪一层是固定的,在拓扑生成过程中,v不会“移动”到其它层的节点集内。
step 4 step 3是一个循环的过程,它自上向下依次生成各层的节点集,当各层的节点都已经生成完毕,算法结束。
3 实验和结果
为了验证HIPL的正确性,对其进行了仿真实现,并进行了一些分析。在实验中试图建立一个AS级的Internet拓扑模型,一些参考的数据输入是来自美国的Oregon大学的BGP路由数据工程[6]。我们参照的是2001年5月7日的BGP数据(1010507),Internet中共10966个AS节点,我们将这些节点分成5层进行拓扑生成。首先生成一定规模的顶层节点,然后依次生成各层的节点。
首先,来考虑生成的拓扑图中各层节点对幂率分布的满足情况。为了节约空间,这里只考虑CCDF(即幂率2)的满足情况。结果如图1、图2、图3所示。从图中可以看出,生成的拓扑图中各层的节点能较好地满足幂率分布规律。
其次,以实际拓扑测量得到的AS级拓扑图为基础,比较了各种拓扑模型与真实AS图之间的差异(如表1所示)。拓扑参数有平均度数、群集系数、直径、特征路径长度,其定义如下[11]:
●平均度数拓扑图中所有节点的出度的算术平均值。
●群集系数用来描绘拓扑图中出现的小集团。设节点v有dv个邻居,那么邻居之间最多有M=dv(dv-l)/2条边,Cv等于邻居间实际边数除以M的商,再将每个节点的C取平均就得到聚类系数。
●直径拓扑图中任意节点对间最短路径的最大值(单位为hop)。
●特征路径长度描述拓扑图的疏密程度,等于图中每对节点之间最短路径距离的平均值(单位为hop)。
4 结论
目前,网络拓扑图作为一种数据输入,广泛地应用于各种网络仿真软件中。本文提出了一种新的基于幂率的层次型拓扑生成算法HIPL,同时抓住了大型网络拓扑结构的层次性和幂率分布两个固有性质。实验证明,该算法很好地将幂率分布规律溶入到层次型拓扑生成算法中,解决了原先的层次型拓扑模型不满足幂率分布规律的问题。
如何描述一个大型复杂网络(如Internet)的特征仍然是一个开放性的问题。本文的下一步工作将涉及下面几个问题:(1)拓扑建模是否可以加入一个时间刻度(time-scale),用来模拟网络随时间变化的动态性变化;(2)是否可建立基于Qos约束的大型网络拓扑模型,更好地模拟实际的网络;(3)模拟实际网络的生成过程中,节点的优先附着是遵循线性规律还是其它的数学规律。
参考文献
[1]张宇，张宏莉．方滨兴．Internet拓扑建模综述[J]．软件学报，2004，15(8)：1220-1226．
[2]姜誉，方滨兴，胡铭曾，何仁清．大型ISP网络拓扑多点测量及其特征分析实例[J]．软件学报，2005，16(5)：846-856．
[3]Doar MB.A better model for generating test networks[C].Proc.of the GLOBECOM:IEEE,1996:86-93.
[4]Zegura E W,Calvert K L,Donahoo M J.A quantitative comparison of graph-based models for Intemet topology[J].IEEE/ACM Transactions on Networking,1997,5(6):770-783.
[5]Siganos G.Faloutsos M.Faloutsos P.Faloutsos C.Power-Laws and the AS-level Internet Topology[J].IEEE/ACM Transactions on Networ- king,2003,11(4):514-524.
[6]Medina A,Lakhina A,Matta I,Byers J.BRITE:An approach to univer- sal topology generation[C].In:Proc.of the MASCOTS 2001.Washing- ton:IEEE Computer Society,2001:346-353.
[7]Aiello W,Chung F,Lu LY.A random graph model for massive graphs [C].In:Proc.of the ACM STOC 2000,Protland:ACM Press,2000: 171-180.
[8]Jarod Winick,Sugih Jamin.Inet-3.0:Intemet topology generator[R].Tech- nical Report,CSE-TR-456-02,Ann Arbor:University of Michigan,2002.