[發明專利]移動邊緣計算中聯合任務調度的功率分配方法

有效

• 申請號: 201910026110.8
• 申請日: 2019-01-11
• 公開（公告）號: CN109767117B
• 公開（公告）日: 2021-05-18
• 發明（設計）人: 鄺祝芳;李林峰;陳清林
• 申請（專利權）人: 中南林業科技大學
• 主分類號: G06Q10/06
• 分類號: G06Q10/06
• 代理公司: 暫無信息
• 代理人: 暫無信息

1.移動邊緣計算網絡中聯合任務調度的功率分配方法，其特征在于，包括以下步驟：

步驟1：計算每個任務在本地的執行時間，在邊緣服務器的執行時間，任務卸載傳輸時間，邊緣服務器執行耗能，本地執行耗能，

步驟2：基于流水車間作業調度的卸載調度方法求卸載任務集合，本地任務集合，以及卸載決策向量，

步驟3：根據步驟2求得的卸載任務集合，本地任務集合，以及卸載決策向量，求解卸載任務集合S中所有任務的卸載傳輸功率，

步驟4：比較Val_old和Val_new，如果新算出的目標值與上一次循環的目標值的差值大于門限值ε，即Val_new-Val_old＞ε，則退出，否則重復步驟1-步驟3；

步驟1中的計算每個任務T_i在本地的執行時間在邊緣服務器的執行時間任務卸載傳輸時間邊緣服務器執行耗能本地執行耗能的步驟為：

S1-1任務T_i在邊緣服務器的執行時間表示為：

其中d_i為任務T_i的數據量大小，單位為比特；c_i為處理任務T_i每單位數據量所需CPU周期數，單位為周期/比特；

S1-2任務T_i的本地執行時間表示為：

其中f_user為邊緣設備的CPU頻率，單位為Hz；

S1-3任務T_i的卸載傳輸速度為：

其中，w為傳輸帶寬，g₀為路徑損耗常數，L₀為相對距離，L為實際距離，θ為路徑損耗指數，N₀為噪聲功率譜密度，p_i表示邊緣設備卸載任務T_i到邊緣服務器的傳輸功率；

S1-4任務T_i的卸載傳輸時間為：

S1-5任務T_i的卸載執行耗能為：

其中，δ_S為邊緣服務器每CPU周期的耗能，單位為焦耳/周期，η₁為任務執行能量權重，f_ser為邊緣服務器的CPU頻率，單位為Hz；

S1-6任務T_i的本地執行耗能為：

其中，δ_L為邊緣設備每CPU周期耗能，單位為焦耳/周期；

步驟2基于流水車間作業調度的卸載調度方法求卸載決策向量，輸入為所有任務集合G，邊緣設備CPU頻率f_user，邊緣服務器CPU頻率f_ser，輸出為卸載任務集合S＝{S₁,S₂,...,S_Ns}，本地任務集合L＝{L₁,L₂,...,L_Nl}，卸載決策向量x，其中Ns表示卸載任務集合數，Nl表示本地任務集合數，基于流水車間作業調度的卸載調度方法的步驟如下：

S2-1對所有任務T_i進行分類，通過比較卸載傳輸時間和邊緣服務器執行時間將卸載傳輸時間小于邊緣服務器執行時間的任務加入數組P，將P中所有任務根據卸載傳輸時間升序排列，將卸載傳輸時間大于或等于邊緣服務器執行時間的任務加入數組Q，將Q中所有任務根據邊緣服務器執行時間降序排列，將數組Q加到數組P后面得到新的任務順序[P Q]；

S2-2設數組P和數組Q的初始下標值分別初始化為h_P＝1和h_Q＝1，從數組P中取出P[h_P]放入卸載任務集合S，任務P[h_P]的卸載決策變量h_P＝h_P+1，從數組Q中取出Q[h_Q]放入本地任務集合L，任務Q[h_Q]的卸載決策變量h_Q＝h_Q+1，

S2-3計算集合L中新加入的第一個任務k₀＝1的完成時間計算集合S中新加入的第一個任務k₁＝1的完成時間分別如式(7)和式(8)所示：

S2-4比較的大小，若說明本地任務集合L中新加入的任務k₀先執行完，則執行步驟S2-4-1，否則執行步驟S2-4-2，以下兩步循環執行直至跳出循環：

S2-4-1從數組Q中反復取任務Q[h_Q]放入本地任務集合L，任務Q[h_Q]的卸載決策變量h_Q＝h_Q+1，k₀＝k₀+1，根據式(9)計算新加入的任務k₀的完成時間，比較與如果小于并且Q中還有任務，則繼續執行步驟S2-4-1；如果大于并且Q中還有任務，則執行步驟S2-4-2；如果小于并且Q中沒有任務了，則說明Q中任務被取完且L中所有任務完成時間仍小于集合S中所有任務的完成時間，則執行步驟S2-5，并將QN標志位置1，表示Q集合被提前分配完且P集合有剩余，

S2-4-2從數組P中反復取任務P[h_P]放入卸載任務集合S，任務P[h_P]的卸載決策變量h_P＝h_P+1，k₁＝k₁+1，根據式(10)計算新加入的任務k₁的完成時間，比較與如果小于并且P中還有任務，則繼續執行步驟S2-4-2；如果大于并且P中還有任務，則執行步驟S2-4-1；如果小于并且P中沒有任務了，則說明P中任務被取完且S中所有任務完成時間仍小于集合L中所有任務的完成時間，則執行步驟S2-5，并將PN標志位置1，表示P集合被提前分配完且Q集合有剩余，

其中

S2-5檢測標志位PN、QN，若QN＝1，則集合P中任務仍有剩余，將集合P中所有任務存入集合M；若PN＝1，則集合Q中任務仍有剩余，將集合Q中所有任務存入集合M；

S2-6取出集合M中的任務，根據公式(9)、(10)分別求出若該任務加入集合L、集合S中的完成時間

S2-7比較兩者大小，若則將任務加入本地任務集合L，否則將任務加入卸載任務集合S；

S2-8反復執行步驟S2-6到步驟S2-7，直至M中任務被取完為止；

步驟3求解卸載任務集合S中所有任務的卸載傳輸功率，輸入為所有卸載任務集合S＝{S₁,S₂,...,S_Ns}，本地任務集合L＝{L₁,L₂,...,L_Nl}，邊緣設備CPU頻率f_user，邊緣服務器CPU頻率f_ser，最大傳輸功率p_max，輸出為卸載任務集合S，卸載任務S_i傳輸功率采用凸優化的方法進行求解，基于凸優化的卸載任務傳輸功率的求解步驟如下：

S3-1聯合任務調度和功率分配問題的目標是最小化能量消耗和所有任務的完成時間，優化問題的數學模型如(12)至(15)所示，記為原問題P1，其中式(12)為目標函數，式(13)至(15)為約束：

其中表示排序后所有卸載任務的完成時間，Ns表示所有卸載執行任務數，Nl表示本地執行任務數，為傳輸能耗，C＝ηN₀w/[g₀(L₀/L)^θ]，η為任務傳輸能量權重參數，為排序后第S_i個卸載任務的傳輸速率的倒數，表示邊緣服務器執行所有卸載任務的總能耗，表示邊緣設備執行所有本地任務的總能耗，為排序后第S_i個卸載任務的完成時間，為集合S中第S_i個卸載任務的服務器處理時間，表示第S_i個卸載任務分配最大傳輸功率p_max時的最大傳輸速率，為集合S中第S₁至第S_i個卸載任務的傳輸時間，計算公式如式(11)所示；

S3-2對步驟S3-1的聯合優化問題P1進行問題轉換，具體步驟包括：

S3-2-1引入拉格朗日乘子和構造的拉格朗日函數如式(16)所示：

S3-2-2根據步驟2求得卸載決策向量之后，可以確定卸載任務集合S，所有卸載任務S_i的完成時間邊緣服務器執行時間卸載任務執行能耗以及本地任務執行能耗故問題P1的最優解可通過求問題P2獲得，如式(17)所示：

其中，為P2的目標式，且為凸函數，又目標式為凸函數之和，故目標式也為凸函數，為P2的約束條件；

S3-3根據式(12)計算當前給定卸載順序和卸載任務最大傳輸功率時的Val_new_S值；

S3-4采用KKT條件求解轉換的問題P2，求解步驟包括：

S3-4-1對目標式求最小值，由于目標式為凸函數，故可采用牛頓法對其進行求解，將求得的解代入約束條件(15)，若求得的解中每一個值都滿足約束條件(15)，則就是目標函數的最優解，否則進入步驟S3-4-2,

S3-4-2目標式對求偏導，可求得拉格朗日乘子的負數，如式(18)所示:

S3-4-3判斷求得的解是否滿足約束條件(15)，并對其進行分類，把滿足式(15)的解記為把不滿足式(15)的解記為集合中元素的個數記為Ndopt，集合中元素的個數記為Nnopt，將集合中的代入式(18)求得對應的拉格朗日乘子再將滿足約束(15)的最優值代入(17)，對應的拉格朗日乘子此時(17)變為以為變量的優化問題，如式(19)所示：

S3-4-4再次采用牛頓法對式(19)進行求解，求得的最優解，將和代入式(20)，求得傳輸功率；

S3-5對所有卸載任務S_i進行分類，通過比較卸載傳輸時間和邊緣服務器執行時間將卸載傳輸時間小于邊緣服務器執行時間的任務加入數組P，將P中所有任務根據卸載傳輸時間升序排列，將卸載傳輸時間大于或等于邊緣服務器執行時間的任務加入數組Q，將Q中所有任務根據邊緣服務器執行時間降序排列，將數組Q加到數組P后面得到新的任務順序[P Q]；

S3-6上一輪的目標值Val_new_S保存至Val_old_S，用于比較兩輪目標值，即Val_old_S＝Val_new_S，根據式(12)計算新的目標值Val_new_S；

S3-7重復執行步驟S3-3至步驟S3-5，直至不滿足條件Val_new_S-Val_old_S≤σ為止，此時將Val_new的值存入Val_old，目標值Val_new_S存入Val_new；

步驟4中比較Val_old和Val_new，如果新算出的目標值與上一次循環的目標值的差值大于門限值ε，即Val_new-Val_old＞ε，則退出，否則重復步驟1-步驟3。