趙繼軍，張曙光，趙文玉

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

1 引言

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

2 波長旋轉(zhuǎn)圖模型設(shè)計

2.1 波長分層圖模型分析

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

波長路由光網(wǎng)絡(luò)的物理拓?fù)湟詿o向圖G(V,E,W)表示，其中, V、E、W 分別表示網(wǎng)絡(luò)的節(jié)點集合、雙向鏈路集合(每個鏈路由 2根方向相反的單向光纖構(gòu)成)和每個鏈路的波長集合(每根光纖所支持的波長數(shù)相同)。波長分層圖模型的物理拓?fù)涫抢梅謱訄D LG(V*,E*)來描述，分層圖 LG(V*,E*)是把網(wǎng)絡(luò)拓?fù)渲械奈锢硗負(fù)鋸?fù)制成相同的|W|份，每一份為一層，對應(yīng)波長集W中的一個波長iλ（其中i=1,2,…,|W|）。

假設(shè)W=3，圖1所示的物理拓?fù)鋱D就變成分層圖（如圖2所示），在波長分層圖模型中形成了3層，自上而下對應(yīng)的波長依次為1λ、2λ和3λ。當(dāng)模型中源—目的節(jié)點對之間滿足波長連續(xù)性限制時，形成的光通路在同一個波長分層內(nèi)。對于一個連接請求，應(yīng)用分層圖模型實現(xiàn)了路由和波長分配的并行計算，它所經(jīng)過的光路徑，就是該光連接在物理拓?fù)渖辖?jīng)過的路徑，光連接所在的波長分層就是光連接所占用的波長。圖 1中的光連接請求（V1,V4）在圖 2中建立的光路徑是，即該光連接請求在物理拓?fù)渲械穆窂綖閂1→V2→V3→V4，且該光連接請求被分配的波長為λ1。因此，基于分層圖模型的RWA算法非常適用于解決具有波長連續(xù)性限制的RWA問題。但是，若源—目的節(jié)點對之間的節(jié)點具有波長轉(zhuǎn)換能力，形成的光通路就有可能在不同波長分層中，具體到分層圖模型中，一個光連接請求進(jìn)行路由和波長分配時，就不僅僅是在一個波長分層中進(jìn)行計算，圖1中的光連接請求（ V1,V4）在圖2中建立的光路徑可能有等，該光連接請求在物理拓?fù)渲械穆窂饺匀粸閂1→V2→V3→V4，但是在具備波長轉(zhuǎn)換能力的網(wǎng)絡(luò)環(huán)境下，該光路徑的每個鏈路上分配的波長就不一定完全都是λ1，某條鏈路上分配的波長可能是λ2或λ3,不再受波長一致性的限制。

圖1 波長路由光網(wǎng)絡(luò)的物理拓?fù)?/p>

圖2 波長路由光網(wǎng)絡(luò)波長分層圖模型

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

2.2 波長旋轉(zhuǎn)圖模型定義

波長旋轉(zhuǎn)圖模型的物理拓?fù)淅眯D(zhuǎn)圖RG (V*, E*)來描述，旋轉(zhuǎn)圖模型是將物理拓?fù)渲泄?jié)點Vi到節(jié)點Vj的物理鏈路eij依據(jù)平均分配的原則分成W個波長鏈路，每一個虛鏈路可以邏輯依附在旋轉(zhuǎn)橢球體的表面，分別為,, … ,，如圖3所示，形成波長旋轉(zhuǎn)圖中的W條鏈路，即物理拓?fù)渲泄?jié)點Vi到節(jié)點Vj的鏈路eij對應(yīng)并且原來的雙向鏈路變成方向相反的 2條有向鏈路，Vi,Vj∈ V ，eij∈ E 。這樣，旋轉(zhuǎn)圖 R G(V*, E*)的每一鏈路都代表一個波長，按順序?qū)γ恳绘溌匪鶎?yīng)的波長進(jìn)行編號，依次為 λ1, λ2, … ,λW。

圖3 波長旋轉(zhuǎn)圖模型鏈路分解

假設(shè)W=3，波長旋轉(zhuǎn)圖的每一鏈路所對應(yīng)的波長依次為λ1,2λ和3λ，則圖1中所示的物理拓?fù)淅眯D(zhuǎn)圖就轉(zhuǎn)變?yōu)閳D4所示。

分析可知，在波長分層圖模型中，光路從源節(jié)點到目的節(jié)點必須受波長一致性約束限制。對于波長旋轉(zhuǎn)圖模型，一個連接請求，可在波長旋轉(zhuǎn)圖上進(jìn)行選路，它所經(jīng)過的路徑，就是該光連接在物理拓?fù)渖辖?jīng)過的路徑，光連接的各個鏈路對應(yīng)的波長就是虛鏈路所對應(yīng)的波長，較好地適應(yīng)了波長轉(zhuǎn)換條件下的選路要求。

圖4 波長旋轉(zhuǎn)圖模型網(wǎng)絡(luò)鏈路分解

2.3 基于波長旋轉(zhuǎn)角的波長分配策略

基于波長旋轉(zhuǎn)圖模型利用RWA算法進(jìn)行選路和波長分配，通過OSPF算法能夠直觀地找到光連接在物理拓?fù)渖辖?jīng)過的鏈路，但光連接所經(jīng)過的鏈路上波長分配就需要根據(jù)網(wǎng)絡(luò)波長資源求解，首先需要解決波長分配問題，為了有效解決這一問題，在波長旋轉(zhuǎn)圖模型的基礎(chǔ)上提出了波長旋轉(zhuǎn)角的概念。

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

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

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

圖5 波長旋轉(zhuǎn)圖節(jié)點對之間虛鏈路投影

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

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

3 基于波長旋轉(zhuǎn)圖模型求解RWA問題的過程

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

構(gòu)建波長旋轉(zhuǎn)圖模型的目的是為了能夠更好地解決WSON中的RWA問題，在本節(jié)將對基于波長旋轉(zhuǎn)圖模型求解 RWA問題的思路進(jìn)行詳細(xì)分析。下面通過圖4中的波長旋轉(zhuǎn)圖來具體闡述基于波長旋轉(zhuǎn)圖的RWA問題求解過程，當(dāng)業(yè)務(wù)連接請求（V1,V4）到達(dá)網(wǎng)絡(luò)時，假設(shè)網(wǎng)絡(luò)中與業(yè)務(wù)請求（V1,V4）有關(guān)的鏈路的狀態(tài)如表1所示。

表1 網(wǎng)絡(luò)中與業(yè)務(wù)請求（V1,V4）有關(guān)的鏈路狀態(tài)

根據(jù)表 1，業(yè)務(wù)請求（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條路徑均無連續(xù)可用波長資源，路徑 V1→V2→V3→V4有連續(xù)可用波長。若RWA算法基于分層圖模型實現(xiàn)，則只能選擇路徑 V1→V2→V3→V4；若RWA算法基于波長旋轉(zhuǎn)圖模型，由于考慮了波長轉(zhuǎn)換能力，按照跳數(shù)最少的原則可以選擇 V1→ V2→ V4、V1→ V3→ V4、 V1→ V5→ V4，從上面例子可以定性地得知利用波長旋轉(zhuǎn)圖模型不但可以解決波長智能調(diào)度問題，還可以改善波長資源利用率。

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

流程中的T是一個控制變量，它的作用是在選擇源-目的節(jié)點對之間光路徑時，使WRG-RWA算法不會陷入死循環(huán)，Const是一個常量，其值通常為業(yè)務(wù)請求的最大跳數(shù)（不同網(wǎng)絡(luò)拓?fù)涞?Const值不同）；s和K的含義與上一節(jié)中的s和K含義相同。

圖6 基于波長旋轉(zhuǎn)圖的RWA（WRG-RWA）算法流程

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

4 仿真結(jié)果與分析

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

圖7 仿真中使用的NSFNET網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)

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

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

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

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

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

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

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

圖12 算法運(yùn)行時間對比（4個波長）

圖13 算法運(yùn)行時間對比（8個波長）

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

5 結(jié)束語

本文提出了一種基于波長旋轉(zhuǎn)圖模型解決具有波長轉(zhuǎn)換能力RWA問題的方法，并通過將網(wǎng)絡(luò)虛拓?fù)滏溌芳瓣P(guān)聯(lián)波長均勻分布到旋轉(zhuǎn)球體的表面，構(gòu)造了一種新型的波長旋轉(zhuǎn)圖模型，而且提出了相應(yīng)的波長分配策略和 RWA算法。通過仿真驗證和分析，旋轉(zhuǎn)圖模型可以有效解決具有波長轉(zhuǎn)換限制的RWA問題，而且WRG-RWA算法比WLG-RWA算法更適合解決具有波長轉(zhuǎn)換限制的RWA問題。

[1] 楊春勇, 王文珍, 劉德明等. 一種全光波長路由器的設(shè)計及性能分析研究[J]. 電子與信息學(xué)報, 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 網(wǎng)絡(luò)中一種基于分層圖模型的RWA算法[J]. 光通信技術(shù), 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] 葛晨暉, 黃晉竹, 孫小菡等. 自相似業(yè)務(wù)下共享通道保護(hù)WDM網(wǎng)絡(luò)性能分析[J]. 電子與信息學(xué)報, 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] 肖詩源, 劉賢德, 金鑫. 一種波長轉(zhuǎn)換受限WDM網(wǎng)絡(luò)的動態(tài)路由和波長分配算法[J]. 電子學(xué)報, 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] 趙繼軍，雷蕾，紀(jì)越峰等. 一種基于ASON的新型動態(tài)恢復(fù)路徑建鏈協(xié)議[J]. 通信學(xué)報, 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.