基于BA網絡的突發事件下靜態局部路由策略研究

仇多利，梁昌勇，肖建于，李 晨①

（1.合肥工業大學 管理學院，安徽 合肥 230000；2.淮北師范大學 計算機科學與技術學院，安徽 淮北 235000；3.蘇試試驗集團股份有限公司，江蘇 蘇州 215000）

0 引言

隨著汽車數量的急劇增加，路網負載急距增大，城市管理者可通過優化路網布局解決路網堵問題，增加道路容量，比如完善立體交通、增加車道數、加強停車場建設等，但此類方法綜合成本較高，因此可通過對網絡模型的研究了解現實路網的內部運行機制，結合突發事件，提出有效的交通路由策略，對于解決路網擁堵問題經濟且省時。

60年代初，Erdost提出著名的ER隨機圖模型，成為復雜網絡研究的基礎理論。Watts等［1］研究從靜態網絡向隨機網絡動態變化的演變過程，提出既擁有規則網絡的聚類特性，又擁有隨機網絡所具有的平均路徑長度小的小世界網絡。Barabasi等［2］提出度分布符合冪分布的BA網絡，指出度數較大的個別節點對網絡傳輸能力起決定性作用。越來越多的學者在BA網絡的基礎上研究網路擁堵和相變過程。Valverde等［3］考慮BA網絡的異質性，模擬交通流的傳輸過程。Holme等［4］通過控制BA網絡一些度大的節點，從而提升網絡傳輸性能。于灝等［5］通過加入適當比例的“受控邊”，在網絡連接邊帶寬資源總量固定的條件下，重新分配帶寬資源。魏鋼等［6］通過對數據包設置優先級和采取動態排隊策略，改善傳輸率。鄭文萍等［7］基于成生圖模型提出一種具有社區結構的可調節聚集系統和模塊性的無標度網絡生成算法，該算法采用合理的連邊策略，能盡可能維持網絡的無標度特征。段佳勇等［8］通過優化系統與網絡節點的關聯度，通過計算關聯度最優時網絡各參數值，從而獲得理想的網絡模型。董昂等［9］針對復雜網絡中失效節點或邊產生的級聯效應，基于初始負載定義對級聯故障模型的影響，提出基于局部熵的初始負載定義方式，并驗證局部熵的有效性。陸秋琴等［10］利用對偶法構建路網拓撲模型，提出路網在隨機換效條件下其可靠性模型和可靠性指數計算方法。王碧瑤等［11］提出一種節點重要度計算方法，結合復雜網絡相關理論分析城市軌道交通網絡的脆弱性，得出單節點攻擊對軌道交通網絡的影響較小，累計節點蓄意攻擊下軌道交通網絡表現出較強的脆弱性。

路由策略好壞很大程度上決定網絡性能，因此研究如何優化路由策略，使網絡吞吐量達到最大，是近些年研究的熱點問題。Wang等［12］提出一種基于局域信息的路由策略，通過設置調節參數α改變路由策略，有利于數據包傳輸過程避開網絡中度數大的節點，降低網絡造成堵塞的可能性。Yan等［13］提出的“有效路由”策略可以使數據包在傳輸過程有效避開原本路徑中一些會發生交通擁堵的節點。王開等［14］提出基于隨機行走理論的路由優化策略，通過調節可變參數，建立節點處理能力均勻分布的路由策略。文宏等［15］通過優化配置節點處理能力和路由算法參數來提高網絡性能的新方法，增加網絡容量，減少報文路由時間。羅開田等［16］研究基于引力場理論的動態路由選擇過程，提出在介數約束下的引力場路由選擇策略。荊霞等［17］將多環網絡中的復雜路由問題轉換為單環網中的簡單路由，結合路徑還原算法，將單一環網改進為增強型環網拓撲，使同一環內通信節點間的路徑還原為完整最短路徑。

目前，城市路網流量經常出現過飽和，若發生突發事件，極易導致交叉口路段交通癱瘓，車輛甚至行人常處于進退兩難的境地，擁堵同樣使得救援工作困難重重。因此，通過理論方法研究突發事件下的交通擁堵疏散策略，一方面可以避免突發事件所造成的影響，另一方面可以為疏散車輛和行人提供現實指導方法。本文以關鍵數據節點突發通信能力降低為基礎進行基于BA網絡的路網建模，研究將靜態局部路由策略應用在網絡遇到突發事件模型下，帶有主動選擇偏好性的交通路由策略，通過仿真模擬不同程度突發事件下最優偏好性參數和優化后的靜態局部路由策略下網絡臨界信息包產生率，以使整個網絡數據包在各節點的分布更加均勻，從而減少數據包傳輸時間，降低突發事件對網絡交通傳輸的影響。

1 BA無標度網絡模型

網絡模型構造如下:設一個全連通網絡的節點數為N，網絡中的節點數量隨每個時間步長逐個增加，加入的節點根據式（1）的概率值在原網絡中選擇節點連接，從式（1）可以看出，原網絡中的節點被連接的概率正比于節點的度。

ki為節點i的度，對節點l的所有相鄰節點求和。給定足夠長演化時間，最終能得到Y=3 的無標度網絡，并且度的分布符合冪律分布p(k)≈k-3，網絡的平均距離D～lnN/ln lnN，簇系數C～(lnN)2。此時網絡呈現出無標度和傳輸平均距離短的特征，可以用來進行路網模擬。圖1展示BA網絡中的度分布。

圖1 BA網絡中的度分布

2 突發事件下路網建模

路網建模如下:每一時間步，網絡隨機新增R個數據包待傳輸，新增數據包隨機選定節點加入網絡并隨機選擇目的節點。每個節點數據包傳輸能力定義為Ci，Ci=ki，其中ki為節點i的度，即節點i在單位時間內向其鄰居節點最多傳輸ki個數據包，數據包發送采用FIFO（先進先出）策略。每一時間步，數據包依據排隊長度對節點處理能力范圍內相鄰節點進行搜索，若存在目的節點，則節點直接將數據包轉發到目的地節點后將數據包從網絡中刪除，否則，數據包隨機選擇鄰居節點轉發。突發事件定義如下:在原來網絡基礎上降低網絡最大度節點數據包處理能力，根據突發事件程度大小分別降低10%、20%、30%、40%和50%。

臨界信息包產生率Rc作為網絡傳輸能力評價指標，定義如下:在保證整個網絡數據包總數最終處于穩定狀態下，每個時間步向網絡中允許加入的最大數據包個數。當每個時間步網絡中新產生的數據包數小于等于RC時，給予充足演化，最終，網絡中總數據包數會趨向穩定，此時網絡以自由流方式運行。當每個時間步網絡中新增隨機數據包數大于RC時，網絡中數據包總數持續增長，隨著網絡深化，網絡將會發生擁堵?？梢缘贸?，網絡在RC處由自由流狀態向擁堵狀態轉變，也可用式（2）來刻畫相變點的位置。

其中ΔNp=Np(t+Δt)-Np(t)，表示網絡總數據包數在Δt時間內的變化量。Np(t)代表t時刻網絡數據包總量。當序參數η=0，總數據包增長率為0，網絡處于自由流狀態；當序參數η＞0，總數據包增長率大于0，網絡總數據包數持續增加，網絡向擁堵演化。

3 網絡交通在突發事件下的變化情況

對基于無標度BA網絡的帶有突發事件下的路網進行仿真，設置如下參數:節點數N=1 000 ，平均度k=6。當網絡未發生突發事件，即ε=0%時，從圖2可以看出:R≤32 時，給定足夠的演化時間，網絡數據包總數最終處于穩定狀態，網絡未發生擁堵。在這個演化過程中，由于網絡數據包從起始節點到達目的地節點需要一段時間，在演化初期，網絡大部分數據包均未找到終點，所以網絡總數據包數增量較大。隨著演化深入，數據包逐漸接近或者到達目的節點。由于已到達目的節點的數據包被刪除，所以網絡總數據包數增速明顯變緩，隨著網絡再進一步演化，每個時間步新加入的數據包和到達目的節點被刪除的數據包相等時，網絡中總數據包數基本不變，網絡穩定處理各數據包。當R＞32 時，網絡在演化初期，網絡總數據包數急速增加，隨著演化時間增加，網絡總數據包數增速放緩，但與R≤32 時情況不同，網絡最終每個時間步數據包因到達目的節點被刪除數持續小于新增數據包數，因此，網絡總數據包數隨時間持續增加，被刪除數據包持續降低，網絡最終會產生全面擁堵，如圖2。

圖2 網絡總信息包數隨演化時間變化曲線

由上可得，網絡在R=32 處發生相變，由自由流狀態轉變為擁堵狀態，所以，在基于BA的無標度網絡中使用自由路徑傳輸路由模型的臨界信息包產生率為32。

當序參數η在R≤32 取值保持為0，當R＞32 時序參數η取值大于0，得出R=32 為網絡由自由流向擁堵狀態轉變的臨界點，網絡信息包通訊能力為32，如圖3。

圖3 η-R 曲線

選擇網絡中最大度節點處理能力降低作為網絡突發事件研究對象。在不同程度突發事件下，依次對網絡交通情況進行模擬，得出在網絡最大度節點信息包處理能力分別降低10%、20%、30%、40%及50%，即ε=10%、20%、30%、40%、50%時網絡相應的臨界信息包產生率。從圖4可以看出，隨著最大度節點數據包處理能力顯著降低，網絡臨界信息包產生率也隨之大幅降低；隨著最大度節點處理能力降低一半，網絡臨界信息包產生率也將近降低一半，說明最大度節點數據包處理能力降低嚴重影響全網傳輸能力。

圖4 臨界信息包產生率隨突發事件程度變化情況

圖5展示網絡臨界信息包產生率隨平均度變化情況，可以得出Rc會隨著網絡平均度的增加而增加，即平均度增加，保持自由流狀態的Rc也會增加。但對于同一平均度的網絡，Rc同樣會隨著突發事件程度的增加而降低，因此為提高整個網絡的數據包傳輸能力，既要盡可能增加節點的度，同時又要降低發生突發事件的可能性。

圖5 網絡臨界信息包產生率隨平均度變化情況

評價網絡傳輸效率不僅要考慮每個時間步能夠向網絡中加入的最大數據包個數，還需考慮整個網絡數據包平均傳輸時間，對此，模擬出網絡最大度節點數據包處理能力降低對整個網絡數據包平均傳輸時間的影響變化曲線，結果如圖6所示。在R=10，R=15時，隨著最大度節點數據包處理能力變低，網絡數據包平均傳輸并未發生明顯變化，因為此時網絡處于自由流狀態，網絡中所有節點均不會發生排隊情況，最大度節點處的數據包也不會隨其節點處理能力降低而在節點處滯留，所以自由流狀態下傳輸時間基本不受最大度節點處理能力降低的影響。在R=35，R=40時，這時網絡處于擁堵狀態時，網絡中必有部分節點發生排隊現象，最大度節點也發生數據包排隊現象。由于最大度節點數據包處理能力降低，單位時間內向鄰居節點傳送出去數據包個數隨之減少，將會加劇數據包在最大度節點的排隊情況。數據包在最大度節點的滯留時間更長，導致整個網絡數據傳輸效率變慢，所以網絡擁堵狀態時，傳輸時間會隨著突發事件程度的增加而增加，相反傳輸效率會不斷降低。

圖6 不同等級突發事件下數據包平均傳輸時間

4 突發事件下網絡交通擁堵疏散策略

當網絡發生突發事件，如果網絡中數據包維持原來的路由策略將無法主動避開意外情況，對此將原網絡隨機路由策略進行優化調整。在突發事件下，每個節點在確定下一個傳輸節點時進行偏好設置。路由策略如下:節點對其鄰居節點進行搜索，如果搜索到數據包的目的節點，則直接將該信息轉發至目的地節點并從網絡中刪除；如果沒有搜索到目的節點地址，則依據概率P選擇節點進行轉發，概率定義如下:

其中ki為節點i的度。對節點l所有鄰居節點進行求和。由式（3）可知，α值越大，其相鄰的度大節點有較大概率被選擇，可以充分發揮度大節點的傳輸優勢，但是度大節點數據包處理能力是有上限的，如果都簡單的依據選擇度大節點進行傳輸，隨著演化深入，度大節點會產生擁堵現象，從而導致傳輸處理時間延長，全網傳輸能力下降，因此α取值過大反而降低臨界信息包產生率；相反，如果α過小，則度大節點被選擇的概率越小，度大節點的傳輸優勢得不到發揮，無法提高臨界信息包產生率，因此對于不同程度的突發事件，α對應著一個最優值能使網絡臨界信息包產生率達到最大。圖7展示不同程度突發事件下能使臨界信息包產生率達到最大最優的α值?？梢钥闯霾煌话l事件下隨著α的增加，臨界信息包產生率都是先增加后減小，呈現上凸狀，最優α值分別為0、-0.1、-0.1、-0.1、-0.2，優化后的臨界信息包產生率分別為31、27、26、24、22，與原策略相比，分別提高0%、8.00%、13.04%、20.00%、29.41%。

圖7 不同程度突發事件下最優α 值

網絡中數據包在節點處的分布越均勻，則越不易發生擁堵，圖8和圖9分別模擬出網絡在突發事件ε=30%和ε=50%情況下自由流狀態時網絡信息包節點分布。從圖8和圖9中可以看出節點度越大，平均排隊數據包越多，并且網絡未優化時度小節點平均排隊數據包數小于優化后度小的節點，未優化時度大節點平均排隊數據包數則小于優化后度大的節點，說明優化后避免網絡部分節點出現數據包堆積現象，使得數據包在節點處的分布更加均勻。

圖8 不同度節點平均排隊信息包情況，ε=30%，R=20

圖9 不同度節點平均排隊信息包情況，ε=50%，R=15

5 結語

本文基于BA網絡，使用降低最大度節點數據包處理能力模擬路網遇到突發事件進行路網建模。通過仿真分析得出不同程度突發事件對網絡臨界信息包產生率及數據包平均傳輸時間的影響可以得出，隨著網絡最大度節點數據包處理能力降低，網絡臨界信息包產生率隨之降低，網絡產生擁堵，數據包傳輸時間也會加長。針對此種情況，將靜態局部路由策略應用在網絡突發事件模型下，網絡在發生突發事件后原隨機路由策略更改為帶有主動選擇偏好性路由策略，經過仿真得出不同程度突發事件下最優偏好性參數時網絡臨界信息包產生率，經過優化，網絡臨界信息包產生率分別提高0%、8.00%、13.04%、20.00%、29.41%。