薛龍燕，王興偉，李福亮，黃 敏

東北大學(xué) 信息科學(xué)與工程學(xué)院，沈陽(yáng) 110819

基于博弈理論的節(jié)能疏導(dǎo)算法*

薛龍燕+，王興偉，李福亮，黃 敏

東北大學(xué) 信息科學(xué)與工程學(xué)院，沈陽(yáng) 110819

XUE Longyan,WANG Xingwei,LI Fuliang,et al.Game-theory based energy-saving grooming algorithm. Journal of Frontiers of Computer Science and Technology,2016,10(11)：1555-1563.

多粒度傳送網(wǎng)作為下一代骨干傳輸網(wǎng)的核心部分，其高帶寬和節(jié)能優(yōu)勢(shì)受到廣泛關(guān)注。但是，由于用戶不斷激增的帶寬需求和全球電力資源日趨緊張的現(xiàn)狀，需要對(duì)網(wǎng)絡(luò)傳輸系統(tǒng)的容量和性能作進(jìn)一步的提高。對(duì)多粒度傳送網(wǎng)能夠快速提供新鏈路和刪除舊鏈路的特點(diǎn)進(jìn)行了研究，并將博弈均衡的思想引入業(yè)務(wù)量疏導(dǎo)的選路過(guò)程中，設(shè)計(jì)了一種基于博弈理論的多粒度傳送網(wǎng)節(jié)能疏導(dǎo)算法。該算法不僅降低了業(yè)務(wù)阻塞率，而且節(jié)省了網(wǎng)絡(luò)能耗。在拓?fù)銭ON和CERNet2下對(duì)算法進(jìn)行了評(píng)估，仿真結(jié)果表明該算法具有可行性和有效性。

多粒度傳送網(wǎng)；博弈；節(jié)能；疏導(dǎo)；阻塞

1 引言

近年來(lái)，隨著多粒度傳送網(wǎng)的迅速發(fā)展，每根光纖的傳輸速率得到了極大的提高，使得核心骨干傳輸網(wǎng)絡(luò)的高負(fù)重得到了一定的緩解[1-2]。但是，目前網(wǎng)絡(luò)用戶數(shù)量和需求的不斷增加，以及光纖傳輸速率和用戶業(yè)務(wù)傳輸速率大小不匹配，造成波長(zhǎng)通道中的帶寬利用率低，波長(zhǎng)資源短缺，因此業(yè)務(wù)疏導(dǎo)是光網(wǎng)絡(luò)中一項(xiàng)非常重要的技術(shù)。此外隨著經(jīng)濟(jì)的高速發(fā)展，社會(huì)對(duì)各種能源需求的顯著提升導(dǎo)致各種能源短缺，而網(wǎng)絡(luò)速率的不斷提高導(dǎo)致網(wǎng)絡(luò)能耗大幅增加，節(jié)能減排也成為設(shè)計(jì)網(wǎng)絡(luò)需要考慮的問(wèn)題[3-4]。如果能夠充分利用光層網(wǎng)絡(luò)的巨大帶寬和低能優(yōu)勢(shì)，那么整個(gè)網(wǎng)絡(luò)的性能將會(huì)得到很大的提升。為了提高光網(wǎng)絡(luò)利用率，降低能耗，許多研究者都對(duì)光網(wǎng)絡(luò)的數(shù)據(jù)傳輸進(jìn)行了研究。這些研究者雖然在一定程度上對(duì)光網(wǎng)絡(luò)的業(yè)務(wù)量進(jìn)行了疏導(dǎo)，提出了網(wǎng)絡(luò)節(jié)能的觀點(diǎn)，但并未將節(jié)能思想很好地融入到業(yè)務(wù)量疏導(dǎo)過(guò)程中。如果可以把節(jié)能和疏導(dǎo)的思想結(jié)合起來(lái)去解決當(dāng)前網(wǎng)絡(luò)中存在的問(wèn)題，那么光網(wǎng)絡(luò)的容量和性能將會(huì)得到進(jìn)一步的改善。根據(jù)這個(gè)思想本文引入博弈的知識(shí)，將波長(zhǎng)劃分為不同的時(shí)隙，網(wǎng)絡(luò)中業(yè)務(wù)請(qǐng)求通過(guò)時(shí)隙及波長(zhǎng)間的博弈均衡來(lái)確定鏈路代價(jià)，并選取業(yè)務(wù)量消耗最小的運(yùn)行路徑以實(shí)現(xiàn)占用帶寬資源的目的。這不僅降低了光網(wǎng)絡(luò)的業(yè)務(wù)阻塞率，同時(shí)降低了整個(gè)網(wǎng)絡(luò)的能耗。

2 相關(guān)工作

近幾年，多粒度傳送網(wǎng)由于其高寬帶和低能耗優(yōu)勢(shì)得到了學(xué)術(shù)界的關(guān)注，同時(shí)關(guān)于多粒度傳送網(wǎng)的業(yè)務(wù)量疏導(dǎo)問(wèn)題也得到了諸多的研究與探索。

文獻(xiàn)[5]通過(guò)多種途徑對(duì)多粒度傳送網(wǎng)進(jìn)行了有效的研究，其中包括混合線性規(guī)劃、啟發(fā)式方法等，并且提出了一種虛擬拓?fù)浣Y(jié)構(gòu)進(jìn)行業(yè)務(wù)量的疏導(dǎo)。文獻(xiàn)[6]將光網(wǎng)絡(luò)傳統(tǒng)業(yè)務(wù)量疏導(dǎo)的研究與互聯(lián)網(wǎng)體系結(jié)構(gòu)最新發(fā)展技術(shù)相結(jié)合，很大程度上提升了網(wǎng)絡(luò)的傳輸性能。文獻(xiàn)[7]提出了一種新穎的想法，將多粒度傳送網(wǎng)的總能耗分擔(dān)至各光路進(jìn)行平衡，并計(jì)算。文獻(xiàn)[8]非常全面地闡述和分析了多粒度傳送網(wǎng)各部分的能量消耗情況，為解決節(jié)能問(wèn)題提供了一種思路。文獻(xiàn)[3]設(shè)計(jì)了一種有效的節(jié)點(diǎn)結(jié)構(gòu)，并用提出的數(shù)學(xué)模型實(shí)現(xiàn)了多粒度光網(wǎng)絡(luò)跨層的低功耗優(yōu)化目標(biāo)。文獻(xiàn)[9]提出了一種確定的多粒度光交叉連接，支持流量分割，解決了流量多樣化的問(wèn)題。文獻(xiàn)[10]提出了一種多播流量疏導(dǎo)機(jī)制，將低粒度流量通道疏導(dǎo)到高粒度流量通道。文獻(xiàn)[11]在全光網(wǎng)絡(luò)中，使用單播/廣播業(yè)務(wù)量疏導(dǎo)，并提出了一個(gè)模型，可以最大限度地減少能源消耗。文獻(xiàn)[12]結(jié)合動(dòng)態(tài)路由和流量疏導(dǎo)，優(yōu)化了光網(wǎng)絡(luò)的主干網(wǎng)，減少了網(wǎng)絡(luò)的能量消耗。文獻(xiàn)[13]設(shè)計(jì)了網(wǎng)絡(luò)節(jié)點(diǎn)模型，虛擬拓?fù)湓O(shè)計(jì)，確定流量矩陣和不確定流量矩陣，實(shí)現(xiàn)了多粒度光網(wǎng)絡(luò)的節(jié)能和低成本的目標(biāo)。

上述工作對(duì)光網(wǎng)絡(luò)業(yè)務(wù)量疏導(dǎo)和節(jié)能分別進(jìn)行了深入的研究，都取得了一定的成果，但是大部分研究側(cè)重于一方面，不能實(shí)現(xiàn)光網(wǎng)絡(luò)疏導(dǎo)和節(jié)能的有效折中。有的文章雖然同時(shí)考慮了這兩個(gè)方面，但仍側(cè)重于疏導(dǎo)，只是引入了節(jié)能的思想。而本文設(shè)計(jì)的基于博弈理論的疏導(dǎo)機(jī)制的貢獻(xiàn)在于，多粒度傳送網(wǎng)能夠高速地提供和刪除光路，同時(shí)考慮疏導(dǎo)和節(jié)能這兩個(gè)關(guān)鍵問(wèn)題，不僅使網(wǎng)絡(luò)現(xiàn)有的資源能夠得到充分的利用，而且以一種低能耗的方式盡可能地對(duì)業(yè)務(wù)量進(jìn)行疏導(dǎo)。

3 博弈模型

3.1 博弈模型的建立

博弈論是分析經(jīng)濟(jì)學(xué)的一個(gè)重要工具，同時(shí)在其他學(xué)科也得到了很多的關(guān)注。它通過(guò)研究參與雙方在相互作用下如何進(jìn)行決策使得各自效益最大化。博弈過(guò)程是指博弈雙方根據(jù)觀察到的信息和狀態(tài)，從可用的策略集合中選出保證自己利益最大策略的過(guò)程。博弈過(guò)程的正常進(jìn)行，包括三方面：首先是博弈參與者，指參加博弈的雙方，他們通過(guò)觀測(cè)現(xiàn)有的信息和狀態(tài)，在隨后的過(guò)程中做出決策；策略集合，博弈參與者能夠采用策略的集合；收益情況，指博弈雙方采用不同策略各自的收益情況。

本文提出的基于博弈理論的節(jié)能疏導(dǎo)算法，利用時(shí)分復(fù)用技術(shù)將光網(wǎng)絡(luò)中一個(gè)波長(zhǎng)信道容量細(xì)分為多個(gè)時(shí)隙通道，發(fā)送節(jié)點(diǎn)和接收節(jié)點(diǎn)選用不同波長(zhǎng)和不同時(shí)隙所要消耗的能量是不同的，因此網(wǎng)絡(luò)業(yè)務(wù)請(qǐng)求通過(guò)節(jié)點(diǎn)間的博弈占用相應(yīng)波長(zhǎng)及時(shí)隙，在網(wǎng)絡(luò)能耗最低的情況下，實(shí)現(xiàn)業(yè)務(wù)量的疏導(dǎo)。依據(jù)以上提到的博弈的要素，構(gòu)成基于博弈理論的節(jié)能疏導(dǎo)算法的3個(gè)要素分別為：

（1）博弈參與者，網(wǎng)絡(luò)中業(yè)務(wù)請(qǐng)求所經(jīng)路徑的各個(gè)需要做出決策的節(jié)點(diǎn)，其中包括發(fā)送節(jié)點(diǎn)和接收節(jié)點(diǎn)。

（2）博弈策略集，博弈參與者，即節(jié)點(diǎn)能夠選擇的策略，即可以使用的剩余波長(zhǎng)和時(shí)隙的集合。

（3）博弈代價(jià)對(duì)，業(yè)務(wù)選擇對(duì)應(yīng)波長(zhǎng)和時(shí)隙的光路進(jìn)行傳輸所要付出的代價(jià)。

3.2 博弈過(guò)程

節(jié)能疏導(dǎo)算法選擇業(yè)務(wù)量傳輸路徑的過(guò)程就是一個(gè)博弈的過(guò)程，通過(guò)博弈，選擇所需能耗最小的路徑，最大可能地對(duì)業(yè)務(wù)量進(jìn)行傳輸。

首先通過(guò)一個(gè)實(shí)例來(lái)敘述基于博弈理論的節(jié)能疏導(dǎo)算法選擇最佳路徑的博弈過(guò)程。如圖1所示，n1和n2分別代表網(wǎng)絡(luò)中兩個(gè)相鄰的網(wǎng)絡(luò)節(jié)點(diǎn)，這兩個(gè)節(jié)點(diǎn)可以直接進(jìn)行通信。由圖可知，兩個(gè)節(jié)點(diǎn)都包括波長(zhǎng)λ0和λ1，其中每個(gè)波長(zhǎng)又分為兩個(gè)時(shí)隙ts0和ts1。陰影部分表示所對(duì)應(yīng)的時(shí)隙已經(jīng)被其他業(yè)務(wù)所占用，即網(wǎng)絡(luò)節(jié)點(diǎn)n1的波長(zhǎng)λ0的時(shí)隙(ts1,λ0,b0)和節(jié)點(diǎn)n2的波長(zhǎng)λ0的時(shí)隙(ts0,λ0,b0)在博弈過(guò)程中均不可再用。

Fig.1 Wavelength and time slot occupancy of nodes圖1 相鄰節(jié)點(diǎn)波長(zhǎng)和時(shí)隙可用情況

當(dāng)網(wǎng)絡(luò)中有新的業(yè)務(wù)請(qǐng)求到達(dá)時(shí)，業(yè)務(wù)所經(jīng)過(guò)的節(jié)點(diǎn)之間會(huì)通過(guò)博弈的過(guò)程選擇最適合的波長(zhǎng)和時(shí)隙，或者新建光路，進(jìn)行業(yè)務(wù)量的疏導(dǎo)，而判定適合的標(biāo)準(zhǔn)就是相鄰節(jié)點(diǎn)提供鏈路所要付出的代價(jià)。代價(jià)包括所要消耗的能量，下面列出代價(jià)的具體分類。

（1）a，傳輸節(jié)點(diǎn)為業(yè)務(wù)量請(qǐng)求新建一條波長(zhǎng)所需要付出的代價(jià)。

（2）b，業(yè)務(wù)量從相鄰節(jié)點(diǎn)已存在的波長(zhǎng)中，選擇同一時(shí)隙并進(jìn)行傳輸所需要付出的代價(jià)。

（3）c，業(yè)務(wù)量在相鄰節(jié)點(diǎn)的同一波長(zhǎng)的不同時(shí)隙傳輸時(shí)需要付出的代價(jià)。

（4）d，業(yè)務(wù)量傳輸發(fā)生在相鄰節(jié)點(diǎn)的不同波長(zhǎng)時(shí)，且假設(shè)所選波長(zhǎng)都存在，節(jié)點(diǎn)所需要付出的代價(jià)。

經(jīng)過(guò)相關(guān)計(jì)算可知[14]，在同一波長(zhǎng)的相同時(shí)隙傳輸所需要付出的代價(jià)最小，其次是同一波長(zhǎng)的不同時(shí)隙，再次是不同波長(zhǎng)的傳輸，而建立波長(zhǎng)所需要的代價(jià)最大，即b

根據(jù)定義可以得到以上實(shí)例所有博弈策略對(duì)應(yīng)的代價(jià)，如表1所示。

Table 1 Game matrix of noden1andn2表1 節(jié)點(diǎn)n1和n2的博弈矩陣

由納什均衡的定義可以得到，最優(yōu)的選擇為(b+c,b+c)，也就是說(shuō)當(dāng)n1選擇(ts0,λ0,b0),并且n2選擇(ts1,λ0,b0)時(shí)，整體的代價(jià)最低，為最優(yōu)的組合。

下面給出基于博弈的疏導(dǎo)節(jié)能算法的一般性描述。假設(shè)有兩個(gè)相鄰節(jié)點(diǎn)nv-1和nv，它們對(duì)應(yīng)的可選擇的策略集為。這兩個(gè)節(jié)點(diǎn)的策略集的任意組合構(gòu)成了博弈的代價(jià)矩陣，其中矩陣的m行代表節(jié)點(diǎn)nv-1的策略集，m值代表策略集中有m個(gè)策略，即，矩陣的n列代表節(jié)點(diǎn)nv的策略集，n值代表策略集中有n個(gè)策略，即。為矩陣的一個(gè)元素，指的是策略組合，其中節(jié)點(diǎn)nv-1和nv的代價(jià)分別為，pi、pj分別為nv-1和nv策略集中的策略。

通過(guò)納什均衡定義可知，博弈兩方的節(jié)點(diǎn)所需代價(jià)達(dá)到最優(yōu)組合時(shí)應(yīng)滿足以下公式：

當(dāng)納什均衡不存在或者有多個(gè)情況時(shí)，需要比較其帕累托優(yōu)勢(shì)程度。通過(guò)下面式子來(lái)定義策略組合的帕累托優(yōu)勢(shì)：

其中，α和β為正常數(shù)，分別代表對(duì)博弈雙方的傾斜權(quán)值。patoij值較大的元素具有更高程度的帕累托優(yōu)勢(shì)，在博弈過(guò)程中即為要選擇的策略組合。

3.3 算法設(shè)計(jì)

首先通過(guò)實(shí)例給出基于博弈理論的節(jié)能疏導(dǎo)算法的描述。

如圖2（a）所示的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，包含6個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)，現(xiàn)網(wǎng)絡(luò)中有一業(yè)務(wù)量請(qǐng)求，以n0為發(fā)送節(jié)點(diǎn)，n3為接收節(jié)點(diǎn)，業(yè)務(wù)請(qǐng)求帶寬為bw。首先，在整個(gè)物理拓?fù)鋱D內(nèi)，從n0開始遍歷所有節(jié)點(diǎn)，判斷任意相鄰節(jié)點(diǎn)間是否有滿足帶寬bw的已建光路，即是否存在滿足業(yè)務(wù)請(qǐng)求的波長(zhǎng)和時(shí)隙，如有，則計(jì)算出對(duì)應(yīng)的代價(jià)，否則這條光路不可行，刪除光路徑。然后，利用最短路徑算法在已經(jīng)標(biāo)記鏈路代價(jià)的選路圖上找出源節(jié)點(diǎn)n0到目的節(jié)點(diǎn)n3的疏導(dǎo)路徑，如果能夠找到，則將業(yè)務(wù)量請(qǐng)求疏導(dǎo)至該條最短路徑中，否則考慮新建光路對(duì)業(yè)務(wù)進(jìn)行疏導(dǎo)，如圖2（b）中虛線所示。

Fig.2 Schematic diagram of traffic grooming圖2 疏導(dǎo)示意圖

本文設(shè)計(jì)的基于博弈的節(jié)能疏導(dǎo)算法流程描述如下：

步驟1根據(jù)物理網(wǎng)絡(luò)拓?fù)浜途W(wǎng)絡(luò)當(dāng)前資源的使用情況，初始化各個(gè)資源矩陣，包括光收發(fā)器剩余矩陣、現(xiàn)存光路矩陣、剩余波長(zhǎng)矩陣和時(shí)隙矩陣等。

步驟2網(wǎng)絡(luò)業(yè)務(wù)請(qǐng)求到達(dá)節(jié)點(diǎn)后的處理，包括到來(lái)請(qǐng)求和離開請(qǐng)求，分別對(duì)應(yīng)不同的操作。

步驟2.1如果業(yè)務(wù)量請(qǐng)求是到來(lái)請(qǐng)求，則轉(zhuǎn)至步驟3。

步驟2.2如果業(yè)務(wù)量請(qǐng)求是離開請(qǐng)求，跳轉(zhuǎn)至步驟5。

步驟3通過(guò)博弈過(guò)程，對(duì)網(wǎng)絡(luò)業(yè)務(wù)量req(s,d,bw)進(jìn)行疏導(dǎo)，選擇最節(jié)能的路徑。其中s代表源節(jié)點(diǎn)，d代表目的節(jié)點(diǎn)，bw代表帶寬需求。

步驟3.1根據(jù)資源矩陣構(gòu)建博弈策略集，利用博弈策略集構(gòu)建用于選路的虛擬拓?fù)洌瑥脑垂?jié)點(diǎn)s開始尋找是否有滿足業(yè)務(wù)請(qǐng)求需求bw的已存在的光路。此過(guò)程需要遍歷物理拓?fù)渖系娜魏喂?jié)點(diǎn)，并判斷它們之間是否存在這樣的光路，如有轉(zhuǎn)至步驟3.2，否則跳轉(zhuǎn)至步驟4。

步驟3.2在上述的選路虛擬拓?fù)渖喜捎媒?jīng)典的最短路徑算法，找到業(yè)務(wù)請(qǐng)求從源節(jié)點(diǎn)s到目的節(jié)點(diǎn)d代價(jià)最小的光路。選路成功就代表著業(yè)務(wù)可以在此路徑上進(jìn)行疏導(dǎo)，業(yè)務(wù)疏導(dǎo)成功，算法結(jié)束，否則跳轉(zhuǎn)至步驟4，進(jìn)行疏導(dǎo)。

步驟4新建光路對(duì)所到達(dá)的業(yè)務(wù)進(jìn)行疏導(dǎo)。首先查看光收發(fā)器矩陣，判斷進(jìn)行傳輸?shù)膬蓚€(gè)節(jié)點(diǎn)是否有能力進(jìn)行發(fā)送和接收。如果不滿足，不接收業(yè)務(wù)請(qǐng)求，業(yè)務(wù)被阻塞，否則，業(yè)務(wù)占有相應(yīng)的光收發(fā)器。接著判斷兩節(jié)點(diǎn)間的最短路徑上是否有相應(yīng)的滿足業(yè)務(wù)量的波長(zhǎng)資源，如沒(méi)有，請(qǐng)求被阻塞，否則，傳輸節(jié)點(diǎn)占有相應(yīng)的波長(zhǎng)和時(shí)隙資源，并建立傳輸所經(jīng)過(guò)單跳光路徑，計(jì)算成功疏導(dǎo)所耗費(fèi)的能量，算法結(jié)束。

步驟5若為離開請(qǐng)求，釋放業(yè)務(wù)量請(qǐng)求所占有的光收發(fā)器、相應(yīng)波長(zhǎng)和時(shí)隙資源，算法結(jié)束。

4 仿真實(shí)現(xiàn)與性能評(píng)價(jià)

4.1 仿真程序總體框架

在真實(shí)的網(wǎng)絡(luò)中，業(yè)務(wù)量的到來(lái)和離去是隨著時(shí)間動(dòng)態(tài)變化的，而不是事先能預(yù)測(cè)或者靜態(tài)的，因此在本文仿真過(guò)程中體現(xiàn)了這一特征。業(yè)務(wù)量請(qǐng)求由隨機(jī)函數(shù)生成，其到來(lái)時(shí)間、離去時(shí)間、持續(xù)時(shí)間都是隨機(jī)的。并假設(shè)業(yè)務(wù)量到來(lái)時(shí)間服從泊松分布，均值為δ，持續(xù)時(shí)間服從均值為1/μ的負(fù)指數(shù)分布，離去時(shí)間由前兩者計(jì)算，為兩者時(shí)間總和。在仿真過(guò)程中業(yè)務(wù)量存放在一個(gè)優(yōu)先級(jí)隊(duì)列中，離開時(shí)間早的業(yè)務(wù)需要被及早處理，因此存放在優(yōu)先級(jí)隊(duì)列的尾部，相反，離開時(shí)間晚的優(yōu)先級(jí)別低，存放在首部。業(yè)務(wù)的到來(lái)和離去對(duì)應(yīng)“到來(lái)事件”和“離開事件”?！暗絹?lái)事件”就是為相應(yīng)的業(yè)務(wù)建立對(duì)應(yīng)的連接，預(yù)留資源。“離開事件”就是釋放業(yè)務(wù)量請(qǐng)求所占有的光收發(fā)器、相應(yīng)波長(zhǎng)和時(shí)隙資源。

本文提出的基于博弈理論的節(jié)能疏導(dǎo)算法的工作流程如圖3所示。

Fig.3 Basic framework of grooming algorithm圖3 疏導(dǎo)算法流程圖

4.2 性能評(píng)價(jià)指標(biāo)

為了對(duì)本文提出的基于博弈的節(jié)能疏導(dǎo)算法進(jìn)行評(píng)價(jià)，選取了能夠體現(xiàn)疏導(dǎo)和節(jié)能的下述指標(biāo)進(jìn)行分析。

（1）業(yè)務(wù)阻塞率。當(dāng)業(yè)務(wù)量請(qǐng)求集中出現(xiàn)時(shí)，可能會(huì)出現(xiàn)網(wǎng)絡(luò)阻塞狀況，即無(wú)法對(duì)連接請(qǐng)求的業(yè)務(wù)量進(jìn)行疏導(dǎo)，從而出現(xiàn)業(yè)務(wù)阻塞的情況。業(yè)務(wù)阻塞率即業(yè)務(wù)請(qǐng)求沒(méi)有得到滿足的情況，在經(jīng)過(guò)多次實(shí)驗(yàn)后，用網(wǎng)絡(luò)業(yè)務(wù)阻塞數(shù)目來(lái)表示阻塞率有一定的局限性，不能真正表明網(wǎng)絡(luò)的當(dāng)前業(yè)務(wù)疏導(dǎo)情況，因此用沒(méi)有成功疏導(dǎo)業(yè)務(wù)的比例來(lái)表示業(yè)務(wù)阻塞率，如下面公式所示。

通常情況下，公式所求的值越低，代表成功疏導(dǎo)的業(yè)務(wù)越多，疏導(dǎo)性能越好，反之，疏導(dǎo)性能越差。

（2）總能耗。由于網(wǎng)絡(luò)范圍的不斷擴(kuò)大，以及物聯(lián)網(wǎng)的不斷普及，網(wǎng)絡(luò)所消耗的能耗也不斷地受到大家的關(guān)注，本文提出算法的一個(gè)主要特點(diǎn)在于節(jié)能，也就是減少整體網(wǎng)絡(luò)的總能耗，因此用總能耗來(lái)評(píng)估算法的有效性符合實(shí)際。其中總能耗包括分配波長(zhǎng)所需要的能耗、分配波帶所需的能耗以及疏導(dǎo)過(guò)程所需的能耗，如下所示：

此外，還涉及到業(yè)務(wù)量強(qiáng)度，表示需要進(jìn)行疏導(dǎo)的業(yè)務(wù)的數(shù)量和業(yè)務(wù)量的大小，業(yè)務(wù)量的大小用業(yè)務(wù)量虛擬持續(xù)時(shí)間來(lái)表示，它們的乘積表示業(yè)務(wù)量強(qiáng)度，單位為愛爾蘭（Erlang）。光纖波長(zhǎng)數(shù)，代表網(wǎng)絡(luò)能用來(lái)疏導(dǎo)業(yè)務(wù)的光纖的波長(zhǎng)資源。在仿真過(guò)程中，可以通過(guò)改變波長(zhǎng)數(shù)目，驗(yàn)證該算法在不同傳輸能力的網(wǎng)絡(luò)上的性能。

4.3 性能評(píng)價(jià)結(jié)果

為了進(jìn)一步地評(píng)價(jià)基于博弈的多粒度傳送網(wǎng)疏導(dǎo)算法，本文選取Power-Aware Provisioning（PAP）算法[10]作為基準(zhǔn)算法，與之進(jìn)行對(duì)照，去驗(yàn)證算法的有效性。

在驗(yàn)證基于博弈理論的節(jié)能疏導(dǎo)算法（GTG）時(shí)，本文采用兩個(gè)不同的網(wǎng)絡(luò)拓?fù)鋱D去模擬網(wǎng)絡(luò)：一個(gè)是歐洲光網(wǎng)絡(luò)拓?fù)銭ON，如圖4所示；另一個(gè)是第二代中國(guó)教育和科研計(jì)算機(jī)網(wǎng)CERNet2，如圖5所示。圖中的數(shù)字表示相鄰兩節(jié)點(diǎn)對(duì)應(yīng)的真實(shí)距離，單位為km。在仿真過(guò)程中，為了對(duì)GTG算法和基準(zhǔn)算法進(jìn)行比較，本文通過(guò)改變業(yè)務(wù)量強(qiáng)度和波長(zhǎng)數(shù)，分別對(duì)兩種算法的業(yè)務(wù)阻塞率和網(wǎng)絡(luò)能耗的變化情況做了研究。其中因波長(zhǎng)數(shù)是變量，為有效得出波長(zhǎng)資源所帶來(lái)的影響，確定唯一變量。假設(shè)波長(zhǎng)的容量為40 Gb/s（等同于光載波等級(jí)OC-768），每個(gè)節(jié)點(diǎn)有兩個(gè)光收發(fā)器用來(lái)接收和發(fā)送業(yè)務(wù)量，在虛擬平臺(tái)上設(shè)置隨機(jī)函數(shù)來(lái)模擬業(yè)務(wù)量的動(dòng)態(tài)到來(lái)和離去。業(yè)務(wù)量大小分為5種不同粒度，包括OC-96、OC-192、OC-256、OC-384和OC-768。

Fig.4 EON topology圖4EON網(wǎng)絡(luò)拓?fù)?/p>

Fig.5 CERNet2 topology圖5 CERNet2網(wǎng)絡(luò)拓?fù)?/p>

4.3.1 業(yè)務(wù)阻塞率

圖6和圖7分別給出了GTG算法和PAP算法在虛擬網(wǎng)絡(luò)拓?fù)銫ERNet2和EON環(huán)境下，業(yè)務(wù)阻塞率隨業(yè)務(wù)量強(qiáng)度變化的曲線，其中波長(zhǎng)數(shù)為固定值80。由圖可知，隨著業(yè)務(wù)量強(qiáng)度的不斷增加，由于資源有限，能夠疏導(dǎo)的業(yè)務(wù)量不能無(wú)限制地增加，從而業(yè)務(wù)阻塞率在不斷地增加，但總體上，本文算法有較低的業(yè)務(wù)阻塞率。

Fig.6 Curve of bandwidth block probability with traffic intensity on CERNet2圖6 CERNet2上不同業(yè)務(wù)量強(qiáng)度的業(yè)務(wù)阻塞率變化圖

Fig.7 Curve of bandwidth block probability with traffic intensity on EON圖7 EON上不同業(yè)務(wù)量強(qiáng)度的業(yè)務(wù)阻塞率變化圖

圖8和圖9分別顯示業(yè)務(wù)阻塞率隨光纖中波長(zhǎng)數(shù)的變化曲線，其中業(yè)務(wù)量強(qiáng)度為500 Erlang。波長(zhǎng)數(shù)的增加能夠提高網(wǎng)絡(luò)的疏導(dǎo)性能，當(dāng)波長(zhǎng)數(shù)增加時(shí)，在相同業(yè)務(wù)量的情況下，業(yè)務(wù)阻塞率變小。但總體上，本文算法有較低的阻塞率，在EON中，當(dāng)波長(zhǎng)增加到100時(shí)，本文算法的業(yè)務(wù)阻塞率幾乎為0。

Fig.8 Curve of bandwidth block probability with the number of wavelengths on CERNet2圖8 CERNet2上不同波長(zhǎng)數(shù)的業(yè)務(wù)阻塞率變化圖

Fig.9 Curve of bandwidth block probability with the number of wavelengths on EON圖9 EON上不同波長(zhǎng)數(shù)的業(yè)務(wù)阻塞率變化圖

4.3.2 能耗

圖10和圖11分別給出了本文基于博弈的算法和基準(zhǔn)算法在虛擬網(wǎng)絡(luò)拓?fù)銫ERNet2和EON環(huán)境下，不同業(yè)務(wù)量強(qiáng)度的總能耗變化圖，其中波長(zhǎng)數(shù)目固定為80。由圖可知，隨著業(yè)務(wù)量強(qiáng)度的增加，疏導(dǎo)業(yè)務(wù)所需要的能耗逐漸增大，但本文算法在疏導(dǎo)時(shí)考慮到了能耗，因此與基準(zhǔn)算法相比，有較低的能耗，具有更好的節(jié)能性能。

Fig.10 Histogram of power consumption with traffic intensity on CERNet2圖10 CERNet2上不同業(yè)務(wù)量強(qiáng)度的能耗變化圖

Fig.11 Histogram of power consumption with traffic intensity on EON圖11 EON上不同業(yè)務(wù)量強(qiáng)度的能耗變化圖

圖12和圖13分別顯示了不同波長(zhǎng)數(shù)的總能耗變化圖，其中業(yè)務(wù)量強(qiáng)度為500 Erlang。由圖可得，隨著波長(zhǎng)數(shù)的增加，網(wǎng)絡(luò)維護(hù)波長(zhǎng)管理所需要的能量增加，總的能耗增加，但是本文算法與基準(zhǔn)算法相比，有較低的能耗，具有更好的節(jié)能性能。

Fig.12 Histogram of power consumption with the number of wavelengths on CERNet2圖12 CERNet2上不同波長(zhǎng)數(shù)的能耗變化圖

Fig.13 Histogram of power consumption with the number of wavelengths on EON圖13 EON上不同波長(zhǎng)數(shù)的能耗變化圖

當(dāng)波長(zhǎng)數(shù)一定，波長(zhǎng)容量發(fā)生變化時(shí)，所得結(jié)果與上述類似，因均為波長(zhǎng)資源發(fā)生改變，影響業(yè)務(wù)阻塞率和總能耗的變化。

綜上所述，本文基于博弈的節(jié)能疏導(dǎo)算法，在不同的網(wǎng)絡(luò)狀況下，比基準(zhǔn)算法PAP具有更好的疏導(dǎo)性能和節(jié)能效能。此外，節(jié)點(diǎn)在博弈過(guò)程中需要存儲(chǔ)博弈對(duì)及博弈代價(jià)等信息，這帶來(lái)了一定的存儲(chǔ)開銷，因?yàn)橹淮鎯?chǔ)相鄰節(jié)點(diǎn)的信息，所以這樣的開銷可以忽略不計(jì)。博弈過(guò)程同樣帶來(lái)了一定的時(shí)間開銷，在尋找最短路徑的過(guò)程中考慮了節(jié)能這個(gè)因素，通過(guò)實(shí)驗(yàn)證明這并未影響業(yè)務(wù)量的成功疏導(dǎo)。本文是對(duì)小規(guī)模網(wǎng)絡(luò)進(jìn)行的實(shí)驗(yàn)，隨著網(wǎng)絡(luò)規(guī)模的不斷擴(kuò)大，節(jié)點(diǎn)數(shù)量的不斷增加，需要對(duì)網(wǎng)絡(luò)進(jìn)一步的分層，再使用該博弈算法。

5 結(jié)束語(yǔ)

本文在運(yùn)用時(shí)分復(fù)用技術(shù)使多個(gè)業(yè)務(wù)共享一個(gè)波長(zhǎng)的條件下，將博弈均衡思想引入業(yè)務(wù)量疏導(dǎo)過(guò)程，設(shè)計(jì)了基于博弈理論的節(jié)能疏導(dǎo)算法，通過(guò)不同波長(zhǎng)和時(shí)隙間的博弈來(lái)選擇能耗最小的路徑。將所提出的算法在不同的網(wǎng)絡(luò)拓?fù)渖线M(jìn)行運(yùn)行，仿真結(jié)果表明，與基準(zhǔn)算法PAP相比，基于博弈理論的疏導(dǎo)算法不僅能夠有效地對(duì)業(yè)務(wù)請(qǐng)求進(jìn)行疏導(dǎo)，而且還具有較好的節(jié)能效果。該機(jī)制的進(jìn)一步完善和實(shí)用化是未來(lái)研究工作的重點(diǎn)。

[1]Tran P N,Killat U.Resource efficient logical topology design for IP over WDM backbone networks[J].Computer Communications,2008,31(16):3771-3777.

[2]Rai S,Song Lei,Cavdar C,et al.A novel approach to provision differentiated services in survivable IP over WDM networks[J].Optical Switching and Networking,2008,5(2/3): 170-176.

[3]Wang Xingwei,Cheng Hui,Li Keqin,et al.A cross-layer optimization based integrated routing and grooming algorithm for green multi-granularity transport networks[J]. Journal of Parallel&Distributed Computing,2013,73(6): 807-822.

[4]Wang Xingwei,Qu Dapeng,Huang Min.An energy-efficient QoS routing scheme for many-to-many multicast requests in green multi-granularity transport networks[C]//Proceedings of the 2013 10th International Conference on Fuzzy Systems and Knowledge Discovery,Shenyang,China,Jul 23-25,2013. Piscataway,USA:IEEE,2013:1050-1054.

[5]Tucker R S,Parthiban R,Baliga J.Evolution of WDM optical IP networks:a cost and energy perspective[J].Journal ofLightwave Technology,2009,27(3):243-252.

[6]Dutta R,Rouskas G,Baldiney I.Converging choice and service in future commodity optical networks using traffic grooming[C]//Proceedings of the 2013 15th International Conference on Transparent Optical Networks,Cartagena, Jun 23-27,2013.Piscataway,USA:IEEE,2013:1-5.

[7]Huang S,Seshadri D,Dutta R.Traffic grooming:a changing role in green optical networks[C]//Proceedings of the 2009 Global Telecommunications Conference,Honolulu,USA, Nov 30-Dec 4,2009.Piscataway,USA:IEEE,2009:1-6.

[8]Bolla R,Bruschi R,Davoli F,et al.Energy efficiency in the future:Internet a survey of existing approaches and trends in energy-aware fixed network infrastructures[J].IEEE Communications Surveys&Tutorials,2011,13(2):223-244.

[9]Wang Xingwei,Hou Weigang,Guo Lei,et al.A new multigranularity grooming algorithm based on traffic partition in IP over WDM networks[J].Computer Networks,2011,55 (3):807-821.

[10]Zhang Songzhu,Wang Xingwei,Huang Min.Amulti-granularity grooming scheme for one-to-many multicast traffic [C]//Proceedings of the 2014 13th International Symposium on Distributed Computing and Applications to Business,Engineering and Science,Xianning,China,Nov 24-27,2014.Piscataway,USA:IEEE,2014:215-219.

[11]Puche W S,Amaya F O,Sierra J E.Energy-minimized design in all-optical networks using unicast/multicast traffic grooming[C]//Proceedings of SPIE,Conference on Novel Optical Systems Design and Optimization,2013,8842.

[12]Biswas P P,Singh A,Chadha D.Energy efficient design for green optical core network[C]//Proceedings of the 2013 National Conference on Communications,New Delhi,Feb 15-17,2013.Piscataway,USA:IEEE,2013:1-5.

[13]Wang Xingwei,Hou Weigang,Guo Lei,et al.Energy saving and cost reduction in multi-granularity green optical networks[J].Computer Networks,2011,55(3):676-688.

[14]Xia Ming,Tornatore M,Zhang Yi,et al.Greening the optical backbone network:a traffic engineering approach[C]// Proceedings of the 2010 IEEE International Conference on Communications,Cape Town,May 23-27,2010.Piscataway, USA:IEEE,2010:1-5.

XUE Longyan was born in 1990.She is a student at College of Information Science&Engineering,Northeastern University.Her research interests include industrial cognitive network and BIO network,etc.

薛龍燕（1990—），女，河北石家莊人，東北大學(xué)信息科學(xué)與工程學(xué)院學(xué)生，主要研究領(lǐng)域?yàn)楣I(yè)認(rèn)知網(wǎng)絡(luò)，仿生網(wǎng)絡(luò)等。

WANG Xingwei was born in 1968.He received the Ph.D.degree from Northeastern University in 1998.Now he is a professor and Ph.D.supervisor at Northeastern University,and the member of CCF.His research interests include cloud computing and future Internet,etc.

王興偉（1968—），男，遼寧沈陽(yáng)人，1998年于東北大學(xué)獲得博士學(xué)位，現(xiàn)為東北大學(xué)教授、博士生導(dǎo)師，CCF會(huì)員，主要研究領(lǐng)域?yàn)樵朴?jì)算，未來(lái)互聯(lián)網(wǎng)等。

LI Fuliang was born in 1986.He received the Ph.D.degree from Tsinghua University in 2015.Now he is a lecturer at Northeastern University.His research interests include next generation Internet and network security,etc.

李福亮（1986—），男，遼寧葫蘆島人，2015年于清華大學(xué)獲得博士學(xué)位，現(xiàn)為東北大學(xué)講師，主要研究領(lǐng)域?yàn)橄乱淮ヂ?lián)網(wǎng)，網(wǎng)絡(luò)安全等。

HUANG Min was born in 1968.She received the Ph.D.degree in control theory from Northeastern University in 1999.Now she is a professor and Ph.D.supervisor at Northeastern University.Her research interests include modeling and optimization for logistics and supply chain system,etc.

黃敏（1968—），女，遼寧沈陽(yáng)人，1999年于東北大學(xué)獲得博士學(xué)位，現(xiàn)為東北大學(xué)教授、博士生導(dǎo)師，主要研究領(lǐng)域?yàn)槲锪髋c供應(yīng)鏈管理，智能算法設(shè)計(jì)與優(yōu)化等。

Game-Theory Based Energy-Saving GroomingAlgorithm?

XUE Longyan+,WANG Xingwei,LI Fuliang,HUANG Min
College of Information Science&Engineering,Northeastern University,Shenyang 110819,China
+Corresponding author:E-mail:xue_longyan@sina.cn

As the core part of next generation backbone transmission network,multi-granularity transport networks have attracted more and more attention because of the advantages of high bandwidth and energy saving.However, due to the growing tendency of users’bandwidth in demand and the increasing tense situation of global electricity resources,it’s important to further improve the capacity and performance of data network transmission.This paper studies the features that the multi-granularity transport networks can establish new paths and delete old paths in a high speed,introduces the ideas of game equilibrium into traffic guidance process,and designs a kind of energy-saving guidance algorithm based on game theory that can achieve the traffic grooming and energy-saving effectively at the same time.Finally,this paper simulates the proposed algorithm on the topologies of EON and CERNet2,the results show that the algorithm is feasible and effective.

multi-granularity transmission networks;game-theory;energy-saving;traffic grooming;blocking

10.3778/j.issn.1673-9418.1509097

A

TP393

*The National Science Foundation for Distinguished Young Scholars of China under Grant Nos.61225012,71325002(國(guó)家杰出青年科學(xué)基金);the National Natural Science Foundation of China under Grant Nos.61572123,61502092(國(guó)家自然科學(xué)基金);the Specialized Research Fund of the Doctoral Program of Higher Education of China for the Priority Development Areas under Grant No.20120042130003(高等學(xué)校博士學(xué)科點(diǎn)專項(xiàng)科研基金優(yōu)先發(fā)展領(lǐng)域資助課題).

Received 2015-08,Accepted 2015-10.

CNKI網(wǎng)絡(luò)優(yōu)先出版:2015-10-30,http://www.cnki.net/kcms/detail/11.5602.TP.20151030.1701.008.html