一種有線網(wǎng)絡(luò)中高效節(jié)能的拓?fù)淇刂茩C(jī)制

吳江海

摘要：最近幾年，節(jié)能網(wǎng)絡(luò)的觀念迅速傳播并獲得了越來越多的關(guān)注。 一方面，節(jié)能網(wǎng)絡(luò)能夠在一定程度上緩解日益嚴(yán)峻的環(huán)境惡化問題，另一方面由于互聯(lián)網(wǎng)消耗著數(shù)量巨大的能量并有迅速增長的趨勢，節(jié)能網(wǎng)絡(luò)可以為電信商和因特網(wǎng)服務(wù)提供商（ISP）帶來巨大的經(jīng)濟(jì)效益。網(wǎng)絡(luò)節(jié)能的通常做法是將網(wǎng)絡(luò)中的路由器和鏈路休眠，但這種做法明顯會降低網(wǎng)絡(luò)性能。該文試圖從整個(gè)網(wǎng)絡(luò)拓?fù)鋵用婵紤]網(wǎng)絡(luò)節(jié)能問題，提出了在保證網(wǎng)絡(luò)性能滿足限定閾值條件的情況下的最優(yōu)化網(wǎng)絡(luò)節(jié)能拓?fù)淇刂颇Ｐ?。針對這個(gè)模型，該文提出了一種啟發(fā)式算法，試圖在保證一定網(wǎng)絡(luò)性能的條件下休眠網(wǎng)絡(luò)節(jié)點(diǎn)和鏈路最小化網(wǎng)絡(luò)能耗。通過網(wǎng)絡(luò)模擬實(shí)驗(yàn)證明了該方法可以在保證一定網(wǎng)絡(luò)Qos的情況下有效地降低網(wǎng)絡(luò)耗能。

關(guān)鍵詞：節(jié)能網(wǎng)絡(luò)；互聯(lián)網(wǎng)；網(wǎng)絡(luò)拓?fù)?；網(wǎng)絡(luò)性能

中圖分類號：TP393.02 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2014）32-7820-05

Abstract： Recently， the concept of energy-saving networking has been widely propagated and gaining an increasing amount of concern. On one hand， energy-efficient networking can alleviate the increasingly serious problem of environment pollution to some extent. On the other hand， energy-saving networking can provide Telecom and ISP huge economic benefits for the current Internet consumes a great amount of energy every year and this trend is becoming increasingly significant. The general method of energy-saving networking is to put some routes and links to sleep mode. However， this strategy will undermine the performance of networks evidently. In this paper， the energy saving of networks is considered on the whole network class and an optimal network topology model for energy savings with some constraints of network performance is proposed. A heuristic algorithm is proposed which is aimed at minimizing the network energy consumption with some Qos constraints by turning off network nodes and links. The simulation experiments demonstrate this strategy can effectively reduce the energy consumption of the network while the Qos is guaranteed to some extent.

Key words： energy-saving networking； Internet； network topology； network performance

1 概述

能量問題是制約無線網(wǎng)絡(luò)生命期的一個(gè)重要因素，因此關(guān)于無線網(wǎng)絡(luò)的節(jié)能問題從很早開始就已經(jīng)有大量的研究[1-4]，而有線網(wǎng)的節(jié)能問題直到近些年來才受到學(xué)術(shù)和工業(yè)界的關(guān)注。近些年來，隨著互聯(lián)網(wǎng)的迅猛發(fā)展，有線網(wǎng)的耗能也迅速增長?，F(xiàn)在，互聯(lián)網(wǎng)耗能已經(jīng)占到總耗能的1%，在未來這一數(shù)字將會增長到4%[5]。即使能夠節(jié)約一小部分的網(wǎng)絡(luò)耗能，也能夠帶來巨大的經(jīng)濟(jì)效益，并減少大量的二氧化碳排放量。

文獻(xiàn)[6]最早提出了互聯(lián)網(wǎng)節(jié)能的問題，它提出可以使路由器或交換機(jī)等網(wǎng)絡(luò)設(shè)備在網(wǎng)絡(luò)空閑情況下進(jìn)行休眠，以達(dá)到一定節(jié)能效果，并通過網(wǎng)絡(luò)中路由器流量的統(tǒng)計(jì)規(guī)律，證明了這種方法的可行性。在文獻(xiàn)[6]之后，文獻(xiàn)[7-10] 進(jìn)一步研究和分析了如何通過休眠網(wǎng)絡(luò)設(shè)備達(dá)到節(jié)能目的。在文獻(xiàn)[7]中，作者提出了一種估測未來數(shù)據(jù)包到來的時(shí)間的方法，并據(jù)此讓網(wǎng)絡(luò)接口進(jìn)入休眠狀態(tài)。文獻(xiàn)[8] 提出并比較了兩種網(wǎng)絡(luò)節(jié)能的方法。第一種方法是將網(wǎng)絡(luò)部件在空閑狀態(tài)下調(diào)整到休眠狀態(tài)以減少在無數(shù)據(jù)包的時(shí)候的能耗；第二種方法是通過調(diào)整網(wǎng)絡(luò)操作的速率以減少數(shù)據(jù)包處理過程中的能耗。這些方法都是從單個(gè)節(jié)點(diǎn)的角度考慮網(wǎng)絡(luò)節(jié)能的問題。

從整個(gè)網(wǎng)絡(luò)層面考慮網(wǎng)絡(luò)節(jié)能問題是綠色網(wǎng)絡(luò)研究的一個(gè)重要方面。文獻(xiàn)[11-12]從路由協(xié)議角度考慮網(wǎng)絡(luò)節(jié)能的問題。它們建立了網(wǎng)絡(luò)鏈路耗能與鏈路流量之間的函數(shù)關(guān)系，在路由選路的時(shí)候，試圖選擇那些能使耗能最少的鏈路，然后讓空閑的鏈路休眠以實(shí)現(xiàn)網(wǎng)絡(luò)節(jié)能。這種方法在一定程度上能夠降低網(wǎng)絡(luò)能耗，但一方面沒有考慮休眠節(jié)點(diǎn)和鏈路可以帶來更大的節(jié)能效果，另一方面沒有考慮節(jié)能給網(wǎng)絡(luò)性能造成的影響?，F(xiàn)在的英特網(wǎng)骨干網(wǎng)提供了比實(shí)際流量大的多的處理能力[13]，并且網(wǎng)絡(luò)一天中的流量隨著時(shí)間會顯著地變化[6]。因此，我們可以在適當(dāng)?shù)臅r(shí)候讓網(wǎng)絡(luò)流量調(diào)整到可以替換的路徑上的鏈路上，并讓空閑的鏈路休眠，以達(dá)到節(jié)能效果。網(wǎng)絡(luò)節(jié)能與性能本身就是一對折中的問題。因此，在本文中，我們試圖在保證一定網(wǎng)絡(luò)性能的前提下節(jié)約網(wǎng)絡(luò)的耗能。該文提出了一種基于休眠骨干網(wǎng)絡(luò)由器和鏈路的拓?fù)渑渲玫淖顑?yōu)化網(wǎng)絡(luò)耗能模型。該最優(yōu)化模型的目標(biāo)是最大化休眠節(jié)點(diǎn)和鏈路的數(shù)目，限制條件是保證接入節(jié)點(diǎn)的連接性和鏈路利用率變化在一定范圍內(nèi)。該問題是是一個(gè)NP難解性問題，因此，我們提出了一種啟發(fā)式的節(jié)能拓?fù)湔{(diào)整算法以獲得近似最優(yōu)解。通過網(wǎng)絡(luò)模擬實(shí)驗(yàn)驗(yàn)證了該方法具有很好的節(jié)能效果。

本文按如下的結(jié)構(gòu)進(jìn)行組織：在第二章，提出的節(jié)能策略可以歸結(jié)為一個(gè)在一定限定條件下的最優(yōu)化問題；在第三章，提出了啟發(fā)式的節(jié)能算法；在第四章，展示了在不同網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)和負(fù)載條件下的實(shí)驗(yàn)結(jié)果；第五部分給出了一些結(jié)論。

2 最優(yōu)化的節(jié)能網(wǎng)絡(luò)拓?fù)淠Ｐ?/p>

3 算法描述

第2章提出的最優(yōu)化問題是一類多商品流問題，眾所周知多商品流問題是NP難解性問題[14]。該問題在網(wǎng)絡(luò)規(guī)模很大的時(shí)候，很難在有限的時(shí)間內(nèi)找到最優(yōu)解。我們提出了一種啟發(fā)式的算法，以獲得能耗近似最優(yōu)的網(wǎng)絡(luò)拓?fù)?。由于一個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)的能耗比單個(gè)鏈路的能耗大很多，因此休眠一個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)比休眠一條單獨(dú)的鏈路所節(jié)約的能耗大。因此，該文提出的算法首先試圖找到可以休眠的最大數(shù)目的節(jié)點(diǎn)，然后尋找可以休眠的最大數(shù)目的鏈路。

這個(gè)啟發(fā)式算法可以分三個(gè)部分進(jìn)行描述： （a）找到最大數(shù)目的可以休眠的路由器；（b）找到可以休眠的最大數(shù)目的鏈路；（c）根據(jù)在某一段時(shí)間T內(nèi)的鏈路利用率的變化，決定網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)因?yàn)榫W(wǎng)絡(luò)狀況的改變是否需要重新配置。算法的程序可以具體按下面的步驟進(jìn)行描述。在選擇嘗試休眠節(jié)點(diǎn)和鏈路的時(shí)候，我們嘗試了兩種不同的方法，一種方法是選擇流量最小的部件，另一種方法是選擇功耗最大的部件。我們比較了這兩種休眠方法的節(jié)能效果。選擇休眠節(jié)點(diǎn)和鏈路的大致步驟圖1所示。

具體的算法描述如下：

我們假定一天中網(wǎng)絡(luò)中的流量呈現(xiàn)正弦變化的特點(diǎn)，網(wǎng)絡(luò)的節(jié)能效果隨流量變化也呈現(xiàn)正弦變化的趨勢。由圖4可以看出，在凌晨2點(diǎn)的時(shí)候，網(wǎng)絡(luò)節(jié)能比例最大。這是因?yàn)榇藭r(shí)，網(wǎng)絡(luò)中的流量最小，網(wǎng)絡(luò)平均利用率最低，可以有更多的節(jié)點(diǎn)和鏈路休眠。隨后網(wǎng)絡(luò)的節(jié)能比例逐漸降低，到下午2點(diǎn)的時(shí)候降到最低。這是因?yàn)閺?點(diǎn)到下午2點(diǎn)的時(shí)候，網(wǎng)絡(luò)流量會逐漸增大，到下午2點(diǎn)的時(shí)候增到最大點(diǎn)，此時(shí)可以休眠的節(jié)點(diǎn)和鏈路也最少。隨后，網(wǎng)絡(luò)節(jié)能效果又逐漸增大，直到凌晨2點(diǎn)達(dá)到最大值。這是由于網(wǎng)絡(luò)流量在下午2點(diǎn)以后逐漸減小，直到凌晨2點(diǎn)降低到最小。類似地，流量最小優(yōu)先的方法比能耗最大優(yōu)先和隨機(jī)算法的節(jié)能效果明顯大很多。

5 結(jié)論

本文從整個(gè)網(wǎng)絡(luò)層面考慮了有線網(wǎng)絡(luò)節(jié)能的問題?？紤]到有線網(wǎng)有較高的冗余，并且流量普遍偏低，我們可以把有線網(wǎng)中的流經(jīng)部分骨干網(wǎng)節(jié)點(diǎn)和鏈路的流量調(diào)整到其他節(jié)點(diǎn)和鏈路上，并讓空閑的節(jié)點(diǎn)和鏈路休眠?；谶@個(gè)基本想法，該文提出了一種能量最優(yōu)的網(wǎng)絡(luò)拓?fù)湔{(diào)整模型，試圖在節(jié)能和網(wǎng)絡(luò)性能之間達(dá)到一定的平衡，并提出了求解該模型的啟發(fā)式算法。通過網(wǎng)絡(luò)模擬實(shí)驗(yàn)，驗(yàn)證了該機(jī)制的合理性和有效性。

參考文獻(xiàn)：

[1] Anastasia G，Contib M，F(xiàn)rancescoa M，Passarellab A. “Energy conservation in wireless sensor networks： A survey， Ad Hoc Networks”[M].2009，7（3）：537-568.

[2] Arindam K，Das， Robert J.Marks， Mohamed El-Sharkawi， Payman Arabshahi， Andrew Gray， “Minimum power broadcast trees for wireless networks： integer programming formulations”[M].003：1001-1010.

[3] 趙保華，李婧，張煒，屈玉貴.基于MIMO 的節(jié)能無線傳感器網(wǎng)絡(luò)[J].電子學(xué)報(bào)，2006，34（8）：1415-1419.

[4] Baghaie M，Krishnamachari B. Delay constrained minimum energy broadcast in cooperative wireless networks[M].INFOCOM， Shanghai， China，2011（5）：864- 872.

[5] J. Baliga， K. Hinton， and R. Tucker. “Energy consumption of the Internet，”Joint International Conference on Optical Internet 2007 and the 32nd Australian Conference on Optical Fiber Technology[M]， COIN-ACOFT， pages 24-27， Melbourne， Australia，2007.

[6] M. Gupta and S. Singh. “Greening of the Internet，” in SIGCOMM 03： Proceedings of the 2003 conference on Applications， technologies， architectures， and protocols for computer communications[M].New York， NY， USA： ACM， 2003：19-26.

[7] M. Gupta， S. Grover， and S. Singh. “A feasibility Study for Power management in Lan switches”[M].in Proc. IEEE ICNP， Berlin， Germany， October， 2004： 361-371.

[8] S.Nedevschi，L.Popa，G.Iannaccone，D.Wetherall，S.Ratnasamy. “Reducing network energy consumption via sleeping and rate-adaptation”[M].Proc. 5th USENIX Symp on Networked Systems Design and Implementation（NSDI 08）， San Francisco， CA， 2008：323-336.

[9] J. Chabarek， J. Sommers， et al. “Power awareness in network design and routing”[M].proceedings of INFOCOM， Phoenix， Arizona， U.S.A， Apr，2008：15-17.

[10] L. Chiaraviglio， M. Mellia， and F. Neri. “Energy-aware networks： Reducing power consumption by switching of network element”[M].FEDERICAPhosphorus tutorial and workshop， Bruges， Belgium， May. 18，2008.

[11] J. Restrepo， C. Gruber， C. Mas Pachuca. “Energy Profile Aware Routing， First International Workshop on Green Communications IEEE International Conference on Communications （ICC）”[M].June 2009.

[12] S.Antonakopoulos，S.Fortune，L.Zhang.“Power-aware routing with rate-adaptive network elements”[M]， GLOBECOM Workshops， Miami，F(xiàn)lorida，Dec，2010：1428- 1432.

[13] International Internet Statistics. TeleGeography Research， 2005.Available at http：//www.itu.int/dms pub/itu-d/md/02/isap2b.1.1/c/D02-ISAP2B.1.1-C-0025??！PDF-E.pdf

[14] T. G. Crainic， M. Gendreau， I. Ghamlouche. “Cycle-based neighborhoods for fixed-charge capacitated multicommodity network design”[M]， Technical report CRT-2001-01， Centre de recherche sur les transports， Universite de Montreal， pages 855.