基於WSON損傷模型的最短路徑的計算方法及其系統與流程
2023-05-05 23:59:26
本發明涉及數據和ip傳輸設備的技術領域，具體是涉及一種基於wson損傷模型的最短路徑的計算方法及其系統。
背景技術：
wson(wavelengthswitchedopticalnetwork)也就是基于波分復用傳輸網的ason，是目前ietf標準組織倡導的智能波分標準，除了傳統ason(automaticallyswitchedopticalnetwork)的功能外，主要解決波分網絡中光纖/波長自動發現、在線波長路由選擇、基於損傷模型的路由選擇等問題，其核心技術依然集中在路徑計算所採用的算法。
wson是將控制平面引入到波長網絡中，在路徑計算時，需要考慮波長的動態變化，以及物理鏈路的osnr(opticalsignalnoiseratio)即光信噪比。通常，初始狀態下，網絡中每段鏈路可以使用的波長信號數量一樣，由於硬體限制，計算得到的邏輯通道路徑上各段鏈路必須使用統一波長的光信號，波長的動態變化，也正是因為網絡拓撲中可以同時存在多條邏輯通道，經過不同路徑、使用不用波長信號的通道佔用了網絡資源，使網絡中各鏈路的可用波長信號發生差異。較為簡單的方法是先使用常用的最短路徑策略，對給定波長計算一條每段鏈路該波長都可用的最短路徑，若算路失敗，遍歷每個波長，直到某個波長算路成功或遍歷完所有波長。此方法實現簡單，但受限于波長不可改變，造成了資源浪費。對此，可以將部分節點作為中繼節點，路由經過中繼節點時，允許改變後續鏈路傳輸信號的波長，同時，也允許路徑經過該節點但不作為中繼節點(即波長不可變)。
通常一條路徑的osnr可以由每段鏈路的硬體參數計算，且隨著鏈路的增加而降低，一條符合傳輸要求的路徑，其總osnr必須大於給定閾值。中繼節點的另一個功能就是對光信號重新放大，使整條路徑的osnr只需要滿足：源節點到下一個中繼節點、相鄰中繼節點、宿節點到上一個中繼節點之間的osnr都大於閾值。
所以，中繼功能可以分為兩個部分：允許變換波長、重置osnr。如圖1所示，要建立節點1到節點3的通道，由於鏈路1-2隻有λ1波可用，鏈路2-3隻有λ2波可用，則必須使節點2作為中繼節點，才能允許通道路徑的子路段信號波長不一致。又如圖2所示，假設路徑上波長都可用，鏈路1-2、2-3的osnr都是20，而路徑1-2-3的整體osnr為15，若給定閾值為18，則必須使節點2作為中繼節點，使路徑1-2-3的兩個子路段osnr都大於閾值。
傳統意義上的最短路徑算法只需要滿足節點最少、鏈路代價最小等路由策略，結合中繼功能重新定義後的最短路徑，若將路徑中源節點到下一個中繼節點、相鄰中繼節點之間、宿節點到上一個中繼節點之間路徑簡稱為子路段，其算法需求可以總結為：尋找一條指定源節點到宿節點的最短路徑，要求路徑中的每一條子路段選擇一個都可用的統一波長，並且所有子路段osnr不超過給定閾值。最後，由於實現中繼功能的硬體代價關係，當路徑經過中繼節點時，該節點也可以選擇不使用中繼功能，作為普通節點，於是，新的算法還必須滿足一個最重要的限制條件：要求路徑上作為中繼的節點數最少，並且此條件要更優先於路由策略。如圖3所示，節點1到節點3的最短路徑在節點最少的路由策略下應該是1-2-3，且節點2作為中繼，但中繼最少的需求更加優先時，1-4-5-6-3才是最佳路徑。
技術實現要素：
本發明的目的是為了克服上述背景技術的不足，提供一種基於wson損傷模型的最短路徑的計算方法及其系統，能夠計算指定源節點到指定宿節點的最短路徑，具有準確率高、實用性強的優點。
本發明提供一種基於wson損傷模型的最短路徑的計算方法，包括如下步驟：
a、根據給定的路由策略計算前k條最短路徑，k為正整數；
b、計算步驟a中k條路徑的最少中繼數，每一條路徑的最少中繼數的計算步驟如下：
b1、以該路徑上所有具備中繼功能的節點為界，將該路徑分割為若干子路段，構造矩陣matrix[m][n]，其中，n為路段數，m為波長數；
b2、將子路段的正向光纖經過的所有光放大器oa的xi疊加值，作為子路段總光信噪比osnr計算指標，得到數組xsum[n]；將子路段的反向光纖經過的所有光放大器oa的xi疊加值，作為子路段的反向osnr計算指標，得到數組rvs_xsum[n]；其中，xi為osnr的計算公式的指數部分，i為正整數，i的取值範圍為1～n，n為路徑單方向所經過的oa的總數，每一條子路段osnr都大於給定閾值t；
b3、根據動態規划算法思想，輸入參數matrix[m][n]、xsum[n]、rvs_xsum[n]，構造三個迭代矩陣：矩陣trans[m][n]、矩陣sum[m][n]、矩陣rvs_sum[m][n]；矩陣trans[m][n]隨著算法迭代過程記錄當前最少中繼數；矩陣sum[m][n]和矩陣rvs_sum[m][n]記錄當前中繼最少方案下到前一個中繼或源節點的osnr計算指標疊加量；
b4、從矩陣trans[m][n]的最後一列選擇最小的數值，即為整個路徑最少中繼數，按迭代規則回溯矩陣，得到路徑的波長選擇結果和中繼選擇結果；若矩陣trans[m][n]最後一列都是無效值，則該路徑不通，動態規劃失敗；
c、比較步驟b中計算得到的k條路徑的最少中繼數，選擇中繼數最少的路徑作為最短路徑。
在上述技術方案的基礎上，步驟b1中，所述矩陣matrix[m][n]的構造過程如下：以子路段按順序映射為行，以路段對所有波長是否可用映射為列，且保證路徑中的每一條子路段至少存在一個都可用的統一波長，矩陣matrix[m][n]的矩陣取值為0或1；
其中，0表示第n路段上第m波長不可用，1表示第n路段上第m波長可用。
在上述技術方案的基礎上，步驟b2中，所述osnr的計算公式為：
其中，opi表示第i個oa的輸入光功率，mi為第i個oa所在鏈路背景波道數，nfi為第i個oa的噪聲係數；
所述xi的計算公式為：
所述xi疊加值滿足其中，t＝10-t/10。
在上述技術方案的基礎上，步驟b3中，所述矩陣trans[m][n]的構造過程如下：設置矩陣trans[m][n]內的數值初始化均為無效值，對矩陣trans[m][n]進行逐列算法迭代，每列按照從上至下的順序計算，共計算m*n次。
在上述技術方案的基礎上，步驟c中，選擇中繼數最少的路徑作為最短路徑時，若出現多條路徑的中繼數相同，則選擇路由策略最佳的路徑，作為最短路徑。
本發明還提供一種基於wson損傷模型的最短路徑的計算系統，該系統包括前k條最短路徑計算模塊、最少中繼數計算模塊和最短路徑選擇模塊；
所述前k條最短路徑計算模塊用於：根據給定的路由策略計算前k條最短路徑，k為正整數；
所述最少中繼數計算模塊用於：計算k條路徑的最少中繼數，每一條路徑的最少中繼數的計算步驟如下：
以該路徑上所有具備中繼功能的節點為界，將該路徑分割為若干子路段，構造矩陣matrix[m][n]，其中，n為路段數，m為波長數；
將子路段的正向光纖經過的所有光放大器oa的xi疊加值作為子路段總光信噪比osnr計算指標，得到數組xsum[n]；將子路段的反向光纖經過的所有光放大器oa的xi疊加值作為子路段的反向osnr計算指標，得到數組rvs_xsum[n]；其中，xi為osnr的計算公式的指數部分，i為正整數，i的取值範圍為1～n，n為路徑單方向所經過的oa的總數，每一條子路段osnr都大於給定閾值t；
根據動態規划算法思想，輸入參數matrix[m][n]、xsum[n]、rvs_xsum[n]，構造三個迭代矩陣：矩陣trans[m][n]、矩陣sum[m][n]、矩陣rvs_sum[m][n]；矩陣trans[m][n]隨著算法迭代過程記錄當前最少中繼數；矩陣sum[m][n]和矩陣rvs_sum[m][n]記錄當前中繼最少方案下到前一個中繼或源節點的osnr計算指標疊加量；
從矩陣trans[m][n]的最後一列選擇最小的數值，即為整個路徑最少中繼數，按迭代規則回溯矩陣，得到路徑的波長選擇結果和中繼選擇結果；若矩陣trans[m][n]最後一列都是無效值，則該路徑不通，動態規劃失敗；
所述最短路徑選擇模塊用於：比較最少中繼數計算模塊計算得到的k條路徑的最少中繼數，選擇中繼數最少的路徑作為最短路徑。
在上述技術方案的基礎上，所述最少中繼數計算模塊具體用於：以子路段按順序映射為行，以路段對所有波長是否可用映射為列，構造矩陣matrix[m][n]，且保證路徑中的每一條子路段至少存在一個都可用的統一波長，將矩陣matrix[m][n]取值0或1；
其中，0表示第n路段上第m波長不可用，1表示第n路段上第m波長可用。
在上述技術方案的基礎上，所述最少中繼數計算模塊具體用於：
計算osnr的公式為：
其中，opi表示第i個oa的輸入光功率，mi為第i個oa所在鏈路背景波道數，nfi為第i個oa的噪聲係數；
計算xi的計算公式為：
保證xi疊加值滿足其中，t＝10-t/10。
在上述技術方案的基礎上，所述最少中繼數計算模塊還用於：設置矩陣trans[m][n]內的數值初始化均為無效值，對矩陣trans[m][n]進行逐列算法迭代，每列按照從上至下的順序計算，共計算m*n次。
在上述技術方案的基礎上，所述最短路徑選擇模塊還用於：選擇中繼數最少的路徑作為最短路徑時，若出現多條路徑的中繼數相同，最短路徑選擇模塊選擇路由策略最佳的路徑，作為最短路徑。
與現有技術相比，本發明的優點如下：本發明結合中繼功能，提出一種針對wson網絡波長動態變化，以及osnr損傷模型的最短路徑算法，能夠自動尋找一條指定源節點到指定宿節點的最短路徑。本發明先根據給定的源節點、宿節點以及路由策略計算出前k條最短路徑，使用動態規劃(dynamicprogramming)算法思想迭代求出該條路徑中哪個節點作為中繼，以及其每條子路段選用哪個波長；最後，選擇k條路徑中使用中繼最少的結果作為算法輸出的最短路徑。本發明的算法不僅簡單，而且準確率高、實用性強。
附圖說明
圖1是現有的三節點的網絡拓撲結構示意圖，其中λ1、λ2為信號波長。
圖2是現有的三節點的鏈路中osnr的網絡拓撲結構示意圖。
圖3是現有的六節點的網絡拓撲結構示意圖。
圖4是本發明實施例基於wson損傷模型的最短路徑的計算方法的流程圖。
圖5是本發明實施例計算k條路徑的最少中繼數的流程圖。
圖6是本發明實施例的七節點的網絡拓撲結構示意圖。
圖7是本發明實施例的兩節點的光放大器oa的正向光纖和反向光纖的網絡拓撲結構示意圖。
具體實施方式
下面結合附圖及具體實施例對本發明作進一步的詳細描述。
參見圖4所示，本發明實施例提供一種基於wson損傷模型的最短路徑的計算方法，包括如下步驟：
s1、根據給定的路由策略計算前k條最短路徑，k為正整數；
s2、計算步驟s1中k條路徑的最少中繼數，參見圖5所示，每一條路徑的最少中繼數的計算步驟如下：
s201、以該路徑上所有具備中繼功能的節點為界，將該路徑分割為若干子路段，構造矩陣matrix[m][n]，其中，n為路段數，m為波長數；
s202、將子路段的正向光纖經過的所有光放大器oa的xi疊加值作為子路段總光信噪比osnr計算指標，得到數組xsum[n]；將子路段的反向光纖經過的所有光放大器oa的xi疊加值作為子路段的反向osnr計算指標，得到數組rvs_xsum[n]；其中，xi為osnr的計算公式的指數部分，i為正整數，i的取值範圍為1～n，n為路徑單方向所經過的oa的總數，每一條子路段osnr都大於給定閾值t；
s203、根據動態規划算法思想，輸入參數matrix[m][n]、xsum[n]、rvs_xsum[n]，構造三個迭代矩陣：矩陣trans[m][n]、矩陣sum[m][n]、矩陣rvs_sum[m][n]；矩陣trans[m][n]隨著算法迭代過程記錄當前最少中繼數；矩陣sum[m][n]和矩陣rvs_sum[m][n]記錄當前中繼最少方案下到前一個中繼或源節點的osnr計算指標疊加量；
s204、從矩陣trans[m][n]的最後一列選擇最小的數值，即為整個路徑最少中繼數，按迭代規則回溯矩陣，得到路徑的波長選擇結果和中繼選擇結果；若矩陣trans[m][n]最後一列都是無效值，則該路徑不通，動態規劃失敗；
s3、比較步驟s2中計算得到的k條路徑的最少中繼數，選擇中繼數最少的路徑作為最短路徑。其中，步驟s1中，已有許多完善算法計算前k條最短路徑，如ksp(topkshortestpaths)算法，k的大小可以根據實際情況調整，計算出最短路徑，第二短的路徑，第三短的路徑，一直到第k短的路徑，一共k條。先按路由策略選出前k短的k條路徑，再在這k條路徑中，根據波長分配和中繼情況，選出一條最符合要求的路徑。
其中，步驟s201中，矩陣matrix[m][n]的構造過程如下：以子路段按順序映射為行，以路段對所有波長是否可用映射為列，且保證路徑中的每一條子路段至少存在一個都可用的統一波長，矩陣matrix[m][n]的矩陣取值為0或1，其中，0表示第n路段上第m波長不可用，1表示第n路段上第m波長可用。參見圖6所示，圖6省略oa器件，只顯示節點與鏈路，若其中一條路徑為1-2-3-4-5-6-7，其中節點3和節點5具備中繼功能，則將路徑分割為1-2-3、3-4-5、5-6-7三個子路段，圖中鏈路標註了可用波長，假如所有可用波為λ1-λ5，則分別取三段子路段的共公可用波集合，分別為λ1-λ4，λ3、λ4，λ4，以子路段按順序映射為行，路段對所有波長是否可用映射為列(此時路段數n＝3，波長數m＝5)，構造矩陣matrix[m][n]，取值0或1，分別表示第n路段上第m波長是否可用，圖6的場景可以構造如下矩陣；
步驟s202中，osnr的計算公式為：
其中，opi表示第i個oa的輸入光功率，mi為第i個oa所在鏈路背景波道數，nfi為第i個oa的噪聲係數；
xi的計算公式為：
子路段單向光纖經過的所有光放大器oa的xi疊加值，滿足
其中，t＝10-t/10。
根據公式(1)、(2)可以得到：
t為給定閾值，每一條子路段osnr都應大於給定閾值t。
由於xi為osnr的計算公式的指數部分，無論op、nf、m如何取值，xi必定大於0；則無論路徑怎樣取，隨著路徑經過的oa數量n的增加而單調遞增，且xi越小越好，根據公式(1)、(2)、(4)，令t＝10-t/10，得出公式(3)。
由於每條路徑可以根據中繼節點分割為若干條子路段，則每一條子路段osnr都應大於給定閾值t可以轉換為：若子路段經過n個oa，則子路段必須滿足公式(3)。
參見圖7所示，節點1與節點2之間的子路段收發光纖各經過2個oa，其參數xn根據公式(2)計算得到x1、x2、x3、x4，則該路段xsum＝x1+x2，rvs_xsum＝x3+x4。實際中，一般實際場景中路徑正向傳播osnr與反向傳播的osnr會有差異。
其中，步驟s203中，設置矩陣trans[m][n]內的數值初始化均為無效值，對矩陣trans[m][n]進行逐列算法迭代，每列按照從上至下的順序計算，共計算m*n次。在實際應用中，無效值可以根據情況指定，只要編碼的時候能夠判斷出哪個是無效值即可。由於子路段數每增加1，中繼數最多增加1，則使子路段數為n的路徑中繼數最少，則其子路段數為n-1的路徑中繼數必然也要最少，又因為當osnr超限或者下一段子路段同波長不可用時中繼數必加1，每次迭代時若第j(0<＝j<n)路段上第i(0<＝i<m)波可用，則重新計算並將trans[i][j]替換為有效值，每次迭代結果如下(0<＝i<m，0<＝j<n)：
if(sum[i][j-1]+xsum[j]<t)&&(rvs_sum[i][j-1]+rvs_xsum[j]<t)&&
(matrix[i][j-1]＝＝1)&&(trans[i][j-1]t，必須進行中繼放大，選擇前一列最小的值加1，即trans[2][2]＝trans[2][1]+1。
在最後一列最小值為1，可以選擇給子路段3分配λ2，子路段2分配λ2，子路段1分配λ1，並且一旦發生狀態轉移(即矩陣元素值發生加1)，則將發生狀態轉移的兩個子路段之間的節點作為中繼節點，即子路段1與子路段2之間的節點作為中繼；若子路段3選擇λ3(需要的中繼數一樣，可以根據不同需求選擇)，則子路段1與子路段2都可以分配λ3，但在子路段2與3之間發生狀態轉移，將子路段2與子路段3之間的節點作為中繼。
在實際應用中，步驟s204中，一條路徑的矩陣trans[m][n]中，若最後一列存在多個相同的最小中繼數，可以根據每次算路給定的指定波長，最終選擇與該指定波長較為接近的波長。
步驟s3中，選擇中繼數最少的路徑作為最短路徑時，若出現多條路徑的中繼數相同，則選擇路由策略最佳的路徑，作為最短路徑。
此外，設網絡拓撲中共v個節點、e條邊，初始狀態可用波長數量為n，一般計算單條最短路徑的時間複雜度大約為o(e+vlgv)，空間複雜度為o(v)，對每條路徑執行步驟s203算法時，最壞的時間複雜度為o(nnv)，空間複雜度為o(nv)，則整個算法時間複雜度為o(k(e+vlgv+nnv))，空間複雜度為o(k(v+nv))。所以，使用本方法計算路徑總共時間、空間複雜度都在多項式級別內，對拓撲規模沒有要求。
本發明還公開一種基於wson損傷模型的最短路徑的計算系統，該系統包括前k條最短路徑計算模塊、最少中繼數計算模塊和最短路徑選擇模塊；
前k條最短路徑計算模塊用於：根據給定的路由策略計算前k條最短路徑，k為正整數；
最少中繼數計算模塊用於：計算k條路徑的最少中繼數，每一條路徑的最少中繼數的計算步驟如下：
以該路徑上所有具備中繼功能的節點為界，將該路徑分割為若干子路段，構造矩陣matrix[m][n]，其中，n為路段數，m為波長數；
將子路段的正向光纖經過的所有光放大器oa的xi疊加值作為子路段總光信噪比osnr計算指標，得到數組xsum[n]；將子路段的反向光纖經過的所有光放大器oa的xi疊加值作為子路段的反向osnr計算指標，得到數組rvs_xsum[n]；其中，xi為osnr的計算公式的指數部分，i為正整數，i的取值範圍為1～n，n為路徑單方向所經過的oa的總數，每一條子路段osnr都大於給定閾值t；
根據動態規划算法思想，輸入參數matrix[m][n]、xsum[n]、rvs_xsum[n]，構造三個迭代矩陣：矩陣trans[m][n]、矩陣sum[m][n]、矩陣rvs_sum[m][n]；矩陣trans[m][n]隨著算法迭代過程記錄當前最少中繼數；矩陣sum[m][n]和矩陣rvs_sum[m][n]記錄當前中繼最少方案下到前一個中繼或源節點的osnr計算指標疊加量；
從矩陣trans[m][n]的最後一列選擇最小的數值，即為整個路徑最少中繼數，按迭代規則回溯矩陣，得到路徑的波長選擇結果和中繼選擇結果；若矩陣trans[m][n]最後一列都是無效值，則該路徑不通，動態規劃失敗；
最短路徑選擇模塊用於：比較最少中繼數計算模塊計算得到的k條路徑的最少中繼數，選擇中繼數最少的路徑作為最短路徑。
其中，最少中繼數計算模塊具體用於：以子路段按順序映射為行，以路段對所有波長是否可用映射為列，構造矩陣matrix[m][n]，且保證路徑中的每一條子路段至少存在一個都可用的統一波長，將矩陣matrix[m][n]取值0或1；
其中，0表示第n路段上第m波長不可用，1表示第n路段上第m波長可用。
其中，最少中繼數計算模塊具體用於：
計算osnr的公式為：
其中，opi表示第i個oa的輸入光功率，mi為第i個oa所在鏈路背景波道數，nfi為第i個oa的噪聲係數；
計算xi的計算公式為：
保證子路段單向光纖經過的所有光放大器oa的xi疊加值滿足其中，t＝10-t/10。
其中，最少中繼數計算模塊還用於：設置矩陣trans[m][n]內的數值初始化均為無效值，對矩陣trans[m][n]進行逐列算法迭代，每列按照從上至下的順序計算，共計算m*n次。
其中，最短路徑選擇模塊還用於：選擇中繼數最少的路徑作為最短路徑時，若出現多條路徑的中繼數相同，最短路徑選擇模塊選擇路由策略最佳的路徑，作為最短路徑。
本領域的技術人員可以對本發明實施例進行各種修改和變型，倘若這些修改和變型在本發明權利要求及其等同技術的範圍之內，則這些修改和變型也在本發明的保護範圍之內。