[發明專利]一種緩解公交網絡擁塞的方法

有效

• 申請號: 201710629087.2
• 申請日: 2017-07-28
• 公開（公告）號: CN107528790B
• 公開（公告）日: 2020-08-04
• 發明（設計）人: 劉雪薇;鄭文武;齊義;林夢楠;王一帆;任濤
• 申請（專利權）人: 東北大學
• 主分類號: H04L12/801
• 分類號: H04L12/801;H04L12/721;H04L29/08
• 代理公司: 大連理工大學專利中心 21200
• 代理人: 梅洪玉

本發明屬于復雜網絡領域，提供了一種緩解公交網絡擁塞的方法。方法針對網絡節點信息的獲取存在時間延遲，通過采用改變節點包先進先出的傳統處理過程，解決時間延遲造成網絡擁塞的問題。在改變節點的處理過程后，有明顯緩解網絡擁塞程度的效果，在交通網絡這一背景下，改變節點的傳統處理過程具有相當的適用價值。對于城市公交網絡，有重要應用價值。

技術領域

本發明屬于復雜網絡領域，涉及一種緩解公交網絡擁塞的方法。

背景技術

隨著經濟的發展和城市化進程的加快，城市機動車擁有量急劇增加，交通擁擠越來越嚴重，并且交通網絡中的節點信息的獲取存在著時間延遲，因此如何緩解時間延遲對路由策略的影響十分重要。本方法通過改變節點的傳統處理過程來緩解時間延遲對網絡擁塞的影響。

當前人們選擇出行到達目的地的時候，他們一般考慮一下因素：(1)最短路徑。即從出發點到終點距離最近，這種方案簡單方便，但是沒有考慮途經站點的等待人數和站點的處理能力的動態狀況。在高峰時期很容易導致整個交通網絡因為擁塞癱瘓，乘客不得不耗費大量的時間處于等待狀態。(2)局部路由策略。這個策略由王丹的博士論文《復雜網絡擁塞分析與路由策略研究》有提出。他們在最短路徑的基礎上考慮了下一跳站點的等待人數和站點的處理能力的動態狀況，即考慮α倍的最短路徑和(1-α)倍的下一跳站點的等待人數站點的處理能力比值，能讓二者之和最小的站點就是轉乘的站點。該策略忽略了全局的擁塞狀態(從起點到終點途經的所有站點的等待人數和站點的處理能力的動態狀況)，僅僅考慮下一跳節點的擁塞狀態。同時由于現實乘客在出發點想要獲得下一站站點的人數存在一定的時間延遲，即等到用戶得到下一站站點的人數的時候，下一站站點已經發生了一些變動，這本質就是因為客觀事實的不可避免性，所有如何減少時間延遲對乘客對路徑規劃的不準確行顯得至關重要。現有的方法不能很好的解決以上問題。

綜上所述，當前使用的方法沒有充分的考慮全局擁塞信息。因此提出了用全局擁塞感知的代價函數計算包傳遞的代價從而解決上述問題的不足。

發明內容

為了解決時間延遲對網絡擁塞產生的不良影響，針對網絡中時間延遲造成的擁塞，本發明提供了一種緩解公交網絡擁塞的方法。通過采用改變節點包先進先出的傳統處理過程，解決時間延遲造成網絡擁塞的問題。在交通網絡這一背景下，改變節點的傳統處理過程具有相當的適用價值。

本發明的技術方案為，一種緩解公交網絡擁塞的方法，包括如下步驟：

步驟一：選取公交網絡，獲得帶有時延的情況下節點擁塞信息為帶有時延情況下節點i對鄰居節點k到目的節點j最短路徑上整體擁塞程度的感知函數。

其中Q_x(t-Δt(L_ix))表示節點x在時間t-Δt(L_ix)時在排隊隊列中等待投遞的包總數，Δt(L_ix)表示節點i感知節點x的擁塞程度的延遲，

Δt(L_ix)＝β*L_ix,β＞0 (2)

當t-Δt(L_ix)＜0時，定義Q_x(t-Δt(L_ix))＝Q_x(0)。其中β為控制節點擁塞信息感知的時延的可調參數。當β＞0時，節點間擁塞信息感知的時延與節點間最短距離呈正相關，β越大，節點間擁塞信息感知的時延越長。b_x表示節點x單位時間的處理能力。表示節點k到目的節點j最短路徑上擁塞程度的累加。

步驟二：利用公式(3)計算每個包的傳遞代價，并且從小到大排序。