應用MCDM的彈性光網絡頻譜碎片整理算法

王鯨魚，冉金志，王 平

(1.國防科學技術大學 信息通信學院，陜西 西安 710106；2.西安電子科技大學 綜合業務網理論與關鍵技術國家重點實驗室，陜西 西安 710071)

隨著信息技術的高速發展，網絡帶寬需求多樣化和網絡中傳輸的信息量呈爆炸式增長[1-2]，傳統的波分復用技術采用固定頻譜間隔來分配頻譜，導致頻譜資源浪費嚴重。彈性光網絡(Elastic Optical Network，EON)由于能夠更靈活地利用頻譜資源，受到越來越多的關注[3-7]。路由選擇與頻譜分配(Routing and Spectrum Assignment，RSA)問題是彈性光網絡中的核心問題，其目標是為每個到達的業務計算并分配合理的帶寬和路由，從而優化頻譜利用率[2]。由于頻譜分配需要遵守一致性和連續性約束[3-4]，在網絡的動態建立與拆除過程中，可能會產生大量的頻譜碎片，而降低頻譜資源的利用率并提升網絡的阻塞率[4-8]。針對這一問題，已經提出了一些頻譜整理的方法。文獻[5]通過在頻譜分配時增加不同業務間的保護帶寬最小化業務帶寬阻塞率，但是只適用固定調制方式，易造成帶寬資源浪費，頻譜利用率低。文獻[8]提出了一種基于連接保持時間的非破壞性碎片整理方案。文獻[9]在將頻譜碎片整理方法分為串行方式與并行方式的基礎上主要研究了彈性光網絡的并行頻譜碎片整理。文獻[10]主要介紹了跳躍重整、推挽重整和先接后斷三種非中斷頻譜碎片整理方法并比較了它們的優缺點。

雖然目前提出了很多碎片整理的算法，但大多僅考慮滿足當前到達業務能夠建立，沒有考慮整理碎片和業務建立后鏈路狀態對后續業務建立的影響。基于此，筆者提出一種基于多準則決策(Multiple Criteria Decision Making，MCDM)[11-13]的彈性光網絡頻譜整理算法，在整理頻譜碎片的過程中，當涉及到碎片的移動或重路由等選擇性問題時，傳統做法是將業務連接移動至空閑頻隙即可，而該過程可能會導致移動后網絡的碎片率增加，反而降低了網絡的容量。筆者擬利用多準則決策的方法對碎片整理過程中遇到的選擇性問題綜合考慮各種指標做出決策，從而在最大程度上整理頻譜碎片，降低網絡的阻塞率。

1 相關定義

為了方便算法的描述，首先對相關術語進行解釋和定義。

(1) 額外空間中的額外頻隙

將頻譜末端的一些空間也就是每個鏈路中超出主要頻譜部分的一些空間稱為額外空間。額外空間中的頻隙稱為額外頻隙。為了給主要頻譜部分留出空間，需要將一些移動后可以改善頻譜的連接移動到額外空間。額外空間中額外頻隙的長度應至少等于連接請求的最大值，并且額外空間不能建立連接請求。

(2) 標簽

在算法運行過程中，不同階段整理不同類型的業務連接，“標簽”是指對不同連接根據類型的不同對它們進行標記。

① “不移動”標簽。“不移動”標簽標記的是頻譜開始端的邊緣的連接且如果一個連接的左側超過1/2(含1/2)相鄰于另一個“不移動”連接，則它也將標簽為“不移動”標簽。在碎片整理過程中，“不移動”連接不會移到任何地方。如圖1所示，因為連接A和連接B在頻譜開始端，所以標記為“不移動”連接；因為連接C相鄰于連接A，所以C也被標記為 “不移動”連接；因為連接D占用了兩個鏈路，其中在鏈路3上的連接相鄰于連接B，滿足超過1/2(含1/2)相鄰于標記有“不移動”連接的條件，所以連接D也被標記為“不移動”連接。

圖1 “不移動”連接示意圖

② “消失”標簽。如果連接的剩余時間小于預定義的閾值(例如2 s)，則將該連接標簽為“消失”。

③ “左移”標簽。如果可以將連接移到更好的位置(即更靠近頻譜的開始側)，則將該連接標記為“左移”。

④ “右移”標簽。此標簽用于標記連接無法移到更好的地方或重新路由到其他路由的連接。

⑤ “重新路由”標簽。不可移動的連接可以通過在其他可用路由進行重路由，從而有第二次機會設置在更好的位置，因此筆者將可重路由的連接標記為“重新路由”。

⑥ “縮短”標簽：當業務連接被重新路由后，該連接所占用的鏈路數會減少，使得業務連接的傳輸占用的頻隙數量減少，將這樣的連接標記為“縮短”連接。

(3) 連接干擾

為了將空閑頻譜塊聚合到每個鏈路的頻譜末端，所以當一條連接干擾到其他連接向頻譜開始端移動時，將這條連接稱為“干擾源”。“干擾源”的判斷條件為：

① 該連接沒有被標簽為“不移動”，因為“不移動”連接在整理的過程中不會被移動并且處于頻譜的開始端，不會影響其他連接前移；

② 該連接所占的頻隙數和與該連接相鄰的空閑頻隙數之和大于該連接右側第一個連接的大小；

③ 該連接之前的空閑頻隙數量小于該連接之后第一個連接所占的頻隙數量。

圖2 連接干擾示意圖

例如圖2中，連接A沒有被標簽為“不移動”，連接A所占用的頻隙數和相鄰空閑頻隙之和大于連接B的大小且連接A之前的空閑頻隙數小于連接B所占用的頻隙數，所以連接A干擾連接B。

(4) 空閑相鄰空間的總和

空閑相鄰空間的總和表示連接之前和之后的相鄰空閑頻隙的數量總和。

(5)鏈路碎片率

鏈路碎片率(L)與鏈路中的空閑頻隙有關。計算一個具有N個空閑區域鏈路的碎片率：

(1)

其中，Fi表示第i個空閑區域中空閑塊的數量。鏈路碎片率越大，該鏈路就越難再加入新連接。

最大碎片率(M)指的是鏈路中出現空閑頻隙與有業務的頻隙交叉排列。設一條鏈路具有N個頻隙，當可用頻隙的數量為奇數而被占用的頻隙為偶數時，鏈路的碎片率最大，此時需要利用上限函數來計算其大小。此時M為

(2)

例如當N=11時，鏈路中的空閑頻隙為6，則M=62=36。

連接碎片率(C)是一個連接在鏈路中的碎片率，由L平均后得到

(3)

其中，i表示連接的第i個連接，Q表示連接的總數。

為了達到比較碎片的連接速率，并方便觀察，將碎片率進行指標化，使得其范圍為[0，1]。首先將鏈路碎片率(L)及式(1)由式(4)進行歸一化，得到指標化鏈路碎片率(NL)：

(4)

然后，將NL除以連接的總數，得到指標化碎片率N：

(5)

2 基于多準則決策的頻譜碎片整理算法描述

2.1 基于多準則決策的頻譜碎片整理算法

頻譜碎片整理是將空閑頻隙聚合在可用頻譜的末尾，將到達剩余時間的連接與不可移動的連接轉移至規定的額外空間中以實現頻譜碎片整理。而在移動頻譜碎片的過程中，移動不同的頻譜碎片對網絡的影響不同，有的可能會降低網絡的碎片率，有的則有可能適得其反。所以，在每次選擇時，采用多準則決策對頻譜碎片進行整理，可以基于網絡此時的狀態在每個階段中做出最佳決策來進行頻譜碎片的整理。

基于多準則決策的彈性光網絡頻譜碎片整理算法分為5個階段。這5個階段中，每個階段都會用不同的標簽標記不同類型的連接，并根據多準則決策所設置的權重對連接進行判斷，最后采取最佳的方案。

第1個階段，通過判斷剩余時間，將滿足設定時間閾值的連接標簽為“消失”，然后通過預先定義的權重將標簽“消失”的連接轉移到額外空間，直到額外空間被填滿或沒有標簽為“消失”的連接，這一階段完成后，主要頻譜中就會出現一些空閑的空間。

第2個階段，通過重新路由的方法，減少連接的數量以便騰出更多的空閑頻隙。

第3個階段，利用首次命中算法將“左移”連接移動到頻譜的開始端，并將滿足“不移動”連接指標的連接標簽為“不移動”連接。

圖3 算法總流程圖

第4個階段，利用K-最短路徑法對“不移動”連接進行重新路由。如果“不移動”連接不能被重新路由，則更新其標簽為“右移”連接。

第5個階段，首先將“右移”連接移動到額外空間，然后返回到第3個階段進行循環，直到不執行操作或者所有的連接都標簽為“不移動”連接。

總流程如圖3所示。5個階段的流程如圖4至圖8所示。

圖4 第1階段算法流程

階段1：

(1) 為每個源到目標節點預先進行計算儲存K條最短路徑；

(2) 將所有剩余時間小于t的連接標簽為“消失”連接；

(3) 對于所有的“消失”連接，如果額外空間中有空閑空間，則進行下一步；

(4) 利用MCDM計算“消失”連接的得分，并將最佳連接轉移到額外空間，直到所有“消失”連接轉移完畢或額外空間沒有空閑空間。

圖5 第2階段算法流程圖

階段2：

(1) 根據K-最短路徑篩選出可以重新路由的連接并且標記為“縮短”連接；

(2) 對于所有“縮短”連接，利用MCDM計算其得分，得分最高的進行重路由，直到沒有“縮短”連接；

(3) 更新連接的標簽。

圖6 第3階段算法流程圖

階段3：

(1) 將在頻譜第一個邊緣或與頻譜第一個邊緣的連接相鄰或1/2相鄰的連接標記為“不可移動”連接；

(2) 將連接前有空閑空間的連接標記為“左移”連接；

(3) 對于所有“左移”連接，利用MCDM計算其得分；

(4) 將得分最高的連接利用首次命中算法將其進行左移，直到沒有“左移”連接。

圖7 第4階段算法流程圖

階段4：

(1) 對于所有標記“不可移動”連接，利用K-最短路徑篩選出可以重新路由的連接并且更新其標簽為“重路由”連接；

(2) 將不可重新路由的“不可移動”連接更新其標簽為“右移”連接；

(3) 對于所有“重路由”連接，利用MCDM計算其得分，將最佳連接進行重路由，直到沒有“重路由”連接。

階段5：

(1) 如果額外空間有空閑空間，則進行下一步；

(2) 對于所有標記“右移”連接，利用多準則決策計算其得分，將最佳連接轉移到額外空間；

(3) 直到所有“右移”連接都轉移或額外空間，沒有空閑空間。

2.2 基于MCDM的頻譜碎片整理算法中指標與權重設定

相關文獻和電信業務數據表明各個指標在不同階段中起到的作用不同，同一指標在不同的階段中可能是肯定指標，也可能是否定指標。例如連接的大小(Sx)這一指標，表示連接x所需要的頻隙數量，在選擇最佳“消失”連接中，Sx是一個肯定指標，因為當連接具有更多的頻隙時，它在轉移后釋放的頻隙也就更多；而在選擇最佳“左移”連接時，Sx是一個否定指標，因為頻隙數量少的連接比頻隙數量多的連接更容易得到匹配。因此，同樣的指標在不同階段中具有不同的權重和作用。以選擇最佳“消失”連接為例，影響選擇“消失”連接的指標有：

① 連接的大小(Sx)：連接x所需的頻隙數量。肯定指標，因為當連接具有更多頻隙時，它將在傳輸后釋放更多頻隙。

② 連接的數量(Lx)：連接x的連接數量。肯定指標，因為連接的數量越多，則占用網絡中的空間就越多，轉移后釋放的空間就越多。

③ 連接受到的干擾數(Ix)：連接x受干擾的連接數。肯定指標，因為干擾連接會阻止其他連接移動到更好的位置。干擾連接x的數量越多，傳輸該連接越好。

④ 剩余時間(Rx)：連接x的剩余時間。否定指標，因為連接的剩余時間越短，該連接將會越快的被釋放，因此，剩余時間越長的連接，占用頻隙的時間也就越長，該連接便越值得被移動。

⑤ 移動后的總空閑時隙之和(Tx)：表示連接x的所有鏈路中所有相鄰空閑時隙(在連接之前和之后)的總和。肯定指標，因為兩側都具有較多自由空間的連接，可以在傳輸后釋放的整體性空間更多。

通過簡單加性加權的方法對每個指標的重要程度進行確定(范圍為1～10)。

對這5個指標進行排序，在“消失”連接的轉移過程中，起決定性作用的是轉移后對網絡空間的影響，所以連接受到的干擾數(Ix)這一指標最為重要，而移動后的總空閑時隙之和(Tx)代表著移動連接后網絡空出的頻隙數，雖然也體現了對網絡的影響，但是Ix的影響程度遠大于Tx，因為移動的連接受到的干擾數越多，代表著這個連接對網絡的影響程度越大，移動后網絡的改善情況就越好。因此，為了凸顯其決定性的作用，筆者將連接受到的干擾數(Ix)的重要程度設置為10，本階段其他4個指標的重要程度設置為：移動后的總空閑時隙之和(Tx)為5；連接的大小(Sx)為4；連接的數量(Lx)和剩余時間(Rx)均為3(表示Lx和Rx重要程度相同)。最終選擇“消失”連接的指標的重要程度表，如表1所示。

表1 選擇“消失”連接的指標的重要程度表

然后利用層次分析法列出滿足一致性的矩陣，如表2所示。

表2 選擇“消失”連接的成對比較矩陣表

再規范表2，將表中的值除以總和，如表3所示。

表3 AHP法加權后的結果

最后通過求平均值，確定出篩選最佳“消失”的每個指標的權重，如表4所示。

表4 選擇“消失”連接的指標及權重

通過同樣的方法確定其他階段中應選擇的最佳連接的指標和權重。

選擇最佳“縮短”連接的指標與權重：

① 連接差(Cx)：表示新路由和當前連接路由的連接數量之間的差。肯定指標，因為如果連接可以移動到連接數量較少的路線，將會釋放更多的頻隙。

② 連接的大小(Sx)：連接x所需的頻隙數量。否定指標，因為由于頻隙數量的限制，要找到一個需要頻隙較多的新連接比較困難。

③ 連接的數量(Lx)：連接x的連接數量。肯定指標，因為連接的數量越多，則占用網絡中的空間就越多，轉移后釋放的空間就越多。

④ 連接受到的干擾數(Ix)：連接x干擾的連接數。肯定指標，因為干擾連接會阻止其他連接移動到更好的位置。干擾連接x的數量越多，傳輸該連接越好。

⑤ 剩余時間(Rx)：連接x的剩余時間。肯定指標，因為剩余時間較少的連接將更快完成，并在鏈接上生成片段；但是剩余時間更多的連接將保留更多的時間，因此對其進行縮短操作。

⑥ 移動后的總空閑時隙之和(Tx)：表示連接x的所有鏈路中所有相鄰空閑時隙(在連接之前和之后)的總和。這是一個肯定的指標，因為兩側都具有較多自由空間的連接，可以在傳輸后釋放的整體性空間更多。

選擇最佳“縮短”連接的指標的重要程度如表5所示。權重的設定如表6所示。

表5 選擇最佳“縮短”連接的指標的重要程度

表6 選擇最佳“縮短”連接的指標與權重

選擇最佳“左移”連接的指標與權重：

① 移動后的總空閑時隙之和(Tx)：表示連接x的所有鏈路中所有相鄰空閑時隙(在連接之前和之后)的總和。肯定指標，因為兩側都具有較多自由空間的連接，可以在傳輸后釋放的整體性空間更多。

② 連接的大小(Sx)：連接x所需的頻隙數量。否定指標，因為小連接有更多機會找到比大地方更好的地方。

③ 剩余時間(Rx)：連接x的剩余時間。肯定指標，因為剩余時間較少的連接將更快完成，并在鏈接上生成片段；但是剩余時間更多的連接將保留更多的時間，因此對其進行縮短操作。

④ 距離(Dx)：連接x與頻譜開始端的距離。肯定指標，越靠近頻譜的開始端，越容易被移動。

⑤ 連接的數量(Lx)：連接x的鏈接數。否定指標，因為鏈接數較少的連接找到空閑頻隙的機會比鏈接數較多的連接大。

⑥ 移動后碎片改善率(Fx)：新的Lx與現有Lx的差異。因為移動一個連接可以降低其鏈接的碎片率，所以這是一個肯定指標。

⑦ 連接受到的干擾數(Ix)：受連接x干擾的連接數。肯定指標，因為干擾連接會阻止其他連接移動到更好的位置。干擾越高，傳輸該連接越好。

⑧ 從起點開始的新距離(Nx)：連接點x的新位置距光譜起點的距離。否定指標，因為筆者的目標是將占用的頻隙移到頻譜的開始端，將空閑頻隙移到頻譜的末尾端。因此，離頻譜開始端較近的位置比距離較遠的位置更好。

選擇“左移”連接的指標的重要程度如表7所示。權重的設定如表8所示。

表7 選擇“左移”連接的指標的重要程度

表8 選擇“左移”連接的指標與權重

因為移動“右移”連接與“消失”連接都是以對網絡空間的影響大小為主，影響越大，移動后頻譜的改善效果就越好，所以在指標的選擇與權重的確定過程中移動“右移”連接與移動“消失”連接的指標與權重相同。選擇“重路由”連接與“縮短”連接時，由于都采用的K-最短路徑算法，所以選擇“重路由”連接與“縮短”連接的指標與權重相同。

3 仿真分析

3.1 仿真條件

為了評估算法的性能，采用美國國家科學基金會(National Science Foundation，NSF)的主干網絡進行仿真，如圖9所示。該網絡擁有14個節點和21個鏈路，每個節點之間的距離以km為單位。每條鏈路上具有110個頻隙，其中10個作為額外頻隙，每個頻隙的大小為12.5 GHz。

圖9 NSF網絡拓撲圖

仿真方案：采用隨機接入一定數量的業務請求連接，每個業務連接大小在2～10個頻隙之間隨機產生，每個連接的保持時間為10 s，業務的源節點和目標節點隨機生成，路由方法采用K-最短路徑法，其中K等于3。為了驗證算法的有效性，筆者選取首次命中(K-Shortest Path with First Fit spectrum allocation，KSP-FF)算法[10]和推挽碎片整理算法(Push Pull，PP)[10]進行比較。仿真過程中，設置“消失”連接的剩余時間閾值為10 s，對帶寬阻塞率、請求阻塞率和頻譜利用率進行分析，其中帶寬阻塞率表示被阻塞的請求帶寬與總請求帶寬的比值，請求阻塞率表示被阻塞的連接數量與總請求的連接數量之比。

3.2 阻塞率分析

圖10為分別采用KSP-FF、PP和基于MCDM碎片整理算法下的網絡帶寬阻塞率。圖中，E為Erlang的縮寫，中文譯為“厄蘭“，話務量，意為”占線小時”。以下圖同。

圖11為基于KSP-FF和多準則決策碎片整理算法的帶寬阻塞率改善對比圖。

圖10 帶寬阻塞率 圖11 帶寬阻塞率改善對比圖

從圖10可以明顯看，出當業務連接較少時，3種算法的帶寬阻塞率差距不大，而隨著業務連接數量的增加帶寬阻塞率都呈現上升趨勢，而基于多準則決策的算法優于PP和KSP-FF，當業務請求負載達到300 E即高負載時，基于多準則決策的碎片整理算法帶寬阻塞率為36%，明顯低于PP和KSP-FF的帶寬阻塞率。同時，從圖11可以看出，當連接數達到60時，首次命中算法的網絡開始出現阻塞情況，而基于多準則決策的算法在業務連接數量達到100左右時，帶寬阻塞率才開始出現變化；此時基于多準則決策的算法，相比首次命中的算法帶寬阻塞率改善最高可達20%；當業務連接數量達到120左右時，可以看出，基于多準則決策的算法整理后的帶寬阻塞率有所降低，當達到140左右時發生突變；此時相比于首次命中算法，基于多準則決策算法的帶寬利用率改善了約10%。隨著業務連接繼續增加，基于多準則決策的頻譜碎片整理算法相比于首次命中算法帶寬阻塞率降低了約17%。

從上述分析可以得出，基于多準則決策的頻譜整理算法可以有效降低網絡的帶寬阻塞率。

圖12 業務請求阻塞率

圖13 業務請求阻塞率改善圖

圖14 頻譜利用率

圖12和圖13為業務請求阻塞率仿真結果。從圖12可以看出隨著業務連接數量的增加，3種算法的網絡請求阻塞率呈現上升趨勢，而基于多準則決策的算法的請求阻塞率小于KSP-FF和PP的阻塞率；從圖13可以看出，基于多準則決策的算法在業務請求達到120時，才出現請求阻塞的情況，當業務請求達到140時，基于多準則決策的算法相對首次命中算法的請求阻塞率得到明顯改善，此時首次命中算法整理后的請求阻塞率為15%左右，基于多準則決策的碎片整理算法整理后的請求阻塞率為10%左右。由以上分析可以得出，相對于其他兩種算法，基于多準則決策的算法可以有效改善彈性光網絡的業務請求阻塞率。由于多準則決策增加了判決機制，算法運行時間大于KSP-FF和PP算法，但是基于多準則決策在改善業務阻塞率方面有明顯的優勢。

3.3 頻譜利用率分析

圖14為頻譜利用率仿真圖，可以看出整理后的頻譜利用率高于整理前的頻譜利用率。

隨著接入業務連接的增多，當達到高流量負載(業務請求數量達到200 E)時，基于多準則決策的頻譜利用率達45%；當業務請求數量達到300 E時，基于多準則決策的頻譜利用率高達65%；而基于KSP-FF在高負載下，頻譜利用率最高約達38%；因此基于多準則決策的頻譜碎片整理算法相比于基于首次命中的頻譜碎片整理算法的頻譜利用率，得到了很大的改善。這表明，基于多準則決策的頻譜碎片整理算法，在降低帶寬阻塞率和請求阻塞率的同時，提高了頻譜利用率，進而提高了網絡資源的利用率。

4 總 結

針對當前彈性光網絡中路由選擇與頻譜分配算法的頻譜碎片整理問題，基于多準則決策，筆者提出了彈性光網絡中頻譜碎片的整理算法降低業務帶寬阻塞率。根據層次分析法確定了算法在運行過程中不同指標的權重，舉例說明了多準則決策的適用性，并且理論分析和仿真結果表明，基于多準則決策的頻譜碎片整理算法，可以有效地提高頻譜利用率并降低網絡的阻塞率。