基于偏好和虛擬適應(yīng)度的兩階段依賴任務(wù)卸載算法

摘要： 針對(duì)云邊端協(xié)同環(huán)境中依賴任務(wù)卸載時(shí)效率低以及任務(wù)卸載失敗的問(wèn)題， 提出一種基于偏好和虛擬適應(yīng)度的兩階段依賴任務(wù)卸載算法. 第一階段， 根據(jù)提出的二維卸載偏好因子對(duì)依賴任務(wù)的部分子任務(wù)進(jìn)行直接卸載決策， 從而有效縮小遺傳算法初始種群的規(guī)模. 第二階段， 提出基于虛擬適應(yīng)度的啟發(fā)式交叉方法， 并對(duì)基于參考點(diǎn)的快速非支配排序遺傳算法（non-dominated sorting genetic algorithm Ⅲ， NSGA-Ⅲ）的交叉算子進(jìn)行改進(jìn)， 保留了種群多樣性并提升了算法收斂速度， 最后使用改進(jìn)的算法對(duì)所有依賴任務(wù)的子任務(wù)進(jìn)行最優(yōu)卸載決策集的搜索. 實(shí)驗(yàn)結(jié)果表明， 與其他算法相比， 該算法在任務(wù)完成時(shí)間、 任務(wù)能耗和邊緣云集群成本方面平均優(yōu)化了10.2%～18.3%， 并且將任務(wù)失敗率平均降低了10.7%～25.6%.

關(guān)鍵詞： 云邊端協(xié)同環(huán)境； 依賴任務(wù)卸載； 多目標(biāo)優(yōu)化； 虛擬適應(yīng)度； 遺傳算法

中圖分類號(hào)： TP393" 文獻(xiàn)標(biāo)志碼： A" 文章編號(hào)： 1671-5489（2024）04-0923-10

Two-Stage Dependent Task Offloading AlgorithmBased on Preference and Virtual Fitness

DONG Liyan1，2， QI Jingze1， LIU Yuanning1，2， FENG Jiahui1

（1. College of Computer Science and Technology， Jilin University， Changchun 130012， China;

2. Key Laboratory of Symbolic Computation and Knowledge Engineering of Ministry of Education，Jilin University， Changchun 130012， China）

Abstract： Aiming at the problem of low efficiency and failure of dependent task offloading" in the cloud-edge-end architecture， we proposed a two-stage" dependent task offloading algorithm based on preference and virtual fitness. In the first stage， based on the proposed two-dimensional offloading preference factor， "direct offloading decisions were made for some sub-tasks of the dependent tasks， thus effectively reducing the size of the initial population of the genetic algorithm.

In the second stage， we proposed a heuristic crossover method based on virtual fitness" to improve the crossover operator of" the fast non-dominated sorting genetic algorithm Ⅲ（NSGA-Ⅲ） based on reference points， which preserved the diversity of population and improved the convergence speed of the algorithm. Finally， we used" the improved algorithm to search for the optimal offloading decision set" for the subtasks of all dependent tasks. The experimental results show that compared with other algorithms， the proposed algorithm optimizes task completion time， task energy consumption and edge cloud cluster cost by 10.2%—18.3% on average and reduces the task failure rate by 10.7%—25.6% on average.

Keywords： cloud-edge-end architecture; dependent task offloading; multi-objective optimization; virtual fitness; genetic algorithm

隨著智能應(yīng)用和物聯(lián)網(wǎng)設(shè)備的快速發(fā)展［1］， 應(yīng)用程序產(chǎn)生的任務(wù)對(duì)計(jì)算資源和存儲(chǔ)資源的需求顯著激增［2］. 但本地移動(dòng)設(shè)備資源和邊緣計(jì)算資源［3＼|4］相對(duì)有限， 無(wú)法支持所有任務(wù)的資源需求， 并且傳統(tǒng)云計(jì)算范式存在高延遲問(wèn)題［5］， 因此云邊端協(xié)同計(jì)算架構(gòu)是一個(gè)更具前景的解決方案［6-7］， 其中邊緣云集群能滿足高實(shí)時(shí)性和低延遲的任務(wù)需求［8-9］， 中心云集群能分擔(dān)邊緣云集群的負(fù)載壓力［10］.

真實(shí)場(chǎng)景中， 許多應(yīng)用任務(wù)由多個(gè)有前驅(qū)后繼關(guān)系的子任務(wù)組成， 這樣的任務(wù)稱為依賴任務(wù)［11］， 而任務(wù)卸載是指將本地移動(dòng)設(shè)備產(chǎn)生的任務(wù)卸載到云環(huán)境的虛擬機(jī)中執(zhí)行. Xu等［12］提出了一種基于博弈論的兩階段依賴任務(wù)卸載算法， 但僅以能耗優(yōu)化為主要目標(biāo). Yuan等［13］提出了一種基于遺傳模擬退火的粒子群優(yōu)化算法， 解決了云邊端協(xié)同環(huán)境中依賴任務(wù)的卸載問(wèn)題， 但僅以降低成本為主要目標(biāo). 文獻(xiàn)［14-16］針對(duì)邊緣計(jì)算范式中依賴任務(wù)卸載問(wèn)題都給出了有效的改進(jìn)方法， 但缺乏對(duì)邊緣計(jì)算資源相對(duì)有限性的考慮， 沒(méi)有將邊緣云與中心云相結(jié)合. Liu等［17］提出了一種基于改進(jìn)強(qiáng)度Pareto進(jìn)化算法的多目標(biāo)卸載算法， 以解決依賴任務(wù)卸載問(wèn)題， 但僅考慮了延遲和能耗的目標(biāo)， 未考慮邊緣服務(wù)器成本. Shahidinejad等［18］利用基于擁擠度的快速非支配排序遺傳（non-dominated sorting genetic algorithm Ⅱ， NSGA-Ⅱ）算法提出了一種基于元啟發(fā)式的加載機(jī)制， 對(duì)云邊端協(xié)同環(huán)境中任務(wù)卸載問(wèn)題進(jìn)行以能耗和執(zhí)行時(shí)間為目標(biāo)的優(yōu)化， 但未考慮邊緣云集群成本和任務(wù)失敗率指標(biāo). 相比NSGA-Ⅱ算法， NSGA-Ⅲ算法［19］引入了參考點(diǎn)對(duì)種群個(gè)體進(jìn)行選擇操作， 從而增強(qiáng)其全局搜索能力［20］， 更適合高維目標(biāo)的優(yōu)化.

本文將云邊端協(xié)同環(huán)境中依賴任務(wù)的卸載問(wèn)題視為多目標(biāo)優(yōu)化問(wèn)題， 構(gòu)建任務(wù)完成時(shí)間、 能耗和成本的多維優(yōu)化目標(biāo)， 提出一種基于偏好和虛擬適應(yīng)度的兩階段依賴任務(wù)卸載算法. 第一階段， 根據(jù)所有依賴任務(wù)信息和設(shè)備環(huán)境信息構(gòu)建二維卸載偏好因子， 從而得到部分子任務(wù)的卸載位置， 進(jìn)而對(duì)初始種群的部分基因進(jìn)行預(yù)設(shè)定； 第二階段， 本文提出基于虛擬適應(yīng)度的交叉方法， 從而改進(jìn)NSGA-Ⅲ算法的交叉操作， 最后通過(guò)改進(jìn)的NSGA-Ⅲ算法對(duì)所有依賴任務(wù)的卸載決策進(jìn)行Pareto最優(yōu)解集的搜索.

1 模型定義

1.1 系統(tǒng)模型

云邊端協(xié)同環(huán)境模型如圖1所示.

本地移動(dòng)設(shè)備層會(huì)產(chǎn)生大量待處理任務(wù)， 可卸載至中心云和邊緣云. 該體系架構(gòu)將整個(gè)中心云集群層作為一個(gè)整體. 邊緣云集群層包括R個(gè)邊緣云集群， 每個(gè)邊緣云集群下劃分出U個(gè)虛擬機(jī)、 1個(gè)基站并服務(wù)于M個(gè)本地移動(dòng)設(shè)備DEVr. 依賴任務(wù)可表示為有向無(wú)環(huán)（DAG）圖［21］， 如圖2所示." 本文所用符號(hào)及其含義如下： R表示邊緣云集群層下邊緣云集群的數(shù)量； ecr表示邊緣云集群層中編號(hào)為r的邊緣云集群， r∈{1，2，…，R}； M表示ecr所服務(wù)本地移動(dòng)設(shè)備的數(shù)量； Tm，rn表示devmr需要執(zhí)行的編號(hào)為n的依賴任務(wù)， n∈{1，2，…，N}； X表示Tm，rn子任務(wù)數(shù)； tm，rnx表示編號(hào)為n的Tm，rn子任務(wù)， x∈{1，2，…，X}； prem，rnx表示tm，rnx的直接前驅(qū)任務(wù)集合； sucm，rnx表示tm，rnx的直接后繼任務(wù)集合； cpum，rnx表示完成tm，rnx執(zhí)行所需的CPU周期數(shù)； ramm，rnx表示執(zhí)行tm，rnx所需的內(nèi)存量； ipm，rnx表示tm，rnx的輸入數(shù)據(jù)量； vmm，rnx表示tm，rnx卸載到ecr上后被安排執(zhí)行的虛擬機(jī)編號(hào)； α表示路徑損耗因子； Em，rn表示Tm，rn各子任務(wù)的前驅(qū)后繼關(guān)系； Km，rn表示Tm，rn的卸載決策集； km，rnx表示tm，rnx的卸載決策； εr，u表示vmru的單位時(shí)間成本的系數(shù)； devmr表示ecr所服務(wù)編號(hào)為m的本地移動(dòng)設(shè)備， m∈{1，2，…，M}； cpultotalr，m表示devmr的CPU總量； cpulrestr，m表示devmr的CPU剩余量； ramltotalr，m表示devmr的RAM總量； ramlrestr，m表示devmr的RAM剩余量； N表示devmr需要執(zhí)行的依賴任務(wù)數(shù)； ξ表示設(shè)備芯片架構(gòu)的有效電容系數(shù)［15］； f表示設(shè)備的計(jì)算能力； P表示設(shè)備的發(fā)射功率； U表示ecr下虛擬機(jī)數(shù)量； vmru表示ecr下編號(hào)為u的虛擬機(jī)， u∈{1，2，…，U}； cputotalr，u表示vmru的CPU總量； cpurestr，u表示vmru的CPU剩余量； ramtotalr，u表示vmru的RAM總量； ramrestr，u表示vmru的RAM剩余量； δ表示ecr虛擬機(jī)資源的最佳利用率上限［22］； URru表示ecr中編號(hào)為u的虛擬機(jī)的當(dāng)前資源利用率.

1.2 執(zhí)行模型

本文執(zhí)行模型包含執(zhí)行時(shí)間和執(zhí)行能耗. 若依賴任務(wù)Tm，rn的子任務(wù)tm，rnx在計(jì)算能力為f且有效電容系數(shù)為ξ的設(shè)備d上執(zhí)行， cpum，rnx為tm，rnx執(zhí)行所需的CPU周期數(shù)， 則其執(zhí)行時(shí)間TEm，rnx，d和執(zhí)行能耗EEm，rnx，d分別為

TEm，rnx，d=cpum，rnxf，（1）

EEm，rnx，d=ξ2（f）·cpum，rnx.（2）

1.3 通信模型

當(dāng)多個(gè)設(shè)備同時(shí)占用一個(gè)信道時(shí)， 由Shannon公式可得設(shè)備a到設(shè)備b的傳輸速率Vba為

Vba=Wlog21+SbaNa，（3）

其中W為信道帶寬， Sba為信號(hào)功率， Na為噪聲功率. 則tm，rnx的輸入數(shù)據(jù)ipm，rnx從設(shè)備a卸載到設(shè)備b的傳輸時(shí)間TTm，r

nx，a，b和傳輸能耗ETm，rnx，a，b分別為

TTm，rnx，a，b=ipm，rnxVba，（4）

ETm，rnx，a，b=TTm，rnx，a，b·Pa，（5）

其中Pa為設(shè)備a的發(fā)射功率.

2 算法設(shè)計(jì)

2.1 優(yōu)化目標(biāo)構(gòu)建

tm，rnx的卸載策略km，rnx為

km，rnx=-1，中心云集群執(zhí)行，0，本地移動(dòng)設(shè)備執(zhí)行，1，邊緣云集群執(zhí)行.（6）

其中： km，rnx=-1， 表示tm，rnx卸載到中心云集群執(zhí)行； km，rnx=0， 表示tm，rnx在本地移動(dòng)設(shè)備devmr

執(zhí)行； km，rnx=1， 表示tm，rnx卸載到邊緣云集群ecr執(zhí)行.

由執(zhí)行模型可得tm，rnx的執(zhí)行時(shí)間TEm，rnx和執(zhí)行能耗EEm，rnx：

TEm，rnx=km，rnx+12

·TEm，rnx，ecr+1-km，rnx2·TEm，r

nx，c+km，rnx-1·TEm，rnx，l，（7）

EEm，rnx=km，rnx+12·EEm，r

nx，ecr+1-km，rnx2·EEm，r

nx，c+km，rnx-1·EEm，rnx，l.（8）

若tm，rnx在ecr執(zhí)行， 則執(zhí)行時(shí)間和執(zhí)行能耗分別為TEm，rnx，err和EEm，rnx，err； 若tm，rnx在devmr執(zhí)行， 則執(zhí)行時(shí)間和執(zhí)行能耗分別為TEm，rnx，l和EEm，rnx，l； 若tm，rnx在中心云集群執(zhí)行， 則執(zhí)行時(shí)間和執(zhí)行能耗分別為TEm，rnx，c和EEm，rnx，c.由通信模型， ipm，rnx的傳輸時(shí)間和傳輸能耗分別為TTm，rnx和ETm，rnx：

TTm，rnx=km，rnx+12·TTm，

rnx，ecr+1-km，rnx2·TTm，rnx，c，（9）

ETm，rnx=km，rnx+12·ETm，r

nx，ecr+1-km，rnx2·ETm，rnx，c.（10）

若tm，rnx在ecr執(zhí)行， 則ipm，rnx的傳輸時(shí)間和傳輸能耗分別為TTm，rnx，ecr和ETm，rnx，ecr； 若tm，rnx在中心云集群執(zhí)行， 則ipm，rnx的傳輸時(shí)間和傳輸能耗分別為TTm，rnx，c和ETm，rnx，c.就緒時(shí)間TRm，rnx是指tm，rnx可以開(kāi)始執(zhí)行的最早時(shí)間， 即tm，rnx前驅(qū)子任務(wù)最長(zhǎng)完成時(shí)間與ipm，rnx傳輸時(shí)間相比的最大值， 即TRm，rnx=max{TTm，rnx，maxi∈perm，rnx{TRm，rni+TEm，rni}}.（11）

Tm，rn的完成時(shí)間TFm，rn為結(jié)束任務(wù)tm，rnx的就緒時(shí)間TRm，rnx與執(zhí)行時(shí)間TEm，rnx的總和， 即TFm，rn=TRm，rnx+TEm，rnx.（12）

tm，rnx的能耗Em，rnx為ipm，rnx傳輸能耗與執(zhí)行能耗的總和， Tm，rn的總能耗Em，rn為所有子任務(wù)的總能耗與計(jì)算依賴任務(wù)卸載方案算法能耗Em，rnDAG的總和， 即Em，rn=∑Xi=1Em，rnx+Em，rnDAG=∑Xi=1（ETm，rni+EEm

，rni）+Em，rnDAG.（13）

Tm，rn的邊緣云集群成本根據(jù)子任務(wù)執(zhí)行時(shí)間計(jì)算， 即其所有子任務(wù)的邊緣云集群成本之和CECm，rn：

CECm，rn=" ∑i∈{xkm，rnx=1 amp; x∈{1，2，…，X}}CECm，rnx=∑i∈{

xkm，rnx=1 amp; x∈{1，2，…，X}}TEm，rnx·εr，vmm，rni.（14）

基于上述分析， 本文將云邊端協(xié)同環(huán)境中依賴任務(wù)卸載問(wèn)題形式化為一個(gè)多目標(biāo)優(yōu)化問(wèn)題P， 構(gòu)建任務(wù)完成時(shí)間TFm，rn、 任務(wù)能耗Em，rn和邊緣云集群成本CECm，rn的多維優(yōu)化目標(biāo)， 即

P： minkm，rnx，vmm，rnx{TFm，rn，Em，rn，CECm，rn}，

s.t. C1： km，rnx=-1，mini={1，2，…，U}{URri}≥δ，0，本地移動(dòng)設(shè)備執(zhí)行，

1，mini={1，2，…，U} {URri}lt;δ，

C2： vmm，rnx=j，km，rnx=1，0，km，rnx=0 或 km，rnx=-1，

j∈{1，2，…，U}，（15）

其中： 約束C1表示km，rnx卸載決策的取值范圍和約束， URri表示ecr中編號(hào)為i虛擬機(jī)的資源利用率， ecr中虛擬機(jī)資源利用率的最小值表示ecr資源利用率， 當(dāng)ecr資源利用率未達(dá)到最優(yōu)上限δ時(shí)， 將任務(wù)卸載到邊緣云集群執(zhí)行， 否則， 將任務(wù)卸載到中心云集群執(zhí)行; 約束C2表示當(dāng)卸載決策km，rnx≠1時(shí)， 子任務(wù)的虛擬機(jī)卸載編號(hào)vmm，rnx為0， 否則為vmm，rnx分配數(shù)值， 數(shù)值范圍為邊緣云集群ecr中的虛擬機(jī)編號(hào)集合.

2.2 基于偏好的卸載決策算法

依賴任務(wù)可劃分為數(shù)據(jù)密集型和計(jì)算密集型［23］， 這兩種類型不互斥. 本文提出二維卸載偏好因子對(duì)子任務(wù)進(jìn)行類型偏好設(shè)置， 設(shè)KRm，rn為Tm，rn子任務(wù)的二維卸載偏好因子集合， krm，rnx表示tm，rnx的二維卸載偏好因子， krm，rnx由一個(gè)二元組（computem，rnx，datam，rnx）表示：

krm，rnx=（1，1），cpum，rnxlt;cpulrestr，m， ramm，rnxlt;raml

restr，m， ipm，rnxlt;ipm，rnx，（1，0），cpum，rnxlt;cpulrestr，m

， ramm，rnxlt;ramlrestr，m， ipm，rnx≥ipm，rnx，（-1，1），cpul

restr，m≤cpum，rnxlt;cpultotalr，m， ramlrestr，m≤ramm，rnxlt;raml

totalr，m， ipm，rnxlt;ipm，rnx，（-1，0），cpulrestr，m≤cpum

，rnxlt;cpultotalr，m， ramlrestr，m≤ramm，rnxlt;ramltotalr，m， ip

m，rnx≥ipm，rnx，（0，1），cpum，rnx≥cpultotalr，m， ramm，rn

x≥ramltotalr，m， ipm，rnxlt;ipm，rnx，（0，0），cpum，rnx≥cpultot

alr，m， ramm，rnx≥ramltotalr，m， ipm，rnx≥ipm，rnx，（16）

ipm，rn=1X∑Xi=1ipm，rnx，（17）

其中： computem，rnx表示是否為計(jì)算密集型， 1為否， 0為是， -1趨于中間； datam，rnx表示是否為數(shù)據(jù)密集型， 1為否， 0為是； ipm，rn為Tm，rn子任務(wù)輸入數(shù)據(jù)的平均值.

首先根據(jù)式（16）得到KRm，rn， 然后devmr將所有依賴任務(wù)信息和KRm，rn發(fā)送到ecr基站， 根據(jù)ecr的計(jì)算屬性條件Θm，rnx， 得到部分子任務(wù)的卸載決策Km，rn. 計(jì)算屬性條件Θm，rnx定義為Θm，rnx=1，cpum，rnxlt;δ·cpurmin， ramm，rnxlt;δ·ramr

min，-1，cpum，rnx≥δ·cpurmax， ramm，rnx≥δ·ramrmax，0，其他，（18）

其中ramrmax和cpurmax分別為ecr中虛擬機(jī)的最大剩余內(nèi)存容量和最大剩余CPU容量， ramrmin和cpurmin分別為ecr中虛擬機(jī)的最小剩余內(nèi)存容量和最小剩余CPU容量.

綜上， 基于偏好的卸載決策算法如下.

算法1 基于偏好的卸載決策算法.

輸入： 任務(wù)信息Tm，rn， 本地移動(dòng)設(shè)備信息devmr， 邊緣云集群信息ecr;

輸出： 二維卸載偏好因子集合KRm，rn， Tm，rn部分子任務(wù)的卸載決策集合Km，rn;

步驟1） 初始化KRm，rn，Km，rn，Θm，rn和Qm，rn， 根據(jù)式（17）計(jì)算ipm，rn；

步驟2） For tm，rnx∈Tm，rn do：

步驟3） 根據(jù)式（16）計(jì)算krm，rnx=（computem，rnx，datam，rnx）并且{krm，rnx}∪KRm，rn；

步驟4） If ipm，rnxlt;ipm，rn then datam，rnx=1并且{tm，rnx}∪Qm，rn；

步驟5） Else datam，rnx=0；

步驟6）" If computem，rnx=1 then km，rnx=0并且{km，rnx}∪Km，rn；

步驟7）" Else {tm，rnx}∪Qm，rn;

步驟8）" End if

步驟9） End if

步驟10） End for

步驟11） For tm，rnx∈Qm，rn do：

步驟12）" 根據(jù)式（18）計(jì)算Θm，rnx;

步驟13）" If Θm，rnx=1， （krm，rnx=（0，1）或krm，rnx=（0，0）） then km，rnx=1并且{km，rnx}∪Km，rn；

步驟14）" Else if Θm，rnx=-1， （krm，rnx=（0，1）或krm，rnx=（0，0）） then km，rnx=-1并且{km，rnx}∪Km，rn；

步驟15）" End if

步驟16） End for.

2.3 基于虛擬適應(yīng)度交叉方法的NSGA-Ⅲ算法

本文對(duì)NSGA-Ⅲ算法的初始種群、 交叉操作和變異操作進(jìn)行優(yōu)化和改進(jìn).

構(gòu)建初始種群： 首先由隨機(jī)的方式產(chǎn)生初始種群， 其中每個(gè)個(gè)體包含N條染色體， 染色體數(shù)量等于依賴任務(wù)的數(shù)量， 每條染色體代表該依賴任務(wù)的子任務(wù)的一組決策， 每條染色體上基因的數(shù)量等于該染色體對(duì)應(yīng)的依賴任務(wù)的子任務(wù)數(shù)量， 每個(gè)基因代表每個(gè)子任務(wù)的決策. 將2.2節(jié)得到的部分子任務(wù)卸載決策填入初始種群， 即算法會(huì)根據(jù)得到的部分卸載策略對(duì)每個(gè)個(gè)體的部分基因進(jìn)行預(yù)設(shè)定， 通過(guò)這種方式對(duì)初始種群進(jìn)行預(yù)處理， 從而優(yōu)化初始種群.

交叉操作： 本文將交叉操作分為對(duì)初始種群交叉操作和對(duì)非初始種群交叉操作. 對(duì)于非初始種群， 使用基于虛擬適應(yīng)度的啟發(fā)式交叉方法. 在對(duì)種群個(gè)體進(jìn)行非支配排序的過(guò)程中， 需要給每個(gè)非支配層指定一個(gè)虛擬適應(yīng)度值， 非支配排序?qū)蛹?jí)越低， 虛擬適應(yīng)度值越大； 反之， 虛擬適應(yīng)度值越小. 這樣可以保證在交叉操作中層級(jí)較低的非支配個(gè)體有更多機(jī)會(huì)被選擇進(jìn)入下一代， 使算法以最快的速度收斂于最優(yōu)區(qū)域. 對(duì)基因?yàn)镻1和P2的父代個(gè)體， 其虛擬適應(yīng)度分別為V1和V2， 設(shè)P1的非支配排序?qū)蛹?jí)低于P2的非支配排序?qū)蛹?jí)， 則V1gt;V2， 其交叉操作如下， 并生成后代個(gè)體S1和S2：

S1=V1V1+V2·P1+V2V1+V2·P2，S2=V2V1+V2·P1+V1V

1+V2·P2.（19）

變異操作： 在依賴任務(wù)卸載問(wèn)題的場(chǎng)景下， 變異率太高會(huì)導(dǎo)致收斂過(guò)慢， 退化為隨機(jī)搜索， 變異率太低則會(huì)導(dǎo)致陷入局部最優(yōu)； 當(dāng)變異算子保持在［0.010，0.025］時(shí)， 結(jié)果能保持在較優(yōu)的狀態(tài)［24］.

基于虛擬適應(yīng)度交叉的NSGA-Ⅲ算法如下.

算法2 基于虛擬適應(yīng)度交叉方法的NSGA-Ⅲ算法.

輸入： KRm，rn，Km，rn，Tm，rn，devmr，ecr， 中心云集群信息;

輸出： 依賴任務(wù)卸載決策的Pareto最優(yōu)解集;

步驟1） 隨機(jī)創(chuàng)建初始種群P， 根據(jù)Km，rn對(duì)P部分基因進(jìn)行預(yù)設(shè)定， 得到種群P*， t=1;

步驟2） While t≤最大迭代次數(shù) do：

步驟3）"" If 首次迭代 then

步驟4）""" 進(jìn)行隨機(jī)交叉和變異操作， 得到新的子代種群Qt， 獲取父子代并集Rt=P*∪Qt;

步驟5）" Else 通過(guò)式（19）進(jìn)行交叉和變異操作， 得到新的子代種群Qt， 獲取父子代并集Rt=Pt∪Qt；

步驟6）" 對(duì)Rt進(jìn)行快速非支配等級(jí)劃分（F1，F(xiàn)2，…）=FNS（Rt）， 初始化精英選擇的子代集合St， i=1；

步驟7）"" while Stlt;N0 do：//每次迭代要選出N0個(gè)個(gè)體作為新一代種群

步驟8）""" St=St∪Fi；

步驟9）""" i=i+1；

步驟10）" End while

步驟11）" 得到最后一個(gè)前沿l=i-1；

步驟12）" If St=N then Pt+1=St；

步驟13）" Else基于參考點(diǎn)進(jìn)行選擇最后一個(gè)前沿的操作［18］；

步驟14）" End if

步驟15）" t=t+1；

步驟16） End while.

3 實(shí)驗(yàn)結(jié)果與分析

3.1 對(duì)比算法

將本文算法與下列5種算法進(jìn)行對(duì)比實(shí)驗(yàn).

1） 完全本地執(zhí)行算法（AL）： 將所有依賴任務(wù)的子任務(wù)放置在本地移動(dòng)設(shè)備上處理.

2） 完全邊緣云集群卸載算法（AM）： 將所有依賴任務(wù)的子任務(wù)卸載到邊緣云集群處理.

3） 隨機(jī)卸載算法（R）： 所有依賴任務(wù)的子任務(wù)通過(guò)隨機(jī)算法進(jìn)行任務(wù)卸載.

4） NSGA-Ⅱ算法： 所有子任務(wù)通過(guò)NSGA-Ⅱ算法得到卸載決策的Pareto最優(yōu)解集.

5） NSGA-Ⅲ算法： 所有子任務(wù)通過(guò)NSGA-Ⅲ算法得到卸載決策的Pareto最優(yōu)解集.

3.2 仿真環(huán)境設(shè)置

基于圖1模型， 本文設(shè)計(jì)一個(gè)由中心云集群、 邊緣云集群和本地移動(dòng)設(shè)備組成的仿真環(huán)境. 所有實(shí)驗(yàn)測(cè)試均在如表1所示的3種型號(hào)設(shè)備中進(jìn)行， 仿真環(huán)境相關(guān)參數(shù)列于表2.

本文實(shí)驗(yàn)任務(wù)數(shù)據(jù)集由仿真環(huán)境任務(wù)生成器隨機(jī)生成得到300～900個(gè)依賴任務(wù).

3.3 模擬實(shí)驗(yàn)結(jié)果分析

將本文算法與其他5種基線算法的實(shí)驗(yàn)結(jié)果進(jìn)行比較， 實(shí)驗(yàn)結(jié)果均為5次實(shí)驗(yàn)取平均值. 本文首先統(tǒng)計(jì)了平均完成時(shí)間、 平均完成能耗以及邊緣云集群成本這3個(gè)指標(biāo)的性能對(duì)比， 結(jié)果列于表3和表4.

由表3和表4可見(jiàn)： AL算法中所有任務(wù)都在本地執(zhí)行， 其邊緣云集群成本為0且平均任務(wù)完成時(shí)間最長(zhǎng)， 隨著依賴任務(wù)的子任務(wù)數(shù)量增多， 平均任務(wù)完成時(shí)間和能耗顯著增長(zhǎng); AM算法中所有任務(wù)都在邊緣云服務(wù)器執(zhí)行， 其邊緣云集群成本最高， 當(dāng)本地移動(dòng)設(shè)備或依賴任務(wù)子任務(wù)數(shù)的數(shù)量增加時(shí)， 邊緣云服務(wù)器的負(fù)載也越來(lái)越高; R算法通過(guò)隨機(jī)方式選擇卸載的位置， 其指標(biāo)通常有較大的波動(dòng)； NSGA-Ⅱ算法、 NSGA-Ⅲ算法和本文算法都屬于多目標(biāo)優(yōu)化算法， 與上述3種算法相比， 這3種算法性能更好. 本文算法基于NSGA-Ⅲ算法， 通過(guò)二維卸載偏好因子優(yōu)化初始種群， 基于虛擬適應(yīng)度改進(jìn)了遺傳算法的交叉因子， 在保證種群多樣性的基礎(chǔ)上增加算法收斂速度， 減少算法搜索時(shí)間， 使實(shí)驗(yàn)指標(biāo)呈現(xiàn)出更優(yōu)的任務(wù)卸載性能. 相比其他兩種多目標(biāo)優(yōu)化算法， 本文算法對(duì)上述3個(gè)指標(biāo)平均優(yōu)化了10.2%～18.3%.

為進(jìn)一步評(píng)估本文算法， 下面對(duì)6種算法的任務(wù)失敗率指標(biāo)進(jìn)行對(duì)比實(shí)驗(yàn). 實(shí)驗(yàn)設(shè)置平均任務(wù)完成時(shí)間的2倍作為任務(wù)最長(zhǎng)容忍完成時(shí)間， 通過(guò)判斷任務(wù)實(shí)際執(zhí)行時(shí)間是否超出任務(wù)最長(zhǎng)容忍完成時(shí)間判斷任務(wù)是否失敗. 實(shí)驗(yàn)結(jié)果如圖3和圖4所示. 由圖3和圖4可見(jiàn)， 相比其他多目標(biāo)優(yōu)化算法， 本文算法將任務(wù)失敗率平均降低了10.7%～25.6%， 并且隨著本地移動(dòng)設(shè)備數(shù)量和子任務(wù)數(shù)量的上升， 本文算法任務(wù)失敗率的上升趨勢(shì)明顯緩于其他算法的上升趨勢(shì).

綜上所述， 針對(duì)云邊端協(xié)同環(huán)境中依賴任務(wù)卸載時(shí)效率低以及任務(wù)卸載失敗的問(wèn)題， 本文在云邊端協(xié)同環(huán)境中提出了一種基于偏好和虛擬適應(yīng)度的兩階段依賴任務(wù)卸載算法. 首先根據(jù)實(shí)時(shí)環(huán)境計(jì)算出依賴任務(wù)的二維卸載偏好因子， 并通過(guò)二維卸載偏好因子對(duì)部分子任務(wù)進(jìn)行直接偏好決策， 使用該部分決策對(duì)初始種群進(jìn)行預(yù)處理， 最后通過(guò)基于虛擬適應(yīng)度的啟發(fā)式交叉操作的NSGA-Ⅲ算法對(duì)全部任務(wù)的卸載決策進(jìn)行最優(yōu)解集的搜索， 從而在縮短算法搜索時(shí)間的情況下， 獲取Pareto最優(yōu)解集， 同時(shí)降低了任務(wù)失敗率. 實(shí)驗(yàn)結(jié)果表明， 本文算法能在合理卸載子任務(wù)的基礎(chǔ)上加快算法收斂速率， 呈現(xiàn)更好的性能和效率.

參考文獻(xiàn)

［1］ GOUDARZI M， WU H， PALANISWAMI M， et al. An Application Placement Technique for Concurrent IoT Applications in Edge and Fog Computing Environments ［J］. IEEE Transactions on Mobile Computing， 2021， 20（4）： 1298-1311.

［2］ BHARADWAJ H K， AGARWAL A， CHAMOLA V， et al. A Review on the Role of Machine Learning in Enabling IoT Based Healthcare Applications ［J］. IEEE Access， 2021， 9： 38859-38890.

［3］ SUN Z J， YANG H， LI C， et al. Cloud-Edge Collaboration in Industrial Internet of Things： A Joint Offloading Scheme Based on Resource Prediction ［J］. IEEE Internet Things Journal， 2022， 9（18）： 17014-17025.

［4］ 羅新剛， 王萬(wàn)銀． 基于正則化思想的tilt＼|Euler法在邊緣深度反演中的應(yīng)用 ＼． 吉林大學(xué)學(xué)報(bào)（地球科學(xué)版）， ２０２４， ５４（２）： ６３３＼|６４６．" （LUO X G， WANG W Y. Application of Tilt＼|Euler Method Based on Regularization in Edge Depth Inversion ＼． Journal of Jilin University （Earth Science Edition）， ２０２４， ５４（２）： ６３３＼|６４６．）

［5］ WANG S Z， WANG W L， JIA Z T， et al. Flexible Task Scheduling Based on Edge Computing and Cloud Collaboration ［J］. Computing System Science and Engineering， 2022， 42（3）： 1241-1255.

［6］ ZHOU H， WANG Z N， CHENG N， et al. Stackelberg-Game-Based Computation Offloading Method in Cloud-Edge Computing Networks ［J］. IEEE Internet Things Journal， 2022， 9（17）： 16510-16520.

［7］ GAO J X， CHANG R， YANG Z P， et al. A Task Offloading Algorithm for Cloud-Edge Collaborative System Based on Lyapunov Optimization ［J］. Cluster Computing： The Journal of Networks Software Tools and Applications， 2023， 26（1）： 337-348.

［8］ TONG Z， DENG X M， MEI J， et al. Response Time and Energy Consumption Co-offloading with SLRTA Algorithm in Cloud-Edge Collaborative Computing ［J］. Future Generation Computer Systems， 2022， 129： 64-76.

［9］ SUN X， TIAN C L， HU C H， et al. Privacy-Preserving and Verifiable SRC-Based Face Recognition with Cloud＼|Edge Server Assistance ［J］. Computing and Security， 2022， 118： 102740-1-102740-14.

［10］ GUO K， ZHANG R L. Fairness-Oriented Computation Offloading for Cloud-Assisted Edge Computing ［J］. Future Generation Computer Systems， 2022， 128： 132-141.

［11］ ZHANG Y F， CHEN J， ZHOU Y C， et al. Dependent Task Offloading with Energy-Latency Tradeoff in Mobile Edge Computing ［J］. IET Communications， 2022， 16（17）： 1993-2001.

［12］ XU F， XIE Y， SUN Y Y， et al. Two-Stage Computing Offloading Algorithm in Cloud-Edge Collaborative Scenarios Based on Game Theory ［J］. Computing Electrical Engineering， 2022， 97： 107624＼|1＼|107624＼|15.

［13］ YUAN H T， HU Q L， WANG M J， et al. Cost-Minimized User Association and Partial Offloading for Dependent Tasks in Hybrid Cloud-Edge Systems ［C］//IEEE 18th International Conference on Automation Science and Engineering. Piscataway， NJ： IEEE， 2022： 1059-1064.

［14］ KHALID M H， AHMED I A， MARWA M K， et al. New Improved Multi-objective Gorilla Troops Algorithm for Dependent Tasks Offloading Problem in Multi-access Edge Computing ［J］. Journal of Grid Computing， 2023， 21（2）： 21-1-21-24.

［15］ SONG F H， XING H L， WANG X H， et al. Offloading Dependent Tasks in Multi-access Edge Computing： A Multi-objective Reinforcement Learning Approach ［J］. Future Generation Computer Systems， 2022， 128： 333-348.

［16］ WANG P， LI K L， XIAO B， et al. Multiobjective Optimization for Joint Task Offloading， Power Assignment， and Resource Allocation in Mobile Edge Computing ［J］. IEEE Internet Things Journal， 2022， 9（14）： 11737-11748.

［17］ LIU L， CHEN H M， XU Z T. SPMOO： A Multi-objective Offloading Algorithm for Dependent Tasks in IoT Cloud-Edge-End Collaboration ［J］. Information， 2022， 13（2）： 75＼|1＼|75＼|15.

［18］ SHAHIDINEJAD A， GHOBAEI-ARANI M. A Metaheuristic-Based Computation Offloading in Edge-Cloud Environment ［J］. Journal of Ambient Intelligence and Humanized Computing， 2022， 13（5）： 2785-2794.

［19］ DEB K， JAIN H. An Evolutionary Many-Objective Optimization Algorithm Using Reference-Point-Based Nondominated Sorting Approach， Part Ⅰ： Solving Problems with Box Constraints ［J］. IEEE Transactions on Evolutionary Computation， 2014， 18（4）： 577-601.

［20］ 張西林， 林兵. 考慮多重不確定性因素的研發(fā)任務(wù)分配優(yōu)化 ［J］. 計(jì)算機(jī)系統(tǒng)應(yīng)用， 2023， 32（7）： 219-225. （ZHANG X L， LIN B. Task Allocation Optimization for Product Development Project Considering Multiple Uncertainties ［J］. Computer Systems and Applications， 2023， 32（7）： 219-225.）

［21］ LIU J G， ZHANG Y M， REN J， et al. Auction-Based Dependent Task Offloading for IoT Users in Edge Clouds ［J］. IEEE Internet of Things Journal， 2022， 10（6）： 4907-4921.

［22］ ZHU L L， FENG J H， LIU D， et al. Balanced Cloud Edge Resource Allocation Based on Conflict Conditions ［J］. IEEE Access， 2020， 8： 193449-193461.

［23］ YU M Y， LIU A F， XIONG N N， et al. An Intelligent Game-Based Offloading Scheme for Maximizing Benefits of IoT-Edge-Cloud Ecosystems ［J］. IEEE Internet Things Journal， 2020， 9（8）： 5600-5616.

［24］ YI J H， DEB S， DONG J Y， et al. An Improved NSGA-Ⅲ Algorithm with Adaptive Mutation Operator for Big Data Optimization Problems ［J］. Future Generation Computer Systems， 2018， 88： 571-585.

（責(zé)任編輯： 韓 嘯）