趙中楠，王健，郭紅微

（1.哈爾濱理工大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院，黑龍江 哈爾濱 150080；2.哈爾濱工程大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院，黑龍江 哈爾濱 150001；3.黑龍江工程學(xué)院數(shù)學(xué)系，黑龍江 哈爾濱 150015）

1 引言

全光網(wǎng)絡(luò)具有全光域信息交換的特點(diǎn)[1]，摒棄了傳統(tǒng)光電轉(zhuǎn)換的模式，大大提高了數(shù)據(jù)的傳輸速度，有效地提升了信息交換的容量，正越來越受到業(yè)界的重視[2-3]，同時路由與波長分配（RWA,routing and wavelength assignment）作為其資源分配的重要方法一直都是研究的熱點(diǎn)，與此同時也提出了很多方法[4-5]來提高資源的分配效率。伴隨著軟件定義網(wǎng)絡(luò)（SDN,software defined network）的提出，業(yè)界很多傳統(tǒng)應(yīng)用都面臨著挑戰(zhàn)，如何能夠使傳統(tǒng)的方法在新框架下實(shí)現(xiàn)有效的應(yīng)用并與之融合也成了當(dāng)下需要分析的問題，因此本文從這個角度進(jìn)行了研究。

在光網(wǎng)中，信息是通過不同鏈路中不同波長信道進(jìn)行傳遞的，RWA 就是根據(jù)傳輸需求選擇合適鏈路并匹配相應(yīng)信道從而實(shí)現(xiàn)信息傳送的方法。其運(yùn)作方式主要分為2 種：靜態(tài)RWA 與動態(tài)RWA，其中，靜態(tài)方式相對穩(wěn)定，調(diào)度成功率高，但是難以適應(yīng)網(wǎng)絡(luò)復(fù)雜變化的需要且資源利用率低，分配方式不夠靈活；動態(tài)方式則通常以在線的方式運(yùn)行，能夠根據(jù)網(wǎng)絡(luò)的變化需要適時進(jìn)行調(diào)配。不同的運(yùn)作方式對系統(tǒng)的運(yùn)行效果產(chǎn)生不同的影響，因此一直是研究的重點(diǎn)，而動態(tài)方式是本文的研究對象。

鑒于此，本文提出了一種基于SDN 的多目標(biāo)自適應(yīng)路由與波長分配（SO-MO-RWA，SDN oriented multi-objective routing and wavelength assignment）方法。該方法考慮到全光網(wǎng)絡(luò)高速傳輸以及高效鏈路調(diào)度的需要將調(diào)度時間和鏈路質(zhì)量作為聯(lián)合調(diào)度目標(biāo)，構(gòu)建了0-1 整數(shù)規(guī)劃的RWA問題模型同時應(yīng)用二進(jìn)制混合拓?fù)淞Ｗ尤核惴▽栴}求解。整個方法采用基于SDN 的調(diào)度方式，能夠?qū)崟r獲取網(wǎng)絡(luò)資源狀態(tài)信息，并以按需方式實(shí)現(xiàn)網(wǎng)絡(luò)資源的動態(tài)分配。

2 相關(guān)工作

RWA 的研究內(nèi)容可以從以下幾個方面進(jìn)行分析。

首先，從不同研究角度設(shè)定不同的評價指標(biāo)，如資源分配比率、鏈路損傷感知、阻塞率等。Bonani等[6]在研究RWA 的固定路由、交替路由和自適應(yīng)路由方法基礎(chǔ)上，提出了最小跳固定交替算法以降低阻塞率。Tyagi 等[7]針對動態(tài)光網(wǎng)絡(luò)，采用改進(jìn)的水滴算法研究了 RWA 問題中的連接阻塞率最小化問題。Ebrahimzadeh 等[8]在建立線性物理層損傷模型的基礎(chǔ)上，對計算出的光路質(zhì)量進(jìn)行估計，提出了一種動態(tài)損傷感知的RWA 方案，該方法通過收集鏈路波長占用信息，采用自適應(yīng)路由技術(shù)建立適合的鏈路。Marsden 等[9]提出了一個包含四波混合誘導(dǎo)串?dāng)_的路由和波長分配的快速計算方法，以最小化建立動態(tài)光路的時間。Dizdarevic 等[10]在對物理層損傷的分類及RWA 相關(guān)算法綜合研究的基礎(chǔ)上，對PLI-RWA（physical layer impairment routing and wavelength assignment）算法性能指標(biāo)進(jìn)行了評價。Velasco 等[11]設(shè)計了一個概率模型來計算光網(wǎng)絡(luò)中每個鏈路中使用波長的數(shù)量，并在此基礎(chǔ)上提出了一種新型的損傷感知RWA 算法。上述各種方法能夠根據(jù)鏈路的狀態(tài)指標(biāo)進(jìn)行分析與設(shè)計，但是均以單指標(biāo)調(diào)度為主，未能考慮復(fù)雜調(diào)度條件下的調(diào)度需要。

其次，不同的調(diào)度方法會對系統(tǒng)的運(yùn)行效果產(chǎn)生影響。Bandyopadhyay 等[12]針對全光網(wǎng)絡(luò)設(shè)計了多種啟發(fā)式算法，在多項式時間內(nèi)有效地解決RWA問題的同時降低了網(wǎng)絡(luò)資源的能耗。Jaumard 等[13]針對RWA 中光路重新排列問題進(jìn)行了研究，采用E-optimal 方法評估它所需要的最小光路重排數(shù)量，以最大化服務(wù)等級。Tang 等[14]考慮到服務(wù)差異化需求和特點(diǎn)，提出了基于預(yù)測和分層圖模型的路由和波長分配算法，通過波長數(shù)預(yù)測機(jī)制結(jié)合分層圖模型綜合考慮實(shí)現(xiàn)路由和波長資源的分配。Ricciardi等[15]能夠在鏈路資源分配的過程中根據(jù)網(wǎng)絡(luò)負(fù)載輕重，通過負(fù)載平衡和能量感知之間的動態(tài)切換實(shí)現(xiàn)網(wǎng)絡(luò)資源的平衡利用。Pavarangkoon 等[16]提出了一種考慮全光載波復(fù)制的路由和波長分配方案，以最小化波長復(fù)用的多載波分布式網(wǎng)絡(luò)所需波長。Hsu 等[17]根據(jù)光網(wǎng)絡(luò)中的RWA 問題的NP（nondeterministic polynomial ）特性，提出了一種基于最大不相交路徑的算法實(shí)現(xiàn)路由與波長的分配方法。以上研究都根據(jù)所研究的問題場景進(jìn)行了算法設(shè)計，但是還缺乏在類似SDN 這種平臺結(jié)構(gòu)下的具體調(diào)度方法的設(shè)計與研究。

SDN 的提出為光網(wǎng)絡(luò)的發(fā)展提供了很好的契機(jī)，近些年很多學(xué)者在光網(wǎng)絡(luò)與SDN 融合方面也進(jìn)行了很多研究。Montero 等[18]針對傳統(tǒng)配置的低效性問題，采用測試信號機(jī)制和OpenFlow 協(xié)議，提出了一種基于SDN 的高效拓?fù)浒l(fā)現(xiàn)方法，允許TON（transparent optical network）自動學(xué)習(xí)光學(xué)設(shè)備之間的物理鄰接，提高數(shù)據(jù)傳輸?shù)男?。光網(wǎng)絡(luò)的發(fā)展伴隨著復(fù)雜性的提升，導(dǎo)致傳統(tǒng)的網(wǎng)絡(luò)控制和管理框架無法與之匹配，文獻(xiàn)[19-20]對SDN 光網(wǎng)絡(luò)中的各種管控機(jī)制及應(yīng)用等相關(guān)問題進(jìn)行了闡述。Yan 等[21]考慮到充分了解當(dāng)前網(wǎng)絡(luò)狀態(tài)對于在短時間內(nèi)更好地實(shí)現(xiàn)軟件定義的可調(diào)度性至關(guān)重要，設(shè)計了網(wǎng)絡(luò)監(jiān)控數(shù)據(jù)和網(wǎng)絡(luò)配置信息結(jié)合的集中式網(wǎng)絡(luò)數(shù)據(jù)庫，使網(wǎng)絡(luò)分析應(yīng)用能夠更好地支持動態(tài)可編程光網(wǎng)絡(luò)。Santos 等[22]提出了一種用于光網(wǎng)絡(luò)的聯(lián)合SDN 控制器體系結(jié)構(gòu)，將集群策略與豐富的層次路徑計算充分結(jié)合以提升路由性能。Chan 等[23]考慮到未來光網(wǎng)絡(luò)會以指數(shù)級的數(shù)據(jù)速率增長，采用認(rèn)知技術(shù)對SDN 的光層及控制器等各層進(jìn)行了分析與設(shè)計。文獻(xiàn)[24-25]提出了相應(yīng)的全光SDN 結(jié)構(gòu)的數(shù)據(jù)中心虛擬化架構(gòu)，能夠按需提供數(shù)據(jù)擴(kuò)展環(huán)境，實(shí)現(xiàn)動態(tài)分割網(wǎng)絡(luò)和計算資源，動態(tài)翻譯并提供虛擬數(shù)據(jù)中心到光層的請求，為用戶提供高帶寬低時延的連接服務(wù)。上述文獻(xiàn)從不同角度對SDN 與光網(wǎng)絡(luò)的技術(shù)融合與應(yīng)用進(jìn)行了研究，但是還缺乏如何在新型網(wǎng)絡(luò)架構(gòu)下進(jìn)行RWA 這類路徑資源分配的具體方案的研究。

3 基于SDN 的全光網(wǎng)絡(luò)框架描述

SDN 是由斯坦福大學(xué)提出的一種新型的網(wǎng)絡(luò)架構(gòu)，其核心思想在于改變了傳統(tǒng)將控制與調(diào)度集成的方式，將控制平面與數(shù)據(jù)平面功能解耦，通過網(wǎng)絡(luò)的可編程性與網(wǎng)絡(luò)功能虛擬化技術(shù)，實(shí)現(xiàn)了網(wǎng)絡(luò)資源的靈活調(diào)度，提升了系統(tǒng)整體的運(yùn)作效率。與此同時，隨著技術(shù)水平的不斷提高，全光網(wǎng)絡(luò)憑借其自身傳輸特性的優(yōu)勢，正成為全球互聯(lián)網(wǎng)主干網(wǎng)絡(luò)的重要信息傳輸載體，SDN 在光網(wǎng)絡(luò)上的部署也引起了業(yè)界和研究團(tuán)體的廣泛興趣[26-27]，同時國際互聯(lián)網(wǎng)工程任務(wù)組（IETF,The Internet Engineering Task Force）也對此進(jìn)行了相應(yīng)的結(jié)構(gòu)定義?；赟DN 的全光網(wǎng)絡(luò)結(jié)構(gòu)如圖1 所示。

圖1 基于SDN 的全光網(wǎng)絡(luò)結(jié)構(gòu)

基于SDN 的全光網(wǎng)絡(luò)結(jié)構(gòu)主要由應(yīng)用層、控制平面和數(shù)據(jù)平面3 層組成，最上層為應(yīng)用層，對應(yīng)各種不同應(yīng)用需求，例如光網(wǎng)互聯(lián)的數(shù)據(jù)中心服務(wù)[28]和云租戶應(yīng)用等。第二層是控制平面，其核心部件為控制器（controller），控制器通過北向接口與應(yīng)用層銜接，并提供不同的接口協(xié)議滿足與不同應(yīng)用的兼容性；通過南向接口與數(shù)據(jù)平面銜接，南向接口負(fù)責(zé)與基礎(chǔ)設(shè)施資源對接，能夠支持多供應(yīng)商和多協(xié)議場景，主要協(xié)議為OpenFlow，該協(xié)議采用字符流的形式，能夠包容不同網(wǎng)絡(luò)的傳輸格式，提供統(tǒng)一的數(shù)據(jù)傳輸接口。SDN 設(shè)計之初主要針對IP 網(wǎng)絡(luò)，并沒有考慮光網(wǎng)絡(luò)的信號傳輸特性，因此近些年相關(guān)研究也針對OpenFlow的結(jié)構(gòu)進(jìn)行了擴(kuò)展[29-30]，使之適應(yīng)于光網(wǎng)絡(luò)的傳輸方式?？刂破鞯闹饕δ苣K包括資源管理、拓?fù)涔芾怼⒄{(diào)度算法模塊、網(wǎng)絡(luò)服務(wù)抽象等。最底層為數(shù)據(jù)平面，主要由全光網(wǎng)絡(luò)基礎(chǔ)設(shè)施構(gòu)成，例如光交叉連接器（OXC,optical cross-connect）、可重構(gòu)光分插復(fù)用器（ROADM,reconfigurable optical add-drop multiplexer）、波長選擇開關(guān)（WSS,wavelength-selective switch）等，由于光網(wǎng)不斷地發(fā)展，在與SDN 融合的過程中很多新的設(shè)備也內(nèi)置了OpenFlow 協(xié)議[31]，實(shí)現(xiàn)與控制器的直接交互，但目前大多數(shù)的光網(wǎng)絡(luò)設(shè)備都無法支持直接與控制器交互，因此提出了OpenFlow 協(xié)議代理（OA,openflow agent）[32]，負(fù)責(zé)對控制器與光交換設(shè)備之間的信息轉(zhuǎn)發(fā)，實(shí)現(xiàn)SDN 結(jié)構(gòu)下的信號傳輸與全光域交換的無縫銜接。

傳統(tǒng)網(wǎng)絡(luò)中用戶以端到端方式獲取資源信息，所有傳輸過程中的資源分配由于調(diào)度結(jié)構(gòu)的限制，無法根據(jù)需要進(jìn)行實(shí)時調(diào)整。網(wǎng)絡(luò)功能虛擬化（NFV,network function virtualization）的提出實(shí)現(xiàn)了對網(wǎng)絡(luò)資源的抽象，通過軟件化方法對網(wǎng)絡(luò)功能加以實(shí)現(xiàn)，完成對資源服務(wù)功能的部署，不但可以優(yōu)化信息流的傳輸路徑、靈活配給信息傳輸流量，還可以縮短業(yè)務(wù)調(diào)度周期、提高資源的調(diào)度效率。隨著SDN 與NFV 的結(jié)合，全光網(wǎng)絡(luò)資源調(diào)度的靈活性得到了有效提升，可以實(shí)現(xiàn)資源的按需分配而不再局限于某個地域、設(shè)備或者某個供應(yīng)商。在這個背景下，IETF 給出了服務(wù)功能鏈（SFC,service function chaining）的概念[33]，服務(wù)功能鏈對應(yīng)著從端到端傳輸所需一系列資源的分配方式。在基于SDN 的全光網(wǎng)絡(luò)結(jié)構(gòu)下，該種方式能夠根據(jù)業(yè)務(wù)邏輯動態(tài)分配承載業(yè)務(wù)的功能節(jié)點(diǎn)，實(shí)現(xiàn)網(wǎng)絡(luò)功能服務(wù)及資源部署。運(yùn)行過程中，控制器的服務(wù)抽象模塊根據(jù)業(yè)務(wù)需求，將服務(wù)所需的若干資源進(jìn)行抽象，提供相應(yīng)服務(wù)功能實(shí)例。同時，調(diào)度算法根據(jù)資源管理模塊提供的網(wǎng)絡(luò)狀態(tài)信息進(jìn)行資源選擇，執(zhí)行服務(wù)功能的資源映射，以不同的粒度實(shí)現(xiàn)資源調(diào)度，適應(yīng)光網(wǎng)絡(luò)鏈路的資源選擇及光路構(gòu)建。服務(wù)功能鏈的資源分配方式對于全光網(wǎng)絡(luò)有著積極意義，解決了傳統(tǒng)調(diào)度低效、資源浪費(fèi)等問題，進(jìn)一步提高網(wǎng)絡(luò)資源重構(gòu)性，實(shí)現(xiàn)網(wǎng)絡(luò)的高效管理與資源的快速有效配給。

4 自適應(yīng)路由與波長分配模型

SDN 對資源虛擬化調(diào)度的過程中，鏈路及相應(yīng)波長等基礎(chǔ)設(shè)施資源承載了數(shù)據(jù)流量，因此在服務(wù)功能鏈資源部署過程中為了提供有效的傳輸服務(wù)，需要綜合考慮光通信的傳輸質(zhì)量和鏈路的調(diào)度效率等因素。

4.1 調(diào)度指標(biāo)設(shè)計

RWA 被認(rèn)為是全光網(wǎng)絡(luò)解決資源調(diào)配的有效手段，在RWA 的調(diào)度過程中，SDN 控制器通過感知網(wǎng)絡(luò)鏈路的物理損傷信息及資源分配狀況，根據(jù)RWA 既定的調(diào)度目標(biāo)對鏈路資源進(jìn)行調(diào)整?；谌饩W(wǎng)絡(luò)調(diào)度需求的特點(diǎn)，本文將調(diào)度時間和鏈路質(zhì)量作為調(diào)度目標(biāo)。其中，調(diào)度時間是指從接受請求、執(zhí)行路徑規(guī)劃到資源映射一系列過程所耗費(fèi)的時間。當(dāng)SDN 控制器接到業(yè)務(wù)請求時，按照服務(wù)功能鏈的資源分配方式，對請求資源的服務(wù)功能進(jìn)行抽象，創(chuàng)建一系列服務(wù)功能集合（SFS,service function set），每個服務(wù)功能集合中由多個服務(wù)實(shí)例（SFI,service function instance）構(gòu)成，可以由不同的服務(wù)供應(yīng)商提供，從而實(shí)現(xiàn)完整鏈路資源的構(gòu)建。因此可以得到m個服務(wù)功能集合SFS1，SFS2,…,SFSm，其中每個服務(wù)功能實(shí)例的請求時間服從泊松分布，所對應(yīng)的平均到達(dá)率為λ1,λ2,…,λn，根據(jù)網(wǎng)絡(luò)流量的特征，服務(wù)功能集合內(nèi)部的服務(wù)實(shí)例的調(diào)度時長服從重尾分布[34]。服務(wù)實(shí)例i(SFIi)的服務(wù)調(diào)度時間Ti為

其中，λi代表SFIi的請求到達(dá)率，分別代表調(diào)度時間的一階矩和二階矩，分別如式(2)和式(3)所示。

重尾分布的概率密度函數(shù)為

鏈路質(zhì)量是網(wǎng)絡(luò)傳輸?shù)闹匾笜?biāo)，在全光網(wǎng)絡(luò)的運(yùn)行過程中，因光學(xué)傳播特性等原因會使信號受到光損耗、串?dāng)_等影響，從而造成信號損傷。SDN控制器擁有全局網(wǎng)絡(luò)視圖，能夠?qū)崟r感知網(wǎng)絡(luò)拓?fù)錉顟B(tài)信息，并根據(jù)信息變化對光路的物理損傷進(jìn)行評估，判斷不同鏈路的服務(wù)狀況為鏈路分配提供依據(jù)。評估模型主要有光信噪比（OSNR,optical signal noise ratio）和Q因子2 種。實(shí)際應(yīng)用中，Q因子模型由于對不同測量環(huán)境的適應(yīng)性較好，應(yīng)用較廣泛。Q因子模型的計算會涉及不同的物理損傷的指標(biāo)，從而對線路進(jìn)行綜合評定，其中包括交叉相位調(diào)制（XPM,cross-phase modulation）、四波混頻效應(yīng)（FWM,four-wave mixing）、放大自發(fā)輻射（ASE,amplified spontaneous emission）等，因此SFIi的鏈路質(zhì)量計算如式(5)所示。

其中，σtotal表示交叉相位調(diào)制、四波混頻效應(yīng)及放大自發(fā)輻射的標(biāo)準(zhǔn)差，Ps表示對應(yīng)光路信道的功率峰值，σ0表示信號為0 時的強(qiáng)度標(biāo)準(zhǔn)差。

4.2 目標(biāo)函數(shù)定義

基于上述分析與定義，構(gòu)建基于SDN 的多目標(biāo)自適應(yīng)路由與波長分配模型。在不同服務(wù)供應(yīng)商基礎(chǔ)設(shè)施上，采用SDN 統(tǒng)一控制邏輯進(jìn)行調(diào)度，利用網(wǎng)絡(luò)可編程性特點(diǎn)執(zhí)行業(yè)務(wù)資源的虛擬化配置，從而實(shí)現(xiàn)RWA 的有效部署。在資源部署過程中，需要考慮以下幾點(diǎn)：1)服務(wù)功能序列的構(gòu)建；2)不同供應(yīng)商提供的服務(wù)基礎(chǔ)設(shè)施的選擇；3)根據(jù)調(diào)度目標(biāo)及約束選擇相匹配的光路。結(jié)合以上分析，本文將基于SDN 的全光網(wǎng)絡(luò)的資源分配問題構(gòu)建為一個0-1 整數(shù)規(guī)劃問題，其模型可以表示為M=（C,I,W），其中，C表示根據(jù)需要由網(wǎng)絡(luò)抽象所構(gòu)建的服務(wù)功能鏈，由服務(wù)功能集合組成；I表示服務(wù)集合內(nèi)部的鏈路資源實(shí)例；W表示鏈路資源內(nèi)部可用的波段集合。相應(yīng)目標(biāo)函數(shù)的定義為

其中，Qth和Bth分別表示Q因子閾值和帶寬容量閾值，k、j、i、m、nj和wi分別表示服務(wù)功能鏈中服務(wù)功能集合、鏈路資源實(shí)例、鏈路可用的波段集合所對應(yīng)的資源變量及相應(yīng)的資源數(shù)量。

該模型融合了鏈路質(zhì)量與調(diào)度時間2 個指標(biāo)，以實(shí)現(xiàn)資源快速有效的調(diào)度。相應(yīng)約束說明如下：1)Q因子閾值，所選擇的鏈路需要滿足指定閾值，以保證所選擇鏈路的信道質(zhì)量符合傳輸要求；2)帶寬容量閾值，根據(jù)業(yè)務(wù)需求提供有效帶寬，保證QoS 的傳輸要求；3)波長一致性，鏈路序列均采用統(tǒng)一波長；4)X取值為1 或0 代表相應(yīng)資源的選擇與否；5)保證光路資源的分配的唯一性；6)權(quán)值約束。

5 模型求解

由于RWA 屬于NP 完全問題，調(diào)度算法直接影響著 SO-MO-RWA 的性能，針對本文所提模型的特點(diǎn)，采用二進(jìn)制混合拓?fù)淞Ｗ尤簝?yōu)化（BHTPSO,binary hybrid topology particle swarm optimization）算法[35]對路徑規(guī)劃問題進(jìn)行求解。

5.1 算法描述

粒子群優(yōu)化（PSO,particle swarm optimization）算法由于具有較高的搜索效率，廣泛應(yīng)用在不同領(lǐng)域中同時也發(fā)展了多個版本，其中二進(jìn)制粒子群優(yōu)化（BPSO,binary particle swarm optimization）算法常用于解決整數(shù)規(guī)劃等離散空間問題的NP 優(yōu)化問題，BHTPSO 針對BPSO 易陷入局部最優(yōu)解，且收斂速度慢等不足進(jìn)行了優(yōu)化，有效地提升了性能，在避免局部最優(yōu)解的同時加速了收斂速度，進(jìn)一步提升了求解整數(shù)規(guī)劃問題的效率。

與BPSO 和PSO 一樣，BHTPSO 也是在混合拓?fù)淞Ｗ尤簝?yōu)化（HTPSO,hybrid topology particle swarm optimization）算法的基礎(chǔ)上離散化獲得的。在BHTPSO 中，向量(Xi,Vi,)分別代表粒子i的位置、速度和最優(yōu)位置，分別代表其鄰居粒子發(fā)現(xiàn)的最優(yōu)位置和整個群體所獲得的最優(yōu)位置。BHTPSO 采用局部拓?fù)浜腿滞負(fù)湎嘟Y(jié)合的方式進(jìn)行搜索，粒子i的下一個速度為

其中，慣性權(quán)重w(t)為

當(dāng)前粒子的下一位置可以根據(jù)群體最優(yōu)Pgbest獲得，如式(9)所示。

其中，加速因子c1、c2、c3由式(10)計算獲得。

為了提升對未知解的探索能力，算法在搜索初期擴(kuò)大搜索范圍，凸顯全局搜索的效果，隨著迭代次數(shù)的增加，減弱全局搜索強(qiáng)化局部搜索加速獲得最優(yōu)解。在此期間每個粒子的最優(yōu)解需要參考和Pgbest獲得。

在BHTPSO 算法的離散化過程中，通過式(11)計算粒子的速度。粒子的速度大小與位置變化有直接的關(guān)系，即0 代表粒子當(dāng)前位置不需要變化，1 則相反。

為了避免在多次迭代中出現(xiàn)停滯，且無法獲取最優(yōu)解的現(xiàn)象，可以將式(12)所示的E值添加給式(11)，以跳出本次迭代并繼續(xù)加速收斂。

由此每個粒子的下一位置如式(13)所示。

在對SO-MO-RWA 求解的過程中，每個粒子Xi代表一個鏈路候選解，目標(biāo)函數(shù)作為適應(yīng)度函數(shù)，計算步驟描述如下。

步驟1初始化粒子Xi、速度Vi、位置以及迭代次數(shù)等參數(shù)。

步驟2獲取，更新粒子速度。

步驟3通過速度、群最優(yōu)位置Pgbest等計算粒子的下一位置。

步驟4如果滿足條件，則結(jié)束運(yùn)行導(dǎo)出最優(yōu)解，否則更新、Pgbest，執(zhí)行步驟5。

步驟5更新參數(shù)w。

步驟6更新參數(shù)c1、c2、c3。

步驟7若最優(yōu)位置在多次迭代中沒有發(fā)生變化，添加E值跳出局部搜索，執(zhí)行步驟2。

5.2 算法參數(shù)優(yōu)化

參數(shù)優(yōu)化需要粒子群算法針對具體的問題選擇適合的參數(shù)以提升模型的計算效率。

1)慣性權(quán)重

針對慣性權(quán)重的取值范圍，本文分別選擇[0.3,0.6]、[0.7,0.9]和[1.0,1.2]這3 個區(qū)間進(jìn)行了實(shí)驗(yàn)，如圖2 所示。不同區(qū)間數(shù)值的測試結(jié)果顯示在不斷迭代過程中各自呈現(xiàn)出不同的變化幅度，其中參數(shù)取值在[0.3,0.6]時系統(tǒng)的運(yùn)行效果最優(yōu)。

2)加速因子

本文算法中加速因子有c1、c2和c3這3 個。根據(jù)經(jīng)驗(yàn)，粒子群算法c1和c2的取值在接近或者相等時系統(tǒng)運(yùn)行效果較好，因此分3 種情況對其進(jìn)行參數(shù)設(shè)定，其中2 種選擇將三者設(shè)置相等數(shù)值，分別為1.5 和2.5，另一種將c1、c2等值而c3差異化取值。如圖3 所示，測試結(jié)果顯示當(dāng)c3差異化取值時，系統(tǒng)的運(yùn)行效果要優(yōu)于三者取值相同的情況。

圖2 慣性權(quán)重參數(shù)測試

圖3 加速因子參數(shù)測試

3)粒子數(shù)

為了測試不同數(shù)量的粒子對系統(tǒng)的影響，本文呈梯度地選擇了30、50、70、100 這4 種粒子數(shù)。加速因子、慣性權(quán)重等參數(shù)設(shè)置在不同粒子數(shù)量場景中均保持一致，如圖4 所示。實(shí)驗(yàn)結(jié)果顯示，當(dāng)粒子數(shù)N=100 時，系統(tǒng)運(yùn)行效果最好，也就是說在粒子數(shù)量較多的情況下，更能夠提高算法的運(yùn)行效率。

圖4 粒子數(shù)參數(shù)測試

4)最大粒子更新速度

最大粒子更新速度測試中，均勻地選取了3、6、9 這3 個數(shù)值，如圖5 所示。當(dāng)v=6 時，測試結(jié)果要好于其他2 種情況，說明更新速度要保持在一個相對適中的值為佳。

圖5 最大粒子更新速度參數(shù)測試

BHTPSO 算法相比于BPSO 算法進(jìn)一步提升了獲取全局最優(yōu)解的性能。在解決整數(shù)規(guī)劃問題時，BHTPSO 算法能夠根據(jù)相應(yīng)的搜索策略和規(guī)則在解空間尋找最優(yōu)可行解，相比傳統(tǒng)方法面對解空間過大、復(fù)雜度升高從而難于計算的情況，BHTPSO算法能夠較好地適應(yīng)解空間的變化從而獲得更好的近似最優(yōu)解。與此同時，為了有效評估該算法計算結(jié)果的精確度，本文選擇與隱枚舉法進(jìn)行比較。隱枚舉法作為分支定界法的一個分類，主要用于計算0-1 整數(shù)規(guī)劃問題，該方法通常能夠獲得問題最優(yōu)解?；诒疚乃x模型以及參數(shù)的設(shè)定，隱枚舉法計算結(jié)果為40.78，為了保證BHTPSO 算法計算結(jié)果的有效性，采用區(qū)間估計的方法對其數(shù)值有效范圍進(jìn)行了統(tǒng)計分析，置信水平設(shè)置為0.95。由運(yùn)行結(jié)果統(tǒng)計可得，BHTPSO 算法獲得的最優(yōu)解符合參數(shù)為μ=41.17、σ=0.42 的正態(tài)分布N(μ,σ2)，置信區(qū)間為[41.02,41.31]，即BHTPSO 算法所求解與最優(yōu)解之間的差值精度在0.6%～1.3%范圍內(nèi)，非常接近最優(yōu)解，這說明該算法能夠有效解決0-1 整數(shù)規(guī)劃問題。

BHTPSO 算法的復(fù)雜度主要由兩部分構(gòu)成，一部分在于問題本身的規(guī)模，包括解的維度D、迭代的次數(shù)I、粒子數(shù)N等，此外還包括求解過程中粒子各種參數(shù)的運(yùn)算步驟，從模型關(guān)系可知，算法的復(fù)雜度可以表示為問題規(guī)模的函數(shù)，所以復(fù)雜度可以表示為O(DIN)。

5.3 模型流程說明

本文整個模型的功能實(shí)現(xiàn)需要多個模塊的調(diào)度協(xié)作，調(diào)度流程如圖6 所示。首先系統(tǒng)能夠?qū)崟r感知底層的各種鏈路損傷及鏈路調(diào)度的狀態(tài)信息，將信息匯聚到資源管理模塊并將多調(diào)度指標(biāo)信息提供給BHTPSO 算法進(jìn)行計算，同時將感知到的資源動態(tài)請求通過網(wǎng)絡(luò)抽象轉(zhuǎn)化成服務(wù)功能鏈的不同功能組件集合，經(jīng)過調(diào)度算法的優(yōu)化獲得合理的資源調(diào)度方案，最后通過拓?fù)涔芾磉M(jìn)行資源映射實(shí)現(xiàn)網(wǎng)絡(luò)的資源重構(gòu)。

圖6 SO-MO-RWA 的結(jié)構(gòu)流程

6 仿真實(shí)驗(yàn)與結(jié)果分析

本文開發(fā)了相應(yīng)的測試平臺對所提出的方法進(jìn)行仿真實(shí)驗(yàn)。測試平臺采用離散事件仿真器OMNeT++對網(wǎng)絡(luò)的部件及功能進(jìn)行了設(shè)計，測試平臺配置為Intel i7，8 GB DDR4 內(nèi)存，Windows 7 64 bit。網(wǎng)絡(luò)拓?fù)溥x擇了歐洲全光網(wǎng)絡(luò)標(biāo)準(zhǔn)測試拓?fù)銹an-European[36]，如圖7 所示，其中包含40 個波段、33 條鏈路及17 個節(jié)點(diǎn)，同時采用擴(kuò)展OpenFlow協(xié)議實(shí)現(xiàn)組件間通信。相關(guān)參數(shù)如表1 所示。

圖7 Pan-European 拓?fù)?/p>

基于損傷感知的路由與波長分配（IA-RWA，impairment-aware based routing and wavelength assignment），一直被認(rèn)為是光網(wǎng)絡(luò)主要的資源分配方法。本文采用其中較為典型的2 種方法，波長隨機(jī)分配（IA-RWA-RF,impairment-aware based routing and wavelength assignment by random-fit）和波長首次適應(yīng)（IA-RWA-FF,impairment-aware based routing and wavelength assignment by first-fit）與本文所提方法進(jìn)行比較。2 種方法采用的主要路由算法為短路徑優(yōu)先，同時結(jié)合各自波長分配形式實(shí)現(xiàn)資源分配。

表1 實(shí)驗(yàn)參數(shù)

1)恢復(fù)時間

恢復(fù)時間指的是從感知損傷異常到系統(tǒng)調(diào)度完成實(shí)現(xiàn)資源重建所用的時間。對于全光網(wǎng)絡(luò)這種大容量高速率傳輸?shù)木W(wǎng)絡(luò)來說，更短的恢復(fù)時間能夠進(jìn)一步減少對系統(tǒng)的影響保證服務(wù)質(zhì)量。該指標(biāo)主要是評價系統(tǒng)是否具有高效靈活的配置資源的調(diào)度能力，為此在不同負(fù)載情況下分別設(shè)置了不同數(shù)量的失效鏈路，以測試在不同負(fù)載及失效鏈路情況下系統(tǒng)的調(diào)度效果。同時對每種情況進(jìn)行了30次測試，取均值作為有效測試結(jié)果，實(shí)驗(yàn)結(jié)果分別如圖8 和圖9 所示。

圖8 100 Erlang 條件下的恢復(fù)時間

首先，在低負(fù)載情況下，如圖8 所示，當(dāng)失效鏈路數(shù)在[1,4]范圍內(nèi)，由于可用資源較多，IA-RWA-RF 調(diào)度所用時間要略少于IA-RWA-FF，隨著失效鏈路數(shù)量增多，IA-RWA-RF 所用時間呈現(xiàn)持續(xù)增長的態(tài)勢，在[5,10]的失效鏈路范圍內(nèi)，其恢復(fù)時間從4.45 ms提升為6.91 ms，增長幅度達(dá)到55%。相比于IA-RWA-RF 和IA-RWA-FF，SO-MO-RWA所用時間的變化幅度要小，呈現(xiàn)的曲線態(tài)勢也較平緩。同樣在[5,10]范圍內(nèi)，其恢復(fù)時間從2.92 ms 到3.65 ms，增長幅度為25%。其次，在負(fù)載較高的情況下，如圖9 所示，IA-RWA-RF 所用時間要多于IA-RWA-FF，同時兩者均高于SO-MO-RWA，實(shí)驗(yàn)結(jié)果顯示，在失效鏈路為[6,10]范圍內(nèi)，3 種方法呈現(xiàn)了一定的差異，IA-RWA-RF 從5.13 ms 變化到7.91 ms，變化幅度為54%，IA-RWA-FF 從4.64 ms變化到6.25 ms，變化幅度為35%，SO-MO-RWA 的3.71 ms 變?yōu)?.09 ms，幅度為10%。

圖9 300 Erlang 條件下的恢復(fù)時間

從測試結(jié)果可以看出，在不同負(fù)載情況下，SO-MO-RWA 所用時間都要低于IA-RWA-RF 和IA-RWA-FF，其原因主要有以下幾點(diǎn)：首先，在調(diào)度結(jié)構(gòu)方面，SO-MO-RWA 采用SDN 控制器通過統(tǒng)一的控制接口，實(shí)時獲取鏈路的運(yùn)行狀態(tài)信息，對鏈路資源進(jìn)行自適應(yīng)調(diào)整，保證服務(wù)的持續(xù)有效；其次，在調(diào)度方式上，虛擬化的資源調(diào)度方式能夠進(jìn)行快速靈活的資源部署，面向業(yè)務(wù)需求優(yōu)化網(wǎng)絡(luò)資源配置；最后，SO-MO-RWA 以調(diào)度時間為目標(biāo)，同時選擇高效的全局優(yōu)化算法對調(diào)度目標(biāo)進(jìn)行資源匹配，進(jìn)一步提高了映射資源的執(zhí)行效率，縮短了調(diào)度時間。相比而言，其他2 種方法采用短路徑優(yōu)先，簡單但具有局部性特點(diǎn)，需要在路由基礎(chǔ)上進(jìn)一步對光路進(jìn)行分配實(shí)現(xiàn)完整的資源調(diào)度，資源分配效率相對要低，無法保證在發(fā)生多條鏈路失效情況下的系統(tǒng)調(diào)度性能。

2)阻塞率

光網(wǎng)絡(luò)的帶寬資源是由不同的波長信道構(gòu)成的，不同傳輸需求會分配不同的帶寬。為了滿足波長一致性的要求，不同鏈路要選擇相同波長信道傳輸信號，當(dāng)部分鏈路無法分配有效資源時，調(diào)度就會受到阻塞，阻塞率反映了有效鏈路資源的分配情況。由于不同算法資源調(diào)度方式直接決定著信道的分配方式，因此該指標(biāo)也作為評估調(diào)度算法資源分配性能的重要指標(biāo)。如圖10 所示，隨著網(wǎng)絡(luò)負(fù)載不斷升高，3 種方法均有不同幅度的上升，其中，由于信道分配具有較大的隨機(jī)性，因此IA-RWA-RF 在[40,200]的負(fù)載區(qū)間內(nèi)阻塞率增長較為明顯，要高于IA-RWA-FF。相比這2 種算法，SO-MO-RWA 的指標(biāo)變化幅度相對平緩，在[90,160]的負(fù)載區(qū)間內(nèi)，其阻塞率從 2.19%變?yōu)?.47%，增長幅度為 12.8%。IA-RWA-RF 和IA-RWA-FF 的阻塞率分別從2.52%提升到4.24%和4.03%提升到6.67%，增長幅度分別為68%和65%；與此同時，在[170,200]的負(fù)載區(qū)間內(nèi)，SO-MO-RWA 隨著負(fù)載的增加，指標(biāo)并未呈現(xiàn)明顯的增幅，而其他2 種算法的上升幅度變化較為明顯。由此，測試結(jié)果顯示，整個測試區(qū)間內(nèi)，SO-MO-RWA 相較于其他2 種算法具有更低的阻塞率。

圖10 阻塞率測試結(jié)果

分析原因主要有以下幾方面：首先，SDN 控制器能夠統(tǒng)一管理網(wǎng)絡(luò)拓?fù)湫畔?，從全局角度匯聚底層的鏈路損傷信息，以及鏈路切換所需要的狀態(tài)信息，進(jìn)而對服務(wù)資源序列進(jìn)行鏈路選擇與流量規(guī)劃，匹配有效資源避免阻塞的發(fā)生；其次，通過服務(wù)功能鏈方式實(shí)現(xiàn)對資源序列的優(yōu)化部署，引導(dǎo)鏈路資源合理配給，提高資源的分配效率；最后，本文將鏈路資源的分配問題構(gòu)建為0-1 整數(shù)規(guī)劃問題，將鏈路傳輸需求等作為約束，并采用改進(jìn)的二進(jìn)制粒子群算法進(jìn)行了全局優(yōu)化，進(jìn)一步提高了對有效資源的分配效率及鏈路建立的成功率。IA-RWA 采用馬爾可夫鏈對路徑資源進(jìn)行構(gòu)建，相比于基于SDN 的全局資源調(diào)配的方式，這種概率模型存在一定的不確定性，且隨著系統(tǒng)復(fù)雜度越來越高，這種不確定性更加明顯，因此在實(shí)驗(yàn)中隨著負(fù)載增加，其阻塞率也會明顯增加。

3)資源利用率

資源利用率是評價參與信息傳輸組件使用效率的指標(biāo)，資源利用率與網(wǎng)絡(luò)的運(yùn)作方式有著緊密的關(guān)系。在以IA-RWA-RF 和IA-RWA-FF 為代表的IA-RWA 調(diào)度方式中，網(wǎng)絡(luò)調(diào)度與物理拓?fù)涫蔷o耦合的，資源調(diào)度缺乏靈活性，導(dǎo)致資源配置融入更多冗余資源進(jìn)而降低網(wǎng)絡(luò)資源利用率。圖11 測試了3 種算法的資源利用率。在不同的負(fù)載情況下，IA-RWA-RF 和IA-RWA-FF 算法所對應(yīng)的資源利用率在19%～41%范圍內(nèi)，而SO-MO-RWA 對資源的利用率則要高出很多，范圍為40%～64%。結(jié)果顯示，在相同負(fù)載情況下SO-MO-RWA 均高于其他兩者。雖然隨著負(fù)載的增加，需要更多的資源參與調(diào)度，資源利用率均有所下降，但是相對趨勢并沒有變化。

圖11 資源利用率測試結(jié)果

這是由于在SDN 架構(gòu)下控制與數(shù)據(jù)轉(zhuǎn)發(fā)之間關(guān)系的解耦，以及服務(wù)功能虛擬化的應(yīng)用極大地提高了網(wǎng)絡(luò)資源配給的靈活性，能夠有針對性地進(jìn)行資源配給，從而有效提升資源的使用效率。同時，SDN 統(tǒng)一控制邏輯能夠根據(jù)全局信息進(jìn)行策略規(guī)劃，制定相應(yīng)的資源需求方案，從而提高資源的分配利用率。SO-MO-RWA 對資源的優(yōu)化，提高了資源及路徑的有效性，相比其他2 種方法的局部優(yōu)化調(diào)度策略而言，在資源利用上更具有優(yōu)勢。此外，SDN 能夠支持不同粒度的調(diào)度，對不同資源調(diào)度需求具有更好的適應(yīng)性，根據(jù)調(diào)度要求進(jìn)行資源按需匹配，有效提高資源利用率。

7 結(jié)束語

本文基于SDN 面向全光網(wǎng)絡(luò)提出了一種自適應(yīng)多目標(biāo)路由與波長分配方法。該方法考慮了調(diào)度時間及鏈路質(zhì)量多個調(diào)度目標(biāo)，根據(jù)服務(wù)功能鏈的資源分配結(jié)構(gòu)將RWA 問題定義為0-1 整數(shù)規(guī)劃模型，同時采用優(yōu)化的二進(jìn)制粒子群算法BHTPSO 對構(gòu)建的模型求解，實(shí)現(xiàn)了SDN 下的路由與波長的分配。實(shí)驗(yàn)結(jié)果表明，本文提出的SO-MO-RWA 方法在恢復(fù)時間、阻塞率及資源利用率等性能指標(biāo)上均優(yōu)于IA-RWA-RF 和IA-RWA-FF 方法。這表明基于SDN 的路由與波長分配相比于傳統(tǒng)方法具有更好的性能，同時也為光網(wǎng)絡(luò)進(jìn)一步開展相關(guān)研究提供了嶄新思路。下一步研究工作中，將考慮設(shè)計全光網(wǎng)絡(luò)故障條件下，面向不同需求的自主調(diào)度方案。