[發明專利]基于蟻群算法的面向低軌道衛星邊緣計算任務調度方法

有效

• 申請號: 202011485598.X
• 申請日: 2020-12-16
• 公開（公告）號: CN112653500B
• 公開（公告）日: 2022-07-26
• 發明（設計）人: 王波;馮彤;黃冬艷;李簫航;謝杰成;任英琦;付中衛
• 申請（專利權）人: 桂林電子科技大學
• 主分類號: H04B7/185
• 分類號: H04B7/185;H04L47/24;G06N3/00;G06F9/50;G06F9/48
• 代理公司: 桂林市華杰專利商標事務所有限責任公司 45112
• 代理人: 童世鋒

1.一種基于蟻群算法的面向低軌道衛星邊緣計算任務調度方法，其特征在于，包括如下步驟：

1)建立通信模型：根據設備個數k(k∈{1,2,...K})、信道帶寬B、傳輸功率P_k、高斯白噪聲信號的功率σ₀、信道增益g_k,s和其他設備對設備k產生的干擾建立上行傳輸速率R_k模型，表達式為

2)建立計算模型：包括所需的CPU周期數目c_k，上行數據大小d_k，計算模型分為本地計算和衛星計算模型，包括如下步驟：

2-1)建立本地計算模型，包括如下步驟：

2-1-1)利用所需的CPU周期數目c_k和時鐘頻率f_k,l建立本地計算時延模型T_k,l，其表達式為

2-1-2)利用所需的CPU周期數目c_k、時鐘頻率f_k,l和有效的開關電容κ建立本計算能耗模型E_k,l，其表達式為E_k,l＝κc_k(f_k,l)²；

2-1-3)利用本地計算時延模型和本地計算能耗模型，建立本地計算時延和能耗函數ψ_k,l，其表達式為ψ_k,l＝(1-β)T_k,l+βE_k,l，其中β∈[0,1]是業務的時延和能耗的權重；

2-2)建立衛星計算模型，包括卸載任務和衛星執行任務，具體步驟如下：

2-2-1)根據排在次序q的第k位的任務數據大小d_q(k)和排在次序q的第k位的任務上行傳輸速率R_q(k)，建立衛星計算的傳輸時延模型其表達式為

2-2-2)根據排在次序q的第k位的所需的CPU周期數目c_q(k)和衛星時鐘頻率f_s，建立衛星計算的計算時延模型其表達式為

2-2-3)根據任務q(k)在衛星計算開始的時刻H_q(k)和任務q(k-1)在衛星計算完成時刻H_q(k-1，建立衛星計算等待時延模型其表達式為

2-2-4)根據步驟2-2-1)建立的傳輸時延模型和排在次序q的第k位的設備傳輸功率P_q(k)，建立傳輸能耗模型

2-2-5)根據有效開關電容κ、排在次序q的第k位的所需的CPU周期數目c_q(k)和衛星的時鐘頻率f_s，建立衛星所消耗的能耗模型κc_q(k)(f_s)²；

2-2-6)根據步驟2-2-1)建立的傳輸時延模型步驟2-2-2)建立的計算時延模型步驟2-2-3)建立的等待時延模型步驟2-2-4)建立的傳輸能耗模型和步驟2-2-5)建立的衛星所消耗的能耗E_q(k),s，建立衛星計算時總的時延和能耗函數模型ψ_q(k),s，其表達式為其中β∈[0,1]是能耗和時延的權重因子；

3)建立問題模型：在設備的任務在本地計算不能超過最大的容忍時間能量消耗不能超過設備的可用能量本地設備的時鐘頻率和卸載任務不能超過截止期限的約束下，以及用二進制表示卸載決策o_k∈{0,1}，通過所述的約束確保設備的計算資源、電池能量和多用戶具有不同QoS需求，根據步驟2-1-3)建立的本地計算時延和能耗函數ψ_k,l和步驟2-2-6)建立的衛星計算時總的時延和能耗函數模型ψ_q(k),s，建立時延和能耗系統最小花費模型

4)設計基于蟻群算法的任務調度方法，采用蟻群算法優化多設備的任務執行次序問題和通過調度時鐘頻率優化本地計算的花費，使時延和能耗系統的總花費最小。

2.根據權利要求1所述的一種基于蟻群算法的面向低軌道衛星邊緣計算任務調度方法，其特征在于，步驟4)中，所述的基于蟻群算法的任務調度方法，具體步驟如下：

4-1)調度時鐘頻率優化本地計算，包括如下步驟：

4-1-1)根據時延和能耗系統最小花費模塊，調度時鐘頻率優化本地計算的模型如下：

4-1-2)令則Q_k,l(f_k,l)的值只取決于f_k,l，因此，將Q_k,l(f_k,l)對f_k,l求導并等于0，得到

4-1-3)根據步驟4-1-1)中的約束條件C1和C2，簡化得到和

4-1-4)根據步驟4-1-3)的結果和步驟4-1-1)中的約束條件C3，聯合得到和

4-1-5)確保f_k,l的可行域是非空，則滿足f_u'≤f_h'，因此步驟4-1-1)問題的最佳結果為：

4-2)優化任務執行次序，用蟻群算法優化多設備的任務執行次序，則步驟3)中的時延和能耗系統最小花費模型化簡為如下所示：

C2:o_k∈{0,1}

基于蟻群算法的任務調度方法步驟如下：

4-2-1)初始化變量：在計算前對CPU周期數目、有效開關電容、設備的傳輸功率、數據大小、能耗和時延的權重因子、衛星的時鐘頻率、螞蟻數目、信息素揮發系數、最大迭代次數、信息素強度相關參數進行初始化；

4-2-2)輸入各個任務在云端執行時間、傳輸時間、計算卸載最大容忍時間、計算卸載的系統花費、本地計算的系統花費；

4-2-3)構建解空間，如下所示：

4-2-3-1)將K個任務進行隨機排列，每只螞蟻隨機地放置于不同的初始任務上，并維護一個路徑記憶向量，用于存放該螞蟻依次經過的任務；

4-2-3-2)螞蟻在構建任務排隊序列的每一步中，用輪盤賭法選擇下一個要選擇的任務；

4-2-3-3)螞蟻在構建任務排隊序列的每一步中，用輪盤賭選擇下一個要選擇的任務；

4-2-3-4)判斷是否有待選的任務，如果有，則重復步驟4-2-3-1)，如果沒有待選的任務，則記錄本次迭代的任務最佳執行次序；

4-2-4)記錄本次迭代的系統最小花費，如下所示：

4-2-4-1)初始化每只螞蟻所走路徑的花費為零，依次把每只螞蟻的路徑取出來，判斷每個任務是否存在等待時間；

4-2-4-2)根據用戶QoS需求，判斷用戶的任務是否計算卸載；

4-2-4-3)如果不滿足用戶QoS需求，則該用戶執行本地計算，通過調度時鐘頻率優化本地計算來降低本地計算的時延和能耗，降低系統的總花費；

4-2-4-4)如果滿足用戶QoS需求，則該用戶執行衛星計算并計算該任務衛星計算的總時延和能耗；

4-2-4-5)記錄本次迭代所有任務總系統花費；

4-2-5)記錄當前迭代次數中的系統花費最小的任務執行次序，同時，對各個任務執行次序上的信息素濃度進行更新；

4-2-6)若迭代次數小于最大迭代次數則迭代次數加一，清空螞蟻經過任務執行次序的記錄表，并返回步驟4-2-3-1)，否則終止計算，輸出最優解。