[發明專利]一種基于免疫退火算法的云任務調度方法及裝置

在審

• 申請號: 202210155048.4
• 申請日: 2022-02-21
• 公開（公告）號: CN114647493A
• 公開（公告）日: 2022-06-21
• 發明（設計）人: 趙莎莎;孫晨輝;張登銀;張竭;何流;秦立丹
• 申請（專利權）人: 南京郵電大學
• 主分類號: G06F9/48
• 分類號: G06F9/48;G06F9/50;G06F9/455
• 代理公司: 南京縱橫知識產權代理有限公司 32224
• 代理人: 董建林

1.一種基于免疫退火算法的云任務調度方法，其特征在于，包括如下步驟：

步驟A:獲取退火表參數，并對所述退火表參數進行初始化，所述退火表參數包括初始溫度T₀，冷卻參數α，最大迭代次數L_max，終止溫度T_e；

步驟B:將每一種虛擬機對任務的可行分配方案視為一個抗體，多個抗體組成一個抗體群，適應度函數視為抗原，將抗體和抗原的結合程度視為親和度，親和度越大表示抗體與抗原的結合程度越好；所述分配方案為隨機生成的可行虛擬機對任務的映射方案；建立虛擬機對各個任務的映射關系，初始化抗體群，計算初始化后的抗體群中每一個抗體與抗原的親和度；

步驟C:根據各抗體的親和度是否高于閾值更新抗體種群；

步驟D:對初始溫度進行降溫操作，根據以下迭代公式對溫度以及迭代次數進行更新；

T_k+1＝α*T_k

L＝L+1

其中，T_k+1是初始溫度進行降溫k次后的溫度值，即當前溫度，α是冷卻參數，用于控制溫度下降速率，L為當前迭代次數；

步驟E:計算新種群的親和度并按照由大到小排列，判斷L是否達到最大迭代次數或者當前溫度是否達到目標溫度，若達到最大迭代次數或者目標溫度，則輸出最優解；若未達到最大迭代次數或者目標溫度，則繼續進入步驟C。

2.根據權利要求1所述的基于免疫退火算法的云任務調度方法，其特征在于，建立虛擬機對各個任務的映射關系，初始化抗體群的方法包括以下步驟：

按照任務的資源需求大小形成一個先進先出隊列，然后將任務逐個分配到滿足其資源需求的當前最小工作負載的虛擬機上，形成一個初始解；

將當前所有任務分配完成后的虛擬機按照工作負載大小進行降序排序，把當前最大工作負載的虛擬機上的預期完成時間最小的任務分配到當前工作負載最小的虛擬機上，形成當前解的一個鄰域解；

循環操作，生成多個鄰域解，將每個初始解或鄰域解視為一個抗體，將所有抗體設置為一個初始抗體群。

3.根據權利要求2所述的基于免疫退火算法的云任務調度方法，其特征在于，所述適應度函數包括完工時間，各虛擬機的負載均衡度以及公平性，計算初始化后的抗體群中每一個抗體與抗原的親和度的方法包括以下步驟：

對各個任務部署到相應的虛擬機進行二進制編碼，有n個任務，m個虛擬機，定義x_ij為第i個任務分配到第j個虛擬機上執行，若第i個任務在第j個虛擬機上執行，則x_ij＝1，否則x_ij＝0；

接收用戶發出的任務請求，每個虛擬機完成各項任務需要的時間為T_j，其中比較各虛擬機的完工時間，以下式得出系統最大完工時間：

Makespan＝time_s+max(T_j)；

其中，time_s是任務調度時間，time_ij是每個任務執行完成時間，Task_i是第i個任務的任務長度，Mips_j是運行第i個任務的第j個虛擬機的計算能力；

完成第i個任務的虛擬機的工作負載為V_i：

式中，C_cpuj和C_memj分別是第j個虛擬機上當前剩余CPU和內存資源，R_cpui和R_memi分別是第i個任務所需的CPU和內存資源；計算系統的負載均衡度為B：

式中，r_j為第j個虛擬機上的總工作負載，為當前所有虛擬機的平均工作負載，

以下式計算整個系統的公平性函數：

其中，第i個任務的公平性函數β為一個常數，β∈(0,1]；

式中，E_cpui和E_memi為第i個任務期望分配到的CPU和內存資源，A_cpui和A_memi為第i個任務實際分配到的CPU和內存資源；

記總適應度函數為C(s)＝μ₁*Makespan+μ₂*B+μ₃*F，則以下式親和度函數計算當前抗體的親和度：

式中，aff(s)表示當前抗體的親和度，Makespan表示系統完工時間，B表示系統負載均衡度，F表示系統的全局公平性，μ₁，μ₂，μ₃分別是上述三個指標的權重，μ₁+μ₂+μ₃＝1。