基于BetweennessCentrality提高復(fù)雜網(wǎng)絡(luò)容量方法

1、基于Betweenness Centrality提高復(fù)雜網(wǎng)絡(luò)容量的方法范晶1, 2 秦卓瓊1,2 張國強(qiáng)1,2 張國清1（1. 中國科學(xué)院計算技術(shù)研究所 北京 100080）（2. 中國科學(xué)院研究生院 北京 100080）摘 要：Betweenness Centrality能夠刻畫節(jié)點在網(wǎng)絡(luò)中的重要程度，能夠反映節(jié)點在網(wǎng)絡(luò)中可能承載的網(wǎng)絡(luò)流量。本文引入Betweenness Centrality對網(wǎng)絡(luò)拓?fù)溥M(jìn)行優(yōu)化和擁塞預(yù)測，通過理論分析和仿真實驗，提出在具有scale-free特征的復(fù)雜網(wǎng)絡(luò)中，依據(jù)Betweenness值以及Betweenness的標(biāo)準(zhǔn)差增加一些捷徑路徑的方法，有效平衡中樞節(jié)

2、點的負(fù)載，緩解擁塞狀況，提高網(wǎng)絡(luò)容量。關(guān)鍵詞：Betweenness Centrality，網(wǎng)絡(luò)拓?fù)洌W(wǎng)絡(luò)容量，擁塞，無標(biāo)度網(wǎng)絡(luò)A METHOD FOR IMPROVING COMPLEX NETWORK CAPACITY BASED ON BETWEENNESS CENTRALITYFan Jing1, 2 Qin Zhuoqiong1, 2 Zhang Guoqiang1, 2 Zhang Guoqing1 (1. Institute of Computing Technology, Chinese Academy of Science Beijing 100080) (2. Gradua

3、te University of Chinese Academy of Science Beijing 100080)ABSTRACT: The Betweenness Centrality index is a direct measure of message traffic. High Betweenness Centrality scores indicate that a vertex lies on considerable fractions of shortest paths connecting others and it plays an important role in

4、 the network. The index is introduced here to optimize network topology and identify nodes which are most likely to cause congestion. We propose some methods after theoretical analysis and experiments to add some shortcuts in scale-free networks according to Betweenness and the variation of Betweenn

5、ess. This can balance load among the core nodes, relieve congestion efficiently and increase the capacity of the network substantially. Key words: Betweenness Centrality, network topology, network capacity, congestion, scale-free network1 引言隨著互聯(lián)網(wǎng)的普及和發(fā)展，各種新興的Internet業(yè)務(wù)不斷涌現(xiàn)，上網(wǎng)的計算機(jī)數(shù)和網(wǎng)站數(shù)迅猛增長，在網(wǎng)絡(luò)使用高峰時段，大

6、多數(shù)網(wǎng)絡(luò)都會出現(xiàn)擁塞，服務(wù)質(zhì)量下降。網(wǎng)絡(luò)擁塞受很多因素影響，例如節(jié)點的容量、鏈路的帶寬、網(wǎng)絡(luò)路由協(xié)議還有網(wǎng)絡(luò)拓?fù)?。為了獲得令人滿意的服務(wù)質(zhì)量，緩解擁塞狀況，大多數(shù)網(wǎng)絡(luò)運(yùn)營決策人員會選擇擴(kuò)容或者更換網(wǎng)絡(luò)設(shè)備，而很少嘗試對已有的網(wǎng)絡(luò)拓?fù)渥餍┬⌒〉母淖儊硖岣呔W(wǎng)絡(luò)性能1。而事實上系統(tǒng)的動態(tài)特征（網(wǎng)絡(luò)流量）和網(wǎng)絡(luò)的靜態(tài)結(jié)構(gòu)（網(wǎng)絡(luò)拓?fù)洌╆P(guān)系非常密切2，網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)是影響網(wǎng)絡(luò)負(fù)載分布的主要因素之一。Betweenness Centrality（簡稱Betweenness）的概念源于分析社會網(wǎng)絡(luò)中個體的重要性3。簡單地講，一個節(jié)點的Betweenness表示所有的節(jié)點對之間通過該節(jié)點的最短路徑條數(shù)。Betwe

7、enness很好地描述了一個網(wǎng)絡(luò)中節(jié)點可能需要承載的流量。一個節(jié)點的Betweenness越大，流經(jīng)它的數(shù)據(jù)分組越多，意味著它更容易擁塞，成為網(wǎng)絡(luò)的瓶頸。在早期的網(wǎng)絡(luò)拓?fù)淠Ｐ偷难芯恐校W(wǎng)絡(luò)拓?fù)淠Ｐ屯ǔ２捎猛耆S機(jī)圖模型，認(rèn)為網(wǎng)絡(luò)中的節(jié)點度大致相同，呈正態(tài)分布。近期的研究表明Internet的網(wǎng)絡(luò)節(jié)點度呈冪律分布，具有這種特征的網(wǎng)絡(luò)就被稱之為無標(biāo)度（scale-free）網(wǎng)絡(luò)。大多數(shù)節(jié)點度較小，而一小部分節(jié)點則節(jié)點度很大，通常稱之為中樞節(jié)點。中樞節(jié)點的Betweenness就往往很大，一旦中樞節(jié)點崩潰，整個網(wǎng)絡(luò)就面臨癱瘓的危險，所以平衡整個網(wǎng)絡(luò)的流量來提高系統(tǒng)容量對符合scale-free特征的

8、網(wǎng)絡(luò)尤為必要。文1中指出在度分布具有Bi-Modal特征、拓?fù)浣Y(jié)構(gòu)較為規(guī)則的網(wǎng)絡(luò)中，單單增加這類Betweenness較大的節(jié)點的容量只能很小程度地減小擁塞，要想有效地避免擁塞，必須大幅度增大節(jié)點容量，而這必然花費相當(dāng)高的成本。然而在Betweenness較大的前5個節(jié)點間增加連接，同時適當(dāng)增加節(jié)點的容量，則會大幅度提高網(wǎng)絡(luò)容量，如果在Betweenness較大的前5個節(jié)點和隨機(jī)選擇的其它的節(jié)點間增加連接，則容量提高得更多。但是對于scale-free網(wǎng)絡(luò)來說，給Betweenness較大的前5個節(jié)點增加連接對于原本負(fù)載就很重的中樞節(jié)點，簡直就是雪上加霜。緩解中樞節(jié)點的壓力比單純提高網(wǎng)絡(luò)容量更

9、為重要。本文以基于Barabási -Albert(BA)算法構(gòu)造的scale-free網(wǎng)絡(luò)為模型，研究在最短路由算法下此類網(wǎng)絡(luò)的容量問題。通過理論分析和實驗仿真，提出依據(jù)Betweenness的值和標(biāo)準(zhǔn)差，增加盡可能少的捷徑路徑，改善中樞節(jié)點的擁塞狀況，提高網(wǎng)絡(luò)容量的方法，對網(wǎng)絡(luò)運(yùn)營決策人員進(jìn)行容量分析和規(guī)劃有實際指導(dǎo)意義。 2基于Betweenness Centrality的網(wǎng)絡(luò)容量分析當(dāng)網(wǎng)絡(luò)負(fù)載很低的時候，轉(zhuǎn)發(fā)節(jié)點的緩沖隊列較空，這時，數(shù)據(jù)分組的平均端到端時延近似的和分組經(jīng)過的平均節(jié)點數(shù)成比例4。當(dāng)加大負(fù)載，轉(zhuǎn)發(fā)節(jié)點的隊列開始增加，平均時延也相應(yīng)增加。當(dāng)負(fù)載更進(jìn)一步加重，達(dá)到一

10、個臨界值c，某些節(jié)點的緩沖隊列將增長很快，數(shù)據(jù)分組平均時延陡增，網(wǎng)絡(luò)性能惡化。這時，認(rèn)為網(wǎng)絡(luò)發(fā)生了擁塞，網(wǎng)絡(luò)的吞吐量由升轉(zhuǎn)降，而c就定義為網(wǎng)絡(luò)的容量。通信網(wǎng)絡(luò)可以用圖G=（V，E）來表示，其中V代表節(jié)點（頂點）集，E代表鏈路（邊）集。主機(jī)、路由器和交換機(jī)在圖中用節(jié)點（頂點）來表示，它們之間的物理連接則用鏈路（邊）來表示。本文只考慮連通無向圖。如果記圖中任意兩點s,d之間的最短路徑條數(shù)為，而這些最短路徑中經(jīng)過節(jié)點w的條數(shù)為，那么節(jié)點s,d之間經(jīng)過w的最短路徑條數(shù)占s,d間總的最短路徑條數(shù)的比例為， 在此基礎(chǔ)上，節(jié)點w的Betweenness Centrality定義為：一個節(jié)點的越大，它就顯得越

11、重要，因為大量的數(shù)據(jù)分組將流經(jīng)它，它的負(fù)載將很重。因此，這種類型的節(jié)點在設(shè)計時需要更大的數(shù)據(jù)處理速率，連接的鏈路也需要更大的帶寬容量5。Scale-free網(wǎng)絡(luò)的中樞節(jié)點通常是數(shù)據(jù)傳輸中使用率很高的節(jié)點，因此會很大。文4從理論上指出，如果 是將標(biāo)準(zhǔn)化，那么網(wǎng)絡(luò)容量可以近似地表示為 ， （1）其中S是包括主機(jī)在內(nèi)的所有節(jié)點數(shù)，是主機(jī)密度，S表示主機(jī)數(shù)，主機(jī)節(jié)點隨機(jī)地分布在網(wǎng)絡(luò)中，集合R(s,d)是從路由表中得到的節(jié)點子集。從公式（1）可以看出，在主機(jī)數(shù)一定的情況下，網(wǎng)絡(luò)的容量和節(jié)點的Betweenness值之間關(guān)系密切。因此，我們研究的目的就是希望通過仿真實驗，進(jìn)一步找出網(wǎng)絡(luò)的靜態(tài)屬性Betwe

12、enness值和網(wǎng)絡(luò)容量之間更直觀、更明確的關(guān)系。3仿真實驗 文中仿真方法類似于文6中所描述的方法。網(wǎng)絡(luò)中有N個節(jié)點，這里N=1，2，3。連續(xù)的時間過程被等分為離散的、等時間間隔的仿真時鐘的推進(jìn)。在每一個仿真步長內(nèi)t,t+1)，N個節(jié)點之中的每一個節(jié)點最多生成M個數(shù)據(jù)分組,每個節(jié)點生成數(shù)據(jù)分組是相互獨立的。具體方法是每個節(jié)點在時刻t生成M個隨機(jī)數(shù)，每個隨機(jī)數(shù)都服從0，1均勻分布。在仿真時鐘開始推進(jìn)之前，設(shè)置一個閾值P（其值在0，1之間）。如果一個節(jié)點在時刻t生成的M個隨機(jī)數(shù)中有m個小于或等于該閾值P，則在此時刻該節(jié)點生成m個數(shù)據(jù)分組。在整個仿真過程中單個節(jié)點和系統(tǒng)數(shù)據(jù)分組生成速率V，Vtota

13、l 表示為：V=M*P Vtotal=N*M*P通過控制參數(shù)M和P，可以調(diào)節(jié)系統(tǒng)數(shù)據(jù)分組生成速率Vtotal。在仿真試驗中，固定參數(shù)M，通過調(diào)節(jié)P的大小來改變Vtotal。當(dāng)P在0，1間變化時，Vtotal在0，N*M*P范圍內(nèi)變化。在每個仿真時刻t，到達(dá)中間路由節(jié)點的數(shù)據(jù)分組進(jìn)入緩沖隊列的尾部，等待轉(zhuǎn)發(fā)。Fig. 1 A scale-free network圖 1一個scale-free網(wǎng)絡(luò)對于如圖1所示的具有scale-free特征的網(wǎng)絡(luò)，節(jié)點數(shù)N=55，圖中圓圈里的數(shù)字代表節(jié)點號，表1按照Betweenness值的降序列出了圖中每個節(jié)點的Betweenness值，我們按照這種排列方式把節(jié)

14、點分為Betweenness值位于前10%的節(jié)點、Betweenness值位于前10%到前20%之間的節(jié)點，Betweenness值位于前20%到前30%的節(jié)點以及Betweenness值排在后70%的節(jié)點。圖中深色的節(jié)點是Betweenness值位于前10%的節(jié)點，即Betweenness值屬于TOP6的中樞節(jié)點。采用上述仿真方法，在NS2仿真平臺上進(jìn)行實驗，其中M=1000，的初值設(shè)為0.05，并以0.001遞增，直至系統(tǒng)開始發(fā)生擁塞。這時的Vtotal就是網(wǎng)絡(luò)容量c，c =N*M*P，通過做多組實驗求出c的平均值作為網(wǎng)絡(luò)容量的無偏估計量。表2列出了增加某些捷徑路徑以后，網(wǎng)絡(luò)容量的變化情況

15、以及與Betweenness的關(guān)系。表中第一列的新增鏈路表示在原圖的基礎(chǔ)上增加一條鏈路，每次增加鏈路后重做上述仿真實驗，例如0-54表示節(jié)點號為0和節(jié)點號為54的兩節(jié)點間增加一條連接，考查此時容量平均值和Betweenness的關(guān)系。圖2則依據(jù)表2的數(shù)據(jù)給出了網(wǎng)絡(luò)容量和Betweenness的標(biāo)準(zhǔn)差的關(guān)系圖。 Table 1 The Betweenness of each node in the Fig.1表1 圖1中每個節(jié)點的Betweenness值列表新增鏈路網(wǎng)絡(luò)容量平均值Betweenness標(biāo)準(zhǔn)差Betweenness和最短路徑長度最短路徑上Top6節(jié)點數(shù)15-496152.11 31

16、216292730-115918.03 322.1516738430-155917.01 317.57166225314-325600.29 319.37167344215-505234.24 317.29162147338-465160.01 322.71163085426-385008.79 340.65164664444-534894.35 333.971694012449-444723.18 333.89168649432-414563.41 328.74166305320-384452.93 358.991622833原圖4331.93 362.2717432-20-544320.3

17、4 357.5162946220-524318.12 356.916040520-444092.04 338.216928840-543904.00 355.1516706830-523142.95 354.2616580737-15872.54 364.3717164217-38870.70 372.361680832Table 2 The relation between the network capacity and nodes Betweenness表2 網(wǎng)絡(luò)容量與節(jié)點的Betweenness關(guān)系表 Fig. 2 The relation between the Variation

18、of Betweenness and network capacity圖2 Betweenness的標(biāo)準(zhǔn)差和網(wǎng)絡(luò)容量關(guān)系圖從以上的圖表可以看出：(1) 網(wǎng)絡(luò)節(jié)點的Betweenness的標(biāo)準(zhǔn)差與網(wǎng)絡(luò)容量關(guān)系緊密。從圖2 我們可以明顯看出，網(wǎng)絡(luò)節(jié)點的Betweenness的標(biāo)準(zhǔn)差越小，網(wǎng)絡(luò)容量越大。網(wǎng)絡(luò)節(jié)點的Betweenness的標(biāo)準(zhǔn)差小，說明網(wǎng)絡(luò)負(fù)載較為均衡，瓶頸節(jié)點出現(xiàn)的概率小，因此發(fā)生網(wǎng)絡(luò)擁塞的概率變小，從而網(wǎng)絡(luò)容量變大。(2) 網(wǎng)絡(luò)節(jié)點的Betweenness的和與網(wǎng)絡(luò)容量沒有明顯關(guān)系。(3) 選擇新增連接的兩點之間的最短路徑長度與網(wǎng)絡(luò)容量沒有明顯的關(guān)系，但是在其他因素相同的情況下，最

19、短路徑長度越長，對容量改進(jìn)效果越明顯。(4) 容量增加顯著的網(wǎng)絡(luò)拓?fù)溆兄粋€共性：選擇連接的兩點之間的最短路徑上，有著較多的Betweenness值位于TOP 6 的節(jié)點，即Betweenness值位于前10%的節(jié)點。當(dāng)兩個節(jié)點之間的最短路徑經(jīng)過較多個Betweenness值位于前10%的節(jié)點時，可以考慮在它們之間增加鏈路，以緩解網(wǎng)絡(luò)擁塞。然而，并不是在最短路徑上有著更多的Betweenness值位于前10%的節(jié)點的節(jié)點對之間增加鏈路，就能更多地提高網(wǎng)絡(luò)容量。(5) 在Betweenness值位于前10%到前20%之間的節(jié)點之間增加連接往往能最大幅度提高網(wǎng)絡(luò)容量。表1中新增連接后容量最大的前五

20、種情況中就有四種是在這樣的節(jié)點間增加的連接。因為具有這種特征的節(jié)點在網(wǎng)絡(luò)中屬于次中樞節(jié)點，重要性也較高，網(wǎng)絡(luò)中不少的流量要經(jīng)過它們，但同時它們的負(fù)載又不是很重，所以增加連接后即能為整個網(wǎng)絡(luò)分流，又不至于本身的負(fù)載過重，有利于網(wǎng)絡(luò)容量的提高。在以基于Barabási -Albert(BA)算法構(gòu)造的其它較大規(guī)模的scale-free網(wǎng)絡(luò)中，進(jìn)行上述同樣的實驗，也能得到類似的結(jié)論。4提高復(fù)雜網(wǎng)絡(luò)容量的方法根據(jù)文7中的算法，可以計算出網(wǎng)絡(luò)中各個節(jié)點的Betweenness值，找到中樞節(jié)點。然后依據(jù)以上的實驗結(jié)果，在節(jié)點間增加一些鏈路，以提高網(wǎng)絡(luò)容量?；痉椒ㄈ缦拢?1) 在網(wǎng)絡(luò)規(guī)模不大（節(jié)

21、點數(shù)很小）的情況下，可以窮盡所有節(jié)點對之間增加鏈路的情況，每次在不存在連接的兩點間新增一條連接，找到使得Betweenness的標(biāo)準(zhǔn)差最小的連接方式，它能最大程度提高網(wǎng)絡(luò)容量；(2) 在網(wǎng)絡(luò)規(guī)模較大的情況下，無法窮盡所有節(jié)點對之間增加鏈路的情況，或者只需要得到一個較優(yōu)方案，沒必要窮盡所有節(jié)點對之間增加鏈路的情況時，可以選擇在網(wǎng)絡(luò)中不存在連接的且對提高網(wǎng)絡(luò)容量影響大的兩個節(jié)點之間增加一條邊。當(dāng)網(wǎng)絡(luò)中所有節(jié)點的Betweenness值按照由大到小的順序排成一個序列時，所述對提高網(wǎng)絡(luò)容量影響大的節(jié)點為：Betweenness值位于所述序列中排在前10至前20范圍內(nèi)的節(jié)點。在滿足上述條件的節(jié)點中，選擇

22、兩點間最短路徑經(jīng)過較多的Betweenness值排在前10的節(jié)點的節(jié)點對，在這樣的節(jié)點對之間加一條邊，除了這兩個節(jié)點的Betweenness值會大幅增加外，其他大多數(shù)中樞節(jié)點的負(fù)載會大幅下降，尤其對Betweenness值排在前10的節(jié)點的改善很明顯，總體容量也能較大提高；(3) 對按(1)或(2)中的方法增加鏈路后的網(wǎng)絡(luò)，重新計算各個節(jié)點的Betweenness值以及整個網(wǎng)絡(luò)Betweenness的標(biāo)準(zhǔn)差，可以從理論上分析每個節(jié)點負(fù)載的變化和網(wǎng)絡(luò)容量的變化；(4) 根據(jù)上述優(yōu)選方案，進(jìn)行實驗仿真或者實際測試，并結(jié)合實際情況，比如兩點之間的實際距離、增加鏈路的費用以及網(wǎng)絡(luò)拓?fù)洳渴鸬牟呗缘纫蛩兀?/p>

23、最終確定合理的優(yōu)化方案。5結(jié)論隨著復(fù)雜網(wǎng)絡(luò)研究的興起，Betweenness Centrality被廣泛用在大規(guī)模網(wǎng)絡(luò)拓?fù)涞姆治鲋?。由于它能夠刻畫不同?jié)點或邊在網(wǎng)絡(luò)中的重要程度，能夠很好地描述一個網(wǎng)絡(luò)中節(jié)點或鏈路可能需要承載的流量，因此本文引入Betweenness Centrality來進(jìn)行網(wǎng)絡(luò)容量分析。對于像Internet這樣具有scale-free特征的網(wǎng)絡(luò)，節(jié)點的重要程度差別很大，少數(shù)中樞節(jié)點成為制約網(wǎng)絡(luò)容量的瓶頸。本文首先進(jìn)行了理論分析，而后通過仿真實驗得出了Betweenness和網(wǎng)絡(luò)容量的關(guān)系，提出通過增加捷徑路徑來平衡中樞節(jié)點的負(fù)載，提高網(wǎng)絡(luò)容量的有效而易于操作的方法。下一步

24、工作將深入考查Betweenness和網(wǎng)絡(luò)容量之間定量的關(guān)系，并考慮復(fù)雜網(wǎng)絡(luò)更多的特征，進(jìn)一步研究網(wǎng)絡(luò)拓?fù)涞撵o態(tài)屬性和網(wǎng)絡(luò)容量的關(guān)系。參考文獻(xiàn)1. Neelima Gupte, Brajendra K. Singh. Role of connectivity in congestion and decongestion in networks. the Proceedings of the 3rd International Conference NEXT-SigmaPhi. 2005.92. Petter Holme. Congestion and centrality in traffic flow on complex networks. Advances in Complex Systems 6, 163-176 (2003).3. L