層間耦合關聯對多層網絡交通傳輸的影響

胡亞琴, 唐 明

（1. 華東師范大學 通信與電子工程學院, 上海 200241;2. 華東師范大學 物理與電子科學學院, 上海 200241）

0 引 言

當今社會是一個高速發展的信息時代, 網絡無處不在, 且在生產生活中發揮著重要的作用, 如社交網絡[1]、交通網絡[2]等. 隨著社會的發展與經濟的進步, 網絡中的用戶量與日俱增, 網絡中的數據也隨之呈現出爆發式增長. 龐大的數據量會使網絡中出現部分節點負荷過載, 這種超負載會逐漸向整個網絡蔓延, 最終造成網絡擁塞甚至網絡崩潰[3]. 而現代社會人們對網絡傳輸速度與傳輸質量的要求卻越來越高, 因此提高網絡的承載能力和傳輸容量非常必要且具有重要意義.

此前關于提高網絡傳輸容量的研究大多集中于孤立的網絡[4-6], 但是現實社會中的大多數基礎設施并不是獨立存在的, 而是相互耦合或相互依賴在一起的, 形成了多層網絡, 如鐵路-航空網絡、公交-地鐵網絡. 由于多層網絡模型更能實際地反映現實世界中的網絡結構, 因此越來越多的學者開始研究多層網絡上的動力學行為[7-12]. Aleta等[9]提出了按交通線或輸運工具分層的方式, 將公共交通系統建模為多重網絡模型, 并分析了9個真實的城市交通的網絡結構來測試和完善模型. Guo等[10]根據隨機游走模型—Lévy, 研究了一種基于多層網絡的新型導航策略, 并得到了到達網絡中任意節點所需的平均時間的表達式. Ma等[11]基于節點介數提出了一種改進的全局感知路由策略, 相較于最短路徑和經典的全局感知路由策略, 改進的全局感知路由策略能更好地提高網絡容量.

一些研究發現, 多層網絡的傳輸容量不僅與其拓撲結構、路由策略和網絡資源有關, 還與多層網絡中層與層之間的耦合方式息息相關. Wu等[13]利用模擬退火(Simulated Annealing, SA)算法得到的最佳層間耦合配置, 與同配耦合、異配耦合和隨機耦合相比, 其得到的耦合配置更能顯著地提高多層網絡的傳輸容量. Chen等[14]提出了一種層間反同配耦合(Anti-Assortative Coupling)機制, 并根據節點介數得出了雙層網絡傳輸容量的理論值. 本文在這些研究的基礎上, 基于層間節點的度-度相關性,提出了一種中間度耦合方式: 層間節點按照度值大小進行排序, 在中間度值的節點之間首先建立連接.并且基于雙層網絡模型, 分別在最短路徑和有效路由[15]兩種經典的路由策略下, 對比同配耦合、異配耦合和隨機耦合這3種耦合方式, 驗證本文提出的中間度耦合方式的有效性. 驗證發現, 本文的中間度耦合方式能夠使多層網絡中流量的分布更加均勻, 有效提升了網絡的傳輸容量, 且數據包在網絡中的平均傳輸時間也較小; 尤其是在層間耦合概率較低時, 即耦合成本較低時, 相較于其他3種耦合方式, 中間度耦合方式更能明顯提高網絡傳輸容量, 降低平均傳輸時間, 保證了網絡整體的傳輸性能.

1 模 型

1.1 網絡模型

為簡化流程, 本文采用雙層網絡模型來進行實驗, 雙層網絡模型的上層為A層, 下層為B層. 考慮到現實中系統大多具有無標度網絡的特性, 因此A層、B層均為無標度網絡. 假設層間互連的節點是一對一的, 即每一個節點至多有一條邊連接到另一層網絡, 層間的耦合概率定義為

首先計算網絡中所有節點的度值并排序(按照A層、B層單獨的網絡結構), 然后將節點按照要求一一耦合. 按照度-度相關性, 本文研究了以下4種層間耦合方式.

(1)同配耦合(Assortative Coupling, AC)方式: 即正相關連接.A層、B層節點按照度值大小排列,A層度值最大的節點與B層度值最大的節點相連,A層度值第二大節點與B層度值第二大節點相連. 重復此過程, 直到層間耦合概率達到p.

(2)異配耦合(Disassortative Coupling, DC)方式: 即負相關連接.A層、B層節點按照度值大小排列,A層度值最大的節點與B層度值最小的節點相連,A層度值第二大節點與B層度值第二小節點相連. 重復此過程, 直到層間耦合概率達到p.

(3)隨機耦合(Random Coupling, RC)方式: 隨機選擇1個A層節點和1個B層節點, 如果2節點間沒有耦合鏈接, 則將它們連接起來; 否則, 重新隨機選擇節點對, 并檢查是否存在鏈接. 重復此過程,直到層間耦合概率達到p.

(4)中間度耦合(Middle-degree Coupling, MC)方式: 將A層、B層節點按照度值大小排列,A層中間度值的節點與B層中間度值的節點相連,A層中間度值加1的節點與B層中間度值加1的節點相連,A層中間度值減1的節點與B層中間度值減1的節點相連. 重復此過程, 直到層間耦合概率達到p.值得注意的是, 當p=1 時, 中間度耦合方式與同配耦合方式相同.

1.2 交通模型

在本文中, 雙層網絡中的所有節點均具有主機和路由器功能, 即每個節點既能產生數據包, 也能轉發數據包. 網絡中的交通模型流程如下.

步驟1: 每個時間步網絡中會產生R個數據包(數據包產生率), 并被隨機賦予源節點、目的節點.

步驟2: 假設雙層網絡中每個節點的處理能力相同, 用C表示, 即每個節點每個時間步中最多可以處理C個數據包, 且數據包在層內和層間傳遞時每一跳的花費相同. 數據包在生成后, 被放置在節點隊列長度的隊尾, 按照先進先出的規則等待處理.

步驟3: 遍歷所有的鄰居節點, 如果鄰居節點中有目的節點則直接傳給目的節點, 否則數據包將按照給定的路由策略選擇下一跳節點, 在網絡中進行傳輸, 本文采用最短路徑和有效路由兩種經典的路由策略.

步驟4: 數據包一旦到達目的節點就會被刪除, 否則在網絡中繼續排隊等待傳輸.

數據包在網絡中的傳輸過程的流程圖如圖1所示.

圖 1 數據包傳輸過程的流程圖Fig. 1 Flow chart of the data packet transmission process

1.3 路由策略

本文主要是研究不同的層間耦合方式對網絡傳輸容量的影響, 數據包分別在最短路徑(Shortestpath, SP)和有效路由(Efficient-routing, ER)這兩種經典的路由策略下傳輸.

(1)最短路徑(SP)策略

最短路徑策略, 顧名思義, 數據包在源節點與目的節點之間選擇跳數最少的路徑進行傳輸, 如存在多條相同的最短路徑, 則隨機選擇一條進行傳遞, 每個節點的路由信息保存在各自的路由表中.

(2)有效路由(ER)策略

網絡中源節點s與目的節點t之間的路徑, 如

其中,xl表示第l跳節點, 源節點s經過n跳到達目的節點t. 源節點s到目的節點t的有效距離定義為

1.4 衡量指標

不同的數據包產生率會給網絡帶來不同的負載, 數據包產生率(每個時間步產生的數據包數量,用R表示)較低時, 網絡處于自由態時, 幾乎不存在數據包堆積; 隨著R的增大, 網絡逐漸出現擁塞現象. 這里引入網絡傳輸閾值的概念, 網絡傳輸閾值指的是網絡從自由態向擁塞態轉變時單位時間步內產生的數據包數目, 用Rc來表示. 當R＜Rc時, 網絡中生成的數據包都能被及時處理, 網絡中流量處于平衡狀態, 無數據包堆積, 即自由態; 當R＞Rc時, 網絡中生成的數據包數量大于被移除的數據包,產生大量數據包堆積, 不能及時到達目的節點, 即擁塞態; 當R=Rc時, 網絡處于從自由態到擁塞態的相變狀態, 網絡中生成的數據包數量恰好與被移除的數據包持平, 即臨界狀態.

為了更好地量化網絡中的擁塞程度, 我們引入序參量H來刻畫, 即

本文設定每個節點的處理能力為C, 要求網絡中不出現擁塞, 則每個時間步每個節點處的數據包都能被及時處理, 即qv≤C, 代入式(6)得到

其中,Ts,t(β) 表示在數據包從源節點s到達目的節點t所需要的傳輸時間,m表示到達目的節點的數據包數量. 數據包的平均傳輸時間越小, 即越快到達目的節點, 說明網絡中數據包傳輸效率越高.

2 仿 真

本文主要是研究不同的層間耦合方式對網絡傳輸容量的影響, 并進行了一系列的仿真實驗. 考慮到實際網絡的特性, 文中雙層網絡的上下兩層均為無標度網絡模型,A層、B層網絡規模為NA=NB=500,〈kA〉=〈kB〉=8 , 層間耦合概率p=0.5 , 節點處理能力C=1 , 數據包分別采用最短路徑和有效路由兩種策略在網絡中傳輸. 為了消除偶然誤差, 本文的實驗結果均由10個不同的雙層網絡獨立仿真100次后平均得到.

數據包采用ER策略在網絡中傳輸時, 分別研究了在AC方式、DC方式、RC方式和MC方式這4種耦合方式下, 網絡的傳輸容量Rc與可調參數β的關系, 如圖2所示. 由圖2可以看到, 在每一種耦合方式下, 傳輸容量的仿真值與理論值幾乎吻合, 其中理論值由公式(8)計算得到. 網絡傳輸容量Rc在4種耦合方式下均呈現出先增加后減小的趨勢, 且均在可調參數β約為0.6時達到最大值, 分別為114、108、111和122. 相較于AC方式、DC方式和RC方式, MC方式下的網絡傳輸容量分別提高了7.0%、13.0%和9.9%, 這說明MC方式能使負載更均勻地分布在網絡中, 更合理地分配了網絡資源.

圖3是數據包分別采用SP策略或ER策略在網絡中傳輸時, 4種耦合方式下序參量H與數據包產生率R的關系. 在4種層間耦合方式下, 序參量H均隨數據包產生率R呈現單調遞增, 且存在相變點, 即網絡傳輸容量Rc. 在數據包產生率較低的時候, 序參量為0, 網絡處于自由態, 網絡中的數據包能及時到達目的節點. 一旦數據包產生率超過閾值Rc, 序參量呈指數增加, 大量數據包堆積在網絡中導致擁塞加劇. 從圖3可以看出, 數據包無論采用SP策略還是ER策略傳輸, MC方式下的傳輸容量Rc均大于AC方式、DC方式和RC方式, 且隨著數據包產生率逐漸增加, MC方式下的序參量增長速度相對平緩, 即網絡擁塞程度增長最慢, 這也進一步說明MC方式的有效性.

數據包的平均傳輸時間〈T〉也是一個重要的衡量網絡性能的指標, 平均傳輸時間越短, 說明數據包越快到達目的節點. 本文研究了在SP策略和ER策略下, 4種不同耦合方式對數據包在網絡中的傳輸時間的影響. 在數據包產生率較低時, 網絡處于自由態, 4種耦合方式下的數據包平均傳輸時間都較低, 說明數據包幾乎都可以很快地到達目的節點. 隨著數據包產生率增加, 網絡中逐漸出現擁塞, 平均傳輸時間迅速增加, 這可能是因為部分節點過載, 數據包產生后不能被及時處理, 長時間在網絡中排隊等待, 導致擁塞加劇. 如圖4所示, 可以看到在SP策略和ER策略下, MC方式下的數據包平均傳輸時間均低于AC方式、DC方式和RC方式, 這可能是因為MC方式下, 層間傳輸主要通過中間度節點來完成, 緩解了上下兩層的中心節點的壓力, 減少了等待時間, 使數據包能很快達到目的節點.

圖 2 ER策略下網絡傳輸容量 R c 與可調參數 β 的關系Fig. 2 The relationship between the traffic capacity, R c , of multilayer networks and the adjustable parameter, β , under the ER strategy

圖 3 4種耦合方式下序參量 H 與數據包產生率 R 的關系Fig. 3 The relationship between the order parameter, H , and the packet generation rate,R, under four different coupling patterns

圖 4 4種耦合方式下平均傳輸時間 〈 T〉 與數據包產生率 R 的關系Fig. 4 The relationship between the average transport time, 〈 T〉 , and the packet generation rate, R , under four different coupling patterns

本文還研究了在4種層間耦合方式下, 網絡的傳輸容量與層間耦合概率的關系, 仿真結果如圖5所示. 圖5(a)中數據包采用SP策略進行傳輸, 可以看到與AC方式、DC方式和RC方式相比, 層間采用MC方式耦合時, 網絡傳輸容量明顯提高. 圖5(b)中數據包采用ER策略進行傳輸, 可以看到在多層網絡的層間耦合概率較低的時候, AC方式、DC方式和RC方式下網絡的傳輸容量差異不大, 而MC方式下網絡傳輸容量明顯較高, 且隨著耦合概率的增加, 4種耦合方式給傳輸容量造成的差異減小. 數據包無論按照SP策略還是ER策略傳輸, 當p=1 時, MC方式與AC方式下網絡的傳輸容量一樣. 從圖5還可以看出, 在4種不同的耦合方式下, 網絡的傳輸容量均隨著耦合概率的增加而增加, 這可能是因為層間耦合概率增加, 也就是層間的鏈接數量增加, 數據包在層間的傳輸可通過更多的中繼節點來完成, 從而增加了整個網絡的傳輸容量.

圖 5 網絡傳輸容量 R c 與層間耦合概率 p 的關系Fig. 5 The relationship between the traffic capacity, R c , of multilayer networks and the coupling probability,p

為了更好地說明層間耦合關聯對多層網絡傳輸能力的一般性影響, 本文增加了A、B均為隨機網絡[16]的仿真實驗, 與上述相同,A層、B層的網絡規模為NA=NB=500 ,〈kA〉=〈kB〉=8 , 層間耦合概率p=0.5 , 節點處理能力C=1 . 網絡的傳輸容量Rc與可調參數β的關系如圖6所示, 其中β=0 時,數據包可以理解成按照最短路徑策略傳輸. 數據包按照SP策略傳輸時, AC方式、DC方式、RC方式和MC方式下, 網絡最大傳輸容量分別為95、109、99和126; 數據包按照ER策略傳輸時, AC方式、DC方式、RC方式和MC方式下, 網絡最大傳輸容量分別為184、183、188和194. 相較于其他3種耦合方式, 中間度耦合方式都能使網絡的傳輸容量達到最大, 最大限度地使流量合理地分布在雙層網絡中. 同時, 與A層、B層均為無標度網絡相比, 隨機網絡構成的雙層網絡的傳輸容量更大, 這說明了網絡結構越均勻, 網絡的傳輸容量越大, 異質網絡的傳輸容量較低.

圖 6 4種耦合方式下網絡傳輸容量 R c 與可調參數 β 的關系Fig. 6 The relationship between the traffic capacity, R c , of networks and the adjustable parameters, β , under four different coupling patterns

3 結 論

為提高多層網絡的傳輸容量, 基于層間節點的度-度相關性, 本文提出了一種中間度耦合方式, 并在BA-BA雙層網絡上進行了仿真驗證. 本文通過推導得到的網絡傳輸容量理論值與本文的實驗結果保持了一致. 在SP策略和ER策略下, 相較于AC方式、DC方式和RC方式, MC方式均能更合理地分配網絡中的負載, 提高了網絡的傳輸容量, 有效減小了數據包的平均傳輸時間. 本文還發現, 隨著層間耦合概率的增加, 網絡的傳輸容量也有所提高; 數據包采用ER策略傳輸時, MC方式在較低耦合概率下的表現尤為突出, 即網絡達到了更高的傳輸容量.A層、B層均為隨機網絡的仿真實驗, 說明了中間度耦合方式能更有效地提高網絡的承載能力, 且越均勻的網絡的傳輸容量越高.