基于自適應協同進化粒子群算法的虛擬網節能映射研究

胡 穎 莊 雷 蘭巨龍 馬 ?、?/p>

?

基于自適應協同進化粒子群算法的虛擬網節能映射研究

胡 穎*①莊 雷①蘭巨龍②馬 ?、佗?/p>

①(鄭州大學信息工程學院 鄭州 450000)②(解放軍信息工程大學國家數字交換系統工程技術研究中心 鄭州 450002)③(河南工業大學信息科學與工程學院 鄭州 450000)

該文針對虛擬網節能映射問題提出自適應的協同進化粒子群算法。首先，為虛擬網節能映射問題設置了聚合度，該聚合度被用于自適應地選擇粒子的搜索方式，即隨機搜索、種內搜索或種外搜索。其次，根據粒子群的進化結果，自適應地確定是否終止對子群的搜索。最后，在常用的測試環境下進行了仿真實驗，對映射的能耗效果對比了結果，實驗結果表明了所提算法的高效性。

虛擬網節能映射；協同進化；自適應算法；粒子群算法

1 引言

當前互聯網自身結構“僵化”，可擴展性差，新功能的增加和新業務的部署非常困難；以及OTT (Over The Top)業務飛速發展給網絡運營商帶來了巨大的挑戰。種種跡象表明，需要一種革命式的新型互聯網體系結構。網絡虛擬化技術是形成新型互聯網體系結構的重要手段[1]。網絡虛擬化屏蔽了物理層的實現細節，在技術上，為在物理網絡上運行多樣化的協議和異構的應用提供了可能，使網絡具有更好的開放性和靈活性；在運行維護上，使得物理網絡具有了彈性特征，這對網絡故障恢復、網絡負載均衡都具有較大意義；在經濟上，通過共享底層基礎設施避免了服務提供商對基礎設施的重復購買，并降低了能耗和運維成本，提高了資源的利用率。網絡虛擬化既可以應用在未來互聯網的中心，也可以應用在互聯網的邊緣，如數據中心[2]，移動網絡[3]等。因此，網絡虛擬化是未來互聯網、云計算和軟件定義網絡的重要技術[1]。該技術通過整合網絡基礎設施資源，能夠合理有效地使用能量，使得智能能量感知的網絡部署成為可能。

隨著電力成本的不斷上漲，商家已經意識到能耗管理的重要性。當前網絡為高峰負荷而設計，資源的超量供給確保了網絡的正常運行，但也導致了資源利用率的低下。據統計，大型ISP骨干網的平均鏈路利用率大約為30%~40%[4]，數據中心服務器的平均利用率為11%~50%[5,6]，過低的資源利用率造成了電能的巨大浪費，促使綠色網絡研究的興起，網絡能耗問題成為研究的熱點[7,8]。虛擬網映射技術根據虛擬網請求的拓撲結構及節點、鏈路的資源需求，分配底層網絡資源構建虛擬網，因此，該技術是網絡虛擬化技術實施的基礎和關鍵。以節能為目標的虛擬網映射應在滿足當前虛擬網請求的前提下，最小化能耗，如何在這種場景下對虛擬網請求進行以節能為目標的映射，成為降低系統能耗以減少商家開銷的關鍵問題。

當前已有一些學者對虛擬網節能映射問題進行了很有意義的研究。文獻[9]從節能和資源最小化兩個角度對虛擬網映射問題建立了整數線性規劃模型，并分別以其一為主要目標，另一個為次要目標進行了解決和分析；文獻[10]從能耗、請求優先級和請求的位置限制等3個條件來限制虛擬網節能映射問題，分析并得到了較優的結果；文獻[11]為數據中心網絡的虛擬網節能映射問題建立了模型，從實際因素出發，在計算資源和網絡資源兩個角度對問題進行了分析討論；文獻[12]應用最優化理論為虛擬網節能映射問題建立了模型；文獻[13]為云計算網絡的虛擬網節能映射問題建立了混合整數線性規劃模型；文獻[14]從節能，負載均衡等多個目標設計虛擬網映射模型，并針對云計算網絡中的節點或鏈路故障問題，提出了一個容錯的映射算法。

在映射算法上，對文獻[15]的算法根據虛擬網映射問題的特點進行改進，并針對虛擬網映射這個具有離散解空間的混合整數規劃問題，設計出多種群的自適應粒子群算法。該算法為避免粒子群算法自身的缺陷，比如易造成早熟停滯等問題，加入了隨機搜索方式、種群內部精英指導搜索方式、種群外部的精英粒子指導搜索方式以及在多種搜索方式(包括粒子群固有的)間自適應切換等因素。最終提出了自適應的協同進化粒子群算法(Particle Swarm Optimization Algorithm based on Adaptive Cooperative Coevolution, PSOAACC)。實驗結果表明，PSOAACC算法在節能映射上有較好的性能。

2 節能映射模型與評價標準

2.1虛擬網節能映射模型

虛擬網節能映射的目標是最小化能耗量，即使得映射和運行每個虛擬網請求所增加的能耗量減至最低。由文獻[16]中底層網絡的節點和鏈路能耗模型，設置虛擬網節能映射的目標：

約束：虛擬網節能映射的約束同文獻[16]，包括容量約束、傳輸約束、一個虛擬節點只能映射到一個物理節點以及相同虛擬網請求的虛擬節點不能映射到同一個底層節點的約束。

2.2節能映射評價標準

在選擇節點和路徑時，為了更有效地利用資源，除了節能這一主要目標，加入對最小化資源量(即最大化收益成本比)的考慮。

2.2.1節點評價標準 應優先選擇已被開啟，剩余資源量較大，且CPU資源能力較大的節點作為宿主節點。定義節點節能度,值越大，節點被選中的概率越高。

2.2.2鏈路評價標準 在路徑選擇時，要兼顧物理路徑長度和物理路徑中物理鏈路的開啟量。本文通過定義路徑耗能度來對虛擬鏈路的可用物理路徑進行評價，值越小，對的評價越好。

3 自適應的協同進化粒子群算法

3.1 適應度函數

在式(1)中給出了虛擬網節能映射的目標函數，函數值越小，節能效果越好，該問題是最小化問題，于是可直接設置目標函數為適應度函數，即

3.2自適應協同進化粒子群算法的實現

PSOAACC算法模型分上下兩層，底層為多個子種群，高層為精英粒子。底層各子種群采用具有合作機制的自適應的粒子群算法分別進化。在進化過程中，從底層的多個種群中提出適應度值最低的粒子組成高層精英粒子，精英粒子連同自身的歷史最優粒子參與對底層各子種群的指導操作，即種間的指導搜索；若子種群使用本群的歷史最優粒子以及自身粒子的歷史最優粒子作為指導搜索，即為種內的指導搜索；另外，為了盡量避免種群陷入局部最優，這里使粒子適時進行隨機搜索。

3.2.1子種群的聚集程度 子種群中粒子各分量上取值的集中程度決定了子種群的聚集程度，且各分量上取值越多樣化，子種群越分散。

為衡量子種群某時刻的聚集程度，可將其與聚集程度的極端情況相比較。子種群的兩個極端情況分別是所有個體都相同和個體各分量均勻地分散。當均勻分散時，要么取值為，要么取值為。其中，取值為的個數為

當所有位置都均勻分散時，由式(6)和式(9)，得到子種群在均勻分散情況下的聚集度為

3.2.2子種群種內外學習的方式 已知，當子種群的聚集程度較大時，應增大子種群的學習范圍，向著擴散的方向進化，因此，此時應進行種間指導搜索；否則，應進行種內指導搜索。設置閾值，若，進行種間學習；否則，進行種內學習。

進行種內學習時，要使用種內最優個體指導粒子的方向。對分量調整的概率：

種間學習時，需要使用種間的精英粒子(即整體的最優粒子)對粒子方向的指導。于是，對種群中粒子的分量調整的概率為

3.2.3隨機搜索的方式 根據式(2)為每個可用物理節點計算出節能度，和文獻[15]中對粒子隨機初始化的方式類似，根據節能度得到依次增大的權重和。生成隨機數，隨機數落到哪個區間即選擇那個物理節點作為映射節點。這樣，節能度大的節點具有較高的選中概率。

3.2.4確定粒子將進行隨機搜索或學習搜索 當聚集程度較大，應增加隨機搜索個體的數量，使種群向著擴散的方向進化。可定義隨機搜索的個體數為

3.2.5種群進化搜索終止條件 若子種群不再進化，即連續次沒有更新子種群的最優個體，說明結果已接近最優值，或難以跳出局部優值，此時，可終止對該子種群的進化搜索。當所有子種群都被停止時，便可終止整個種群的進化搜索。為避免出現搜索時間過長的情況。

3.3 自適應的協同進化粒子群算法流程

以上分析了PSOAACC算法的主要思想，下面就具體算法實現流程描述如表1。

表1自適應的協同進化粒子群算法流程

(1)初始化參數；

(4)按3.2.3節對該粒子進行隨機搜索，生成映射的物理節點序列；

表2 Sub_ep(,,if_terminate_)程序

(13) 按3.2.2節對該粒子種間指導搜索，生成映射的物理節點序列；

(17) Else

(18) 按3.2.3節對該粒子進行隨機搜索，生成映射的物理節點序列；

(22) End if

4 實驗

4.1實驗環境

本實驗在雙核CPU 3.4 GHz, 4 G內存的PC機上運行。底層網絡拓撲和虛擬網請求拓撲由GT- ITM[18]工具生成，實驗設置同文獻[19]：底層網絡共包含50個節點，每兩節點間連接的概率為0.5。底層節點的計算資源和底層鏈路的帶寬資源取值在[50,100]內均勻分布。虛擬網請求的到達時刻服從平均100個時間單元到達4個請求的泊松過程，即到達時刻服從均值為25的泊松分布。持續時間服從均值為1000的指數分布。每個請求的節點個數在[2,10]內均勻分布，節點連接率為0.5，虛擬節點請求的CPU資源取值在[0,20]，虛擬鏈路請求的帶寬資源取值在[0,50]之間均勻分布。虛擬網請求共計1000個，實驗共運行25000個左右的時間單元。

PSOAACC是以節能為目標的智能搜索算法，實驗選取的比較對象有兩個：較經典的同樣以節能為目標的貪婪映射算法EAVNE[20]和基于粒子群的映射算法PSO[15]。

在參數設置上，同文獻[18,21-23]中的設置，得到節點和鏈路能耗中常數的值為：為150 W;為300 W;為15 W。由于鏈路功耗差異較大，和文獻[16]中設置一樣，這里比較了鏈路功耗在1 W, 15 W和30 W下的網絡總能耗，如圖1(d)所示。PSOAACC算法的參數設置為子種群個體數= 30，最大迭代次數=5，子種群數=3；其它的參數設置為=3,=0.5,=1,=1,=1,,,=5,=0.1,=0.2和=0.7，物理節點已開啟時設置=100，物理節點尚未被開啟時=1,=5。PSO算法的參數設置為種群個體數是30，最大迭代次數為15。

圖1 運行結果

為提高實驗結果的可信度，所有實驗運行10組不同的虛擬網請求，取平均值作為實驗結果。

4.2 節能比較

本文的虛擬網節能映射方法降低了底層網絡節點和鏈路的開啟數量，很大程度地減少了底層網絡能耗，并使得運行中的平均能耗增長較不明顯。

為方便分析描述，首先作如下定義：

定義1 如果在某個時間段內，底層網絡上沒有發生虛擬網請求的到達或離開事件，稱此時段的底層網絡處于穩定狀態。

定義2 如果在某時刻發生了虛擬網請求的映射或離開事件(這里認為映射和離開事件的發生時間忽略不計)，稱該時刻為分裂點。

定義3 相鄰兩個分裂點間的時間段，稱為有效時間片。

由以上定義可知，在有效時間片內，底層網絡處于穩定狀態；在不同的有效時間片間，底層網絡單位能耗量不同。于是，對底層網絡計算總能耗前應先確定所有分裂點，由各分裂點將運行時間分為多個有效時間片，在各個有效時間片內分別計算底層網絡的能耗，底層網絡的總能耗即各有效時間片的能耗總和：

在有效時間片內，物理網絡設備穩定運行，底層網絡能耗即各類設備的能耗之和：

定義平均節點開啟量(Average Number of Open Nodes, ANON)、平均鏈路開啟量(Average Number of Open Links, ANOL)和平均能耗量(Average Amount of Energy Consumption, AAEC)為總和與有效時間片個數之商(時間段均從初始時刻起)。

圖1(a)，圖1(b)和圖1(c)表示節點和鏈路的平均開啟量以及底層網絡的平均能耗量隨時間變化的情況。圖中表明在開啟節點數量，開啟的鏈路數量和能耗量上，PSOAACC算法較PSO和EAVNE有較為明顯的優勢。

底層網絡物理鏈路功耗參數對底層網絡運行總能耗的有影響，但本文算法PSOAACC和粒子群算法PSO相比在各種情況下均有效降低了能耗。

圖1(d)給出底層鏈路功耗參數分別取1 W, 15W和30 W的底層網絡總能耗(根據式(17))情況。圖1(d)表明PSOAACC算法在不同的鏈路能耗下都能取得較好的節能效果。當鏈路功耗為1 W時，PSO較EAVNE的底層網絡總能耗降低了35.8% , PSOAACC較PSO的底層網絡總能耗降低了7.72%；當鏈路功耗為15 W時，PSO較EAVNE的底層網絡總能耗降低了29.31%, PSOAACC較PSO的底層網絡總能耗降低了10.53%；當鏈路功耗為30 W時，PSO較EAVNE的底層網絡總能耗降低了15.49%, PSOAACC較PSO的底層網絡總能耗降低了12.59%。

5 結束語

本文研究了網絡虛擬化環境下的系統能耗問題，根據節能運行的實際需要，設計自適應的協同進化粒子群算法(PSOAACC)，把虛擬網映射在一個較小的節點和鏈路集合中，提高休眠的節點鏈路數量，以實現高效節能。實驗結果表明了PSOAACC算法能夠有效降低底層網絡的能量消耗，與經典節能算法相比，提高了收益成本比。這里將問題限定在集中方式下的單域虛擬網節能映射問題，下一步將對跨域映射問題進行進一步的研究。

參考文獻

[1] ANDERSON T, PETERSON L, SHENKER S,. Overcoming the internet impasse through virtualization[J]., 2005, 38(4): 34-41. doi: 10.1109/MC.2005.136.

[2] CORREA E S, FLETSCHER L A, and BOTERO J F. Virtual data center embedding: a survey [J]., 2015, 13(5): 1661-1670. doi: 10.1109/ TLA.2015.7112029.

[3] CHOCHLIDAKIS G and FRIDERIKOS V. Robust virtual network embedding for mobile networks[C]. 2015 IEEE 26th Annual International Symposium on Personal, Indoor and Mobile Radio Communications, Hong Kong, China, 2015: 1867-1871. doi: 10.1109/PIMRC.2015.7343603.

[4] FISHER W, SUCHARA M, and REXFORD J. Greening backbone networks: Reducing energy consumption by shutting off cables in bundled links[C]. ACM SIGCOMM Workshop on Green Networking, India, 2010: 29-34. doi: 10.1145/1851290. 1851297.

[5] BARROSO L and HOLZLE U. The case for energy- proportional computing[J]., 2007, 40(12): 33-37. doi: 10.1109/MC.2007.443.

[6] BOHRER P, ELNOZAHY E N, KELLER T,The Case for Power Management in Web Servers[M]. New York, NY , USA, Kluwer Academic/Plenum Publishers, 2002: 261-289.

[7] 林闖, 田源, 姚敏. 綠色網絡和綠色評價: 節能機制、模型和評價[J]. 計算機學報, 2011, 34(4): 593-612. doi: 10.3724/ SP.J.1016.2011.00593.

LIN Chuang, TIAN Yuan, and YAO Min. Green network and green evaluation: mechanism, modeling and evaluation[J]., 2011, 34(4): 593-612. doi: 10. 3724/SP.J.1016.2011.00593.

[8] 葉可江, 吳朝暉, 姜曉紅, 等. 虛擬化云計算平臺的能耗管理[J]. 計算機學報, 2012, 35(6): 1262-1285. doi: 10.3724/SP.J. 1016.2012.01262.

YE Kejiang, WU Zhaohui, JIANG Xiaohong,Power management of virtualized cloud computing platform[J]., 2012, 35(6): 1262-1285. doi: 10.3724/SP.J.1016.2012.01262.

[9] MELO M, SARGENTO S, KILLAT U,. Optimal virtual network embedding: Energy aware formulation[J]., 2015, 91: 184-195. doi: 10.1016/j.comnet.2015. 08.011.

[10] TRIKI N, KARA N, BARACHI M E,. A green energy-aware hybrid virtual network embedding approach[J]., 2015, 91: 712-737. dio: 10.1016/j. comnet.2015.08.016.

[11] GUAN X J, CHOI B Y, and SONG S. Energy efficient virtual network embedding for green data centers using data center topology and future migration[J]., 2015, 69(9): 50-59. doi: 10.1016/j.comcom.2015.05.003.

[12] CHEN Xiaohua, LI Chunzhi, and JIANG Yunliang. Optimization model and algorithm for energy efficient virtual node embedding[J]., 2015, 19(8): 1327-1330. doi: 10.1109/LCOMM.2015.2442575.

[13] NONDE L, El-GORASHI T E H, and ELMIRGHANI J M H. Energy efficient virtual network embedding for cloud networks[J]., 2015, 33(9): 1828-1849. doi: 10.1109/JLT.2014.2380777.

[14] HOUIDI I, LOUATI W, and ZEGHLACHE D. Exact multi-objective virtual network embedding in cloud environments[J]., 2015, 58(3): 403-415. doi: 10.1093/comjnl/bxu154.

[15] ZHANG Zhongbao, CHENG Xiang, SU Sen,. A unified enhanced particle swarm optimization-based virtual network embedding algorithm[J].2013, 26(8): 1054-1073. doi: 10. 1002/dac.1399.

[16] 陳曉華, 李春芝, 陳良育, 等. 主動休眠節點鏈路的高效節能虛擬網絡映射[J]. 軟件學報, 2014, 25(7): 1416-1431.

CHEN Xiaohua, LI Chunzhi, CHEN Liangyu,. Energy efficient virtual network embedding based on actively hibernating substrate nodes and links[J]., 2014, 25(7): 1416-1431.

[17] EPPATEIN D. Finding theshortest paths[J]., 1998, 28(2): 652-673. doi: 10.1137/ S0097539795290477.

[18] ZEGURA E W, CALVERT K L, and BHATTACHARJEE S. How to model an Internetwork[C]. Proceedings of IEEE INFOCOM,96. Conference on Computer Communications, San Francisco, CA, USA, 1996: 594-602. doi: 10.1109/ INFCOM.1996.493353.

[19] CHOWDHURY N M M K, RAHMAN M R, and BOUTABA R. Virtual network embedding with coordinated node and link mapping[C]. 2009 IEEE INFOCOM 28th International Conference on Computer Communications, Rio de Janeiro, Brazil, 2009: 783-791. doi: 10.1109/INFCOM.2009.5061987.

[20] SU Sen, ZHANG Zhongbao, CHENG Xiang,. Energy- aware virtual network embedding through consolidation[C]. IEEE Conference on Computer Communications, Orlando, FL, USA, 2012: 127-132. doi: 10.1109/INFOCOMM. 2012. 6193473.

[21] SIVARAMAN V, VISHWANATH A, ZHAO Z,Profiling per-packet and per-byte energy consumption in the NetFPGA Gigabit router[C]. IEEE INFOCOM 2011 - IEEE Conference on Computer Communications Workshops, Shanghai, China, 2011: 331-336. doi: 10.1109/INFCOMW. 2011.5928833

[22] UNNIKRISHNAN D, VADLAMANI R, LIAO Y,Scalable network virtualization using FPGAs[C]. 18th ACM International Symposium on Field-Programmable Gate Arrays, Monterey, CA , USA, 2010: 219-228.

[23] BARROSO L A, CLIDARAS J, and HOLZLE U. The Datacenter as A Computer: An Introduction to the Design of Warehouse-scale Machines[M]. San Rafael, CA, USA, Morgan & Claypool Publishers, 2013: 1-154.

Energy Aware Virtual Network Embedding Using Particle Swarm Optimization Algorithm Based on Adaptive Cooperative Coevolution

HU Ying①ZHUANG Lei①LAN Julong②MA Ding①③

①(,,450000,)②(&,,450002,)③(,,450000,)

A novel adaptive co-evolutionary particle swarm optimization algorithm is presented for energy aware virtual network embedding problem. The polymerization degree is designed, which is used to adaptively select searching method, namely variation search, internal search or external search. Second, the algorithm adaptively determine whether to terminate the searching process of particle swarm according to the evolution result. Moreover, extensive simulation under common test environment compares results in energy consumption performing goal, and the results indicate the efficiency of the proposed algorithm.

Energy aware virtual network embedding; Co-evolution; Adaptive algorithm; Particle swarm optimization algorithm

TP311

A

1009-5896(2016)10-2660-07

10.11999/JEIT151434

2015-12-17；改回日期：2016-07-01；網絡出版：2016-08-26

胡穎 huying_yx@126.com

國家973計劃(2012CB315901)，國家自然科學基金(61379079)，河南省科技廳攻關項目(122102210042)

The National 973 Program of China (2012CB315901), The National Natural Science Foundation of China (61379079), The Science and Technology Key Project of Henan Province (122102210042)

胡 穎： 女，1982年生，講師，研究方向為網絡虛擬化.

莊 雷： 女，1963年生，教授，研究方向為網絡和自動機.

蘭巨龍： 男，1962年生，教授，研究方向為新一代信息網絡關機理論和技術.

馬 ?。?男，1978年生，講師，研究方向為服務路徑組合和網絡虛擬化.