陳 韓, 張 晶,3,*, 董 俊, 董 潔

(1. 南京郵電大學(xué)通信與信息工程學(xué)院, 江蘇 南京 210003; 2. 南京郵電大學(xué)江蘇省無(wú)線(xiàn)通信重點(diǎn)實(shí)驗(yàn)室, 江蘇 南京 210003; 3. 南京郵電大學(xué)物聯(lián)網(wǎng)研究院, 江蘇 南京 210003;4. 中國(guó)科學(xué)院合肥物質(zhì)科學(xué)研究院智能機(jī)械研究所, 安徽 合肥 230031;5. 安徽中科德技智能科技有限公司, 安徽 合肥 230031; 6. 國(guó)家無(wú)線(xiàn)電監(jiān)測(cè)中心, 北京 100037)

0 引 言

隨著5G時(shí)代的來(lái)臨,移動(dòng)通信與物聯(lián)網(wǎng)加速融合,集中式處理的云計(jì)算已經(jīng)滿(mǎn)足不了多行業(yè)的分布式應(yīng)用需求[1-2],移動(dòng)邊緣計(jì)算(mobile edge computing,MEC)應(yīng)運(yùn)而生。MEC技術(shù)將分布式計(jì)算能力置于移動(dòng)網(wǎng)絡(luò)邊緣,利用無(wú)線(xiàn)接入網(wǎng)絡(luò)為用戶(hù)提供互聯(lián)網(wǎng)技術(shù)服務(wù)和計(jì)算功能,加速網(wǎng)絡(luò)中各項(xiàng)內(nèi)容、服務(wù)及應(yīng)用的快速提供,讓消費(fèi)者享有不間斷的高質(zhì)量網(wǎng)絡(luò)體驗(yàn)[3-4]。基于MEC技術(shù),物聯(lián)網(wǎng)設(shè)備可以將應(yīng)用任務(wù)卸載到邊緣服務(wù)器計(jì)算處理,不再需要“長(zhǎng)途跋涉”地傳輸?shù)皆贫颂幚?因此大大減少了任務(wù)的平均處理延遲和能量消耗[5-6]。

如何設(shè)計(jì)計(jì)算任務(wù)卸載模型并做出最優(yōu)的卸載決策,是MEC面臨的一個(gè)挑戰(zhàn)性難題。不合理的卸載決策可能會(huì)導(dǎo)致任務(wù)處理時(shí)延和能耗上升,從而影響MEC的性能。目前大部分卸載模型將每個(gè)計(jì)算任務(wù)視為不可分割的獨(dú)立單元,任一獨(dú)立的計(jì)算任務(wù)只能選擇全部本地處理或者全部卸載到MEC服務(wù)器處理,即二進(jìn)制卸載[7]。文獻(xiàn)[8]研究了超密集邊緣網(wǎng)絡(luò)中的二進(jìn)制卸載和任務(wù)調(diào)度問(wèn)題,提出了基于次梯度的非聯(lián)盟博弈求解算法,有效地節(jié)省了能耗。文獻(xiàn)[9]研究了在線(xiàn)和離線(xiàn)卸載平衡問(wèn)題,探討了成本模型、用戶(hù)配置和環(huán)境因素等約束條件下的二進(jìn)制任務(wù)卸載算法,以實(shí)現(xiàn)低延遲和更好的能效。文獻(xiàn)[10]提出了分層MEC系統(tǒng)架構(gòu),探討了基于該架構(gòu)的二進(jìn)制任務(wù)卸載方案。文獻(xiàn)[11]研究了異構(gòu)移動(dòng)邊緣云環(huán)境中的非合作用戶(hù)博弈方法,以實(shí)現(xiàn)二進(jìn)制卸載計(jì)算策略的優(yōu)化。文獻(xiàn)[12]確立了MEC質(zhì)量和服務(wù)響應(yīng)時(shí)間的平衡點(diǎn),以解決服務(wù)質(zhì)量有損情況下的MEC卸載計(jì)算問(wèn)題。文獻(xiàn)[13]研究了功率約束下的二進(jìn)制卸載計(jì)算時(shí)延最小化問(wèn)題。文獻(xiàn)[14]提出了一個(gè)基于博弈論的分布式卸載算法(potential game-based offloading algorithm, PGOA),該算法基于二進(jìn)制卸載,以解決多用戶(hù)多服務(wù)器的分布式卸載計(jì)算。該文獻(xiàn)基于博弈論制定卸載策略,決定是否應(yīng)該卸載整個(gè)應(yīng)用程序以減少執(zhí)行時(shí)間。然而該工作忽略了子任務(wù)之間的依賴(lài)關(guān)系,增加了任務(wù)執(zhí)行的額外時(shí)延。

對(duì)于大型計(jì)算任務(wù),這種“二進(jìn)制任務(wù)卸載”模型存在較大的處理時(shí)延。為此,近來(lái)有學(xué)者提出了非二進(jìn)制的任務(wù)部分卸載策略,即將計(jì)算任務(wù)細(xì)分為多個(gè)子任務(wù),部分子任務(wù)本地執(zhí)行,部分子任務(wù)卸載到MEC服務(wù)器執(zhí)行,從而大大提高計(jì)算效率,降低處理時(shí)延。文獻(xiàn)[15]針對(duì)本地/邊緣服務(wù)器聯(lián)合計(jì)算場(chǎng)景,探索了基于任務(wù)關(guān)系圖的卸載策略,提出了時(shí)延最小的任務(wù)部分卸載算法。文獻(xiàn)[16]考慮云-邊協(xié)調(diào)計(jì)算場(chǎng)景,研究了模塊化任務(wù)的卸載計(jì)算優(yōu)化決策方案,提出了一種迭代啟發(fā)式MEC資源分配算法。上述兩篇文獻(xiàn)只是簡(jiǎn)單地將子任務(wù)看成一種順序執(zhí)行問(wèn)題,沒(méi)有考慮任務(wù)之間的數(shù)據(jù)依賴(lài)性。為此,文獻(xiàn)[17]考慮任務(wù)間的依賴(lài)性提出了一種分布式最早完成時(shí)間卸載(distributed earliest finish-time offloading, DEFO)算法來(lái)動(dòng)態(tài)地執(zhí)行MEC卸載決策,然而該算法犧牲了子任務(wù)的并行性來(lái)減少系統(tǒng)時(shí)延,因?yàn)樾遁d到不同邊緣服務(wù)器的子任務(wù)需要額外的等待時(shí)延,這意味著卸載計(jì)算的并行性和的服務(wù)器資源利用率較低。

針對(duì)當(dāng)前MEC卸載研究中存在的問(wèn)題,本文提出了一種基于子任務(wù)調(diào)度和時(shí)延聯(lián)合優(yōu)化的MEC部分卸載計(jì)算方案。在該方案中,用戶(hù)任務(wù)劃分為多個(gè)有順序依賴(lài)關(guān)系的子任務(wù),以子任務(wù)間交換數(shù)據(jù)量為權(quán)重,構(gòu)建一個(gè)任務(wù)關(guān)系的有向無(wú)環(huán)圖(directed acyclic graph,DAG);基于此圖建立子任務(wù)調(diào)度-計(jì)算時(shí)延聯(lián)合優(yōu)化問(wèn)題,提出一種基于節(jié)點(diǎn)復(fù)制的最早卸載算法(earliest offloading algorithm of node replication,EOAONR),完成子任務(wù)面向MEC服務(wù)器的最小時(shí)延卸載決策。相比于PGOA,本文考慮子任務(wù)之間的依賴(lài)關(guān)系,減少了任務(wù)執(zhí)行的額外時(shí)延。而相比于DEFO算法,本文通過(guò)節(jié)點(diǎn)復(fù)制消除了部分節(jié)點(diǎn)對(duì)其前驅(qū)子任務(wù)計(jì)算結(jié)果的等待時(shí)間,提高了卸載計(jì)算的并行性和服務(wù)器資源利用率。

1 系統(tǒng)模型

考慮圖1所示的微蜂窩系統(tǒng),其中存在一個(gè)活躍用戶(hù)和N個(gè)配置有MEC服務(wù)器的微基站,用戶(hù)可以同時(shí)與多個(gè)微基站關(guān)聯(lián)?；钴S用戶(hù)申請(qǐng)一個(gè)大容量應(yīng)用服務(wù),該應(yīng)用服務(wù)可分解為M個(gè)有順序依賴(lài)關(guān)系的計(jì)算型子任務(wù),除首個(gè)子任務(wù)之外,其他每個(gè)子任務(wù)的執(zhí)行需要依賴(lài)其相鄰前驅(qū)子任務(wù)的計(jì)算結(jié)果。每個(gè)子任務(wù)可以由終端(本地處理器)執(zhí)行計(jì)算,亦可以卸載至MEC服務(wù)器執(zhí)行計(jì)算。每個(gè)微基站關(guān)聯(lián)一個(gè)邊緣服務(wù)器,N個(gè)邊緣服務(wù)器通過(guò)高速光纖網(wǎng)絡(luò)彼此連接,即邊緣服務(wù)器之間可以互相通信,協(xié)作完成一個(gè)用戶(hù)的DAG任務(wù)。

圖1 系統(tǒng)模型Fig.1 System model

定義本地處理器/邊緣服務(wù)器集合為S={s1,s2,…,sj,…,sN}∪{s0},其中N表示邊緣服務(wù)器的數(shù)量,sj(j>0)表示第j個(gè)邊緣服務(wù)器,s0表示本地處理器。本地處理器/邊緣服務(wù)器sj的計(jì)算能力用fj表示,j∈N={0,1,…,j,…,N},其中f0表示本地處理器的計(jì)算能力。用戶(hù)子任務(wù)集合為V={v1,v2,…,vi,…,vM},其中vi表示第i個(gè)子任務(wù),i∈M={1,2,…,M};子任務(wù)vi的屬性表示為T(mén)i={mi,ci,ai},其中mi表示子任務(wù)vi的數(shù)據(jù)量,ci表示完成子任務(wù)vi所需要的中央處理器周期數(shù),ai表示子任務(wù)vi的卸載決策,表示子任務(wù)vi在本地處理器s0上計(jì)算,ai=j表示子任務(wù)vi在邊緣服務(wù)器sj,j∈N上計(jì)算;a=(a1,a2,…,ai,…,aM)表示M個(gè)子任務(wù)的聯(lián)合卸載決策向量。

(1)

(2)

式中:δl為本地處理器在每個(gè)中央處理器周期的能耗。

若用戶(hù)子任務(wù)vi卸載到MEC服務(wù)器sj計(jì)算,用戶(hù)子任務(wù)vi至邊緣服務(wù)器sj的上行傳輸速率可計(jì)算為

(3)

子任務(wù)vi至服務(wù)器sj的傳輸時(shí)間ωi, j、邊緣計(jì)算執(zhí)行時(shí)間ti, j和傳輸能耗ei, j、分別表示為

(4)

(5)

(6)

2 子任務(wù)卸載調(diào)度優(yōu)化問(wèn)題

2.1 構(gòu)建子任務(wù)關(guān)系圖

根據(jù)系統(tǒng)模型,活躍用戶(hù)的任務(wù)劃分為M個(gè)有順序依賴(lài)關(guān)系的子任務(wù)分別卸載計(jì)算。為了找到滿(mǎn)足順序關(guān)系約束且時(shí)延最小的子任務(wù)卸載調(diào)度排序方案,本文首先以子任務(wù)間的交換數(shù)據(jù)量為權(quán)重構(gòu)建一個(gè)有向無(wú)環(huán)的任務(wù)關(guān)系圖來(lái)描述子任務(wù)間的依賴(lài)關(guān)系,具體構(gòu)建方法如下:以應(yīng)用程序的起始子任務(wù)為圖的首層任務(wù)節(jié)點(diǎn)(入口子任務(wù)節(jié)點(diǎn)),將與其相鄰的后繼子任務(wù)依次放至圖的第二層并分別與首層任務(wù)節(jié)點(diǎn)關(guān)聯(lián),形成第二層任務(wù)節(jié)點(diǎn);再?gòu)牡诙拥拿總€(gè)子任務(wù)出發(fā),將與其相鄰的后繼子任務(wù)依次放至圖的第三層并與上層節(jié)點(diǎn)關(guān)聯(lián),以此類(lèi)推形成圖的其他層節(jié)點(diǎn),直至遍歷到應(yīng)用程序的最終子任務(wù)(出口子任務(wù)節(jié)點(diǎn)),它為圖的最下層節(jié)點(diǎn),這樣就形成了用戶(hù)任務(wù)的DAG。用G={V,E}表示建立好的用戶(hù)子任務(wù)DAG,其中V={v1,v2,…,vi,…,vM}表示子任務(wù)節(jié)點(diǎn)集,E={e(vi,vi′)}表示子任務(wù)間的有向邊集合,有向邊e(vi,vi′)由上層指向下層,代表上層子任務(wù)vi的計(jì)算結(jié)果將傳遞給其相鄰的下層子任務(wù)vi′;有向邊e(vi,vi′)的權(quán)值為βii′,表示兩個(gè)子任務(wù)間的數(shù)據(jù)交換量。

一個(gè)包含7個(gè)子任務(wù)的用戶(hù)計(jì)算任務(wù)的DAG如圖2所示,它可以記為G={{v1,v2,…,v7},{e(v1,v2),e(v1,v3),e(v1,v4),e(v2,v5),…,e(v6,v7)}},其中,v1為入口子任務(wù)節(jié)點(diǎn),v7為出口子任務(wù)節(jié)點(diǎn),e(v1,v2)的權(quán)值為β12=10,表示節(jié)點(diǎn)v1與v2間交互數(shù)據(jù)量為10 bits。

圖2 基于DAG的任務(wù)模型的圖示Fig.2 Illustration of the DAG-based task model

2.2 優(yōu)化問(wèn)題闡述

本文的目標(biāo)是將應(yīng)用程序的總計(jì)算執(zhí)行時(shí)間降至最低,即DAG中全部子任務(wù)的總執(zhí)行時(shí)間最小化。應(yīng)用程序的卸載計(jì)算需要考慮以下兩個(gè)問(wèn)題:

(1) 子任務(wù)卸載策略:在本地處理子任務(wù)還是將子任務(wù)卸載到邊緣服務(wù)器上;

(2) 子任務(wù)調(diào)度順序:對(duì)不同子任務(wù)進(jìn)行卸載排序,以降低系統(tǒng)的整體延遲。

在構(gòu)建子任務(wù)卸載調(diào)度優(yōu)化問(wèn)題之前,首先定義兩個(gè)變量:①子任務(wù)vi卸載至服務(wù)器sj的執(zhí)行開(kāi)始時(shí)間(the execution start time, TEST),表示為T(mén)EST(i,j);②子任務(wù)vi卸載至服務(wù)器sj計(jì)算時(shí)的執(zhí)行完成時(shí)間(the execution finish time, TEFT),表示為T(mén)EFT(i),i∈M={1,2,…,M},j∈N={0,1,…,j,…,N}。

事實(shí)上,子任務(wù)vi開(kāi)始執(zhí)行前需求具備兩個(gè)條件:①其所需的來(lái)自相鄰前驅(qū)子任務(wù)的數(shù)據(jù)已經(jīng)傳輸?shù)竭_(dá);②其目標(biāo)卸載服務(wù)器sj已經(jīng)空出并準(zhǔn)備提供服務(wù)。于是,子任務(wù)執(zhí)行開(kāi)始時(shí)間TEST(i,j)和完成時(shí)間TEFT(i)分別表示為

(7)

(8)

(9)

不失一般性,本文規(guī)定DAG入口任務(wù)節(jié)點(diǎn)(例如,圖2中v1)的開(kāi)始執(zhí)行時(shí)間為0,即有

TEST(1,j)=0,j∈N

(10)

(11)

式中:TEFTM表示最后一個(gè)子任務(wù)的完成時(shí)間;TEST(M,0)表示最后一個(gè)子任務(wù)的開(kāi)始執(zhí)行時(shí)間,由式(7)、式(8)、式(10)迭代得到,表示為

(12)

式中:TEFT(i′)可由式(8)計(jì)算得到。

以最小化所有子任務(wù)的執(zhí)行完成時(shí)間為目標(biāo),同時(shí)考慮用戶(hù)設(shè)備的能耗約束,建立如下的優(yōu)化問(wèn)題:

(13)

式中：式(13a)表示與子任務(wù)有關(guān)的能耗約束,即本地計(jì)算能耗和傳輸能耗,Costi表示子任務(wù)vi的能耗,包含本地計(jì)算能耗和傳輸能耗;C表示每個(gè)子任務(wù)的能耗閾值,即最大能耗限值;1[x]表示指標(biāo)函數(shù),x成立時(shí)1[x]=1,否則為0。式(13b)表示子任務(wù)的傳輸能耗。式(13c)表示子任務(wù)的本地計(jì)算能耗。式(13d)表示子任務(wù)的計(jì)算卸載決策,a表示卸載決策向量,ai=j,j∈N表示子任務(wù)vi在本地處理器或MEC服務(wù)器sj上計(jì)算;a1=0,aM=0約束初始子任務(wù)和最終子任務(wù)均在本地執(zhí)行。

式(13)所述優(yōu)化問(wèn)題屬于多變量整數(shù)優(yōu)化問(wèn)題,很難給出閉式解。下面研究該問(wèn)題的求解算法。

3 EOAONR

本節(jié)提出一種EOAONR求解式(13)所述優(yōu)化問(wèn)題,以實(shí)現(xiàn)所有子任務(wù)的最小時(shí)延卸載決策。鑒于子任務(wù)的調(diào)度順序影響總卸載時(shí)延,而待卸載的子任務(wù)具有順序依賴(lài)關(guān)系,本節(jié)基于DAG賦予不同子任務(wù)卸載優(yōu)先級(jí),據(jù)此找到執(zhí)行完全部子任務(wù)的最大時(shí)延路徑——關(guān)鍵卸載路徑,實(shí)現(xiàn)任務(wù)調(diào)度順序的優(yōu)化,在此基礎(chǔ)上設(shè)計(jì)最小時(shí)延任務(wù)卸載決策算法。

3.1 劃分子任務(wù)優(yōu)先級(jí)

對(duì)于用戶(hù)子任務(wù)DAG,賦予圖中子任務(wù)節(jié)點(diǎn)vi卸載等級(jí)：

(14)

式中:δi表示子任務(wù)vi的平均執(zhí)行時(shí)間方差;succ(i)表示子任務(wù)vi的相鄰后繼任務(wù)組成的集合;Cii′表示子任務(wù)vi與其相鄰后繼子任務(wù)vi′的平均通信時(shí)間。

式(14)是求DAG中子任務(wù)vi到出口子任務(wù)的路徑長(zhǎng)度,路徑長(zhǎng)度用時(shí)延衡量,用來(lái)解決任務(wù)依賴(lài)問(wèn)題。例如,入口子任務(wù)的路徑長(zhǎng)度是最大的,表示依賴(lài)關(guān)系最多;出口子任務(wù)的路徑長(zhǎng)度是最小的,表示依賴(lài)關(guān)系最少。

δi和Cii′分別由下式得到：

(15)

(16)

(17)

Bjj′表示服務(wù)器sj和sj′之間的信道帶寬;βii′表示子任務(wù)vi和vi′間的通信數(shù)據(jù)量。

由式(14)可知,rank(i)大的子任務(wù)依賴(lài)關(guān)系多,需要優(yōu)先卸載,因此,將所有子任務(wù)按照rank(i)值降序排列,rank(i)值大的子任務(wù)具有更高的卸載優(yōu)先級(jí),優(yōu)先執(zhí)行卸載計(jì)算。

3.2 求關(guān)鍵卸載路徑

定義 1關(guān)鍵卸載路徑為DAG中入口子任務(wù)節(jié)點(diǎn)到出口子任務(wù)節(jié)點(diǎn)的時(shí)延最長(zhǎng)路徑。

為尋址DAG的關(guān)鍵卸載路徑,引入子任務(wù)vi的最大升秩值ranku(i)和最大降秩值rankd(i)兩個(gè)參數(shù),分別計(jì)算如下：

(18)

(19)

式中:ranku(i)表示子任務(wù)vi至其相鄰后繼任務(wù)節(jié)點(diǎn)的最大升秩值,rankd(i)表示子任務(wù)至其相鄰前驅(qū)任務(wù)節(jié)點(diǎn)的最大降秩值;succ(i)表示子任務(wù)vi的相鄰后繼任務(wù)組成的集合,pred(i)表示子任務(wù)vi的相鄰前驅(qū)任務(wù)組成的集合;Cii′表示子任務(wù)vi到其相鄰后繼任務(wù)節(jié)點(diǎn)vi′的平均通信時(shí)間。

特別地,入口子任務(wù)沒(méi)有前驅(qū)節(jié)點(diǎn),出口子任務(wù)沒(méi)有后繼節(jié)點(diǎn),相應(yīng)地補(bǔ)充規(guī)定入口子任務(wù)v1的rankd(1)=0,出口子任務(wù)vM的ranku(M)=0。

定義 2對(duì)于某一子任務(wù)vi∈V,若其ranku(i)+rankd(i)值大于其當(dāng)前所在DAG圖層G(vi)中的其他子任務(wù)節(jié)點(diǎn),則vi是關(guān)鍵卸載路徑上的子任務(wù)節(jié)點(diǎn)。

很顯然,DAG的入口節(jié)點(diǎn)和出口節(jié)點(diǎn)必然在關(guān)鍵卸載路徑上。

3.3 子任務(wù)卸載計(jì)算決策算法

以圖2所示的DAG為例,EOAONR詳細(xì)描述如下。

步驟 1確定待卸載子任務(wù)集合并初始化卸載決策向量,根據(jù)式(14)計(jì)算集合中各子任務(wù)的卸載等級(jí);

如圖4(a)所示,當(dāng)前待卸載子任務(wù)集合為G={v1,v2,…,v7},其中子任務(wù)vi的卸載等級(jí)為rank(i)。

圖3 EOAONR流程圖Fig.3 Flowchart of EOAONA

步驟 2選擇待卸載子任務(wù)集合中優(yōu)先級(jí)最高的子任務(wù)vi*,判斷其是否為出口子任務(wù)節(jié)點(diǎn)或者出口子任務(wù)節(jié)點(diǎn),若是,直接本地執(zhí)行計(jì)算并跳轉(zhuǎn)至步驟6;否則,在式(13)能耗約束下為子任務(wù)vi*確定最優(yōu)卸載MEC服務(wù)器,轉(zhuǎn)步驟3。

例如,圖4(a)中,具有最大rank(i)值(最高卸載優(yōu)先級(jí))的子任務(wù)為v1,其卸載優(yōu)先級(jí)最高;由于v1是入口節(jié)點(diǎn),由式(13)可知,v1在本地執(zhí)行,待v1計(jì)算完成之后,轉(zhuǎn)步驟6。若當(dāng)前具有最高卸載優(yōu)先級(jí)的子任務(wù)vi*不是入口節(jié)點(diǎn)/出口節(jié)點(diǎn),如v2、v3、v6,對(duì)vi*分別遍歷j∈N,在滿(mǎn)足能耗約束的情況下確定使TEFT(i*)最小的MEC服務(wù)器sj*,即為vi*匹配的最優(yōu)卸載MEC服務(wù)器,然后轉(zhuǎn)步驟3。

步驟 3根據(jù)確定好的關(guān)鍵卸載路徑,判斷當(dāng)前要執(zhí)行子任務(wù)vi*的相鄰前驅(qū)子任務(wù)是否為關(guān)鍵卸載路徑上的節(jié)點(diǎn)。

例如,圖4(a)中,根據(jù)式(18)、式(19)求得的關(guān)鍵卸載路徑為v1→v4→v5→v7。若當(dāng)前待執(zhí)行子任務(wù)vi*為v2,其相鄰前驅(qū)子任務(wù)v1是關(guān)鍵卸載路徑上的節(jié)點(diǎn),轉(zhuǎn)步驟4;若當(dāng)前待執(zhí)行子任務(wù)vi*為v6,其相鄰前驅(qū)子任務(wù)v3不是關(guān)鍵卸載路徑上的節(jié)點(diǎn),轉(zhuǎn)步驟5。

圖4 DAG更新過(guò)程Fig.4 Update process of DAG

步驟 4判斷當(dāng)前要執(zhí)行的子任務(wù)vi*是否滿(mǎn)足前驅(qū)子任務(wù)復(fù)制卸載條件,即是否滿(mǎn)足不等式：

(20)

若是,將vi*的相鄰前驅(qū)子任務(wù)的數(shù)據(jù)復(fù)制到vi*匹配的MEC服務(wù)器中,轉(zhuǎn)步驟5;否則,直接轉(zhuǎn)步驟5。

(21)

(22)

例如,圖4(a)中,v2和v4滿(mǎn)足前驅(qū)子任務(wù)復(fù)制卸載條件,v3不滿(mǎn)足前驅(qū)子任務(wù)復(fù)制卸載條件,因此v3直接轉(zhuǎn)步驟5;對(duì)于v2和v4,其前驅(qū)子任務(wù)v1分別復(fù)制到v2和v4匹配的MEC服務(wù)器中(步驟2已選定),形成合并子任務(wù),然后轉(zhuǎn)步驟5。

步驟 5MEC服務(wù)器sj*對(duì)當(dāng)前卸載的子任務(wù)vi*(包括其復(fù)制任務(wù))一并計(jì)算處理。

例如,如圖4(a)中,子任務(wù)v2的匹配服務(wù)器同時(shí)處理子任務(wù)v1+v2,子任務(wù)v4的匹配服務(wù)器同時(shí)處理子任務(wù)v1+v4;而子任務(wù)v3的匹配服務(wù)器等待終端(本地)執(zhí)行完v1后將數(shù)據(jù)返回方可處理子任務(wù)v3。

步驟 6將子任務(wù)sj*從待卸載子任務(wù)集合G中刪除,更新待卸載子任務(wù)集合和卸載決策向量a;若更新后的待卸載子任務(wù)集合非空,轉(zhuǎn)步驟1,否則,轉(zhuǎn)步驟7。

如圖4(a)所示,v1的相鄰后繼任務(wù)節(jié)點(diǎn)v2、v3、v4全部卸載執(zhí)行完成后,刪除v1,更新任務(wù)關(guān)系圖,其中v3(v1)表示包含v1計(jì)算結(jié)果的v3。同時(shí)更新卸載決策向量a和v2、v3、v4的TEST(i,j),TEFT(i)。

步驟 7求得最后子任務(wù)的完成時(shí)間TEFTM和所有子任務(wù)的最優(yōu)卸載決策向量a*,算法結(jié)束。

根據(jù)上述步驟,后續(xù)DAG更新過(guò)程如圖4(b)所示。

由更新過(guò)程可知,將關(guān)鍵卸載路徑上的部分任務(wù)通過(guò)復(fù)制將“串行”卸載計(jì)算轉(zhuǎn)變?yōu)椤安⑿小毙遁d計(jì)算,消除部分節(jié)點(diǎn)對(duì)其前驅(qū)子任務(wù)計(jì)算結(jié)果的等待時(shí)間。

4 仿真分析

基于Matlab軟件,本節(jié)對(duì)提出的EOAONR的性能進(jìn)行仿真研究。仿真參數(shù)設(shè)置如表1所示。

表1 仿真參數(shù)

圖5給出EOAONR不同邊緣服務(wù)器計(jì)算能力下子任務(wù)數(shù)量與任務(wù)卸載計(jì)算時(shí)延的關(guān)系,并與文獻(xiàn)[17]的DEFO算法進(jìn)行比較。可以得出,隨著子任務(wù)數(shù)量增加,EOAONR和DEFO算法的任務(wù)卸載處理時(shí)延均呈現(xiàn)上升趨勢(shì)。這是因?yàn)殡S著子任務(wù)數(shù)量增加,完成該應(yīng)用程序所需要的傳輸時(shí)延和計(jì)算時(shí)延會(huì)增大,導(dǎo)致任務(wù)卸載計(jì)算的總時(shí)延增大。與DEFO算法相比,本文提出的EOAONR的任務(wù)卸載計(jì)算時(shí)延更小;隨著子任務(wù)數(shù)量的增加,本文算法的低時(shí)延優(yōu)勢(shì)更為顯著。這是因?yàn)?本文算法通過(guò)任務(wù)復(fù)制將“串行”卸載計(jì)算轉(zhuǎn)變?yōu)椤安⑿小毙遁d計(jì)算,消除了部分節(jié)點(diǎn)對(duì)其前驅(qū)子任務(wù)計(jì)算結(jié)果的等待時(shí)間,因此大大降低了任務(wù)的卸載時(shí)延。還可以得出,有較大計(jì)算能力的邊緣服務(wù)器會(huì)帶來(lái)更低的任務(wù)卸載處理時(shí)延,例如f=2.5 GHz與f=10 GHz的邊緣服務(wù)器相比,雖然計(jì)算能力是4倍關(guān)系,但卸載計(jì)算時(shí)延卻降低了不到兩倍,這是因?yàn)樾遁d計(jì)算時(shí)延包含了計(jì)算時(shí)延和傳輸時(shí)延,隨著子任務(wù)數(shù)量的增加,傳輸時(shí)延會(huì)增大,導(dǎo)致任務(wù)卸載計(jì)算的總時(shí)延不能成倍降低。值得一提的是,與DEFO算法相比,在不同邊緣服務(wù)器計(jì)算能力下,本文提出的EOAONR在子任務(wù)數(shù)量較少時(shí),例如N<33時(shí),能依靠算法的優(yōu)勢(shì)彌補(bǔ)服務(wù)器計(jì)算能力的差距,但當(dāng)子任務(wù)數(shù)量進(jìn)一步增加時(shí),邊緣服務(wù)器計(jì)算能力的差距就不能靠EOAONR的優(yōu)勢(shì)來(lái)彌補(bǔ)。

圖5 不同邊緣服務(wù)器計(jì)算能力下子任務(wù)的數(shù)量與 卸載計(jì)算時(shí)延的關(guān)系(N=5)Fig.5 Relationship between the number of subtasks and the offloading calculation delay under different edge server computing capabilities (N=5)

圖6給出EOAONR的服務(wù)器數(shù)量與卸載計(jì)算時(shí)延的關(guān)系,并與文獻(xiàn)[17]的DEFO算法和文獻(xiàn)[14]的PGOA進(jìn)行比較?？梢钥闯?相比基于二進(jìn)制卸載模型的PGOA,基于部分卸載模型的EOAONR和DEFO算法具有明顯的時(shí)延優(yōu)勢(shì)。隨著MEC服務(wù)器數(shù)量的增加,DEFO算法和EOAONR的任務(wù)卸載計(jì)算時(shí)延逐漸下降并趨于恒定,而PGOA的任務(wù)卸載計(jì)算時(shí)延始終保持恒定。而且,EOAONR的任務(wù)卸載計(jì)算時(shí)延總是小于DEFO算法,當(dāng)服務(wù)器數(shù)量較少時(shí),例如N<8時(shí),兩者的時(shí)延差距尤為明顯;當(dāng)N>8時(shí),兩者時(shí)延差距逐漸減小,但EOAONR仍具優(yōu)勢(shì)。

圖7給出子任務(wù)的數(shù)量與服務(wù)器資源利用率的關(guān)系,并與DEFO算法進(jìn)行比較。待卸載計(jì)算的應(yīng)用程序大小固定,被分為1～40個(gè)子任務(wù),服務(wù)器數(shù)量設(shè)置為5?？梢钥闯?隨著子任務(wù)數(shù)量增加,EOAONR和DEFO算法的服務(wù)器資源利用率均呈現(xiàn)上升趨勢(shì)。但本文算法的服務(wù)器資源利用率要高于DEFO算法,提升幅度大概20%。當(dāng)子任務(wù)的數(shù)量達(dá)到32時(shí),本文算法的服務(wù)器資源利用率不再增加,這一結(jié)果可用于指導(dǎo)邊緣服務(wù)器的部署。雖然子任務(wù)數(shù)增加,但用戶(hù)所需的計(jì)算資源保持不變,這可以推斷,通過(guò)將應(yīng)用程序劃分為更多的子任務(wù),可以進(jìn)一步提高服務(wù)器的利用率。

圖6 服務(wù)器的數(shù)量與卸載計(jì)算時(shí)延的關(guān)系(M=25)Fig.6 Relationship between the number of servers and the offloading calculation delay (M=25)

圖7 子任務(wù)的數(shù)量與服務(wù)器資源利用率的關(guān)系Fig.7 Relationship between the number of subtasks and the server resource utilization

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

本文研究了大容量計(jì)算型任務(wù)的低時(shí)延邊緣卸載計(jì)算問(wèn)題。針對(duì)端-邊協(xié)同MEC場(chǎng)景,考慮將用戶(hù)任務(wù)劃分為多個(gè)有順序依賴(lài)關(guān)系的子任務(wù)并構(gòu)建任務(wù)的DAG,設(shè)計(jì)了子任務(wù)調(diào)度優(yōu)化方案,進(jìn)而提出了一種EOAONR完成子任務(wù)面向MEC服務(wù)器的最小時(shí)延卸載決策。仿真結(jié)果驗(yàn)證了本文算法的優(yōu)越性,亦表明所提出的算法在能耗的約束下,能夠有效降低任務(wù)處理時(shí)延,并且該算法的服務(wù)器資源利用率更高。本文只考慮多子任務(wù)的單用戶(hù) MEC 系統(tǒng),所設(shè)計(jì)的卸載優(yōu)化算法是針對(duì)單用戶(hù)的,后續(xù)的工作可以將通信場(chǎng)景擴(kuò)展為多用戶(hù),并探尋一種多用戶(hù)卸載優(yōu)化算法。同時(shí),在這項(xiàng)工作中,我們的性能提升主要來(lái)自于最大限度地提升邊緣服務(wù)器之間的并行性。在未來(lái)的工作中,我們將重點(diǎn)評(píng)估子任務(wù)之間的并行度,驗(yàn)證算法在不同并行度下的性能。