張佳唯, 錢鳳臣, 楊俊強, 趙 騫, 張崢嶸

(國防科技大學信息通信學院, 陜西 西安 710106)

0 引 言

近年來,隨著云計算、視頻點播等高流量型應用的不斷興起以及物聯(lián)網等新型網絡范式的廣泛使用,以光纖通信為基礎的現代信息通信技術受到越來越多的關注。其中,基于波分復用(wavelength division multiplexing,WDM)技術的第二代光網絡采用固定波長資源分配模式,已無法滿足具有較大帶寬需求且靈活復雜的新型流量業(yè)務,使得目前急需一種能夠支持高動態(tài)、高容量和高傳輸質量服務的網絡架構。由此,以光正交頻分復用(optical orthogonal frequency division multiplexing,O-OFDM)技術為基礎的彈性光網絡(elastic optical networks,EONs)應運而生。

在EONs中,帶寬資源規(guī)劃的高靈活性是其彈性概念的重要體現之一,所涉及的關鍵技術稱為路由與頻譜分配(routing and spectrum allocation,RSA)算法。迄今為止,有關RSA算法的研究已經較為深入,但當前公開發(fā)表的相關綜述性文章偏于陳舊,并且詳述的大多為靜態(tài)性算法,即業(yè)務需求均為已知。然而,未來應用中網絡業(yè)務流量將呈現出較強的突發(fā)性和不確定性,因此對動態(tài)求解算法的深入總結概括可以為后續(xù)研究人員提供更有實用價值的參考。本文首先簡要介紹EONs的概念內涵,接著對RSA問題展開描述,然后分別從靜態(tài)和動態(tài)特性入手,基于精確算法、智能優(yōu)化算法、啟發(fā)式算法以及學習型算法4個大類對近5年來RSA算法的最新研究現狀進行總結剖析,最后指出RSA算法的未來發(fā)展方向。

1 彈性光網絡

作為下一代最具前景的光傳輸網絡,EONs的概念起源于頻譜可切片彈性光連接網絡(spectrum-sliced elastic optical path network, SLICE),通過在光頻域中引入靈活的粒度,提升頻譜資源的利用效率以及網絡的可擴展性。

EONs的核心是O-OFDM技術,這是一種多載波調制技術,可以將高速數據流調制在相互正交的低速子載波上進行傳輸。如圖1所示,與需要在波長之間設置固定信道間隔來消除干擾的WDM技術相比,OFDM由于正交性而允許單個子載波的頻譜重疊,節(jié)約了帶寬資源。同時,OFDM通過靈活的粒度聚合服務可以支持從Gbps到Tbps等多種數據速率,并能夠根據傳輸質量調整子載波數量和調制格式,完成高效的頻譜分配,實現了動態(tài)帶寬的擴展與收縮,增大了系統(tǒng)容量。在傳輸流量不足時,OFDM還可關閉某些子載波來節(jié)省功耗。此外,每個子載波所調制符號的持續(xù)時間比相同總數據速率的單載波系統(tǒng)的持續(xù)時間長得多,縮減了OFDM信號的周期。

圖1 WDM與OFDM頻譜劃分示例

EONs的基礎網絡架構如圖2所示,主要涉及兩大類節(jié)點:一類是處在網絡邊緣位置上,連接用戶端和中心網絡的帶寬可變收發(fā)器(bandwidth-variable transponder, BVT);另一類是處在網絡中心位置上,連接BVT的帶寬可變波長交叉連接器(bandwidth-variable wavelength cross-connector, BV-WXC)。工作時,BVT依據用戶的業(yè)務需求配置子載波個數并選取調制方式,以此產生合適的光信號;BV-WXC對接收的光信號進行連續(xù)頻譜分割和多粒度交換,以完成相應信號到下一節(jié)點的傳送。通過上述兩類節(jié)點的配合,最終能夠在EONs中以高頻譜效率建立起端到端的靈活光路徑。

圖2 EONs基礎架構

2 RSA問題

RSA問題最早由Jinno等人于2009年和EONs的概念一同提出,是指根據用戶需求在源節(jié)點和目的節(jié)點之間找到一條合適的光路徑,并為此光路請求分配相應的頻譜資源,目的是滿足某種最優(yōu)的性能指標(如阻塞率最低、頻譜利用率最高等)。

在EONs中,頻譜資源的最小分配單元稱為頻隙(frequency slot, FS),多個連續(xù)FS的組合稱為FS塊(FS block, FSB),從簡化網絡設計的角度出發(fā),單個FS的粒度大小通常被設置為12.5 GHz。頻譜資源在分配時需要遵循3個最基本的約束條件。

(1) 頻譜連續(xù)性約束:如果某業(yè)務請求需要個FS,則必須為其分配個連續(xù)的FS。

(2) 頻譜一致性約束:建立業(yè)務請求對應的端到端光路徑時,必須在該路徑所經過的每條鏈路上分配位置相同的個連續(xù)FS。

(3) 頻譜不重疊約束:同一條鏈路中任意兩個已占用FSB之間不可以出現FS重疊的情況,即同一個頻隙不能同時被分配給多個業(yè)務。

應用圖3所示的例子對上述3項約束內涵加以解釋。圖3中,上半部分表示一個結構簡單的EONs,下半部分表示當前時刻網內各條鏈路上頻譜資源的使用情況(白色代表未被占用,灰色代表已被占用)。假設此時需要建立由節(jié)點到節(jié)點的一條光路請求,該請求占用2個FS。通過判斷發(fā)現,由于在鏈路1和鏈路3中不存在相同位置上的連續(xù)兩個空閑FS,因此無法選擇——這條路徑。相比之下,在鏈路1、鏈路2和鏈路4中對應位置索引為1和2的頻隙是連續(xù)(滿足連續(xù)性約束)且空閑的(滿足不重疊約束)以及對齊的(滿足一致性約束),從而可以選取路徑———來建立光路請求。

圖3 頻譜連續(xù)性約束、一致性約束和不重疊約束示例

經過上述討論可以看出,EONs中網絡資源的規(guī)劃從單個波長細化到了頻譜層面,精細的頻譜劃分粒度導致整個網絡范圍內需要管理的資源數量變得巨大;加之存在連續(xù)性、一致性以及保護帶寬等更嚴苛的約束限制,使得每條光路徑的建立都會在一定程度上改變網內資源的分布情況,進而影響到業(yè)務的頻譜分配結果,這種緊密的耦合關系進一步增大了實際應用中資源規(guī)劃的復雜程度,從而加劇了RSA問題的求解難度。同時,RSA問題已被證明是一種非確定性多項式(non-deterministic, NP)難問題,即不存在多項式時間算法進行最優(yōu)化求解。

當前,基于RSA問題的多種復雜變體形式也備受關注。如根據不同的路徑長度和傳輸質量采用不同的調制格式時,RSA問題演變?yōu)榱寺酚?、調制與頻譜分配(routing, modulation, and spectrum assignment, RMSA)問題;考慮動態(tài)建立和拆除光路產生的頻譜碎片時,RSA問題則變成了頻譜碎片感知RSA(fragmentation aware RSA, FA-RSA)問題;依照業(yè)務流類型的不同,RSA問題又可以劃分為單播(unicast)、任播(anycast)以及組播(multicast)RSA問題。此外,還包括流量疏導RSA(traffic grooming with RSA, TG-RSA)問題、生存性 RSA(survivability RSA, S-RSA)問題等。

3 RSA算法

針對RSA這一關鍵問題,根據業(yè)務請求是否為已知,將對應的求解算法歸為兩大類,分別是靜態(tài)RSA算法(業(yè)務請求提前給定)以及動態(tài)RSA算法(業(yè)務請求隨機到達),如圖4所示。

圖4 RSA配算法分類圖

3.1 靜態(tài)RSA算法

在靜態(tài)RSA算法中,輸入包括一組源節(jié)點、目的節(jié)點和帶寬需求均已知的業(yè)務請求,輸出的是在離線狀態(tài)下為每個請求所選擇的光路徑以及指定的連續(xù)FS資源,優(yōu)化目標一般為最小化頻譜資源占用總量。

3.1.1 精確算法

為了深入解析RSA問題的結構特性并求取最優(yōu)化結果,整數線性規(guī)劃(integer linear programming, ILP)方法被提出用以建立問題模型。其中,文獻[21-24]詳述了多種相關的ILP模型,這是在早期階段依據不同應用背景、不同優(yōu)化目標以及不同假設條件所提出的。在此基礎之上,文獻[25]根據定義決策變量的表達含義不同(即鏈路資源和FS資源的占用情況是用一組變量聯(lián)合表示,還是用兩組變量分別表示),共建立了4個基礎性的ILP模型并衍生出十多種變體形式,通過分析各模型所涉及變量與約束的數量級,明確了模型的復雜度,最后利用數字優(yōu)化技術CPLEX軟件求解測試算例,對比各模型的性能,總結出其適用性。

當問題規(guī)模稍有增大時,僅依靠求解器是無法在可行時間內得出最佳解決方案的,為此一些精確算法被引入以提升求解效率,包括列生成法(column generation, CG)用于線性松弛模型求出問題下界(lower bound, LB),或利用分支定界法(branch and bound, BB)、分支定價法(branch and price, BP)等直接求取整數解。由于具備求解大規(guī)模變量問題的優(yōu)良特性,CG被廣泛采用,基本思路為:首先將“列”定義為可滿足業(yè)務請求的一種候選光路結構,該結構包含鏈路與FS占用信息,通過啟發(fā)式規(guī)則首先獲得一組初始列,然后根據建立的光路生成子問題模型(如最短路徑模型、最小化平均頻譜使用數量模型),查找并添加新列以提高求解質量。此外,BP因為結合了分支定界的求整特性與列生成的解大規(guī)模特性,也被引入到RSA問題的求解中,并且通過相關啟發(fā)式方法的配合(如使用模擬退火(simulated annealing, SA)、貪婪規(guī)則、遺傳算法(genetic algorithm, GA)改善解方案的上界,使用松弛法則改善解方案的下界),提升了算法的求解性能,使其能夠解決商用求解器(如CPLEX)難以求出的較大規(guī)模問題實例。

3.1.2 啟發(fā)式算法

利用精確算法固然能得到最優(yōu)解,但是隨著網絡規(guī)模與業(yè)務數量的進一步增加,問題對應的復雜度會不斷提升,導致求解時間代價變得非常昂貴。比如,對于一種含有14個節(jié)點、46條鏈路的大型網絡結構而言,采用ILP模型是無法在有效時間內輸出可行結果的。因此,啟發(fā)式算法的提出對于在有限時間內獲取問題的可行解具有極為重要的意義。

從RSA問題結構的角度出發(fā),關于啟發(fā)式算法的設計,通常做法是將其分為兩個獨立的子算法進行研究,包括路由選擇子算法與頻譜分配子算法,稱為兩步法:首先為每個業(yè)務在光網絡中進行選路,常用的策略包括固定路由(fixed routing, FR)、固定備選路由(fixed alternate routing, FAR)以及自適應路由(adaptive routing, AR)等;接著依據所選路徑的狀態(tài)為其分配連續(xù)可用的FS,常用的策略包括首次適配(first fit, FF)、尾部適配(last fit, LF)、隨機適配(random fit, RF)以及精確適配(exact fit, EF)等。此外,還有綜合考慮兩類子算法特性的方式,通過采用貪婪策略或基于學習的規(guī)則同時進行路由選擇與頻譜資源查找,稱為一步法。本節(jié)只涉及兩步法和一步法中用于靜態(tài)RSA算法設計的部分內容,下節(jié)會重點介紹其在動態(tài)RSA算法中的應用。

根據以上多種基礎性策略,一些更為復雜有效的啟發(fā)式算法被提出。文獻[39]從提升能量效率和降低業(yè)務阻塞率的角度考慮,設計了一種基于能量感知的改進RSA算法。文獻[40]以各FS對齊程度為考慮,提出了一種首尾精確適配(first-last-exact fit, FLEF)策略,目的就是為了增加連續(xù)可用的且對齊的FS數量,從而提升頻譜使用效率。文獻[41]中介紹了一種基于頻譜優(yōu)先的分層算法,該算法采用一步式貪婪策略,以業(yè)務的FS需求為基礎,通過查找可用鏈路并構建層級子圖的方式實現了路由與頻譜資源的聯(lián)合分配。文獻[42]利用節(jié)點度數設計了具有分光能力的節(jié)點選擇策略,并提出了一種預計算最短路徑樹的RSA算法并驗證了其有效性。此外,存在部分研究以靜態(tài)RSA問題特性為依據,嘗試借鑒傳統(tǒng)的優(yōu)化調度理論進行計算。比如,文獻[43-44]將靜態(tài)RSA問題映射為多處理器調度模型,并通過設計表調度算法(list scheduling algorithm, LSA)進行求解;文獻[45]建立了靜態(tài)RSA問題的圖染色模型,并分別針對鏈狀網絡和環(huán)狀網絡提出了有效的頻譜分配算法。具體總結如圖5所示。

圖5 靜態(tài)啟發(fā)式策略

3.1.3 智能優(yōu)化算法

除了上述基于直觀或經驗構造出的啟發(fā)式算法外,還有一類是根據人體智能、生物群體社會性或自然現象規(guī)律總結出的方法,稱之為智能優(yōu)化算法,也稱元啟發(fā)式算法。與啟發(fā)式算法在可接受時間內給出待解決優(yōu)化問題的一個可行解不同,智能優(yōu)化算法在任務規(guī)模變得更大、約束條件變得更加苛刻時能夠具有良好的問題探索能力和收斂效率,尤其是在解決NP難問題時,智能優(yōu)化算法可以有效應對“組合爆炸”現象, 獲取到問題的滿意解。

智能優(yōu)化算法目前已廣泛應用于交通、醫(yī)療、工業(yè)制造等多個領域。其中,采用經典之一的GA求解靜態(tài)RSA問題已得到深入研究。為了建立完備的路由空間,文獻[46]提出了一種基于優(yōu)先權編碼尋路的GA,并結合最大化頻譜重合度原則來降低業(yè)務阻塞率。在考慮單播與任播業(yè)務資源聯(lián)合分配的需求下,文獻[47]將局部搜索引入GA中以改善RSA問題的求解效率。在GA的基礎框架之下,文獻[48]根據組播業(yè)務特性設計了合理的選擇與交叉算子,有效提升了解的質量。為了降低種群維護的高計算成本,文獻[49]提出了一種動態(tài)子種群數量控制策略來設計相應的RSA算法。文獻[50]根據GA的思想,分別提出了改進資源分配算法來處理純單播業(yè)務以及混合資源分配算法來處理單播與組播混合業(yè)務。文獻[51]結合深度神經網絡與GA,設計了一種基于軟故障感知的RSA算法。當考慮同時優(yōu)化如FS占用總數、服務質量等多個目標時,文獻[52-54]提出了多目標GA來求解RSA問題。

此外,其他一些成熟的智能優(yōu)化算法框架也被引入到靜態(tài)RSA算法的設計中,包括禁忌搜索(tabu search, TS)、粒子群優(yōu)化(particle swarm optimization, PSO)、差分進化(differential evolution, DE)、SA、蜂群優(yōu)化(bee colony optimization, BCO)等。

以上總結了近年來主要的靜態(tài)RSA算法,而未來大多面臨的是隨機到來的業(yè)務請求,網絡環(huán)境會變得愈發(fā)復雜,因此動態(tài)RSA算法的研究更加符合EONs的發(fā)展趨勢,同時也更具挑戰(zhàn)性。

3.2 動態(tài)RSA算法

在動態(tài)RSA算法中,輸入為隨機到達的業(yè)務請求(包括源節(jié)點、目的節(jié)點、帶寬需求、到達時間和持續(xù)時間等屬性),輸出的是根據當前網絡狀態(tài)為每項業(yè)務請求在線選擇的光路徑以及指定的連續(xù)頻譜資源,優(yōu)化目標一般為最小化業(yè)務阻塞率。

3.2.1 啟發(fā)式算法

動態(tài)RSA問題通常涉及到業(yè)務的時間屬性,即隨著時間推移,光路連接會不斷被建立與釋放,由此導致網內頻譜資源的狀態(tài)總是處于變化之中,極大增加了網絡資源的優(yōu)化難度。經過工程實踐驗證,啟發(fā)式算法目前是解決動態(tài)優(yōu)化問題的一類有效技術。區(qū)別于第3.1.2節(jié)中的內容,本節(jié)將著重介紹啟發(fā)式算法在動態(tài)RSA問題中的應用。

在動態(tài)場景下,業(yè)務的隨機到來和離去使得光路連接處于不斷的拆建過程之中,路由狀態(tài)復雜多變;同時,頻譜資源也隨之被反復占用與釋放,進而產生了大量難以滿足一致性和連續(xù)性約束且無法為后續(xù)業(yè)務提供服務的小頻譜塊,稱之為頻譜碎片。迄今為止,絕大多數動態(tài)RSA算法的研究都是以路由狀態(tài)和頻譜碎片作為最基礎的啟發(fā)式信息。圖6所示為動態(tài)啟發(fā)式RSA算法的基本框架。

圖6 動態(tài)啟發(fā)式算法框架

(1) 頻譜碎片感知

頻譜碎片感知是指當業(yè)務到達時，通過某些策略預判出頻譜塊最適合的分配位置，所謂最適合，即盡可能使分配后剩余的空閑FS保持連續(xù)且齊整，以承載更多后續(xù)業(yè)務，達到最小化碎片產生數量的目的。

文獻[62]以指定時間窗內到達業(yè)務的帶寬需求為基礎定義了業(yè)務的優(yōu)先級指標，同時依據當前光網絡中所有空閑FSB的大小找出中位數所在，接著通過判斷此中位數與各業(yè)務帶寬需求的關系并結合業(yè)務優(yōu)先級，進而確定出最終的頻譜分配方案。文獻[63]采用了一種可變分組機制，該機制首先依據帶寬需求將業(yè)務分為不同種類，接著對應不同業(yè)務類型將鏈路總頻段劃分為多個組，每個組僅需明確其起始FS位置，并規(guī)定相鄰兩組之間的空閑FS可根據實際需要合并至任意一組中；此外還定義了組規(guī)模的概念與計算公式，以此為動態(tài)業(yè)務選取最優(yōu)路徑與頻譜塊。文獻[64]首先采用了條最短路算法離線計算業(yè)務路由，接著定義了塊成本函數的概念來評估可用的候選頻譜塊，該函數的取值基于鏈路中相鄰FS的狀態(tài)而定。文獻[65]引入了頻譜候選窗的概念來為新到達業(yè)務篩選可用的FSB，同時基于精確適配策略定義了空閑頻譜連續(xù)度的指標，并以此為依據選出最適合此業(yè)務的頻譜資源。文獻[66]定義了鄰接度和鄰接度降低的概念分別來衡量空閑FSB的鄰接程度以及使用過后的鄰接變化程度，并據此提出了最小化路徑鄰接度降低和鏈路鄰接度降低算法。

(2) 頻譜碎片重構

頻譜碎片重構也稱碎片整理，即通過網絡中斷的方式，利用一定手段對已有光路徑進行重新建立，或對已分配頻譜進行位置搬移，進而達到最大化碎片集中整合的目的。

文獻[67]以定義頻譜連續(xù)度的預設閾值為啟動機制，采用頻譜搬移的思想提出了基于滑動窗口機制下的重路由算法；同時，根據網絡的實時拓撲狀態(tài)，利用介數分析法評估節(jié)點的重要度并確定出關鍵鏈路，由此提出了基于關鍵鏈路的重路由算法。文獻[68]在綜合考慮局部頻譜資源狀態(tài)和業(yè)務連接需求的情況下，巧妙設計了路徑整理前后的頻譜可用度、阻塞業(yè)務需求度等計算公式，并由此提出了基于策略的頻譜整理比較觸發(fā)機制以及基于所選路徑的阻塞觸發(fā)頻譜碎片整理算法。為了找尋頻譜分配結果的最優(yōu)性與頻譜重配置所導致的網絡中斷次數之間的平衡關系，文獻[69]通過建立一種新穎的混合整數線性規(guī)劃模型來為新到達業(yè)務選取合適的路徑，并基于首次適配策略提出了一種動態(tài)啟發(fā)式算法來確定業(yè)務所占的FS位置。

(3) 路由狀態(tài)感知

所謂路由狀態(tài)感知，即通過對候選鏈路或光路徑的狀態(tài)信息(如能耗、距離、負載、碎片化程度等)進行評估，并基于評估結果為新到達業(yè)務選取一條合適的光路徑，以達到最小化路由狀態(tài)受影響的目的。

針對傳輸速率實時變化的業(yè)務,文獻[70]提出了兩種頻譜擴展/縮減方案用于網絡性能分析,以確定出各方案實施后的網絡阻塞概率,并基于條最短路策略設計了路徑最小負載的啟發(fā)式規(guī)則。文獻[71]以網絡能耗為考慮,提出了持續(xù)時間感知的能效路由算法求取代價最小的光路徑,隨后根據業(yè)務與所選光路在時間域上的關系, 分配時間差較小且頻譜連貫度最高的頻譜塊作為承載資源。文獻[72]提出了一種固定/備用選路機制,該機制能夠實時構建節(jié)點對間的最短和次最短路徑信息,并通過定義頻譜碎片規(guī)模的權值量化公式選取合適的路徑,接著基于精確適配與最小可用原則設計了頻譜動態(tài)匹配策略?？紤]在每條鏈路具有多根光纖的前提下,文獻[73]首先離線計算出每個節(jié)點對之間可行的候選路徑及其概率分布,接著提出了一種基于后續(xù)狀態(tài)感知和路徑選擇概率的頻譜分配算法。文獻[74]提出了一種距離自適應路徑策略,該策略同步考慮了各條備選路徑的跳數及其可達的最高調制等級,并以此為基礎確定出終選路徑。文獻[75]通過設置光路徑對應跳數的增量閾值,提出了一種基于約束的低索引塊策略,該策略主要考慮在跳數較少的路徑上分配起始索引較低的頻譜塊,而當某一路徑的跳數大于另一條但可用頻譜塊的最低起始索引又小于另一條時,如果其跳數之差不大于預設閾值,則優(yōu)先選取低索引FSB及所在路徑。文獻[76]以高調制等級作為路徑的首選標準,其次定義了外部碎片指標,考慮當多條路徑調制等級相同時將選取該指標最小的一條,同時還考慮當多條路徑的上述指標也均相同時,則基于最小跳數作出路由決策,最后又結合首次適配與尾部適配策略提出了一種首尾混合適配頻譜分配方案。考慮到光信號質量易受物理層損耗的影響,文獻[77]引入了跨層優(yōu)化的思想,首先通過對鏈路中光信噪比與色散這兩項參數值的估計來評估其狀態(tài),接著基于評估結果提出了鏈路狀態(tài)感知路由算法來搜索滿足傳輸質量要求的可行路徑,同時設計了碎片減少算法來分配頻譜資源。在光纖鏈路可以改變調制格式的前提下,文獻[78]優(yōu)先選擇節(jié)點數最少的路徑或在節(jié)點數相同時選擇距離之和最小的路徑,并將此路徑劃分成一定數目的子路徑,然后采用距離自適應調制技術為每條子路徑分配頻譜資源。

(4) 其他策略

不同于上述3種常用的動態(tài)啟發(fā)式思想,還有部分其他新穎的策略被提出。

例如,考慮不同網絡應用在時延敏感度和帶寬感知度的差異性,文獻[79]構建了3類典型的業(yè)務請求模型,通過在時間維度上采用離散化處理的方式進行網絡操作,并依據各類業(yè)務特性設計了多種啟發(fā)式策略,由此生成了對應的帶寬資源動態(tài)調度算法。文獻[80]以分層圖模型為基礎,對其進行修改并建立了一種新的過濾圖來表示網絡實時狀態(tài),接著通過采用首次適配與最短路的思想設計出兩種動態(tài)啟發(fā)式算法,此外還推導出一個具有較高精度的分析模型以估計所需的分層圖數量。文獻[81]通過建立一種線性規(guī)劃模型來離線解決路由子問題,此模型可確保所有鏈路的阻塞水平維持在一個閾值域內,且該步計算耗時為可接受的秒級范圍,并基于獲取的路由信息采用首次適配策略在線分配頻譜。為了應對業(yè)務分配路徑不均勻的現象,文獻[82]設計了一種基于節(jié)點重要度的路由選擇方法,該方法以犧牲業(yè)務路徑距離為代價,將大量集中于關鍵節(jié)點上的業(yè)務安排至其他節(jié)點,并利用精確適配策略與首次適配策略相結合的方式完成頻譜分配。文獻[83]考慮在傳統(tǒng)WDM光網絡向EONs轉型的過渡期間,主要是以固定柵格與靈活柵格并存的混合形式出現,由此設計了一種基于混合網格感知的動態(tài)資源規(guī)劃算法。

3.2.2 學習型算法

當前,啟發(fā)式算法仍是求解各類動態(tài)性優(yōu)化問題的常規(guī)方法,具有較強的適用性,但由于其受限在僅能維持某一種或某幾種特定的求解策略,這對于未來具有高動態(tài)特性的EONs而言,將無法全面感知愈發(fā)復雜多變的環(huán)境狀態(tài),從而極大影響到資源的使用效率和業(yè)務請求的完成效率。

近年來隨著人工智能技術的崛起,以數據和知識為驅動的計算智能、機器學習、深度學習、強化學習等一系列學習型算法迎來了發(fā)展高潮,并且已成功應用于光網絡領域中的多個方面,如流量預估、故障檢測、業(yè)務分類、調制格式識別、網絡運營與規(guī)劃等,相關綜述性總結可查閱文獻[84-85]。

然而迄今為止,有關學習型算法求解光網絡中動態(tài)資源分配問題的研究開展相對較少。經過分析,本文將其歸為兩類,一類稱為間接學習型,另一類稱為直接學習型。

(1) 間接學習型

所謂間接學習,即首先利用學習型算法充分挖掘光網絡中承載的歷史業(yè)務數據,進而對未來業(yè)務進行預測,并在此基礎上選取光路徑以及分配頻譜資源。例如,文獻[86]中引入了反向傳播神經網絡預測未來業(yè)務的到達時間和持續(xù)時間,提出了基于預測的最小綜合權重算法以及基于蜂群引導原則的混合蟻群算法;文獻[87]探索了深度學習算法在數據中心光網絡中的應用,設計了一種基于深度神經網絡的業(yè)務預測策略,并提出了基于深度學習的RSA資源分配算法。

(2) 直接學習型

所謂直接學習,即通過實時分析光網絡環(huán)境特性,采用學習型算法對網絡狀態(tài)開展在線學習,進而完成由動態(tài)業(yè)務輸入到分配資源輸出的直接映射,一種典型的學習框架如圖7所示。早在2008年,文獻[88]就將光突發(fā)交換網絡的路由與波長分配問題描述為強化學習領域中經典的多臂老虎機問題(multi-armed bandits problem, MABP),即考慮把路徑選擇與波長分配視為老虎機中對其支臂的選取決策,并通過設計一種改進的Q-learning算法進行求解,以最大程度地減小突發(fā)損失概率。隨著深度強化學習技術的火熱發(fā)展,到了2019年,文獻[89]采用了一種高效的異步學習框架——異步優(yōu)勢動作評價(asynchronous advantage actor-critic, A3C)算法來求解動態(tài)路由、調制與頻譜分配問題,其依據問題特性設計了狀態(tài)空間、動作空間、獎勵機制以及深度神經網絡模型,同時將資源預配置過程劃分成多個回合,并提出了一種基于滑動窗口的靈活訓練策略以減小累計獎勵的震蕩,從而提升算法運行的收斂性。

圖7 一種典型的直接學習型算法框架

以上即為近年來EONs中主要的RSA算法,具體總結如表1所示。

表1 路由與頻譜分配算法總結

4 結 論

本文首先從靜態(tài)和動態(tài)角度入手對EONs中RSA算法進行綜述,接著依據不同類型的優(yōu)化算法框架將其分別歸納為精確算法、智能優(yōu)化算法、啟發(fā)式算法以及學習型算法,同時通過分析每一類算法的求解特性與優(yōu)缺點,對其又做了進一步細致的分類與概括。

總的來講,隨著未來多樣化業(yè)務請求數量的急劇攀升,網絡環(huán)境必定會變得越發(fā)復雜,而作為下一代最具前景的光網絡,EONs展現出了較多優(yōu)勢,這些優(yōu)勢很大程度上則依賴于網絡資源的高效靈活分配。對此,本文將RSA算法的未來發(fā)展趨勢總結為以下幾點。

(1) 由靜態(tài)向動態(tài)轉變

隨著數據業(yè)務量的指數級增長,光網絡的承載壓力勢必會大大增加,此時考慮業(yè)務的動態(tài)時間屬性就顯得尤為重要,特別是針對大量突發(fā)性業(yè)務請求的產生與結束,這將直接導致資源配置難度的急劇攀升。為了更好適應未來發(fā)展,有關動態(tài)性RSA算法的研究還需深入開展下去,包括對不同類型動態(tài)問題結構(如多播、任播業(yè)務等)、算法解決思路(如資源預留、動態(tài)重構等)以及動態(tài)算法性能(如魯棒性、自適應性等)等的進一步探索。當然,靜態(tài)性方面的研究仍不可忽視,比如數學模型構建的合適與否體現的是對一個或一類問題本質特性的掌握程度,這有助于實現算法設計由靜態(tài)向動態(tài)的高效轉變。

(2) 由單目標向多目標轉變

在現實生活中,多目標優(yōu)化問題是普遍存在的,而且處于非常重要的地位。作為EONs中的一項關鍵技術,RSA算法在應用時也存在著多個目標,例如阻塞率最低、頻譜利用率最高、任務完成率最大、鏈路負載均衡等,這些目標之間還可能具有一定的沖突性,并且對于不同的用戶偏好與工程背景,優(yōu)化目標的側重程度也會有較大差異。同時,當前較為成熟的一些多目標優(yōu)化手段在求解帶有復雜約束的大規(guī)模問題時仍存在著計算復雜度高、優(yōu)化結果質量較差等弊端,而EONs在未來必然會愈發(fā)復雜化,面對的業(yè)務規(guī)模也會成倍數擴大。因此,研究高效的多目標RSA算法能夠更加深入了解問題內涵,理清不同目標間的相關性,從而為工程決策提供綜合性的優(yōu)化方案。

(3) 由基于策略規(guī)則向基于數據知識轉變

針對EONs中RSA問題的求解,現有研究大多是從策略角度入手,通過構造多種啟發(fā)式規(guī)則設計相應算法,尤其對于動態(tài)性問題更是如此。雖然這類方法應用廣泛且取得了不錯的效果,但為了更進一步提升算法優(yōu)化性能,獲得更快的資源配置速率,實現更高的動態(tài)響應能力,就要充分利用數據并通過學習從中獲取知識,例如使用可以感知復雜EONs狀態(tài)的深度神經網絡來學習RSA參數化策略,由此設計出高動態(tài)網絡資源的協(xié)同調度機理與方法。因此,嘗試引入深度學習、深度強化學習等新興人工智能技術框架來求解RSA問題,有助于生成基于任務需求數據與網絡行為知識的資源調度能力,以便支持高資源利用率網絡建設,完成網絡自配置與自優(yōu)化,從而為實現真正智能的光網絡提供理論與算法支撐,這將成為未來的主要研究趨勢。