基于引力需求的輸運網絡配流模型

韓景倜，李周平 ，2

（1.上海財經大學 信息管理與工程學院，上海 200433；2.上海理工大學 管理學院，上海 200093）

0 引言

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

本文將借助引力模型預測輸運網絡系統中節點間的潛在輸運需求，以此反映真實輸運系統中，由節點強度與距離阻抗因素所引起的輸運需求的異質性分布。并綜合考慮網絡結構、路由策略、輸運需求分布三方面因素，建立輸運網絡中流量分配的仿真模型，重點分析輸運需求的異質性分布對于網絡系統輸運能力的影響作用。

1 輸運網絡配流模型

本文所提出的“基于引力需求的輸運網絡配流模型”將基于特定的輸運網絡結構與最短路徑路由策略，重點研究輸運需求的分布特征對于網絡輸運能力的影響作用。本文模型的構建主要包括三個部分：BBV網絡拓撲結構、基于引力模型的輸運需求分布、基于最短路徑的路由策略。

1.1 網絡結構演化算法

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

BBV網絡結構演化算法不僅反映了輸運網絡在網絡演化過程中節點度與邊權分布的冪律分布特征，更重要的是該模型將距離因素引入復雜網絡的演化過程。考慮BBV演化算法中受節點強度與距離因素影響的偏好連接機制與邊權的動態演化機制，符合一般性輸運網絡結構的演化特征。因此，本文將以BBV演化算法為基礎構建一般性輸運網絡拓撲結構。

1.2 基于空間引力模型的輸運需求分布

牛頓引力模型作為空間質點相互作用的經典模型，自20世紀30年代起，便被廣泛應用于經濟地理學領域，并發展為經濟地理引力理論。該理論認為地區間經濟聯系存在著類似萬有引力的規律。筆者認為，在復雜輸運網絡中，各節點間的輸運需求難以得到準確的統計數據，但是，真實輸運系統在二維歐氏空間背景下的網絡節點間也存在著類似萬有引力規律的聯系，各節點間的輸運聯系應遵循經典的空間引力模型[5]，如式（3）。其中Tij表示節點i與j之間的輸運需求引力，dij為節點i,j之間的歐氏距離，阻抗系數b則反應空間距離對節點間輸運需求阻抗作用的強弱。

根據輸運網絡中節點對的引力值可以計算出在節點i,j之間產生單位輸運需求量的概率為F(ODij)，如式（4），其中F(ODij)為節點i,j上輸運需求引力值Tij與系統中所有節點間需求引力之和的比值。

可以發現，模型中節點間的輸運需求的產生不再是等概率隨機事件，節點i,j間產生單位輸運需求量的概率將正比于該節點間引力值的大小Tij，而節點之間的引力值受節點強度sw與節點間距離dij的影響。

1.3 最短路徑路由策略

在輸運系統中，網絡流將根據源節點與目的節點間的輸運需求，按照一定的路由策略沿著輸運路徑進行流量分配。根據Wardrop配流理論[6]，網絡流在起點與終點之間的所有流動路線中，將選擇阻抗最小的路徑流動。在真實輸運系統中起點與終點間各條路徑的輸運距離是確定路徑阻抗的決定性因素。因此本文設定仿真模型中節點間的輸運需求將選擇源目節點間距離最短的路徑傳輸。

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

需要說明的是，由于本文在網絡結構與輸運需求中引入了空間距離因素，因此模型中路徑距離的計算不同于傳統的基于路徑上節點跳數的計算方法，而是由該路徑上各邊距離值確定。

1.4 仿真模型

（1）輸運網絡結構仿真。根據BBV網絡演化算法構建輸運網絡拓撲結構，網絡節點總數N=500，初始節點數m0=3，距離系數η=0.01，權變系數δ=1，新邊的初始權值w0=1。演化過程中，新節點將同時與該網絡中m=3個老節點產生連邊，產生節點的圓形區域半徑L=10。

（2）輸運需求分布仿真，設定每個時間步向輸運系統加入R個信息包，每個信息包的輸運起始與目的節點的選取，將按照（4）式的輸運需求分布概率的計算方法，以一定概率隨機選取。

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

2 仿真分析

本文根據上述仿真機制編寫仿真程序，設定程序運行的仿真時間為5000個時間步，每個時間步同時向系統輸入R個仿真信息包；并從輸運需求距離分布與輸運網絡容量兩個方面對仿真結果進行統計分析。

2.1 輸運需求距離分布

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

圖1 輸運需求距離分布圖

2.2 網絡容量

根據系統的輸運狀態可以將輸運系統分為自由態與擁塞態，自由態下單位時間輸出系統的信息包數量大于或等于輸入系統的信息包數量；擁塞態下單位時間輸出系統的信息包數量小于輸入系統的信息包量，此時系統處于超負荷狀態。因此，當系統處于自由態向擁塞態轉變的臨界點時，系統的輸運能力達到峰值。本文采用臨界點時單位時間輸入系統的信息包數量Rc來表征輸運網絡的容量。為表示輸運系統由自由態向擁塞態的轉變，設定序參量ρ[2]如式（6），該序參量表示當仿真時間處于無窮大時，單位時間內系統信息包的增加率，Np(t)為t時刻系統中正在運輸的信息包數量。

圖2 輸運狀態序參量與信息包產生速率關系圖

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

圖3 網絡容量與距離阻抗系數關系圖

為探究距離阻抗因素對于網絡容量影響的函數關系，進一步在改變距離阻抗系數b的條件下，仿真分析網絡容量Rc的變化情況。如圖3，當b=-1.1時網絡容量達到最大值42，b=＜-1.1時網絡容量成指數上升，而b＞-1.1時網絡容量成指數衰減。因此，在真實輸運系統中距離阻抗抑制作用較強時（對應于圖3中b＜-1.1的區域），將造成輸運需求集中在距離較近的節點之間，這導致距離較長而輸運能力較強的連邊的利用率降低，從而造成了網絡容量的降低；而距離阻抗抑制作用較弱時（對應于圖3中b＞-1.1的區域），輸運需求集中在距離較遠的節點之間，雖然有效利用了輸運能力較強的連邊，但在最短路徑路由策略作用下，將造成系統中某些關鍵連邊的擁塞，從而降低整個系統的輸運能力。

3 結論

本文在BBV網絡結構與最短路徑路由策略基礎上，提出了基于引力需求的輸運網絡配流模型，重點分析了網絡輸運需求的異質性分布特征對網絡輸運能力的影響作用。首先，在距離阻抗因素的作用下，網絡系統中的輸運需求節點間的距離分布表現出指數衰減的異質性特征，這不同于傳統配流模型中，隨機預測需求時所表現出的正態分布的同質性特征。其次，輸運需求節點間距離分布的異質性特征，在很大程度上能影響網絡系統的輸運能力，而傳統配流模型將注意力集中在網絡拓撲結構與路由策略對于網絡輸運能力的影響，卻忽略了輸運需求分布這一重要影響因素。最后，現實輸運系統中可以通過調整距離對于輸運需求的阻抗作用（對應于模型中的系數b），有效控制輸運需求的分布，從而達到優化系統輸運能力的目的。

[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]閆衛陽,王發曾,秦耀辰.城市空間相互作用理論模型的演進與機理[J].地理科學進展,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).