耦合節(jié)點(diǎn)選擇對(duì)網(wǎng)絡(luò)交通動(dòng)力學(xué)的影響分析

景興利 胡茂彬

(1.濟(jì)源職業(yè)技術(shù)學(xué)院，河南 濟(jì)源 459000)(2.中國(guó)科學(xué)技術(shù)大學(xué) 工程科學(xué)學(xué)院，合肥 230026)

0 前 言

隨著經(jīng)濟(jì)和社會(huì)的發(fā)展，交通擁堵問(wèn)題越來(lái)越嚴(yán)重。如何解決交通擁堵問(wèn)題，提高交通效率，一直是交通問(wèn)題研究的熱點(diǎn)。在過(guò)去的20多年里，學(xué)者們致力于復(fù)雜網(wǎng)絡(luò)框架下的交通擁堵問(wèn)題，將真實(shí)網(wǎng)絡(luò)中傳輸或移動(dòng)的旅客、汽車、飛機(jī)甚至是信息抽象為復(fù)雜網(wǎng)絡(luò)中移動(dòng)的單元以揭示交通問(wèn)題的機(jī)理。研究表明，交通擁堵問(wèn)題的形成與交通網(wǎng)絡(luò)結(jié)構(gòu)密切相關(guān)[1-2]。為了提高網(wǎng)絡(luò)通行能力，減少交通擁堵，學(xué)者們提出了一系列措施用以改善網(wǎng)絡(luò)通行狀況，包括改變網(wǎng)絡(luò)結(jié)構(gòu)、設(shè)計(jì)更好的路由策略、優(yōu)化交通資源配置等[1，3-10]。然而，目前的大多數(shù)研究都集中于孤立網(wǎng)絡(luò)的建模和分析?，F(xiàn)代網(wǎng)絡(luò)系統(tǒng)中包含很多子網(wǎng)絡(luò)或子系統(tǒng)，且它們之間又互相聯(lián)系[11-12]。例如，城市交通網(wǎng)由道路網(wǎng)和地鐵網(wǎng)組成，運(yùn)輸網(wǎng)由鐵路網(wǎng)和航空網(wǎng)組成。耦合網(wǎng)絡(luò)中的交通問(wèn)題研究將為真實(shí)網(wǎng)絡(luò)中交通擁堵治理提供一定的思路。學(xué)者們將單層網(wǎng)絡(luò)的交通動(dòng)力學(xué)過(guò)程描述為旅客按照路由引導(dǎo)從起點(diǎn)流向終點(diǎn)的過(guò)程[13]。將該交通動(dòng)力學(xué)過(guò)程的概念推廣到耦合網(wǎng)絡(luò)，即成為耦合網(wǎng)絡(luò)的交通動(dòng)力學(xué)過(guò)程，但耦合網(wǎng)絡(luò)的交通動(dòng)力學(xué)特性與單層網(wǎng)絡(luò)有著明顯的不同[14-19]。Zhuo等人研究了物理層-邏輯層耦合網(wǎng)絡(luò)的交通動(dòng)力學(xué)特性，發(fā)現(xiàn)物理層越同構(gòu)，網(wǎng)絡(luò)的整體通行能力越大[20]。Morris等人研究了一個(gè)空間耦合網(wǎng)絡(luò)的交通輸運(yùn)過(guò)程，發(fā)現(xiàn)隨著耦合強(qiáng)度增加，輸運(yùn)的平均最短路徑長(zhǎng)度隨之減小[21]。Sole-Ribalta等人研究了一個(gè)標(biāo)準(zhǔn)化多層網(wǎng)絡(luò)模型的交通動(dòng)力學(xué)特性，認(rèn)為網(wǎng)絡(luò)層的耦合強(qiáng)度和耦合方式對(duì)多層網(wǎng)絡(luò)的通行能力有顯著影響[22]。Gao等人提出了考慮網(wǎng)絡(luò)局域信息和不同層間速度分布的有效路由策略，可以通過(guò)調(diào)節(jié)網(wǎng)絡(luò)的平均度和層間速度分布提高耦合網(wǎng)絡(luò)的通行能力[23]。

現(xiàn)有研究一般是基于隨機(jī)選擇節(jié)點(diǎn)進(jìn)行耦合而生成網(wǎng)絡(luò)，而不同耦合機(jī)制將對(duì)其網(wǎng)絡(luò)結(jié)構(gòu)和交通動(dòng)力學(xué)特性產(chǎn)生影響[20-23]。本次研究提出兩種新的網(wǎng)絡(luò)耦合機(jī)制：選擇度大節(jié)點(diǎn)進(jìn)行耦合和選擇度小節(jié)點(diǎn)進(jìn)行耦合，并分別將其與隨機(jī)耦合機(jī)制對(duì)網(wǎng)絡(luò)交通通行能力的影響進(jìn)行對(duì)比。為了進(jìn)一步揭示這3種不同機(jī)制生成的耦合網(wǎng)絡(luò)的動(dòng)力學(xué)特性，分析了其中的平均傳輸時(shí)間(〈T〉)、平均傳輸距離(〈h〉)和層間平均轉(zhuǎn)換次數(shù)(〈n〉)等運(yùn)行指標(biāo)。研究結(jié)果表明，選擇度小節(jié)點(diǎn)進(jìn)行耦合，可以達(dá)到更高的通行能力，并減少交通擁堵。本次研究為設(shè)計(jì)更加高效的交通傳輸網(wǎng)絡(luò)提供了一種新思路。

1 模型的建立

1.1 網(wǎng)絡(luò)模型

假設(shè)耦合網(wǎng)絡(luò)由低速層網(wǎng)絡(luò)A和高速層網(wǎng)絡(luò)B兩個(gè)子網(wǎng)絡(luò)組成[14，23]。由于高速層網(wǎng)絡(luò)的建設(shè)成本較高，所以其網(wǎng)絡(luò)規(guī)模小于低速層。例如鐵路-航空網(wǎng)，航空網(wǎng)的建設(shè)成本高于鐵路網(wǎng)，鐵路網(wǎng)的規(guī)模大于航空網(wǎng)，而航空網(wǎng)的旅行速度(成本)大于鐵路網(wǎng)。在此應(yīng)用Barabási-Albert(BA)網(wǎng)絡(luò)模型[24]建立節(jié)點(diǎn)總數(shù)為NA的低速層子網(wǎng)絡(luò)A，應(yīng)用Erd?-Rényi(ER)網(wǎng)絡(luò)模型[25]建立節(jié)點(diǎn)總數(shù)為NB的高速層子網(wǎng)絡(luò)B，NA>NB。

(1)隨機(jī)選擇節(jié)點(diǎn)進(jìn)行耦合。首先，構(gòu)建具有NA個(gè)節(jié)點(diǎn)的子網(wǎng)絡(luò)A；然后，在子網(wǎng)絡(luò)A中隨機(jī)選取NB個(gè)節(jié)點(diǎn)一一進(jìn)行復(fù)制，將其作為子網(wǎng)絡(luò)B的節(jié)點(diǎn)；最后，將子網(wǎng)絡(luò)B的節(jié)點(diǎn)按照ER網(wǎng)絡(luò)模型生成子網(wǎng)絡(luò)B[14，20，23]。

(2)選擇度大節(jié)點(diǎn)進(jìn)行耦合。復(fù)制子網(wǎng)絡(luò)A中的前NB個(gè)度大的節(jié)點(diǎn)作為子網(wǎng)絡(luò)B的節(jié)點(diǎn)，并相應(yīng)生成子網(wǎng)絡(luò)B。

(3)選擇度小節(jié)點(diǎn)進(jìn)行耦合。復(fù)制子網(wǎng)絡(luò)A中的前NB個(gè)度小的節(jié)點(diǎn)作為子網(wǎng)絡(luò)B的節(jié)點(diǎn)，并相應(yīng)生成子網(wǎng)絡(luò)B。

圖1所示為在不同耦合機(jī)制下生成的耦合網(wǎng)絡(luò)。圖中的實(shí)線圓圈表示子網(wǎng)絡(luò)A的節(jié)點(diǎn)，虛線圓圈表示子網(wǎng)絡(luò)B的節(jié)點(diǎn)(以下各圖相同)。每個(gè)圓圈中都標(biāo)注有該節(jié)點(diǎn)的屬性字符。例如，一個(gè)圓圈中標(biāo)注有“6(1)”，表示該節(jié)點(diǎn)的度為6，在該子網(wǎng)絡(luò)中所有節(jié)點(diǎn)度按照從大到小進(jìn)行排序，該節(jié)點(diǎn)位列第1。在圖1a中子網(wǎng)絡(luò)B為從子網(wǎng)絡(luò)A中隨機(jī)選擇的節(jié)點(diǎn)經(jīng)復(fù)制而生成的耦合網(wǎng)絡(luò)；圖1b中子網(wǎng)絡(luò)B為從子網(wǎng)絡(luò)A中選擇度大節(jié)點(diǎn)經(jīng)復(fù)制而生成的耦合網(wǎng)絡(luò)；圖1c中子網(wǎng)絡(luò)B為從子網(wǎng)絡(luò)A中選擇度小節(jié)點(diǎn)經(jīng)復(fù)制而生成的耦合網(wǎng)絡(luò)。

圖1 不同耦合機(jī)制生成的耦合網(wǎng)絡(luò)

1.2 交通模型

假設(shè)子網(wǎng)絡(luò)A的每個(gè)節(jié)點(diǎn)都可以產(chǎn)生和輸運(yùn)旅客，而子網(wǎng)絡(luò)B的節(jié)點(diǎn)僅用于輸運(yùn)旅客。旅客在耦合節(jié)點(diǎn)處可以通過(guò)層間連邊變換旅行的網(wǎng)絡(luò)層。這里假設(shè)層間轉(zhuǎn)換不消耗時(shí)間，每個(gè)節(jié)點(diǎn)在每個(gè)時(shí)間步發(fā)送旅客的能力為C。假設(shè)子網(wǎng)絡(luò)A節(jié)點(diǎn)和子網(wǎng)絡(luò)B節(jié)點(diǎn)的旅客發(fā)送能力相等且均等于1，即CA=CB=1。由于節(jié)點(diǎn)處理能力有限，每個(gè)節(jié)點(diǎn)都需要一個(gè)緩沖隊(duì)列來(lái)容納等待處理的旅客。假設(shè)緩沖區(qū)有足夠的長(zhǎng)度空間容納滯留旅客，在處理每個(gè)隊(duì)列的旅客時(shí)遵循先進(jìn)先出的原則。旅客在耦合節(jié)點(diǎn)處的輸運(yùn)方法見(jiàn)圖2，圓圈中的數(shù)字為節(jié)點(diǎn)編號(hào)。在〈T〉=1時(shí)間步，按照旅客到達(dá)節(jié)點(diǎn)6的先后順序進(jìn)行排隊(duì)，假設(shè)旅客a位于隊(duì)首，按照一定的導(dǎo)航策略，a的輸運(yùn)路徑為：…→6→6"→4→…；在〈T〉=2時(shí)間步，按照先進(jìn)先出及每個(gè)節(jié)點(diǎn)在每個(gè)時(shí)間步的旅客發(fā)送能力CA=1的原則，節(jié)點(diǎn)6僅能將旅客a輸運(yùn)到6"處，由于6與6"為耦合節(jié)點(diǎn)，那么旅客a將直接被輸運(yùn)至節(jié)點(diǎn)4處。耦合網(wǎng)絡(luò)上的交通傳輸過(guò)程可以被描述如下：每個(gè)時(shí)間步，在子網(wǎng)絡(luò)A上產(chǎn)生R個(gè)旅客，他們的出發(fā)點(diǎn)和目的地節(jié)點(diǎn)分別為在子網(wǎng)絡(luò)A上隨機(jī)選擇的不同節(jié)點(diǎn)。每個(gè)旅客按照既定的路由策略從出發(fā)點(diǎn)到達(dá)目的地節(jié)點(diǎn)，如果到達(dá)目的地節(jié)點(diǎn)，則從網(wǎng)絡(luò)中移除。顯然旅客從出發(fā)點(diǎn)i到達(dá)目的地節(jié)點(diǎn)j的路徑有很多，這里以Yan、Gao等人提出的有效路由策略作為旅客的傳輸路徑Pi→j進(jìn)行導(dǎo)航[4，23]：

圖2 耦合節(jié)點(diǎn)處旅客輸運(yùn)方法示意圖

(1)

式中：αF(αF>0)為旅客在F(F∈{A，B})層傳輸速度的調(diào)控參數(shù)，αF越小則在相應(yīng)層的傳輸速度越快;kx為節(jié)點(diǎn)x的度；l為路徑長(zhǎng)度；θF為旅客在F層傳輸時(shí)，通過(guò)節(jié)點(diǎn)度來(lái)控制傳輸偏好的調(diào)控參數(shù)。旅客在從i到j(luò)的路徑中選擇旅行成本最小的路徑：當(dāng)θF<0(θF>0)時(shí)，旅客將優(yōu)先選擇F層中選擇度大(小)的節(jié)點(diǎn)進(jìn)行傳輸;當(dāng)θF=0時(shí)，為最短路徑路由策略。在最短路徑路由策略中，網(wǎng)絡(luò)擁堵總是最先出現(xiàn)在中心(Hub)節(jié)點(diǎn)，Yan等人在單層網(wǎng)絡(luò)上通過(guò)改變?chǔ)戎?，引?dǎo)旅客向選擇度小節(jié)點(diǎn)傳輸，提高了網(wǎng)絡(luò)的通行能力[4]。在此，僅對(duì)θF≥0的情況進(jìn)行分析。按照上述交通傳輸過(guò)程的描述，旅客的輸運(yùn)過(guò)程算法流程如圖3所示。

圖3 旅客在網(wǎng)絡(luò)中的輸運(yùn)算法流程圖

網(wǎng)絡(luò)的最大通行能力可以通過(guò)旅客臨界產(chǎn)生率Rc來(lái)度量。Rc可以通過(guò)分析序參量η得到[4]：

(2)

ΔNp=Np(t+Δt)-Np(t)

式中：Np(t)為在t時(shí)間步時(shí)網(wǎng)絡(luò)中的旅客總數(shù)?！处p〉表示對(duì)所有的仿真時(shí)間窗口Δt取平均。當(dāng)RRc時(shí)，η>0網(wǎng)絡(luò)為擁堵?tīng)顟B(tài)。相變點(diǎn)R=Rc為網(wǎng)絡(luò)交通為自由流狀態(tài)和擁堵?tīng)顟B(tài)的臨界值，可用于表征網(wǎng)絡(luò)的通行能力。

2 仿真結(jié)果及分析

基于有效路由策略,分別對(duì)3種不同機(jī)制耦合網(wǎng)絡(luò)的交通動(dòng)力學(xué)特性進(jìn)行仿真分析。耦合網(wǎng)絡(luò)節(jié)點(diǎn)總數(shù)(N)為2 000，子網(wǎng)絡(luò)A的節(jié)點(diǎn)數(shù)(NA)為1 500，子網(wǎng)絡(luò)B的節(jié)點(diǎn)數(shù)(NB)為500。A、B子網(wǎng)絡(luò)的平均度相等，即==6。對(duì)于單層網(wǎng)絡(luò)的有效路由策略[4，20]，θA=1.0時(shí)，網(wǎng)絡(luò)可取得最大臨界旅客產(chǎn)生率。根據(jù)對(duì)αF的定義，αB/αA可調(diào)控旅客在兩層網(wǎng)絡(luò)中的傳輸速度，在以下仿真過(guò)程中不作特殊說(shuō)明時(shí)設(shè)αA=1.0，θA=1.0，通過(guò)調(diào)控其他參數(shù)來(lái)分析不同耦合網(wǎng)絡(luò)的交通動(dòng)力學(xué)特性。每次仿真模擬系統(tǒng)運(yùn)行總計(jì)20 000個(gè)時(shí)間步。

圖4為3種不同機(jī)制下生成的耦合網(wǎng)絡(luò)采用有效路由策略時(shí)，取不同的調(diào)控參數(shù)αB和θB對(duì)應(yīng)的交通流相變情況的仿真結(jié)果(Random:隨機(jī)選擇節(jié)點(diǎn)進(jìn)行耦合;Small First:選擇度小節(jié)點(diǎn)進(jìn)行耦合;Large First:選擇度大節(jié)點(diǎn)進(jìn)行耦合)。選擇度大節(jié)點(diǎn)進(jìn)行耦合，當(dāng)αB=0.2，θB=1.5時(shí)，取得最大臨界旅客產(chǎn)生率Rc≈129；選擇度小節(jié)點(diǎn)進(jìn)行耦合，當(dāng)αB=0.1，θB=1.6時(shí)，取得最大臨界旅客產(chǎn)生率Rc≈159；隨機(jī)選擇節(jié)點(diǎn)進(jìn)行耦合，當(dāng)αB=0.4，θB=1.2時(shí)，取得最大臨界旅客產(chǎn)生率Rc≈138。因此，選擇度小節(jié)點(diǎn)進(jìn)行耦合，其網(wǎng)絡(luò)具有更優(yōu)的通行能力。

圖4 不同耦合機(jī)制下的網(wǎng)絡(luò)交通流相變情況仿真結(jié)果

圖5為臨界旅客產(chǎn)生率隨不同調(diào)控參數(shù)的變化情況。由圖5a知，選擇度大節(jié)點(diǎn)、隨機(jī)選擇節(jié)點(diǎn)進(jìn)行耦合時(shí)，Rc隨著αB增大均先增大后減??；選擇度小節(jié)點(diǎn)進(jìn)行耦合時(shí)，Rc隨著αB增大而減小。由圖5b知，3種不同耦合機(jī)制下Rc均隨著θB增大先增大后減小。這進(jìn)一步證明，選擇度小節(jié)點(diǎn)進(jìn)行耦合其網(wǎng)絡(luò)可取得最優(yōu)通行能力。研究表明，在相同條件下，網(wǎng)絡(luò)度分布越均勻，Rc越大[24]。選擇度小節(jié)點(diǎn)進(jìn)行耦合生成的網(wǎng)絡(luò)度分布最均勻，隨機(jī)選擇節(jié)點(diǎn)進(jìn)行耦合次之，而選擇度大節(jié)點(diǎn)進(jìn)行耦合生成的網(wǎng)絡(luò)度分布最不均勻。因此，選擇度小節(jié)點(diǎn)進(jìn)行耦合時(shí)，其網(wǎng)絡(luò)能獲得更大的通行能力。

圖5 臨界旅客產(chǎn)生率隨不同調(diào)控參數(shù)的變化情況

進(jìn)一步對(duì)耦合網(wǎng)絡(luò)的平均傳輸時(shí)間(〈T〉)、平均傳輸距離(〈h〉)、層間平均轉(zhuǎn)換次數(shù)(〈n〉)等交通動(dòng)力學(xué)特性刻畫(huà)指標(biāo)進(jìn)行分析[26-29]，結(jié)果如圖6、圖7所示。

平均傳輸時(shí)間定義為：

(3)

式中：m為到達(dá)目的地點(diǎn)的旅客總數(shù)；Tp為旅客p的旅行時(shí)間。為了提高網(wǎng)絡(luò)通行能力，必須降低傳輸時(shí)間。

平均傳輸距離定義為：

(4)

式中：hp為旅客p從始發(fā)點(diǎn)到目的地點(diǎn)所經(jīng)過(guò)的節(jié)點(diǎn)總數(shù)。平均傳輸距離受到調(diào)控參數(shù)αF和θF的影響。

層間平均轉(zhuǎn)換次數(shù)定義為：

(5)

式中：np為旅客p在完成從出發(fā)點(diǎn)到目的地點(diǎn)的傳輸過(guò)程中在A、B層間轉(zhuǎn)換的次數(shù)。

在自由流狀態(tài)下(Rc=10)，3種不同機(jī)制下生成的耦合網(wǎng)絡(luò)取最優(yōu)θB時(shí)，不同調(diào)控參數(shù)αB對(duì)應(yīng)的〈T〉、〈h〉、〈n〉等指標(biāo)的變化情況如圖6所示。3種耦合網(wǎng)絡(luò)隨著αB的增大，〈T〉和〈h〉均先迅速減小而后增大；在各耦合網(wǎng)絡(luò)最優(yōu)αB值處，分別取得了較小的〈T〉和〈h〉值。由圖6(c)知，隨著αB增大，3種耦合網(wǎng)絡(luò)的〈n〉均先單調(diào)下降后趨于穩(wěn)定。〈n〉在趨于穩(wěn)定前，選擇度大節(jié)點(diǎn)進(jìn)行耦合的網(wǎng)絡(luò)〈n〉對(duì)αB的變化最為敏銳，其次為選擇度小節(jié)點(diǎn)進(jìn)行耦合的網(wǎng)絡(luò)。當(dāng)選擇度小節(jié)點(diǎn)進(jìn)行耦合時(shí)，在最優(yōu)值αB=0.1處，〈n〉≈2.07；當(dāng)選擇度大節(jié)點(diǎn)進(jìn)行耦合時(shí)，在最優(yōu)值αB=0.2處，〈n〉≈1.48；當(dāng)隨機(jī)選擇節(jié)點(diǎn)進(jìn)行耦合時(shí)，在最優(yōu)值αB=0.4處，〈n〉≈1.36。在相同條件下，當(dāng)0.2≤αB≤2時(shí)，隨機(jī)選擇節(jié)點(diǎn)機(jī)制下網(wǎng)絡(luò)傳輸過(guò)程層間轉(zhuǎn)換較另外兩種機(jī)制下傳輸更加頻繁，但其對(duì)應(yīng)的〈T〉與〈h〉并非最小值。

圖6 不同交通動(dòng)力學(xué)特性刻畫(huà)指標(biāo)隨調(diào)控參數(shù)αB的變化情況

在自由流狀態(tài)下(Rc=10)，3種不同耦合網(wǎng)絡(luò)取最優(yōu)的αB時(shí)，不同調(diào)控參數(shù)θB對(duì)應(yīng)的〈T〉、〈h〉、〈n〉的變化情況如圖7所示。隨著θB的增大，〈T〉、〈h〉均先減小而后增大。在各耦合網(wǎng)絡(luò)的最優(yōu)θB值處，取得了較小的〈T〉和〈h〉值。由圖7(c)知，在相同條件下，選擇度小節(jié)點(diǎn)進(jìn)行耦合，〈n〉始終保持較大值。當(dāng)選擇度大節(jié)點(diǎn)進(jìn)行耦合時(shí)，由于BA、ER網(wǎng)絡(luò)的結(jié)構(gòu)性質(zhì)，耦合節(jié)點(diǎn)在BA層的鄰居節(jié)點(diǎn)度較大，而其在ER層的鄰居節(jié)點(diǎn)度較小(平均度約為6)。較小的θB不能改變度大節(jié)點(diǎn)被選作傳輸路徑的優(yōu)勢(shì)，表現(xiàn)為θB<1范圍內(nèi)，αB對(duì)〈n〉的影響較小。

圖7 不同交通動(dòng)力學(xué)特性刻畫(huà)指標(biāo)隨不同調(diào)控參數(shù)θB的變化情況

3 結(jié) 語(yǔ)

耦合網(wǎng)絡(luò)的交通動(dòng)力學(xué)是網(wǎng)絡(luò)交通領(lǐng)域研究的熱點(diǎn)問(wèn)題。為提高網(wǎng)絡(luò)的通行能力，提出了兩種新的節(jié)點(diǎn)選擇耦合機(jī)制。研究結(jié)果表明，包括常見(jiàn)的隨機(jī)選擇節(jié)點(diǎn)機(jī)制在內(nèi)，選擇度小節(jié)點(diǎn)進(jìn)行耦合生成的網(wǎng)絡(luò)能夠可以減少交通擁堵，獲取更大的網(wǎng)絡(luò)通行能力。

為揭示其中的機(jī)理，進(jìn)一步對(duì)耦合網(wǎng)絡(luò)的〈T〉、〈h〉、〈n〉等交通動(dòng)力學(xué)特性刻畫(huà)指標(biāo)進(jìn)行了分析。研究結(jié)果表明，選擇度小節(jié)點(diǎn)進(jìn)行耦合生成的網(wǎng)絡(luò)在〈T〉、〈h〉等方面較另外兩種耦合機(jī)制有明顯優(yōu)勢(shì)。