復雜耦合網絡交通動力學模型研究

馬金龍,李 敏,2

(1.河北科技大學信息科學與工程學院,河北石家莊 050018;2.南京郵電大學自動化學院、人工智能學院, 江蘇南京 210023)

復雜網絡理論是研究現實中各類網絡結構與功能的重要工具[1]。如今網絡中的數據量發生急劇增長[2],比如:交通網絡中交通車輛的增加[3-4];通信網絡中用戶及服務的增加;電力網中用電的增加[5]。隨著網絡中信息的不斷增加,網絡交通容量要有一定的增加,才能與之相匹配[6-7]。網絡由節點和連邊構成,已有大量學者對網絡關鍵節點[8]、網絡結構[9]進行了研究。而在網絡交通動力學方面,網絡交通動力學模型對研究網絡交通行為具有重要意義。

在單層網絡模型中,反映網絡中信息交通情況的經典模型為隨機行走[10],但是該模型無法精確反映現實網絡中信息的交通過程。文獻[11]在層次網絡上研究了信息的交通情況,提出了一種簡單的分層分支網絡交通動力學模型。文獻[12]提出2種交通動力學模型,并針對不同結構的網絡節點的信息處理能力對網絡性能的影響進行了研究。文獻[13]在一定路由規則下提出了一種交通動力學模型,并研究了該交通模型中交通容量的時間相關性。以上交通動力學模型均是在單層網絡的交通動力學的基礎上提出來的,然而現實中許多網絡都具有多層耦合結構。文獻[14]引入分層的思想,提出一種雙層網絡模型,該雙層網絡由物理層和邏輯層耦合構成,在此類耦合網絡中,邏輯層并沒有參與信息的交通過程,另一類耦合網絡中每一層都具有交通功能,例如由高速層和低速層耦合構成的雙層網絡[15]。文獻[16]—文獻[19],在相同交通動力學模型下,對網絡交通容量進行了策略研究?？紤]到現實網絡的情況,本文提出一種新的耦合網絡交通動力學模型,在此動力學模型中,網絡中所有的節點都能夠產生信息,并且所有信息通過節點之間的交通都需要消耗代價。這種新的交通動力學模型更能夠反映現實中的情況。

1 模 型

1.1 耦合網絡模型

耦合網絡由低速層A和高速層B構成,并且低速層和高速層均是由無標度網絡模型構建而成[20]。耦合網絡生成過程如下。

1)生成具有無標度網絡特性的低速層結構模型,設低速層的節點數為NA。

3)高速層也是由無標度網絡模型構建,網絡節點數為NB,標記高速層節點為vB。

4)將高速層節點vB與低速層中對應節點vA進行一一匹配,稱為一對耦合節點。耦合節點之間的交通方式與交通速度是不相同的。

按以上方法生成耦合網絡,如圖1所示。從耦合網絡示意圖中可以看出低速層A中有一部分節點是沒有與之對應的耦合節點的,高速層B的節點是低速層A的子集,但是2個子層的結構不同。耦合節點之間由黑色虛線相連。

圖1 耦合網絡模型Fig.1 Coupled network model

1.2 改進的交通動力學模型

在由低速層和高速層耦合而成的網絡交通動力學模型中,網絡中所有節點都能夠產生和傳遞信息,并且耦合節點之間信息的交通需要消耗時間。為了方便研究,假設網絡中所有節點的信息處理能力都是相等的,設低速層的節點處理能力為CA,高速層的節點處理能力為CB,則有CA=CB=C。在每個時間步內,低(高)速層每個節點最多處理CA(CB)個信息。由于節點處理能力有限,因此隨著信息產生率的不斷增大,未被及時處理的信息在節點處排隊等待,形成節點緩沖隊列,并等待處理。交通過程如下。

1)信息的產生 每一個時間步,網絡中都產生R個信息,產生的信息都隨機選擇源節點和目的節點,要保證這2個節點不是相同節點,遵循傳輸流分配路由策略[16]選擇一條有效交通路徑。在面對多條路徑的情況下,隨機選擇一條路徑進行信息交通。

2)信息交通過程 在每個時間步內,每個節點都最多能處理C個信息。隨著信息產生速率的增大,會有越來越多的信息在節點緩存隊列中等待處理。在這種情況下,每個時間步,節點最多處理其緩存隊列中前C個信息。如果節點被傳輸到目的節點,則將該信息在網絡中刪除。另外,每個時間步,信息只能進行一次傳遞。

耦合網絡信息的有效交通過程如圖2所示。信息隨機選擇源節點和目的節點,確定有效交通路徑P(s→t)={s→iA→iB→jB→tB→tA}。在T1時刻,信息從源節點s傳遞到下一跳節點iA;在T2時刻,信息從節點iA傳遞到其耦合節點iB;在T3時刻,信息從節點iB傳遞到下一跳節點jB;在T4時刻,信息從節點jB傳遞到下一跳節點tB;在T5時刻,信息從節點tB傳遞到其耦合節點tA,此時信息到達目的節點,完成交通過程。

2 性能參數

為了研究耦合網絡的信息交通動力學過程,引入以下性能參數對其性能進行分析評估。

1)序參量H該參數能夠反映網絡中信息交通狀態的變化,其關系式為

(1)

式中,〈ΔW〉=W(t+Δt)-W(t),其中〈…〉表示Δt時間段內的平均值,W(t)表示在t時間系統中信息的數量,也就是說網絡中沒有到達目的節點的信息數量。根據序參量H和信息產生速率R的變化關系,可以得到網絡處于臨界狀態的閾值Rc。Rc是反映網絡交通容量的關鍵值。

2)耦合系數λ為了觀察信息在網絡中的交通狀況,引入了耦合系數λ,其表達式為

(2)

3)有效邊比例函數δ為更清楚地反映信息交通過程中通過不同層的情況,引入了有效邊比例函數,其表達式為

(3)

4)平均有效路徑長度〈d〉 該參數可以反映信息的交通情況,平均距離的長短反映節點之間傳遞信息的困難程度,其表達式為

(4)

式中:dst(αF,βF)表示節點s和t之間的有效路徑長度;N表示網絡中的總節點數;〈d〉的值越小,表示信息需要越短的路徑就可以到達目的節點。

3 仿真實驗與分析

3.1 仿真實驗參數設置

在仿真實驗中,設置由BA無標度網絡模型[20]構成的低速層網絡,其規模為NA=600,〈kA〉=8,由BA無標度網絡模型構成的高速層網絡規模是低速層的一半,即NB=300,〈kB〉=4。設網絡中所有節點的信息處理能力均為1,即C=CA=CB=1,并且選擇在交通流分配路由策略下進行仿真實驗。有效路徑函數的表達式為

(5)

式中,該路由策略引入了層間控制參數αF和層內控制參數βF,其中F代表不同網絡層,F∈(A,B)。αF來控制F層中信息的傳遞速度,當αA>αB時,信息在A層傳遞所需時間比在B層長,B層的傳遞速度更快,反之,信息在A層傳遞所需時間比在B層短,B層的傳遞速度更慢;βF用來控制信息在層內傳遞過程中對不同度數節點的選擇情況,當βF>0時,信息在選擇下一跳的節點時,偏向選擇度數小的節點,反之,偏向選擇度數大的節點。在BA無標度網絡中,當βA≈1時,網絡的交通容量達到最大[21],因此設置控制參數αA=1和βA=1,為了體現層之間速度的不同, 設置αB=0.5,此時高速層B的交通速度是低速層A的2倍。

3.2 仿真結果分析

圖3反映了在參數βB取不同值的情況下,序參量H隨信息產生速率R的變化趨勢。當R較小時,H基本不變,H≈0,隨著信息產生速率R的不斷增大,H也隨之迅速增大,并且不同參數βB對應的閾值Rc也是不同的。從圖4中可以發現,網絡規模NA分別為400和600時,網絡交通容量Rc表現出與層內控制參數βB非單調變化的結果,當βB=3.8時,網絡交通容量Rc較大,并且最優控制參數βB不受網絡規模的影響,因此當低速層網絡規模NA分別為400和600時,它們對應的最優層內控制參數βB=3.8。

圖3 序參量H隨信息產生率R的變化關系Fig.3 Relationship between order parameter H and information generation rate R

圖4 不同規模NA下,交通容量Rc隨層內控制參數βB的變化關系Fig.4 Relationship between the traffic capacity Rc and the intralayer control parameter βB under the different sizes NA

此外,網絡交通容量Rc與信息的平均交通時間〈T〉有關。一般平均交通時間越短,其網絡交通容量越大。如圖5所示,可以看出平均交通時間隨信息產生速率的變化趨勢與序參量隨信息產生速率的變化趨勢一致。當信息產生速率R較小時,平均交通時間基本不變,當R增大到一定程度時,平均交通時間迅速增大。圖5所示結果與理論“網絡交通容量越大,平均交通時間越短”相符。

圖5 平均交通時間〈T〉隨信息產生速率R的變化關系Fig.5 Relationship between the average traffic time 〈T〉 and information generation rate R

圖6研究了耦合系數λ隨控制參數βB的變化情況,控制參數βB的取值范圍是0～6,耦合系數λ的結果范圍是0.3～1.0。由于信息隨機選擇網絡中的節點,因此會有一部分信息選擇高速層B為源節點或目的節點,耦合系數必然是大于0的值。此外,當控制參數βB值較小時,信息通過高速層B的節點進行交通可以使有效路徑函數值最小,因此耦合系數λ的值高達1,但是隨著參數βB的不斷增大,為保證有效路徑函數值最小,網絡中產生的信息將不再通過B層進行交通,因此耦合系數λ的值不斷減小。并且當參數βB>3.8時,耦合系數變化幅度很小,此時信息交通路徑的選擇不再受參數βB的影響。圖7研究了有效邊比例函數δ隨層內控制參數βB的變化情況,其與圖6的變化趨勢是一致的,當參數βB≤3.8時,信息交通路徑會受其影響,表現為參數越小,越多的信息選擇通過B層進行交通,反之,則會很少有信息通過B層交通。并且,當參數βB>3.8時,信息則基本不會通過B層交通。圖8同樣也反映出,平均有效路徑長度〈d〉在控制參數βB≤3.8時會發生變化,當參數βB>3.8時,平均有效路徑長度〈d〉將基本不會受到影響。

圖6 耦合系數λ隨層內控制參數βB的變化關系Fig.6 Relationship between the coupled coefficient λ and the intralayer control parameter βB

圖7 有效邊比例函數δ隨層內控制參數βB的變化關系Fig.7 Relationship between the effective edge ratio δ and the intralayer control parameter βB

圖8 平均有效路徑長度〈d〉隨層內控制參數βB的變化關系Fig.8 Relationship between the average length of effective path 〈d〉 and the intralayer control parameter βB

4 結 語

通過分析實際網絡中信息的產生和傳遞過程,提出了一種基于復雜耦合網絡的改進交通動力學模型。改進的模型重點考慮了信息在通過層間進行傳遞時需要消耗的代價,更準確地反映了現實交通網絡之間信息的傳遞情況。并在基于無標度網絡構建的復雜耦合網絡上對改進的交通動力學模型進行了仿真實驗,研究了其網絡交通容量的動態變化情況。具體結論如下。

1)當層內控制參數為3.8時,網絡交通容量達到最大,并且在低速層網絡規模為400和600時,網絡最大傳輸容量對應的最優層內控制參數均為3.8。可知,最優控制參數與網絡規模無關。

2)隨著層內控制參數的增大,網絡中信息通過低速層進行交通的比例也逐漸增大,并且當控制參數增大到3.8左右時,耦合系數在0.3上下微小變化,有效邊比例趨于0.1,平均有效路徑長度在4.7上下微小變化。這表明,在層內控制參數增大到3.8之后,其對網絡中信息傳遞過程的影響甚小。

通過提出的改進交通動力學模型及其仿真統計結果得到的交通動力學特征,對于交通網絡擁塞問題的緩解具有指導意義。在接下來的研究中,計劃獲取鐵路網和航空網數據來構建真實網絡,對耦合網絡的交通動力學作進一步的實證研究。