基于BetweennessCentrality提高复杂网络容量的方法

2006全国复杂网络学术会议（CCCN’06）中国，武汉，华中师范大学，2006年11月16日－19日──────────收稿日期：作者简介：范晶（1982－），女，湖北武汉人，硕士研究生，[e-mail]基于BetweennessCentrality提高复杂网络容量的方法范晶1,2秦卓琼1,2张国强1,2张国清1（1.中国科学院计算技术研究所北京100080）（2.中国科学院研究生院北京100080）摘要：BetweennessCentrality能够刻画节点在网络中的重要程度，能够反映节点在网络中可能承载的网络流量。本文引入BetweennessCentrality对网络拓扑进行优化和拥塞预测，通过理论分析和仿真实验，提出在具有scale-free特征的复杂网络中，依据Betweenness值以及Betweenness的标准差增加一些捷径路径的方法，有效平衡中枢节点的负载，缓解拥塞状况，提高网络容量。关键词：BetweennessCentrality，网络拓扑，网络容量，拥塞，无标度网络AMETHODFORIMPROVINGCOMPLEXNETWORKCAPACITYBASEDONBETWEENNESSCENTRALITYFanJing1,2QinZhuoqiong1,2ZhangGuoqiang1,2ZhangGuoqing1(1.InstituteofComputingTechnology,ChineseAcademyofScienceBeijing100080)(2.GraduateUniversityofChineseAcademyofScienceBeijing100080)ABSTRACT:TheBetweennessCentralityindexisadirectmeasureofmessagetraffic.HighBetweennessCentralityscoresindicatethatavertexliesonconsiderablefractionsofshortestpathsconnectingothersanditplaysanimportantroleinthenetwork.Theindexisintroducedheretooptimizenetworktopologyandidentifynodeswhicharemostlikelytocausecongestion.Weproposesomemethodsaftertheoreticalanalysisandexperimentstoaddsomeshortcutsinscale-freenetworksaccordingtoBetweennessandthevariationofBetweenness.Thiscanbalanceloadamongthecorenodes,relievecongestionefficientlyandincreasethecapacityofthenetworksubstantially.Keywords:BetweennessCentrality,networktopology,networkcapacity,congestion,scale-freenetwork2006全国复杂网络学术会议（CCCN’06）论文集1引言随着互联网的普及和发展，各种新兴的Internet业务不断涌现，上网的计算机数和网站数迅猛增长，在网络使用高峰时段，大多数网络都会出现拥塞，服务质量下降。网络拥塞受很多因素影响，例如节点的容量、链路的带宽、网络路由协议还有网络拓扑。为了获得令人满意的服务质量，缓解拥塞状况，大多数网络运营决策人员会选择扩容或者更换网络设备，而很少尝试对已有的网络拓扑作些小小的改变来提高网络性能[1]。而事实上系统的动态特征（网络流量）和网络的静态结构（网络拓扑）关系非常密切[2]，网络拓扑结构是影响网络负载分布的主要因素之一。BetweennessCentrality（简称Betweenness）的概念源于分析社会网络中个体的重要性[3]。简单地讲，一个节点的Betweenness表示所有的节点对之间通过该节点的最短路径条数。Betweenness很好地描述了一个网络中节点可能需要承载的流量。一个节点的Betweenness越大，流经它的数据分组越多，意味着它更容易拥塞，成为网络的瓶颈。在早期的网络拓扑模型的研究中，网络拓扑模型通常采用完全随机图模型，认为网络中的节点度大致相同，呈正态分布。近期的研究表明Internet的网络节点度呈幂律分布，具有这种特征的网络就被称之为无标度（scale-free）网络。大多数节点度较小，而一小部分节点则节点度很大，通常称之为中枢节点。中枢节点的Betweenness就往往很大，一旦中枢节点崩溃，整个网络就面临瘫痪的危险，所以平衡整个网络的流量来提高系统容量对符合scale-free特征的网络尤为必要。文[1]中指出在度分布具有Bi-Modal特征、拓扑结构较为规则的网络中，单单增加这类Betweenness较大的节点的容量只能很小程度地减小拥塞，要想有效地避免拥塞，必须大幅度增大节点容量，而这必然花费相当高的成本。然而在Betweenness较大的前5个节点间增加连接，同时适当增加节点的容量，则会大幅度提高网络容量，如果在Betweenness较大的前5个节点和随机选择的其它的节点间增加连接，则容量提高得更多。但是对于scale-free网络来说，给Betweenness较大的前5个节点增加连接对于原本负载就很重的中枢节点，简直就是雪上加霜。缓解中枢节点的压力比单纯提高网络容量更为重要。本文以基于Barabási-Albert(BA)算法构造的scale-free网络为模型，研究在最短路由算法下此类网络的容量问题。通过理论分析和实验仿真，提出依据Betweenness的值和标准差，增加尽可能少的捷径路径，改善中枢节点的拥塞状况，提高网络容量的方法，对网络运营决策人员进行容量分析和规划有实际指导意义。2基于BetweennessCentrality的网络容量分析当网络负载很低的时候，转发节点的缓冲队列较空，这时，数据分组的平均端到端时延近似的和分组经过的平均节点数成比例[4]。当加大负载，转发节点的队列开始增加，平均时延也相应增加。当负载更进一步加重，达到一个临界值λc，某些节点的缓冲队列将增长很快，数据分组平均时延陡增，网络性能恶化。这时，认为网络发生了拥塞，网络的吞吐量由升转降，而λc就定义为网络的容量。2006全国复杂网络学术会议（CCCN’06）论文集通信网络可以用图G=（V，E）来表示，其中V代表节点（顶点）集，E代表链路（边）集。主机、路由器和交换机在图中用节点（顶点）来表示，它们之间的物理连接则用链路（边）来表示。本文只考虑连通无向图。如果记图中任意两点s,d之间的最短路径条数为sd，而这些最短路径中经过节点w的条数为)w(sd，那么节点s,d之间经过w的最短路径条数占s,d间总的最短路径条数的比例为sdsd)w(，在此基础上，节点w的BetweennessCentrality定义为：sdBsdsVdsV(w)C(w)一个节点的BC越大，它就显得越重要，因为大量的数据分组将流经它，它的负载将很重。因此，这种类型的节点在设计时需要更大的数据处理速率，连接的链路也需要更大的带宽容量[5]。Scale-free网络的中枢节点通常是数据传输中使用率很高的节点，因此BC会很大。文[4]从理论上指出，如果BBBvVC(w)C(w)C(v)是将BC标准化，那么网络容量可以近似地表示为c1SD，（1）其中S是包括主机在内的所有节点数，0,1是主机密度，ρS表示主机数，主机节点随机地分布在网络中，BsVdsVvR(s,d)1DC(v)S(S1)，集合R(s,d)是从路由表中得到的节点子集。从公式（1）可以看出，在主机数一定的情况下，网络的容量和节点的Betweenness值之间关系密切。因此，我们研究的目的就是希望通过仿真实验，进一步找出网络的静态属性Betweenness值和网络容量之间更直观、更明确的关系。3仿真实验文中仿真方法类似于文[6]中所描述的方法。网络中有N个节点，这里N=1，2，3……。连续的时间过程被等分为离散的、等时间间隔的仿真时钟的推进。在每一个仿真步长内[t,t+1)，N个节点之中的每一个节点最多生成M个数据分组,每个节点生成数据分组是相互独立的。具体方法是每个节点在时刻t生成M个随机数，2006全国复杂网络学术会议（CCCN’06）论文集每个随机数都服从{0，1}均匀分布。在仿真时钟开始推进之前，设置一个阈值P（其值在[0，1]之间）。如果一个节点在时刻t生成的M个随机数中有m个小于或等于该阈值P，则在此时刻该节点生成m个数据分组。在整个仿真过程中单个节点和系统数据分组生成速率V，Vtotal表示为：V=M*PVtotal=N*M*P通过控制参数M和P，可以调节系统数据分组生成速率Vtotal。在仿真试验中，固定参数M，通过调节P的大小来改变Vtotal。当P在[0，1]间变化时，Vtotal在[0，N*M*P]范围内变化。在每个仿真时刻t，到达中间路由节点的数据分组进入缓冲队列的尾部，等待转发。0203874612345626273231304748495051525453343623373539404142454344891011121314151819161721223324252829Fig.1Ascale-freenetwork图1一个scale-free网络对于如图1所示的具有scale-free特征的网络，节点数N=55，图中圆圈里的数字代表节点号，表1按照Betweenness值的降序列出了图中每个节点的Betweenness值，我们按照这种排列方式把节点分为Betweenness值位于前10%的节点、Betweenness值位于前10%到前20%之间的节点，Betweenness值位于前20%到前30%的节点以及Betweenness值排在后70%的节点。图中深色的节点是Betweenness值位于前10%的节点，即Betweenness值属于TOP6的中枢节点。采用上述仿真方法，在NS2仿真平台上进行实验，其中M=1000，Ｐ的初值设为0.05，并以0.001递增，直至系统开始发生拥塞。这时的Vtotal就是网络容量λc，λc=N*M*P，通过2006全国复杂网络学术会议（CCCN’06）论文集做多组实验求出λc的平均值作为网络容量的无偏估计量。表2列出了增加某些捷径路径以后，网络容量的变化情况以及与Betweenness的关系。表中第一列的新增链路表示在原图的基础上增加一条链路，每次增加链路后重做上述仿真实验，例如0--54表示节点号为0和节点号为54的两节点间增加一条连接，考查此时容量平均值和Betweenness的关系。图2则依据表2的数据给出了网络容量和Betweenness的标准差的关系图。Table1TheBetweennessofeachnodeintheFig.1表1图1中每个节点的Betweenness值列表新增链路网络容量平均值Betweenness标准差Betweenness和最短路径长度最短路径上Top6节点数15--496152.1131216292730--115918.03322.1516738430--155917.01317.57166225314--325600.29319.37167344215--505234.24317.29162147338--465160.01322.71163085426--385008.79340.6516466442006全国复杂网络学术会议（CCCN’06）论文集44--534894.35333.971694012449--444723.18333.8