[發明專利]一種基于多代價指標的路由裁剪優化方法

有效

• 申請號: 201810254608.5
• 申請日: 2018-03-26
• 公開（公告）號: CN110365585B
• 公開（公告）日: 2021-08-03
• 發明（設計）人: 黃傳河;覃匡宇
• 申請（專利權）人: 武漢大學
• 主分類號: H04L12/721
• 分類號: H04L12/721
• 代理公司: 武漢科皓知識產權代理事務所(特殊普通合伙) 42222
• 代理人: 薛玲

本發明提出了一種基于多代價指標的路由裁剪優化方法。本發明通過代價指標向量構造多維度空間并根據精度建立的步進序列對每維度軸進行變長分段；從源節點至目標節點路由經過節點中選擇中間節點，計算源節點至中間節點的鄰居節點的代價指標向量；將源節點至中間節點的鄰居節點的所有代價指標向量中任意兩個代價指標向量進行比較實現路由一次裁剪；根據源節點至中間節點的鄰居節點的剩余代價指標向量在多維度空間中進行二次裁剪；重復執行一次裁剪以及二次裁剪至搜索到源節點到目標節點的路由并進行優化選擇；多次迭代重復執行搜索到源節點到目標節點的路由并進行優化。與現有技術相比，本發明簡單易行，可在多項式時間內處理高維代價指標。

技術領域

本發明涉及無線網絡通信技術領域，尤其涉及一種基于多代價指標的路由裁剪優化方法。

背景技術

在最短路徑的計算中，每條鏈路帶有一個代價值，路由決策模塊通過尋找到目的地具有最少總代價的路徑來完成路由。在RIP協議中，使用跳數作為選路的依據，每條鏈路的代價為1。在OSPF協議中，默認是使用基準帶寬除以接口帶寬來作為每個出口鏈路的代價指標。

近年來，軟件定義網絡(Software Defined Networking，SDN)得到了很大的發展。軟件定義網絡通過將控制平面和數據平面分離，實現了控制邏輯的集中管理。在軟件定義網絡中，數據的轉發由SDN控制器來作出決策。由于SDN控制器具備全局視圖，因而可以很精確的為每個流規劃路徑。在進行路由決策時，對于兩點間的路徑，路徑的代價是各條鏈路的代價之和。控制器根據網絡中各路徑的代價值來選擇從源節點到目標節點的最佳路徑。

目前的控制器使用單一指標來衡量鏈路的代價，但在實際使用中一條真正好的路徑往往不能簡單地用一個單一指標來衡量，需要同時考慮多種因素，包括時延、帶寬、跳數和租金等，這時對于每條鏈路應考慮兩種甚至更多的代價指標。在按照單一代價來選擇最優路徑時，可以使用Dijkstra算法來計算。但對于多指標的路徑，目前還沒有很好的辦法。主要的問題在于其搜索空間太大，考慮一個n節點的全連接網絡，其任意兩點間的路徑可以有(n-1)！條，最優路徑的計算無法在短時間內完成。該問題被稱為Multi-Object OptimalPath，MOOP，相關研究表明這是一個NP-完全問題，要想獲得帕累托最優解集，需要指數式的時間。因而，目前的SDN控制器只支持單一代價指標的路由選擇，尚無多代價指標下的路由方案。

發明內容

為了解決上述問題，本發明提供了一種基于多代價指標的路由裁剪優化方法，本發明所采用的技術方案是：

步驟1：通過代價指標向量構造多維度空間，根據精度建立的步進序列對多維度空間的每維度軸進行變長分段；

步驟2：從網絡節點中選擇源節點以及目標節點，從源節點至目標節點路由經過節點中選擇中間節點，根據源節點至中間節點的代價指標向量計算源節點至中間節點的鄰居節點的代價指標向量；

步驟3：通過遍歷源節點至中間節點的鄰居節點的所有代價指標向量，并將任意兩個代價指標向量進行比較實現路由一次裁剪得到節點至中間節點的鄰居節點的剩余代價指標向量以及剩余路由集合；

步驟4：根據源節點至中間節點的鄰居節點的剩余代價指標向量在多維度空間中對源節點至中間節點的鄰居節點的剩余路由進行二次裁剪；

步驟5：重復步驟3至步驟4至搜索到源節點到目標節點的路由并進行優化選擇；

步驟6：多次迭代重復執行步驟5。

作為優選，步驟1中所述代價指標向量為：

W_xy,i＝(w_xy,i,1,w_xy,i,2,...,w_xy,i,K)x∈[1,N],y∈[1,N],i∈[1,|P_xy|],x≠y