[發(fā)明專利]基于遺傳算法的移動云環(huán)境下協(xié)同計算卸載方法

在審

• 申請?zhí)枺?/td>: 202110758065.2
• 申請日: 2021-07-05
• 公開（公告）號: CN113672295A
• 公開（公告）日: 2021-11-19
• 發(fā)明（設(shè)計）人: 謝曉蘭;常盼;陳靈彬;劉亞榮
• 申請（專利權(quán)）人: 桂林理工大學(xué)
• 主分類號: G06F9/445
• 分類號: G06F9/445;G06N3/12
• 代理公司: 暫無信息
• 代理人: 暫無信息

1.一種基于遺傳算法的移動云環(huán)境下協(xié)同計算卸載方法，其特征在于，包括以下步驟：

步驟S1.建立系統(tǒng)模型：計算卸載系統(tǒng)模型應(yīng)用于由多個終端，一個邊緣節(jié)點和一個云端服務(wù)器組成的計算場景，應(yīng)用程序被劃分為K個子任務(wù)V＝{v₁，v₂，…，v_k}，以分布式形式部署；根據(jù)多個終端設(shè)備上應(yīng)用程序的子任務(wù)之間的約束關(guān)系構(gòu)建任務(wù)關(guān)系圖，建立由時延模型和能耗模型組成的多站點分布式計算卸載系統(tǒng)模型；

步驟S2編碼和初始化種群：使用加權(quán)海明距離構(gòu)造初始化種群，根據(jù)子任務(wù)與處理器的映射關(guān)系進行編碼，得到任務(wù)調(diào)度方案；

步驟S3構(gòu)建適應(yīng)度函數(shù)：定義適應(yīng)度函數(shù)為應(yīng)用程序計算卸載總代價的倒數(shù)，根據(jù)適應(yīng)度函數(shù)對初始種群中的個體進行選擇操作，得到新的種群；

步驟S4構(gòu)建交叉機制：選擇局部適應(yīng)度最優(yōu)的方式對新種群中的個體進行交叉操作；

步驟S5基因變異：對交叉后產(chǎn)生的染色體種群進行基因變異，構(gòu)造與當(dāng)前種群中精英染色體數(shù)目相等的隨機染色體，共同組成新一代染色體種群；

步驟S6輸出最優(yōu)解：判斷是否滿足預(yù)先設(shè)定的迭代次數(shù)最大值,若是則輸出種群中最優(yōu)個體的編碼,否則重復(fù)步驟S3-S5；

所述步驟S1中子任務(wù)之間的任務(wù)關(guān)系圖模型為G＝(V,E)，其中V表示子任務(wù)集合，E表示子任務(wù)之間的約束關(guān)系,其中表示當(dāng)前任務(wù)輸入數(shù)據(jù)大小，表示當(dāng)前任務(wù)輸出數(shù)據(jù)大小,w_k表示完成任務(wù)需要的CPU周期數(shù)；

所述步驟S1計算卸載方案為X＝{x₁,x₂,…,x_k}，其中x_k∈{-1,0,1}，-1表示計算任務(wù)在云端執(zhí)行,0表示計算任務(wù)在邊緣節(jié)點執(zhí)行,1表示計算任務(wù)在本地執(zhí)行,計算卸載方案X的計算消耗為:

其中T(X)和E(X)分別代表時延代價和能量消耗，T_OR和E_OR表示應(yīng)用程序不通過計算卸載時的時延和能量消耗，α和β表示時延和能耗的權(quán)重比值；

所述步驟S1中時延模型包括任務(wù)計算時延和數(shù)據(jù)傳輸時延，任務(wù)v_k在各站點的本地服務(wù)器上的計算時延為：

在邊緣節(jié)點的計算時延為：

在云服務(wù)器上的計算時延為：

其中，w_i表示任務(wù)大小，f_L，f_E，f_C分別表示用戶本地服務(wù)器，邊緣節(jié)點和云端的計算能力，即每秒可以提供的CPU周期數(shù),如果任務(wù)v_i和任務(wù)v_j的計算卸載目的地相同時，其數(shù)據(jù)傳輸時延為0；若兩個任務(wù)分別在處理器x和處理器y上執(zhí)行時，它們之間的數(shù)據(jù)傳輸時延為：

其中r_x，y為數(shù)據(jù)傳輸速率，則應(yīng)用程序時延模型為：

其中，表示任務(wù)的計算時延；

所述步驟S1中能量消耗模型包括計算能耗和數(shù)據(jù)通信能耗，任務(wù)v_k在各處理器的計算能耗為：

其中，表示服務(wù)器的計算功率，如果處理器為邊緣節(jié)點或者云端，此時計算能耗為0；若兩個任務(wù)分別在處理器x和處理器y上執(zhí)行時，通信能耗為：

應(yīng)用程序的能耗模型為：

所述步驟S2中使用加權(quán)海明距離初始化種群，定義加權(quán)海明距離函數(shù)為：

其中H_ij為個體i和j之間的加權(quán)海明距離，與為染色體上的基因，o_m為染色體上的各個基因的加權(quán)值；

所述步驟S2中對任務(wù)進行編碼，因應(yīng)用程序的K個子任務(wù)可以卸載到本地計算，也可以卸載到邊緣節(jié)點或者云端，因此每條染色體有三個可能值組成，即-1,0，1；

所述步驟S3的適應(yīng)度函數(shù)定義為：

在種群個體進行第i次迭代時，首先計算第i代種群中每個個體的適應(yīng)度函數(shù)值，將種群中的個體依函數(shù)值大小進行排序，選取適應(yīng)度較高的前一半個體進行交叉；

所述步驟S4構(gòu)建交叉機制不同于經(jīng)典遺傳算法的隨機選擇一個交叉點，然后互換交叉點前后的父染色體從而得到下一代，本發(fā)明采用比較兩個父染色體每一個基因的局部適應(yīng)度函數(shù)值，選擇具有更佳局部適應(yīng)度函數(shù)值的基因復(fù)制到下一代染色體中，兩條父染色體交叉后只能產(chǎn)生一條下一代染色體，局部適應(yīng)度函數(shù)為：

f_i＝w_i·t_i+(1-w_i)e_i (12)

所述步驟S5的變異過程是根據(jù)設(shè)定的突變概率改變?nèi)旧w的若干基因值，對交叉后產(chǎn)生的染色體種群進行基因變異，構(gòu)造與當(dāng)前種群中精英染色體數(shù)目相等的隨機染色體，共同組成新一代染色體種群。