業(yè)務(wù)持續(xù)時(shí)間感知的綠色共享通路保護(hù)算法

曹榮超,何榮希

(大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院,遼寧大連 116026)

業(yè)務(wù)持續(xù)時(shí)間感知的綠色共享通路保護(hù)算法

曹榮超,何榮希

(大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院,遼寧大連 116026)

針對IP(互聯(lián)網(wǎng)協(xié)議)over WDM(波分復(fù)用)網(wǎng)絡(luò)的節(jié)能保護(hù)問題,綜合考慮業(yè)務(wù)持續(xù)時(shí)間和利用混合能源供能等因素,提出了一種HTAGSPP(業(yè)務(wù)持續(xù)時(shí)間感知的綠色共享通路保護(hù))算法,鼓勵選擇業(yè)務(wù)持續(xù)時(shí)間內(nèi)需要額外消耗傳統(tǒng)能源最少的路徑建立連接。仿真結(jié)果表明,與傳統(tǒng)節(jié)能共享保護(hù)算法相比,HTAGSPP算法消耗的傳統(tǒng)能源更少且可使用更多的可再生能源,在保持較低阻塞率的同時(shí),降低了業(yè)務(wù)平均傳統(tǒng)能耗和二氧化碳排放量。

IP over WDM網(wǎng)絡(luò);業(yè)務(wù)持續(xù)時(shí)間;可再生能源;共享通路保護(hù);低碳排放

0 引 言

IP(互聯(lián)網(wǎng)協(xié)議)over WDM(波分復(fù)用)網(wǎng)絡(luò)是承載IP業(yè)務(wù)的有效解決方案。隨著IP業(yè)務(wù)量的爆炸式增長,網(wǎng)絡(luò)規(guī)模持續(xù)增大,導(dǎo)致網(wǎng)絡(luò)中能耗不斷增加[1],伴隨著CO2(二氧化碳)等溫室氣體的大量排放,給生態(tài)平衡造成巨大壓力。與此同時(shí),單根光纖已能支持太比特每秒的業(yè)務(wù)速率,任何鏈路或者節(jié)點(diǎn)的故障將導(dǎo)致不可估量的損失[1]。因此,如何在保障網(wǎng)絡(luò)生存性的同時(shí),減少網(wǎng)絡(luò)能耗,降低CO2的排放已成為亟需解決的一個(gè)關(guān)鍵問題。近年來,業(yè)界越來越重視抗毀光網(wǎng)絡(luò)的節(jié)能問題,提出了多種節(jié)能方案[1-2],但其大多針對使用傳統(tǒng)能源供能的光網(wǎng)絡(luò),通過業(yè)務(wù)疏導(dǎo)或休眠等機(jī)制來降低網(wǎng)絡(luò)能耗,很少涉及到可再生能源[3]的使用。為了進(jìn)一步降低網(wǎng)絡(luò)的碳排放量,文獻(xiàn)[4-7]提出了混合使用可再生能源和傳統(tǒng)能源為網(wǎng)絡(luò)供能的路由算法,但并未涉及網(wǎng)絡(luò)的生存性問題。

利用GMPLS(通用多協(xié)議標(biāo)簽交換)協(xié)議和PCE(路徑計(jì)算單元)等可控制和管理光路的動態(tài)建立,從而可以感知業(yè)務(wù)請求和業(yè)務(wù)連接的持續(xù)時(shí)間[8-9]。文獻(xiàn)[8-11]在研究光網(wǎng)絡(luò)的路由機(jī)制時(shí)將業(yè)務(wù)持續(xù)時(shí)間作為一個(gè)重要考慮因素,可以提高網(wǎng)絡(luò)資源利用率。

如何降低CO2排放已成為光網(wǎng)絡(luò)研究中的熱點(diǎn)問題,本文在IP over WDM網(wǎng)絡(luò)已有節(jié)能保護(hù)策略的基礎(chǔ)上,綜合考慮業(yè)務(wù)持續(xù)時(shí)間和利用可再生能源與傳統(tǒng)能源為網(wǎng)絡(luò)供能兩個(gè)因素,基于LG(分層圖)模型[12],提出一種HTAGSPP(業(yè)務(wù)持續(xù)時(shí)間感知的綠色共享通路保護(hù))算法,仿真結(jié)果表明,該算法消耗的傳統(tǒng)能源更少且能使用更多的可再生能源,在保持較低阻塞率的同時(shí),能進(jìn)一步降低業(yè)務(wù)平均傳統(tǒng)能耗和CO2排放。

1 網(wǎng)絡(luò)模型

IP over WDM網(wǎng)絡(luò)可以分為IP層和WDM光層,如圖1所示[5]。IP層用來承載業(yè)務(wù),節(jié)點(diǎn)的核心設(shè)備是路由器,路由器向下連接到對應(yīng)的光交換節(jié)點(diǎn)。WDM光層節(jié)點(diǎn)的主要設(shè)備為OXC(光交叉連接器),節(jié)點(diǎn)之間用光纖鏈路連接。光收發(fā)器用來

連接光層和IP層,實(shí)現(xiàn)業(yè)務(wù)的光/電轉(zhuǎn)換。在長距離傳輸時(shí),為了保證信號的可靠傳輸,需要利用放大器放大信號。網(wǎng)絡(luò)中主要的耗能器件有OXC、路由器端口、光收發(fā)器和光放大器。光放大器分為前置放大器、后置放大器和中繼放大器。OXC、光收發(fā)器和放大器是激活器件,能耗是一個(gè)固定值,不隨業(yè)務(wù)大小的變化而變化。如果器件已經(jīng)處于開啟狀態(tài),則后續(xù)業(yè)務(wù)經(jīng)過此器件不再需要額外消耗能量。

圖1 IP over WDM網(wǎng)絡(luò)模型

網(wǎng)絡(luò)物理拓?fù)淇杀硎緸镚(N,L,F,W),其中,N為節(jié)點(diǎn)集,L為雙向鏈路集,F為每條物理鏈路上的光纖集,W為每條光纖上的波長集。|N|和|L|分別表示網(wǎng)絡(luò)拓?fù)渲械墓?jié)點(diǎn)數(shù)目和鏈路數(shù)目,|F|表示鏈路上的光纖數(shù)目,|W|表示每條光纖上的波長數(shù)目。假設(shè):(1)每條鏈路都由一對方向相反的單向光纖組成,每條光纖的可用波長數(shù)為|W|,即支持的波長集為{λ1,λ2,…,λ|W|}。(2)網(wǎng)絡(luò)中所有節(jié)點(diǎn)都不具備波長變換能力,但支持業(yè)務(wù)疏導(dǎo)。(3)業(yè)務(wù)連接請求r(s,d,t,th,b)均為雙向業(yè)務(wù),其中,s、d代表源、宿節(jié)點(diǎn);t為業(yè)務(wù)請求到達(dá)時(shí)間;th為業(yè)務(wù)持續(xù)時(shí)間;b為業(yè)務(wù)的帶寬需求。所有業(yè)務(wù)請求的源、宿節(jié)點(diǎn)在所有節(jié)點(diǎn)中隨機(jī)選取,而且一對節(jié)點(diǎn)之間可能同時(shí)存在多個(gè)業(yè)務(wù)請求。(4)對于每一個(gè)到達(dá)的業(yè)務(wù)請求,都要為其建立連接(一對鏈路分離的工作路徑和保護(hù)路徑)。如果建立連接失敗,則拒絕該業(yè)務(wù)請求并丟棄該業(yè)務(wù)。(5)為了保持每個(gè)業(yè)務(wù)的獨(dú)立性,業(yè)務(wù)不允許分拆成幾部分在不同路徑中傳輸。(6)網(wǎng)絡(luò)中節(jié)點(diǎn)采用混合能源(可再生能源和傳統(tǒng)能源)供能,如果可再生能源(本文僅考慮太陽能)的輸出不足以滿足其能量需求,則需補(bǔ)充傳統(tǒng)能源供能。(7)考慮到太陽能存儲的效率和代價(jià)等因素,本文采用即產(chǎn)即用策略,也就是不考慮將可再生能源存儲使用。

LG模型將物理拓?fù)銰轉(zhuǎn)化為|W|個(gè)互不相鄰的子圖,每個(gè)子圖分別對應(yīng)一個(gè)特定的波長λi(i=1,2,3…,|W|),稱為WP(波長平面)[12]。G中節(jié)點(diǎn)i和節(jié)點(diǎn)j之間存在鏈路lij∈L,那么該鏈路的光纖上每一個(gè)波長就稱為一個(gè)波長信道,波長信道是雙向的。G中的每個(gè)節(jié)點(diǎn)nj∈N(j=1,2,3…,|N|),在LG中都被復(fù)制|W|次,對應(yīng)|W|個(gè)WP的節(jié)點(diǎn)nkj(k=1,2,3…,|W|),即在第k個(gè)WP上的節(jié)點(diǎn)j。

利用LG模型來解決IP over WDM網(wǎng)絡(luò)的RWA(路由和波長分配)問題時(shí),將涉及波長鏈路和虛鏈路[12]。波長鏈路liab∈L表示波長平面λi上節(jié)點(diǎn)a和節(jié)點(diǎn)b之間鏈路,也就是物理拓?fù)銰上節(jié)點(diǎn)a和節(jié)點(diǎn)b之間光纖對上的波長λi對應(yīng)的波長信道。虛鏈路viab表示G中在節(jié)點(diǎn)a和節(jié)點(diǎn)b之間建立了一條光路,該光路使用波長λi,虛鏈路可以看作網(wǎng)絡(luò)在IP層上的邏輯鏈路。由于建立一條虛鏈路viab要占用WDM光層上節(jié)點(diǎn)間的波長信道,因此應(yīng)去掉LG中相應(yīng)WP上該虛鏈路對應(yīng)的波長鏈路。

2 網(wǎng)絡(luò)能耗分析

在分析網(wǎng)絡(luò)能耗之前,引入以下變量和符號:i表示物理拓?fù)銰中的節(jié)點(diǎn);lij表示G中節(jié)點(diǎn)i和j之間的雙向鏈路;表示波長平面λk上節(jié)點(diǎn)i和j之間波長鏈路;pw、pb表示為業(yè)務(wù)請求建立的工作和保護(hù)路徑;Pi表示節(jié)點(diǎn)i上的能耗;Prouter表示每個(gè)路由器端口(每建一個(gè)業(yè)務(wù)連接將占用一個(gè)端口)的能耗;POXC、Ptrans分別表示OXC和光收發(fā)機(jī)的能耗;fi(t)表示節(jié)點(diǎn)i所在區(qū)域太陽能供給量曲線; dij表示鏈路lij的物理距離;Ppath表示為業(yè)務(wù)請求建立連接時(shí)額外消耗的能量;PES表示每次電交換所需的能量;Pb表示電交換每Gbit/s業(yè)務(wù)所需的能耗;Pamp表示鏈路上每個(gè)放大器的能耗;dspan表示每兩個(gè)放大器之間的物理距離,設(shè)為80 km;Plij表示鏈路lij的能耗;表示鏈路lij在時(shí)間[t,t+th]內(nèi)額外消耗的傳統(tǒng)能源;表示鏈路的代價(jià)值;表示鏈路的代價(jià)函數(shù),它取決于鏈路的資源利用情況、能耗情況以及業(yè)務(wù)連接請求的帶寬需求b等因素;W、B、F分別表示已建業(yè)務(wù)連接工作路徑所經(jīng)鏈路構(gòu)成的集合、保護(hù)路徑所經(jīng)鏈路構(gòu)成的集合和空閑鏈路構(gòu)成的集合;分別表示鏈路上工作路徑占用帶寬、保護(hù)路徑占用帶寬、剩余帶寬和總帶寬,且滿足(t,th)表示節(jié)點(diǎn)i需要額外消耗的傳統(tǒng)能源。

在LG模型中,業(yè)務(wù)連接的工作路徑可以建立在虛鏈路上,也可以建立在波長鏈路上,還可以同時(shí)使用虛鏈路和波長鏈路來建立連接。由于空閑資源和只被保護(hù)路徑使用的資源可以休眠,因此業(yè)務(wù)連接所需能耗取決于工作路徑的能耗。可以使用以下

4種策略來建立工作路徑:

(1)在源、宿節(jié)點(diǎn)之間新建一條虛鏈路。此時(shí)需要新開啟網(wǎng)絡(luò)器件,因此虛鏈路上的器件需要耗能。該虛鏈路經(jīng)節(jié)點(diǎn)i需要的能耗Pi為

每一次電交換所需的能量和業(yè)務(wù)的大小有關(guān),當(dāng)業(yè)務(wù)較大時(shí)能耗也相應(yīng)的增大,具體關(guān)系為

新建虛鏈路時(shí),鏈路上的能耗來自放大器的能量消耗。每根光纖鏈路上包含一個(gè)前置放大器、一個(gè)后置放大器和一定數(shù)量的摻餌光纖放大器,假設(shè)它們消耗的能量相同,則鏈路lij上的能耗Plij為

(2)利用源、宿節(jié)點(diǎn)之間多個(gè)已建虛鏈路的級聯(lián)。此方式無需額外開啟新的網(wǎng)絡(luò)器件,但是當(dāng)業(yè)務(wù)從一個(gè)虛鏈路切換到另一個(gè)虛鏈路時(shí),在中間節(jié)點(diǎn)要多進(jìn)行一次電交換。此時(shí)建立一個(gè)從源到宿節(jié)點(diǎn)的連接額外所需的能耗來自節(jié)點(diǎn)的能耗,鏈路上放大器無需額外耗能。對于已建虛鏈路上的節(jié)點(diǎn)i,額外的能耗Pi為

(3)利用直接連接源、宿節(jié)點(diǎn)的已建虛鏈路。在此方式下,網(wǎng)絡(luò)中光收發(fā)器、OXC、放大器無需額外耗能,僅在源、宿節(jié)點(diǎn)需要額外耗能Pi,表示為

(4)利用源、宿節(jié)點(diǎn)間已建的和新建的虛鏈路。此時(shí),已建虛鏈路上光收發(fā)器、OXC、放大器無需額外耗能,新建虛鏈路上器件都需開啟,此策略的能耗可依據(jù)具體情況由式(1)～(4)計(jì)算得出。

本文基于以上4種策略,在選路過程中綜合考慮虛鏈路和波長鏈路,選擇業(yè)務(wù)持續(xù)時(shí)間內(nèi)額外消耗傳統(tǒng)能源最少的路徑來建立工作路徑?？紤]到可以休眠保護(hù)路徑上的資源,因此建立業(yè)務(wù)連接所需能耗為

3 HTAGSPP算法

HTAGSPP算法主要目的是盡可能減少網(wǎng)絡(luò)中傳統(tǒng)能源的消耗,降低CO2排放。主要思想是選擇業(yè)務(wù)持續(xù)時(shí)間內(nèi)額外消耗傳統(tǒng)能源最少的路徑建立連接,在選路過程中盡可能將工作路徑和保護(hù)路徑匯集在不同光纖,也就是將工作路徑盡可能匯集在處于激活的光纖上,而保護(hù)路徑盡可能匯集在處于休眠的光纖上,從而使無工作路徑經(jīng)過的資源進(jìn)入休眠狀態(tài)以節(jié)能。當(dāng)工作鏈路發(fā)生故障時(shí),對應(yīng)的保護(hù)路徑迅速從休眠狀態(tài)切換到激活狀態(tài)。

網(wǎng)絡(luò)中可以利用可再生能源(太陽能)為節(jié)點(diǎn)上的路由器端口、光收發(fā)器和OXC供能;光纖鏈路上的放大器只使用傳統(tǒng)能源供能。經(jīng)過統(tǒng)計(jì),可以得出節(jié)點(diǎn)所在區(qū)域不同時(shí)間的太陽能輸出情況(用供能曲線fi(t)表示),一天中從日出開始到日落之前都有太陽能輸出,輸出量開始逐漸增加,達(dá)到最大值后逐漸減少。當(dāng)節(jié)點(diǎn)的能耗大于可再生能源供能量時(shí),需要補(bǔ)充傳統(tǒng)能源為其供能;當(dāng)節(jié)點(diǎn)的能耗低于可再生能源供能量時(shí),則只需用可再生能源供能,而無需額外消耗傳統(tǒng)能源。

為業(yè)務(wù)連接請求r(s,d,t,th,b)建立工作路徑時(shí),依據(jù)區(qū)間[t,t+th]上節(jié)點(diǎn)i的能耗Pi和節(jié)點(diǎn)處太陽能供能曲線fi(t),可求出節(jié)點(diǎn)上需要額外消耗的傳統(tǒng)能源值。Pi與fi(t)的相交情況有不相交、一個(gè)交點(diǎn)和兩個(gè)交點(diǎn)3種。假設(shè)Pi與fi(t)交點(diǎn)個(gè)數(shù)為m,則有:

(1)當(dāng)m=0時(shí),結(jié)果如圖2所示。

圖2 交點(diǎn)個(gè)數(shù)為0

由圖2(a)可看出,在業(yè)務(wù)持續(xù)時(shí)間內(nèi)太陽能能夠滿足節(jié)點(diǎn)的能耗需求,無需額外消耗傳統(tǒng)能源。此時(shí),節(jié)點(diǎn)i在業(yè)務(wù)持續(xù)時(shí)間內(nèi)需要額外增加的傳統(tǒng)能耗值(t,th)=0。

由圖2(b)可看出,此時(shí)在業(yè)務(wù)持續(xù)時(shí)間內(nèi)太陽能無法滿足節(jié)點(diǎn)的能耗需求,需要消耗的傳統(tǒng)能源為圖中陰影部分面積。因此節(jié)點(diǎn)i上額外消耗的傳統(tǒng)能源值為

(2)當(dāng)m=1時(shí),結(jié)果如圖3所示。

由圖3(a)可看出,節(jié)點(diǎn)i在業(yè)務(wù)持續(xù)時(shí)間內(nèi)需要額外消耗的傳統(tǒng)能源為圖中陰影面積,即

圖3 交點(diǎn)個(gè)數(shù)為1

由圖3(b)可看出,節(jié)點(diǎn)i在業(yè)務(wù)持續(xù)時(shí)間內(nèi)需要額外消耗的傳統(tǒng)能源為圖中陰影面積,即

由圖3(c)可看出,節(jié)點(diǎn)i在業(yè)務(wù)持續(xù)時(shí)間內(nèi)需要額外消耗的傳統(tǒng)能源為圖中陰影面積,即

(3)當(dāng)m=2時(shí),結(jié)果如圖4所示。

圖4 交點(diǎn)個(gè)數(shù)為2

從圖4可以看出,節(jié)點(diǎn)i在業(yè)務(wù)持續(xù)時(shí)間內(nèi)需要額外消耗的傳統(tǒng)能源為圖中陰影部分的面積,即

對于業(yè)務(wù)連接請求r(s,d,t,th,b),需要為其尋找一條工作路徑和一條保護(hù)路徑,二者鏈路分離。尋找工作路徑時(shí),首先將物理拓?fù)銰轉(zhuǎn)化為|W|個(gè)WP,由于WP上并非所有的鏈路都滿足帶寬需求,因此將WP上剩余帶寬不滿足業(yè)務(wù)帶寬需求的鏈路(虛鏈路和波長鏈路)刪除。尋找工作路徑時(shí),鏈路權(quán)值設(shè)定為

HTAGSPP算法在WP上進(jìn)行選路時(shí)會盡量減少傳統(tǒng)能源消耗量,因此由鏈路狀態(tài)和承載該業(yè)務(wù)時(shí)鏈路lij及其端節(jié)點(diǎn)上需要額外消耗的傳統(tǒng)能源決定。由于在WP中鏈路分為波長鏈路和虛鏈路，可分兩種情況求出:

(1)當(dāng)鏈路為波長鏈路時(shí),鏈路上放大器及其端節(jié)點(diǎn)上額外需要消耗的傳統(tǒng)能源為

(2)當(dāng)鏈路為虛鏈路時(shí),鏈路端節(jié)點(diǎn)上額外需要消耗的傳統(tǒng)能耗為

從而,可定義

式中,γ1和γ2為常數(shù)因子,用來調(diào)節(jié)鏈路工作狀態(tài)對鏈路權(quán)值的影響。為了鼓勵將工作路徑和保護(hù)路徑分別集中在不同光纖上,使更多資源進(jìn)入休眠狀態(tài),在建立工作路徑時(shí)應(yīng)優(yōu)先選擇只存在工作路徑的鏈路,然后選擇既有工作路徑又有保護(hù)路徑的鏈路,其次選擇空閑鏈路,最后才選擇只存在保護(hù)路徑的鏈路。因此,設(shè)置0＜γ1＜γ2＜1。

為工作路徑pw尋找對應(yīng)的保護(hù)路徑時(shí),鏈路權(quán)值設(shè)定為

其中,

式中,ε1為無限接近0的一個(gè)常數(shù);ε2為常數(shù),取值范圍為0＜ε2＜1。與工作路徑不同,保護(hù)路徑在選路時(shí)優(yōu)先選擇只存在保護(hù)路徑的鏈路,然后選擇處于空閑的鏈路,其次選擇既有工作路徑又有保護(hù)路徑的鏈路,最后才選擇只存在工作路徑的鏈路來建立連接。β(β＞0)為共享因子,用于調(diào)節(jié)鏈路上保護(hù)帶寬的使用情況對鏈路權(quán)值的影響,γ()與鏈路中帶寬資源有關(guān),用來控制選路的優(yōu)先順序,可定義為[12]

HTAGSPP算法的具體步驟如下:

步驟(1):初始化網(wǎng)絡(luò)資源,將給定網(wǎng)絡(luò)物理拓?fù)銰(N,L,F,W)轉(zhuǎn)化成LG模型,并輸入各節(jié)點(diǎn)處的太陽能曲線fi(t),i∈N。

步驟(2):等待業(yè)務(wù)請求r(s,d,t,th,b)到達(dá):如果是業(yè)務(wù)連接請求,則轉(zhuǎn)至步驟(3);如果是業(yè)務(wù)釋放請求,則轉(zhuǎn)至步驟(6)。

步驟(3):為業(yè)務(wù)連接找尋工作路徑。根據(jù)到達(dá)業(yè)務(wù)請求b和LG上鏈路狀態(tài)情況,按照式(12)～(15)計(jì)算各個(gè)WP上的波長鏈路和虛鏈路的代價(jià)函數(shù)值,并利用Dijkstra算法在|W|個(gè)WP上尋找各自的最短路徑pi,要求0＜C(pi)＜+∞:如果一條最短路徑都沒有找到,則拒絕該業(yè)務(wù)建立請求,并轉(zhuǎn)至步驟(2);如果找到v(0＜v≤|W|)條工作路徑pi(i=1,2,3,…,v),則從中選擇代價(jià)最小的工作路徑pw(假設(shè)該路徑位于波長平面λk),暫時(shí)記錄該工作路徑的信息,轉(zhuǎn)向步驟(4)。

步驟(4):為業(yè)務(wù)連接找尋保護(hù)路徑。根據(jù)式(16)～(18)調(diào)整波長平面λk上鏈路權(quán)值,然后在該WP利用Dijkstra算法為pw尋找相應(yīng)保護(hù)路徑pb,要求0＜C(pb)＜+∞:如果沒找到,則刪除臨時(shí)記錄的工作路徑pw的信息,拒絕當(dāng)前業(yè)務(wù)連接請求,轉(zhuǎn)到步驟(2);如果找到符合要求的保護(hù)路徑pb,則詳細(xì)記錄其信息,轉(zhuǎn)向步驟(5)。

步驟(5):在找到的工作路徑pw上建立連接,同時(shí)在保護(hù)路徑上預(yù)留相應(yīng)的保護(hù)帶寬。對于工作路徑和保護(hù)路徑中新建的光路,相應(yīng)地在LG中增加一條虛鏈路,并刪除相應(yīng)WP上該虛鏈路所經(jīng)過節(jié)點(diǎn)對間的波長鏈路,修改波長平面λk上相應(yīng)鏈路的剩余帶寬;統(tǒng)計(jì)業(yè)務(wù)的到達(dá)總數(shù)和建立該連接額外消耗的能量,轉(zhuǎn)到步驟(2)。

步驟(6):釋放該業(yè)務(wù)連接,更新它所對應(yīng)的工作路徑和保護(hù)路徑所經(jīng)鏈路的剩余帶寬值以及鏈路和節(jié)點(diǎn)的狀態(tài)信息;如果某條虛鏈路上剩余帶寬達(dá)到波長容量,則釋放該條虛鏈路,將它還原為相應(yīng)節(jié)點(diǎn)對間的波長鏈路,轉(zhuǎn)到步驟(2)。

由于在N個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)中運(yùn)行Dijkstra算法的復(fù)雜度為O(|N|2),而光纖中可用的波長數(shù)為|W|,因此需要在|W|個(gè)WP上找出各自的最短路徑,執(zhí)行Dijkstra算法的次數(shù)為|W|次,然后在找到工作路徑的WP上找到一條保護(hù)路徑,此時(shí)執(zhí)行1次Dijkstra算法,上述過程中Dijkstra算法執(zhí)行次數(shù)為|W|+1次,因此,HTAGSPP算法的復(fù)雜度近似為O((|W|+1)|N|2)。

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

仿真拓?fù)洳捎肗SFNET(美國國家科學(xué)基金網(wǎng)絡(luò)),按照地理位置的不同可將它分為4個(gè)時(shí)間區(qū)域,每個(gè)相鄰時(shí)間區(qū)域相差一個(gè)小時(shí),將東部時(shí)間區(qū)域作為標(biāo)準(zhǔn)時(shí)間[5]。不同時(shí)間區(qū)域的日落時(shí)間不同,因此在同一時(shí)間,不同區(qū)域的節(jié)點(diǎn)得到的太陽能能量不同。一天中不同時(shí)刻、不同節(jié)點(diǎn)處太陽能供能曲線fi(t)采用文獻(xiàn)[5]的統(tǒng)計(jì)數(shù)據(jù)。

算法性能評價(jià)指標(biāo)包括阻塞率、業(yè)務(wù)連接平均傳統(tǒng)能耗、業(yè)務(wù)連接平均可再生能耗和CO2排放量。阻塞率指被拒絕的業(yè)務(wù)連接請求數(shù)與總的業(yè)務(wù)請求數(shù)之比。阻塞率越小,說明成功建立連接的業(yè)務(wù)量越多,算法的性能就越好。業(yè)務(wù)連接平均傳統(tǒng)能耗定義為所有成功建立業(yè)務(wù)的傳統(tǒng)能耗值和成功建立連接的業(yè)務(wù)數(shù)S的比值,其值越小,說明算法的綠色節(jié)能效果越明顯。業(yè)務(wù)連接平均可再生能耗定義為所有成功建立接連業(yè)務(wù)的可再生能源的總消耗量和S的比值,其值越大,說明算法使用了更多的可再生能源。

第k個(gè)成功建立連接的業(yè)務(wù)在持續(xù)時(shí)間[t,t+ th]內(nèi)網(wǎng)絡(luò)中CO2排放量為[6]

式中,P′i為節(jié)點(diǎn)i上傳統(tǒng)能源的能耗;P′l為鏈路l上傳統(tǒng)能源的能耗;εi和εl為節(jié)點(diǎn)和鏈路上CO2排放系數(shù)。仿真中εi=εl=0.998 kg/k Wh[4]。從而可求出成功建立連接數(shù)為S時(shí)總的CO2排放量為

本文采用動態(tài)業(yè)務(wù)仿真模型,所有的業(yè)務(wù)請求按平均速率服從參數(shù)為λ的泊松分布到達(dá)網(wǎng)絡(luò),業(yè)務(wù)連接的持續(xù)時(shí)間服從均值為1/μ的指數(shù)分布,即全網(wǎng)的總負(fù)載為λ/μErl。每根光纖支持的波長數(shù)為4,波長容量OC(光載波)-192。業(yè)務(wù)的帶寬需求從OC-1、OC-2、OC-12、OC-48和OC-192中隨機(jī)選取。仿真中設(shè)置γ1=0.25,γ2=0.5,ε1=10―4,ε2= 0.25,β=5,Prouter=1 k W,POXC=85 W,Ptrans= 73 W,Pamp=8 W,Pb=67.5 W/10 Gbps[5]。在對網(wǎng)絡(luò)進(jìn)行保護(hù)時(shí),僅考慮應(yīng)對單鏈路失效。業(yè)務(wù)的

仿真時(shí)間為1天,所得結(jié)果為模擬105次業(yè)務(wù)請求后經(jīng)統(tǒng)計(jì)得出。

為了評估HTAGSPP算法的性能,將其與EASPP(節(jié)能共享保護(hù))算法[9]和Non-HTAGSPP(不考慮業(yè)務(wù)持續(xù)時(shí)間的HTAGSPP)算法進(jìn)行對比。EA-SPP算法在選路過程中不考慮業(yè)務(wù)持續(xù)時(shí)間和使用可再生能源,選擇能耗最低路徑建立連接; Non-HTAGSPP算法僅考慮利用可再生能源為網(wǎng)絡(luò)供能,在業(yè)務(wù)到達(dá)時(shí)選擇網(wǎng)絡(luò)中可再生能源供能最大的路徑建立連接。

圖5所示為3種算法的阻塞率性能對比圖。由圖可以看出,3種算法的阻塞率隨網(wǎng)絡(luò)負(fù)載的增加而逐漸增大,而且EA-SPP具有最小的阻塞率,HTAGSPP的阻塞率介于EA-SPP和Non-HTAGSPP之間。這是由于在業(yè)務(wù)負(fù)載較小時(shí),網(wǎng)絡(luò)中可用帶寬資源豐富,3種算法能夠成功建立的連接數(shù)較多,阻塞率較小。隨著網(wǎng)絡(luò)負(fù)載增大,單位時(shí)間內(nèi)到達(dá)業(yè)務(wù)數(shù)增加,網(wǎng)絡(luò)中可用的帶寬資源逐漸減少,導(dǎo)致成功建立連接的業(yè)務(wù)數(shù)減少,阻塞率逐漸變大。由于EA-SPP選擇網(wǎng)絡(luò)中能耗最低的路徑建立連接,有利于選擇源、宿節(jié)點(diǎn)間的最短路徑建立連接,占用帶寬資源較少,因此阻塞率較低;而Non-HTAGSPP和HTAGSPP兩種算法考慮可再生能源這個(gè)因素,為了多利用網(wǎng)絡(luò)中的可再生能源,所選路徑可能較長,占用帶寬資源較多,因此阻塞率較高。另外,Non-HTAGSPP算法當(dāng)業(yè)務(wù)到達(dá)時(shí)選擇可再生能源供能最大的路徑建立連接,潛在地會導(dǎo)致業(yè)務(wù)集中在經(jīng)過這些節(jié)點(diǎn)的路徑上,使這些路徑所經(jīng)鏈路的帶寬資源過快耗光,從而導(dǎo)致后續(xù)業(yè)務(wù)請求易發(fā)生阻塞,因此阻塞率要高于HTAGSPP。

圖5 不同負(fù)載下的阻塞率性能

圖6 所示為3種算法的業(yè)務(wù)連接平均傳統(tǒng)能耗對比圖。由圖可以看出,隨著業(yè)務(wù)負(fù)載的增大,3種算法的業(yè)務(wù)平均傳統(tǒng)能耗逐漸降低,HTAGSPP和 Non-HTAGSPP算法業(yè)務(wù)連接平均傳統(tǒng)能耗明顯小于EA-SPP算法,HTAGSPP的業(yè)務(wù)連接平均傳統(tǒng)能耗最低。主要原因在于隨著業(yè)務(wù)負(fù)載增大,網(wǎng)絡(luò)中已激活器件增多,此時(shí)為業(yè)務(wù)建立連接時(shí)可使用更多已激活器件,而無需額外產(chǎn)生能耗,業(yè)務(wù)連接平均能耗降低,相應(yīng)地業(yè)務(wù)連接平均傳統(tǒng)能耗也隨之降低。其次,HTAGSPP和Non-HTAGSPP算法在選路時(shí)鼓勵使用可再生能源為網(wǎng)絡(luò)供能,因此兩種算法的業(yè)務(wù)平均傳統(tǒng)能耗低于EA-SPP。另外,HTAGSPP選擇業(yè)務(wù)持續(xù)時(shí)間內(nèi)額外消耗傳統(tǒng)能源最少的路徑建立連接,能夠更加有效地利用可再生能源,減少對傳統(tǒng)能源的消耗,因此其業(yè)務(wù)連接平均傳統(tǒng)能耗最低。

圖6 不同負(fù)載下的業(yè)務(wù)連接平均傳統(tǒng)能耗

3種算法的業(yè)務(wù)連接平均可再生能耗仿真結(jié)果如圖7所示。由圖可知,隨著網(wǎng)絡(luò)負(fù)載增大,平均可再生能耗逐漸降低,HTAGSPP和Non-HTAGSPP算法業(yè)務(wù)平均可再生能耗都大于EA-SPP算法,HTAGSPP具有最大的業(yè)務(wù)平均可再生能耗值。原因在于:隨著業(yè)務(wù)負(fù)載增大,網(wǎng)絡(luò)中處于激活的器件增多,可使用更多已激活器件為業(yè)務(wù)建立連接,減少額外耗能量,因此,3種算法的業(yè)務(wù)連接平均能耗降低,可再生能源的能耗相應(yīng)降低。在一定網(wǎng)絡(luò)負(fù)載下,HTAGSPP和Non-HTAGSPP算法在選路過程中都考慮利用可再生能源供能,算法對可再生能源的利用高于EA-SPP,業(yè)務(wù)連接的平均可再生能耗高于EA-SPP。其次,與Non-HTAGSPP算法相比,HTAGSPP算法能夠更充分地利用可再生能源,減少對傳統(tǒng)能源的使用。因此,其業(yè)務(wù)平均可再生能耗最高。

圖7 不同負(fù)載下的業(yè)務(wù)連接平均可再生能耗

圖8所示為3種算法的CO2排放量對比圖。由圖可知,隨著網(wǎng)絡(luò)負(fù)載增大,3種算法的CO2排放量不斷減少。EA-SPP算法的CO2排放量高于HTAGSSP和Non-HTAGSPP算法,而且HTAGSSP的CO2排放量最低。正如上文所述,當(dāng)網(wǎng)絡(luò)負(fù)載逐漸增加時(shí),業(yè)務(wù)連接的平均能耗以及平均傳統(tǒng)能耗都逐漸降低,加之成功建立連接的業(yè)務(wù)數(shù)也不斷減少,因此,總的CO2排放量不斷減少。其次,EA-SPP算法在選路時(shí)沒有考慮利用可再生能源供能,導(dǎo)致業(yè)務(wù)傳統(tǒng)能源消耗過多,算法的CO2排放量最高。另外,HTAGSSP算法考慮了業(yè)務(wù)的持續(xù)時(shí)間,業(yè)務(wù)連接的平均傳統(tǒng)能耗和平均可再生能耗指標(biāo)均優(yōu)于Non-HTAGSSP。因此HTAGSPP算法在CO2排放方面優(yōu)于其他兩種算法。

圖8 不同負(fù)載下的CO2排放量

5 結(jié)束語

研究了IP over WDM網(wǎng)絡(luò)中考慮節(jié)能的生存性問題,基于LG模型,提出了一種HTAGSPP算法。該算法鼓勵選擇在業(yè)務(wù)持續(xù)時(shí)間內(nèi)額外消耗傳統(tǒng)能源最少的路徑建立連接,在提高保護(hù)資源利用率的同時(shí),盡量使用已激活器件建立工作路徑,而選擇保護(hù)路徑時(shí)盡可能選擇處于休眠狀態(tài)的資源。所提算法有利于更多的使用可再生能源,以略高的阻塞率為代價(jià),有效地降低了業(yè)務(wù)平均傳統(tǒng)能耗和CO2的排放,實(shí)現(xiàn)了網(wǎng)絡(luò)綠色節(jié)能的目的。

[1]王汝言,馬禮東,張超,等.IP over WDM網(wǎng)絡(luò)中能耗自感知的混合疏導(dǎo)專有保護(hù)算法[J].光電子·激光,2014,9(25):1701―1708.

[2]He R,Lin B.Dynamic power-aware shared path protection algorithms in WDM mesh networks[J].Journal of Communications,2013,8(1):55―65.

[3]國家發(fā)展和改革委員會.可再生能源中長期發(fā)展規(guī)劃[J].可再生能源,2007,25(5):1―5.

[4]Ricciardi S,Wang J,Palmieri F,et al.Eco-sustainable routing in optical networks[J].Photonic Network Communications,2013,26(2-3):140―149.

[5]Dong X,El Gorashi T,Elmirghani J M H.IP over WDM networks employing renewable energy sources [J].Journal of Lightwave Technology,2011,29(1): 3―14.

[6]Schondienst T,Vokkarane V M.Renewable energy-aware grooming in IP-over-WDM networks[C]//ICNC 2014.Honolulu,US:IEEE,2014:163―167.

[7]Gattulli M,Tornatore M,Fiandra R,et al.Low-carbon routing algorithms for cloud computing services in IP over WDM networks[C]//ICC 2012.Ottawa,Canada:IEEE,2012:2999―3003.

[8]Xu Z,Huang J,Zhou Z,et al.A novel grooming algorithm with the adaptive weight and load balancing for dynamic holding-time-aware traffic in optical networks [J].Optical Fiber Technology,2013,19(5):392―399.

[9]熊余,馬禮冬,王汝言.帶有業(yè)務(wù)持續(xù)時(shí)間感知的節(jié)能共享保護(hù)[J].華中科技大學(xué)學(xué)報(bào):自然科學(xué)版,2014,42(10):25―30.

[10]Tornatore M,Zhu H,Mukherjee B,et al.Holdingtime-aware dynamic traffic grooming[J].IEEE Journal on Selected Areas in Communication,2008,26(3): 28―35.

[11]劉煥淋,劉洋,陳勇,等.WDM光網(wǎng)絡(luò)中帶寬預(yù)留型業(yè)務(wù)的時(shí)間感知綠色疏導(dǎo)算法[J].北京郵電大學(xué)學(xué)報(bào),2014,55(05):71―74.

[12]何榮希,張治中,王光興,等.IP/MPLS over WDM網(wǎng)中基于共享風(fēng)險(xiǎn)鏈路組限制的共享通路保護(hù)算法[J].電子學(xué)報(bào),2002,30(11):1638―1642.

Holding-Time-Aware Green Shared Path Protection Algorithm

CAO Rong-chao,HE Rong-xi
(College of Information Science and Technology,Dalian Maritime University,Dalian 116026,China)

In order to solve the issue of energy-saving protection in IP over WDM networks,a Hold-Time-Aware Green Shared Path Protection(HTAGSPP)algorithm is proposed.The algorithm also considers the issues of holding-time of traffic and use of renewable energy.It encourages choosing the path with the least additional traditional energy consumption during the holding-time of traffic.The simulation results show that our proposed algorithm can not only maintain a low blocking probability and use renewable energy effectively,but also reduce traditional energy consumption and carbon emissions by using more renewable energy,when comparing with other traditional energy-saving shared path protection algorithms.

IP over WDM network;hold-time of traffic;renewable energy;shared path protection;low carbon emissions

TN913.24

A

1005-8788(2016)06-0009-07

10.13756/j.gtxyj.2016.06.003

2016-06-23

國家自然科學(xué)基金資助項(xiàng)目(61371091);大連海事大學(xué)“十三五”重點(diǎn)科研資助項(xiàng)目(3132016318)

曹榮超(1991―),男,山東臨沂人。碩士研究生,主要研究方向?yàn)楣饩W(wǎng)絡(luò)。

何榮希,教授。Email:hrx@dlmu.edu.cn