[發(fā)明專利]基于無序節(jié)點約束的路由確定方法、裝置以及存儲介質(zhì)

在審

• 申請?zhí)枺?/td>: 201710709437.6
• 申請日: 2017-08-18
• 公開（公告）號: CN109412954A
• 公開（公告）日: 2019-03-01
• 發(fā)明（設(shè)計）人: 胡騫;荊瑞泉;趙國永;魏思源
• 申請（專利權(quán)）人: 中國電信股份有限公司
• 主分類號: H04L12/751
• 分類號: H04L12/751;H04L12/721;H04L12/705
• 代理公司: 中國國際貿(mào)易促進委員會專利商標事務(wù)所 11038
• 代理人: 方亮

本發(fā)明公開了一種基于無序節(jié)點約束的路由確定方法、裝置以及存儲介質(zhì)，其中的方法包括：基于網(wǎng)絡(luò)節(jié)點以及網(wǎng)絡(luò)節(jié)點之間的鏈路建立第一鄰接矩陣；將第一鄰接矩陣中的排除節(jié)點以及排除節(jié)點相關(guān)聯(lián)的鏈路去除，重構(gòu)后獲得第二鄰接矩陣；在第二鄰接矩陣中確定位于源節(jié)點和目的節(jié)點之間、并經(jīng)過必經(jīng)節(jié)點的最短路徑。本發(fā)明的方法、裝置以及存儲介質(zhì)，可以處理包括排除節(jié)點和必經(jīng)節(jié)點的組合約束問題，支持無序必經(jīng)節(jié)點的約束，采用分治思想大幅減少路由問題的搜索空間，采用先剪枝或動態(tài)剪枝的方法處理所有不可能經(jīng)過的節(jié)點，避免無效計算，降低路由計算開銷，確保能收斂至全局最優(yōu)，對于大規(guī)模網(wǎng)絡(luò)復(fù)雜度低。

技術(shù)領(lǐng)域

本發(fā)明涉及網(wǎng)絡(luò)通信技術(shù)領(lǐng)域，尤其涉及一種基于無序節(jié)點約束的路由確定方法、裝置以及存儲介質(zhì)。

背景技術(shù)

路由算法的目的是找到一條從源節(jié)點到目的節(jié)點的滿足約束的路徑，目前已提出多種經(jīng)典路由算法，現(xiàn)有的路由算法主要以最短路徑、最小費用、最小時延等相關(guān)代價值為約束，較少涉及節(jié)點的約束。在光傳送網(wǎng)領(lǐng)域中，考慮到單點/多點故障以及必經(jīng)節(jié)點的需求，經(jīng)常會在節(jié)點約束的前提下進行路由計算，但現(xiàn)有的經(jīng)典路由算法往往不再適用。目前，在非通信學(xué)科分支雖然有關(guān)于節(jié)點約束路由算法的研究，但算法過于復(fù)雜，且均未考慮通信網(wǎng)絡(luò)領(lǐng)域?qū)β酚傻臒o環(huán)路、無自環(huán)等要求。因此，需要一種在具有節(jié)點約束的情況下確定路由的方法。

發(fā)明內(nèi)容

有鑒于此，本發(fā)明要解決的一個技術(shù)問題是提供一種基于無序節(jié)點約束的路由確定方法、裝置以及存儲介質(zhì)。

根據(jù)本發(fā)明的一個方面，提供一種基于無序節(jié)點約束的路由確定方法，包括：基于網(wǎng)絡(luò)節(jié)點以及網(wǎng)絡(luò)節(jié)點之間的鏈路建立第一鄰接矩陣；根據(jù)節(jié)點約束條件確定所述網(wǎng)絡(luò)節(jié)點中的排除節(jié)點和必經(jīng)節(jié)點；將第一鄰接矩陣中的所述排除節(jié)點以及所述排除節(jié)點相關(guān)聯(lián)的鏈路去除；對經(jīng)過去除處理的所述第一鄰接矩陣進行重構(gòu)，獲得第二鄰接矩陣；在所述第二鄰接矩陣中確定位于源節(jié)點和目的節(jié)點之間、并經(jīng)過所述必經(jīng)節(jié)點的最短路徑。

可選地，所述在所述第二鄰接矩陣中確定位于源節(jié)點和目的節(jié)點之間、并經(jīng)過所述必經(jīng)節(jié)點的最短路徑包括：獲取必經(jīng)節(jié)點集合，對所述必經(jīng)節(jié)點集合中的所有必經(jīng)節(jié)點進行全排列組合，獲得必經(jīng)節(jié)點的全排列集合；對所述全排列集合中的必經(jīng)節(jié)點排列進行遍歷，根據(jù)所述必經(jīng)節(jié)點排列對位于源節(jié)點和目的節(jié)點之間、并經(jīng)過所有必經(jīng)節(jié)點的路徑進行分段，確定與每個分段路徑所對應(yīng)的分段最短路徑；根據(jù)所述分段最短路徑確定位于源節(jié)點和目的節(jié)點之間、并經(jīng)過所有必經(jīng)節(jié)點的最短路徑。

可選地，所述對所述全排列集合中的必經(jīng)節(jié)點排列進行遍歷、根據(jù)所述必經(jīng)節(jié)點排列對位于源節(jié)點和目的節(jié)點之間、并經(jīng)過所有必經(jīng)節(jié)點的路徑進行分段、確定與每個分段路徑對應(yīng)的分段最短路徑包括：獲取所述全排列集合中的所述必經(jīng)節(jié)點排列為<a₁，a₂,…,a_n-1,a_n>，其中，a₁，a₂,…,a_n-1,a_n為必經(jīng)節(jié)點；根據(jù)所述必經(jīng)節(jié)點排列中的必經(jīng)節(jié)點的排列順序生成n+1個節(jié)點對，確定每個節(jié)點對所包含的兩個節(jié)點之間的最短路徑；其中，所述n+1個節(jié)點對包括：由相鄰的兩個必經(jīng)節(jié)點組成的n-1個節(jié)點對、由第一個必經(jīng)節(jié)點與所述源節(jié)點組成的節(jié)點對、由最后一個必經(jīng)節(jié)點與所述目的節(jié)點組成的節(jié)點對。

可選地，所述確定每個節(jié)點對所包含的兩個節(jié)點之間的最短路徑包括：獲取所述n+1個節(jié)點對中的一個節(jié)點所對所包含的必經(jīng)節(jié)點，從所述第二鄰接矩陣中去除其余必經(jīng)節(jié)點以及與所述其余必經(jīng)節(jié)點相關(guān)聯(lián)的鏈路；對經(jīng)過了去除處理的所述第二鄰接矩陣進行重構(gòu)，獲得第三鄰接矩陣；在所述第三鄰接矩陣中確定此節(jié)點對所包含的兩個節(jié)點之間的最短路徑。