[發明專利]一種針對分層流量復雜網絡的路徑優化方法

在審

• 申請號: 201711452300.3
• 申請日: 2017-12-28
• 公開（公告）號: CN107872354A
• 公開（公告）日: 2018-04-03
• 發明（設計）人: 穆獻中;李國昊;胡廣文;吳玉鋒
• 申請（專利權）人: 北京工業大學
• 主分類號: H04L12/24
• 分類號: H04L12/24;H04L12/721;H04L12/801
• 代理公司: 北京思海天達知識產權代理有限公司11203
• 代理人: 張慧

1.一種針對分層流量復雜網絡的動態路徑優化方法，其特征在于，包括以下步驟：

步驟一：網絡準備與預處理

為計算各轉運站和節點的流量總和；

步驟二：確定網絡優化目標

在原有的網絡上增加一層，以將原層網絡中的流量分至新的一層；

步驟三：分層節點分類

初步確定分層節點的大致位置，其基本思想為①分層節點應盡量與周邊節點聯通；②分層節點應優先選取節點密集或流量較大的擁堵空間，得到重新分類后的節點分類，其包括：節點坐標、節點流量、節點擁堵系數；

步驟四：分層節點優化

在確定了分層節點個數和位置后，對分層節點進行優化，以確定最佳網絡路徑結構。

2.如權利要求1所述的針對分層流量復雜網絡的動態路徑優化方法，其特征在于，步驟二中，根據每一個分層節點的設立能夠達到緩解區域網絡擁擠程度的基本要求，將可選位置進行篩選；當原有網絡中流量由于分層節點的加入而引起網絡負擔降低時，認為該節點位置時初步可行的；

擁堵改變程度以下述公式衡量：

h′i=ti-t′iti]]>

其中，h′_i為節點i的擁堵改變程度；t_i為初始流量；t′_i為改變后流量；

設在完成篩選后，有滿足最短路徑范圍內的n個可行位置，有：

s.t0<hi′≥0.5t′i≤tiΣil=1ntil′≤Mi]]>

其中，h′_i改變程度不小于0.5；M_i為節點i的負載上限。

目標函數為：

minΣl=1nhil′m]]>

其中，m表示預期準備設置的分層節點數量。

3.如權利要求2所述的針對分層流量復雜網絡的動態路徑優化方法，其特征在于，作為優選，步驟四具體為：獲取所有二級節點的坐標、節點的流通量、不同種類的路線的成本以及運載成本，

具體處理過程為：

連通矩陣初始為一個n維零矩陣，其中，n為節點總數；

最小成本初始為0；

從中心節點出發，對中心節點覆蓋區域中所有的二級節點排序，連接中心節點與距離最短的二級節點；

對下一個節點，計算該節點可與已經存在連通圖上的每一個節點的距離，由此計算其新增成本：對于已經存在于連通圖上的路徑，不計算其建造成本，只計算運載成本；對該連接新增的路徑需計算其建造成本和運載成本；

對所有新增成本進行排序，選擇成本最低的連接方式；

更新連通矩陣和最小成本；

重復上述步驟，直到遍歷完所有的節點

得到連通矩陣和最小成本，即可得到優化后的網絡連通圖。