[發明專利]層次化確定網絡中的多約束雙路徑路由方法

有效

• 申請號: 201810293525.7
• 申請日: 2018-04-04
• 公開（公告）號: CN108494601B
• 公開（公告）日: 2020-02-21
• 發明（設計）人: 盛立杰;秦丹
• 申請（專利權）人: 西安電子科技大學
• 主分類號: H04L12/24
• 分類號: H04L12/24;H04L12/721
• 代理公司: 陜西電子工業專利中心 61205
• 代理人: 田文英;王品華

1.一種層次化確定網絡中的多約束雙路徑路由方法，其特征在于，將確定網絡劃分為由不同數量的子網絡組成的多個父網絡，利用啟發式多約束最優路徑算法的的反向線性標記法和正向標記法，通過對網絡拓撲圖中父網絡、子網絡與節點的三次簡化，獲得滿足多個約束要求的不存在重復鏈路的兩條路徑，該方法的具體步驟包括如下：

(1)獲取網絡拓撲圖中各條鏈路的服務質量參數和可靠性數值：

(1a)子網絡中的每個節點向與其相鄰的節點發送查詢信息，將相鄰節點接收信息后的應答，作為該兩個相鄰節點之間鏈路的服務質量參數和可靠性數值；

(1b)利用迪杰斯特拉算法，查找子網絡中每兩個邊界節點之間的最短路徑，將最短路徑的服務質量參數和可靠性數值，作為該兩個邊界節點之間鏈路的服務質量參數和可靠性數值；

(1c)在每個子網絡中保留邊界節點，隱藏除了邊界節點之外的其他節點；

(1d)子網絡的邊界節點向與其相鄰的子網絡的邊界節點發送查詢信息，將與其相鄰的子網絡的邊界節點接收信息之后的應答作為該兩個相鄰邊界節點之間鏈路的服務質量參數和可靠性數值；

(2)確定源邊界節點和目的邊界節點：

(2a)在網絡拓撲圖中隨機選取一個節點，作為源節點；

(2b)在網絡拓撲圖中除所選的節點外，隨機選取一個節點，作為目的節點；

(2c)利用迪杰斯特拉算法，計算從源節點到源節點所處的子網絡內的每個邊界節點的路徑，在所有的路徑中選擇服務質量參數中的跳數值最小的邊界節點作為源邊界節點；

(2d)利用迪杰斯特拉算法，計算從目的節點到目的節點所處的子網絡內的每個邊界節點的路徑，在所有路徑中選擇服務質量參數中的跳數值最小的邊界節點，作為目的邊界節點；

(3)獲得源邊界節點的反向線性標記值：

利用啟發式多約束最優路徑算法的反向線性標記法，得到源邊界節點的反向線性標記值；

(4)判斷源邊界節點的反向線性標記值是否滿足多約束服務質量參數條件，若是，則執行步驟(5)；否則，執行步驟(18)；

(5)計算網絡拓撲圖中的第一條路徑：

(5a)利用啟發式多約束最優路徑算法的正向標記法對網絡拓撲圖中的每個節點進行標記；

(5b)將標記后的目的邊界節點作為第一個節點，將第一個節點作為工具節點，將工具節點的前一跳節點作為第一個節點的下一個節點，依次類推，直到工具節點為源邊界節點為止，從第一個節點開始，將依次得到的下一個節點進行連接，得到第一條路徑；

(6)對網絡拓撲圖進行第一次簡化：

(6a)判斷第一條路徑上從源邊界節點到目的邊界節點之間的每個節點與源邊界節點是否屬于同一個父網絡，若是，則執行步驟(6b)；否則，執行步驟(6c)；

(6b)刪去網絡拓撲圖中與源邊界節點屬于同一個父網絡的節點；

(6c)判斷不屬于源邊界節點所在父網絡的節點與目的邊界節點是否屬于同一個父網絡，若是，則執行步驟(6d)；否則，執行步驟(6e)；

(6d)刪去網絡拓撲圖中與目的邊界節點屬于同一個父網絡中的節點；

(6e)刪去網絡拓撲圖中既不屬于源邊界節點所在父網絡，又不屬于目的邊界節點所在父網絡的節點所在的父網絡后，得到第一次簡化后的網絡拓撲圖；

(7)獲得源邊界節點的反向線性標記值：

在第一次簡化后的網絡拓撲圖中，利用啟發式多約束最優路徑算法的反向線性標記法，得到源邊界節點的反向線性標記值；

(8)判斷源邊界節點的反向線性標記值是否滿足多約束服務質量參數條件，若是，則執行步驟(9)；否則，執行步驟(10)；

(9)計算第二條路徑：

(9a)在第一次簡化后的網絡拓撲圖中,利用啟發式多約束最優路徑算法的正向標記法對網絡拓撲圖中的每個節點進行標記；

(9b)將標記后的目的邊界節點作為第一個節點，將第一個節點作為工具節點，將工具節點的前一跳節點作為第一個節點的下一個節點，依次類推，直到工具節點為源邊界節點為止，從第一個節點開始，將依次得到的下一個節點進行連接，得到第二條路徑后執行步驟(19)；

(10)對第一次簡化前的網絡拓撲圖進行第二次簡化：

(10a)判斷第一條路徑上從源邊界節點到目的邊界節點之間的每個節點與源邊界節點是否屬于同一個子網絡，若是，則執行步驟(10b)；否則，執行步驟(10c)；

(10b)刪去網絡拓撲圖中與源邊界節點屬于同一個子網絡的節點；

(10c)判斷不屬于源邊界節點所在子網絡的節點與目的邊界節點是否屬于同一個子網絡，若是，則執行步驟(10d)；否則，執行步驟(10e)；

(10d)刪去網絡拓撲圖中與目的邊界節點屬于同一個子網絡中的節點；

(10e)刪去網絡拓撲圖中，既不屬于源邊界節點所在子網絡，又不屬于目的邊界節點所在子網絡的節點所在的子網絡后，得到第二次簡化后的網絡拓撲圖；

(11)獲得源邊界節點的反向線性標記值：

在第二次簡化后的網絡拓撲圖中，利用啟發式多約束最優路徑算法的反向線性標記法，得到源邊界節點的反向線性標記值；

(12)判斷源邊界節點的反向線性標記值是否滿足多約束服務質量參數條件，若是，則執行步驟(13)；否則，執行步驟(14)；

(13)計算第二條路徑：

(13a)在第二次簡化后的網絡拓撲圖中,利用啟發式多約束最優路徑算法的正向標記法對網絡拓撲圖中的每個節點進行標記；

(13b)將標記后的目的邊界節點作為第一個節點，將第一個節點作為工具節點，將工具節點的前一跳節點作為第一個節點的下一個節點，依次類推，直到工具節點為源邊界節點為止，從第一個節點開始，將依次得到的下一個節點進行連接，得到第二條路徑后執行步驟(19)；

(14)對第一次簡化前的網絡拓撲圖進行第三次簡化：

刪去網絡拓撲圖中第一條路徑上從源邊界節點到目的邊界節點之間的所有節點，得到第三次簡化后的網絡拓撲圖；

(15)獲得源邊界節點的反向線性標記值：

在第三次簡化后的網絡拓撲圖中，利用啟發式多約束最優路徑算法的反向線性標記法，得到源邊界節點的反向線性標記值；

(16)判斷源邊界節點的反向線性標記值是否滿足多約束服務質量參數條件，若是，則執行步驟(17)；否則，執行步驟(19)；

(17)計算第二條路徑：

(17a)在第三次簡化后的網絡拓撲圖中,利用啟發式多約束最優路徑算法的正向標記法，對網絡拓撲圖中的每個節點進行標記；

(17b)將標記后的目的邊界節點作為第一個節點，將第一個節點作為工具節點，將工具節點的前一跳節點作為第一個節點的下一個節點，依次類推，直到工具節點為源邊界節點為止，從第一個節點開始，將依次得到的下一個節點進行連接，得到第二條路徑后執行步驟(19)；

(18)查找失敗；

(19)完成多約束雙路徑路由。