［張偉 師寶康 劉甫琴］

1 引言

邊緣計算作為解決5G 通信網(wǎng)絡(luò)uRLLC 場景時延過長的殺手锏，它讓用戶的部分任務(wù)卸載到邊緣服務(wù)器端處理，在一定程度上提升了用戶的感知水平。但是邊緣服務(wù)器的計算存儲能力相較于云中心更小，為了優(yōu)化計算存儲資源的利用率，研究用戶的任務(wù)調(diào)度很有必要。目前邊緣網(wǎng)絡(luò)資源管理沒有考慮卸載任務(wù)存在多用戶競爭的因素，從而造成邊緣計算資源和傳輸資源在處理任務(wù)時產(chǎn)生的時延具有不確定性的問題。隨著用戶的增多，任務(wù)傳輸時延和計算時延受到多用戶競爭的影響，如何合理調(diào)度任務(wù)是提高系統(tǒng)性能的關(guān)鍵問題。當(dāng)前關(guān)于任務(wù)調(diào)度存在三大主要問題：（1）目前研究用戶任務(wù)調(diào)度的研究不少，但是大多數(shù)側(cè)重于獨立任務(wù)[1～3]，也就是認(rèn)為用戶的任務(wù)是一個整體，獨立用戶在服務(wù)器與用戶調(diào)度之間是聯(lián)合調(diào)度的。但在現(xiàn)實中，移動終端通常會將任務(wù)分割成多個子任務(wù)，任務(wù)直接存在時間處理上的依賴關(guān)系。（2）目前研究忽視高等級用戶的任務(wù)動態(tài)到達的問題[4,5]，也就是當(dāng)高等級用戶的任務(wù)需要插隊處理時，如何將高等級用戶子任務(wù)插入到執(zhí)行鏈表隊列中，從而滿足現(xiàn)實依賴性任務(wù)細(xì)粒度調(diào)度的動態(tài)性需求。（3）目前研究沒有考慮共享服務(wù)器在處理任務(wù)時資源的動態(tài)變化問題，靜態(tài)任務(wù)調(diào)度[6,7]或在線任務(wù)調(diào)度[8～10]往往導(dǎo)致任務(wù)處理時延過大，無法滿足用戶需求。

為了解決上面3 個問題，本文研究多用戶多MEC 服務(wù)器場景下，根據(jù)任務(wù)的依賴關(guān)系構(gòu)建拓?fù)鋱D和服務(wù)器的實際負(fù)載，分別計算任務(wù)在移動終端和在MEC 服務(wù)器上的計算時間，以執(zhí)行時延最小為目標(biāo)來執(zhí)行任務(wù)的卸載策略。主要步驟包括：

（1）考慮到用戶任務(wù)存在依賴性，因此，本文將用戶的任務(wù)劃分割成子任務(wù)并形成任務(wù)隊列，采用強化學(xué)習(xí)來最大化所獲得的累積獎勵，將子任務(wù)分配到合適的服務(wù)器中。增強學(xué)習(xí)用于動態(tài)環(huán)境的資源調(diào)度策略，以應(yīng)對服務(wù)器計算資源存在變化的時候，處理器發(fā)生變化，從而解決由于時延發(fā)生變化的問題。

（2）當(dāng)有新任務(wù)出現(xiàn)時，根據(jù)任務(wù)調(diào)度的優(yōu)先級（用戶級別、任務(wù)屬性、最晚完成時間）采用鏈表依賴性任務(wù)在線滑動調(diào)度的方式結(jié)合已調(diào)度任務(wù)的執(zhí)行時間冗余為新到達的任務(wù)尋找合適的執(zhí)行槽位，當(dāng)所有任務(wù)調(diào)度完成時，將每一個任務(wù)節(jié)點的執(zhí)行時間設(shè)置為最早完成時間，以保證任務(wù)的時延需求。

因此，本文在整個系統(tǒng)時延最低目標(biāo)的基礎(chǔ)上，以任務(wù)的依賴關(guān)系、時延約束以及整個系統(tǒng)的負(fù)載均衡為約束，結(jié)合任務(wù)調(diào)度優(yōu)先級形成靈活的、自適應(yīng)的任務(wù)調(diào)度策略，從而實現(xiàn)任務(wù)平均響應(yīng)時延最低。

2 基于任務(wù)可分割性的多用戶依賴性任務(wù)調(diào)度策略

2.1 系統(tǒng)模型

隨著移動終端的智能化，移動終端能夠?qū)崿F(xiàn)越來越多復(fù)雜的應(yīng)用。當(dāng)移動終端執(zhí)行某個應(yīng)用時，將一個任務(wù)拆分成多個子任務(wù)，圖1 左邊1 號終端將任務(wù)拆分成7 個子任務(wù)。圖1 右邊時任務(wù)調(diào)度結(jié)果和執(zhí)行順序，子任務(wù)1 必須在移動終端執(zhí)行，1 號邊緣節(jié)點執(zhí)行子任務(wù)2，4，而2號邊緣節(jié)點執(zhí)行子任務(wù)3，5，6，最后，2 號邊緣節(jié)點將結(jié)果反饋到1 號邊緣節(jié)點，1 號邊緣節(jié)點執(zhí)行結(jié)束后將最終結(jié)果反饋到1 號終端。系統(tǒng)模型圖如圖1 所示。

圖1 系統(tǒng)模型圖

由于本文變量較多，在構(gòu)建網(wǎng)絡(luò)模型和計算模型之前，本文將相關(guān)的變量以列表的形式給出，具體如表1 所示。

表1 相關(guān)變量解釋

2.2 網(wǎng)絡(luò)模型

本文考慮的是移動邊緣計算的服務(wù)協(xié)同問題，圖1 顯示系統(tǒng)模型，1 號終端在執(zhí)行某應(yīng)用時，首先是將該應(yīng)用的任務(wù)進行分割，分割完畢之后，需要對任務(wù)進行是否卸載的決策；然后要考慮如何將子任務(wù)卸載到哪些服務(wù)器的問題；最后還要考慮子任務(wù)動態(tài)調(diào)度的問題，也就是考慮任務(wù)的執(zhí)行方式以及任務(wù)調(diào)度的優(yōu)先級。為了對用戶任務(wù)調(diào)度更好的描述，本文用集合N={0,1,2,…,n,…,M}表示移動終端設(shè)備、MEC 邊緣服務(wù)器集合，統(tǒng)一看成為處理單元。其中N={0}表示移動終端。n 代表第n 個邊緣服務(wù)器，M代表處理能力資源總數(shù)。

用集合V={1，2，…，i，…，Q}表示任務(wù)集合，其中i 代表第i 個任務(wù)，Q 代表任務(wù)總數(shù)。

用集合U={1，2，…，j，…，P}表示用戶集合，其中j 代表第j 個用戶，P 代表用戶總數(shù)。

2.3 通信模型

一旦移動終端執(zhí)行卸載策略，任務(wù)卸載需要考慮任務(wù)的傳輸速率和任務(wù)在無線側(cè)的傳輸時間。假設(shè)無線側(cè)上傳鏈路信道的帶寬B，高斯白噪音功率；手機終端發(fā)射功率G，信道增益參數(shù)，假設(shè)基站帶寬足夠并且?guī)捚骄纸o該基站的移動用戶，得到數(shù)據(jù)平均傳輸速率：

其中信道增益參數(shù)Hi與上傳鏈路的信道衰落因子h以及終端傳輸任務(wù)起始到結(jié)束的平均距離有關(guān)。

基于傳輸速率，得到任務(wù)在無線側(cè)的傳輸時延false：

2.4 計算模型

如果任務(wù)選擇在本地處理任務(wù)，那么基于本地計算能力所產(chǎn)生的時延為：

f υ表示終端處理任務(wù)i 所需要的計算資源（也就是終端CPU 芯片的時鐘頻率，單位是赫茲），Ci表示服務(wù)器處理任務(wù)i 所需要的計算資源（也就是服務(wù)器是CPU 芯片的時鐘頻率，單位是赫茲），表示終端處理任務(wù)i 所需要的時延。如果終端處理任務(wù)i 所需要的時延大于業(yè)務(wù)要求的最大容忍時延那么需要進行部分卸載。變量的任務(wù)卸載比例，表示為：

考慮邊緣服務(wù)器協(xié)同的場景，那么一旦卸載或者全部卸載，都滿足：

卸載到邊緣計算節(jié)點，其產(chǎn)生的時延為：

那么，任務(wù)i 完成的總時間為：

本文不考慮不考慮有包交互、有線傳輸時間的時延和子任務(wù)處理完回傳到終端側(cè)的時延。正如前面所述，我們在任務(wù)卸載之前，已經(jīng)將任務(wù)劃拆分成多個子任務(wù)，每個子任務(wù)是可以在不同設(shè)備上執(zhí)行的。因此，本文通過公式8 計算協(xié)同服務(wù)器中哪一臺服務(wù)器執(zhí)行子任務(wù)的總時間最大作為任務(wù)卸載處理時間。

一旦子任務(wù)i 被放置到第n 個處理器時，需要區(qū)分前驅(qū)子任務(wù)和后驅(qū)子任務(wù)。因此，服務(wù)器的選擇不僅僅需要依據(jù)子任務(wù)完成的時延進行資源調(diào)度，還要考慮到當(dāng)前服務(wù)器的任務(wù)隊列，也就是考慮每一個服務(wù)器的時間槽最早開始執(zhí)行的位置。本文按照間隔的大小將服務(wù)器的處理器分割成多個槽位，子任務(wù)i 在多個邊緣服務(wù)器內(nèi)選擇合適的槽位進行任務(wù)處理，服務(wù)器處理時間調(diào)度模型如圖2 所示。

本文還是以圖1 的任務(wù)為例，子任務(wù)在可選的邊緣服務(wù)器和時間槽的占用情況，最終選擇了2 個服務(wù)器節(jié)點，那么我們在服務(wù)器n 的總時延就是：

公式11 的最后三個公式是指任務(wù)分配到服務(wù)器n 時，任務(wù)i 所需要的CPU 計算資源、存儲計算資源和帶寬資源都不能大于服務(wù)器最大值。

上述情況時沒有考慮到動態(tài)任務(wù)的到達情況，一旦有高用戶等級的任務(wù)進來，本文采用滑動窗口的方式微調(diào)任務(wù)節(jié)點的時間，將動態(tài)到達的任務(wù)插入鏈表隊列中，減少調(diào)度的開銷。

在靜態(tài)情況下用戶的任務(wù)資源配置過程，上一個用戶任務(wù)配置如圖2 所示，任務(wù)已經(jīng)分配給兩個邊緣服務(wù)器。這時，有多個VIP 用戶將任務(wù)卸載到這兩個服務(wù)器。當(dāng)有多個VIP 用戶的任務(wù)動態(tài)到達時，上一個用戶的任務(wù)執(zhí)行開始時間將會是發(fā)生變化的。如果能夠調(diào)整上述已經(jīng)安排好時間槽的子任務(wù)執(zhí)行時間，那么VIP 用戶很有可能通過“插隊”將任務(wù)插入執(zhí)行鏈表之中。

首先，結(jié)合任務(wù)的最大時延需求確定已經(jīng)安排槽位的任務(wù)最早允許執(zhí)行和最晚允許執(zhí)行的時間，用戶執(zhí)行任務(wù)的最早和最晚時間示意圖如圖3 所示。

圖3 用戶執(zhí)行任務(wù)的最早和最晚時間

其次，結(jié)合新到達用戶的子任務(wù)調(diào)度優(yōu)先級（VIP 等級和任務(wù)類型），對子任務(wù)的時間槽位進行靈活調(diào)整，采用滑動窗口的方式將已分配的任務(wù)最晚時間為原則，對最新到達的子任務(wù)插入鏈表中，充分利用服務(wù)器的任務(wù)資源，節(jié)省調(diào)度開銷。任務(wù)滑動處理后的任務(wù)隊列示意圖如圖4所示。

圖4 任務(wù)滑動處理后的任務(wù)隊列

最后，將新到達用戶的子任務(wù)調(diào)度優(yōu)先級（VIP 等級和任務(wù)類型）與圖3 空白位置的時間槽進行判斷，如果上述的時間槽滿足子任務(wù)處理時延的要求，那么就將其放進空白的時間槽進行處理，否則，再尋找合適的時間槽，不斷迭代，直到找到合適的時間槽為止。

3 實驗分析

3.1 實驗?zāi)康?/h3>

為了驗證本文提出的算法，將本文算法與傳統(tǒng)的任務(wù)調(diào)度方法（隨機調(diào)度）進行未超時任務(wù)比例以及任務(wù)平均處理時間這兩項性能的比較，驗證本文算法的依賴性任務(wù)調(diào)度能夠在一定程度上降低任務(wù)的平均時延。由于子任務(wù)之間存在競爭關(guān)系，因此邊緣計算節(jié)點的處理能力和存儲能力是一個動態(tài)變化的過程。本文重點驗證在處理器數(shù)量變化與未超時任務(wù)比例和處理器數(shù)量變化與任務(wù)平均處理時延的變化，以此說明本文算法更加使用動態(tài)場景。

3.2 實驗仿真與分析

為了評估動態(tài)場景下系統(tǒng)的調(diào)度策略，實現(xiàn)多用戶依賴性任務(wù)的自適應(yīng)調(diào)度，本文在中山聯(lián)通5G 試驗網(wǎng)中進行測試，通過模擬多用戶的任務(wù)請求，以期驗證該方法在多用戶依賴性任務(wù)調(diào)度的可靠性。每次測試都是在固定其余參數(shù)的情況下，更改其中一個參數(shù)。比如，在邊緣節(jié)點處理器數(shù)量固定的情況下，隨著任務(wù)動態(tài)到達數(shù)量的變化，計算出不同任務(wù)狀態(tài)下的未超時任務(wù)比例與任務(wù)平均處理時延；或者在固定任務(wù)達到數(shù)量的情況下，隨著邊緣節(jié)點處理器數(shù)量的變化，計算出不同任務(wù)狀態(tài)下的未超時任務(wù)比例與任務(wù)平均處理時延。未超時任務(wù)比例隨著處理器數(shù)量的變化關(guān)系以及任務(wù)平均處理時間隨著處理器數(shù)量的變化關(guān)系分別如圖5 和圖6 所示。

圖5 未超時任務(wù)比例隨著處理器數(shù)量的變化關(guān)系圖

圖5 和圖6 展示在隨機達到任務(wù)數(shù)量（任務(wù)數(shù)量為200）的情況下，處理器數(shù)量從5 變化到25 過程中，未超時任務(wù)比例和任務(wù)平均處理時間隨著處理器的變化情況。

隨著處理器數(shù)量的增多，未超時任務(wù)比例的差距越來越大，而任務(wù)平均處理時間的差距越來越小。未超時任務(wù)比例隨著任務(wù)數(shù)量的變化關(guān)系和任務(wù)平均處理時間隨著任務(wù)數(shù)量的變化關(guān)系分別如圖7 和圖8 表示。由圖7 和圖8可知，本文的算法較隨機調(diào)度的算法性能高，這是因為在每一輪調(diào)度過程中，本文算法以任務(wù)的依賴關(guān)系、時延約束以及整個系統(tǒng)的負(fù)載均衡為約束，通過優(yōu)化服務(wù)器任務(wù)調(diào)度優(yōu)先級，能夠在一定程度降低用戶將任務(wù)卸載時傳輸和處理任務(wù)時延的不確定性。

在處理器數(shù)量（處理器數(shù)量為20）確定的情況下，不同算法在任務(wù)數(shù)量增多的情況下，未超時任務(wù)比例和任務(wù)平均處理時間的變化情況。隨著任務(wù)數(shù)量的增多，任務(wù)平均處理時間的差距越來越大，而為超時任務(wù)比例在每一輪的調(diào)度中比隨機調(diào)度算法小得多。由此可知，本文的算法以任務(wù)的依賴關(guān)系和時延為約束，結(jié)合任務(wù)調(diào)度優(yōu)先級形成靈活的、自適應(yīng)的任務(wù)調(diào)度策略，根據(jù)任務(wù)數(shù)量的變化自適應(yīng)調(diào)整卸載策略，從而降低任務(wù)處理時延的不確定性。

圖7 未超時任務(wù)比例隨著任務(wù)數(shù)量的變化關(guān)系圖

圖8 任務(wù)平均處理時間隨著任務(wù)數(shù)量的變化關(guān)系圖

4 結(jié)束語

本文提出一種基于任務(wù)可分個性的多用戶依賴性任務(wù)調(diào)度策略。該策略以任務(wù)依賴關(guān)系，將子任務(wù)形成任務(wù)隊列后，采用增強學(xué)習(xí)將任務(wù)分配到合適的服務(wù)器中，解決多用戶依賴性的任務(wù)調(diào)度問題；其次，當(dāng)新任務(wù)出現(xiàn)時，結(jié)合子任務(wù)調(diào)度的優(yōu)先級，采用鏈表依賴性任務(wù)在線滑動調(diào)度的方式實現(xiàn)新到達任務(wù)的槽位安排，在保證任務(wù)時延需求下提升VIP 用戶滿意度。相比于傳統(tǒng)的隨機調(diào)度算法，本文的任務(wù)調(diào)度算法具有更強的移植性以及擴展性。