光網(wǎng)絡(luò)中若干路由和頻譜分配算法研究

陳 鵬

（北京郵電大學(xué)，北京 海淀 100876）

0 引言

當(dāng)前，以信息技術(shù)為核心的全球新一輪科技革命和產(chǎn)業(yè)變革正在蓬勃興起，隨著人們對網(wǎng)絡(luò)帶寬需求的快速增長，作為信息網(wǎng)絡(luò)基礎(chǔ)架構(gòu)的核心一環(huán)，光網(wǎng)絡(luò)具有不可替代的重要地位。彈性光網(wǎng)絡(luò)的核心是路由和頻譜分配問題研究，路由和頻譜分配（RSA）問題是廣泛研究的路由和波長分配（RWA）問題的一般推廣，在光網(wǎng)絡(luò)中，波長路由和波長分配是一個(gè)基礎(chǔ)的研究問題，也是一個(gè)重要的研究課題。在路由和頻譜分配問題中，頻譜分配必須滿足三個(gè)約束條件，相比路由和波長分配，增加了頻譜連續(xù)性約束，這使得在路由和波長分配中研究的相應(yīng)算法在路由和頻譜分配問題不在適用，并且路由和頻譜分配問題的研究會更加復(fù)雜。路由和頻譜分配問題可以分為靜態(tài)由和動態(tài)路由，也可以將路由和頻譜分配問題拆分為路由問題和頻譜分配兩個(gè)子問題分析[1]。在近幾年的研究中，有采用距離自適應(yīng)調(diào)制模式[2,3]來分析路由和頻譜分配問題，也運(yùn)用智能算法優(yōu)化路由選擇機(jī)制和頻譜分配[8,11,12]，負(fù)載均衡策略[14]和能量消耗[15]也被考慮到路由選擇中，另外，路由和頻譜分配問題也可以看作是多處理機(jī)調(diào)度[5]問題的一種特殊情況，因此，已經(jīng)提出了幾種調(diào)度算法分析求解固定選擇路由和頻譜分配問題中的資源使用情況。已知即使在簡單的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中，路由和頻譜分配問題也是NP-難的，如在四個(gè)節(jié)點(diǎn)的線網(wǎng)絡(luò)上頻譜分配問題已經(jīng)得到證實(shí)，在具有N個(gè)節(jié)點(diǎn)的環(huán)網(wǎng)絡(luò)頻譜分配研究存在一個(gè)3ε+近似算法[6]，另外，在星圖上的頻譜分配問題有一個(gè)4近似算法[7]。如何有效地分析的路由和頻譜分配問題，是本文研究的主要目的。考慮到在網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中一條路由上分配的頻譜必須是連續(xù)的，在動態(tài)路徑建立和頻譜資源釋放過程中會產(chǎn)生一些頻譜碎片[9,10]，降低了頻譜使用效率[13]，如果能研究出很好的路由和頻譜分配算法，既能節(jié)約光纖中帶寬資源，還能保證業(yè)務(wù)通信質(zhì)量[4]。為了節(jié)約頻譜資源，考慮到圖染色模型和路由和頻譜分配問題之間的對應(yīng)關(guān)系，我們從這個(gè)角度建立數(shù)學(xué)模型。優(yōu)化網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)上染色所要的染色數(shù)最少和滿足請求所需的頻譜資源數(shù)最少相對應(yīng)，本文主要介紹了兩者之間的模型轉(zhuǎn)化和相關(guān)的算法分析，在以后的研究中這可應(yīng)用到路由和頻譜分配問題分析中。

1 模型轉(zhuǎn)化

1.1 路由和頻譜分配問題介紹

彈性光網(wǎng)中路由和頻譜分配問題是光網(wǎng)絡(luò)波分復(fù)用技術(shù)的路由和波長分配問題的一般推廣和發(fā)展。路由和波長分配（RWA）問題是對于每一個(gè)業(yè)務(wù)連接請求通過選擇一條合適的路線建立光路連接，并且沿著該路徑分配合適的波長。在沒有波長轉(zhuǎn)換器的光網(wǎng)絡(luò)中，在每個(gè)連接請求建立的端到端路徑中必須分配相同的波長，這就是波長一致性約束條件。

定義1.1(RSA)：給定一個(gè)圖 G = ( V, A)，其中V是頂點(diǎn)集，A是邊集（有向邊），和一個(gè)頻譜需求矩陣 T = [ tsd]，其中 tsd表示請求從節(jié)點(diǎn)s到節(jié)點(diǎn)d需要的頻譜數(shù)目，服務(wù)每一個(gè)業(yè)務(wù)請求尋找一條光路徑和分配連續(xù)的頻譜目標(biāo)是使網(wǎng)絡(luò)中所有請求使用的頻譜總數(shù)目最少；

RSA問題約束條件：

（1）每一個(gè)請求分配連續(xù)的頻譜資源；

（2）每一個(gè)請求在它路徑的每條邊上分配相同的頻譜資源；

（3）使用同一條邊的頻譜分配的頻譜段不相交；

如果每一個(gè)請求的路徑給定，則RSA問題就退化為SA問題。

定義1.2（SA）：在約束從節(jié)點(diǎn)s到節(jié)點(diǎn)d的所有請求必須沿著給定的物理路徑sdp 下RSA問題。

1.2 圖染色模型

1.2.1 圖染色模型介紹

定義 1.3（圖染色）：經(jīng)典圖染色問題是在一個(gè)無向圖G上，給G的每一個(gè)結(jié)點(diǎn)分配一種顏色，如果（ u, v）是一條邊，表示兩個(gè)節(jié)點(diǎn)相鄰，則分配給u和v不同的顏色，目標(biāo)是使用很少的顏色就能為G染色。形式化表示為，G的 k -染色是一個(gè)函數(shù)f: V → {1 ,2,… k }使得對每一條邊（ u , v）有 f ( u)≠f( v)，其中1,2,…k表示可使用的顏色，函數(shù)f表示給每一個(gè)結(jié)點(diǎn)選擇的顏色。如果G有一個(gè) k -染色，則稱它是 k -可染色的圖。

定義 1.4（帶權(quán)圖染色：）帶權(quán)圖染色問題表示無向圖G上的每一個(gè)結(jié)點(diǎn)v有一個(gè)權(quán)重 w ( v)，它表示給頂點(diǎn)v染色所需要的顏色數(shù)，與經(jīng)典圖染色問題最大不同之處在于經(jīng)典圖染色問題只需給每一個(gè)結(jié)點(diǎn)分配一種顏色，而帶權(quán)圖染色問題需要給每一個(gè)結(jié)點(diǎn)v分配 w ( v)顏色數(shù)。同時(shí)，有如果（ u , v）是一條邊，則分配給u和v不同的顏色，目標(biāo)是使用最少的顏色就能為G染色。

1.2.2 模型轉(zhuǎn)化

考慮一般圖 N = ( V, E)上的RSA問題，對于給定的請求集合 R = { ri| ri= ( si, ti, bi)}，業(yè)務(wù)請求 ri的路徑給定，其中 bi表示請求 ri需要的頻譜數(shù)。構(gòu)造圖G′= ( V′, E ′)的染色模型，（1）對于每一個(gè)結(jié)點(diǎn)v′∈ V ′，有請求集R中的一個(gè)請求 rv和節(jié)點(diǎn)v′相對應(yīng)，即 v ′ ? rv= ( sv, tv, bv)；

（2）對于每一條邊(u, v) ∈ E ′，當(dāng)且僅當(dāng)請求集R中的請求 ru和 rv有公共邊，即 pu∩pv≠φ；

（3）對于圖G′中每一個(gè)節(jié)點(diǎn)v′∈V所帶的權(quán)值w( v′)，有請求集R中的一個(gè)請求 rv所需要的頻譜數(shù)bv與之相對應(yīng)，即 w ( v′) = bv；

RSA問題優(yōu)化目標(biāo)服務(wù)每一個(gè)業(yè)務(wù)請求使網(wǎng)絡(luò)中所有請求使用的頻譜總數(shù)目最少就轉(zhuǎn)化為帶權(quán)圖G′定點(diǎn)染色使使用的顏色數(shù)目最小。

同時(shí)，滿足下面的約束條件：頻譜不相交約束，圖G′中相鄰兩頂點(diǎn)使用不同的顏色數(shù)，為每個(gè)頂點(diǎn)v′∈V分配的色數(shù)區(qū)間為w( v′ ) = [ w, w + bv- 1 ]，即

頻譜連續(xù)性約束，即分配給每一個(gè)頂點(diǎn)v′∈V上色數(shù)區(qū)間 w ( v′ ) = [ w, w + bv- 1 ]是連續(xù)的；

頻譜一致性約束，即每一個(gè)頂點(diǎn)v′∈V染色使用的顏色是不同的；服務(wù)網(wǎng)絡(luò)中所有請求使用的頻譜總數(shù)目最少就等價(jià)于為帶權(quán)圖G′定點(diǎn)染色使使用的顏色數(shù)目最小。

2 設(shè)計(jì)算法

算法1：

輸入：一個(gè)n個(gè)頂點(diǎn)的集合V， V ={vi| (w( vi))}

輸出：頂點(diǎn)集V的染色數(shù)

開始時(shí)，所有頂點(diǎn) vi未被染色，

對vi，1≤i≤n，

對區(qū)間圖頂點(diǎn)度d(vi)按照降序排列，

即 d (v1) ≥ d ( v2)≥ … ≥ d ( vn)，

如果頂點(diǎn) vi色數(shù)區(qū)間與已染色頂點(diǎn)色數(shù)區(qū)間不

相交，

依次按照首次適合方法為頂點(diǎn) vi分配顏色，

結(jié)束

算法2：

輸入：一個(gè)n個(gè)頂點(diǎn)的集合V，V ={vi| (w( vi))}

輸出：頂點(diǎn)集V的染色數(shù)

開始時(shí)，所有頂點(diǎn) vi未被染色，

對vi，1≤i≤n，

對區(qū)間圖頂點(diǎn)度與權(quán)值積大小

{d(vi) × w( vi)}按照降序排列，即d(v1)× w( v1)≥d(v2) × w( v2)≥ … ≥d(vn) × w( vn)

如果頂點(diǎn) vi色數(shù)區(qū)間與已染色頂點(diǎn)色數(shù)區(qū)間不相交，

依次按照首次適合方法為頂點(diǎn) vi分配顏色，

結(jié)束

為了不失一般性，我們采用文獻(xiàn)[6]中的網(wǎng)絡(luò)拓?fù)鋱D作為模型轉(zhuǎn)化的對象，對于更加復(fù)雜的圖同理按照上述算法分析。即將圖1上的頻譜分配問題轉(zhuǎn)化圖染色問題，其中圖 1上請求為 r1= ( 2,3,3)，r2= ( 2,1,4)，r3= ( 1,4,2)，r4= ( 1,2,5)，r5= (1,4,2)，r6= ( 3,2,2)，按照上述算法(1)，轉(zhuǎn)化為求為圖2染色所需的染色數(shù)，其中圖2表示每個(gè)節(jié)點(diǎn)所需要的色數(shù)。在滿足圖染色約束條件下圖2所需染色數(shù)為7，考慮頻譜分配問題有一個(gè)下界，可以認(rèn)為不小于邊 L1上所有請求需要的頻譜總數(shù)，即所求染色數(shù) 7是頻譜分配問題的最優(yōu)解。

圖1 具有五條有向邊的網(wǎng)狀網(wǎng)絡(luò)上SA問題的實(shí)例Fig.1 Instance of the SA problem on a mesh network with five directed links

圖2 對應(yīng)最優(yōu)圖染色問題網(wǎng)絡(luò)Fig.2 Optimal network of the corresponding graph coloring problem

3 總結(jié)

本文通過對網(wǎng)絡(luò)中路由和頻譜分配問題的研究，設(shè)計(jì)了圖染色算法，并應(yīng)用于路由和頻譜分配問題中。在此過程中，首先介紹了路由和頻譜分配問題，它是路由和波長分配問題的一般推廣，為了模型的簡化，證明了路由和頻譜分配問題可以轉(zhuǎn)化為圖染色模型，并且圖染色模型設(shè)計(jì)的算法也可應(yīng)用于路由和頻譜分配問題。本文主要介紹了模型轉(zhuǎn)化及算法設(shè)計(jì)，以后還需對算法進(jìn)行改進(jìn)，完善算法。本文最后提出的算法，可以有效地求解路由和頻譜分配問題，在以后研究可應(yīng)用到彈性光網(wǎng)絡(luò)路由和頻譜分配問題分析中。

[1] BC Chatterjee , N Sarma , E Oki. Routing and Spectrum Allocation in Elastic Optical Networks: A Tutorial[J]. IEEE Communications Surveys & Tutorials, 2015, 17(3): 1776-1800.

[2] T Takagi, H Hasegawa, K Sato, Y Sone. Dynamic routing and frequency slot assignment for elastic optical path networks that adopt distance adaptive modulation[J]. Optical Fiber Communication Conference & Exposition, 2011,19(24): 1-3.

[3] S Talebi, I Katib, GN Rouskas. Distance-adaptive routing and spectrum assignment in rings[J]. Iet Networks, 2016,5(3): 64-70.

[4] Kewei Sha, Aaron Striegel, Min Song. Advances in Computer Communications and Networks: From Green,Mobile, Pervasive Networking to Big Data Computing[M].Netherlands: River Publishers, 2017.

[5] S Talebi, E Bampis, G Lucarelli, I Katib, GN Rouskas.Spectrum Assignment in Optical Networks: A Multiprocessor Scheduling Perspective[J]. IEEE/OSA Journal of Optical Communications & Networking, 2014, 6(8): 754-763.

[6] S Talebi , E Bampis , G Lucarelli , I Katib. On Routing and Spectrum Assignment in Rings[J]. Journal of Lightwave Technology, 2015, 33(1): 151-160.

[7] JC Bermond, FZ Moataz. On Spectrum Assignment in Elastic Optical Tree-Networks[J]. Inria Sophia Antipolis, Univ. Nice Sophia Antipolis, 2015.

[8] H Xuan, Y Wang, Z Xu, S Ha, X Wanga. New optimization model for routing and spectrum assignment with nodes insecurity[J]. Optics Communications, 2017, 389: 42-50.

[9] 趙永利, 張杰, 紀(jì)越峰. 頻譜靈活光網(wǎng)絡(luò)[M]. 北京: 人民郵電出版社, 2013.

[10] 鞠衛(wèi)國. 靈活柵格光網(wǎng)絡(luò)中的頻譜碎片整理與動態(tài)路由算法. [D] 北京: 北京郵電大學(xué), 2013.

[11] 李唱, 焦彥平. 一種基于改進(jìn)蟻群的QoS單播路由算法[J].軟件, 2013, 34(4): 42-45.

[12] 徐加利, 管章玉. 協(xié)作無線網(wǎng)絡(luò)中基于遺傳算法的聯(lián)合中繼選擇與認(rèn)知頻譜接入機(jī)制[J]．新型工業(yè)化, 2014, 4(5):41-47.

[13] 孫健, 張錦南. 頻譜資源利用評價(jià)體系研究[J]. 軟件,2016, 37(02): 17-21.

[14] 馮偉, 別紅霞. 具有擁塞感知w的Mesh 負(fù)載均衡路由策略[J]. 軟件, 2013, 34(1): 56-59.

[15] 夏季文, 馬福昌, 喬學(xué)工. 節(jié)能的無線傳感器網(wǎng)絡(luò)分簇路由算法的研究[J]. 新型工業(yè)化, 2011, 1(8): 56-63.