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

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

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

1 引 言

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

如何定量地描述網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)信息是研究網(wǎng)絡(luò)傳輸性能的關(guān)鍵問題.當(dāng)以信息的角度去描述網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)時(shí), 信息論中的香農(nóng)熵理論是一個(gè)有力的工具.香農(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)信息的度量評(píng)估上.Wang 等[38]研究了可以度量網(wǎng)絡(luò)異質(zhì)性的度分布熵.吳俊等[39]利用節(jié)點(diǎn)相對(duì)度值定義了網(wǎng)絡(luò)的結(jié)構(gòu)熵, 可以定量分析無標(biāo)度網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的非均勻性.蔡萌等[40]從網(wǎng)絡(luò)結(jié)構(gòu)中的“點(diǎn)”差異性和“邊”差異性兩方面綜合考慮度值大小和度分布作為結(jié)構(gòu)重要性的度量, 進(jìn)而提出一種新的網(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]針對(duì)以往用以度量網(wǎng)絡(luò)異構(gòu)型不足問題引入網(wǎng)絡(luò)流的概念, 綜合考慮徑向測(cè)度和中間測(cè)度,提出一種新的網(wǎng)絡(luò)結(jié)構(gòu)熵, 能夠從全局刻畫網(wǎng)絡(luò)的真實(shí)結(jié)構(gòu), 但這種網(wǎng)絡(luò)結(jié)構(gòu)熵并不是單獨(dú)考慮網(wǎng)絡(luò)的靜態(tài)拓?fù)浣Y(jié)構(gòu), 而是從流量角度刻畫網(wǎng)絡(luò)真實(shí)結(jié)構(gòu), 復(fù)雜度較高.胡鋼等[42]研究了節(jié)點(diǎn)與其直接相連的鄰節(jié)點(diǎn)和一次間接相連的鄰節(jié)點(diǎn)之間的關(guān)聯(lián)關(guān)系, 提出了節(jié)點(diǎn)鄰接信息熵算法, 并以節(jié)點(diǎn)的信息熵?cái)?shù)值大小表征節(jié)點(diǎn)在網(wǎng)絡(luò)中的重要性程度.陳單等[43?45]以通信能力函數(shù)矩陣為基礎(chǔ)引入香農(nóng)熵理論, 并提出通信序列熵的概念.由于網(wǎng)絡(luò)節(jié)點(diǎn)間的通信能力函數(shù)考慮了節(jié)點(diǎn)之間的所有可能路徑,所以通信序列熵能完整地體現(xiàn)網(wǎng)絡(luò)的整體拓?fù)湫再|(zhì), 可以作為網(wǎng)絡(luò)之間的差異性的衡量指標(biāo).

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

2 方 法

2.1 通信序列熵

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

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

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

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

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

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

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

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

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

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

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

2.3 理論評(píng)估

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

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

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

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

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

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

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

在復(fù)雜網(wǎng)絡(luò)數(shù)據(jù)包傳輸動(dòng)力學(xué)行為研究過程中, 網(wǎng)絡(luò)中度值較大的核心節(jié)點(diǎn)具有舉足輕重的地位, 數(shù)據(jù)包傳輸過程中產(chǎn)生的擁塞現(xiàn)象與之息息相關(guān).因此, 有效路由策略(efficient routing)[54]將網(wǎng)絡(luò)中節(jié)點(diǎn)的度作為路由選擇的代價(jià)函數(shù), 假如從節(jié)點(diǎn)i到節(jié)點(diǎn)j的路徑為P(i →j):=i ≡x0, x1, ··· ,xn?1,xn ≡j, 其代價(jià)函數(shù)為其中n為路徑長度,a為控制參數(shù).此次仿真采用的為有效路由策略且策略中的可調(diào)控制參數(shù)均為通過仿真得到的最優(yōu)控制參數(shù).設(shè)定網(wǎng)絡(luò)節(jié)點(diǎn)規(guī)模為N=400 , 網(wǎng)絡(luò)中數(shù)據(jù)包生成速率R=80 , 節(jié)點(diǎn)的處理能力C=1.采用文獻(xiàn)[10]中的網(wǎng)絡(luò)生成算法生成網(wǎng)絡(luò)平均度為〈k〉=2m, 并且網(wǎng)絡(luò)的度分布服從指數(shù)為γ=?3 的BA 無標(biāo)度網(wǎng)絡(luò).采用文獻(xiàn)[11]中的網(wǎng)絡(luò)生成算法生成WS 小世界網(wǎng)絡(luò), 網(wǎng)絡(luò)中任意節(jié)點(diǎn)都與它左右相鄰的各 2 個(gè)節(jié)點(diǎn)相連, 重連概率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ò)的通信序列熵在增大的時(shí)候, 網(wǎng)絡(luò)的度值范圍增大, 但網(wǎng)絡(luò)中節(jié)點(diǎn)的度分布曲線從陡峭化向平緩狀態(tài)發(fā)展, 網(wǎng)絡(luò)愈加均勻.分析如下: 網(wǎng)絡(luò)向均勻網(wǎng)絡(luò)發(fā)展時(shí), 通信序列元素集合B中的元素會(huì)變得更加均勻, 進(jìn)而通信序列熵值會(huì)增大.隨著網(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ò)的均勻性會(huì)隨著網(wǎng)絡(luò)節(jié)點(diǎn)之間的連接情況的改變而改變.當(dāng)網(wǎng)絡(luò)變得越來越稠密時(shí), 網(wǎng)絡(luò)通信序列熵中的元素?cái)?shù)值彼此接近且均勻, 進(jìn)而導(dǎo)致網(wǎng)絡(luò)的通信序列熵增大.從網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)角度來看, 網(wǎng)絡(luò)中許多非鄰節(jié)點(diǎn)隨著通信序列熵的增大或減小而進(jìn)行連接或斷開, 這些節(jié)點(diǎn)的度值會(huì)因此增大或減小, 使網(wǎng)絡(luò)中原有的核心節(jié)點(diǎn)的影響降低或增大.網(wǎng)絡(luò)的核心節(jié)點(diǎn)比例程度極大地影響網(wǎng)絡(luò)的均勻性.當(dāng)均勻性較低時(shí), 網(wǎng)絡(luò)中核心節(jié)點(diǎn)影響力高, 網(wǎng)絡(luò)向非均勻性網(wǎng)絡(luò)發(fā)展, 根據(jù)傳統(tǒng)流量模型隨機(jī)選取的兩個(gè)節(jié)點(diǎn)之間的數(shù)據(jù)包傳輸路徑經(jīng)過網(wǎng)絡(luò)的核心節(jié)點(diǎn)的概率高, 數(shù)據(jù)包將會(huì)通過網(wǎng)絡(luò)的核心節(jié)點(diǎn), 核心節(jié)點(diǎn)的處理能力是固定的, 那么數(shù)據(jù)包在核心節(jié)點(diǎn)的緩存隊(duì)列中需要等待更長時(shí)間, 隨著時(shí)間的延長, 網(wǎng)絡(luò)就會(huì)處于一個(gè)擁塞狀態(tài).反之, 當(dāng)均勻性程度較高時(shí), 網(wǎng)絡(luò)中核心節(jié)點(diǎn)影響力低, 網(wǎng)絡(luò)向均勻性網(wǎng)絡(luò)發(fā)展, 根據(jù)傳統(tǒng)流量模型隨機(jī)選取的兩個(gè)節(jié)點(diǎn)之間的數(shù)據(jù)包傳輸路徑經(jīng)過網(wǎng)絡(luò)的核心節(jié)點(diǎn)的概率低, 數(shù)據(jù)包傳輸將會(huì)經(jīng)過更多的普通節(jié)點(diǎn),舒緩了核心節(jié)點(diǎn)上的負(fù)載壓力(數(shù)據(jù)包負(fù)載數(shù)目),網(wǎng)絡(luò)不易擁塞.且本次路由策略選取的是有效路由的策略, 合理有效地避開了部分核心節(jié)點(diǎn), 再一次降低了核心節(jié)點(diǎn)的影響力.對(duì)以上分析我們采取負(fù)載在節(jié)點(diǎn)分布的方法進(jìn)行驗(yàn)證.

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

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

圖4 數(shù)據(jù)包負(fù)載 (traffic load) 在網(wǎng)絡(luò)中節(jié)點(diǎn)度值上的分布情況 (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é)點(diǎn)的最大介數(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é)點(diǎn)最先發(fā)生擁塞, 與網(wǎng)絡(luò)傳輸容量成反比.通過仿真實(shí)驗(yàn)計(jì)算網(wǎng)絡(luò)的傳輸容量非常耗時(shí), 因此可以通過計(jì)算在不同路由策略下網(wǎng)絡(luò)中所有節(jié)點(diǎn)的有效介數(shù)的最大值來間接評(píng)估網(wǎng)絡(luò)的傳輸容量.通過對(duì)圖6(a)和圖6(b)的觀察可以看出, 基于有效路由算法下,同等規(guī)模的網(wǎng)絡(luò)通信序列熵值變化較快時(shí), 網(wǎng)絡(luò)的最大有效介數(shù)變化隨之增快, 可見網(wǎng)絡(luò)的節(jié)點(diǎn)最大介數(shù)敏感于通信序列熵的變化.當(dāng)通信序列熵最大時(shí), 網(wǎng)絡(luò)中最大介數(shù)值最小, 傳輸容量最大.當(dāng)通信序列熵最小時(shí), 網(wǎng)絡(luò)中最大介數(shù)值最大, 傳輸容量最小.

4 結(jié) 論

網(wǎng)絡(luò)傳輸容量與其拓?fù)浣Y(jié)構(gòu)密切相關(guān).本文引入了通信序列熵這一概念, 研究了不同網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)與其通信序列熵的對(duì)應(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ò)拓?fù)浣Y(jié)構(gòu)從非均勻網(wǎng)絡(luò)性向均勻網(wǎng)絡(luò)發(fā)展演化, 網(wǎng)絡(luò)的均勻拓?fù)浣Y(jié)構(gòu)利于數(shù)據(jù)包的傳輸.在網(wǎng)絡(luò)的傳輸動(dòng)力學(xué)中, 可以通過提高網(wǎng)絡(luò)的通信序列熵來優(yōu)化網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)進(jìn)而提高網(wǎng)絡(luò)的整體傳輸能力.這些工作表明在未來的實(shí)際網(wǎng)絡(luò)工程中, 可以通過增大網(wǎng)絡(luò)的通信序列熵的方法來優(yōu)化網(wǎng)絡(luò)的傳輸容量.這對(duì)實(shí)際網(wǎng)絡(luò)的設(shè)計(jì)與優(yōu)化具有一定的參考價(jià)值, 我們將在未來的研究中著重研究通信序列熵的應(yīng)用價(jià)值.