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

［張偉 師寶康 劉甫琴］

1 引言

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

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

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

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

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

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

2.1 系統(tǒng)模型

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

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

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

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

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

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

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

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

2.3 通信模型

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

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

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

2.4 計(jì)算模型

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖4 任務(wù)滑動(dòng)處理后的任務(wù)隊(duì)列

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

3 實(shí)驗(yàn)分析

3.1 實(shí)驗(yàn)?zāi)康?/h3>

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

3.2 實(shí)驗(yàn)仿真與分析

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

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

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

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

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

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

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

4 結(jié)束語

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