基于通信序列熵的復(fù)雜網(wǎng)絡(luò)傳輸容量*

馬金龍 張俊峰 張冬雯 張紅斌

(河北科技大學(xué)信息科學(xué)與工程學(xué)院, 石家莊 050018)

網(wǎng)絡(luò)的傳輸性能在一定程度上依賴于網(wǎng)絡(luò)的拓撲結(jié)構(gòu).本文從結(jié)構(gòu)信息的角度分析復(fù)雜網(wǎng)絡(luò)的傳輸動力學(xué)行為, 尋找影響網(wǎng)絡(luò)傳輸容量的信息結(jié)構(gòu)測度指標(biāo).通信序列熵可以有效地量化網(wǎng)絡(luò)的整體結(jié)構(gòu)信息,為了表征網(wǎng)絡(luò)整體傳輸能力, 把通信序列熵引入到復(fù)雜網(wǎng)絡(luò)傳輸動力學(xué)分析中, 研究網(wǎng)絡(luò)的通信序列熵與傳輸性能之間的關(guān)聯(lián)特性, 分析這種相關(guān)性存在的內(nèi)在機理.分別在BA 無標(biāo)度和WS 小世界網(wǎng)絡(luò)模型上進行仿真, 結(jié)果顯示: 網(wǎng)絡(luò)的通信序列熵與其傳輸容量存在密切關(guān)聯(lián)性, 隨著通信序列熵的增加, 網(wǎng)絡(luò)拓撲結(jié)構(gòu)的均勻性隨之增強, 傳輸容量明顯增加.網(wǎng)絡(luò)的傳輸容量是通信序列熵的單調(diào)遞增函數(shù), 與通信序列熵成正關(guān)聯(lián)關(guān)系.通信序列熵可有效評估網(wǎng)絡(luò)的傳輸容量, 本結(jié)論可為設(shè)計高傳輸容量網(wǎng)絡(luò)提供理論依據(jù).

1 引 言

現(xiàn)實世界中有著各式各樣的網(wǎng)絡(luò), 如通信網(wǎng)絡(luò)[1?4]、交通網(wǎng)絡(luò)[5,6]、社區(qū)網(wǎng)絡(luò)[7,8]、貿(mào)易網(wǎng)絡(luò)[9]等.這些網(wǎng)絡(luò)大多表現(xiàn)出高度的復(fù)雜性, 如連接結(jié)構(gòu)的復(fù)雜性、節(jié)點類型的復(fù)雜性和網(wǎng)絡(luò)演化過程的復(fù)雜性等.復(fù)雜網(wǎng)絡(luò)理論不僅可以幫助我們更好地理解現(xiàn)實網(wǎng)絡(luò)的復(fù)雜結(jié)構(gòu)特征, 還可以有效研究發(fā)生在現(xiàn)實網(wǎng)絡(luò)上的動力學(xué)行為[10?14].網(wǎng)絡(luò)的拓撲結(jié)構(gòu)決定其功能, 網(wǎng)絡(luò)上的動力學(xué)行為受到網(wǎng)絡(luò)拓撲結(jié)構(gòu)的影響.隨著大數(shù)據(jù)時代的到來, 網(wǎng)絡(luò)擁塞現(xiàn)象越發(fā)嚴重, 如何提升網(wǎng)絡(luò)傳輸容量成為廣大學(xué)者關(guān)注的問題.Guimerá等[15]證明了缺少高介數(shù)節(jié)點的均勻網(wǎng)絡(luò)具有更大的網(wǎng)絡(luò)承載能力.Zhao 等[16]基于概率統(tǒng)計方法對影響網(wǎng)絡(luò)傳輸容量的因素進行了分析, 指出網(wǎng)絡(luò)的傳輸容量與網(wǎng)絡(luò)平均最短路徑和節(jié)點最大介數(shù)值所占比重成反比關(guān)系, 提出了可用于衡量網(wǎng)絡(luò)傳輸容量的數(shù)值計算公式.孫磊等[17]從網(wǎng)絡(luò)的拓撲結(jié)構(gòu)指標(biāo)(最大介數(shù)、最大介數(shù)比例、平均路徑長度)角度研究了網(wǎng)絡(luò)結(jié)構(gòu)對網(wǎng)絡(luò)傳輸容量的影響, 研究表明網(wǎng)絡(luò)的拓撲結(jié)構(gòu)指標(biāo)的變化對網(wǎng)絡(luò)的傳輸容量有著顯著影響.Chen 等[18]通過理論分析表明, 為緩解擁塞現(xiàn)象, 最佳的網(wǎng)絡(luò)拓撲應(yīng)具有兩個關(guān)鍵特征: 流量分布均勻和傳輸距離短.現(xiàn)有一些學(xué)者通過增加或刪除部分比例的邊, 或者將一定比例的雙向邊更改為單向邊的方法來優(yōu)化網(wǎng)絡(luò)的拓撲結(jié)構(gòu), 進而緩解網(wǎng)絡(luò)擁塞的發(fā)生, 提升網(wǎng)絡(luò)的傳輸容量[19?34].

如何定量地描述網(wǎng)絡(luò)拓撲結(jié)構(gòu)信息是研究網(wǎng)絡(luò)傳輸性能的關(guān)鍵問題.當(dāng)以信息的角度去描述網(wǎng)絡(luò)的拓撲結(jié)構(gòu)時, 信息論中的香農(nóng)熵理論是一個有力的工具.香農(nóng)熵理論本身是描述事物帶有某種信息的不確定性, 在熱力學(xué)與信息學(xué)理論中廣泛應(yīng)用[35?37].隨著復(fù)雜網(wǎng)絡(luò)研究的逐漸深入, 為了有效地量化網(wǎng)絡(luò)結(jié)構(gòu)信息, 香農(nóng)熵理論被廣泛地應(yīng)用到復(fù)雜網(wǎng)絡(luò)模型相關(guān)信息的度量評估上.Wang 等[38]研究了可以度量網(wǎng)絡(luò)異質(zhì)性的度分布熵.吳俊等[39]利用節(jié)點相對度值定義了網(wǎng)絡(luò)的結(jié)構(gòu)熵, 可以定量分析無標(biāo)度網(wǎng)絡(luò)拓撲結(jié)構(gòu)的非均勻性.蔡萌等[40]從網(wǎng)絡(luò)結(jié)構(gòu)中的“點”差異性和“邊”差異性兩方面綜合考慮度值大小和度分布作為結(jié)構(gòu)重要性的度量, 進而提出一種新的網(wǎng)絡(luò)結(jié)構(gòu)熵定義.這種網(wǎng)絡(luò)結(jié)構(gòu)熵可以更有效地反映網(wǎng)絡(luò)的結(jié)構(gòu)特征, 能夠更為合理地解釋稀疏網(wǎng)絡(luò)及星型網(wǎng)絡(luò)的結(jié)構(gòu)差異.蔡萌等[41]針對以往用以度量網(wǎng)絡(luò)異構(gòu)型不足問題引入網(wǎng)絡(luò)流的概念, 綜合考慮徑向測度和中間測度,提出一種新的網(wǎng)絡(luò)結(jié)構(gòu)熵, 能夠從全局刻畫網(wǎng)絡(luò)的真實結(jié)構(gòu), 但這種網(wǎng)絡(luò)結(jié)構(gòu)熵并不是單獨考慮網(wǎng)絡(luò)的靜態(tài)拓撲結(jié)構(gòu), 而是從流量角度刻畫網(wǎng)絡(luò)真實結(jié)構(gòu), 復(fù)雜度較高.胡鋼等[42]研究了節(jié)點與其直接相連的鄰節(jié)點和一次間接相連的鄰節(jié)點之間的關(guān)聯(lián)關(guān)系, 提出了節(jié)點鄰接信息熵算法, 并以節(jié)點的信息熵數(shù)值大小表征節(jié)點在網(wǎng)絡(luò)中的重要性程度.陳單等[43?45]以通信能力函數(shù)矩陣為基礎(chǔ)引入香農(nóng)熵理論, 并提出通信序列熵的概念.由于網(wǎng)絡(luò)節(jié)點間的通信能力函數(shù)考慮了節(jié)點之間的所有可能路徑,所以通信序列熵能完整地體現(xiàn)網(wǎng)絡(luò)的整體拓撲性質(zhì), 可以作為網(wǎng)絡(luò)之間的差異性的衡量指標(biāo).

本文基于網(wǎng)絡(luò)通信序列熵理論, 分析不同類型網(wǎng)絡(luò)通信序列熵與網(wǎng)絡(luò)承載能力的數(shù)量變化關(guān)系,以明確網(wǎng)絡(luò)的拓撲結(jié)構(gòu)的特征對傳輸容量的影響.系統(tǒng)地研究了無標(biāo)度網(wǎng)絡(luò)和小世界網(wǎng)絡(luò)的通信序列熵和傳輸容量之間的關(guān)聯(lián)特性.最終的研究結(jié)果表明, 對于無標(biāo)度網(wǎng)絡(luò)和小世界網(wǎng)絡(luò)而言, 它們的通信序列熵與傳輸容量成正關(guān)聯(lián).這一發(fā)現(xiàn)對構(gòu)建高效率的傳輸網(wǎng)絡(luò)具有一定指導(dǎo)意義.

2 方 法

2.1 通信序列熵

一個無權(quán)無向網(wǎng)絡(luò)可以用N×N的鄰接矩陣A表示節(jié)點之間的連接關(guān)系.如果網(wǎng)絡(luò)中的節(jié)點i和節(jié)點j直接相連, 則鄰接矩陣A中的元素aij=1 ,否則aij=0.Estrada 等[46?48]根據(jù)網(wǎng)絡(luò)中節(jié)點之間相互到達的所有路徑與該網(wǎng)絡(luò)的冪次鄰接矩陣之間的關(guān)系, 并考慮到在節(jié)點間較短的路徑對節(jié)點的通信能力影響比較大, 因此將較短的路徑賦予較大的權(quán)重, 用正值表示網(wǎng)絡(luò)中節(jié)點間的通信能力,提出了可用來表示網(wǎng)絡(luò)節(jié)點之間的通信能力的矩陣CA:

通信能力矩陣CA的第i行第j列的元素(ca)ij代表節(jié)點i和節(jié)點j之間的通信能力,l表示兩個節(jié)點之間的路徑長度.當(dāng)i=j時, (ca)ij是節(jié)點的子圖中心性, 表示節(jié)點的自通信能力(本次研究暫不考慮).為方便計算, 首先使用矩陣論中的矩陣分解A=Q ∧Q?1, 然后求出通信能力矩陣CA=eA=Qe∧Q?1, 其中Q為標(biāo)準正交基組成的正交矩陣.

通信序列熵的概念描述如下: 首先將通信能力矩陣的對角線上方的元素取出來存儲到通信序列元素集合B=[(ca)12,(ca)13, ··· ,(ca)1N; (ca)23,(ca)24, ··· ,(ca)2N;···], 然后根據(jù)香農(nóng)熵理論計算概率集合P=[P1,P2, ··· ,PM] ,M=N(N ?1)/2 ,其中集合P中的元素為(1 ≤l≤M,1 ≤i

定義通信序列標(biāo)準熵為

本文用到的通信序列熵為通信序列標(biāo)準熵.

2.2 流量模型

復(fù)雜網(wǎng)絡(luò)的傳輸容量是衡量網(wǎng)絡(luò)傳輸性能的重要指標(biāo), 衡量網(wǎng)絡(luò)傳輸容量的模型為流量模型.流量模型用來描述數(shù)據(jù)包在網(wǎng)絡(luò)的傳輸過程, 并可判斷網(wǎng)絡(luò)從自由態(tài)到擁塞態(tài)的相變.本文采用了復(fù)雜網(wǎng)絡(luò)研究中經(jīng)典的流量模型[49?51], 具體描述如下:

1)節(jié)點有主機和路由功能, 即節(jié)點本身同時具有產(chǎn)生、接收、轉(zhuǎn)發(fā)數(shù)據(jù)包的功能.節(jié)點尾部設(shè)置緩存隊列, 用來存儲節(jié)點自身產(chǎn)生和來自其他節(jié)點的數(shù)據(jù)包, 此緩存隊列設(shè)置為無窮大.數(shù)據(jù)包進出緩存隊列時采用先進先出的規(guī)則.

2)數(shù)據(jù)包產(chǎn)生: 每個時間步內(nèi), 網(wǎng)絡(luò)中會生成R個數(shù)據(jù)包, 各個數(shù)據(jù)包的源節(jié)點s和目的節(jié)點d隨機確定, 并且不能為同一節(jié)點.

3)數(shù)據(jù)包傳輸: 每個時間步內(nèi), 網(wǎng)絡(luò)中的所有節(jié)點都具有相同的對數(shù)據(jù)包的處理能力C, 這種處理能力是節(jié)點每個時間步能處理的數(shù)據(jù)包數(shù)量.

4)數(shù)據(jù)包接收: 如果每個時間步內(nèi)超過C個數(shù)據(jù)包需要處理, 則節(jié)點先對前C個數(shù)據(jù)包進行處理, 節(jié)點的緩存隊列會對剩余的數(shù)據(jù)包進行保存,等待下一時間步內(nèi)處理.如果數(shù)據(jù)包到達目的節(jié)點, 則被立即從網(wǎng)絡(luò)中移除.

通過流量模型可以知道, 當(dāng)節(jié)點處理能力C為有限值時, 隨著數(shù)據(jù)包的生成速率R逐漸增大, 網(wǎng)絡(luò)中的部分節(jié)點緩存隊列堆積的數(shù)據(jù)包的數(shù)量越來越多, 造成這部分節(jié)點緩存隊列中的數(shù)據(jù)包無法及時處理而越積越多, 最后數(shù)據(jù)包數(shù)量超過了網(wǎng)絡(luò)的承受能力, 網(wǎng)絡(luò)進入擁塞狀態(tài).數(shù)據(jù)包的生成速率R存在一個關(guān)鍵值Rc.當(dāng)RRc時, 網(wǎng)絡(luò)的總數(shù)據(jù)包數(shù)目呈無限增長趨勢, 會導(dǎo)致網(wǎng)絡(luò)產(chǎn)生擁塞現(xiàn)象.引入有序參數(shù)H(R) 對網(wǎng)絡(luò)從自由態(tài)向擁塞態(tài)轉(zhuǎn)換進行刻畫:

式 中〈?W〉=W(t+?T)?W(t) , 其 中,W(t) 表示在t時刻, 網(wǎng)絡(luò)中所擁有的數(shù)據(jù)包的數(shù)目,?W表示在 ?T窗口時間內(nèi), 網(wǎng)絡(luò)中的數(shù)據(jù)包數(shù)量的變化.當(dāng)RRc時,H(R)>0 , 隨著時間的增加, 網(wǎng)絡(luò)中的緩存數(shù)據(jù)包越積越多, 出現(xiàn)擁塞現(xiàn)象.

2.3 理論評估

介數(shù)(betweenness centrality)可以表示節(jié)點在網(wǎng)絡(luò)中的中心程度, 其最初的定義為在最短路由算法下經(jīng)過節(jié)點i的最短路徑條數(shù)[52]:

其中,σsd表示源節(jié)點s到達目的節(jié)點d之間的最短路徑條數(shù),σsd(i) 表 示從源節(jié)點s到達目的節(jié)點d的最短路徑中經(jīng)過節(jié)點i的最短路徑條數(shù).雖然介數(shù)的定義基于最短路徑路由算法, 但是有很多已經(jīng)存在的路由算法并不是以最短路徑為基礎(chǔ).研究人員將介數(shù)的定義擴充為有效介數(shù), 用以評估實際路由策略下網(wǎng)絡(luò)的容量情況, 有效介數(shù)一般定義為[53]

其中表示節(jié)點i的有效介數(shù),指在某種路由算法下從節(jié)點s到節(jié)點d之間的路徑條數(shù),表示從源節(jié)點s到達目的節(jié)點d的路徑中通過節(jié)點i的條數(shù).

可以使用介數(shù)對網(wǎng)絡(luò)的傳輸容量進行理論評估[50],RBi/[N(N ?1)] 表示每個時間步長內(nèi), 到達網(wǎng)絡(luò)中任何一個節(jié)點i的平均數(shù)據(jù)包個數(shù), 其中Bi/[N(N ?1)] 表 示一個數(shù)據(jù)包到達介數(shù)為Bi的節(jié)點i的概率.如果RBi/[N(N ?1)]>C, 那么數(shù)據(jù)包將在節(jié)點i上逐漸堆積, 網(wǎng)絡(luò)擁塞現(xiàn)象將會發(fā)生.當(dāng)保證網(wǎng)絡(luò)中節(jié)點都不發(fā)生數(shù)據(jù)包堆積時, 那么所有的節(jié)點都應(yīng)滿足RBi/[N(N ?1)]≤C, 整理此式可以得到下式:

其中Bmax表示網(wǎng)絡(luò)中所有節(jié)點介數(shù)的最大值.網(wǎng)絡(luò)傳輸容量Rc=CN(N ?1)/Bmax為使得網(wǎng)絡(luò)不發(fā)生擁塞的最大R值, 則從該式可以看出, 要想得到網(wǎng)絡(luò)最大的傳輸容量, 可通過最小化網(wǎng)絡(luò)中節(jié)點的最大介數(shù).因此, 可以用網(wǎng)絡(luò)中節(jié)點介數(shù)的最大值Bmax的變化來評估網(wǎng)絡(luò)傳輸容量的變化情況.

3 復(fù)雜網(wǎng)絡(luò)通信序列熵與傳輸容量的關(guān)系

3.1 仿真數(shù)值的設(shè)置

在復(fù)雜網(wǎng)絡(luò)數(shù)據(jù)包傳輸動力學(xué)行為研究過程中, 網(wǎng)絡(luò)中度值較大的核心節(jié)點具有舉足輕重的地位, 數(shù)據(jù)包傳輸過程中產(chǎn)生的擁塞現(xiàn)象與之息息相關(guān).因此, 有效路由策略(efficient routing)[54]將網(wǎng)絡(luò)中節(jié)點的度作為路由選擇的代價函數(shù), 假如從節(jié)點i到節(jié)點j的路徑為P(i →j):=i ≡x0, x1, ··· ,xn?1,xn ≡j, 其代價函數(shù)為其中n為路徑長度,a為控制參數(shù).此次仿真采用的為有效路由策略且策略中的可調(diào)控制參數(shù)均為通過仿真得到的最優(yōu)控制參數(shù).設(shè)定網(wǎng)絡(luò)節(jié)點規(guī)模為N=400 , 網(wǎng)絡(luò)中數(shù)據(jù)包生成速率R=80 , 節(jié)點的處理能力C=1.采用文獻[10]中的網(wǎng)絡(luò)生成算法生成網(wǎng)絡(luò)平均度為〈k〉=2m, 并且網(wǎng)絡(luò)的度分布服從指數(shù)為γ=?3 的BA 無標(biāo)度網(wǎng)絡(luò).采用文獻[11]中的網(wǎng)絡(luò)生成算法生成WS 小世界網(wǎng)絡(luò), 網(wǎng)絡(luò)中任意節(jié)點都與它左右相鄰的各 2 個節(jié)點相連, 重連概率P設(shè)置為從 0.1 至 0.9.

3.2 仿真結(jié)果分析

圖1(a)和圖1(b)分別給出了BA 無標(biāo)度網(wǎng)絡(luò)和WS 小世界網(wǎng)絡(luò)的通信序列熵SN和網(wǎng)絡(luò)的度分布P(k) 之間的關(guān)系.可以看出, 兩種類型網(wǎng)絡(luò)的通信序列熵在增大的時候, 網(wǎng)絡(luò)的度值范圍增大, 但網(wǎng)絡(luò)中節(jié)點的度分布曲線從陡峭化向平緩狀態(tài)發(fā)展, 網(wǎng)絡(luò)愈加均勻.分析如下: 網(wǎng)絡(luò)向均勻網(wǎng)絡(luò)發(fā)展時, 通信序列元素集合B中的元素會變得更加均勻, 進而通信序列熵值會增大.隨著網(wǎng)絡(luò)通信序列熵的增大, BA 無標(biāo)度網(wǎng)絡(luò)的度分布并沒有改變整體的冪律分布形狀, WS 小世界網(wǎng)絡(luò)的度分布則更加趨近于正態(tài)分布.

圖2 和圖3 給出了網(wǎng)絡(luò)的通信序列熵與傳輸容量的關(guān)系.可以看出, 網(wǎng)絡(luò)傳輸容量隨著通信序列熵的增大而增大.理論分析如下: 網(wǎng)絡(luò)的均勻性會隨著網(wǎng)絡(luò)節(jié)點之間的連接情況的改變而改變.當(dāng)網(wǎng)絡(luò)變得越來越稠密時, 網(wǎng)絡(luò)通信序列熵中的元素數(shù)值彼此接近且均勻, 進而導(dǎo)致網(wǎng)絡(luò)的通信序列熵增大.從網(wǎng)絡(luò)的拓撲結(jié)構(gòu)角度來看, 網(wǎng)絡(luò)中許多非鄰節(jié)點隨著通信序列熵的增大或減小而進行連接或斷開, 這些節(jié)點的度值會因此增大或減小, 使網(wǎng)絡(luò)中原有的核心節(jié)點的影響降低或增大.網(wǎng)絡(luò)的核心節(jié)點比例程度極大地影響網(wǎng)絡(luò)的均勻性.當(dāng)均勻性較低時, 網(wǎng)絡(luò)中核心節(jié)點影響力高, 網(wǎng)絡(luò)向非均勻性網(wǎng)絡(luò)發(fā)展, 根據(jù)傳統(tǒng)流量模型隨機選取的兩個節(jié)點之間的數(shù)據(jù)包傳輸路徑經(jīng)過網(wǎng)絡(luò)的核心節(jié)點的概率高, 數(shù)據(jù)包將會通過網(wǎng)絡(luò)的核心節(jié)點, 核心節(jié)點的處理能力是固定的, 那么數(shù)據(jù)包在核心節(jié)點的緩存隊列中需要等待更長時間, 隨著時間的延長, 網(wǎng)絡(luò)就會處于一個擁塞狀態(tài).反之, 當(dāng)均勻性程度較高時, 網(wǎng)絡(luò)中核心節(jié)點影響力低, 網(wǎng)絡(luò)向均勻性網(wǎng)絡(luò)發(fā)展, 根據(jù)傳統(tǒng)流量模型隨機選取的兩個節(jié)點之間的數(shù)據(jù)包傳輸路徑經(jīng)過網(wǎng)絡(luò)的核心節(jié)點的概率低, 數(shù)據(jù)包傳輸將會經(jīng)過更多的普通節(jié)點,舒緩了核心節(jié)點上的負載壓力(數(shù)據(jù)包負載數(shù)目),網(wǎng)絡(luò)不易擁塞.且本次路由策略選取的是有效路由的策略, 合理有效地避開了部分核心節(jié)點, 再一次降低了核心節(jié)點的影響力.對以上分析我們采取負載在節(jié)點分布的方法進行驗證.

圖1 網(wǎng)絡(luò)的通信序列熵SN 與網(wǎng)絡(luò)的度分布P(k)之間的關(guān)系圖 (a) BA 無標(biāo)度網(wǎng)絡(luò); (b) WS 小世界網(wǎng)絡(luò)Fig.1.Rrelationship between the network’s communication sequence entropy SN and the network’s degree distribution P(k): (a) BA scale-free network; (b) WS small world network.

圖2 (a)不同的通信序列熵的BA 無標(biāo)度網(wǎng)絡(luò)下, 有序參數(shù)H(R)與數(shù)據(jù)包生成率R 的關(guān)系; (b) BA 無標(biāo)度網(wǎng)絡(luò)通信序列熵SN與傳輸容量 R c 的關(guān)系.采用的路由策略為有效路由策略Fig.2.(a) Relationship between the order parameter H(R) and the packet generation rate R under BA scale-free network with different communication sequence entropy; (b) relationship between BA scale-free network communication sequence entropy S N and traffic capacity R c.The routing strategy adopted is an effective routing strategy.

圖3 (a)不同的通信序列熵的WS 小世界網(wǎng)絡(luò)下, 有序參數(shù)H(R)與數(shù)據(jù)包生成率R 的關(guān)系; (b) WS 小世界網(wǎng)絡(luò)通信序列熵SN與傳輸容量 R c 的關(guān)系.采用的路由策略為有效路由策略Fig.3.(a) Relationship between the order parameters H (R) and the packet generation rate R under the WS small world network with different communication sequence entropy; (b) relationship between WS small world network communication sequence entropy SN and traffic capacity R c.The routing strategy adopted is an effective routing strategy.

圖4 (a)和圖4(b)所示為兩種網(wǎng)絡(luò)的節(jié)點度值上的數(shù)據(jù)包負載 (traffic load)分布.可以看出, 隨著通信序列熵的增大, 數(shù)據(jù)包負載在各個不同度值大小的節(jié)點間的分布愈加緩和及均勻.核心節(jié)點和普通節(jié)點的數(shù)據(jù)包負載數(shù)目隨著通信序列熵的增大漸漸地接近于相同的數(shù)值.數(shù)據(jù)包負載在傳輸過程中的分布愈加均勻, 進而使網(wǎng)絡(luò)的傳輸容量整體提升, 所以BA 無標(biāo)度網(wǎng)絡(luò)及WS 小世界網(wǎng)絡(luò)的傳輸容量隨著網(wǎng)絡(luò)的通信序列熵的增大而增大, 成正關(guān)聯(lián)關(guān)系.通信序列熵亦可成為評估同種類型但不拓撲同結(jié)構(gòu)網(wǎng)絡(luò)的傳輸容量的指標(biāo).

圖5(a)和圖5(b)給出了網(wǎng)絡(luò)的平均路徑長度隨通信序列熵的變化.可以看出, 網(wǎng)絡(luò)的平均路徑長度隨著通信序列熵的增大反而減小.這是因為路由策略考慮的數(shù)據(jù)包在傳輸時盡量是避開核心節(jié)點, 對于數(shù)據(jù)包選擇的路徑而言, 節(jié)點之間間隔較短的路徑上有度值較大的核心節(jié)點, 節(jié)點之間間隔遠的路徑上有度值較小的普通節(jié)點.由于隨著網(wǎng)絡(luò)通信序列熵的增大, 網(wǎng)絡(luò)從稀疏狀態(tài)向稠密狀態(tài)發(fā)展, 使節(jié)點之間間隔遠的路徑上的非鄰節(jié)點之間進行連接, 出現(xiàn)了許多的度值較大的節(jié)點, 使核心節(jié)點的地位降低.源節(jié)點和目的節(jié)點之間的數(shù)據(jù)包傳輸會經(jīng)過更多新出現(xiàn)的度值較大節(jié)點, 經(jīng)過更少的邊.從而導(dǎo)致節(jié)點與節(jié)點之間的傳輸路徑長度變小, 進而導(dǎo)致整個網(wǎng)絡(luò)的平均路徑減小, 會使數(shù)據(jù)包到達各個目的節(jié)點的平均時間整體降低, 提高了數(shù)據(jù)包整體的傳輸效率.

圖4 數(shù)據(jù)包負載 (traffic load) 在網(wǎng)絡(luò)中節(jié)點度值上的分布情況 (a) BA 無標(biāo)度網(wǎng)絡(luò); (b) WS 小世界網(wǎng)絡(luò)Fig.4.Distribution of traffic load on degree value of nodes in the network: (a) BA scale-free network; (b) WS small world network.

圖5 網(wǎng)絡(luò)的通信序列熵 S N 與平均路徑長度 〈 L〉 的關(guān)系 (a) BA 無標(biāo)度網(wǎng)絡(luò); (b) WS 小世界網(wǎng)絡(luò)Fig.5.Relationship between communication sequence entropy SN and average path length 〈 L〉 in the network: (a) BA scale-free network; (b) WS small world network.

圖6 網(wǎng)絡(luò)的通信序列熵 S N 與節(jié)點的最大介數(shù) B max 的關(guān)系 (a) BA 無標(biāo)度網(wǎng)絡(luò); (b) WS 小世界網(wǎng)絡(luò)Fig.6.Relationship between communication sequence entropy S N and the maximum betweenness of nodes B max in the network:(a) BA scale-free network; (b) WS small world network.

根據(jù)2.3 節(jié)得知, 網(wǎng)絡(luò)中介數(shù)值最大的節(jié)點最先發(fā)生擁塞, 與網(wǎng)絡(luò)傳輸容量成反比.通過仿真實驗計算網(wǎng)絡(luò)的傳輸容量非常耗時, 因此可以通過計算在不同路由策略下網(wǎng)絡(luò)中所有節(jié)點的有效介數(shù)的最大值來間接評估網(wǎng)絡(luò)的傳輸容量.通過對圖6(a)和圖6(b)的觀察可以看出, 基于有效路由算法下,同等規(guī)模的網(wǎng)絡(luò)通信序列熵值變化較快時, 網(wǎng)絡(luò)的最大有效介數(shù)變化隨之增快, 可見網(wǎng)絡(luò)的節(jié)點最大介數(shù)敏感于通信序列熵的變化.當(dāng)通信序列熵最大時, 網(wǎng)絡(luò)中最大介數(shù)值最小, 傳輸容量最大.當(dāng)通信序列熵最小時, 網(wǎng)絡(luò)中最大介數(shù)值最大, 傳輸容量最小.

4 結(jié) 論

網(wǎng)絡(luò)傳輸容量與其拓撲結(jié)構(gòu)密切相關(guān).本文引入了通信序列熵這一概念, 研究了不同網(wǎng)絡(luò)拓撲結(jié)構(gòu)與其通信序列熵的對應(yīng)關(guān)系, 并探究網(wǎng)絡(luò)通信序列熵與傳輸容量的關(guān)聯(lián)性, 研究發(fā)現(xiàn)復(fù)雜網(wǎng)絡(luò)的通信序列熵和網(wǎng)絡(luò)的傳輸容量之間成正關(guān)聯(lián).隨著網(wǎng)絡(luò)通信序列熵的增大, 網(wǎng)絡(luò)拓撲結(jié)構(gòu)從非均勻網(wǎng)絡(luò)性向均勻網(wǎng)絡(luò)發(fā)展演化, 網(wǎng)絡(luò)的均勻拓撲結(jié)構(gòu)利于數(shù)據(jù)包的傳輸.在網(wǎng)絡(luò)的傳輸動力學(xué)中, 可以通過提高網(wǎng)絡(luò)的通信序列熵來優(yōu)化網(wǎng)絡(luò)的拓撲結(jié)構(gòu)進而提高網(wǎng)絡(luò)的整體傳輸能力.這些工作表明在未來的實際網(wǎng)絡(luò)工程中, 可以通過增大網(wǎng)絡(luò)的通信序列熵的方法來優(yōu)化網(wǎng)絡(luò)的傳輸容量.這對實際網(wǎng)絡(luò)的設(shè)計與優(yōu)化具有一定的參考價值, 我們將在未來的研究中著重研究通信序列熵的應(yīng)用價值.