[發明專利]聯合能量和延遲優化的移動邊緣計算任務調度方法

有效

• 申請號: 201910026321.1
• 申請日: 2019-01-11
• 公開（公告）號: CN109710336B
• 公開（公告）日: 2021-01-05
• 發明（設計）人: 鄺祝芳;李林峰;汪茄琪
• 申請（專利權）人: 中南林業科技大學
• 主分類號: G06F9/445
• 分類號: G06F9/445;G06F9/48
• 代理公司: 暫無信息
• 代理人: 暫無信息

1.聯合能量和延遲優化的移動邊緣計算任務調度方法，其特征在于，包括以下步驟：

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

步驟2：基于CPU處理任務所需周期數的卸載調度方法求卸載決策向量，

步驟3：求解卸載任務集合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周期耗能，單位為焦耳/周期，f_user為邊緣設備的CPU頻率，單位為Hz；

步驟2中的基于CPU處理任務所需周期數的卸載調度方法求卸載決策向量，輸入為所有任務集合G，邊緣設備CPU頻率f_user，邊緣服務器CPU頻率f_ser；輸出為卸載任務集合S＝{S₁,S₂,...,S_Ns}，本地任務集合L＝{L₁,L₂,...,L_Nl}，卸載決策向量x；基于CPU處理任務所需周期數的卸載調度方法步驟如下：

S2-1求各個任務對應的CPU處理所需周期數K＝{K_i|K_i＝d_ic_i,T_i∈G}，根據K_i的大小對所有任務降序排列，得到新的任務順序K^opt；

S2-2設數組K^opt初始下標值為h＝1；k0＝1，k1＝1，其中k0表示本地任務集合L的下標，k1表示卸載任務集合S的下標，根據公式(7)(8)分別計算若放入本地任務集合L、卸載任務集合S后的完成時間

S2-3若則放入本地任務集合L，任務的卸載決策變量h＝h+1，進入步驟i)；反之，任務放入卸載任務集合S，任務的卸載決策變量h＝h+1，進入步驟ii)；

ⅰ)比較放入本地任務集合L和卸載任務集合S的完成時間的大小，根據式(9)計算任務L_k0完成時間，根據式(10)計算任務S_k1完成時間；若任務的卸載決策變量任務放入本地任務集合L，h＝h+1，重復執行步驟ⅰ)；反之，任務放入卸載任務集合S，h＝h+1，并執行S2-4，

ⅱ)比較放入本地任務集合L和卸載任務集合S的完成時間的大小，根據式(9)計算任務L_k0完成時間，根據式(10)計算任務S_k1完成時間；任務的卸載決策變量任務放入卸載任務集合S，h＝h+1，重復執行步驟ⅱ)；反之，任務放入本地任務集合L，h＝h+1，并執行S2-4，

其中如式(11)所示：

S2-4根據式(9)計算任務L_k0完成時間，根據式(10)計算任務S_k1完成時間，若任務的卸載決策變量任務放入本地任務集合L，否則任務的卸載決策變量任務放入卸載任務集合S，h＝h+1，反復執行步驟S2-4直至h＝N；

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

步驟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_i個卸載任務的完成時間，為集合S中第S_i個卸載任務的服務器處理時間；表示第S_i個卸載任務分配最大傳輸功率p_max時的最大傳輸速率，為集合S中第S₁至第S_i個卸載任務的傳輸時間，計算公式如式(11)所示；

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

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

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

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

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

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

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

ⅱ)目標式對求偏導，可求得拉格朗日乘子的負數，如式(18)所示：

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

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

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

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

S3-7重復步驟步驟S3-3至步驟3-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。