網(wǎng)絡(luò)可靠性感知資源任務(wù)能耗調(diào)度方法仿真

薛佳楣，李美珊，劉 越

(佳木斯大學(xué)信息電子與技術(shù)學(xué)院，黑龍江 佳木斯154007)

1 引言

降低服務(wù)器執(zhí)行能耗對(duì)降低網(wǎng)絡(luò)可靠性感知資源任務(wù)調(diào)度能耗具有一定的參考意義。服務(wù)器執(zhí)行任務(wù)的能量消耗是用戶指定任務(wù)在服務(wù)器上進(jìn)行運(yùn)轉(zhuǎn)時(shí)形成的能量消耗，并且能量消耗會(huì)隨服務(wù)器對(duì)指定任務(wù)工作而產(chǎn)生的功率以及執(zhí)行指定任務(wù)時(shí)間的變化而變化，以對(duì)于服務(wù)器執(zhí)行任務(wù)的能耗調(diào)度不僅要滿足用戶對(duì)服務(wù)質(zhì)量與服務(wù)效率的要求，還要盡最大可能來降低服務(wù)器在執(zhí)行任務(wù)時(shí)的能量消耗。

如何降低服務(wù)器執(zhí)行任務(wù)的能量消耗、延長(zhǎng)網(wǎng)絡(luò)的壽命等問題成為了研究網(wǎng)絡(luò)綠色環(huán)境的熱點(diǎn)，能耗優(yōu)化是達(dá)成網(wǎng)絡(luò)綠色環(huán)境的關(guān)鍵前提條件。文獻(xiàn)[1]提出一種云工作流任務(wù)調(diào)度能效優(yōu)化方法，將最初任務(wù)自底向上進(jìn)行分級(jí)排序，然后得到所有任務(wù)的調(diào)度初始順序，再利用數(shù)據(jù)信息處理器合并，最后使各個(gè)任務(wù)選擇合適等級(jí)的服務(wù)器資源完成調(diào)度，該方法資源利用率較高，但是該方法執(zhí)行任務(wù)時(shí)間過長(zhǎng)，效率較低。文獻(xiàn)[2]提出基于繁忙時(shí)間的并行調(diào)度能耗優(yōu)化方法。將所要執(zhí)行的任務(wù)加入待執(zhí)行任務(wù)列表中，根據(jù)網(wǎng)絡(luò)服務(wù)器可用節(jié)點(diǎn)將任務(wù)劃分為首要任務(wù)和非首要任務(wù)；再根據(jù)任務(wù)列表指示，使所有服務(wù)器節(jié)點(diǎn)完成任務(wù)的總服務(wù)時(shí)間局部最優(yōu)，按準(zhǔn)則分配服務(wù)器進(jìn)行調(diào)度。完成所有作業(yè)請(qǐng)求后，將非作業(yè)窗口進(jìn)行劃分，直至全部作業(yè)請(qǐng)求執(zhí)行結(jié)束。該方法的弊端是服務(wù)器負(fù)載太重，縮短了網(wǎng)絡(luò)壽命。以上兩種調(diào)度方法不能將任務(wù)均衡分配，并且沒有考慮到服務(wù)器能量消耗會(huì)隨著任務(wù)的不同而變化，存在計(jì)算量大、服務(wù)器能耗高、網(wǎng)絡(luò)使用壽命短等問題。

為解決上述問題，本文提出一種新的網(wǎng)絡(luò)可靠性感知資源任務(wù)能耗調(diào)度方法。將多個(gè)目標(biāo)任務(wù)進(jìn)行單一優(yōu)化再分配，達(dá)到能耗均衡。仿真證明，本文提出的網(wǎng)絡(luò)可靠性感知資源調(diào)度方法，在一定程度上降低服務(wù)器能耗，提高網(wǎng)絡(luò)壽命。

2 網(wǎng)絡(luò)可靠性感知資源多目標(biāo)任務(wù)調(diào)度模型

研究環(huán)境是以執(zhí)行器(服務(wù)器)節(jié)點(diǎn)作為簇首的網(wǎng)絡(luò)結(jié)構(gòu)，如圖1所示。當(dāng)服務(wù)器接收到用戶發(fā)出的指定任務(wù)時(shí)，執(zhí)行節(jié)點(diǎn)向服務(wù)器發(fā)送運(yùn)行任務(wù)的屬性信息數(shù)據(jù)通知，并根據(jù)該屬性完成任務(wù)，或服務(wù)器自己執(zhí)行或與其它服務(wù)器聯(lián)合執(zhí)行完成指定任務(wù)目標(biāo)[3]。為避免等待執(zhí)行任務(wù)時(shí)間的增加會(huì)導(dǎo)致能量消耗增大的問題，達(dá)到實(shí)時(shí)處理與能量消耗均衡同時(shí)兼顧的要求，需連通相鄰服務(wù)器節(jié)點(diǎn)共同協(xié)作完成任務(wù)。

圖1 網(wǎng)絡(luò)結(jié)構(gòu)圖

針對(duì)執(zhí)行器節(jié)點(diǎn)能耗均衡協(xié)作中[4]，將可靠性感知資源任務(wù)分為多個(gè)任務(wù)，執(zhí)行單元量化為多目標(biāo)模型[5]。并且運(yùn)用理想點(diǎn)法將用戶發(fā)出的多個(gè)指定任務(wù)進(jìn)行單個(gè)目標(biāo)任務(wù)處理，借此獲取最優(yōu)能量消耗的調(diào)度方法。根據(jù)上述網(wǎng)絡(luò)結(jié)構(gòu)，進(jìn)行用戶指定任務(wù)類型的設(shè)定及其任務(wù)實(shí)現(xiàn)所需時(shí)間的求解。

2.1 用戶指定任務(wù)類型的設(shè)定

在執(zhí)行用戶指定任務(wù)時(shí)，由執(zhí)行器進(jìn)行單個(gè)節(jié)點(diǎn)執(zhí)行或者多個(gè)節(jié)點(diǎn)執(zhí)行，這種執(zhí)行任務(wù)的方法可解決在任務(wù)發(fā)生頻率較高時(shí)服務(wù)器壓力過大導(dǎo)致能耗消耗較多的問題，使得能量消耗均衡并且使用壽命延長(zhǎng)[6]，假如，各個(gè)服務(wù)器節(jié)點(diǎn)的條件一致，可得出以下設(shè)定：

假設(shè)1：完成一個(gè)指定任務(wù)的執(zhí)行能耗與執(zhí)行時(shí)間是可以預(yù)測(cè)的，將該操作作為一個(gè)執(zhí)行單元，將其標(biāo)記為t，一個(gè)可靠性感知資源任務(wù)為t=t1∪t2∪…∪tn，且滿足?ti，tj∈t，?ti∩tj。此時(shí)稱可靠性感知資源任務(wù)具有可分性。

假設(shè)2：若O={o1，o2，…，on}為任務(wù)t的n個(gè)任務(wù)單元執(zhí)行序次，o1只有一個(gè)后任務(wù)單元，on只有一個(gè)前任務(wù)單元，則可稱執(zhí)行過程具有工序限制。

2.2 最大任務(wù)的完成時(shí)間求解

考慮到n個(gè)有工序的可靠性感知資源任務(wù)在m個(gè)服務(wù)器節(jié)點(diǎn)上的工作過程[7]，為在最短的時(shí)間內(nèi)完成全部任務(wù)使得能量消耗最少，在指派可靠性感知資源任務(wù)的時(shí)要對(duì)能量消耗均衡函數(shù)f(E)加以考慮，在保證能耗均衡的前提下加快任務(wù)屬性數(shù)據(jù)資源的流轉(zhuǎn)延長(zhǎng)執(zhí)行器的使用壽命，進(jìn)而縮短存儲(chǔ)時(shí)間降低存儲(chǔ)成本LT；且需要減少可靠性感知資源任務(wù)的完成時(shí)間Cmax，以達(dá)到實(shí)時(shí)調(diào)度的要求。

1)任務(wù)能量均衡函數(shù)f(E)

設(shè)P(t)為在單位時(shí)間內(nèi)執(zhí)行器節(jié)點(diǎn)完成用戶指定任務(wù)后所需要的能量消耗，γ是用戶指定任務(wù)所需的能量，則執(zhí)行器節(jié)點(diǎn)k執(zhí)行時(shí)的能量消耗是

(1)

在分配任務(wù)的同時(shí)也要考慮到執(zhí)行器所剩能量的多少產(chǎn)生的局限性，各個(gè)執(zhí)行器在完成任務(wù)后所剩下的能量是要保證完成再分配的任務(wù)單元，并且還需要將指定任務(wù)的執(zhí)行數(shù)據(jù)信息傳到下一服務(wù)器節(jié)點(diǎn)[8]。r為服務(wù)器節(jié)點(diǎn)傳遞數(shù)據(jù)距離，l為幀長(zhǎng)，則數(shù)據(jù)的傳輸和接收能耗表示為

(2)

其中，αr為在距離r傳輸?shù)陌l(fā)射功率；β為發(fā)射數(shù)據(jù)電路的能量消耗系數(shù)，w為數(shù)據(jù)發(fā)射通道衰減的倍數(shù)。則一個(gè)服務(wù)器節(jié)點(diǎn)k執(zhí)行所有任務(wù)所需要的總能量消耗為

(3)

為了對(duì)比能量消耗是否均衡的問題[9]，本文調(diào)度方法建立的能量消耗均衡指標(biāo)，設(shè)執(zhí)行器節(jié)點(diǎn)k在運(yùn)行某一任務(wù)單元ji時(shí)候的能量消耗Ek-all與剩余能量Ek-rest的比值E=Ek-all/Ek-rest，由此可推出云計(jì)算能量均衡的函數(shù)為

(4)

上式比值越小可以說明服務(wù)器剩余能量越多，可以執(zhí)行的任務(wù)越多；反之服務(wù)器剩余能量越少，可以執(zhí)行的任務(wù)越少。

2)執(zhí)行器存儲(chǔ)成本函數(shù)LT

執(zhí)行器的存儲(chǔ)成本是指在執(zhí)行器運(yùn)行用戶指定任務(wù)時(shí)，需要對(duì)用戶指定的任務(wù)進(jìn)行自動(dòng)存儲(chǔ)長(zhǎng)度為L(zhǎng)信息數(shù)據(jù)和任務(wù)開始等待時(shí)間到執(zhí)行完成時(shí)間長(zhǎng)度T的乘積[10]。

假設(shè)STji代表j的第i個(gè)任務(wù)單元的開始運(yùn)行瞬間，令STj0=0，則其需要的等待時(shí)間

(5)

設(shè)Lji為在運(yùn)行任務(wù)j的第i個(gè)任務(wù)單元的過程中對(duì)任務(wù)數(shù)據(jù)的存儲(chǔ)長(zhǎng)度，由此可以推出執(zhí)行器總存儲(chǔ)成本的目標(biāo)函數(shù)如下所示

(6)

3)最大任務(wù)的完成時(shí)間Cmax

設(shè)pi，j是在非固定服務(wù)器節(jié)點(diǎn)上執(zhí)行某個(gè)任務(wù)j第i個(gè)任務(wù)單元的執(zhí)行時(shí)間，C(ji，k)是執(zhí)行某個(gè)任務(wù)j的第i個(gè)任務(wù)單元在服務(wù)器某節(jié)點(diǎn)k的完成時(shí)間，π=(j1，j2，…，jn)是全部目標(biāo)任務(wù)的順序。一般來說，目標(biāo)網(wǎng)絡(luò)服務(wù)器中對(duì)某一指定任務(wù)的執(zhí)行時(shí)間toper包括：用戶下達(dá)任務(wù)指令的時(shí)間tcomm，有效信息數(shù)據(jù)收集時(shí)間tcolle，任務(wù)信息數(shù)據(jù)處理時(shí)間tproc，即

pi，j=tcomm+tcolle+tproc

(7)

可靠性感知資源任務(wù)在服務(wù)器節(jié)點(diǎn)上執(zhí)行的完成時(shí)間可通過以下描述

C(j1，k)=C(j1，k-1)+pj1，kxj1，k

(8)

其中：xji，k=1表示任務(wù)單元ji由服務(wù)器節(jié)點(diǎn)k執(zhí)行，xji，k=0表示沒有被選中，由此可以推出

C(ji，k)=max{C(ji-1，k)，C(ji，k-1)}+pji，kxji，k

(9)

由上式可知，服務(wù)器節(jié)點(diǎn)k在運(yùn)行某一任務(wù)單元ji的時(shí)候，必須保證服務(wù)器節(jié)點(diǎn)k已經(jīng)完成上一個(gè)任務(wù)單元ji-1，則完成任務(wù)最大時(shí)間為

Cmax(π)=C(ji，k)

(10)

綜合上述過程完成任務(wù)能量均衡函數(shù)、執(zhí)行器存儲(chǔ)成本函數(shù)以及最大任務(wù)的完成時(shí)間的計(jì)算，為網(wǎng)絡(luò)可靠性感知資源任務(wù)能耗調(diào)度提供理論數(shù)據(jù)基礎(chǔ)。

3 基于改進(jìn)蟻群優(yōu)化算法的任務(wù)調(diào)度模型

考慮到實(shí)際應(yīng)用中所要面對(duì)的公平問題和效率問題，對(duì)蟻群算法進(jìn)行改進(jìn)：首先要以執(zhí)行指定任務(wù)的延長(zhǎng)時(shí)間作為目標(biāo)建立函數(shù)來解決執(zhí)行用戶指定任務(wù)中存在的問題；然后為了解決對(duì)執(zhí)行器任務(wù)分配均勻的公平性問題，利用改進(jìn)的蟻群算法將用戶指定任務(wù)屬性數(shù)據(jù)作為公平因子進(jìn)行計(jì)算。為了簡(jiǎn)化計(jì)算，重新對(duì)可靠性感知資源調(diào)度等待序列Qk中的子任務(wù)進(jìn)行標(biāo)記Qk={q1，…，qm}，將可靠性感知資源集合描述為A={a1，…，an}，可靠性感知資源任務(wù)qi的準(zhǔn)備處理時(shí)間和開始處理時(shí)間分別表示為Ti、Tj，st表示可靠性感知資源任務(wù)調(diào)度時(shí)間窗。

將服務(wù)器執(zhí)行任務(wù)的時(shí)間和任務(wù)完成的時(shí)間作為2個(gè)啟發(fā)因子

(11)

η2(qi)=st-ATi

(12)

將服務(wù)器任務(wù)頻率數(shù)據(jù)作為參數(shù)引入到蟻群算法中，設(shè)N(c)是用戶ci的待執(zhí)行任務(wù)的數(shù)量；η3(qi)是用戶指定任務(wù)qi的公平因子；F(ci)是用戶指定任務(wù)qi屬性數(shù)據(jù)的公平因子ci，則得到任務(wù)調(diào)度模型為

(13)

綜上所述，實(shí)現(xiàn)了網(wǎng)絡(luò)可靠性感知資源任務(wù)能耗調(diào)度方法，為檢驗(yàn)本文方法的有效性及可行性，需進(jìn)行仿真。

4 仿真證明

將所提出的網(wǎng)絡(luò)可靠性感知資源任務(wù)能耗的調(diào)度方法與文獻(xiàn)[1]提出的云工作流任務(wù)調(diào)度能效優(yōu)化算法和文獻(xiàn)[2]提出的基于繁忙時(shí)間的并行調(diào)度能耗算法，在CloudSim下進(jìn)行仿真對(duì)比。CloudSim是模擬包SimJava開發(fā)的數(shù)據(jù)信息包，CloudSim繼承了GridSim的程序模式，并且具有以下特征：

1)CloudSim可以支持大規(guī)模的數(shù)據(jù)計(jì)算，并且可對(duì)基礎(chǔ)設(shè)施建模和仿真；

2)CloudSim具有自給自足的信息數(shù)據(jù)平臺(tái)、服務(wù)代理用戶、任務(wù)能耗調(diào)度和平均分配的程序。

CloudSim的Cloud Information Service(CIS)與Data CenterBroker(DCB)可實(shí)現(xiàn)用戶資源發(fā)現(xiàn)以及信息交互，這是模擬能耗調(diào)度的關(guān)鍵核心，本文提出的能耗調(diào)度方法主要在DCB中實(shí)現(xiàn)，在相同的實(shí)驗(yàn)環(huán)境條件下。在此基礎(chǔ)上進(jìn)行本文方法的性能檢測(cè)。

4.1 不同方法的任務(wù)完成時(shí)間

少量任務(wù)仿真，將指定任務(wù)分配到5個(gè)服務(wù)器節(jié)點(diǎn)，從20到100逐漸改變?nèi)蝿?wù)的個(gè)數(shù)，記錄全部任務(wù)的完成時(shí)間(ms)如表1。

表1 任務(wù)完成時(shí)間

將指定任務(wù)分配到20個(gè)執(zhí)行服務(wù)器節(jié)點(diǎn)上，從1000到4000逐漸改變?nèi)蝿?wù)的個(gè)數(shù)，記錄全部任務(wù)的完成時(shí)間(ms)，結(jié)果如圖2所示。

圖2 不同方法全部任務(wù)調(diào)度完成時(shí)間

任務(wù)個(gè)數(shù)固定為4000，從10到40逐漸改變服務(wù)器節(jié)點(diǎn)的個(gè)數(shù)，記錄全部任務(wù)的完成時(shí)間，如圖3所示。

圖3 變化節(jié)點(diǎn)數(shù)時(shí)不同方法完成任務(wù)時(shí)間

從圖3可看出，在任務(wù)數(shù)量固定、服務(wù)器節(jié)點(diǎn)數(shù)較少的情況下，其它調(diào)度方法完成任務(wù)的時(shí)間與本文方法完成任務(wù)調(diào)度的時(shí)間存在明顯差距。綜合考慮圖2、圖3給出的實(shí)驗(yàn)結(jié)果可知，在任務(wù)數(shù)量較多的情況下，本文調(diào)度方法完成任務(wù)用時(shí)最短，優(yōu)勢(shì)比較突出。

4.2 不同方法的任務(wù)處理負(fù)載狀態(tài)

任務(wù)集固定為4000時(shí)，將任務(wù)分配到5個(gè)資源節(jié)點(diǎn)(R1，R2，R3，R4，R5)上處理，記錄5個(gè)服務(wù)器上的資源負(fù)載情況。如圖4所示。

圖4 大量任務(wù)下不同方法處理任務(wù)的負(fù)載狀態(tài)

從圖4可看出，在指定任務(wù)數(shù)量多、服務(wù)器節(jié)點(diǎn)運(yùn)算的能力存在較大差異的情況下，本文方法的任務(wù)負(fù)載均衡程度較好，而其它調(diào)度方法在執(zhí)行任務(wù)中，出現(xiàn)給執(zhí)行任務(wù)能力高的服務(wù)器分布的任務(wù)數(shù)量較少，而給執(zhí)行任務(wù)能力較低的服務(wù)器分布的任務(wù)數(shù)量較多的情況。

4.3 不同方法的任務(wù)處理負(fù)載能耗及壽命

為了驗(yàn)證3種調(diào)度方法在執(zhí)行任務(wù)時(shí)的能量消耗大小，模擬目標(biāo)網(wǎng)絡(luò)1min內(nèi)隨機(jī)加入不同數(shù)量的可靠性感知資源任務(wù)群，圖5與圖6描述了在任務(wù)不斷增加時(shí)網(wǎng)絡(luò)系統(tǒng)的總耗能和壽命。

圖5 任務(wù)負(fù)載變化時(shí)的總能耗

圖6 任務(wù)負(fù)載變化時(shí)網(wǎng)絡(luò)系統(tǒng)壽命

從圖5、圖6中可以看出，當(dāng)服務(wù)器的工作負(fù)載不斷增加時(shí)，目標(biāo)網(wǎng)絡(luò)系統(tǒng)的能量消耗不斷增加，但是網(wǎng)絡(luò)系統(tǒng)的使用壽命不斷減少，同時(shí)可以看出本文方法執(zhí)行任務(wù)時(shí)能量消耗均比其它2種調(diào)度方法少。分析具體過程可知，文獻(xiàn)[1]方法將最初任務(wù)自底向上進(jìn)行分級(jí)排序，為各個(gè)任務(wù)選擇合適等級(jí)的服務(wù)器資源完成調(diào)度，在執(zhí)行任務(wù)中出現(xiàn)給執(zhí)行任務(wù)能力高的服務(wù)器分布的任務(wù)數(shù)量較少，而給執(zhí)行任務(wù)能力較低的服務(wù)器分布的任務(wù)數(shù)量較多的情況，導(dǎo)致任務(wù)調(diào)度過程時(shí)間過長(zhǎng)，加大了服務(wù)器負(fù)載，導(dǎo)致網(wǎng)絡(luò)系統(tǒng)的壽命縮短。相比之下，本文方法進(jìn)行網(wǎng)絡(luò)可靠性感知資源任務(wù)能耗調(diào)度優(yōu)勢(shì)更加明顯。

5 結(jié)束語

針對(duì)傳統(tǒng)能耗調(diào)度方法中存在完成任務(wù)時(shí)間長(zhǎng)、網(wǎng)絡(luò)的壽命短、能耗不均衡等缺點(diǎn)，提出一種新的網(wǎng)絡(luò)可靠性感知資源任務(wù)能耗調(diào)度方法。仿真證明，本文提出的新的網(wǎng)絡(luò)可靠性感知資源任務(wù)能耗調(diào)度方法能夠在保障網(wǎng)絡(luò)環(huán)境的可靠性的前提下，降低服務(wù)器能量消耗，并且有較好的任務(wù)規(guī)模擴(kuò)展性，可實(shí)現(xiàn)能量消耗的均衡，進(jìn)而延長(zhǎng)網(wǎng)絡(luò)系統(tǒng)的使用壽命。