云輔助移動(dòng)邊緣計(jì)算中的計(jì)算卸載策略

王 妍,葛海波,馮安琪

(西安郵電大學(xué) 電子工程學(xué)院,西安 710121)

0 概述

隨著移動(dòng)設(shè)備的普及,計(jì)算密集型、時(shí)延敏感型等新興移動(dòng)應(yīng)用不斷涌現(xiàn)并迅速受到用戶的青睞,如增強(qiáng)現(xiàn)實(shí)、圖像識(shí)別、網(wǎng)絡(luò)游戲、車聯(lián)網(wǎng)等[1]。這類新興的應(yīng)用通常需要消耗大量的計(jì)算資源,以滿足低時(shí)延需求。然而,資源有限的移動(dòng)設(shè)備很難滿足上述移動(dòng)應(yīng)用的需求[2]。計(jì)算卸載是一種有效的解決方案,通過(guò)卸載計(jì)算任務(wù)到云服務(wù)器或者邊緣服務(wù)器,從而達(dá)到緩解計(jì)算和存儲(chǔ)的限制、降低時(shí)延的目的。移動(dòng)云計(jì)算(Mobile Cloud Computing,MCC)被認(rèn)為是一種很有效的卸載計(jì)算任務(wù)的方法,其強(qiáng)大的計(jì)算能力可以顯著降低移動(dòng)服務(wù)的處理時(shí)延。然而,將計(jì)算任務(wù)卸載到空間上遠(yuǎn)離移動(dòng)設(shè)備的云服務(wù)器上會(huì)造成較高的傳輸時(shí)延,增加能量消耗。為了解決云計(jì)算卸載過(guò)程中面臨的高傳輸時(shí)延等問(wèn)題,移動(dòng)邊緣計(jì)算(Mobile Edge Computing,MEC)應(yīng)運(yùn)而生[3],MEC的核心思想是將服務(wù)器的計(jì)算和存儲(chǔ)資源遷移到移動(dòng)設(shè)備附近,降低移動(dòng)服務(wù)處理過(guò)程中的傳輸時(shí)延、處理時(shí)延,減少能量消耗。移動(dòng)邊緣計(jì)算是移動(dòng)云計(jì)算的一種特殊情況。

在計(jì)算卸載問(wèn)題中,MCC和MEC各有利弊,適用于不同的移動(dòng)服務(wù)[4]。當(dāng)面臨延遲敏感任務(wù)時(shí),MEC以其靠近移動(dòng)設(shè)備、傳輸延遲短的優(yōu)點(diǎn),可以提供比MCC更好的服務(wù),當(dāng)處理非延遲敏感任務(wù)時(shí),則會(huì)突出MCC中計(jì)算資源豐富的優(yōu)勢(shì)。因此,MCC和MEC兩者應(yīng)相互協(xié)調(diào)、相互補(bǔ)充,確保計(jì)算卸載策略能滿足不同的應(yīng)用場(chǎng)景。

本文綜合考慮MCC計(jì)算資源豐富以及MEC靠近移動(dòng)設(shè)備的優(yōu)勢(shì),提出一種云輔助移動(dòng)邊緣計(jì)算的計(jì)算卸載策略(CAME),在此基礎(chǔ)上,設(shè)計(jì)基于改進(jìn)遺傳算法的計(jì)算卸載算法(CAMEGA),優(yōu)化移動(dòng)服務(wù)的運(yùn)行時(shí)間和設(shè)備能耗,從而得到系統(tǒng)總代價(jià)較優(yōu)的計(jì)算卸載策略。

1 相關(guān)研究

計(jì)算卸載是研究MEC的關(guān)鍵問(wèn)題之一。近年來(lái),研究人員對(duì)MEC中的計(jì)算卸載問(wèn)題進(jìn)行了大量研究,并且取得了突破性的進(jìn)展。這些研究旨在探索制定最佳卸載決策,達(dá)到降低時(shí)延和節(jié)省移動(dòng)設(shè)備能耗的目的。文獻(xiàn)[5]利用馬爾科夫鏈理論分析給定計(jì)算任務(wù)的時(shí)延,運(yùn)用一維搜索算法尋找時(shí)延最小的計(jì)算卸載策略。文獻(xiàn)[6]研究在移動(dòng)邊緣計(jì)算環(huán)境下,卸載延時(shí)和可靠性之間的權(quán)衡問(wèn)題,利用基于啟發(fā)式搜索、重構(gòu)造線性化技術(shù)和半定松弛3種算法,實(shí)現(xiàn)系統(tǒng)延時(shí)和卸載失敗率最小。文獻(xiàn)[7]運(yùn)用排隊(duì)網(wǎng)絡(luò)的方法分析系統(tǒng)時(shí)延,提出一種具有線性復(fù)雜度的算法,該算法能顯著降低系統(tǒng)時(shí)延。文獻(xiàn)[8]提出一種基于李亞普諾夫的動(dòng)態(tài)卸載算法,在滿足指定應(yīng)用程序?qū)r(shí)延要求的前提下,實(shí)現(xiàn)系統(tǒng)節(jié)能。文獻(xiàn)[9]研究一個(gè)帶有能量收集器件的MEC系統(tǒng),提出基于李亞普諾夫優(yōu)化的動(dòng)態(tài)計(jì)算卸載算法,實(shí)現(xiàn)應(yīng)用程序的執(zhí)行延遲最小。文獻(xiàn)[10]提出一種細(xì)粒度卸載策略,將任務(wù)卸載問(wèn)題表示為一個(gè)有約束的0-1規(guī)劃問(wèn)題,采用BPSO算法,旨在滿足嚴(yán)格的延時(shí)約束的同時(shí),最大限度地減少能量消耗。文獻(xiàn)[11]研究了由多個(gè)用戶組成的移動(dòng)邊緣計(jì)算卸載系統(tǒng)中的資源分配問(wèn)題,將最優(yōu)資源分配問(wèn)題表示為一個(gè)凸優(yōu)化問(wèn)題,實(shí)現(xiàn)在滿足時(shí)延要求的條件下,移動(dòng)設(shè)備能耗最小。文獻(xiàn)[12]提出一種面向優(yōu)先級(jí)業(yè)務(wù)的邊緣計(jì)算資源分配方法,根據(jù)業(yè)務(wù)價(jià)值賦予相應(yīng)的優(yōu)先級(jí),對(duì)不同優(yōu)先級(jí)的任務(wù)進(jìn)行加權(quán)資源分配,旨在降低業(yè)務(wù)的執(zhí)行時(shí)間和能耗。文獻(xiàn)[13]提出基于拉格朗日的計(jì)算卸載策略,將移動(dòng)邊緣計(jì)算框架下的計(jì)算卸載問(wèn)題建模為一個(gè)凸優(yōu)化問(wèn)題,采用拉格朗日乘子法優(yōu)化移動(dòng)終端總的計(jì)算時(shí)間和能耗。文獻(xiàn)[14]采用云輔助移動(dòng)邊緣計(jì)算框架,旨在以最小的系統(tǒng)成本保證用戶服務(wù)質(zhì)量。文獻(xiàn)[15]提出一種新的異構(gòu)網(wǎng)絡(luò)兩層計(jì)算卸載框架?；诖丝蚣?設(shè)計(jì)有效的計(jì)算卸載方案,以使總體能耗最小化。文獻(xiàn)[16]提出一個(gè)云、MEC和LoT集成的融合框架,解決MEC面臨的可擴(kuò)展問(wèn)題,設(shè)計(jì)了一個(gè)選擇卸載方案,在滿足時(shí)延要求的條件下實(shí)現(xiàn)移動(dòng)設(shè)備能耗最小。文獻(xiàn)[17]提出一種資源優(yōu)化方法來(lái)最小化多天線接入點(diǎn)的能耗。文獻(xiàn)研究總結(jié)如表1所示,其中,√為是,×為否。

表1 不同方案的計(jì)算卸載策略

上述對(duì)于移動(dòng)邊緣計(jì)算環(huán)境下的計(jì)算卸載問(wèn)題的研究工作,大部分只是將能耗或時(shí)延其中一項(xiàng)作為優(yōu)化目標(biāo),或者沒(méi)有考慮任務(wù)之間的數(shù)據(jù)依賴關(guān)系和順序依賴關(guān)系。此外,大部分研究集中于應(yīng)用MEC或MCC來(lái)卸載計(jì)算任務(wù),并未考慮兩者之間的協(xié)作。很少有文獻(xiàn)在綜合考慮以上3種情況的基礎(chǔ)上研究計(jì)算卸載問(wèn)題,這就導(dǎo)致設(shè)計(jì)的卸載策略局限性較大。因此,設(shè)計(jì)一個(gè)適用于不同移動(dòng)服務(wù)的計(jì)算卸載策略成為計(jì)算卸載問(wèn)題中的難點(diǎn)。為了解決上述問(wèn)題,本文提出CAMEGA計(jì)算卸載算法。主要工作如下:

1)綜合考慮MEC傳輸時(shí)延低、計(jì)算能力有限而MCC傳輸時(shí)延高、計(jì)算資源豐富的特點(diǎn),提出云輔助移動(dòng)邊緣計(jì)算的計(jì)算卸載框架(CAME)。

2)考慮到任務(wù)之間的依賴關(guān)系,將復(fù)雜的移動(dòng)服務(wù)簡(jiǎn)化為具有優(yōu)先約束關(guān)系的工作流模型處理。

3)設(shè)計(jì)基于改進(jìn)遺傳算法的計(jì)算卸載算法(CAEMGA),利用改進(jìn)遺傳算法循環(huán)得到最優(yōu)卸載策略,最小化移動(dòng)服務(wù)總的執(zhí)行時(shí)間和能耗。

2 系統(tǒng)模型

本節(jié)主要闡述系統(tǒng)模型,系統(tǒng)模型主要包括移動(dòng)服務(wù)模型和計(jì)算卸載模型。

2.1 移動(dòng)服務(wù)模型

本文主要研究云輔助移動(dòng)邊緣計(jì)算環(huán)境下單用戶單個(gè)移動(dòng)服務(wù)的計(jì)算卸載問(wèn)題。將復(fù)雜的移動(dòng)服務(wù)簡(jiǎn)化為具有優(yōu)先約束關(guān)系的工作流模型處理。用S={s1,s2,…,si,…,sn}表示工作流中任務(wù)的集合,n為任務(wù)的數(shù)量,用戶可以通過(guò)調(diào)整任務(wù)的數(shù)量以及任務(wù)間的依賴關(guān)系來(lái)模擬各種各樣的移動(dòng)服務(wù)。每個(gè)任務(wù)被建模為一個(gè)二元組{αi,βi},其中,αi為第i個(gè)任務(wù)的工作量,βi為輸出數(shù)據(jù)量。

在移動(dòng)服務(wù)的運(yùn)行過(guò)程中,本地設(shè)備輸入數(shù)據(jù),第一個(gè)任務(wù)從本地設(shè)備獲取數(shù)據(jù),因此第一個(gè)任務(wù)必須在本地設(shè)備中執(zhí)行。類似地,當(dāng)移動(dòng)服務(wù)運(yùn)行完后,應(yīng)該把輸出數(shù)據(jù)傳回本地設(shè)備,最后一個(gè)任務(wù)也必須在本地執(zhí)行。

2.2 計(jì)算卸載模型

計(jì)算卸載模型如圖1所示,移動(dòng)設(shè)備通過(guò)移動(dòng)網(wǎng)絡(luò)連接到基站。當(dāng)移動(dòng)設(shè)備運(yùn)行移動(dòng)服務(wù)時(shí),可以將工作流中的任務(wù)卸載到邊緣服務(wù)器或云服務(wù)器中執(zhí)行。邊緣服務(wù)器和云服務(wù)器接收來(lái)自移動(dòng)用戶的請(qǐng)求并處理,最后將處理結(jié)果返回給移動(dòng)用戶。移動(dòng)用戶可以根據(jù)移動(dòng)服務(wù)的需求選擇任務(wù)部分卸載或者完全卸載。由圖1可知,用戶U3將工作流中第2個(gè)任務(wù)卸載至邊緣服務(wù)器中執(zhí)行,將第3個(gè)任務(wù)卸載至云服務(wù)器中執(zhí)行,第1個(gè)和第4個(gè)任務(wù)在本地設(shè)備執(zhí)行。

圖1 計(jì)算卸載模型Fig.1 Computation offloading model

邊緣服務(wù)器可通過(guò)一個(gè)二元組E={Ce,Fe},其中,Ce為邊緣服務(wù)器處理1 bit數(shù)據(jù)所需的CPU周期數(shù),Fe為邊緣服務(wù)器計(jì)算能力。

云服務(wù)器可通過(guò)一個(gè)二元組E={Cc,Fc},其中用Cc表示云服務(wù)器處理1bit數(shù)據(jù)所需的CPU周期數(shù),Fc為云服務(wù)器計(jì)算能力。

3 問(wèn)題分析

圖2展示了一個(gè)由9個(gè)任務(wù)組成的移動(dòng)服務(wù)工作流,這9個(gè)任務(wù)的執(zhí)行順序具有優(yōu)先約束關(guān)系,箭頭表示任務(wù)執(zhí)行的先后順序,這些任務(wù)可以在本地設(shè)備、邊緣服務(wù)器或云服務(wù)器中執(zhí)行。由圖2可以看出,任務(wù)S1、S2、S5、S9在本地執(zhí)行,S3、S4、S7在邊緣服務(wù)器中執(zhí)行,S6、S8在云服務(wù)器中執(zhí)行。

圖2 任務(wù)卸載模型Fig.2 Task offloading model

本文旨在制定最佳的卸載策略,實(shí)現(xiàn)工作流的執(zhí)行時(shí)間和移動(dòng)設(shè)備的能耗最小。因此,將目標(biāo)函數(shù)定義為工作流執(zhí)行時(shí)間和能耗的加權(quán)和。

F=ωT+(1-ω)E

(1)

其中,E為執(zhí)行工作流服務(wù)過(guò)程中移動(dòng)設(shè)備的總能耗,T為工作流執(zhí)行的總時(shí)間,ω為時(shí)延權(quán)重系數(shù),1-ω為能耗權(quán)重系數(shù)。ω可根據(jù)移動(dòng)服務(wù)的需求及移動(dòng)設(shè)備的狀態(tài)來(lái)設(shè)置,例如,當(dāng)運(yùn)行延時(shí)敏感型移動(dòng)服務(wù)時(shí),可以適當(dāng)增加ω的值,當(dāng)移動(dòng)設(shè)備電量不足時(shí),ω必須設(shè)置為較小的值。本文以時(shí)延敏感型移動(dòng)服務(wù)為例,ω取0.8。

按照如下方式計(jì)算目標(biāo)函數(shù)中的分量:

1)任務(wù)i在本地執(zhí)行的計(jì)算時(shí)間為:

(2)

任務(wù)i在本地執(zhí)行的能耗為:

El=Tl×Pl

(3)

2)任務(wù)i從本地卸載至邊緣服務(wù)器的總時(shí)間為:

(4)

任務(wù)i從本地卸載至邊緣服務(wù)器的總能耗為:

(5)

3)任務(wù)i從本地設(shè)備卸載至云服務(wù)器的總時(shí)間為:

(6)

任務(wù)i從本地設(shè)備卸載至云服務(wù)器的總能耗為:

(7)

綜上所述,移動(dòng)服務(wù)運(yùn)行的總時(shí)間和移動(dòng)設(shè)備的總能耗可以表述為:

(8)

(9)

4 卸載算法設(shè)計(jì)

目前,研究人員使用智能算法解決優(yōu)化問(wèn)題[18-19]。本文選擇遺傳算法作為基礎(chǔ)算法,部分修改傳統(tǒng)遺傳算法,以滿足計(jì)算卸載問(wèn)題的特殊需求[20-21]。

在云輔助移動(dòng)邊緣計(jì)算的計(jì)算卸載系統(tǒng)中,移動(dòng)服務(wù)工作流中的每個(gè)任務(wù)可在不同服務(wù)器上執(zhí)行(本地、邊緣、云),這些服務(wù)器具有不同的計(jì)算能力,所以不同的執(zhí)行位置會(huì)造成不同的執(zhí)行時(shí)間和設(shè)備能耗。此外,當(dāng)工作流中包含大量任務(wù)數(shù)時(shí),會(huì)出現(xiàn)多個(gè)任務(wù)同時(shí)競(jìng)爭(zhēng)一個(gè)計(jì)算資源的情況。因此,本文采用排序任務(wù)的執(zhí)行順序來(lái)解決這個(gè)問(wèn)題?？紤]以上兩點(diǎn),本文主要關(guān)注任務(wù)的執(zhí)行位置和執(zhí)行順序兩組變量,這兩組變量相互影響,共同決定卸載策略。如果分開(kāi)優(yōu)化每組變量,將不能得到最優(yōu)卸載策略。本文采用改進(jìn)遺傳算法,即嵌套遺傳算法,同時(shí)優(yōu)化任務(wù)執(zhí)行順序和執(zhí)行位置。

4.1 編碼

本文采用改進(jìn)浮點(diǎn)數(shù)編碼的編碼方式。與傳統(tǒng)的浮點(diǎn)數(shù)編碼不同的是,分別讓浮點(diǎn)數(shù)整數(shù)和小數(shù)部分映射不同的個(gè)體特征,即一種基因型映射兩種表現(xiàn)型,這樣編碼能夠降低算法復(fù)雜度,提高運(yùn)算效率。假設(shè)n為任務(wù)總數(shù),用集合X.Y={x1.y1,x2.y2,…,xi.yi,…,xn.yn}表示任務(wù)執(zhí)行順序和執(zhí)行位置,其中整數(shù)部分xi表示工作流中的某個(gè)任務(wù),小數(shù)部分yi表示任務(wù)xi∈{s0,s1,s2,…,si,…,sn-1}的執(zhí)行位置,yi=0表示任務(wù)在本地設(shè)備執(zhí)行,yi=1表示任務(wù)在邊緣服務(wù)器執(zhí)行,yi=2表示任務(wù)在云服務(wù)器執(zhí)行。圖3描述的是編碼方案示例。

圖3 編碼方案示例Fig.3 Example of encoding scheme

4.2 適應(yīng)度函數(shù)

在遺傳算法中,適應(yīng)度是描述個(gè)體性能的主要指標(biāo),適應(yīng)度越大,個(gè)體越優(yōu)秀。根據(jù)適應(yīng)度的大小,對(duì)個(gè)體進(jìn)行優(yōu)勝劣汰。本文關(guān)注的問(wèn)題是搜尋最優(yōu)卸載策略,實(shí)現(xiàn)移動(dòng)服務(wù)工作流的執(zhí)行時(shí)間與能耗的加權(quán)和最小化。因此,使用目標(biāo)函數(shù)的倒數(shù)計(jì)算工作流的適應(yīng)度值。

4.3 初始化

由于任務(wù)之間有一定的順序關(guān)系,因此借助優(yōu)先約束矩陣PCM來(lái)初始化任務(wù)的執(zhí)行順序。PCM是一個(gè)n×n矩陣,用D表示,Dij表示工作流中第i個(gè)任務(wù)與第j個(gè)任務(wù)的約束關(guān)系。當(dāng)Dij=0時(shí)表示任務(wù)i和任務(wù)j沒(méi)有優(yōu)先約束關(guān)系,可以同時(shí)執(zhí)行;Dij=1表示任務(wù)i必須先執(zhí)行;Dij=-1表示任務(wù)j必須先執(zhí)行?？梢愿鶕?jù)任務(wù)的數(shù)量及任務(wù)之間的具體依賴關(guān)系自定義PCM矩陣,圖4為圖2中9個(gè)任務(wù)的優(yōu)先約束矩陣。

圖4 優(yōu)先約束矩陣

具體的操作步驟為:每次選取沒(méi)有先序任務(wù)或先序任務(wù)已經(jīng)排序完畢的任務(wù),即選取優(yōu)先約束矩陣中所有Cij不等于-1的行數(shù),然后把優(yōu)先約束矩陣中與所選取任務(wù)相關(guān)的行和列都置為0,即選取任務(wù)Si后,將Cij、Cji都置為0。按照此方法繼續(xù)選取下一任務(wù),直到形成一組可行任務(wù)序列。循環(huán)N次形成初始種群,N為種群規(guī)模。

完成任務(wù)執(zhí)行順序初始化后,進(jìn)行任務(wù)執(zhí)行位置初始化。隨機(jī)產(chǎn)生0.0、0.1、0.2中的一個(gè)數(shù),如果產(chǎn)生為0.0,則表示任務(wù)在本地設(shè)備執(zhí)行,同理,產(chǎn)生0.1、0.2分別表示在邊緣服務(wù)器或云服務(wù)器中執(zhí)行。

4.4 交叉

采用傳統(tǒng)的單點(diǎn)交叉法,進(jìn)行任務(wù)執(zhí)行位置的交叉操作,經(jīng)過(guò)交叉操作后,得到新的個(gè)體X1.Y12和X2.Y21。

算法1排序交叉算法

輸入完成位置交叉操作的任務(wù)序列

輸出完成整體交叉操作的任務(wù)序列

Begin

1.生成[1,n]之間的隨機(jī)數(shù)r;

3.X12.Y12=X21.Y211≠φ

4.for i=1 to r

6.end for

8.for i=1 to r

10.end for

12.for i=1 to n+r

13.for m=1 to n

16.else

18.end if

19.end for

20.for i=1 to n+r

21.for m=1 to n

24.else

26.end if

27.end for

任務(wù)執(zhí)行順序變異過(guò)程如圖5所示。

圖5 任務(wù)執(zhí)行順序變異過(guò)程1Fig.5 Mutation process 1 of task execution sequence

4.5 變異

變異操作是將染色體中的某個(gè)基因值做出變動(dòng)。隨機(jī)選取任務(wù)序列中一個(gè)任務(wù)作為變異點(diǎn),以突變概率決定是否進(jìn)行變異,若變異,則任務(wù)執(zhí)行位置變?yōu)槌?dāng)前執(zhí)行位置之外的任一位置,即基因小數(shù)部分0變?yōu)?或2、1變?yōu)?或2、2變?yōu)?或1。

在執(zhí)行任務(wù)執(zhí)行順序的變異操作時(shí),同樣需要考慮任務(wù)之間的優(yōu)先約束關(guān)系。從任務(wù)集合X.Y中隨機(jī)選取一個(gè)任務(wù)xi.yi作為變異點(diǎn),在任務(wù)集合X.Y中,以xi.yi為中心,分別往正反方向查找,直到找到xi.yi所有的先序任務(wù)集合{x1.y1,x2.y2,…,xa.ya}和后繼任務(wù)集合{xb.yb,xb+1.yb+1,…,xn.yn}。最后,在不包含xi.yi的先序任務(wù)和后繼任務(wù)的序列{xa+1.ya+1,xa+2.ya+2,…,xb+1.yb+1}中,隨機(jī)選取一個(gè)任務(wù),與xi.yi交換執(zhí)行順序。任務(wù)執(zhí)行順序的變異過(guò)程如圖6所示。

圖6 任務(wù)執(zhí)行順序變異過(guò)程2Fig.6 Mutation process 2 of task execution sequence

算法2排序變異算法

輸入完成位置變異的任務(wù)序列

輸出完成整體變異操作的任務(wù)序列

Begin

1.生成[1,n-1]之間隨機(jī)數(shù)r;

2.for i=1 to r

3.搜索xr.yr的先序任務(wù)集{x1.y1,x2.y2,…,xa.ya};

4.end for

5.for i=r to n-1

6.搜索xr.yr的后繼任務(wù){(diào)xb.yb,xb+1.yb+1,…,xn.yn};

7.end for

8.得到集合X′.Y′={xa+1.ya+1,xa+2.ya+2,…,xb+1.yb+1};

9.排出xr.yr當(dāng)前位置,在集合X′.Y′中隨機(jī)選擇位置插入

10.得到新個(gè)體

End

5 仿真實(shí)驗(yàn)與結(jié)果分析

本節(jié)對(duì)本文CAMEGA算法以及All-Local算法、Random算法、ECGA算法進(jìn)行了仿真對(duì)比實(shí)驗(yàn)。根據(jù)已有相關(guān)文獻(xiàn),遺傳算法相關(guān)參數(shù)由表2[23]給出,網(wǎng)絡(luò)仿真參數(shù)由表3給出,其中,任務(wù)工作量為服從[1,200]之間均勻分布(單位為GHz),輸出數(shù)據(jù)量為服從[1,50]之間均勻分布(單位為MB)。

表2 遺傳算法相關(guān)參數(shù)

表3 網(wǎng)絡(luò)仿真參數(shù)

All-Local算法:將所有的任務(wù)都放在移動(dòng)設(shè)備執(zhí)行。

Random算法:在云輔助移動(dòng)邊緣計(jì)算的計(jì)算卸載框架下,隨機(jī)分配任務(wù)的執(zhí)行位置(本地、邊緣、云)和執(zhí)行順序。

ECGA算法:移動(dòng)邊緣計(jì)算的計(jì)算卸載框架下,基于遺傳算法的計(jì)算卸載算法。

5.1 任務(wù)數(shù)變化對(duì)系統(tǒng)總代價(jià)的影響

本節(jié)主要研究在不同的工作流任務(wù)數(shù)量下,CAMEGA算法、All-Local算法、Random算法、ECGA算法的性能比較,模擬的任務(wù)數(shù)分別為30、60、90、120和150的情況。如圖7所示,隨著工作流中任務(wù)數(shù)的增加,系統(tǒng)的總代價(jià)逐漸增加。與All-Local算法、Random算法、ECGA算法相比,CAMEGA算法的系統(tǒng)總代價(jià)最小,約為All-Local算法的8.4%、Random算法的43.7%、ECGA算法的30%。因此,在計(jì)算卸載問(wèn)題中,CAMEGA算法有較大的優(yōu)勢(shì)。

圖7 任務(wù)數(shù)變化對(duì)系統(tǒng)總代價(jià)的影響Fig.7 Impact of task number changes on total system cost

5.2 時(shí)延權(quán)重變化對(duì)系統(tǒng)總代價(jià)的影響

本節(jié)主要研究時(shí)延權(quán)重ω與能耗權(quán)重1-ω的比值大小在[0.01,100]時(shí),CAMEGA算法、All-Local算法、ECGA算法與Random算法4種算法的性能比較。如圖8所示,針對(duì)不同的時(shí)延和能耗比值,本文提出的CAMEGA算法得到的結(jié)果明顯優(yōu)于其他3種算法。因此,CAMEGA算法可以更好地適用于需求不同的移動(dòng)服務(wù)。

圖8 時(shí)延權(quán)重與能耗權(quán)重的比值對(duì)系統(tǒng)總代價(jià)的影響Fig.8 Effect of ratio of delay weight to energy consumption weight on total system cost

5.3 迭代次數(shù)對(duì)系統(tǒng)總代價(jià)的影響

本節(jié)主要研究迭代次數(shù)在[10,100]時(shí),迭代次數(shù)的變化對(duì)系統(tǒng)總代價(jià)的影響。取移動(dòng)服務(wù)工作流中的任務(wù)數(shù)N=60,如圖9所示,隨著迭代次數(shù)的增加,All-Local算法得到的實(shí)驗(yàn)結(jié)果幾乎沒(méi)有變化(略去),基于CAMEGA算法、Random算法、ECGA算法的系統(tǒng)總代價(jià)值呈下降趨勢(shì),當(dāng)?shù)螖?shù)在[10,100]時(shí),系統(tǒng)總代價(jià)的下降趨勢(shì)較大,迭代次數(shù)超過(guò)50以后,系統(tǒng)總代價(jià)的變化趨勢(shì)很小、趨于穩(wěn)定。由此可以得出,迭代次數(shù)取50時(shí),可以得到較優(yōu)的實(shí)驗(yàn)結(jié)果。

圖9 迭代次數(shù)對(duì)系統(tǒng)總代價(jià)的影響Fig.9 Impact of workload changes on total system cost

5.4 工作量變化對(duì)系統(tǒng)總代價(jià)的影響

本節(jié)主要研究任務(wù)工作量在[0,200]之間時(shí)系統(tǒng)總代價(jià)的變化。從圖10可以看出,隨著任務(wù)工作量的增加,系統(tǒng)總代價(jià)也在逐漸增加。這是因?yàn)樵诒镜卦O(shè)備、邊緣服務(wù)器、云服務(wù)器的計(jì)算能力不變的情況下,增加任務(wù)的輸入數(shù)據(jù)量必然會(huì)導(dǎo)致執(zhí)行時(shí)間變長(zhǎng),從而系統(tǒng)總代價(jià)變大。同樣,CAMEGA算法得到的系統(tǒng)總代價(jià)明顯小于All-Local算法、Random算法和ECGA算法。

圖10 工作量變化對(duì)系統(tǒng)總代價(jià)的影響Fig.10 Impact of workload changes on total system cost

5.5 任務(wù)輸出數(shù)據(jù)量變化對(duì)系統(tǒng)總代價(jià)的影響

本節(jié)主要研究工作流任務(wù)的輸出數(shù)據(jù)在[10,50]時(shí),4種算法的系統(tǒng)總代價(jià)的變化。如圖11所示,對(duì)于All-Local算法,隨著任務(wù)輸出數(shù)據(jù)量的增加,All-Local算法的系統(tǒng)總代價(jià)幾乎沒(méi)有變化,這是由于在All-Local算法中,移動(dòng)服務(wù)中所有任務(wù)都在本地執(zhí)行,不存在數(shù)據(jù)上傳/下載過(guò)程,也就不存在傳輸時(shí)延和傳輸能耗。對(duì)于Random算法、ECGA算法和CAMEGA算法,任務(wù)的輸出數(shù)據(jù)量越大,系統(tǒng)總代價(jià)越大。這是因?yàn)槿蝿?wù)的輸出數(shù)據(jù)量對(duì)于工作流執(zhí)行過(guò)程中的上傳/下載的時(shí)延和能耗都會(huì)產(chǎn)生較大的影響。在同樣的卸載策略下,較大的數(shù)據(jù)傳輸量會(huì)花費(fèi)較長(zhǎng)的時(shí)間。同樣,較大的數(shù)據(jù)傳輸量會(huì)給移動(dòng)設(shè)備帶來(lái)更多的傳輸能耗。

圖11 輸出數(shù)據(jù)量對(duì)系統(tǒng)總代價(jià)的影響Fig.11 Impact of amount of output data on total system cost

綜合上述分析可以看出,與All-Local算法、Random算法和ECGA算法相比,本文提出的CAMEGA算法均能得到最小的系統(tǒng)總代價(jià)。

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

本文針對(duì)移動(dòng)服務(wù)的執(zhí)行時(shí)間和移動(dòng)設(shè)備能耗的優(yōu)化問(wèn)題進(jìn)行研究,設(shè)計(jì)云輔助移動(dòng)邊緣計(jì)算的計(jì)算卸載框架,并提出基于改進(jìn)遺傳算法的計(jì)算卸載算法。通過(guò)選擇、交叉、變異等遺傳操作,迭代得到最優(yōu)的卸載策略,實(shí)現(xiàn)系統(tǒng)總代價(jià)最小。仿真結(jié)果表明,與All-Local算法、Random算法和ECGA算法相比,CAMEGA算法系統(tǒng)總代價(jià)最小。下一步工作將對(duì)包含多個(gè)移動(dòng)設(shè)備、邊緣服務(wù)器和云服務(wù)器等系統(tǒng)中的計(jì)算卸載問(wèn)題進(jìn)行研究。