適用于波長交換光網絡的波長旋轉圖模型設計

趙繼軍，張曙光，趙文玉

(1. 河北工程大學 信息與電氣工程學院，河北 邯鄲 056038；2. 工業和信息化部 電信傳輸研究所，北京 100045)

1 引言

在解決波長交換光網絡（WSON）的路由與波長分配（RWA）問題時，無論是把RWA問題拆分為路由和波長分配2個子問題，還是利用啟發式算法解決RWA問題都需要考慮波長分配問題[1～4]，目前在解決波長分配子問題時一般是基于分層圖的思想，分層圖對于解決具有波長一致性限制的RWA問題十分有效[5,6]，但解決具有波長智能調度的RWA問題時，就顯得不是十分有效[7～9]，主要存在波長轉換的次數選擇、波長轉換節點確定、波長分配繁瑣等多種限制。本文根據波長智能調度的需要提出了一種基于波長轉換旋轉圖模型解決RWA問題的思想，并構建了波長轉換旋轉圖模型和提出基于新模型的路由波長分配新策略。仿真結果表明，基于波長旋轉模型的波長分配策略可以有效降低網絡的阻塞率，提高全網資源利用率。

2 波長旋轉圖模型設計

2.1 波長分層圖模型分析

利用分層圖模型解決具有波長一致性限制的RWA問題是有效的，因此，近年來很多文獻利用分層圖模型解決RWA問題，文獻[6]提出了一種基于分層圖的最大邊不相關RWA算法；文獻[7]利用分層圖方法來記錄WDM網絡狀態，提出了一種鏈路狀態描述模型；文獻[8]基于分層圖模型提出了一種解決 WDM 網絡的動態路由和波長分配問題的算法；文獻[9]基于分層圖提出了一種在WDM網狀網中支持多種可靠要求的業務量疏導算法，但是文獻[6～9]利用分層圖模型解決的都是具有波長一致性約束限制的RWA問題，如果利用現有的分層圖模型解決具有波長轉換能力的WDM網絡RWA問題，就需要考慮層與層之間的倒換，具體分析如下。

波長路由光網絡的物理拓撲以無向圖G(V,E,W)表示，其中, V、E、W 分別表示網絡的節點集合、雙向鏈路集合(每個鏈路由 2根方向相反的單向光纖構成)和每個鏈路的波長集合(每根光纖所支持的波長數相同)。波長分層圖模型的物理拓撲是利用分層圖 LG(V*,E*)來描述，分層圖 LG(V*,E*)是把網絡拓撲中的物理拓撲復制成相同的|W|份，每一份為一層，對應波長集W中的一個波長iλ（其中i=1,2,…,|W|）。

假設W=3，圖1所示的物理拓撲圖就變成分層圖（如圖2所示），在波長分層圖模型中形成了3層，自上而下對應的波長依次為1λ、2λ和3λ。當模型中源—目的節點對之間滿足波長連續性限制時，形成的光通路在同一個波長分層內。對于一個連接請求，應用分層圖模型實現了路由和波長分配的并行計算，它所經過的光路徑，就是該光連接在物理拓撲上經過的路徑，光連接所在的波長分層就是光連接所占用的波長。圖 1中的光連接請求（V1,V4）在圖 2中建立的光路徑是，即該光連接請求在物理拓撲中的路徑為V1→V2→V3→V4，且該光連接請求被分配的波長為λ1。因此，基于分層圖模型的RWA算法非常適用于解決具有波長連續性限制的RWA問題。但是，若源—目的節點對之間的節點具有波長轉換能力，形成的光通路就有可能在不同波長分層中，具體到分層圖模型中，一個光連接請求進行路由和波長分配時，就不僅僅是在一個波長分層中進行計算，圖1中的光連接請求（ V1,V4）在圖2中建立的光路徑可能有等，該光連接請求在物理拓撲中的路徑仍然為V1→V2→V3→V4，但是在具備波長轉換能力的網絡環境下，該光路徑的每個鏈路上分配的波長就不一定完全都是λ1，某條鏈路上分配的波長可能是λ2或λ3,不再受波長一致性的限制。

圖1 波長路由光網絡的物理拓撲

圖2 波長路由光網絡波長分層圖模型

通過對分層圖模型的分析發現，任意的一個光連接請求從源節點到達目的節點在同一波長分層內選擇路由，并且每條鏈路只允許一個光連接經過，較好地滿足了波長一致性約束限制下的RWA問題的解決。然而，基于分層圖解決具有波長轉換能力的 RWA問題時，主要是在選擇光通路時選擇一條或幾條代價為0的虛鏈路，但是如果這樣就增加了選路的時間，同時還存在如下 3個問題：1）在哪個節點處進行波長轉換？2）用何種波長轉換策略？3）如何分配波長？因此，本文就想如何不用選擇一條或幾條代價為0的虛鏈路也能解決具有波長轉換能力的 RWA問題，所以在本論文中提出了一種波長旋轉圖模型（WRG,wavelength rotation graph），并構建了波長旋轉圖模型，在該模型上不僅可以同時解決WDM網絡中的選路和波長分配問題，還使波長在節點處智能調度可行。

2.2 波長旋轉圖模型定義

波長旋轉圖模型的物理拓撲利用旋轉圖RG (V*, E*)來描述，旋轉圖模型是將物理拓撲中節點Vi到節點Vj的物理鏈路eij依據平均分配的原則分成W個波長鏈路，每一個虛鏈路可以邏輯依附在旋轉橢球體的表面，分別為,, … ,，如圖3所示，形成波長旋轉圖中的W條鏈路，即物理拓撲中節點Vi到節點Vj的鏈路eij對應并且原來的雙向鏈路變成方向相反的 2條有向鏈路，Vi,Vj∈ V ，eij∈ E 。這樣，旋轉圖 R G(V*, E*)的每一鏈路都代表一個波長，按順序對每一鏈路所對應的波長進行編號，依次為 λ1, λ2, … ,λW。

圖3 波長旋轉圖模型鏈路分解

假設W=3，波長旋轉圖的每一鏈路所對應的波長依次為λ1,2λ和3λ，則圖1中所示的物理拓撲利用旋轉圖就轉變為圖4所示。

分析可知，在波長分層圖模型中，光路從源節點到目的節點必須受波長一致性約束限制。對于波長旋轉圖模型，一個連接請求，可在波長旋轉圖上進行選路，它所經過的路徑，就是該光連接在物理拓撲上經過的路徑，光連接的各個鏈路對應的波長就是虛鏈路所對應的波長，較好地適應了波長轉換條件下的選路要求。

圖4 波長旋轉圖模型網絡鏈路分解

2.3 基于波長旋轉角的波長分配策略

基于波長旋轉圖模型利用RWA算法進行選路和波長分配，通過OSPF算法能夠直觀地找到光連接在物理拓撲上經過的鏈路，但光連接所經過的鏈路上波長分配就需要根據網絡波長資源求解，首先需要解決波長分配問題，為了有效解決這一問題，在波長旋轉圖模型的基礎上提出了波長旋轉角的概念。

波長旋轉圖的旋轉角定義為：把節點Vi到節點Vj的鏈路eij分解成虛鏈路,,…,，并且都依次依附在旋轉球體的表面，任意虛鏈路之間夾角稱為波長旋轉圖的旋轉角，記為。

定義波長旋轉圖的旋轉角是想通過旋轉角能夠在選路的同時直接分配波長，也就是利用虛鏈路和之間的旋轉角 α imjn進行波長分配，節點Vi到節點Vj之間選擇波長思路如下。

1) 置K=1，若節點Vi的上一節點與節點Vi之間分配的波長是sλ，判斷節點Vi與節點Vj之間的波長sλ是否空閑，若空閑，則給鏈路分配波長sλ，并把該鏈路的波長sλ置為已占用；否則，轉到步驟 2)。

圖5 波長旋轉圖節點對之間虛鏈路投影

2) 節點Vi和節點Vj之間的旋轉圖以ViVj為軸逆時針旋轉 360。/W 度，判斷波長λs+K是否空閑，若空閑，則分配波長；若已占用，則K+1，然后重復步驟2)直至K=W。其中：s代表被分配波長的波長數；sλ代表節點Vi的上一節點與節點Vi之間分配的波長是第s個波長資源；K是一個控制變量，它的作用就是在節點Vi與節點Vj之間選擇波長時，使節點Vi與節點Vj之間沒有空閑的波長資源，從而不會出現死循環；λs+K代表分配的波長資源是第s+K個波長。

綜上所述，通過波長旋轉圖模型的構建，提供了一種基于波長旋轉角的波長分配策略，可以同時解決具有波長轉換能力的選路和波長分配問題，因此本文構建的波長旋轉圖模型在 WSON網絡中具有較好的適用性。

3 基于波長旋轉圖模型求解RWA問題的過程

由于RWA問題是一個NP完全問題[3,8],一般將其分成路由和波長分配2個子問題分別解決。本文提出的波長選轉圖模型將RWA問題轉化為在波長旋轉圖上給最短路徑分配波長，并沒有改變 RWA問題是一個NP完全問題的特性，所以基于波長旋轉圖的RWA問題仍然是NP問題。因此，基于波長旋轉圖模型的RWA算法仍然通過將RWA問題拆分為路由和波長分配2個子問題的思想。

構建波長旋轉圖模型的目的是為了能夠更好地解決WSON中的RWA問題，在本節將對基于波長旋轉圖模型求解 RWA問題的思路進行詳細分析。下面通過圖4中的波長旋轉圖來具體闡述基于波長旋轉圖的RWA問題求解過程，當業務連接請求（V1,V4）到達網絡時，假設網絡中與業務請求（V1,V4）有關的鏈路的狀態如表1所示。

表1 網絡中與業務請求（V1,V4）有關的鏈路狀態

根據表 1，業務請求（V1,V4）可選擇路徑有V1→ V2→ V4、 V1→ V3→ V4、 V1→ V5→ V4、V1→V2→V3→V4、V1→V3→V2→V4；在這 5條 路 徑 中 ， V1→ V2→ V4、 V1→ V3→ V4、V1→ V5→ V4、V1→V3→V2→V44條路徑均無連續可用波長資源，路徑 V1→V2→V3→V4有連續可用波長。若RWA算法基于分層圖模型實現，則只能選擇路徑 V1→V2→V3→V4；若RWA算法基于波長旋轉圖模型，由于考慮了波長轉換能力，按照跳數最少的原則可以選擇 V1→ V2→ V4、V1→ V3→ V4、 V1→ V5→ V4，從上面例子可以定性地得知利用波長旋轉圖模型不但可以解決波長智能調度問題，還可以改善波長資源利用率。

通過前面論述和分析可知，利用波長旋轉圖模型解決RWA問題是有效可行的，下面給出基于波長旋轉圖模型求解RWA問題的流程，如圖6所示。

流程中的T是一個控制變量，它的作用是在選擇源-目的節點對之間光路徑時，使WRG-RWA算法不會陷入死循環，Const是一個常量，其值通常為業務請求的最大跳數（不同網絡拓撲的 Const值不同）；s和K的含義與上一節中的s和K含義相同。

圖6 基于波長旋轉圖的RWA（WRG-RWA）算法流程

通過上面的介紹，基于波長分層圖的RWA算法可以實現波長可變的路由，但是在選擇光通路時還需要選擇一條代價為0的虛鏈路，若波長轉換次數相對較多，則選擇代價為0的虛鏈路數也就相對較多，這樣就增加了選路的時間。而基于波長旋轉圖的 RWA算法在選擇光通路時則不需要選擇一條代價為0的虛鏈路，這樣就節省了選擇一條代價為0的虛鏈路的時間，因此，基于波長旋轉圖的 RWA算法就在一定的程度上節省了選路時間。從時間復雜度分析，基于波長分層圖的RWA算法和基于波長旋轉圖的 RWA算法的路由算法都采用 OSPF算法，時間復雜度相同，主要區別在波長分配上，基于波長分層圖的RWA算法在波長分配時最壞情況下時間復雜度為O(H|W|)，基于波長旋轉圖的RWA算法在波長分配時最壞情況下時間復雜度為 O(|W|H)（其中，H是光路徑的跳數，|W|是光纖鏈路上的波長數）。舉例說明，當跳數為3，波長數為8時，38=6 561＞83=512，即在最壞情況下，WLG- RWA算法在波長分配時的時間復雜度遠大于 WRG-RWA算法在波長分配時的時間復雜度。

4 仿真結果與分析

基于前述思路，本文對基于波長分層圖的RWA（WLG-RWA）算法和基于波長旋轉圖的RWA（WRG-RWA）算法進行了對比仿真研究。WLG-RWA算法中路由算法采用OSPF算法，波長分配使用首次命中（FF）算法；WRG-RWA算法的仿真過程中仍然采用OSPF算法進行路徑計算，從計算出的路徑中利用旋轉圖的思想進行波長分配。采用美國NSFNET網絡作為仿真網絡拓撲（如圖7所示），包含14個節點，21條鏈接的網絡，每條鏈接代表了一對雙向光纖。在NSFNET中，本文假設最大波長數分別為4和8，并且每個光節點的信息處理速率相同，業務連接請求是動態業務，服從平均分布，并且網絡具有完全波長轉換能力。通過仿真，主要進行網絡的阻塞率、全網波長資源利用率和算法運行時間3個指標參數的分析。

圖7 仿真中使用的NSFNET網絡拓撲結構

當每根光纖中最大傳輸波長數為 4時，使用WLG-RWA算法和WRG-RWA算法對比的仿真結果如圖8所示；當每根光纖中最大傳輸波長數為8時，使用WLG-RWA算法和WRG-RWA算法對比的仿真結果如圖9所示。仿真結果表明，每條鏈路的總波長數為4或8，WRG-RWA算法的阻塞率都有效降低。當每條鏈路的總波長數為 4時，使用WRG-RWA算法比使用WLG-RWA算法的阻塞率平均降低5.03%，當每條鏈路的總波長數為8時，使用WRG-RWA算法比使用WLG-RWA算法的阻塞率平均降低9.71%，可以看出在波長數較多時，連接請求阻塞率性能提升較為顯著，這是因為隨著波長數的增加，在利用旋轉圖進行波長分配時可以利用的波長增加了，使業務連接請求被阻塞的概率大大降低，這樣，很自然地使連接請求阻塞率性能提升較為顯著。

圖8 阻塞率對比（4個波長）

圖9 阻塞率對比（8個波長）

圖 10和圖 11給出了 WLG-RWA算法和WRG-RWA算法的資源利用率對比圖，分別使用4、8作為每條鏈路的總波長數。仿真結果表明，每條鏈路的總波長數為4或8，WRG-RWA算法的資源利用率均有顯著提高。當每條鏈路的總波長數為4時，使用WRG-RWA算法的阻塞率比使用WLG-RWA算法的資源利用率平均提高 3.3%，當每條鏈路的總波長數為8時，使用WRG-RWA算法的比使用WLG-RWA算法的資源利用率平均提高1.54%。從圖10和圖11可以看出在波長數較多時，全網的資源利用率明顯下降，這是因為總波長數增加，使利用旋轉圖選擇波長時被分配的波長的使用頻率降低，這樣，很自然地使全網的資源利用率明顯下降。

圖10 資源利用率對比（4個波長）

圖11 資源利用率對比（8個波長）

圖 12和圖 13給出了 WLG-RWA算法和WRG-RWA算法的運行時間對比，分別使用 4、8作為每條鏈路的總波長數。從圖中可以看出，每條鏈路的總波長數為4或8時，WRG-RWA算法的運行時間均明顯降低，這恰恰說明了在最壞情況下，WLG-RWA算法在波長分配時的時間復雜度遠大于WRG-RWA算法在波長分配時的時間復雜度。

圖12 算法運行時間對比（4個波長）

圖13 算法運行時間對比（8個波長）

通過對網絡的阻塞率、全網波長資源利用率 2個指標參數的對比分析，WRG-RWA算法的阻塞率明顯降低，全網資源利用率明顯提高。所以，通過仿真和分析可以得出結論，旋轉圖模型可以解決具有波長轉換限制的RWA問題，而且WRG-RWA算法比 WLG-RWA算法更適合解決具有波長轉換限制的RWA問題。

5 結束語

本文提出了一種基于波長旋轉圖模型解決具有波長轉換能力RWA問題的方法，并通過將網絡虛拓撲鏈路及關聯波長均勻分布到旋轉球體的表面，構造了一種新型的波長旋轉圖模型，而且提出了相應的波長分配策略和 RWA算法。通過仿真驗證和分析，旋轉圖模型可以有效解決具有波長轉換限制的RWA問題，而且WRG-RWA算法比WLG-RWA算法更適合解決具有波長轉換限制的RWA問題。

[1] 楊春勇, 王文珍, 劉德明等. 一種全光波長路由器的設計及性能分析研究[J]. 電子與信息學報, 2008, 30(2):455-458.YANG C Y, WANG W Z, LIU D M, et al. Design and performance analysis of an all-optics wavelength router[J]. Journal of Electronics &Information Technology, 2008, 30(2): 455-458.

[2] AZODOLMOLKY S, KLINKOWSKI M, MARIN E, et al. A survey on physical layer impairments aware routing and wavelength assignment algorithms in optical networks[J]. Computer Networks,2009,53(7):926-944.

[3] MAEKOVIC G Z, TEODOROVIC D B, ACIMOVIC-RASPOPOVIC V S. Routing and wavelength assignment in all-optical networks based on the bee colony optimization[J]. AI Communications, 2007, 20(4):273-285.

[4] POINTURIER Y, BRANDT-PEARCE M, SUBRAMANIAM S, et al.Cross-layer adaptive routing and wavelength assignment in all-optical networks[J]. IEEE Journal on Selected Areas in Communications,2008, 26(6):1-13.

[5] BERTHOLD J, SALEH A A M, BLAIR L, et al. Optical networking:past, present and future[J]. Journal of Lightwave Technology,2009,29(9):1104-1117.

[6] 王汝言, 張普釗, 隆克平等. WDM 網絡中一種基于分層圖模型的RWA算法[J]. 光通信技術, 2007, 31(10):4-6.WANG R Y, ZHANG P Z, LONG K P, et al. A layered graph-based RWA algorithm in WDM networks[J]. Optical Communication Technolgy, 2007, 31(10):4-6.

[7] 葛晨暉, 黃晉竹, 孫小菡等. 自相似業務下共享通道保護WDM網絡性能分析[J]. 電子與信息學報, 2006,28(11):2148-2151.GE C H, HUANG J Z, SUN X H, et al. Performance of WDM network with shared-path protection under self-similar traffic[J]. Journal of Electronics & Information Technology, 2006,28 (11):2148-2151.

[8] 肖詩源, 劉賢德, 金鑫. 一種波長轉換受限WDM網絡的動態路由和波長分配算法[J]. 電子學報, 2005,33(6):1140-1142.XIAO S Y, LIU X D, JIN X. An algorithm for dynamic routing and wavelength assignment in WDM network with limited wavelength conversion[J]. Acta Electronica Sinica, 2005,33 (6):1140-1142.

[9] 趙繼軍，雷蕾，紀越峰等. 一種基于ASON的新型動態恢復路徑建鏈協議[J]. 通信學報, 2003, 24(5):85-93.ZHAO J J, LEI L, JI Y F, et al. A novel ASON-based dynamic restoration path setup protocol[J]. Journal on Communications, 2003, 24(5):85-93.