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

有效

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

1.一種基于多代價指標的路由裁剪優化方法，其特征在于，包括以下步驟：

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

步驟2：對于給定的網絡源節點以及目標節點，從源節點至目標節點進行廣度遍歷獲得中間節點，根據源節點至中間節點的代價指標向量計算源節點至中間節點的鄰居節點的代價指標向量；

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

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

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

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

2.根據權利要求1所述的基于多代價指標的路由裁剪優化方法，其特征在于，步驟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

其中，W_xy,i為網絡節點x至網絡節點y第i條路由的代價指標向量，P_xy為網絡節點x至網絡節點y的路由集合，|P_xy|為網絡節點x至網絡節點y的路由數量即代價指標向量的數量，N為網絡中的節點數量，K為網絡中的指標數量，w_xy,i,k k∈[1,K]為網絡節點x至網絡節點y第i條路由的代價指標向量的第k個代價指標；

根據網絡中指標的數量K構造多維度空間H_K，其維度為K；

設所有路徑中第j維代價的下界為LB_j，上界為UB_j，精度為e，1≤j≤K,且存在一個M_j∈Z⁺(正整數)使得則

根據步驟1中所述精度e建立的步進序列為：

其中，步進序列中第m個元素為LB_j*(1+e)^m-1，m∈[1,M_j+1]；

步驟1中所述對多維度空間H_K的第j維度軸進行分段為：

其中，第j維度軸上第n段為[LB_j*(1+e)^n-1,LB_j*(1+e)ⁿ]n∈[1,M_j]，多維度空間H_K的K個軸均根據步進序列進行變長分段。