基于多接入邊緣計(jì)算的任務(wù)卸載和資源分配策略研究

許 波，陳禮波，張 鵬，曹童杰（.中訊郵電咨詢?cè)O(shè)計(jì)院有限公司，北京 00048；.中國(guó)聯(lián)合網(wǎng)絡(luò)通信集團(tuán)有限公司，北京 00033）

0 引言

近年來，商用5G 已初具規(guī)模［1］。與前幾代移動(dòng)通信技術(shù)相比，5G的高帶寬、低時(shí)延、廣連接特性使其在在線游戲、智能識(shí)別、增強(qiáng)現(xiàn)實(shí)和虛擬現(xiàn)實(shí)（AR&VR）［2］、自動(dòng)駕駛［3］等領(lǐng)域得到廣泛應(yīng)用。然而，由于終端的計(jì)算能力和電池容量等方面的局限性，終端本身已無法滿足日益增長(zhǎng)的各種計(jì)算需求，云服務(wù)器應(yīng)運(yùn)而生。傳統(tǒng)的云服務(wù)器采用集中式的計(jì)算方法，由中心云完成計(jì)算任務(wù)并將結(jié)果返回至設(shè)備端，這就導(dǎo)致設(shè)備端接收計(jì)算結(jié)果的時(shí)間取決于中心云與設(shè)備端之間的距離和核心網(wǎng)絡(luò)的流量，在多數(shù)情況下很難滿足低時(shí)延甚至“無感知“的需求。為了解決這一難點(diǎn)，科學(xué)家提出了一種分布式的計(jì)算策略——多接入邊緣計(jì)算（Multi-access Edge Computing，MEC）［4］。MEC 將中心云分解為多個(gè)“微云”，即云服務(wù)節(jié)點(diǎn)，并將其分散在設(shè)備附近，以完成設(shè)備卸載的計(jì)算任務(wù)。由于“微云”和設(shè)備的距離很近，流量較少，能夠滿足各類計(jì)算請(qǐng)求對(duì)時(shí)延的需求；其缺點(diǎn)是計(jì)算能力較弱，一般只接收附近終端的計(jì)算任務(wù)。任務(wù)卸載和資源分配是移動(dòng)邊緣計(jì)算的關(guān)鍵問題［5］。合理的任務(wù)卸載和資源分配策略對(duì)提升MEC 的服務(wù)性能和用戶服務(wù)質(zhì)量（Quality of Service，QoS）［6］具有重要的意義。

1 相關(guān)研究

近幾年，有關(guān)MEC的研究比較熱。MEC將單一的云功能分解并下沉至多個(gè)邊緣服務(wù)器［7］，利用物理位置的變化減少任務(wù)執(zhí)行處理的時(shí)延［8］。部分研究將MEC 簡(jiǎn)化為在小型基站上部署一部分額外的資源［9-10］，但沒有考慮到基站位置的不可移動(dòng)性，使得邊緣服務(wù)器的部署有了很大限制；現(xiàn)有MEC 多為云-邊協(xié)同架構(gòu)［11］，既有云端高速處理的優(yōu)勢(shì)，又有邊緣側(cè)低時(shí)延的優(yōu)勢(shì)［12］；對(duì)于MEC 中的任務(wù)卸載問題，參考文獻(xiàn)［13］認(rèn)為邊緣服務(wù)器具有統(tǒng)一的計(jì)算能力，并提出了一種偽在線任務(wù)調(diào)度算法。Jia 等人在參考文獻(xiàn)［14］中利用排隊(duì)理論設(shè)計(jì)了用戶和服務(wù)器模型，并提出了一種啟發(fā)式策略來解決調(diào)度問題。本文在這些理論研究的基礎(chǔ)上，結(jié)合任務(wù)之間的拓?fù)浣Y(jié)構(gòu)，提出了一種細(xì)粒度的任務(wù)卸載和資源分配方式。

2 多接入邊緣計(jì)算

MEC 系統(tǒng)的核心就是分布式的邊緣服務(wù)器，即在源頭提供具有網(wǎng)絡(luò)、計(jì)算、存儲(chǔ)等功能的服務(wù)器節(jié)點(diǎn)［15］，計(jì)算任務(wù)被分別卸載到邊緣服務(wù)器上，經(jīng)過資源分配和計(jì)算后再將結(jié)果返回至設(shè)備端。這樣，能同時(shí)滿足多設(shè)備的計(jì)算需求，有效減少資源浪費(fèi)，提高計(jì)算效率。無論是在空間距離上還是網(wǎng)絡(luò)拓?fù)渖?，邊緣?jié)點(diǎn)都更靠近設(shè)備側(cè)，與傳統(tǒng)的云中心計(jì)算模式相比，MEC 時(shí)延更低、安全性更高，對(duì)時(shí)延敏感型和帶寬密集型任務(wù)更加友好［16］。MEC 的系統(tǒng)架構(gòu)如圖1 所示。

邊緣服務(wù)器分布在網(wǎng)絡(luò)的邊緣側(cè)，一般在基站或接入點(diǎn)附近，更靠近設(shè)備側(cè)，圖1 示出了2 種任務(wù)卸載的路徑：卸載至邊緣服務(wù)器或直接卸載至云端。其連接性、約束性和分布性是5G網(wǎng)絡(luò)協(xié)議提供可靠服務(wù)的保證。MEC 可以顯著縮短通信距離，被廣泛應(yīng)用于在線游戲、智能制造、智慧交通、智慧城市、物聯(lián)網(wǎng)、車聯(lián)網(wǎng)等領(lǐng)域，這些領(lǐng)域的需求主要體現(xiàn)在時(shí)延、帶寬與安全3 個(gè)方面。然而，使用MEC 系統(tǒng)架構(gòu)還存在一定的挑戰(zhàn)性，其關(guān)鍵在于任務(wù)卸載的決策和計(jì)算資源的分配。

3 任務(wù)卸載

MEC 的實(shí)際應(yīng)用中往往催生大量的算力需求。當(dāng)移動(dòng)終端自身的算力無法滿足時(shí)，計(jì)算任務(wù)會(huì)被就近分配至邊緣服務(wù)器，待計(jì)算完成后將結(jié)果返回至終端，這一過程就是任務(wù)卸載［17］。任務(wù)卸載可以幫助終端分擔(dān)復(fù)雜的計(jì)算任務(wù)，降低能耗的同時(shí)實(shí)現(xiàn)更快的任務(wù)處理速度，提供更好的QoS。

任務(wù)卸載一般有2 個(gè)方式：水平卸載和垂直卸載［18］。水平卸載一般指在相同層的設(shè)備和服務(wù)器之間進(jìn)行通信和協(xié)同計(jì)算；垂直卸載是根據(jù)計(jì)算能力將系統(tǒng)劃分為云中心、邊緣服務(wù)器、移動(dòng)終端3 層，卸載方向?yàn)榈退懔拥礁咚懔?，如圖2所示。

圖2 垂直任務(wù)卸載示意圖

現(xiàn)階段對(duì)任務(wù)卸載的研究集中在判斷是否要進(jìn)行卸載，把任務(wù)當(dāng)成一個(gè)整體，而忽略了部分卸載的可能性。判斷任務(wù)卸載的結(jié)果至少應(yīng)該包括不卸載（進(jìn)行本地計(jì)算）、全部卸載和部分卸載3種情況，如圖3所示。詳細(xì)卸載過程如圖4所示。

圖3 任務(wù)卸載的3種方式

圖4 計(jì)算任務(wù)卸載過程

4 資源分配

合理的任務(wù)卸載策略可以幫助MEC 提高網(wǎng)絡(luò)效能和QoS，但考慮到帶寬容量和算力資源的有限性，如果同一時(shí)間涌現(xiàn)大量計(jì)算任務(wù)，帶寬會(huì)限制數(shù)據(jù)的發(fā)送和接收，算力會(huì)限制任務(wù)的處理時(shí)長(zhǎng)，在這種情況下，MEC 就失去了其低時(shí)延、無感知的優(yōu)勢(shì)。因此，除了合理的任務(wù)卸載策略，MEC 還需要配合資源分配策略，以保證該計(jì)算體系正常且有效的應(yīng)用。資源分配面臨的2 個(gè)關(guān)鍵問題，一是如何在有限資源的情況下更加細(xì)粒度的部署網(wǎng)絡(luò)功能，二是采用哪種部署策略能夠更好地應(yīng)對(duì)網(wǎng)絡(luò)波動(dòng)對(duì)服務(wù)質(zhì)量的影響。針對(duì)上述2 個(gè)問題，本文采取網(wǎng)絡(luò)功能虛擬化和深度強(qiáng)化學(xué)習(xí)方法來制定資源分配策略，有效適應(yīng)多種邊緣場(chǎng)景，提高資源利用率和QoS。圖5 為該資源分配策略示意圖，在此策略中，每個(gè)任務(wù)請(qǐng)求既有其專用通道，又有多請(qǐng)求復(fù)用通道，較好地權(quán)衡了時(shí)延和資源使用量之間的關(guān)系。如果進(jìn)一步降低時(shí)延，需要增加至少3 個(gè)虛擬機(jī)，以求每個(gè)任務(wù)請(qǐng)求都有專用通道；如果縮減虛擬機(jī)數(shù)量，會(huì)進(jìn)一步增長(zhǎng)時(shí)延。

圖5 一種平衡分配策略示意圖

5 模型建立與算法設(shè)計(jì)

5.1 模型建立

綜合考慮任務(wù)拓?fù)浣Y(jié)構(gòu)和計(jì)算資源的異構(gòu)性，本文提出一種合適的任務(wù)卸載策略：分析任務(wù)拓?fù)浣Y(jié)構(gòu)，挖掘潛在的子任務(wù)卸載可能，判斷哪些子任務(wù)適合卸載，哪種卸載組合可以最大限度地降低總時(shí)延；考慮傳輸時(shí)延波動(dòng)和子任務(wù)處理時(shí)間波動(dòng)，協(xié)調(diào)多用戶的卸載策略以達(dá)到最小化平均延遲。任務(wù)卸載模型符號(hào)集如表1所示。

表1 任務(wù)卸載模型符號(hào)集

S=[1,2,…,k,…,S]表示邊緣服務(wù)器集合；D=[1,2,…,i,…,D]表示終端設(shè)備集合。那么設(shè)備i的任務(wù)卸載策略表示為

香農(nóng)定理是通信模型和信道建模的普適性定理，因此，依據(jù)香農(nóng)定理，當(dāng)確定所有卸載策略A=(a1,a2,…,aN)后，可以得到第i個(gè)設(shè)備和第k個(gè)服務(wù)器之間的無線鏈路傳輸時(shí)間為：

式中，B為設(shè)備和服務(wù)器之間的可用信道帶寬；U表示發(fā)射信號(hào)的能量值；N0為環(huán)境底噪；N表示與在同段時(shí)間選擇同一服務(wù)器進(jìn)行處理的任務(wù)對(duì)信道造成的影響，可以理解為干擾強(qiáng)度。

當(dāng)計(jì)算任務(wù)無需進(jìn)行卸載，本地計(jì)算時(shí)，子任務(wù)Ti,j的任務(wù)處理時(shí)間和處理任務(wù)所需的能耗分別為：

ti,j=ci,j/Pi

ei,j=δici,j

其中，Pi為設(shè)備i的本地處理能力；δi為設(shè)備i運(yùn)行單個(gè)CPU周期時(shí)消耗的能量。

當(dāng)計(jì)算任務(wù)需要卸載至邊緣服務(wù)器上時(shí)，子任務(wù)Ti,j卸載至服務(wù)器k所需的時(shí)間為：

其中，fk表示服務(wù)器k的計(jì)算能力，服務(wù)器之間的異構(gòu)性使得不同服務(wù)器在不同時(shí)間和任務(wù)處理情況下的計(jì)算能力各不相同；mi,j/ri,k()A表示任務(wù)上傳至服務(wù)器所需的時(shí)間，mi,j為子任務(wù)的大?。籧i,j/fk表示子任務(wù)在服務(wù)器中的處理時(shí)間。

上述公式表明，任務(wù)卸載時(shí)長(zhǎng)與任務(wù)傳輸、排隊(duì)和計(jì)算時(shí)間息息相關(guān)，而前置任務(wù)又影響著排隊(duì)時(shí)間，因此想要降低總時(shí)延就要考慮到每個(gè)子任務(wù)的卸載策略和相互之間的影響，降低競(jìng)爭(zhēng)性并得到一個(gè)分布式的協(xié)調(diào)卸載策略。

考慮子任務(wù)在網(wǎng)絡(luò)中的相互影響關(guān)系和任務(wù)處理的時(shí)序問題，用有向無環(huán)圖（Directed Acyclic Graph，DAG）來表示子任務(wù)之間的相互關(guān)系。為了實(shí)現(xiàn)平均總時(shí)延的最小化，首先要對(duì)每個(gè)子任務(wù)的處理情況進(jìn)行建模。當(dāng)設(shè)備選擇在服務(wù)器k上進(jìn)行任務(wù)卸載時(shí)，任務(wù)j的開始執(zhí)行時(shí)間用ST(j,k)表示，子任務(wù)結(jié)束時(shí)間用FT(j,k)表示。ST(j,k)取決于所有前置任務(wù)的處理時(shí)間，因此采用遞歸方式從有向無環(huán)圖的起始任務(wù)來定義：

其中，avail{0∪[k]}表示本地服務(wù)器或k服務(wù)器的可用時(shí)段；pred(j)表示j的所有前置任務(wù)，Cjj′是DAG中j→j′的通信消耗；FT(j′)表示j的處理結(jié)束時(shí)間，表示j的處理時(shí)長(zhǎng)。

avail{0∪[k]}和是子任務(wù)開始處理的2個(gè)必要條件，前者表示服務(wù)器可用，后者表示任務(wù)處理所需的數(shù)據(jù)均已處理完畢并傳至服務(wù)器；二者必須同時(shí)滿足，因此二者的較大值決定了任務(wù)開始的時(shí)間。

為了得到總時(shí)延，將上述2個(gè)公式進(jìn)行遍歷，直到得到最后一個(gè)子任務(wù)的結(jié)束時(shí)間，即為整個(gè)任務(wù)的結(jié)束時(shí)間：

任務(wù)卸載一般會(huì)由邊緣服務(wù)器返回一個(gè)結(jié)果，本地服務(wù)器進(jìn)行收集，因此可以認(rèn)為最后一個(gè)子任務(wù)的執(zhí)行方式為不卸載，就用來表示最后一個(gè)子項(xiàng)目本地執(zhí)行所需的時(shí)長(zhǎng)。

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

為了設(shè)計(jì)一個(gè)能滿足低時(shí)延和合理資源配置動(dòng)態(tài)平衡的算法，要考慮2個(gè)問題：子任務(wù)的優(yōu)先級(jí)和邊緣服務(wù)器的選擇。

首先定義DAG中j→j′的權(quán)重：

dataj′,j為2 個(gè)子任務(wù)之間進(jìn)行交互的數(shù)據(jù)量；Cjj′表示有關(guān)聯(lián)的子任務(wù)之間的通信時(shí)延，當(dāng)子任務(wù)在同一個(gè)服務(wù)器上時(shí)，該時(shí)延可認(rèn)為是0；因此DAG 中j→j′的平均時(shí)延可以定義為：

子任務(wù)j的平均處理時(shí)間為：

因此，子任務(wù)j的優(yōu)先級(jí)可以被定義為：

其中，Succ(j)表示直接后繼任務(wù)。

根據(jù)上述模型的建立，可以得到任務(wù)卸載算法如圖6所示。

圖6 任務(wù)卸載算法

該算法考慮了單服務(wù)器場(chǎng)景下的任務(wù)卸載策略。首先對(duì)子任務(wù)的優(yōu)先級(jí)進(jìn)行排序，然后按照優(yōu)先級(jí)最高到最低的順序依次判斷子任務(wù)的卸載策略，判斷方法為比較不同卸載方式需要的時(shí)間（本地處理或邊緣處理）并擇優(yōu)，最后通過每個(gè)子任務(wù)的卸載策略得到總的卸載策略。該算法利用優(yōu)先級(jí)的順序進(jìn)行策略制定，避免了對(duì)每個(gè)子任務(wù)進(jìn)行窮舉決策，復(fù)雜度僅為O［n］。

6 結(jié)束語

本文針對(duì)傳統(tǒng)工業(yè)互聯(lián)網(wǎng)自動(dòng)化程度低、靈活性差等問題，提出了一種基于拓?fù)浣Y(jié)構(gòu)的任務(wù)卸載策略和邊緣資源分配策略，任務(wù)卸載策略通過前期任務(wù)處理（判定優(yōu)先級(jí)）等方式，大大降低了復(fù)雜度，并有效降低端到端時(shí)延；邊緣資源分配策略綜合考慮了時(shí)延和資源之間的平衡，給出了一種在保證時(shí)延的條件下，盡可能減少資源浪費(fèi)的方式。除此之外，本文給出了一種基于拓?fù)浣Y(jié)構(gòu)的任務(wù)卸載算法和流程圖，解決了現(xiàn)有任務(wù)傳輸路徑算法的不足，保障了工業(yè)生產(chǎn)的整體效率。