基于通信序列熵的復雜網絡傳輸容量*

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

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

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

1 引 言

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

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

本文基于網絡通信序列熵理論, 分析不同類型網絡通信序列熵與網絡承載能力的數量變化關系,以明確網絡的拓撲結構的特征對傳輸容量的影響.系統地研究了無標度網絡和小世界網絡的通信序列熵和傳輸容量之間的關聯特性.最終的研究結果表明, 對于無標度網絡和小世界網絡而言, 它們的通信序列熵與傳輸容量成正關聯.這一發現對構建高效率的傳輸網絡具有一定指導意義.

2 方 法

2.1 通信序列熵

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

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

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

定義通信序列標準熵為

本文用到的通信序列熵為通信序列標準熵.

2.2 流量模型

復雜網絡的傳輸容量是衡量網絡傳輸性能的重要指標, 衡量網絡傳輸容量的模型為流量模型.流量模型用來描述數據包在網絡的傳輸過程, 并可判斷網絡從自由態到擁塞態的相變.本文采用了復雜網絡研究中經典的流量模型[49?51], 具體描述如下:

1)節點有主機和路由功能, 即節點本身同時具有產生、接收、轉發數據包的功能.節點尾部設置緩存隊列, 用來存儲節點自身產生和來自其他節點的數據包, 此緩存隊列設置為無窮大.數據包進出緩存隊列時采用先進先出的規則.

2)數據包產生: 每個時間步內, 網絡中會生成R個數據包, 各個數據包的源節點s和目的節點d隨機確定, 并且不能為同一節點.

3)數據包傳輸: 每個時間步內, 網絡中的所有節點都具有相同的對數據包的處理能力C, 這種處理能力是節點每個時間步能處理的數據包數量.

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

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

式 中〈?W〉=W(t+?T)?W(t) , 其 中,W(t) 表示在t時刻, 網絡中所擁有的數據包的數目,?W表示在 ?T窗口時間內, 網絡中的數據包數量的變化.當RRc時,H(R)>0 , 隨著時間的增加, 網絡中的緩存數據包越積越多, 出現擁塞現象.

2.3 理論評估

介數(betweenness centrality)可以表示節點在網絡中的中心程度, 其最初的定義為在最短路由算法下經過節點i的最短路徑條數[52]:

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

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

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

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

3 復雜網絡通信序列熵與傳輸容量的關系

3.1 仿真數值的設置

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

3.2 仿真結果分析

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

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

圖1 網絡的通信序列熵SN 與網絡的度分布P(k)之間的關系圖 (a) BA 無標度網絡; (b) WS 小世界網絡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 無標度網絡下, 有序參數H(R)與數據包生成率R 的關系; (b) BA 無標度網絡通信序列熵SN與傳輸容量 R c 的關系.采用的路由策略為有效路由策略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 小世界網絡下, 有序參數H(R)與數據包生成率R 的關系; (b) WS 小世界網絡通信序列熵SN與傳輸容量 R c 的關系.采用的路由策略為有效路由策略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)所示為兩種網絡的節點度值上的數據包負載 (traffic load)分布.可以看出, 隨著通信序列熵的增大, 數據包負載在各個不同度值大小的節點間的分布愈加緩和及均勻.核心節點和普通節點的數據包負載數目隨著通信序列熵的增大漸漸地接近于相同的數值.數據包負載在傳輸過程中的分布愈加均勻, 進而使網絡的傳輸容量整體提升, 所以BA 無標度網絡及WS 小世界網絡的傳輸容量隨著網絡的通信序列熵的增大而增大, 成正關聯關系.通信序列熵亦可成為評估同種類型但不拓撲同結構網絡的傳輸容量的指標.

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

圖4 數據包負載 (traffic load) 在網絡中節點度值上的分布情況 (a) BA 無標度網絡; (b) WS 小世界網絡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 網絡的通信序列熵 S N 與平均路徑長度 〈 L〉 的關系 (a) BA 無標度網絡; (b) WS 小世界網絡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 網絡的通信序列熵 S N 與節點的最大介數 B max 的關系 (a) BA 無標度網絡; (b) WS 小世界網絡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.

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

4 結 論

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