基于復雜梯度網絡的能效優化路由算法

宋莎莎,周金和

(北京信息科技大學 信息與通信工程學院,北京 100101)

0 概述

近年來互聯網的飛速發展,便利人們生活的同時,伴隨著巨大的能源消耗。移動互聯網的普及和用戶對高質量多媒體的需求更是加劇了網絡流量的得增長。據統計,從2007年～2012年,網絡能耗的年平均復合增長率達到10.4%,超過了PC和數據中心的能耗增長速度。能源技術咨詢和投資顧問公司數字能源小組的研究表明,在不包括數據中心網絡在內的運營商網絡基礎設施的能耗保守估計為250 TWh/年—400 TWh/年。據經濟合作與發展組織(OECD)統計,全球互聯網設備呈指數增長,預計到2020年將達到50億,到2030年將達到100億,且在未來的數十年中將增加至500億。2015年召開的巴黎大會上,習近平重申了中國此前做出的承諾,2030年單位國內生產總值二氧化碳排放比2005年下降60%～65%。節能減排成為各行業的發展主題,隨著能耗的持續增長,信息通信技術(Information Communication Technology,ICT)行業造成的碳排放量也在急劇增長,降低互聯網的能耗成為學術研究熱點。

自1998年Watts和Strogatz在Nature上提出小世界網絡模型[1],文獻[2]提出了無標度網絡模型,復雜網絡成為人們研究的熱點。復雜網絡的研究主要包括:復雜網絡的靜態特性,復雜網絡的演化機制,網絡結構和功能的關系。網絡結構和功能的關系是復雜網絡動力學的研究內容,網絡結構能夠影響網絡的動力學行為,同時也被網絡的動力學行為所影響,因此,復雜網絡動力學成為研究重點。

文獻[3]基于介數的節點加權策略,便是針對網絡結構和功能之間的研究,探討了無標度網絡抵制級聯失效的魯棒性。文獻[4]通過分析梯度場和局部網絡結構的關系,提出了復雜梯度網絡的一種傳輸優化策略,驗證了無標度網絡結構和梯度驅動傳輸模式有利于提高網絡的傳輸容量。文獻[5]提出復雜網絡上的基于局部信息路由的擁塞梯度驅動傳輸,分析了多種擁塞感知度的下的傳輸行為。文獻[6]研究了度-度關聯性在無標度梯度網絡動力學過程中對于擁塞的影響。文獻[7]研究權重無標度梯度網絡的擁塞,通過構建邊權函數,證明了存在一個最佳參數使得擁塞最小,這個參數取決于平均連接度。文獻[8]提出有效路由(Efficient Routing)改進了最短路徑路由,認為多數網絡中節點的度和節點的介數正相關,將路徑上所有節點的度作為路由代價函數尋找有效路徑。該路由策略提高了網絡傳輸容量,在一定程度上降低;網絡擁塞。文獻[9]研究了復雜網絡的結構和功能,包括小世界網絡、無標度網絡,以及動力學過程,提出了最大度路由策略,通過仿真驗證了在無標度網絡中具有較高的傳輸效率。文獻[10]研究了信息傳輸中的梯度機制,節點的容量依據節點大小分配,并且傳輸時間隨著中心節點數量增加而減少,通過仿真驗證梯度機制可以優先緩解網絡擁塞。文獻[11]通過關閉或者斷開一些度大節點之間鏈路的方法提高無標度網絡傳輸容量,對于全局路由策略,能更好的提高網絡容量,緩解網絡擁塞。文獻[12]提出對易擁塞節點的鏈路賦予權重,并利用此權重計算有效距離,這種權重分配策略減小了網絡的最大負載,提高了網絡容量,緩解了網絡擁塞,保證傳輸效率。

以上路由算法大多是針對網絡擁塞問題以及網絡傳輸容量和效率的研究,并未涉及網絡能耗問題。為此,本文針對網絡能耗巨大的問題,借助于復雜網絡中關于復雜系統的理論研究,展開對網絡結構和功能的關系研究,提出基于復雜梯度網絡的能效優化路由算法。

1 復雜梯度網絡簡介

隨著信息化的發展,網絡滲透到生活的邊邊角角,復雜網絡的信息流的傳輸屬于典型的動力學過程。在很多真實網絡中,信息傳輸過程并非是隨機的,而是傾向更高效的傳輸方式,某些實體的局部的梯度引起輸運過程,網絡中的信息、能量和物質的輸運就是沿著這些實體的梯度方向進行。綜合網絡結構特征和信息傳輸的動態特性提高數據傳輸效率,卻需要掌握全局信息,這對于日漸增大的網絡規模很難實現。于是,物理學家試圖通過純量場的梯度分布來研究網絡輸運[13],梯度輸運在日常生活中非常普遍,將物理學與網絡科學緊密聯系在一起,提供了一種有效的網絡輸運模式。近年來,很多研究開始將梯度標量場與局域拓撲聯系起來提高網絡的傳輸效率。

2004年,Toroczkai和Bassler提出由底網局部梯度引發的輸運過程,并稱由分布在節點上的區域梯度導出一種有向圖之為梯度網絡[14]。Toroczkai和Bassler給出的梯度網絡的模型定義:首先,選取一個包含N個節點的基網S,給每個節點i賦予一個標量場,隨機的選取0到1之間的數值作為節點的標量,數值記為hi,hi用于刻畫點i的潛力,從每個節點i,引出一條線,引出的線的方式:從每個節點i引出一條指向底網中與節點i相連的所有鄰居里面勢最大的點的線。若節點i的勢最大,那么就指向自身,這樣保證了網絡中的每個節點都有一條出線,如圖1所示。

圖1 梯度網絡定義

Toroczkai和Bassler[14]又通過數值模擬發現,不管基網是無標度網絡還是隨機網絡,當hi是獨立分布的隨機變量,得到的梯度網絡均是無標度網絡。不同之處在于,若基網是無標度網絡,那么得到的梯度網絡的與基網有相同的指數,若基網是隨機網絡,得到的梯度網絡的入度分布是指數γ=1的冪率分布。Park和Lai[15]將梯度運輸應用于隨機網絡和無標度網絡。研究了隨機梯度網絡和無標度梯度網絡下的網絡擁塞,發現無標度梯度網絡在平均度大于10時,網絡阻塞比隨機梯度網絡小。

關于梯度驅動機制,以上的研究都是基于隨機選取的標量值,沒有考慮標量場和網絡結構的關系。本文提出基于復雜梯度網絡的梯度驅動路由(Gradient Dirven Routing,GDR)算法,運用梯度驅動機制,選取的標量場取決于鄰居節點的介數,達到提高網絡能效的效果,最終實現節能減排。

2 系統模型和能效優化傳輸策略

2.1 網絡模型

考慮許多現實網絡服從冪率分布,即具有無標度網絡的特性,本文采用以無標度網絡為底網構造的梯度網絡模型。網絡節點總數為N,為每個節點賦予一個標量場,即節點“勢”,節點“勢”代表節點的潛力。由于節點的介數能更加具體的體現節點的中心性和負載壓力,因此選取節點介數這一結構特性作為影響節點“勢”的因素。節點“勢”由其鄰居節點的介數決定,定義為:

(1)

其中,Bj為節點j的介數,j為i的鄰居節點。

2.2 流量模型

在本文采用廣泛使用的流量模型,將每一個節點看作路由和主機,即每個節點既可以產生數據包同時也可以轉發數據包。網絡中每個時間步有R個數據包產生,并且每個數據包隨機的選取源節點和目的節點。每個節點的隊列長度是一定的,采用先進先出的隊列管理策略。每一步每個節點向目的節點最多轉發C個數據包,一旦數據包到達目的節點,將被移出網絡。數據包的轉發速率為:

(2)

其中,ni,j為時間步為(t-1)緩沖區中隊列長度,Ri,j為i,j連邊的最大帶寬。

2.3 梯度驅動能效路由算法

任意節點均可以看作是主機和路由器,即均具有產生和轉發數據包的功能。任意源節點s到任意目的節點t的路徑可以定義為:

p(s→t):=s≡x0,x1…,xn-1,xn≡t

(3)

其中,(x0,x1,…,xn-1,xn)為(s→t)經過的節點。

采用梯度驅動機制進行數據包的轉發,任意節點s轉發數據包到節點t是依據節點t的“勢”,即節點t是節點s的鄰居節點中“勢”最小的節點,轉發路徑可以定義為:

(4)

其中,α為調節因,當α為0時即為最短路徑,α不為0時,使得L取得最小值就是本文提出的梯度驅動路由策略。

(5)

由于傳輸容量的最大值取決于擁塞點,擁塞出現在介數最大的節點,因此:

(6)

對于節點和鏈路能耗:

(7)

PLij=f(r)=ηerδ,r>0

(8)

總能耗可以表示為:

P=PNi+PLij=f(r)=σe+μerε+ηerδ,r>0

(9)

其中,PNi和PLij分別為節點和鏈路能耗,σe為基礎能耗,ηe,μe,ε為調節因子。

3 仿真及結果分析

本文采用度分布符合冪率分布為P(k)～k-2.5的無標度網絡為底網,選取100個節點,使用Python+networkx+matplotlib和Matlab做仿真模擬。本文選取SPR和ER進行實驗對比,SPR為最短路徑路由算法,ER為Yan等人提出的有效路由算法,GDR為本文提出的梯度驅動路由算法。

數據包產生速率與平均能耗的關系如圖2所示,在數據包產生速率較小時,SPR數據包的傳輸為最短路徑的能耗較小,隨著數據包產生速率的增加,SPR發生擁塞,而GDR對于數據包產生速率的增長沒有SPR敏感,而且由圖2看出,比ER算法節能,本文提出的GDR顯示了在能耗方面的優勢。

圖2 數據包產生速率與平均能耗

平均能耗與參數α的關系如圖3所示,在α為0.3時,路由選擇策略為GDR,由圖3可知,此時的平均能耗最小,GDR算法,繞過了介數較大的節點,對于緩解了數據包在產生速率較大時的擁塞,從而達到節能的效果。

圖3 α與平均能耗的關系

數據包的產生速率和轉發時間的關系如圖4所示,在數據包產生速率較小時,網絡轉發能力足以轉發產生的數據請求,隨著數據請求的增加,SPR在重要節點就會發生擁塞行為,使數據包不停的等待重發,導致轉發時間增加,ER繞過的是節點度較大的節點,節點度大不一定節點介數大,還會在一些節點介數大,但節點度卻不大的節點上出現擁塞,而GDR在轉發數據包時繞過了介數較大的節點,因此,轉發時間得到改善。

圖4 數據包的產生速率與平均轉發時間的關系

網絡節點數和平均路徑長度的關系如圖5所示,獲得收益的同時就要付出代價,GDR降低網絡能耗是以犧牲平均路徑長度為代價的。GDR繞過介數較大的節點,也即放棄選擇最短的路徑,以獲得能效優化的效果。從圖5可以看出,比ER算法的平均路徑長度短。

圖5 網絡節點數與平均路徑長度的關系

4 結束語

本文通過對現實網絡建模,構造以無標度網絡為底網的復雜梯度網絡模型,提出梯度驅動路由策略。Python仿真驗證了其能取得較好的效果。下一步的主要工作是通過繼續探索網絡結構,利用網絡自身的特性構建綠色網絡體系。

[1] WATTS D J,STROGATZ S H.Collective Dynamics of ‘Small-world’ Networks[J].Nature,1998,393(6684):440-442.

[3] 丁 琳,張嗣瀛,鹿江春.加權無標度網絡抵制級聯失效的魯棒性研究[J].計算機工程,2012,38(21):261-263,267.

[4] NIU R W,PAN G J.Transport Optimization on Complex Gradient Networks[J].Chinese Journal of Physics,2016,54(2):278-284.

[5] DANILA B,YU Y,EARL S,et al.Congestion-gradient Driven Transport on Complex Networks[J].Physical Review E,2006,74(2).

[6] PIONTTI A L P,BRAUNSTEIN L A,MACRI P A.Jamming in Complex Networks with Degree Correlation[J].Physics Letters A,2010,374(46):4658-4663.

[7] WANG B,AIHARA K,CHEN L.Jamming in Weighted Scale-free Gradient Networks[J].Europhysics Letters,2008,83(2):28006.

[8] YAN G,ZHOU T,HU B,et al.Efficient Routing on Complex Networks[J].Physical Review E,2006,73(4).

[9] NEWMAN M E J.The Structure and Function of Complex Networks[J].SIAM Review,2003,45(2):167-256.

[10] MUKHERJEE S,GUPTE N.Gradient Mechanism in a Communication Network[J].Physical Review E,2008,77(3).

[11] LIU Z,HU M B,JIANG R,et al.Method to Enhance Traffic Capacity for Scale-free Networks[J].Physical Review E,2007,76(3).

[12] LI M,LIU F,REN F Y.Routing Strategy on a Two-dimensional Small-world Network Model[J].Physical Review E,2007,75(6).

[13] ANGHEL M,TOROCZKAI Z,BASSLER K E,et al.Com-petition-driven Network Dynamics:Emergence of a Scale-free Leadership Structure and Collective Efficiency[J].Physical Review Letters,2004,92(5).

[14] TOROCZKAI Z,BASSLER K E.Network Dynamics:Jamming is Limited in Scale-free Systems[J].Nature,2004,428(6984):716-716.

[15] PARK K,LAI Y C,ZHAO L,et al.Jamming in Complex Gradient Networks[J].Physical Review E,2005,71(6).