張 姣,劉三陽，白藝光

(西安電子科技大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院,西安 710126)

0 引言

受到上述研究的啟發(fā)，在本文中，我們提出了一種新的基于社團(tuán)結(jié)構(gòu)組合網(wǎng)絡(luò)特征信息的鏈路重連策略，即CCLS策略。該策略在社團(tuán)結(jié)構(gòu)基礎(chǔ)上,依據(jù)節(jié)點(diǎn)間的同配與異配程度和k-core結(jié)構(gòu)對(duì)網(wǎng)絡(luò)進(jìn)行重連邊。其分別在偽隨機(jī)網(wǎng)絡(luò)、CWS小世界網(wǎng)絡(luò)、無標(biāo)度社團(tuán)網(wǎng)絡(luò)以及真實(shí)網(wǎng)絡(luò)上進(jìn)行的仿真實(shí)驗(yàn)表明，它能有效地減弱網(wǎng)絡(luò)社團(tuán)特性,提高網(wǎng)絡(luò)傳輸容量。

1 相關(guān)模型與參數(shù)

1.1 流量模型

假定:網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)都有創(chuàng)建,接收和轉(zhuǎn)發(fā)數(shù)據(jù)包的能力,并且每個(gè)節(jié)點(diǎn)的存儲(chǔ)都是無限制的。每個(gè)時(shí)刻t，每個(gè)節(jié)點(diǎn)以概率ρ產(chǎn)生一個(gè)數(shù)據(jù)包，每個(gè)數(shù)據(jù)包隨機(jī)選擇與初始節(jié)點(diǎn)不同的目的節(jié)點(diǎn)，另外每個(gè)節(jié)點(diǎn)對(duì)數(shù)據(jù)包的處理能力都相同設(shè)置為C，新到達(dá)的數(shù)據(jù)包根據(jù)排隊(duì)機(jī)制放在隊(duì)列的末尾，不能及時(shí)處理的數(shù)據(jù)包排在隊(duì)列末尾等候，節(jié)點(diǎn)依據(jù)First-in-First-out原則對(duì)數(shù)據(jù)包進(jìn)行處理。數(shù)據(jù)包到達(dá)目的節(jié)點(diǎn)后就從網(wǎng)絡(luò)中離開。

1.2 網(wǎng)絡(luò)傳輸

當(dāng)網(wǎng)絡(luò)中節(jié)點(diǎn)產(chǎn)生數(shù)據(jù)包的概率ρ逐漸增加時(shí)，網(wǎng)絡(luò)將由暢通逐漸變?yōu)閾砣?。這個(gè)過程存在一個(gè)臨界值ρc，當(dāng)ρ<ρc時(shí),網(wǎng)絡(luò)產(chǎn)生的數(shù)據(jù)包小于節(jié)點(diǎn)的處理能力,數(shù)據(jù)包無堆積，網(wǎng)絡(luò)暢通；當(dāng)ρ>ρc時(shí),網(wǎng)絡(luò)產(chǎn)生的數(shù)據(jù)包超過節(jié)點(diǎn)的處理能力，數(shù)據(jù)包不能被及時(shí)傳輸而堆積,網(wǎng)絡(luò)擁塞。為了準(zhǔn)確描述從暢通狀態(tài)到擁塞狀態(tài)的臨界點(diǎn),可引入有序參數(shù)η與ρ的關(guān)系來分析網(wǎng)絡(luò)變化。

(1)

其中，N為網(wǎng)絡(luò)的節(jié)點(diǎn)個(gè)數(shù)，ΔW=W(t+Δt)-W(t)，W(t)為t時(shí)刻網(wǎng)絡(luò)中數(shù)據(jù)包的個(gè)數(shù)，〈ΔW〉表示對(duì)時(shí)間窗口Δt對(duì)應(yīng)的ΔW求平均。當(dāng)ρ<ρc時(shí)，ΔW=0和η=0，網(wǎng)絡(luò)處于暢通狀態(tài)；當(dāng)ρ>ρc時(shí)，序參數(shù)變?yōu)檎?，網(wǎng)絡(luò)中的數(shù)據(jù)包發(fā)生堆積,網(wǎng)絡(luò)處于擁塞狀態(tài)。因此，可以用ρc來量化網(wǎng)絡(luò)傳輸容量。

在網(wǎng)絡(luò)暢通狀態(tài)，任意節(jié)點(diǎn)vj接收到的數(shù)據(jù)包為ρBj/(N-1),其中Bj是節(jié)點(diǎn)vj的有效介數(shù)，定義如下：

(2)

nil表示節(jié)點(diǎn)vi→vl的最短路徑條數(shù)；nil(j)表示經(jīng)過節(jié)點(diǎn)vj的vi→vl的最短路徑的條數(shù)。如果ρBj/(N-1)>C,那么數(shù)據(jù)包將在節(jié)點(diǎn)vj上堆積,網(wǎng)絡(luò)將會(huì)發(fā)生擁塞。因此,要想網(wǎng)絡(luò)不發(fā)生擁塞,必須保證網(wǎng)絡(luò)所有節(jié)點(diǎn)都不發(fā)生數(shù)據(jù)包堆積,即它們都滿足ρBj/(N-1)

(3)

其中，Bmax表示網(wǎng)絡(luò)節(jié)點(diǎn)介數(shù)的最大值。

令C=1，網(wǎng)絡(luò)傳輸容量ρc即為網(wǎng)絡(luò)不發(fā)生擁塞的最大ρ值,可以用下邊公式估計(jì)：

ρc=(N-1)/Bmax

(4)

1.3 社團(tuán)劃分的評(píng)價(jià)

社團(tuán)是網(wǎng)絡(luò)的一種中尺度結(jié)構(gòu)，本文我們采用Newman等人提出的模塊度Q來量化復(fù)雜網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)的質(zhì)量，把初始網(wǎng)絡(luò)劃分成k個(gè)社團(tuán)，E=(eij)是k階對(duì)稱矩陣。模塊度Q可以定義為:

(5)

2 策略分析

實(shí)際生活中多數(shù)網(wǎng)絡(luò)具有明顯的社團(tuán)結(jié)構(gòu),且明顯的社團(tuán)結(jié)構(gòu)不利于網(wǎng)絡(luò)傳輸。因此，本文鏈路重連策略在對(duì)網(wǎng)絡(luò)劃分社團(tuán)結(jié)構(gòu)的基礎(chǔ)上，利用節(jié)點(diǎn)間度度相關(guān)性，核心-外圍結(jié)構(gòu)等特征信息來模糊社團(tuán)結(jié)構(gòu)進(jìn)而提高網(wǎng)絡(luò)傳輸容量。

表1 算法1

需要注意的是每次刪邊和添邊后，如果都重新對(duì)網(wǎng)絡(luò)劃分社團(tuán)結(jié)構(gòu)，計(jì)算量龐大，為簡化計(jì)算，刪除邊時(shí)，若節(jié)點(diǎn)i與它所在的社團(tuán)沒有相連接的節(jié)點(diǎn)，對(duì)節(jié)點(diǎn)i按照社團(tuán)對(duì)它的吸引力(吸引力是按照節(jié)點(diǎn)i與其他社團(tuán)的連接度，度越大則吸引力越大)重新劃分社團(tuán)；添邊時(shí)采用文章WCS策略[15]的命題3來重新規(guī)劃節(jié)點(diǎn)u和v的社團(tuán)歸屬。

在本文的鏈路重連策略中，要保證網(wǎng)絡(luò)的連通性，如果刪除一條邊將導(dǎo)致某些節(jié)點(diǎn)斷開連接，我們將不會(huì)將其刪除并繼續(xù)處理下一條邊。重連邊的比例被定義為：fc=mr/m，其中mr是重連邊的數(shù)目，m是初始網(wǎng)絡(luò)中的總邊數(shù)。(本文的仿真結(jié)果數(shù)值都至少進(jìn)行了20次獨(dú)立重復(fù)實(shí)驗(yàn))

3 試驗(yàn)結(jié)果與分析

3.1 在偽隨機(jī)網(wǎng)絡(luò)中的驗(yàn)證

在基于ER[23]模型生成的偽隨機(jī)網(wǎng)絡(luò)上分析CCLS策略對(duì)其傳輸性能的影響。該網(wǎng)絡(luò)的產(chǎn)生方式如下：1)網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)n=128，隨機(jī)均分成4個(gè)社團(tuán)。2)同一社團(tuán)內(nèi)兩節(jié)點(diǎn)對(duì)以概率Pin連接，不同社團(tuán)間兩節(jié)點(diǎn)對(duì)以概率Pout連接。3)社團(tuán)內(nèi)部平均連接度為Zin，社團(tuán)間平均連接度為Zout，且Zin+Zout=16。選擇合適參數(shù)生成模塊度Q=0.625和Q=0.5的網(wǎng)絡(luò)，分別標(biāo)記為Net1和Net2，Net2的社團(tuán)特性比Net1的弱。應(yīng)用CCLS策略，重連鏈路比例fc與網(wǎng)絡(luò)傳輸容量ρc之間的關(guān)系如圖1a所示，兩個(gè)網(wǎng)絡(luò)的傳輸容量ρc都得到提升?；?.2(4)的分析，網(wǎng)絡(luò)傳輸容量可以簡化為ρc∝1/Bmax,因此，理論上網(wǎng)絡(luò)的最大介數(shù)Bmax可以用來評(píng)估網(wǎng)絡(luò)的傳輸能力。圖1b顯示了Bmax與重連鏈路比例fc的關(guān)系，由圖可得，隨著fc的增加，網(wǎng)絡(luò)的最大介數(shù)Bmax在兩個(gè)網(wǎng)絡(luò)上都逐漸減小，這正說明網(wǎng)絡(luò)負(fù)載傳輸能力在不斷提升。由此可見，CCLS策略對(duì)偽隨機(jī)網(wǎng)絡(luò)的負(fù)載傳輸能力改善效果明顯。最后圖1c表明了網(wǎng)絡(luò)模塊度Q隨著fc的增加在不斷減小，說明CCLS策略能明顯削弱網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)，a和c證實(shí)了模糊社團(tuán)結(jié)構(gòu)有利于網(wǎng)絡(luò)負(fù)載容量傳輸。并且隨著fc的增加，Net1網(wǎng)絡(luò)ρc的提升以及Bmax和Q的下降都略快于Net2網(wǎng)絡(luò)。因此，在偽隨機(jī)網(wǎng)絡(luò)上，CCLS策略能有效改善網(wǎng)絡(luò)擁擠，提高網(wǎng)絡(luò)傳輸容量，且對(duì)社團(tuán)明顯的Net1網(wǎng)絡(luò)的改善效果稍稍優(yōu)于Net2網(wǎng)絡(luò)，但是效果不明顯。

圖1 在偽隨機(jī)網(wǎng)絡(luò)上,CCLS策略下ρcBmax以及Q與fc的關(guān)系Fig.1 On the pseudo-random network,ρcBmax and Q versus fc under the CCLS strategy

3.2 在CWS小世界網(wǎng)絡(luò)中的驗(yàn)證

CWS[24]模型構(gòu)造算法：1)網(wǎng)絡(luò)有N個(gè)節(jié)點(diǎn)，包含c個(gè)社團(tuán)，初始時(shí)N/c個(gè)節(jié)點(diǎn)排成環(huán)，每個(gè)節(jié)點(diǎn)選擇離它最近的K/2個(gè)節(jié)點(diǎn)連接，各社團(tuán)首尾之間連接一條邊；2)重連概率P=Pin+Pout，其中Pin表示社團(tuán)內(nèi)部重連概率，Pout表示社團(tuán)之間重連概率；它們也分別表示社團(tuán)內(nèi)部重連邊和社團(tuán)間重連邊的比例。

調(diào)整CWS模型的參數(shù)，分別生成Q=0.7和Q=0.55節(jié)點(diǎn)N=800的社團(tuán)網(wǎng)絡(luò),分別標(biāo)記為CWS1和CWS2。比較CCLS策略對(duì)兩個(gè)社團(tuán)網(wǎng)絡(luò)CWS1和CWS2的影響，其中包括重連邊比例fc分別與網(wǎng)絡(luò)傳輸容量(ρc),網(wǎng)絡(luò)節(jié)點(diǎn)的最大介數(shù)(Bmax)以及網(wǎng)絡(luò)社團(tuán)模塊度(Q)的關(guān)系。從圖2a、c可得，兩個(gè)網(wǎng)絡(luò)隨著重連邊比例fc的增加，網(wǎng)絡(luò)傳輸容量ρc都在提升，模塊度Q都在減小。由此可以說明，CCLS策略能有效模糊社團(tuán)結(jié)構(gòu)進(jìn)而改善CWS網(wǎng)絡(luò)的傳輸容量。從圖2b最大介數(shù)Bmax的明顯變化可看出，社團(tuán)較強(qiáng)的CWS1網(wǎng)絡(luò)的最大介數(shù)下降的快于CWS2網(wǎng)絡(luò)，因此CCLS策略對(duì)社團(tuán)較強(qiáng)的CWS1網(wǎng)絡(luò)容量傳輸性能的改善效果略好于CWS2網(wǎng)絡(luò)。

圖2 在CWS網(wǎng)絡(luò)上,CCLS策略下ρcBmax以及Q與fc的關(guān)系Fig.2 On the CWS network,ρcBmax and Q versus fc under the CCLS strategy

圖3 CWS網(wǎng)絡(luò)節(jié)點(diǎn)N=500，fc=0.15時(shí)，rρ與Q的關(guān)系Fig.3 rρ versus Q under the CWS network N=500 and fc=0.15

3.3 在無標(biāo)度社團(tuán)網(wǎng)絡(luò)上的驗(yàn)證

在基于BA模型生成的無標(biāo)度社團(tuán)SFC[25]和CBEN[26]網(wǎng)絡(luò)上的分析：調(diào)整兩個(gè)模型的參數(shù)，分別生成Q值為0.69的N=500的SFC網(wǎng)絡(luò)和Q值為0.65的N=500的CBEN網(wǎng)絡(luò)。將我們的鏈路重連策略CCLS分別和基于社團(tuán)結(jié)構(gòu)的其他3種鏈路重連策略進(jìn)行比較，3種策略如下：

1)社團(tuán)隨機(jī)重連策略(CRR)：在社團(tuán)內(nèi)部隨機(jī)刪除鏈路，社團(tuán)間隨機(jī)增加鏈路。

2)社團(tuán)介數(shù)重連策略(CBR)：在最大社團(tuán)內(nèi)刪除高介數(shù)節(jié)點(diǎn)間的鏈路ω=Bi×Bj，增加最低介數(shù)節(jié)點(diǎn)與非其所在最大社團(tuán)間的低介數(shù)節(jié)點(diǎn)間的鏈路ω=Bi×Bj。其中Bi，Bj分別表示節(jié)點(diǎn)i和j的介數(shù)。

3)社團(tuán)度重連策略(CDR)：在最大社團(tuán)內(nèi)刪除高度節(jié)點(diǎn)間的鏈路ω=ki×kj，增加最低度節(jié)點(diǎn)與非其所在最大社團(tuán)間的低度節(jié)點(diǎn)間的鏈路ω=ki×kj。其中ki，kj分別表示節(jié)點(diǎn)i和j的度。

ρc和Bmax與fc的關(guān)系如圖4的a和b，c和d所示，隨著重連邊比例fc的提升，四種鏈路重連策略下，網(wǎng)絡(luò)傳輸容量ρc都得到提高，分析其原因，CCLS，CBR，CDR策略下，根據(jù)無標(biāo)度網(wǎng)絡(luò)的社團(tuán)特性，社團(tuán)內(nèi)節(jié)點(diǎn)聚集，邊稠密，其內(nèi)部Hub節(jié)點(diǎn)非常容易發(fā)生擁塞，因此，在社團(tuán)內(nèi)刪除負(fù)載較重節(jié)點(diǎn)間的連邊，那么許多數(shù)據(jù)包就不會(huì)到達(dá)這些Hub節(jié)點(diǎn)，前往非Hub節(jié)點(diǎn)，這樣利用非Hub節(jié)點(diǎn)緩解了社團(tuán)內(nèi)Hub節(jié)點(diǎn)的擁塞。其次社團(tuán)間的連邊作為橋梁，到達(dá)的數(shù)據(jù)包較多，負(fù)載較重，因此造成擁塞的節(jié)點(diǎn)一般是這些橋梁的兩端，我們?cè)谏鐖F(tuán)間選擇負(fù)載較小的節(jié)點(diǎn)進(jìn)行連邊，利用這些連邊，可以分擔(dān)原始網(wǎng)絡(luò)中社團(tuán)間橋梁的負(fù)載，這樣削弱了社團(tuán)結(jié)構(gòu)，同時(shí)提高了網(wǎng)絡(luò)對(duì)數(shù)據(jù)包的傳輸能力。而CRR策略根據(jù)模糊社團(tuán)結(jié)構(gòu)有利于網(wǎng)絡(luò)傳輸?shù)奶匦?，其在社團(tuán)內(nèi)刪除鏈路，在社團(tuán)間進(jìn)行隨機(jī)重連來削弱社團(tuán)結(jié)構(gòu)進(jìn)而提高了網(wǎng)絡(luò)傳輸容量。圖4整體顯示，隨著fc的增加,這四種鏈路重連策略均能模糊社團(tuán)結(jié)構(gòu)來提高網(wǎng)絡(luò)負(fù)載能力，并且當(dāng)fc=0.25時(shí)，對(duì)SFC網(wǎng)絡(luò)傳輸容量的改善能力CCLS>CBR>CDR>CRR；對(duì)CBEN網(wǎng)絡(luò)傳輸容量的改善能力CCLS>CDR>CBR>CRR。

圖4 在不同鏈路重連策略下ρcBmax以及Q與fc的關(guān)系Fig.4 ρcBmax and Q versus fc under different link rewiring strategies

圖5 SFC網(wǎng)絡(luò)節(jié)點(diǎn)N=500，fc=0.15時(shí)，rρ與Q的關(guān)系Fig.5 rρ versus Q under SFC network N=500 and fc=0.15

下面分析CCLS策略分別對(duì)不同模塊度的SFC和CBEN網(wǎng)絡(luò)傳輸容量的影響，如圖5所示，SFC網(wǎng)絡(luò)節(jié)點(diǎn)N=500，平均度k=14,調(diào)整其參數(shù)分別生成不同的模塊度值Q，在重連邊比例fc=0.15的情況下，我們發(fā)現(xiàn)社團(tuán)結(jié)構(gòu)越明顯，CCLS策略對(duì)其傳輸容量的改善效果越好。

從圖6我們分別生成Q=0.7(標(biāo)記為CBEN1)和Q=0.55(標(biāo)記為CBEN2)N=1 000的兩個(gè)CBEN網(wǎng)絡(luò)。利用CCLS策略，兩個(gè)網(wǎng)絡(luò)的傳輸容量ρc都得到提升，但是隨著重連邊比例fc的增加，CBEN1網(wǎng)絡(luò)的ρc值提升快于CBEN2網(wǎng)絡(luò)，并且CBEN1網(wǎng)絡(luò)的Bmax的減少快于CBEN2網(wǎng)絡(luò)，圖6c顯示，CCLS策略明顯減弱了網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)，且社團(tuán)結(jié)構(gòu)越明顯，減弱的也相對(duì)越快。因此，以上結(jié)果顯示CCLS策略對(duì)社團(tuán)特征相對(duì)較強(qiáng)的CBEN1的網(wǎng)絡(luò)傳輸容量改善能力優(yōu)于CBEN2。由此可見，在無標(biāo)度社團(tuán)網(wǎng)絡(luò)中，網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)越強(qiáng)，CCLS策略對(duì)網(wǎng)絡(luò)傳輸性能的改善效果也相對(duì)越好。

圖6 在CBEN網(wǎng)絡(luò)上，CCLS策略下ρcBmax以及Q與fc的關(guān)系Fig.6 On the CBEN network,ρcB max and Q versus fc under the CCLS strategy

圖7 在CCLS策略下ρc與fc的關(guān)系Fig.7 ρc versus fc under the CCLS strategy

最后在真實(shí)的US Air lines(來自于Pajek datasets)節(jié)點(diǎn)數(shù)332,邊數(shù)2 126網(wǎng)絡(luò)上的驗(yàn)證：在CCLS策略下,首先利用Newman的快速社團(tuán)探測(cè)算法，把US Air lines劃分為5個(gè)社團(tuán)，網(wǎng)絡(luò)傳輸容量ρc與重連邊比例fc的關(guān)系如圖7所示:可以看到隨著重連邊比例的增加，網(wǎng)絡(luò)的傳輸容量在不斷提升。

4 結(jié)語

本文提出了一種通過削弱社團(tuán)結(jié)構(gòu)，社團(tuán)內(nèi)刪除鏈路，社團(tuán)間添加鏈路的重連策略即CCLS策略。分別在偽隨機(jī)網(wǎng)絡(luò)、CWS小世界網(wǎng)絡(luò)、無標(biāo)度等人造社團(tuán)網(wǎng)絡(luò)中進(jìn)行了仿真實(shí)驗(yàn)，CCLS策略能有效抑制網(wǎng)絡(luò)擁塞，進(jìn)一步提高網(wǎng)絡(luò)傳輸容量。在真實(shí)的網(wǎng)絡(luò)中，如航空網(wǎng)絡(luò)中通過本文策略，改變航線，提高了飛行的容量。因此，對(duì)于多數(shù)網(wǎng)絡(luò)，本策略都具有較高的實(shí)用價(jià)值。