一種PTN網絡路由調度方法

王銳

（中國移動通信集團廣東有限公司，廣東 廣州 510623）

0 引言

分組傳送網（PTN,Packet Transport Network）是一種光傳送網絡架構和技術，在IP業務和底層光傳輸媒質之間設置了一個層面，它針對分組業務流量的突發性和統計復用傳送的要求而設計，以分組業務為核心并支持多業務提供[1]。PTN結構復雜，需要合理地調度網絡資源，以保證較好的網絡服務水平和用戶體驗。PTN路由調度的目標是尋找一條從起始網元（簡稱A端）到目標網元（簡稱Z端）之間的最佳路由[2]。該路由除了要求權值和最小外，還需要滿足多種業務約束（如必經節點、禁止節點）[3]。PTN路由調度屬于典型的帶約束最短路徑優化（CSP,Constrained Shortest Path），無法使用傳統的最短路徑算法精確求解[4-5]。

現有的技術方案一般把路由調度當成無約束最短路徑問題（SP,Shortest Path）來求解[6]，經常使用的有Dijkstra算法[7-8]、A*算法[9]等，并對基本算法進行定制修改以實現對特定業務約束的要求。比如，業務要求A、Z端的路由必經網元C，則分別計算最短路徑A-C、C-Z，再將這兩個結果拼接組成最終結果（A-C-Z）。這種方法需要窮舉所有必經點的排列，計算復雜度等于必經點數量的階乘。隨著約束數量的增加，需要計算的組合數呈爆炸式增長，無法在有效時間內求解。

現有技術方案存在計算復雜度高、支持業務約束規模受限以及算法與業務強耦合的問題，而且在計算路由時未考慮復用已有A、Z端路由方案，若路由與用戶經驗不符，則需要花費額外的精力進行調整及優化。

蟻群算法是一種仿生學算法，它是意大利學者M.Dorigo在1991年提出的[10]。在其提出后的十多年里，蟻群算法在理論研究和實際應用上均取得較大發展。到目前為止，蟻群算法已在優化領域取得眾多應用，其中在組合優化領域的應用最為廣泛，包括旅行商問題（TSP,Traveling Salesman Problem）、二次指派問題（QAP,Quadratic Assignment Problem）、車間作業調度問題（JSP,Job Scheduling Problem）、車輛調度問題（VRP,Vehicle Routing Problem）等。

蟻群算法具有的優點包括：正反饋、較強的魯棒性、分布式計算、易于與其他方法結合等。同時，蟻群算法也有自身的不足之處，包括：需要較長的計算時間、容易出現停滯現象。圍繞著改進蟻群算法的性能，從最初的螞蟻系統開始，學者們進行了大量的改進研究。蟻群算法主要包括5個基本系統：螞蟻系統（AS,Ant System）、精英系統（ASelite,Ant System with Elitist Strategy）、排序系統（ASrank,Rank-Based Version of Ant System）、蟻群系統（ACS,Ant Colony System）和最大最小螞蟻系統（MMAS,Max-Min Ant System）[10-13]。這些系統是蟻群算法不斷完善的產物，其中MMAS在大量的應用中體現出較好的品質。

本文提出了一種PTN網絡路由調度方法，該方法將路由調度的約束轉換成統一的必經節點約束，結合改進后的Dijkstra算法和帶變異策略的最大最小螞蟻算法（VMMAS,Variation Max-Min Ant System）來計算PTN最佳路由。其中，改進后的Dijkstra算法在時間復雜度和空間復雜度都有了一定的提升；VMMAS算法是基于信息素混合更新和變異更新策略對最大最小螞蟻算法進行優化得到，通過自適應調整參數和變異策略實現收斂速度與計算精確度的平衡。

1 路由調度約束轉換

PTN路由調度屬于典型的帶約束最短路徑優化，隨著約束數量的增加，計算復雜度和計算時長將會呈現指數級增長。本文將路由調度中的4類主要業務約束統一轉換為必經點約束，從而將帶約束路由調度問題轉換成節點遍歷問題求解。

1.1 業務約束轉換

目前PTN路由調度業務約束主要有4類：必須經過某些節點、必須經過某些路由、禁止通過某些節點以及禁止通過某些路由，約束由操作員在計算路由前根據規劃要求輸入。通過調整網絡參數，可以將這4類業務約束統一轉換為必經點約束。

具體約束轉換方法為：將業務約束中必須經過路由的兩端節點設置為必經點，且必須經過的路由設置為兩端節點的最短路由；將業務約束中禁止通過節點和禁止通過路由設置為節點不可達，如圖1所示。通過這種方法，4類主要業務約束都可以統一轉換成必經點約束。

圖1 通過設置節點不可達實現禁止類型約束

1.2 獲取網絡中所有必經點

必經點的獲取方法為：網絡圖經過約束轉換后，把禁止節點和禁止鏈路進行剔除，結合必經節點和必經鏈路的起、止節點，即可得出PTN網絡中的所有必經點。

如圖2所示，節點A、Z分別是所求路由的起始網元和目標網元，對于禁止通過的節點X，刪除網絡中所有目標節點為X的鏈路；對于禁止通過的鏈路L，刪除網絡中的鏈路L；對于必須經過的鏈路L，令L的起點M1和終點M2為必經節點，同時設置必經點M1和M2的最短路由為L，并且不計算M1到其他節點的最短路由，即L為必經點M1到M2的最短且唯一路由。

圖2 提取網絡中的必經點

2 最短路徑算法改進

最優路由依賴于必經點間的路徑權重之和，經轉換后的目標網絡圖能得到路由中所有的必經點。通過最短路徑算法，計算目標網絡中的路由起止點和各必經點任意兩點之間的最短路徑。

2.1 Dijkstra算法優化

傳統單源最短路徑的Dijkstra算法可以找到從起始點到其他點的最短路徑信息，在地圖障礙物較多的情況下，其搜索時間較長[14]。因此，本文提出從時間復雜度和空間復雜度這兩方面對Dijkstra算法進行優化改進，以降低計算時間和空間資源。

（1）時間復雜度優化

原生Dijkstra算法采用線性搜索，其時間復雜度為O(N2)，其中N為網絡節點數量。通過使用二分法搜索代替線性搜索，將時間復雜度由O(N2)下降到O(N*log(N))，如4萬個節點的搜索平均比較次數由2萬次下降到15次，可有效地降低搜索時間。除此以外，實際網絡中存在多條相同長度的路由，在選擇下一步要處理的節點時，相同長度的路由可以并行處理，使用并行計算代替串行計算，從而提高計算效率。

（2）空間復雜度優化

原生Dijkstra算法使用鄰接矩陣存儲路徑權值，鄰接矩陣較為簡便，也容易理解。但是，它的空間復雜度始終為O(N2)，所以在稀疏圖的情況下會導致空間的大量浪費[15]。可通過使用HashMap+List代替鄰接矩陣存儲路由關系，以減少存儲空間。比如，某生產網絡中有4萬個節點、7萬條鏈路，若使用鄰接矩陣，需要16億個存儲單元，而使用HashMap+List只需11萬個，空間復雜度由O(N2)下降到O(N+R)，其中N為網絡節點數量，R為鏈路數量。

2.2 算法對比及結果分析

原生Dijkstra算法的時間復雜度是O(N2)，并且空間復雜程度也是O(N2)[16]。而改進后的Dijkstra算法使用HashMap+List存儲路徑權值，并使用二分法搜索和并行方式進行計算，時間復雜度是O(N*log(N))，空間復雜度是O(N+R)，空間和時間復雜度都有了較大的提升。將算法改進前后的時間復雜度和空間復雜度進行對比，具體如圖3和圖4所示：

圖3 算法改進前后的時間復雜度對比

圖4 算法改進前后的空間復雜度對比

3 最優路由求解過程

最優路由調度方法：基于目標網絡必經點間最短路徑，通過使用VMMAS計算出滿足約束條件的最優路由。其中，VMMAS是基于信息素混合更新和變異更新策略對最大最小螞蟻算法進行優化得到。

3.1 個性化信息素設計

蟻群算法具有并行性、魯棒性、正反饋性等特點，最早成功應用于解決著名的旅行商問題[17]。作為一類新型的機器學習技術，已經廣泛用于組合優化問題的求解[18]。螞蟻個體之間通過一種稱為信息素的物質來進行信息傳遞，個體可以根據信息素的強度來指導自己的前進方向；而信息素會隨著時間推移逐漸揮發，于是路徑上通過螞蟻的多少就會影響該路徑殘余信息素的強度[19-21]。現有技術方案的算法與約束強耦合，在算法實現中揉進業務約束的內容。這種方式具有明顯的缺陷：不同業務約束之間可能存在互相制約，影響穩定性及正確性；業務約束實現需考慮算法本身的特點，效率低且不具有通用性。針對上述缺陷，引入自適應調整參數以制定不同環境的蟻群信息素，可使不同區域根據自身網絡特點、各自的業務習慣和要求，獲取最適配的路由調度結果。

3.2 VMMAS設計

最大最小螞蟻算法（MMAS）是比利時學者Tomas Stutzle提出的[12]，具有收斂速度快的優點，也容易陷入局部最優。Weixin Ling等學者提出了自適應參數設置策略、分段求解等方式，對蟻群算法作進一步的優化改進[22-25]。參考Dorigo[26]對蟻群算法的全局收斂性進行的初步討論，針對上述問題，對MMAS算法做了以下改進來增強算法的全局搜索能力：

（1）MMAS在開始階段只使用迭代最優螞蟻對信息素更新，以擴大算法的搜索范圍。而隨著算法的運行，MMAS逐漸增加使用至今最優螞蟻的頻率以保證算法的收斂。如果幾次更新都使用迭代最優螞蟻，至今最優解可能會因為信息素揮發而被螞蟻遺忘。因此，提出信息素混合更新策略，每次迭代同時增加迭代最優解和至今最優解的信息素以擴大最優解搜索方向。更新權重考慮迭代最優解和至今最優解的路由長度，更新規則為：

其中，τij為路由(i,j)的信息素濃度；ρ為信息素蒸發的速率；x=Cp/Cl-1，Cp為當前迭代最優解長度，Cl為當前迭代之前所找到的最優解長度；f(x)代表信息素全局更新時Δ所占的比重。

當Cp≤Cl時，本次迭代沒發現更優解，應增加Δ所占比重；反之，則應減少Δ所占比重。當Cp=Cl時，Δ和Δ比重各占1/2。

（2）MMAS存在容易陷入局部最優的不足。參考遺傳算法思路，每一輪迭代選擇部分解實施變異操作以增強全局搜索能力[27]。一般的變異算子隨機選擇某些變異位，這種操作可能會破壞優秀基因結構。參考2-opt算法思路，對變異的個體任意兩點之間的基因片段進行倒置，變異后的個體若路徑長度優于變異前，則保留變異結果，否則保留變異前個體。如變異前路徑為(1,2,3,6,5,4,7,8)，變異片段為(3,6,5)，則變異后個體為(1,2,5,6,3,4,7,8)。然后比較變異前后兩個路徑長度，若變異后路徑長度更小，則保留變異后路徑，否則保留變異前路徑。

改進后的VMMAS算法通過自適應調整參數和變異策略讓MMAS在迭代早期可以快速收斂，在迭代后期跳出局部最優，實現收斂速度與計算精確度平衡。

3.3 最優路由計算過程

計算路由分為兩部分：存量路由搜索和使用VMMAS計算。首先在存量路由中查找相同起點、終點和必經點的路由。如果存在這樣一條路由，則直接返回路由，否則繼續下一步計算。

使用VMMAS計算路由過程如下：

（1）初始化種群，將所有螞蟻置于起始網元A上；

（2）對每次迭代的每只螞蟻k：

從起始網元A出發，搜索一條遍歷A和必經點Mi(i=1,2,…,m)的路由。由節點i轉移到節點j的轉移概率為：

其中，τij為路由(i,j)的信息素濃度；nij=1/dij為啟發式因子；α、β分別代表信息素和啟發因子的影響程度；dij為節點i到節點j的最短路由長度。

每只螞蟻k都找到一條(A,…,Mki,Z)的路由后，隨機選擇部分路由實施變異算子操作。如果變異后路徑長度更小，則保留變異后路徑，否則保留變異前路徑。

對于至今最優解和迭代最優解所經過的路由，按照公式(1)更新信息素濃度，其他路由則按照以下公式更新信息素：

VMMAS計算流程圖如圖5所示：

圖5 VMMAS計算流程圖

3.4 實驗分析

實驗分析主要針對MMAS和VMMAS算法進行比較，其中VMMAS各參數取固定值，實驗只改變必經節點數量，兩種算法分別測試10次求最優解平均值并記錄算法找到最優解的次數。在Intel I5 2.6 GHz/4 GB機器運行程序，測試結果如表1所示，其中方括號中的數字表示測試過程中找到最優解的次數。鏈路權重由時延、抖動、帶寬利用率、優先級等QoS相關參數計算獲得，權重越小則鏈路質量越高。

表1 MMAS和VMMAS算法求解情況對比

通過分析表1 中兩種算法的求解結果，可以看出VMMAS所求得的結果平均值更小、找到最優解次數更多，而且隨著節點規模變大，VMMAS更能求出最優解，說明改進后的VMMAS算法具有更全面的搜索能力。

同時，通過分析MMAS 和VMMAS 算法分別求解節點數為76 的最優解演進過程，對算法的收斂情況進行對比，具體如圖6 所示：

圖6 MMAS和VMMAS算法求解節點數為76的演進情況對比

從圖6可以看出，雖然MMAS能很快找到次優解，但之后需要經過480次迭代后才能找到下一個更優解；而VMMAS能夠一直保持較穩定的全局搜索能力，收斂速度越來越快于MMAS，最終比MMAS更快找到最優解。

綜上所述，VMMAS在全局搜索能力和收斂速度方面均勝于MMAS算法，其不僅能擴大螞蟻的搜索范圍、加快算法收斂速度，還能減少算路陷入局部最優的情況，使得路由調度更加精確、快速。

4 結束語

本文將路由調度問題轉換成節點遍歷問題，并綜合使用改進后的Dijkstra算法和VMMAS解決PTN網絡路由調度，可以降低路由計算效率、提高路由計算準確性，并有效地解決復雜度高、業務約束繁多以及算法與業務強耦合的現狀問題。

改進Dijkstra算法計算兩點的最短路徑時間復雜度由O(N2)下降到O(N*log(N))，而實際生產網絡節點數量較大，改進算法可以減少計算時間超過1 000倍；VMMAS通過信息素混合更新和變異策略，使得在算路迭代早期可以快速收斂，在迭代后期跳出局部最優，實現收斂速度與計算精確度平衡。綜上所述，本文所提出的方法在計算時間復雜度、空間復雜度和計算精度都有不同程度提升。同時，通過引入自適應調整參數和既有路由搜索，能滿足不同PTN網絡的個性化需求和相關歷史經驗，計算出最優路由，減少人工干預。