基于引力需求的輸運(yùn)網(wǎng)絡(luò)配流模型

韓景倜，李周平 ，2

（1.上海財(cái)經(jīng)大學(xué) 信息管理與工程學(xué)院，上海 200433；2.上海理工大學(xué) 管理學(xué)院，上海 200093）

0 引言

近幾年，諸如Internet與交通網(wǎng)絡(luò)中流量的分配與擁塞問題，成為復(fù)雜網(wǎng)絡(luò)研究的又一熱點(diǎn)。2004年Tadic等人[1]研究了WG、SF、RG三種網(wǎng)絡(luò)結(jié)構(gòu)對(duì)于網(wǎng)絡(luò)系統(tǒng)輸運(yùn)動(dòng)力學(xué)過程的影響作用。2005年Echenique等人[2]通過對(duì)最短路徑路由策略的優(yōu)化，提出了自意識(shí)路由策略，分析了自意識(shí)路由參數(shù)對(duì)于網(wǎng)絡(luò)輸運(yùn)性能的影響作用。2008年胡茂彬等人[3]基于節(jié)點(diǎn)容量與連邊權(quán)重，研究了加權(quán)網(wǎng)絡(luò)的輸運(yùn)配流問題。可以發(fā)現(xiàn)國(guó)內(nèi)外學(xué)者對(duì)于網(wǎng)絡(luò)輸運(yùn)問題的研究，主要關(guān)注于網(wǎng)絡(luò)結(jié)構(gòu)、路由策略對(duì)于網(wǎng)絡(luò)系統(tǒng)輸運(yùn)性質(zhì)的影響作用。但各類輸運(yùn)網(wǎng)絡(luò)模型中，對(duì)于網(wǎng)絡(luò)系統(tǒng)節(jié)點(diǎn)間輸運(yùn)需求的處理，卻采用以相同概率隨機(jī)選取兩節(jié)點(diǎn)作為輸運(yùn)需求的源節(jié)點(diǎn)與目地節(jié)點(diǎn)，并賦以一個(gè)常量作為輸運(yùn)需求量的簡(jiǎn)化處理方法。該方法認(rèn)為網(wǎng)絡(luò)系統(tǒng)中任意節(jié)點(diǎn)間產(chǎn)生輸運(yùn)需求的概率相同，而忽略了真實(shí)輸運(yùn)系統(tǒng)中，受節(jié)點(diǎn)強(qiáng)度與空間距離等因素影響的輸運(yùn)需求分布的異質(zhì)特性。

本文將借助引力模型預(yù)測(cè)輸運(yùn)網(wǎng)絡(luò)系統(tǒng)中節(jié)點(diǎn)間的潛在輸運(yùn)需求，以此反映真實(shí)輸運(yùn)系統(tǒng)中，由節(jié)點(diǎn)強(qiáng)度與距離阻抗因素所引起的輸運(yùn)需求的異質(zhì)性分布。并綜合考慮網(wǎng)絡(luò)結(jié)構(gòu)、路由策略、輸運(yùn)需求分布三方面因素，建立輸運(yùn)網(wǎng)絡(luò)中流量分配的仿真模型，重點(diǎn)分析輸運(yùn)需求的異質(zhì)性分布對(duì)于網(wǎng)絡(luò)系統(tǒng)輸運(yùn)能力的影響作用。

1 輸運(yùn)網(wǎng)絡(luò)配流模型

本文所提出的“基于引力需求的輸運(yùn)網(wǎng)絡(luò)配流模型”將基于特定的輸運(yùn)網(wǎng)絡(luò)結(jié)構(gòu)與最短路徑路由策略，重點(diǎn)研究輸運(yùn)需求的分布特征對(duì)于網(wǎng)絡(luò)輸運(yùn)能力的影響作用。本文模型的構(gòu)建主要包括三個(gè)部分：BBV網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)、基于引力模型的輸運(yùn)需求分布、基于最短路徑的路由策略。

1.1 網(wǎng)絡(luò)結(jié)構(gòu)演化算法

2005年Barrat等人[4]所提出了BBV加權(quán)網(wǎng)絡(luò)演化模型，該模型繼承了無標(biāo)度網(wǎng)絡(luò)在演化過程中的增長(zhǎng)與偏好連接機(jī)制，并引入了空間距離的制約與邊權(quán)動(dòng)態(tài)演化因素。模型中新加入的節(jié)點(diǎn)n與已存在的節(jié)點(diǎn)i將以概率Πn→i產(chǎn)生連邊，并且節(jié)點(diǎn)間連邊的建立將對(duì)相鄰邊的邊權(quán)產(chǎn)生影響。節(jié)點(diǎn)間連接概率受節(jié)點(diǎn)強(qiáng)度與節(jié)點(diǎn)間的距離影響，如式（1），其中為節(jié)點(diǎn)i的強(qiáng)度，dni為節(jié)點(diǎn)間的歐式距離，rc為節(jié)點(diǎn)間的距離調(diào)節(jié)系數(shù)，V(i)為與節(jié)點(diǎn)i相鄰的節(jié)點(diǎn)集合。邊權(quán)演化機(jī)制如式（2），wij為連接節(jié)點(diǎn)i與節(jié)點(diǎn)j連邊的權(quán)值，δ為邊權(quán)演化系數(shù)。

BBV網(wǎng)絡(luò)結(jié)構(gòu)演化算法不僅反映了輸運(yùn)網(wǎng)絡(luò)在網(wǎng)絡(luò)演化過程中節(jié)點(diǎn)度與邊權(quán)分布的冪律分布特征，更重要的是該模型將距離因素引入復(fù)雜網(wǎng)絡(luò)的演化過程?？紤]BBV演化算法中受節(jié)點(diǎn)強(qiáng)度與距離因素影響的偏好連接機(jī)制與邊權(quán)的動(dòng)態(tài)演化機(jī)制，符合一般性輸運(yùn)網(wǎng)絡(luò)結(jié)構(gòu)的演化特征。因此，本文將以BBV演化算法為基礎(chǔ)構(gòu)建一般性輸運(yùn)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。

1.2 基于空間引力模型的輸運(yùn)需求分布

牛頓引力模型作為空間質(zhì)點(diǎn)相互作用的經(jīng)典模型，自20世紀(jì)30年代起，便被廣泛應(yīng)用于經(jīng)濟(jì)地理學(xué)領(lǐng)域，并發(fā)展為經(jīng)濟(jì)地理引力理論。該理論認(rèn)為地區(qū)間經(jīng)濟(jì)聯(lián)系存在著類似萬有引力的規(guī)律。筆者認(rèn)為，在復(fù)雜輸運(yùn)網(wǎng)絡(luò)中，各節(jié)點(diǎn)間的輸運(yùn)需求難以得到準(zhǔn)確的統(tǒng)計(jì)數(shù)據(jù)，但是，真實(shí)輸運(yùn)系統(tǒng)在二維歐氏空間背景下的網(wǎng)絡(luò)節(jié)點(diǎn)間也存在著類似萬有引力規(guī)律的聯(lián)系，各節(jié)點(diǎn)間的輸運(yùn)聯(lián)系應(yīng)遵循經(jīng)典的空間引力模型[5]，如式（3）。其中Tij表示節(jié)點(diǎn)i與j之間的輸運(yùn)需求引力，dij為節(jié)點(diǎn)i,j之間的歐氏距離，阻抗系數(shù)b則反應(yīng)空間距離對(duì)節(jié)點(diǎn)間輸運(yùn)需求阻抗作用的強(qiáng)弱。

根據(jù)輸運(yùn)網(wǎng)絡(luò)中節(jié)點(diǎn)對(duì)的引力值可以計(jì)算出在節(jié)點(diǎn)i,j之間產(chǎn)生單位輸運(yùn)需求量的概率為F(ODij)，如式（4），其中F(ODij)為節(jié)點(diǎn)i,j上輸運(yùn)需求引力值Tij與系統(tǒng)中所有節(jié)點(diǎn)間需求引力之和的比值。

可以發(fā)現(xiàn)，模型中節(jié)點(diǎn)間的輸運(yùn)需求的產(chǎn)生不再是等概率隨機(jī)事件，節(jié)點(diǎn)i,j間產(chǎn)生單位輸運(yùn)需求量的概率將正比于該節(jié)點(diǎn)間引力值的大小Tij，而節(jié)點(diǎn)之間的引力值受節(jié)點(diǎn)強(qiáng)度sw與節(jié)點(diǎn)間距離dij的影響。

1.3 最短路徑路由策略

在輸運(yùn)系統(tǒng)中，網(wǎng)絡(luò)流將根據(jù)源節(jié)點(diǎn)與目的節(jié)點(diǎn)間的輸運(yùn)需求，按照一定的路由策略沿著輸運(yùn)路徑進(jìn)行流量分配。根據(jù)Wardrop配流理論[6]，網(wǎng)絡(luò)流在起點(diǎn)與終點(diǎn)之間的所有流動(dòng)路線中，將選擇阻抗最小的路徑流動(dòng)。在真實(shí)輸運(yùn)系統(tǒng)中起點(diǎn)與終點(diǎn)間各條路徑的輸運(yùn)距離是確定路徑阻抗的決定性因素。因此本文設(shè)定仿真模型中節(jié)點(diǎn)間的輸運(yùn)需求將選擇源目節(jié)點(diǎn)間距離最短的路徑傳輸。

節(jié)點(diǎn)i,j之間的路徑距離的計(jì)算如（5）式，其中d(pk:i→j)為節(jié)點(diǎn)i到節(jié)點(diǎn)j的第k條路徑的距離，集合{lPk:i→j}由節(jié)點(diǎn)i到節(jié)點(diǎn)j的第k條路徑上的各邊組成。因此節(jié)點(diǎn)i,j之間的路徑距離為該路徑上各邊距離之和。

需要說明的是，由于本文在網(wǎng)絡(luò)結(jié)構(gòu)與輸運(yùn)需求中引入了空間距離因素，因此模型中路徑距離的計(jì)算不同于傳統(tǒng)的基于路徑上節(jié)點(diǎn)跳數(shù)的計(jì)算方法，而是由該路徑上各邊距離值確定。

1.4 仿真模型

（1）輸運(yùn)網(wǎng)絡(luò)結(jié)構(gòu)仿真。根據(jù)BBV網(wǎng)絡(luò)演化算法構(gòu)建輸運(yùn)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，網(wǎng)絡(luò)節(jié)點(diǎn)總數(shù)N=500，初始節(jié)點(diǎn)數(shù)m0=3，距離系數(shù)η=0.01，權(quán)變系數(shù)δ=1，新邊的初始權(quán)值w0=1。演化過程中，新節(jié)點(diǎn)將同時(shí)與該網(wǎng)絡(luò)中m=3個(gè)老節(jié)點(diǎn)產(chǎn)生連邊，產(chǎn)生節(jié)點(diǎn)的圓形區(qū)域半徑L=10。

（2）輸運(yùn)需求分布仿真，設(shè)定每個(gè)時(shí)間步向輸運(yùn)系統(tǒng)加入R個(gè)信息包，每個(gè)信息包的輸運(yùn)起始與目的節(jié)點(diǎn)的選取，將按照（4）式的輸運(yùn)需求分布概率的計(jì)算方法，以一定概率隨機(jī)選取。

（3）最短路徑路由策略仿真。進(jìn)入輸運(yùn)系統(tǒng)的信息包將選擇輸運(yùn)需求節(jié)點(diǎn)間距離最短的路徑進(jìn)行傳輸，一旦信息包到達(dá)目的節(jié)點(diǎn)，則離開輸運(yùn)系統(tǒng)；網(wǎng)絡(luò)中各邊單位時(shí)間處理信息包的個(gè)數(shù)由該邊的權(quán)值w決定，即單位時(shí)間第s條網(wǎng)絡(luò)邊能同時(shí)輸運(yùn)ws個(gè)信息包，一旦達(dá)到該邊單位時(shí)間的最大處理能力，信息包則需排隊(duì)等待，出于簡(jiǎn)化模型考慮，仿真模型中對(duì)排隊(duì)長(zhǎng)度不做限制；設(shè)定信息包在系統(tǒng)中的傳輸速率為V=1，則信息包在第s條邊上的傳輸時(shí)間Ts=ds/V=ds，其中ds為第s條邊的長(zhǎng)度。

2 仿真分析

本文根據(jù)上述仿真機(jī)制編寫仿真程序，設(shè)定程序運(yùn)行的仿真時(shí)間為5000個(gè)時(shí)間步，每個(gè)時(shí)間步同時(shí)向系統(tǒng)輸入R個(gè)仿真信息包；并從輸運(yùn)需求距離分布與輸運(yùn)網(wǎng)絡(luò)容量?jī)蓚€(gè)方面對(duì)仿真結(jié)果進(jìn)行統(tǒng)計(jì)分析。

2.1 輸運(yùn)需求距離分布

傳統(tǒng)配流模型通過隨機(jī)選取源目節(jié)點(diǎn)對(duì)，并產(chǎn)生輸運(yùn)需求量的方法，使得仿真系統(tǒng)中輸運(yùn)需求分布表現(xiàn)出正態(tài)分布的同質(zhì)性特征，但真實(shí)輸運(yùn)系統(tǒng)中各節(jié)點(diǎn)間的輸運(yùn)需求受節(jié)點(diǎn)強(qiáng)度與節(jié)點(diǎn)間輸運(yùn)距離阻抗因素的影響，實(shí)質(zhì)上表現(xiàn)出異質(zhì)性分布特征。為刻畫節(jié)點(diǎn)間的引力作用對(duì)于輸運(yùn)需求異質(zhì)性分布的影響作用，本文對(duì)輸運(yùn)需求節(jié)點(diǎn)間的距離分布函數(shù)P(d)進(jìn)行仿真分析。如圖1，橫坐標(biāo)b為距離阻抗系數(shù)，反應(yīng)節(jié)點(diǎn)間距離對(duì)節(jié)點(diǎn)間輸運(yùn)需求阻抗作用的強(qiáng)弱；縱坐標(biāo)P(d)為輸運(yùn)需求距離為d的節(jié)點(diǎn)對(duì)數(shù)量占節(jié)點(diǎn)對(duì)總數(shù)的比例。當(dāng)b=0時(shí)如式（3）、（4）節(jié)點(diǎn)間產(chǎn)生輸運(yùn)需求的概率只受節(jié)點(diǎn)強(qiáng)度影響，而與節(jié)點(diǎn)間的距離阻抗無關(guān)，此時(shí)P(d)近似成正態(tài)分布，與隨機(jī)設(shè)定輸運(yùn)需求的結(jié)果相同，表現(xiàn)出同質(zhì)性特點(diǎn)。隨著距離阻抗系數(shù)b的減小，P(d)成指數(shù)衰減分布，并且b越小P(d)的衰減趨勢(shì)越強(qiáng)，同時(shí)輸運(yùn)需求分布的異質(zhì)性也越強(qiáng)?？梢姽?jié)點(diǎn)間輸運(yùn)需求的距離分布主要受引力模型中阻抗系數(shù)b的影響，而與節(jié)點(diǎn)強(qiáng)度無明顯關(guān)系。因此，在現(xiàn)實(shí)輸運(yùn)系統(tǒng)中通過調(diào)整節(jié)點(diǎn)強(qiáng)度來控制輸運(yùn)需求距離分布的效果將不明顯，可以考慮通過調(diào)整距離阻抗系數(shù)（輸運(yùn)成本）的方式，來有效控制輸運(yùn)需求的距離分布。

圖1 輸運(yùn)需求距離分布圖

2.2 網(wǎng)絡(luò)容量

根據(jù)系統(tǒng)的輸運(yùn)狀態(tài)可以將輸運(yùn)系統(tǒng)分為自由態(tài)與擁塞態(tài)，自由態(tài)下單位時(shí)間輸出系統(tǒng)的信息包數(shù)量大于或等于輸入系統(tǒng)的信息包數(shù)量；擁塞態(tài)下單位時(shí)間輸出系統(tǒng)的信息包數(shù)量小于輸入系統(tǒng)的信息包量，此時(shí)系統(tǒng)處于超負(fù)荷狀態(tài)。因此，當(dāng)系統(tǒng)處于自由態(tài)向擁塞態(tài)轉(zhuǎn)變的臨界點(diǎn)時(shí)，系統(tǒng)的輸運(yùn)能力達(dá)到峰值。本文采用臨界點(diǎn)時(shí)單位時(shí)間輸入系統(tǒng)的信息包數(shù)量Rc來表征輸運(yùn)網(wǎng)絡(luò)的容量。為表示輸運(yùn)系統(tǒng)由自由態(tài)向擁塞態(tài)的轉(zhuǎn)變，設(shè)定序參量ρ[2]如式（6），該序參量表示當(dāng)仿真時(shí)間處于無窮大時(shí)，單位時(shí)間內(nèi)系統(tǒng)信息包的增加率，Np(t)為t時(shí)刻系統(tǒng)中正在運(yùn)輸?shù)男畔鼣?shù)量。

圖2 輸運(yùn)狀態(tài)序參量與信息包產(chǎn)生速率關(guān)系圖

當(dāng)ρ=0時(shí)輸運(yùn)系統(tǒng)始終處于自由狀態(tài)；ρ＞0時(shí)，隨著仿真時(shí)間的增加，輸運(yùn)系統(tǒng)中信息包的數(shù)量將單調(diào)增加，最終進(jìn)入擁塞狀態(tài)。如圖2，橫坐標(biāo)R表示單位時(shí)間進(jìn)入輸運(yùn)系統(tǒng)的信息包數(shù)量，縱坐標(biāo)ρ為反映信息包增加率的序參量。當(dāng)b=0時(shí)，一旦信息包輸入速率R＞3，系統(tǒng)便進(jìn)入擁塞狀態(tài)，此時(shí)網(wǎng)絡(luò)容量Rc=3；而b=-1時(shí)，當(dāng)R＞39時(shí)系統(tǒng)才進(jìn)入擁塞狀態(tài)，此時(shí)網(wǎng)絡(luò)容量Rc=39。因此，距離阻抗因素將導(dǎo)致輸運(yùn)需求距離的異質(zhì)性分布，而輸運(yùn)需求距離的異質(zhì)性分布又將進(jìn)一步影響輸運(yùn)系統(tǒng)的輸運(yùn)能力。

圖3 網(wǎng)絡(luò)容量與距離阻抗系數(shù)關(guān)系圖

為探究距離阻抗因素對(duì)于網(wǎng)絡(luò)容量影響的函數(shù)關(guān)系，進(jìn)一步在改變距離阻抗系數(shù)b的條件下，仿真分析網(wǎng)絡(luò)容量Rc的變化情況。如圖3，當(dāng)b=-1.1時(shí)網(wǎng)絡(luò)容量達(dá)到最大值42，b=＜-1.1時(shí)網(wǎng)絡(luò)容量成指數(shù)上升，而b＞-1.1時(shí)網(wǎng)絡(luò)容量成指數(shù)衰減。因此，在真實(shí)輸運(yùn)系統(tǒng)中距離阻抗抑制作用較強(qiáng)時(shí)（對(duì)應(yīng)于圖3中b＜-1.1的區(qū)域），將造成輸運(yùn)需求集中在距離較近的節(jié)點(diǎn)之間，這導(dǎo)致距離較長(zhǎng)而輸運(yùn)能力較強(qiáng)的連邊的利用率降低，從而造成了網(wǎng)絡(luò)容量的降低；而距離阻抗抑制作用較弱時(shí)（對(duì)應(yīng)于圖3中b＞-1.1的區(qū)域），輸運(yùn)需求集中在距離較遠(yuǎn)的節(jié)點(diǎn)之間，雖然有效利用了輸運(yùn)能力較強(qiáng)的連邊，但在最短路徑路由策略作用下，將造成系統(tǒng)中某些關(guān)鍵連邊的擁塞，從而降低整個(gè)系統(tǒng)的輸運(yùn)能力。

3 結(jié)論

本文在BBV網(wǎng)絡(luò)結(jié)構(gòu)與最短路徑路由策略基礎(chǔ)上，提出了基于引力需求的輸運(yùn)網(wǎng)絡(luò)配流模型，重點(diǎn)分析了網(wǎng)絡(luò)輸運(yùn)需求的異質(zhì)性分布特征對(duì)網(wǎng)絡(luò)輸運(yùn)能力的影響作用。首先，在距離阻抗因素的作用下，網(wǎng)絡(luò)系統(tǒng)中的輸運(yùn)需求節(jié)點(diǎn)間的距離分布表現(xiàn)出指數(shù)衰減的異質(zhì)性特征，這不同于傳統(tǒng)配流模型中，隨機(jī)預(yù)測(cè)需求時(shí)所表現(xiàn)出的正態(tài)分布的同質(zhì)性特征。其次，輸運(yùn)需求節(jié)點(diǎn)間距離分布的異質(zhì)性特征，在很大程度上能影響網(wǎng)絡(luò)系統(tǒng)的輸運(yùn)能力，而傳統(tǒng)配流模型將注意力集中在網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)與路由策略對(duì)于網(wǎng)絡(luò)輸運(yùn)能力的影響，卻忽略了輸運(yùn)需求分布這一重要影響因素。最后，現(xiàn)實(shí)輸運(yùn)系統(tǒng)中可以通過調(diào)整距離對(duì)于輸運(yùn)需求的阻抗作用（對(duì)應(yīng)于模型中的系數(shù)b），有效控制輸運(yùn)需求的分布，從而達(dá)到優(yōu)化系統(tǒng)輸運(yùn)能力的目的。

[1]Tadi′c,B.,S.Thurner,Information Super-diffusion on Structured Net?works[J].Physica A:Statistical Mechanics and its Applications,2004，332.

[2]Echenique,P.,J.Gomez-Gardenes,Y.Moreno.Dynamics of Jamming Transitions in Complex Networks[J].Europhysics Letters,2005，（71）.

[3]Hu,M.B.,et al.The Effect of Bandwidth in Scale-free Network Traffic[J].Europhysics Letters,2007，（79）.

[4]Barrat,A.,M.Barthélemy,A.Vespignani.The Effects of Spatial Con?straints on the Evolution of Weighted Complex Networks[J].Journal of Statistical Mechanics:Theory and Experiment,2005,5.

[5]閆衛(wèi)陽,王發(fā)曾,秦耀辰.城市空間相互作用理論模型的演進(jìn)與機(jī)理[J].地理科學(xué)進(jìn)展,2009，28(4).

[6]Borkar,V.S.,P.R.Kumar.Dynamic Cesaro-Wardrop Equilibration in Networks[J].Automatic Control,IEEE Transactions on,2003，48(3).