一種資源通道聯合優化P圈配置方法與流程

2023-12-06 16:55:56

本發明涉及網絡技術領域，特別是涉及一種資源通道聯合優化P圈配置方法。

背景技術：

隨著光纖通信技術的廣泛採用，由於光纖的高速大容量的特點使得網絡故障給社會和經濟造成的危害非常嚴重，因此需要研究光網絡的生存性技術，P圈是網狀網的一種保護方法，可以為圈上鏈路提供1條保護路徑，為跨接鏈路提供2條保護路徑，它綜合了環網恢復速度快和網狀網資源利用效率高的優勢，可以實現50ms級的保護。目前對P圈配置方法的研究主要可以分為兩類：啟發式算法和線性規划算法，啟發式算法耗時較少，得到的是一個優化解，而線性規划算法雖然得到的是一個最優解，但是耗時巨大。如何找到耗時少且資源利用效率高的P圈配置方法是P圈配置研究的主流方向，然而無論哪一類方法，P圈的配置方法都分為兩步：高質量的備選P圈集合的計算和空閒容量的分配，其中備選P圈集合的計算需要消耗大量的時間。

技術實現要素：

為了克服上述現有技術的不足，本發明提供了一種資源通道聯合優化P圈配置方法，來減少P圈的配置時間並提高資源利用效率，它屬於線性規劃方法，。

本發明所採用的技術方案是，一種資源通道聯合優化P圈配置方法，包含以下三個步驟，如附圖1所示。

1.P圈集合數量估算

總的P圈集合數量J是求解模型的一個預置參數，可以通過待求解網絡的拓撲結構和工作容量來估算，估算按照如下公式：

其中(u,v)表示節點u和v之間的鏈路，luv是節點u和v之間的工作容量；E是網絡中所有鏈路的集合；將段定義為一條至少包含兩條鏈路並且中間節點的度數為2的路徑，則S是所有段上的鏈路的集合；δ是一個較小的正整數。

2.目標函數設置

本發明使用空閒容量最小作為求解目標，具體的公式如下：

其中j是P圈集合CSj的索引號；cuv是系統為鏈路(u,v)增加一個單位的空閒容量所需的成本，如果節點之間的距離僅採用跳數作為衡量單位，則對於網絡中存在的所有鏈路來說，cuv＝1；表示在P圈集合CSj中，節點u和v之間是否存在向量u→v，取1表示存在，取0表示不存在。

3.約束條件設定

3.1基於節點梯度值構造向量

本發明使用一個圈上向量u→v或者v→u表示一個P圈集合CSj的圈上鏈路，對於向量u→v，定義u是頭部節點，v是尾部節點，在構造P圈集合CSj的時候，給節點u分配一個P圈節點梯度值尾部節點的P圈節點梯度值比頭部節點大，在一個P圈中，如果節點u同時作為2個向量的頭部節點，則定義節點u為根節點，如果節點v同時為2個向量的尾部節點，則定義節點v為反轉節點，節點梯度值構造的向量如附圖2所示。

3.2排除節點梯度值衝突的P圈

如果一個P圈中有唯一的根節點和反轉節點成對出現，那麼一系列合理的P圈節點梯度值就可以分配到當前的P圈，但是如果沒有唯一的根節點和反轉節點成對出現，就會出現P圈節點梯度值的衝突，如附圖3所示，因為尾部節點的值總是比頭部大，如果缺乏反轉節點將會無法形成一個閉合的P圈。為了避免衝突的出現，當一個P圈集合CSj中有多個P圈出現時，只保留具有唯一的根節點和反轉節點成對出現的那個P圈，將其它所有的P圈都排除掉。

本發明的有益效果是：是簡化了P圈配置步驟，不需要先計算備選P圈集合，與啟發式算法相比，本發明具有更高的資源利用效率，與傳統的線性規劃方法相比，本發明取消了備選P圈集合計算這個步驟，耗時更短。

附圖說明

圖1為本發明的整體步驟示意圖；

圖2為基於節點梯度值的向量構造示意圖；

圖3為節點梯度值衝突的示意圖；

具體實施方式

下面結合附圖對本發明進一步說明。

1.P圈集合數量估算

總的P圈集合數量J是求解模型的一個預置參數，可以通過待求解網絡的拓撲結構和工作容量來估算，估算按照如下公式：

其中(u,v)表示節點u和v之間的鏈路；luv是節點u和v之間的工作容量；E是所有鏈路的集合；將段定義為一條至少包含兩條鏈路並且中間節點的度數為2的路徑，則S是所有段上的鏈路的集合；δ是一個較小的正整數。

2.目標函數設置

本發明使用空閒容量最小作為求解目標，具體的公式如下：

其中j是P圈集合CSj的索引號；cuv是系統為鏈路(u,v)增加一個單位的空閒容量所需的成本，如果節點之間的距離僅採用跳數作為衡量單位，則對於網絡中存在的所有鏈路來說，cuv＝1；表示在P圈集合CSj中，節點u和v之間是否存在向量u→v，取1表示存在，取0表示不存在。

3.約束條件設定

3.1所有鏈路的集合E中每一條鏈路(u,v)在構造一個P圈集合CSj時最多能夠用一個向量表示，可以是u→v或者v→u，或者沒有被選中，可以用如下的公式表示：

3.2使用向量構造P圈集合CSj,網絡中每一個節點都有2個或者0個圈上向量與之相關(不考慮向量的方向)，可以用如下的公式表示：

其中V是網絡中所有節點的集合；是0-1變量，如果節點u在P圈集合CSj上，則取1，否則取0；

3.3確保工作容量受到100％的保護，可以用如下的公式表示：

其中是0-1變量，表示鏈路(u,v)能否受到P圈集合CSj的保護，如果能受到保護，則取1，否則取0；

3.4每一個P圈集合CSj中最多有一個根節點，可以用如下的公式表示:

其中為0-1變量，表示節點u是否為P圈集合CSj的根節點，是則取1，否則取0；

3.5在一個P圈集合中，只有根節點可以作為2個向量的頭部節點，其它節點最多可以作為1個向量的頭部節點，這樣能夠保證根節點和反轉節點可以唯一成對出現，用如下的公式表示：

3.6向量u→v的尾部節點比頭部節點的P圈節點梯度值更大，可以用如下的公式表示：

其中為小數變量，是構造P圈集合CSj時節點u的P圈節點梯度值，α是一個預先定義的小數常量，滿足

3.7隻有鏈路(u,v)的兩個端節點都在P圈集合CSj上時，鏈路(u,v)才能夠被P圈集合CSj中唯一的P圈保護，可以用如下的公式表示：

3.8對單個P圈的長度或者跳數進行限制，可以用如下的公式表示：

其中L為單個P圈允許的最多跳數；

以步驟2為目標函數，以步驟1中的J值為參數，使用步驟3中的約束條件，進行線性規劃求解就是本發明的內容。