劉煥淋李瑞艷孔德謙陳勇

?

基于多目標遺傳算法優(yōu)化彈性光網絡的多路徑保護機制

劉煥淋*①李瑞艷①孔德謙①陳 勇②

①(重慶郵電大學光纖通信技術與網絡重點實驗室 重慶 400065)②(重慶郵電大學自動化學院 重慶 400065)

彈性光網絡中多路徑的保護方案相比單路徑有效地降低網絡帶寬阻塞率，但會導致接收端多徑時延差的問題，且業(yè)務的多路徑分割傳輸策略使用了光網絡較多的頻譜資源。該文基于多目標遺傳算法提出了遺傳多路徑保護算法(Genetic Multipath Protection Algorithm, GMPA)，解決多路徑時延差和節(jié)約頻譜資源問題。在GMPA算法中，根據業(yè)務請求在光網絡中建立條邊分離最短路徑和帶寬分配方案作為GMPA算法的初始種群，設計了一種聯(lián)合考慮傳輸時延差和帶寬資源分配的向量函數優(yōu)化種群分類和擁擠距離排序。為提高算法的搜索能力和收斂速度，算法在交叉操作中設計個體自交叉方式，在變異過程中設置了帶寬基因位變異范圍及約束條件。仿真結果表明，相比多路徑保護(Multiple Path Protection, MPP)算法和工作路徑首次分配保護路徑最后分配(Primary First-fit Modified Backup Last-fit, PF-MBL) 算法，GMPA算法獲得最低的帶寬阻塞率，其頻譜資源利用率接近最優(yōu)的MPP算法，路徑間距離差異性能優(yōu)于MPP算法。

彈性光網絡；遺傳多路徑保護算法；路徑間距離差異

1 引言

傳統(tǒng)的波分復用網絡(Wavelength Division Multiplexing, WDM)采用固定波長帶寬的分配方式。當業(yè)務需求小于一個波長容量時，將導致資源浪費[1,2]。因此，頻譜效率更高、更靈活的彈性光網絡(Elastic Optical Networks, EONs)應運而生。EONs能根據業(yè)務的帶寬需求靈活配置頻譜資源，實現Gbit/s級至Tbit/s級間的帶寬靈活配置。EONs被廣泛地認為是下一代光網絡發(fā)展的主要方向之一[3]。

影響EONs性能的一個重要因素是路由和頻譜分配問題(Routing and Spectrum Assignment, RSA)。文獻[4]設計了一個以最小化網絡頻譜資源為目標，頻譜連續(xù)性和一致性為約束的靜態(tài)RSA整數線性規(guī)劃模型。文獻[5]設計了動態(tài)RSA算法，實現了網絡中動態(tài)業(yè)務的靈活配置。在對動態(tài)業(yè)務進行頻譜分配過程中，頻譜資源的動態(tài)分配和釋放會引發(fā)頻譜碎片問題。文獻[6]提出了工作路徑首次分配、保護路徑最后分配(Primary First-fit Modified Backup Last-fit, PF-MBL)算法解決頻譜分配過程中的碎片問題及處理方法。然而，由于在頻譜分配時頻譜連續(xù)性和一致性的約束，單路徑路由和頻譜分配難以傳輸大帶寬的業(yè)務，導致較高的業(yè)務阻塞率[7]。文獻[8]表明對業(yè)務采用多路徑傳輸相比單路徑傳輸有效地降低網絡的阻塞率。

隨著單光纖提供的帶寬達到400 Gb/s甚至1 Tb/s以上，大容量光纖線路故障將導致大量的數據業(yè)務丟失，對網絡性能影響將是災難性的，因此，光網絡的生存性路徑問題變得至關重要。文獻[9]研究了彈性光網絡中靜態(tài)多路徑保護問題，為最小最大化網絡消耗的頻譜索引值提出多路徑保護啟發(fā)式算法，相比于傳統(tǒng)的單路徑保護算法，多路徑保護算法具有較高的頻譜利用率。文獻[10]針對彈性光網絡中動態(tài)多路徑保護問題，提出了動態(tài)多路徑保護(Multiple Path Protection, MPP)算法，MPP算法通過優(yōu)化多條路徑上頻譜資源的分配傳輸業(yè)務，降低了網絡帶寬阻塞率，但MPP算法忽略了多路徑傳輸對接收端產生的時延差問題。由于多路徑路由產生的時延差將導致目的節(jié)點需要配置額外的緩沖區(qū)對業(yè)務進行緩存排序接收[11]。隨著互聯(lián)網應用發(fā)展，涌現了大量的視頻類數據應用，這些新的數據應用需要較多傳輸帶寬資源保證且對時延也更加敏感。因此，彈性光網絡多路徑保護的路徑間時延差問題急需解決。文獻[12]研究了同步光纖網(Synchronous Optical NETwork, SONET)時延約束下多路徑保護問題，當業(yè)務到達網絡時，把業(yè)務分成份小粒度的業(yè)務在條邊分離的路徑上進行傳輸，1條路徑滿足業(yè)務帶寬的需求，其中剩余一條路徑上分配的帶寬滿足1條路徑上分配帶寬的最大值，并指出此問題是一個NP難解問題。同時在多路徑傳輸的業(yè)務帶寬分配中，業(yè)務帶寬的多徑分割策略也是一個重要的研究問題，不同的帶寬分割策略會影響光網絡資源的帶寬使用情況。而且，在彈性光網絡的路由和頻譜分配時需要考慮到頻譜連續(xù)性和一致性約束，增加了多徑傳輸路由和頻譜分配的難度。因此，研究彈性光網絡中動態(tài)多路徑保護配置的時延問題，相比于SONET網絡將更加復雜。很多研究證明，智能優(yōu)化算法是解決此類NP難解問題的一種有效方法。

本文采用多目標遺傳算法解決考慮時延差的多路徑保護路由和頻譜分配問題。根據業(yè)務請求，選擇條最短邊分離路徑和業(yè)務帶寬設計種群初始化方案，依據路徑時延差和網絡資源設計優(yōu)化向量函數，通過個體的優(yōu)化向量函數值對業(yè)務進行等級分類和擁擠距離排序，最終得到多條傳輸路徑間時延差較小并且網絡資源較少的多路徑保護的路由和頻譜分配方案。

2 多路徑保護配置的模型

設彈性光網絡的網絡拓撲用有向無環(huán)圖(,,)表示，其中表示節(jié)點集合，表示鏈路集合，表示每條鏈路上的頻隙集合。網絡中的業(yè)務請求=(,),為源節(jié)點，為目的節(jié)點。B表示業(yè)務的請求帶寬。B表示業(yè)務的第條路徑中需要的帶寬。表示業(yè)務所需要的條邊分離路徑。l表示業(yè)務第條路徑經過的鏈路數目。本文把業(yè)務所需要的頻譜資源最小和業(yè)務最長路徑和最短路徑的差值最小化設置為生存性多路徑配置的優(yōu)化目標，建立了如式(1)所示的優(yōu)化模型：

約束條件為

(2)

(4)

(5)

,q分別為業(yè)務之間保護帶寬的需求和業(yè)務所有傳輸路徑中最大的帶寬需求；L表示業(yè)務第條路徑的物理距離；為二進制變量，業(yè)務第條路徑占用鏈路上的頻隙時取值為1，否則為0;為應用最短路徑算法為業(yè)務找到條最短邊分離路徑。式(2)約束了在單鏈路故障下，為保證業(yè)務傳輸，業(yè)務的路徑帶寬需求。式(3)表明業(yè)務的條路徑為鏈路不相交的路徑。式(4)約束業(yè)務在頻譜分配時要滿足頻譜一致性約束。式(5)約束業(yè)務在頻譜分配時要滿足頻譜連續(xù)性約束。

則多路徑保護的配置優(yōu)化問題的優(yōu)化向量函數為

3 基于多目標遺傳算法的多路徑保護機制

彈性光網絡中多路徑保護的路由和頻譜分配問題是一個NP難問題[9]。為解決此問題，本文基于多目標非支配排序的遺傳算法(Non-dominated Sorting Genetic Algorithm, NSGA-II)設計了一種遺傳多路徑保護算法(Genetic Multipath Protection Algorithm, GMPA)。GMPA 算法首先，設計了初始化種群方案產生初始種群，非支配排序后通過選擇策略、個體自交叉和帶寬基因位的變異操作得到第1代子種群；其次，從第2代開始，合并父代種群和子代種群并進行非支配排序。同時，計算每個非支配等級中個體的擁擠距離，根據非支配關系與個體的擁擠距離進行個體選擇，作為新的父代種群；最后，通過個體自交叉和帶寬基因位的變異產生新的子代種群；依次類推，最終產生一組Pareto最優(yōu)解。從而得到彈性光網絡多路徑保護的路由和頻譜分配的解決方案。

3.1初始化種群設計

在種群初始化方案中，種群規(guī)模的大小和密切相關。文獻[7]指出：為了減少網絡頻譜資源的使用，的取值至少為3，當條路徑可以滿足業(yè)務傳輸需求時，隨著值的增大，雖然業(yè)務所需的頻譜資源不變，但是，路徑增加導致保護頻譜資源的需求增多。因此，分配的頻譜資源可以滿足業(yè)務傳輸需求時，就不再增加值。

在GMPA算法中，采用基于不定長十進制的編碼方式構造初始個體。根據光網絡拓撲為每個業(yè)務請求的源節(jié)點到目的節(jié)點計算條邊分離路徑，并把可以產生潛在可行解的條邊分離路徑組合形成為一個個體。文獻[13]表明在不考慮每條路徑的光路長度時，每條路徑分配的帶寬為B/；若考慮路徑的光路長度，這種分配方案不能最小化網絡資源使用情況，每條路徑分配的帶寬可在B/左右尋找到最優(yōu)解。為此本文在種群初始化方案中為每個個體，即條邊分離路徑中的最后一位設計了一個帶寬基因位。則種群初始化方案即從條邊分離最短路徑中選取組邊分離的路徑組合和設計的帶寬基因位構造種群。為了更清楚理解GMPA算法種群的初始化方案，采用圖1的網絡拓撲進行舉例說明。

圖1 USNET網絡拓撲(km)

假設請求傳輸的業(yè)務(6, 15)需要從節(jié)點6到目的節(jié)點15，首先采用最短路徑算法為該業(yè)務計算條邊分離最短路徑，分別為6-8-11-15, 6-5-10-14-15, 6-7-9-12-16-15, 6-2-1-5-8-9-13-17-16-21-15，這里=4。若取值為3，利用條邊分離最短路徑構造GMPA算法的一種初始化種群如圖2所示。

圖2 種群初始化方案(K=4，N=3)

3.2 精英策略的選擇機制

精英策略的選擇機制即從父代中選取優(yōu)良個體進入子代，它是遺傳算法以概率1收斂的必要條件。在GMPA算法的選擇過程中，精英策略的選擇機制主要由下面的步驟組成：

步驟1 將父代個體和子代個體合并成一個種群，并依據優(yōu)化向量函數式(6)計算種群中每個個體的優(yōu)化向量函數值。

步驟2 依據優(yōu)化向量函數值對種群中的個體進行等級分類和擁擠距離排序。

步驟3 從種群中隨機選擇兩個個體。判斷兩個個體是否屬于同一等級。若是，則選擇出等級最低的個體；否則，選出擁擠距離最大的個體。

3.3個體自交叉和帶寬基因位的變異

為改進種群多樣性，在GMPA算法的交叉操作中設計了一種個體自交叉方式以便產生新的可行個體，即對個體中表示路徑的基因位對應相同網絡節(jié)點處進行交叉操作。如圖2，個體2的第2條路徑和第3條路徑有相同節(jié)點5，則在此基因位進行交叉產生一個新的個體，具體操作如圖3所示。

圖3 個體2的自交叉操作產生新個體示意圖

GMPA算法中，對個體中表示帶寬的基因位進行變異操作可以產生新的可行解。為產生較優(yōu)的帶寬分配方案，對個體中表示帶寬的基因位以固定概率進行變異。同時，為提高收斂速度和考慮彈性光網絡頻譜分配情況，GMPA算法的變異帶寬至少是一個頻隙帶寬，則變異空間為)。為滿足業(yè)務的傳輸保護頻帶需求，在條路徑中隨機選取兩條路徑,不進行變異，對剩余-2條路徑{1,2,,k–2}進行變異。在考慮式(2)帶寬約束的條件下，隨機選取路徑為保護路徑，則,兩條路徑的帶寬分配需求要滿足式(7)，式(8)條件：

(8)

以個體2為例說明GMPA算法的變異操作，假設對個體2的第1條路徑的帶寬基因位進行變異，則變異后的結果如圖4所示。

圖4 個體2的帶寬基因位變異過程

3.4 GMPA算法具體流程

輸入：彈性光網絡的網絡拓撲(,,)、交叉概率p、變異概率p、最大迭代次數nsize。

輸出：彈性光網絡多路徑保護的路由和頻譜分配方案。

步驟1 等待網絡中業(yè)務請求到達。如果有業(yè)務請求到達，轉至步驟2；否則，更新網絡狀態(tài)。

步驟2 使用最短路徑算法為業(yè)務計算工作路徑。并采用首次命中算法為工作路徑分配頻譜資源。若上述操作成功執(zhí)行，轉至步驟3；否則，轉至步驟4。

步驟3 使用最短路徑算法為業(yè)務計算一條保護路徑。并采用首次命中算法為保護路徑分配頻譜資源。若上述操作成功執(zhí)行，轉至步驟1；否則，轉至步驟4。

步驟4 為業(yè)務計算前條最短邊分離路徑，且初始化=3。

步驟5 判斷是否小于等于。若是，根據此條邊分離的最短路徑構造一個規(guī)模為的第代的父代種群P,=0，并初始化第代的子代種群；否則，阻塞此業(yè)務，轉至步驟1。

步驟6 將P和Q的個體合并放入U中，并根據優(yōu)化向量函數式(6)，計算U中個體的優(yōu)化向量函數值。

步驟7 根據非支配集排序方法對U中的個體進行等級分類，并對同一等級中的個體進行擁擠距離排序。

步驟9 依據個體自交叉和帶寬基因位的變異策略對P1中的個體進行交叉和變異操作，產生子代種群Q+1，=+1。

步驟10 判斷是否小于迭代次數，若是則轉至步驟11；否則，轉至步驟6。

步驟11 輸出P和Q非支配解的一個個體，依據個體帶寬基因位的帶寬對個體中的路徑用首次命中算法進行頻譜分配。若個體中的條路徑頻譜分配都成功，則轉至步驟1；否則，=+1，并轉至步驟5。

對于GMPA算法，主要由3個步驟組成，條邊分離路徑的計算、NSGA-II算法對路徑的優(yōu)化和頻譜分配過程；基于Dijkstra最短路徑算法計算條邊分離路徑的時間復雜度為(g)；用NSGA-II算法對路徑進行優(yōu)化的時間復雜度主要取決于優(yōu)化目標數目和種群規(guī)模大小，時間復雜度為(2(C)2)[14]；頻譜分配過程中主要查詢業(yè)務路徑經過的鏈路上的空閑頻隙，然后進行資源分配，則時間復雜度為，其中為業(yè)務路徑經過的鏈路數目；經上述分析GMPA總的時間復雜度為(lg+NSE+2(C)2)。

4 算法仿真結果分析

4.1 仿真參數設置

為了驗證算法的性能，本文將GMPA算法分別與PF-MBL算法[6]MPP算法[10]進行了帶寬阻塞率，資源利用率和路徑距離差的性能仿真。仿真中使用的分別是24個節(jié)點43條鏈路的USNET網絡和14個節(jié)點21條鏈路的NSFNET網絡，分別如圖1和圖5所示。仿真時假設業(yè)務請求到達服從參數為的泊松分布，業(yè)務的源-目的節(jié)點服從均勻分布，業(yè)務的持續(xù)時間服從參數為1/的指數分布。每根光纖總頻隙寬度為4.47 THz，頻隙寬度為12.5 GHz，因而每根光纖有358個頻隙。網絡中的業(yè)務從{10 Gbps, 40 Gbps, 100 Gbps}隨機產生。仿真中設置的基本參數：交叉概率為p=0.8，變異概率p=0.005，最大迭代次數nsize=100[15]。

圖5 NSFNET網絡拓撲(km)

4.2仿真結果分析

圖6和圖7分別顯示了3種算法在兩種網絡場景中隨負載變化時帶寬阻塞率的變化情況。可以看出，3種算法的帶寬阻塞率都隨著負載的增加而增加。但在相同的負載情況下，MPP算法相比于PF-MBL算法具有更低的帶寬阻塞率，且GMPA算法獲得的帶寬阻塞率最低。這充分表明了多路徑保護機制在業(yè)務傳輸時，由于把業(yè)務分割為多個小粒度的業(yè)務進行多路徑傳輸，相比單路徑傳輸，可以明顯地降低業(yè)務的帶寬阻塞率。而本文提出的GMPA算法帶寬阻塞率更低于MPP算法，這主要因為GMPA算法在業(yè)務傳輸時優(yōu)化了業(yè)務帶寬的分割策略，通過對帶寬基因位的變異操作，找到占用網絡頻譜資源較少的多路徑帶寬分配方案。相比圖6，圖7所示各算法的帶寬阻塞率在相同負載下比圖6所示數值都低一些，這是由于業(yè)務在節(jié)點和路徑更多的USNET網絡中傳輸時，源到目的節(jié)點所需路徑的平均跳數較少。由于頻譜分配需要滿足頻譜一致性和連續(xù)性約束，業(yè)務傳輸路徑的平均跳數越少，越容易被成功傳輸。

圖6 NSFNET網絡中不同負載下帶寬阻塞率的對比???????? 圖7 USNET網絡不同負載下帶寬阻塞率的對比

圖8和圖9分析了3種路徑保護算法在兩種網絡環(huán)境下對頻譜資源利用率的影響。頻譜資源利用率為傳輸業(yè)務需要的帶寬資源與網絡中總的帶寬資源比值。圖8和圖9都中表明MPP算法和GMPA算法相比于PF-MBL算法頻譜資源利用率提升了，主要原因是在相同負載下PF-MBL算法阻塞了更多的業(yè)務不能有效地利用網絡資源。此外MPP算法的頻譜利用率高于GMPA算法，這是因為GMPA算法在個體的基因位構造中設置了帶寬基因位，并基于網絡資源設置了優(yōu)化向量函數，在算法遺傳階段通過對個體的等級分類和擁擠距離排序可以找到占用網絡帶寬資源少的路由和頻譜分配方案，因此，在傳輸相同業(yè)務時，GMPA算法比MPP算法占用更少的頻譜帶寬資源。相比圖8，圖9所示各算法的頻譜資源利用率比圖8所示的指標低一些，這是由于業(yè)務在連通度較高的USNET網絡中傳輸時，為源節(jié)點到目的節(jié)點找到的邊分離路徑數目較多，找到跳數更少的傳輸路徑概率較大，因此在USNET網絡中傳輸相同業(yè)務時需要消耗的頻譜資源少一些，從而節(jié)約了網絡頻譜資源。

圖8 NSFNET網絡中不同負載下頻譜資源利用率的對比???????? 圖9 USNET網絡不同負載下頻譜資源利用率的對比

圖10和圖11表明了GMPA算法和MPP算法路徑距離差異性能。路徑距離差異是平均每個業(yè)務的最長路徑和最短路徑距離的差值，差值大小對業(yè)務的接收端多路徑時延差影響較大。由于PF-MBL算法是單路徑保護策略不存在路徑間時延差問題，因此，這里性能對比僅針對GMPA算法和MPP算法進行了路徑距離差異性能的比較。在NSFNET和USNET網絡中，GMPA算法路徑距離差異性能明顯優(yōu)于MPP算法，這表明GMPA算法在基于前條邊分離最短路徑設置的種群初始化方案，經過個體路徑基因位的自交叉操作，可以找到滿足帶寬的多路徑傳輸方案；同時，GMPA算法基于優(yōu)化向量函數的等級分類和擁擠距離排序，能從眾多的多路徑組合方案中找到路徑距離差異較小的路由方案。相比圖10，圖11所示MPP算法和GMPA算法在USNET網絡中比在NSFNET網絡中仿真得到的路徑時延差性能較好一些，原因是NSFNET連通度較低，使業(yè)務的平均最短路徑和次短路徑距離差距較大。

圖10 NSFNET網絡中不同負載下路徑距離差異的對比???????? 圖11 USNET網絡不同負載下路徑距離差異的對比

5 結束語

本文研究了彈性光網絡中生存性保障的多路徑路由和頻譜分配問題，基于NSGA-II多目標遺傳算法，提出了遺傳多路徑保護算法GMPA，解決彈性光網絡多路徑時延差過大的問題，同時節(jié)約了網絡頻譜資源。GMPA算法使用智能優(yōu)化算法思想，設計了一種有效的個體基因位組合方式，通過帶寬基因位的變異、自交叉操作方式和精英保留策略，能有效地找到滿足生存性多路徑傳輸時延差較小和帶寬分配較優(yōu)的多路徑傳輸和頻譜帶寬分配方案。隨著光網絡的發(fā)展，將軟件定義網絡(Software Defined Networking, SDN)通過集中控制器直接提供流交換的思想引入光網絡中，減小光網絡數據轉發(fā)中的配置時間，在有效降低業(yè)務恢復所需傳輸時延同時，以進一步有效地減少用戶端到端傳輸時延滿足時延敏感類業(yè)務的恢復時間，對推動新的數據業(yè)務在未來光網絡中應用和性能保證至關重要。

[1] ZHOU H, MAO S, and AGRAWAL P. Optical power allocation for adaptive transmissions in wavelength-division multiplexing free space optical networks[J]., 2015, 1(3): 171-180. doi:10.1016/j.dcan.2015.09.004.

[2] 劉煥淋, 方強, 雷芳. WDM光網絡中多播業(yè)務量疏導方法分析[J]. 重慶郵電大學學報(自然學報), 2012, 24(3): 269-277. doi: 10.3979/j.issn.1673-825X.2012.03.001.

LIU Huanlin, FANG Qiang, and LEI Fang. Analysis of multicast traffic grooming algorithms in WDM mesh networks [J].()2012, 24(3): 269-277. doi: 10.3979/j.issn.1673-825X.2012.03.001.

[3] 劉煥淋, 歲蒙, 徐一帆, 等. 基于距離自適應和有效共享路徑感知的光疏導方法[J]. 電子與信息學報, 2015, 37(8): 1955-1970. doi: 10.11999/JEIT141442.

LIU Huanlin, SUI Meng, XU Yifan,A method of optical grooming for distance-adaptive and effective sharing path-aware[J].&,2015, 37(8): 1955-1970. doi: 10.11999/ JEIT141442.

[4] SHEN G, WEI Y, and BOSE S K. Optimal design for shared backup path protected elastic optical networks under single-link failure[J]., 2014, 6(7): 649-659. doi: 10.1109/JOCN.2014. 6850206.

[5] WAN X, HUA N, and ZHENG X. Dynamic routing and spectrum assignment in spectrum-flexible transparent optical networks[J]., 2012, 4(8): 603-613. doi: 10.1364/JOCN.4. 000603.

[6] TARHAN A and CAVDAR C. Shared path protection for distance adaptive elastic optical networks under dynamic traffic [C]. Reliable Networks Design and Modeling (RNDM), Almaty, 2013: 62-67. doi: 10.1109/ICUMT.2013.6798405.

[7] WANG X, KUANG K X, WANG S,. Dynamic routing and spectrum allocation in EONs with mixed line rates[J]., 2014, 6(12): 1115-1127. doi: 10.1109/JOCN.2014.6985903.

[8] ZHU Z, LU W, ZHANG L,Dynamic service provisioning in elastic optical networks with hybrid single-multi-path routing[J]., 2013, 31(1): 15-22. doi: 10.1109/JLT.2012.2227683.

[9] XIAO N and RUAN L. Survivable multipath provisioning in OFDM-based flexible optical networks[C]. Globecom Workshops, Anaheim, 2012: 346-351. doi: 10.1109/ GLOCOMW.2012.6477595.

[10] RUAN L and ZHENG Y. Dynamic survivable multipath routing and spectrum allocation in OFDM-based flexible optical networks[J]., 2014, 6(1): 77-85. doi: 10.1364/JOCN.6.000077.

[11] LU W, ZHOU X, GONG L,. Dynamic multi-path service provisioning under differential delay constraint in elastic optical networks[J]., 2013, 17(1): 158-161. doi: 10.1109/LCOMM.2012.120612.121343.

[12] HUANG S, MARTEL C U, and Mukherjee B. Survivable multipath provisioning with differential delay constraint in telecom mesh networks[J]., 2011, 19(3): 657-669. doi: 10.1109/TNET.2010. 2082560.

[13] 尹珊. 靈活光網絡中的資源優(yōu)化[D]. [博士論文], 北京郵電大學, 2014.

YIN Shan. Resource optimization in flexible optical WDM networks[D]. [Ph.D. dissertation], Beijing University of Posts and Telecommunications, 2014.

[14] 申曉寧, 李濤, 張敏. 一種基于模糊邏輯引入偏好信息的多目標遺傳算法[J]. 南京理工大學學報, 2011, 32(2): 245-250. doi:10.14177/j.cnki.32-1397n.2011.02.015.

SHEN Xiaoning, LI Tao, and ZHANG Min. Multi-objective optimization genetic algorithm incorporating preference information based on fuzzy logic[J]., 2011, 32(2): 245-250. doi:10.14177/j.cnki.32-1397n.2011.02.015.

[15] 張宇, 李國建, 史彬. 非支配排序進化策略求解煤氣化多目標優(yōu)化問題[J]. 化工學報, 2013, 64(12): 4628-4633.

ZHANG Yu, LI Guojian, and SHI Bin. Multi-objective optimization of coal gasifier using NSES[J]., 2013, 64(12): 4628-4633.

Optimization Survivable Multipath Provisioning Based on Multi-objectives Genetic Algorithm for Elastic Optical Networks

LIU Huanlin①LI Ruiyan①KONG Deqian①CHEN Yong②

①(Key Laboratory of Optical Communications and Networks, Chongqing University of Posts and Telecommunications, Chongqing 400065, China)②(School of Automation, Chongqing University of Posts and Telecommunications, Chongqing 400065, China)

Multipath provisioning algorithm outperforms single-path provisioning algorithm in terms of bandwidth blocking probability. However, multipath transmission causes the differential delay among different paths and affects the usage of spectrum resources. To address the problem, a Genetic Multipath Protection Algorithm (GMPA) is proposed based on multi-objectives genetic algorithm. according to traffic requests, thelink-disjoined paths and bandwidth assignments are designed as the population initialization scheme. A vector function is proposed to balance the path-distance difference and network spectrum resources by optimizing population classification and crowding distance sorting. An individual self-cross pattern is introduced and the variation range and constraint conditions of bandwidth gene are designed to improve the algorithm search ability and convergence. Compared with the Multiple Path Protection (MPP) and Primary First-fit Modified Backup Last-fit (PF-MBL), simulation results show that the proposed GMPA algorithm can get lowest bandwidth blocking probability, its spectrum resource utilization is close to the optimal MPP, and the path-distance difference of GMPA is better than that of MPP.

Elastic Optical Networks (EONs); Genetic Multipath Protection Algorithm (GMPA); Path-distance difference

TN929.11

A

1009-5896(2016)09-2261-07

10.11999/JEIT151384

2016-05-13；

2016-07-04

國家自然科學基金(61275077,61571072)，重慶市教委自然科學基金(KJ1140421)，重慶市科委自然基金(2015jcyjA40024)

The National Natural Science Foundation of China (61275077, 61571072), The Scientific Research Fund of Chongqing Municipal Commission (KJ1140421), The Basic and Frontier Research Program of Chongqing (2015jcyjA40024)

劉煥淋 liuhl2@sina.com

劉煥淋： 女，1970年生，教授，研究方向為光通信技術與業(yè)未來網絡.

李瑞艷， 女，1989年生，碩士，研究方向為彈性光網絡生存性路由和頻譜分配算法.

孔德謙， 男，1995年生，本科生，研究方向為光網絡與通信技術.

陳 勇， 男，1963年生，教授，研究方向為光通信技術、傳感檢測與自動化技術.