[發(fā)明專利]在邊緣計算中在線批并行任務(wù)調(diào)度方法

在審

• 申請?zhí)枺?/td>: 202110731470.5
• 申請日: 2021-06-29
• 公開（公告）號: CN113448707A
• 公開（公告）日: 2021-09-28
• 發(fā)明（設(shè)計）人: 郭星;魯俊;李煒;張以文
• 申請（專利權(quán)）人: 安徽大學(xué)
• 主分類號: G06F9/48
• 分類號: G06F9/48
• 代理公司: 合肥市長遠(yuǎn)專利代理事務(wù)所(普通合伙) 34119
• 代理人: 孫麗麗

1.在邊緣計算中在線批并行任務(wù)調(diào)度方法，其特征在于，具體步驟為：

S1、使用馬爾科夫決策過程進(jìn)行建模；

S2、在每一段時間片段內(nèi)，為每一個邊緣服務(wù)器的Batch容器進(jìn)行任務(wù)分發(fā)；

S3、使用強(qiáng)化學(xué)習(xí)來進(jìn)行求解，最終完成在線任務(wù)的調(diào)度。

2.根據(jù)權(quán)利要求1所述的在邊緣計算中在線批并行任務(wù)調(diào)度方法，其特征在于，步驟S1具體如下：

將處理一個任務(wù)集的時間段平均分為多個長度相等的決策周期T＝{1,2,...,t}，在每個決策周期內(nèi)為待處理任務(wù)找到最優(yōu)的調(diào)度策略；模型用四元組M_t＝(S(t),A(t),P_sa(t))來表示，其中R(s,a))表示決策周期t內(nèi)的MDP；S(t)＝{0,1,2,...,n}表示在決策周期t內(nèi)的有限狀態(tài)集，S(t)的值代表當(dāng)前決策周期內(nèi)未處理的任務(wù)數(shù)量；A(t)＝{1,2,3,...,m}表示在決策周期t內(nèi)可能采取的有限action集合，A(t)的值表示在不同的狀態(tài)選擇用來處理任務(wù)的邊緣服務(wù)器編號；R(s,a)＝T(s,a)+W(s,a)+P(s,a)作為在狀態(tài)s采用行為a所得到的回報函數(shù)，在本文中我們視為對邊緣服務(wù)器增加的開銷；P_sa(t)表示在狀態(tài)s下采取動作a的狀態(tài)轉(zhuǎn)移概率。

3.根據(jù)權(quán)利要求1所述的在邊緣計算中在線批并行任務(wù)調(diào)度方法，其特征在于，S2的步驟如下：

S21、對每個任務(wù)計算其處理優(yōu)先級g_j來決定任務(wù)的調(diào)度順序；每個任務(wù)都有一個任務(wù)最遲開始處理時間與最遲完成時間兩者為：

其中s_j表示任務(wù)j需要的計算資源，p_i表示服務(wù)器s_i的處理速率；

定義任務(wù)J_j的處理優(yōu)先級g_j為：

T(t)為當(dāng)前時間點；

S22、建立一個空batchB_ki來收集分配給邊緣服務(wù)器S_i的待處理任務(wù)，并將當(dāng)前處理優(yōu)先級最高的任務(wù)放入并初始化空batchB_ki；在選擇為處理任務(wù)放入B_ki時，建立一個任務(wù)候選集CL；

S23、在任務(wù)候選集CL建立完畢后，根據(jù)優(yōu)先級對其中的任務(wù)進(jìn)行降序排列，并在Sb_ki≤c_i前提下，依次選取其中的任務(wù)放入batchB_ki中。

4.根據(jù)權(quán)利要求3所述的在邊緣計算中在線批并行任務(wù)調(diào)度方法，其特征在于，所述候選集中的候選任務(wù)滿足的條件為：1)候選任務(wù)的資源需求量不能超出邊緣服務(wù)器S_i當(dāng)前所剩余的資源量；2)候選任務(wù)不會引起已存在于B_ki中的任務(wù)處理超時；

為分辨出后候選任務(wù)是否會導(dǎo)致先加入的任務(wù)的處理超時，定義B_ki的最遲開始處理時間

其中表示某一批次任務(wù)的最晚開始時間。

5.根據(jù)權(quán)利要求3所述的在邊緣計算中在線批并行任務(wù)調(diào)度方法，其特征在于，任務(wù)候選集CL的定義為：

c_i表示服務(wù)器s_i的資源總量，Sb_ki表示某批次的已經(jīng)使用的資源總和，s_j表示任務(wù)j需要的資源量，r_ji′表示任務(wù)j到達(dá)邊緣服務(wù)器的時間。

6.根據(jù)權(quán)利要求1所述的在邊緣計算中在線批并行任務(wù)調(diào)度方法，其特征在于，步驟S3的增強(qiáng)學(xué)習(xí)使用Q-learning方法，具體為：

每一個(s,a)對應(yīng)Q值Q(s,a)，智能體不斷地以某種策略在不同的狀態(tài)選取行為，并根據(jù)新到達(dá)的狀態(tài)與得到的回報值來更新Q(s,a)，直到到達(dá)終止?fàn)顟B(tài)；更新Q值的方式為：

Q(s,a)＝Q(s,a)+α[R(s,a)+γmin_a′Q(s′,a′)-Q(s,a)](5)

其中R(s,a)表示在狀態(tài)s采取行動a,即在剩余任務(wù)數(shù)量為s時，分配到服務(wù)器編號為a所得到的的即時回報，α為學(xué)習(xí)率，γ為獎勵衰變因子，Q(s′,a′)為下一個狀態(tài)下的Q值。