一種PTN網(wǎng)絡(luò)路由調(diào)度方法

王銳

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

0 引言

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

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

現(xiàn)有技術(shù)方案存在計算復(fù)雜度高、支持業(yè)務(wù)約束規(guī)模受限以及算法與業(yè)務(wù)強耦合的問題，而且在計算路由時未考慮復(fù)用已有A、Z端路由方案，若路由與用戶經(jīng)驗不符，則需要花費額外的精力進行調(diào)整及優(yōu)化。

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

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

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

1 路由調(diào)度約束轉(zhuǎn)換

PTN路由調(diào)度屬于典型的帶約束最短路徑優(yōu)化，隨著約束數(shù)量的增加，計算復(fù)雜度和計算時長將會呈現(xiàn)指數(shù)級增長。本文將路由調(diào)度中的4類主要業(yè)務(wù)約束統(tǒng)一轉(zhuǎn)換為必經(jīng)點約束，從而將帶約束路由調(diào)度問題轉(zhuǎn)換成節(jié)點遍歷問題求解。

1.1 業(yè)務(wù)約束轉(zhuǎn)換

目前PTN路由調(diào)度業(yè)務(wù)約束主要有4類：必須經(jīng)過某些節(jié)點、必須經(jīng)過某些路由、禁止通過某些節(jié)點以及禁止通過某些路由，約束由操作員在計算路由前根據(jù)規(guī)劃要求輸入。通過調(diào)整網(wǎng)絡(luò)參數(shù)，可以將這4類業(yè)務(wù)約束統(tǒng)一轉(zhuǎn)換為必經(jīng)點約束。

具體約束轉(zhuǎn)換方法為：將業(yè)務(wù)約束中必須經(jīng)過路由的兩端節(jié)點設(shè)置為必經(jīng)點，且必須經(jīng)過的路由設(shè)置為兩端節(jié)點的最短路由；將業(yè)務(wù)約束中禁止通過節(jié)點和禁止通過路由設(shè)置為節(jié)點不可達，如圖1所示。通過這種方法，4類主要業(yè)務(wù)約束都可以統(tǒng)一轉(zhuǎn)換成必經(jīng)點約束。

圖1 通過設(shè)置節(jié)點不可達實現(xiàn)禁止類型約束

1.2 獲取網(wǎng)絡(luò)中所有必經(jīng)點

必經(jīng)點的獲取方法為：網(wǎng)絡(luò)圖經(jīng)過約束轉(zhuǎn)換后，把禁止節(jié)點和禁止鏈路進行剔除，結(jié)合必經(jīng)節(jié)點和必經(jīng)鏈路的起、止節(jié)點，即可得出PTN網(wǎng)絡(luò)中的所有必經(jīng)點。

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

圖2 提取網(wǎng)絡(luò)中的必經(jīng)點

2 最短路徑算法改進

最優(yōu)路由依賴于必經(jīng)點間的路徑權(quán)重之和，經(jīng)轉(zhuǎn)換后的目標網(wǎng)絡(luò)圖能得到路由中所有的必經(jīng)點。通過最短路徑算法，計算目標網(wǎng)絡(luò)中的路由起止點和各必經(jīng)點任意兩點之間的最短路徑。

2.1 Dijkstra算法優(yōu)化

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

（1）時間復(fù)雜度優(yōu)化

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

（2）空間復(fù)雜度優(yōu)化

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

2.2 算法對比及結(jié)果分析

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

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

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

3 最優(yōu)路由求解過程

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

3.1 個性化信息素設(shè)計

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

3.2 VMMAS設(shè)計

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

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

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

當Cp≤Cl時，本次迭代沒發(fā)現(xiàn)更優(yōu)解，應(yīng)增加Δ所占比重；反之，則應(yīng)減少Δ所占比重。當Cp=Cl時，Δ和Δ比重各占1/2。

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

改進后的VMMAS算法通過自適應(yīng)調(diào)整參數(shù)和變異策略讓MMAS在迭代早期可以快速收斂，在迭代后期跳出局部最優(yōu)，實現(xiàn)收斂速度與計算精確度平衡。

3.3 最優(yōu)路由計算過程

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

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

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

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

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

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

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

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

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

圖5 VMMAS計算流程圖

3.4 實驗分析

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

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

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

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

圖6 MMAS和VMMAS算法求解節(jié)點數(shù)為76的演進情況對比

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

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

4 結(jié)束語

本文將路由調(diào)度問題轉(zhuǎn)換成節(jié)點遍歷問題，并綜合使用改進后的Dijkstra算法和VMMAS解決PTN網(wǎng)絡(luò)路由調(diào)度，可以降低路由計算效率、提高路由計算準確性，并有效地解決復(fù)雜度高、業(yè)務(wù)約束繁多以及算法與業(yè)務(wù)強耦合的現(xiàn)狀問題。

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