趙 曦

(91550部隊，遼寧 大連 116023)

互聯(lián)網(wǎng)設(shè)備和業(yè)務(wù)的發(fā)展，不斷豐富著人們的日常與社交生活，卻也帶來了能耗急劇升高的關(guān)鍵問題[1-2]。據(jù)統(tǒng)計和報道，互聯(lián)網(wǎng)能耗占據(jù)了美國總能耗的2%～10%[3]。此外，互聯(lián)網(wǎng)能源效率也極低，為互聯(lián)網(wǎng)的可持續(xù)發(fā)展帶來了挑戰(zhàn)[4]。因此，如何有效減少互聯(lián)網(wǎng)(IP網(wǎng)絡(luò))所需能耗受到了業(yè)界關(guān)注。

開放最短路徑優(yōu)先(OSPF)是IP網(wǎng)絡(luò)中較為常見且使用頻繁的域內(nèi)路由協(xié)議。然而，由于業(yè)務(wù)流量的動態(tài)變化特性，OSPF利用鏈路權(quán)重優(yōu)化流量分布的節(jié)能效果不佳[5-6]。此外，目前的文獻對節(jié)能中業(yè)務(wù)量時間段的劃分標準和方法不清晰，且業(yè)務(wù)量在各時間段切換的拓撲收斂更新時間會降低網(wǎng)絡(luò)性能[7-8]。因此，以動態(tài)變化的流量為依據(jù)，對時間片段進行合理劃分是非常重要的。

針對上述問題，本文基于預(yù)置多拓撲(PMT)技術(shù)設(shè)計了一種互聯(lián)網(wǎng)節(jié)能(ESPMT)算法。該算法先以歷史動態(tài)業(yè)務(wù)量為依據(jù)，對時間進行劃分，并將各時間片中出現(xiàn)的流量峰值輸入到該片段的節(jié)能問題中，從而得到流量最小的冗余和較好的節(jié)能效果。之后，利用鄰域搜索設(shè)計快速啟發(fā)式算法對鏈路權(quán)重進行優(yōu)化，完成節(jié)能子拓撲的設(shè)計，從而實現(xiàn)鏈路容量約束下的單拓撲極限節(jié)能。

1 多拓撲的時間分割設(shè)計

本文基于歷史記錄中各時間段所表現(xiàn)出的流量特征對節(jié)能子拓撲進行設(shè)計，以實現(xiàn)業(yè)務(wù)流量動態(tài)變化下網(wǎng)絡(luò)設(shè)備的工作和休眠調(diào)節(jié)。通常，IP網(wǎng)絡(luò)流量曲線圖在正常工作時會同時呈現(xiàn)波峰和波谷特征(帶寬余量充足)。因此，在某個時間片范圍內(nèi)必定也會出現(xiàn)波峰值與供應(yīng)量恰好相等的情形，劃分的基準點便可選擇該時間片下的波峰[9]。最終流量曲線圖在波峰分割法下被劃分為業(yè)務(wù)量需求上升和下降階段，如圖1所示。從圖中可以看到，該曲線圖按照波峰分割法可被劃分為4個時間片。

圖1 取波峰作為基準點的網(wǎng)絡(luò)流量曲線圖

2 節(jié)能子拓撲算法設(shè)計

由于OSPF協(xié)議下的路由，是以鏈路權(quán)重為依據(jù)通過最短路徑計算而進行的。因此，在節(jié)能路由的相關(guān)設(shè)計中應(yīng)休眠部分鏈路集合(利用率較低)，并轉(zhuǎn)移業(yè)務(wù)流量到其他正常工作的鏈路[10-12]。由此可知，可以借助權(quán)重來調(diào)整網(wǎng)絡(luò)中各鏈路上分布的業(yè)務(wù)流量。如下圖2的網(wǎng)絡(luò)拓撲(7條鏈路和5個節(jié)點，括號左右分別為權(quán)重及業(yè)務(wù)流量)所示。若節(jié)點a向e傳送業(yè)務(wù)(6個單位)，則易知a-c-b-d-e以及a-b-d-e為該網(wǎng)絡(luò)中的最短路徑。此外，從圖中也可以發(fā)現(xiàn)，鏈路權(quán)重越小(大)則流量越大(小)，優(yōu)化鏈路權(quán)重可有效改變網(wǎng)絡(luò)中的流量分布，進而完成節(jié)能的設(shè)計目標。

圖2 拓撲權(quán)重及相應(yīng)業(yè)務(wù)流量分布圖

本文在權(quán)重優(yōu)化的啟發(fā)式算法上選用Fortz設(shè)計的鄰域搜索算法，設(shè)定最大鏈路利用率的最小化為問題的優(yōu)化目標，并調(diào)整權(quán)重搜索方法以實現(xiàn)負載和節(jié)能的均衡[13]。該算法具體為：

(1)權(quán)重向量及其他變量的初始化。其中，搜索面積q和次數(shù)z分別初始化為0；

(2)調(diào)整鏈路權(quán)重，產(chǎn)生新的權(quán)重向量；

(3)令z自加1，若z已累加至搜索次數(shù)，則跳轉(zhuǎn)至步驟(8)；否則跳轉(zhuǎn)至步驟(4)；

(4)利用最短路徑算法計算網(wǎng)絡(luò)中可能存在的最短路徑鏈路(設(shè)定的業(yè)務(wù)工作節(jié)點之間)，從而獲知流量分布情況及開關(guān)狀態(tài)，并依照目標函數(shù)計算該權(quán)重向量作用下的能耗；

(5)評估能耗，若能滿足鏈路容量約束，并能小于目前計算得到的最小能耗，則更新該最小能耗及最優(yōu)權(quán)重向量，使q為0，跳轉(zhuǎn)至步驟(7)；否則跳轉(zhuǎn)至步驟(6)；

(6)令q自加1，若q已累加至搜索面積，則對權(quán)重向量實行擾動操作，并令z自加1，跳轉(zhuǎn)至步驟(7)；否則，跳轉(zhuǎn)至步驟(2)；

(7)判斷搜索次數(shù)是否已經(jīng)達到，若是則跳轉(zhuǎn)至步驟(8)；否則跳轉(zhuǎn)至步驟(2)；

(8)結(jié)束當前算法。

上述算法中的鏈路權(quán)重調(diào)整策略應(yīng)使利用率較低(低于閾值Tlow)或較高(高于閾值Thigh)的鏈路上承擔的工作業(yè)務(wù)盡量向利用率中等的相關(guān)鏈路轉(zhuǎn)移，此時鏈路具有兩級分布特性。因此，也具備較好的節(jié)能效果，并能滿足一定的容量約束。本文取Tlow=0.90，Thigh=0.33，以消除網(wǎng)絡(luò)擁塞并維持一定的網(wǎng)絡(luò)性能。由于算法中的鏈路權(quán)重被初始化為1，增幅單位也為1。因此，鏈路權(quán)重的相應(yīng)增減可具體為

(1)

其中，l，c和l/c分別代表的是鏈路負載、容量和利用率。

3 仿真及分析

結(jié)合仿真在多拓撲的時間片劃分以及節(jié)能子拓撲兩個方面對ESPMT算法進行性能驗證，并與目前存在的其他算法進行對比及分析。

3.1 時間片劃分對比和分析

本算法和等時間片劃分方法在Matlab仿真中的冗余流量變化結(jié)果與對比，如圖3所示。從圖中可以看到，兩種算法的預(yù)估流量均隨時間片數(shù)目的不斷增多而減少。在相同時間片數(shù)目下，ESPMT算法具有更小的冗余流量，與實際情況吻合較好。然而隨著時間片數(shù)目的不斷增加，ESPMT算法在冗余流量上的優(yōu)勢會不斷變小，直至消失。

圖3 本文算法和等時間片劃分方法對比結(jié)果

3.2 節(jié)能子拓撲算法對比和分析

結(jié)合C++仿真，本文對ESPMT算法、基于代數(shù)連通度節(jié)能(ESACON)算法、最小流量(LF)算法和能量感知路由(EAR)算法的節(jié)能效果進行了分析和對比。該仿真拓撲網(wǎng)絡(luò)分別為APARNET(32條鏈路和20個節(jié)點)和USANET網(wǎng)絡(luò)(42條鏈路和24個節(jié)點)，各鏈路均為雙向。此外，鄰域擾動的權(quán)重在1～40范圍內(nèi)隨機產(chǎn)生，搜索次數(shù)和面積分別為3 000和100，并取概率p為0.3以實現(xiàn)權(quán)重向量分量的改變。假設(shè)各鏈路由休眠轉(zhuǎn)變?yōu)殚_啟時具有相同的能耗，故目標函數(shù)可簡化為工作鏈路總數(shù)的最小化。

本算法借助波峰將一天(5:00開始)劃分成6個時間片(分別命名為1～6)，并針對各時間片的業(yè)務(wù)流量峰值進行對應(yīng)的節(jié)能設(shè)計。各節(jié)能算法在兩個網(wǎng)絡(luò)下的能耗對比，如圖4所示。從圖中可知，ESPMT算法具有最優(yōu)的節(jié)能效果；ESACON和EAR算法由于未曾對流量進行考慮，其能耗基本沒有變化；而ESPMT和LF算法能耗與業(yè)務(wù)呈正相關(guān)。由此可知，ESPMT算法由于按照設(shè)定的流量矩陣，對網(wǎng)絡(luò)的拓撲結(jié)構(gòu)進行了確定，并借助權(quán)重調(diào)整產(chǎn)生了最優(yōu)權(quán)重向量。最終趨使整個網(wǎng)絡(luò)的流量向節(jié)能鏈路轉(zhuǎn)移，因此具有良好的節(jié)能效果。

圖4 各算法在不同網(wǎng)絡(luò)中的拓撲能耗對比圖

本文也針對不同的劃分時間片方法(控制時間片個數(shù)為6個)，借助鄰域搜索對各方法所耗的能量進行計算分析和對比。由圖5可知，ESPMT算法對時間片劃分的節(jié)能效果更優(yōu)，且具有更低的能耗?？傮w來看，本文設(shè)計的算法能耗更低且節(jié)能效果更好，滿足了設(shè)計目標和需求。

圖5 不同時間片劃分方法下鄰域搜索的能耗對比

4 結(jié)束語

針對IP網(wǎng)絡(luò)，本文基于預(yù)置多拓撲技術(shù)設(shè)計了一種節(jié)能ESPMT算法。該算法首先利用波峰分割法，對1天進行合理劃分，得到若干個時間片；之后在各時間片中，利用鄰域搜索(啟發(fā)式)的相關(guān)節(jié)能方法和策略設(shè)計子拓撲算法。經(jīng)仿真實驗與測試，證明該算法和其他現(xiàn)有算法相比具有更優(yōu)的節(jié)能效果，為相關(guān)網(wǎng)絡(luò)節(jié)能算法的研究提供了參考。

[1] 張法,Antonio Fernandez Anta,王林,等.網(wǎng)絡(luò)能耗系統(tǒng)模型及能效算法[J].計算機學報,2012,35(3):603-615.

[2] 李偉,張溪.半馬爾科夫鏈的無線傳感網(wǎng)絡(luò)能耗模型的設(shè)計與分析[J].電子設(shè)計工程,2016,24(11):95-98.

[3] 伍元勝,郭兵,沈艷,等.面向核心網(wǎng)的多層網(wǎng)絡(luò)能耗優(yōu)化方法[J].計算機學報,2013,36(7):1538-1548.

[4] 陳曉華.高效節(jié)能虛擬網(wǎng)絡(luò)映射模型與算法研究[D].上海:華東師范大學,2016.

[5] Cianfrani A,Eramo V,Listanti M,et al.An energy saving routing algorithm for a green ospf protocol[C]. Honolulu:INFOCOM IEEE Conference on Computer Communications Workshops,IEEE,2010.

[6] Cuomo W F, Abbagnale A, Cianfrani A, et al. Keeping the connectivity and saving the energy in the internet[C].Anchorage:Computer Communications Workshops,IEEE,2011.

[7] Chiaraviglio L,Mellia M,Neri F.Reducing power consumption in backbone networks[C].Seattle:IEEE International Conference on Communications,IEEE,2009.

[8] Jamakovic A,Uhlig S.On the relationship between the algebraic connectivity and graph’s robustness to node and link failures[C].Phoenix:Eurongi Conference on Next Generation Internet Networks,IEEE,2007.

[9] 王夢菊,吳小龍,石若玉.基于波峰搜索算法的視頻客流計數(shù)系統(tǒng)研究[J].現(xiàn)代交通技術(shù),2015,12(6):76-80.

[10] Moy J.OSPF version 2[M].Indianapolis:RFC Editor Press,1998.

[11] Guerin R A,Orda A,Williams D.QoS routing mechanisms and OSPF extensions[C].Detroit:Global Telecommunications Conference,IEEE,1999.

[12] Moy J.Multicast extensions to OSPF[M]. Indianapolis:RFC Editor Press,1994.

[13] Fortz B,Thorup M.Internet traffic engineering by optimizing OSPF weights[C].Vancouver:Proceedings of IEEE INFOCOM,2000.