基于服務(wù)質(zhì)量的能耗感知工作流卸載策略

袁友偉,吳浩天+,張雪峰,李萬清,李忠金,邱仁志

(1.杭州電子科技大學(xué) 計算機學(xué)院,浙江 杭州 310018;2.浙江省腦機協(xié)同智能重點實驗室,浙江 杭州 310018)

0 引言

隨著物聯(lián)網(wǎng)技術(shù)和移動通信技術(shù)的快速發(fā)展,包括音頻識別、增強現(xiàn)實和協(xié)同駕駛等應(yīng)用[1]在內(nèi)的延時敏感型和計算密集型計算任務(wù)已逐步在移動設(shè)備(Mobile Device,MD)上廣泛應(yīng)用,為用戶提供更加便捷的移動服務(wù)。然而,移動設(shè)備在存儲資源、網(wǎng)絡(luò)帶寬、計算能力和電池續(xù)航方面存在巨大的限制[2-3]。為應(yīng)對上述問題帶來的挑戰(zhàn),移動邊緣計算(Mobile Edge Computing,MEC)被提出,使得復(fù)雜計算任務(wù)能夠在移動邊緣設(shè)備上被高能效地完成。工作流延時優(yōu)化作為邊緣計算環(huán)境下工作流調(diào)度的關(guān)鍵挑戰(zhàn),隨著應(yīng)用的進一步發(fā)展,傳統(tǒng)的調(diào)度方案無法繼續(xù)滿足用戶對低延時的需要,故需采用新的調(diào)度方案。其次,移動設(shè)備由于其體積較小,極大地限制了電池壽命。若直接將計算任務(wù)卸載至邊緣服務(wù)器執(zhí)行,尤其在較差的網(wǎng)絡(luò)環(huán)境中,不僅任務(wù)執(zhí)行延時較高,還會造成大量的電池能量消耗,極大地降低設(shè)備待機時間。要解決MEC領(lǐng)域性能的瓶頸問題,為用戶提供更高質(zhì)量的服務(wù)體驗,關(guān)鍵在于進一步降低移動設(shè)備的延時和能耗[4]。而諸如圖像識別、推薦算法等計算密集型且對計算精度要求不高的應(yīng)用,可以通過降低卸載節(jié)點的服務(wù)質(zhì)量(Quality of Service,QoS)即引入近似計算技術(shù)[5-6],降低卸載到邊緣節(jié)點的任務(wù)計算精度,以最大限度降低移動設(shè)備的能耗與工作流的延時。

基于上述原因,本文研究了邊緣計算工作流調(diào)度的任務(wù)卸載問題,提出一種基于服務(wù)質(zhì)量的能耗感知工作流卸載策略(Energy Aware workflow offloading strategy based on Quality of Service,EA-QoS)。該策略通過對工作流進行分層,利用HEFT(heterogeneous earliest finish time)算法生成就緒隊列,確保卸載任務(wù)間依賴關(guān)系的有效性;搜集邊緣節(jié)點信息,為節(jié)點分組設(shè)置QoS等級,降低任務(wù)調(diào)度過程的復(fù)雜度;利用非支配排序算法(Non-dominated Sorting Genetic Algorithm Ⅲ,NSGA-Ⅲ)生成調(diào)度方案,確保能耗與時延的全局最優(yōu)性。

1 相關(guān)工作

近年來,移動智能設(shè)備及MEC得到了快速發(fā)展,眾多專家學(xué)者對MEC環(huán)境下工作流卸載問題的延時優(yōu)化和能耗優(yōu)化算法進行了研究,本章主要從MEC環(huán)境下工作流卸載的延時優(yōu)化和能耗優(yōu)化兩個方面對研究現(xiàn)狀進行介紹。

MEC作為一種新興的并行式計算技術(shù),通過將工作流從資源受限的智能移動設(shè)備卸載到邊緣演進型節(jié)點(evolved Node B,eNB)中執(zhí)行,以降低應(yīng)用任務(wù)的處理延時。最常見的工作流卸載的延時優(yōu)化調(diào)度算法是整數(shù)線性規(guī)劃(Integer Linear Program,ILP)[7-9],也有許多專家學(xué)者研究了貪心算法[10]、馬爾可夫決策過程[11]和Petri網(wǎng)[12]等卸載方法。KIM等[13]提出一種基于預(yù)測工作流任務(wù)的卸載方法,通過使用線性回歸預(yù)測任務(wù)的預(yù)期處理時間,以降低每個MEC服務(wù)器上應(yīng)用程序的平均處理時間。TONG等[14]考慮了移動用戶設(shè)備在基站件的移動性,提出一種基于深度強化學(xué)習(xí)(Deep Reinforcement Learning,DRL)的任務(wù)卸載方法,有效降低了任務(wù)平均響應(yīng)時間。ALGHAMDI等[15]針對工作流卸載中數(shù)據(jù)質(zhì)量感知的卸載順序決策問題,通過最大化卸載任務(wù)到處理時間最短邊緣節(jié)點的概率,從而顯著減少分析任務(wù)執(zhí)行的預(yù)期處理時間。XU等[16]研究了云邊緣環(huán)境下的物聯(lián)網(wǎng)大數(shù)據(jù)卸載問題,提出一種結(jié)合NSGA-Ⅲ的計算卸載方法,顯著降低了工作流的執(zhí)行延時。

智能移動設(shè)備的電池容量有限,故能耗優(yōu)化成為了移動邊緣計算卸載性能評估的重要標(biāo)準(zhǔn)。ZHANG等[17]提出一種能耗感知卸載方案,該方案通過利用小型邊緣節(jié)點調(diào)整計算任務(wù)的卸載服務(wù)器,以降低工作流卸載的能耗。MAZOUZI等[18]研究了多用戶工作流能耗受限的邊緣與遠程聯(lián)合卸載問題,提出一種利用拉格朗日分解法的分布式線性啟發(fā)式算法,從而最小化移動設(shè)備能耗。ALAM等[19]綜合考慮資源需求、資源可用性和網(wǎng)絡(luò)狀態(tài)的代碼卸載單元,最大限度地減少了工作流遷移計算的能耗。XU等[20]分析了原始接入節(jié)點到目的接入節(jié)點之間的所有接入路由,提出一種搜索尋找最短路徑卸載任務(wù)的算法,以大幅降低設(shè)備能耗。徐佳等[3]對云邊緣計算環(huán)境中的計算資源進行了綜合的考慮,提出一種多重資源計算卸載粒子群任務(wù)調(diào)度算法,在考慮了響應(yīng)時間的約束下,充分降低移動終端的能耗。

當(dāng)前在MEC環(huán)境下工作流卸載問題的研究主要是通過任務(wù)調(diào)度來減少延時與能耗,這種通過調(diào)度任務(wù)卸載位置的優(yōu)化方式存在一定的局限,然而結(jié)合近似計算技術(shù)對被調(diào)度的工作流任務(wù)本身進行優(yōu)化處理的研究很少。本文在上述研究的基礎(chǔ)上提出的基于服務(wù)質(zhì)量的能耗感知工作流卸載策略,采用近似計算優(yōu)化處理工作流任務(wù),從而降低工作流任務(wù)的計算工作量。實現(xiàn)了在滿足服務(wù)質(zhì)量限制的情況下,在原有調(diào)度算法研究的基礎(chǔ)上,進一步降低移動設(shè)備的能耗和延時。

2 系統(tǒng)模型

本章主要介紹邊緣環(huán)境下的基于服務(wù)質(zhì)量的能耗感知工作流卸載模型、QoS模型、時間模型、能耗模型和優(yōu)化目標(biāo),其中QoS模型、時間模型和能耗模型為基于服務(wù)質(zhì)量的能耗感知工作流卸載模型的組成部分。

2.1 邊緣環(huán)境下基于服務(wù)質(zhì)量的能耗感知工作流卸載模型

邊緣環(huán)境下基于服務(wù)質(zhì)量的能耗感知工作流卸載架構(gòu)如圖1所示,系統(tǒng)首先對每個移動設(shè)備應(yīng)用程序提交的工作流進行建模分層,確定就緒任務(wù)隊列。然后搜集邊緣節(jié)點信息,使用能耗感知優(yōu)化方法進行排序并分組分配服務(wù)質(zhì)量(QoS)級別。再對就緒工作流隊列、邊緣節(jié)點等進行編碼,最后任務(wù)調(diào)度器利用非支配排序算法(NSGA-Ⅲ)確定最優(yōu)卸載方案,卸載任務(wù)到相應(yīng)節(jié)點上執(zhí)行,得到工作流執(zhí)行結(jié)果。

圖1 邊緣環(huán)境下基于服務(wù)質(zhì)量的能耗感知工作流卸載架構(gòu)示意圖

2.2 工作流模型

2.3 QoS模型

(1)

當(dāng)q=0時,表示實際輸出的近似結(jié)果與所能達到的最高精度結(jié)果完全不同;當(dāng)q=1時,表示服務(wù)質(zhì)量達到當(dāng)前邊緣節(jié)點的最高級別,近似結(jié)果與精確計算的結(jié)果完全相同。

定義1QoS約束。令Q為移動設(shè)備(用戶)賦予某特定應(yīng)用程序所能接受的最低QoS等級。每一個邊緣節(jié)點都會被分配一個服務(wù)質(zhì)量等級qi(qi∈[0,1])。無論工作負(fù)載如何分布,系統(tǒng)中負(fù)責(zé)處理任務(wù)的節(jié)點的聚合QoS等級不能小于Q,即：

(2)

2.4 時間模型

MEC場景中的響應(yīng)時間主要由工作流執(zhí)行計算的任務(wù)處理時間Tex和數(shù)據(jù)傳輸時間Ttx組成。在執(zhí)行計算任務(wù)時,任務(wù)處理時間取決于計算任務(wù)的工作量、計算平臺的計算能力和分配給卸載節(jié)點的QoS等級。工作負(fù)載為wi的任務(wù)vi計算時間為：

Tex=wi/Ci=wiTi(qi)。

(3)

其中：Ci為節(jié)點i的處理能力,Ti(qi)表示節(jié)點i以qi的QoS等級處理單位工作負(fù)載所消耗的時間。

設(shè)Bi為移動設(shè)備與邊緣節(jié)點i之間的數(shù)據(jù)傳輸速度,則任務(wù)vi數(shù)據(jù)傳輸所需的時間為：

(4)

總體工作負(fù)載的處理時間被定義為：

(5)

2.5 能耗模型

(6)

(7)

故此,移動設(shè)備的總能耗E為：

(8)

2.6 目標(biāo)函數(shù)

本文主要考慮在最小化移動設(shè)備總能耗的情況下,同時降低工作流執(zhí)行時間并滿足應(yīng)用程序?qū)Ψ?wù)質(zhì)量的要求,目標(biāo)函數(shù)表示為：

minE+αT。

s.t.

(9)

其中α為時間與能耗的權(quán)重因子,用于反映對于延時和能耗的偏好。用戶對能耗的要求越高,α的取值越低;反之,用戶對時延的要求越高,α的取值越高。系統(tǒng)可以通過調(diào)整α的取值針對不同應(yīng)用場景改善實際優(yōu)化效果。

3 基于服務(wù)質(zhì)量的能耗感知工作流卸載策略

本章提出一種基于服務(wù)質(zhì)量的能耗感知工作流卸載策略。該策略以非支配排序遺傳算法(NSGA-Ⅲ)[21]為基礎(chǔ),結(jié)合基于服務(wù)質(zhì)量的能耗感知(Energy Aware,EA)優(yōu)化方法降低生成卸載方案過程的復(fù)雜度,同時保證對移動設(shè)備能耗和延時的優(yōu)化。最后通過NSGA-Ⅲ算法生成調(diào)度方案,保證方案的全局優(yōu)化。下面分別從基于服務(wù)質(zhì)量的能耗感知優(yōu)化方法和EA-QoS卸載策略的流程進行介紹。

3.1 基于服務(wù)質(zhì)量的能耗感知優(yōu)化方法

在實際場景中,非線性處理時間Ti(qi)往往是QoS等級qi的凸函數(shù),因為Ti(qi)具有單調(diào)遞增的梯度,所以,當(dāng)Ti(qi)=aif(qi)時,對于一些αi>0和凸函數(shù)f,在滿足EA-QoS優(yōu)化約束下的最優(yōu)解中,工作流卸載的單位負(fù)載傳輸能耗較小的邊緣節(jié)點總是能獲得較高的QoS等級。

(10)

(11)

(12)

因此,根據(jù)以下等價鏈

(13)

可以得出 ：

(14)

(15)

3.2 EA-QoS算法步驟

EA-QoS卸載基于非支配排序遺傳算法實現(xiàn)[21]。非支配排序遺傳算法是一種隨機搜索算法,從初始種群出發(fā),經(jīng)過交叉、變異和最優(yōu)化選擇產(chǎn)生下一代種群,然后通過迭代找到期望目標(biāo)。EA-QoS算法首先對所有邊緣節(jié)點劃分QoS組,然后利用遺傳算法得到最優(yōu)任務(wù)調(diào)度方案,主要包括編碼、種群初始化、交叉和變異、初始選擇、優(yōu)化選擇5個步驟,EA-QoS卸載策略具體流程如圖2所示。

圖2 EA-QoS算法流程示意圖

(2)編碼策略 使用遺傳算法解決工作流任務(wù)卸載問題,需要將卸載策略轉(zhuǎn)化為算法中對應(yīng)的染色體編碼。假設(shè)某工作流可被分解為N個任務(wù),當(dāng)可卸載節(jié)點數(shù)量為h時,染色體編碼包括工作流的任務(wù)執(zhí)行順序V={v0,v1,…,vN},其中任務(wù)的執(zhí)行先后順序必須滿足任務(wù)的依賴關(guān)系;邊緣網(wǎng)絡(luò)中h+1個用于提供計算服務(wù)的節(jié)點Vm={vm0,vm1,vm2,…,vmh},其中vm0表示提交工作流的移動設(shè)備;分配給卸載節(jié)點的QoS級別QoS={q0,q1,…,qN},聚合的QoS等級必須滿足QoS約束。

(3)種群初始化 首先確定NSGA-Ⅲ的參數(shù),包括種群大小M,迭代的最大次數(shù)Max,交叉概率Cr和突變概率Cf。然后采用隨機法初始化任務(wù)調(diào)度位置和執(zhí)行順序。任務(wù)調(diào)度順序進行初始化時,應(yīng)考慮任務(wù)間的依賴關(guān)系,即初始化任務(wù)vi時,其前驅(qū)任務(wù)必須為已排序任務(wù)。

(4)交叉與變異 本文采用單點交叉法生成新個體,以交叉概率Cr隨機選取染色體交叉點。為避免“早熟”現(xiàn)象,通過變異概率Cf確定個體是否發(fā)生變異。然后隨機確定變異位置,并隨機生成一個除原位置之外的vmi(0≤vmi≤h)作為新的基因值。通過交叉和變異操作生成包含有效工作流遷移策略的子代Qt。

(5)初始選擇 選擇操作的目的是為下一次迭代篩選更優(yōu)秀的個體,保持種群大小在迭代前后一致以確保算法性能。EA-QoS卸載策略采用NSGA-Ⅲ中的非支配排序算法選擇性能表現(xiàn)優(yōu)秀的遷移策略個體。首先合并父種群與交叉變異產(chǎn)生的新種群得到Rt(|Rt|=2M)。然后通過計算個體適應(yīng)度確定支配與非支配關(guān)系。EA-QoS算法為聯(lián)合優(yōu)化能耗與延時,選取式(16)作為適應(yīng)度函數(shù)。

Fitness=E+αT。

(16)

對Rt進行非支配排序,首先計算Rt中個體對應(yīng)的移動設(shè)備能耗E和延時T,根據(jù)適應(yīng)度Fitness=E+αT,劃分Rt為若干非支配解層(F1,F2,…)。然后計算個體被其他解支配數(shù)ni和支配解集合SPi。將所有ni=0的個體納入當(dāng)前非支配解層Fj,并將其支配解集SPi中個體的被支配數(shù)nk減1,令j=j+1。重復(fù)上述過程,直到所有個體都被納入一個非支配解層。最后重復(fù)將最低非支配解層Fi納入臨時種群St中,直到|St|≥M。若|St|=M,則令新一代種群Pt+1=St,否則進行優(yōu)化選擇。

(17)

(18)

然后在截距為1的坐標(biāo)軸上進行劃分,使用結(jié)構(gòu)化參考點生成方法生成參考點。計算St中的染色體坐標(biāo)點到連線的垂直距離,從而將所有個體與參考點相關(guān)聯(lián)。根據(jù)參考點關(guān)聯(lián)的個體數(shù),隨機從Fl中選擇個體進入下一代種群Pt+1中,直到|Pt+1|=M。

EA-QoS卸載策略的流程如算法1所示。

算法1EA-QoS卸載策略。

輸入：QoS分組數(shù)K,可用節(jié)點Vm,種群大小M,最大迭代次數(shù)Max,變異概率Cf,交叉概率Cr;

輸出：Pt+1//遷移工作流策略。

1.任務(wù)分層

2.HEFT算法得到工作流就緒隊列

3.搜集節(jié)點信息并劃分為K組

4.設(shè)置卸載節(jié)點分組的QoS等級

5.生成初始種群

6.for t=1 to I do

7.QtRt=Pt∪Coross_Mutation(Pt)//交叉變異至個體數(shù)為2M

8.(F1,F2,…)=Non-dominate-sort(Rt)//非支配排序

9.while |St|

10.St=St∪Fiand i=i+1

11.end while

12.if|St|>M then//優(yōu)化選擇,維持遷移策略的多樣性

14.搜索E、T最小值并計算各點截距

15.對Fl中個體進行歸一化并關(guān)聯(lián)參考點

16.根據(jù)參考點選取k(k=M-|Pt+1|)個遷移策略加入Pt+1

17.else

18.Pt+1=St

19.end for

20.return Pt+1

4 仿真實驗評估

為了分析和評估EA-QoS的性能,本文首先在不同的QoS等級下進行任務(wù)調(diào)度,研究QoS等級對工作流的任務(wù)處理時間的影響。然后將EA-QoS與不采用近似計算的NSGA-Ⅲ算法[16]、粒子群優(yōu)化(Particle Swarm Optimization,PSO)算法[3]進行對比,研究引入QoS的優(yōu)化角度和遺傳算法對工作流調(diào)度能耗與延時的影響。最后為研究EA-QoS與其他調(diào)度策略之間的性能差異,分別選取4種策略作為比較對象,各算法說明如下：策略Ⅰ(B-QoS)：采用最高QoS等級均勻卸載;策略Ⅱ(R-QoS)：采用最低QoS等級均勻卸載;策略Ⅲ(E-QoS)：最小化傳輸能耗,單位負(fù)載傳輸能耗較小的節(jié)點分配更多的任務(wù);策略Ⅳ(T-QoS)：最大限度地減少響應(yīng)時間,調(diào)整節(jié)點的任務(wù)數(shù)量與強度來平衡負(fù)載。

4.1 實驗環(huán)境與實驗參數(shù)

實驗中MD與基站之間的距離是[1,200]的隨機變量(單位：m),MD與不同邊緣節(jié)點傳輸功率不同,MD的數(shù)據(jù)傳輸基準(zhǔn)功率Ptx=110 mW,MD的CPU基礎(chǔ)頻率為1.8 GHz,加速頻率為3.2 GHz,計算能力為900 mW。在仿真實驗中,采用DAG隨機生成的方式產(chǎn)生工作流,假定隨機生成的工作流任務(wù)滿足進行近似計算的需求,每個工作流任務(wù)數(shù)服從[10,110]的正態(tài)分布,工作流中的任務(wù)大小服從1～10之間的均勻分布(單位：kB),工作量W為0.1～1之間服從正態(tài)分布的隨機值(單位：GHz/s),節(jié)點的QoS分組K=3,最大迭代次數(shù)Max=500。邊緣節(jié)點的參數(shù)如表1所示。

表1 邊緣節(jié)點參數(shù)設(shè)置

4.2 QoS等級對任務(wù)處理時間的影響研究實驗

本節(jié)主要研究QoS等級對任務(wù)處理時間的影響,并量化QoS等級與單位任務(wù)處理時間的關(guān)系,實驗中針對圖像處理應(yīng)用定義了10個不同的QoS等級,并在每個不同的QoS等級下分別進行10次實驗,實驗結(jié)果如圖3所示。

圖3 不同QoS等級與處理時間關(guān)系圖

由實驗可知,QoS等級和單位任務(wù)處理時間呈凸函數(shù)關(guān)系。當(dāng)節(jié)點的QoS等級不斷增大時,當(dāng)前節(jié)點所需處理的工作量也不斷增大,故單位任務(wù)負(fù)載的處理時間逐漸增大。經(jīng)過后續(xù)的大量實驗測試,使用凸曲線擬合QoS等級和處理速度的誤差為9.1%左右。

4.3 QoS對能耗延時影響研究實驗

為探究引入QoS的角度對工作流設(shè)備能耗和任務(wù)處理時間的影響,本節(jié)采用不使用近似計算技術(shù)的NSGA-Ⅲ、PSO與EA-QoS策略進行比較,在表1所示的邊緣環(huán)境中,設(shè)置EA-QoS的α=200,QoS等級q=0.96,其他參數(shù)與NSGA-Ⅲ、PSO相同,初始種群也相同的情況下進行實驗。針對4組工作量逐漸增大的工作流WF1、WF2、WF3、WF4,3種方案的調(diào)度實驗結(jié)果如圖4所示。

圖4 相同環(huán)境下各算法能耗延時對比

在4組實驗中,NSGA-Ⅲ算法的性能表現(xiàn)要優(yōu)于通常的PSO算法,因為NSGA-Ⅲ算法能夠更快速地尋找多目標(biāo)優(yōu)化的全局最優(yōu)解,所以優(yōu)化效果優(yōu)于PSO。由圖4a中可以看出,EA-QoS策略在工作流卸載的能耗方面的表現(xiàn)始終優(yōu)于NSGA-Ⅲ和PSO,這是由于EA-QoS策略在任務(wù)卸載執(zhí)行的過程中通過設(shè)置QoS等級犧牲任務(wù)的部分準(zhǔn)確率,從而進一步降低移動設(shè)備的能耗。由圖4b可知,EA-QoS與NSGA-Ⅲ算法的任務(wù)處理時間的差距隨工作量增大而逐漸減小。原因在于為節(jié)點分配QoS等級消耗時間不變且占比逐漸減小,而QoS對任務(wù)處理時間的優(yōu)化效果隨任務(wù)計算量增大而增大。在大多數(shù)情況下,采用NSGA-Ⅲ算法相較于普通基因算法,都能帶來明顯的性能改善。而引入QoS的優(yōu)化角度能夠進一步使工作流的設(shè)備能耗降低8.98%～12.31%。

4.4 EA-QoS卸載策略性能研究實驗

本節(jié)主要研究EA-QoS和4種基本策略在最小化設(shè)備能耗和任務(wù)處理時間方面的表現(xiàn)。為探究不同用戶對能耗E和整體延時T的偏好對卸載策略性能的影響,實驗設(shè)置了4種不同的α等級以模擬從能耗敏感(α=50)到延時敏感(α=1 000)的場景,QoS等級設(shè)置為q=0.96。每組實驗分別運行30次,將結(jié)果取平均值并記錄。實驗結(jié)果如圖5所示。

圖5 不同α下各卸載策略性能對比

由實驗可知,在不同偏好的調(diào)度環(huán)境中,EA-QoS策略始終擁有相對較好的性能表現(xiàn)。由圖5中優(yōu)化目標(biāo)實驗結(jié)果中可以看出,EA-QoS策略的優(yōu)化目標(biāo)始終優(yōu)于其他算法,其原因在于,EA-QoS策略綜合考慮了任務(wù)執(zhí)行時間與能耗關(guān)系,優(yōu)化了任務(wù)卸載策略,如將任務(wù)中計算量較大、QoS等級要求較高的任務(wù)卸載至高性能低傳輸能耗的節(jié)點執(zhí)行,可以降低任務(wù)整體延時并減少能耗。在該場景中,EA-QoS策略的性能相對其他4種基礎(chǔ)策略提高了43%～87%。

為進一步探究EA-QoS的實際性能表現(xiàn),實驗測量圖5對應(yīng)的4組模擬實驗中,邊緣節(jié)點的工作負(fù)載與QoS等級的分配情況。qi為分配給邊緣節(jié)點i的QoS等級,wi為該節(jié)點所分配的工作量,實驗詳細(xì)設(shè)置如表2所示。

表2 各算法工作負(fù)載與QoS等級分配情況

由表2可知,EA-QoS算法通過優(yōu)化工作量分配和為邊緣節(jié)點分配不同的QoS等級,實現(xiàn)了如圖5所示的降低能耗與延時的整體性能提升。通過對比策略Ⅰ、Ⅱ可知,當(dāng)將QoS等級從1放寬到0.96時,近似計算能夠降低應(yīng)用的時延與能耗。此外,通過比較策略Ⅱ、Ⅳ與EA-QoS算法的實際表現(xiàn)可以看出,EA-QoS算法相對于其他兩種策略對能耗和時延的聯(lián)合優(yōu)化擁有更好的性能表現(xiàn)。

4.5 網(wǎng)絡(luò)規(guī)模對EA-QoS的影響研究

為探究不同網(wǎng)絡(luò)規(guī)模對于EA-QoS策略的影響,實驗首先使用表1中的參數(shù)設(shè)置4個邊緣節(jié)點,然后對工作流進行調(diào)度,測量能耗與延時情況,重復(fù)10次取平均值。實驗完成后,在實驗環(huán)境中添加4個邊緣節(jié)點,參數(shù)與表1一致,進行下一次實驗。重復(fù)上述步驟,直至環(huán)境中邊緣節(jié)點個數(shù)達到40。實驗主要測試了α=50,α=200和α=800時設(shè)備的能耗與任務(wù)延時情況,實驗結(jié)果如圖6所示。

圖6 不同節(jié)點數(shù)量對EA-QoS算法的影響圖

從實驗中可以看出,隨著可用邊緣節(jié)點數(shù)量的增加,實現(xiàn)的優(yōu)化目標(biāo)E+αT值不斷減小,說明EA-QoS能夠有效利用邊緣環(huán)境中的可用資源來進行任務(wù)調(diào)度。在α值較高的調(diào)度方案中,時間的權(quán)重比例較大,增加節(jié)點能夠提供更多的優(yōu)質(zhì)節(jié)點選擇,使任務(wù)執(zhí)行時間大幅降低,故在α=800時,增加節(jié)點帶來的收益最大,而在α=50時,增加節(jié)點帶來的收益最小。當(dāng)α一定時,隨著邊緣節(jié)點數(shù)增大,增加邊緣節(jié)點帶來的收益增量在不斷減小,其原因在于,當(dāng)邊緣節(jié)點數(shù)增加時,任務(wù)劃分?jǐn)?shù)量增多能夠減少一部分的執(zhí)行延時,但傳輸時間不可避免,且不能無限劃分任務(wù),當(dāng)任務(wù)工作量到某個臨界值時,任務(wù)執(zhí)行延時達到最低,此時工作流結(jié)束時間主要由數(shù)據(jù)傳輸時間決定。此外,由于協(xié)議和通信開銷,有效數(shù)據(jù)傳輸?shù)臅r間比例變小,將工作負(fù)載分配給更多的邊緣節(jié)點也可能導(dǎo)致更高的能耗。

5 結(jié)束語

為進一步降低工作流卸載的能耗與延時,本文結(jié)合近似計算優(yōu)化處理工作流任務(wù),通過引入服務(wù)質(zhì)量(QoS)的優(yōu)化角度,限制任務(wù)準(zhǔn)確度損失,并在此基礎(chǔ)上考慮了不同場景下平衡移動設(shè)備的能耗與任務(wù)時延的問題,提出一種基于服務(wù)質(zhì)量的能耗感知工作流卸載策略。該策略利用HEFT算法對工作流任務(wù)分層進行拓?fù)渑判?保證遺傳編碼對應(yīng)遷移策略的有效性;基于QoS的能耗感知優(yōu)化降低了分配QoS等級的復(fù)雜度;結(jié)合NSGA-Ⅲ算法,加快了尋找全局最優(yōu)解的速度。仿真實驗結(jié)果表明,EA-QoS策略由于引入了QoS的優(yōu)化角度,能夠有效降低移動設(shè)備能耗并減少工作流延時,并且其結(jié)合NSGA-Ⅲ算法生成的卸載策略較4種基礎(chǔ)QoS卸載策略,能耗與延時的優(yōu)化效果顯著。未來的工作中,期望能夠進一步改進EA-QoS卸載策略,在該策略中考慮多用戶的工作流租用成本問題與卸載過程中的安全問題,并結(jié)合工作流調(diào)度歷史進行研究。