劉向舉,李金賀,方賢進(jìn),王 宇

(安徽理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院,安徽 淮南 232001)

1 引言

隨著物聯(lián)網(wǎng)和無(wú)線通信技術(shù)的快速發(fā)展,各類移動(dòng)設(shè)備得到大量普及,越來(lái)越多先進(jìn)的無(wú)線應(yīng)用被廣泛應(yīng)用于智能設(shè)備中,如無(wú)人駕駛、電子醫(yī)療、在線游戲等[1,2]。然而,移動(dòng)設(shè)備由于物理尺寸通常較小,電池容量和計(jì)算能力有限[3],當(dāng)移動(dòng)設(shè)備同時(shí)處理多個(gè)應(yīng)用任務(wù)時(shí),可能無(wú)法滿足用戶對(duì)低時(shí)延和低能耗的需求。如何滿足用戶任務(wù)日益增長(zhǎng)的計(jì)算資源需求,成為一個(gè)迫在眉睫的問(wèn)題。移動(dòng)邊緣計(jì)算MEC(Mobile Edge Computing)[4]作為一種新的分布式計(jì)算范式應(yīng)運(yùn)而生。通過(guò)在移動(dòng)網(wǎng)絡(luò)邊緣部署高性能的MEC服務(wù)器,可以讓云計(jì)算功能更有效、無(wú)縫地實(shí)現(xiàn)到移動(dòng)網(wǎng)絡(luò)中,為用戶設(shè)備、移動(dòng)運(yùn)營(yíng)商和服務(wù)提供商等提供便利[5]。

MEC中的卸載決策和資源分配在減少執(zhí)行任務(wù)的能耗和時(shí)延方面,發(fā)揮著重要作用。目前在卸載決策研究方面,按照任務(wù)卸載的方向,可以分為設(shè)備到邊緣和邊緣到云。

(1)設(shè)備到邊緣。對(duì)于需要強(qiáng)大容量或邊緣數(shù)據(jù)聚合的應(yīng)用,移動(dòng)設(shè)備將他們的任務(wù)卸載到MEC服務(wù)器,可以為移動(dòng)設(shè)備實(shí)現(xiàn)不同的需求。為了減少任務(wù)處理延遲,文獻(xiàn)[6]考慮了子任務(wù)之間的依賴關(guān)系以及邊緣用戶之間的競(jìng)爭(zhēng),提出了一種輕量級(jí)的卸載方案,有效地減少了物聯(lián)網(wǎng)應(yīng)用程序的整體應(yīng)用延遲。為了降低移動(dòng)設(shè)備在最壞情況下的能耗,文獻(xiàn)[7]利用極值理論來(lái)界定不確定事件的發(fā)生概率,研究了受應(yīng)用程序執(zhí)行時(shí)間影響的計(jì)算卸載問(wèn)題。文獻(xiàn)[8]通過(guò)博弈論提出了一個(gè)計(jì)算卸載決策方案,用于計(jì)算均衡的多項(xiàng)式復(fù)雜度算法,目的是最小化延遲和能耗的組合成本,以確定是否將終端設(shè)備的任務(wù)卸載到MEC服務(wù)器。文獻(xiàn)[9]針對(duì)車聯(lián)網(wǎng)中單個(gè)MEC服務(wù)器無(wú)法有效解決車輛資源不足的問(wèn)題,提出了一種多MEC服務(wù)器的聯(lián)合卸載方案,有效降低了整體任務(wù)失敗率。

(2)從邊緣到云。從移動(dòng)設(shè)備卸載的任務(wù)一般由邊緣層的計(jì)算節(jié)點(diǎn)處理,如果邊緣層的任務(wù)數(shù)據(jù)不能被計(jì)算節(jié)點(diǎn)及時(shí)處理,可以進(jìn)一步卸載到云中心,以實(shí)現(xiàn)平衡過(guò)載。這種從邊緣到云的卸載方向,實(shí)際上是在邊緣-云協(xié)作方式下操作的。文獻(xiàn)[10]針對(duì)云-邊緣計(jì)算網(wǎng)絡(luò),提出了一種基于博弈論的計(jì)算卸載方法,采用逆向歸納法對(duì)提出的博弈進(jìn)行了分析,設(shè)計(jì)了一個(gè)基于梯度的迭代搜索算法來(lái)獲得最優(yōu)解。文獻(xiàn)[11]為了利用MEC系統(tǒng)中的有限資源,提出了一種云-邊-端協(xié)同任務(wù)卸載框架,結(jié)合人工蜂群ABC(Artificial Bee Colony)算法和粒子群優(yōu)化PSO(Particle Swarm Optimization)算法設(shè)計(jì)了人工粒子蜂群APS(Artificial Particle Swarm)算法,以求解卸載決策,該方案有效降低了時(shí)延和能耗。但是,上述文獻(xiàn)都沒(méi)有考慮對(duì)卸載決策后的資源進(jìn)行分配。

有效的資源分配可以進(jìn)一步提高卸載的效果,相關(guān)研究人員考慮聯(lián)合優(yōu)化卸載決策和資源分配。文獻(xiàn)[12]為了實(shí)現(xiàn)延遲最小化的工作負(fù)載優(yōu)化分配,提出了平衡初始化、資源分配和任務(wù)分配算法,有效地降低了服務(wù)延遲。文獻(xiàn)[13]研究了多用戶協(xié)同移動(dòng)邊緣計(jì)算網(wǎng)絡(luò)中的卸載決策、協(xié)作決策、計(jì)算和通信資源分配的問(wèn)題,提出一種兩級(jí)交替方法,解決了公式化的MINLP(Mixed Integer Non-Linear Program)問(wèn)題,仿真結(jié)果表明,該方法在能量效率和任務(wù)完成率上均取得了優(yōu)異的性能。文獻(xiàn)[14]針對(duì)醫(yī)療物聯(lián)網(wǎng)場(chǎng)景,提出了一種基于組合拍賣和改進(jìn)粒子群優(yōu)化的電子醫(yī)療計(jì)算卸載方法,以滿足醫(yī)療監(jiān)測(cè)中低時(shí)延、低能耗的服務(wù)質(zhì)量QoS(Quality of Service)要求。文獻(xiàn)[15]為了最小化物聯(lián)網(wǎng)節(jié)點(diǎn)的總能耗,研究了多用戶卸載、傳輸功率和MEC資源的聯(lián)合分配問(wèn)題,然后基于問(wèn)題的解耦和KKT(Karush-Kuhn-Tucker)條件導(dǎo)出的表達(dá)式解決了該問(wèn)題。

上述研究在不同的約束條件和場(chǎng)景中都能取得很好的效果,在滿足用戶不同需求、提升用戶體驗(yàn)方面取得了進(jìn)展。但是,上述研究主要針對(duì)的是單MEC服務(wù)器場(chǎng)景下的計(jì)算卸載或資源分配問(wèn)題。對(duì)于多MEC服務(wù)器的場(chǎng)景,特別是在制定聯(lián)合優(yōu)化的卸載決策、資源分配策略方面,以及如何在能耗和時(shí)延之間實(shí)現(xiàn)平衡優(yōu)化方面,上述研究尚未給出具體解決方案。因此,針對(duì)當(dāng)前實(shí)際應(yīng)用場(chǎng)景多由海量智能終端設(shè)備、多基站組成的通信環(huán)境,本文研究了多用戶、多MEC服務(wù)器場(chǎng)景下的計(jì)算卸載和資源分配問(wèn)題,并為該場(chǎng)景提出了更廣泛的計(jì)算卸載解決方案。本文具體工作如下:

(1)考慮了多用戶、多基站和多MEC服務(wù)器的移動(dòng)邊緣計(jì)算網(wǎng)絡(luò)模型,對(duì)通信資源和計(jì)算資源進(jìn)行建模,量化了用戶執(zhí)行任務(wù)的時(shí)延和能耗,并將用戶的時(shí)延和能耗的加權(quán)和作為優(yōu)化目標(biāo)。

(2)提出了聯(lián)合優(yōu)化計(jì)算卸載和資源分配的問(wèn)題,考慮到問(wèn)題的復(fù)雜性,將問(wèn)題解耦為卸載決策和計(jì)算資源分配2個(gè)子問(wèn)題。對(duì)于計(jì)算資源分配問(wèn)題,采用拉格朗日乘子法;對(duì)于卸載決策問(wèn)題,設(shè)計(jì)了改進(jìn)的鯨魚(yú)優(yōu)化算法,能在短時(shí)間內(nèi)得到問(wèn)題穩(wěn)定收斂的最優(yōu)解。

(3)通過(guò)與其他基準(zhǔn)方案進(jìn)行對(duì)比,以及在相關(guān)參數(shù)的變化下對(duì)本文所提算法的性能評(píng)估,驗(yàn)證了本文所提算法的性能增益。

2 系統(tǒng)模型

考慮一個(gè)多用戶、多基站和多MEC服務(wù)器組成的移動(dòng)邊緣計(jì)算場(chǎng)景。如圖1所示的MEC系統(tǒng)模型中,每個(gè)基站都配備一個(gè)MEC服務(wù)器,MEC服務(wù)器可以是具有計(jì)算能力的物理服務(wù)器或虛擬機(jī),并通過(guò)回程鏈路與其相關(guān)聯(lián)的基站互連。其中,有S個(gè)MEC服務(wù)器部署在網(wǎng)絡(luò)邊緣中,將MEC服務(wù)器的集合定義為M={mi,i=1,2,…,S}。K個(gè)用戶的移動(dòng)設(shè)備可以通過(guò)無(wú)線網(wǎng)絡(luò)連接基站,將其任務(wù)卸載至MEC服務(wù)器上,則用戶集合定義為N={nj,j=1,2,…,K}。在計(jì)算任務(wù)卸載的過(guò)程中,考慮的是一個(gè)移動(dòng)終端設(shè)備不切換接入點(diǎn)的準(zhǔn)靜態(tài)系統(tǒng)[16],即移動(dòng)設(shè)備每次卸載的時(shí)間段內(nèi),用戶設(shè)備的組成是不變的。在這個(gè)場(chǎng)景中,每個(gè)用戶有一個(gè)移動(dòng)設(shè)備,每個(gè)移動(dòng)設(shè)備每次僅有一個(gè)任務(wù)需要進(jìn)行處理。

Figure 1 System model of MEC圖1 MEC系統(tǒng)模型

由于每個(gè)任務(wù)可以在用戶設(shè)備上進(jìn)行本地處理,也可以卸載到任意一個(gè)MEC服務(wù)器上進(jìn)行處理,并且 MEC服務(wù)器獨(dú)立工作,用戶的計(jì)算任務(wù)是不可分割的,定義yj,i∈{0,1}為用戶nj的卸載決策。yj,i=1表示用戶nj將任務(wù)卸載至MEC服務(wù)器mi上;否則yj,i=0。本地計(jì)算用第S+1個(gè)MEC服務(wù)器mS+1表示,即yj,S+1=1。因此,K個(gè)用戶S個(gè)MEC服務(wù)器的最終卸載結(jié)果可以用一個(gè)K×(S+1)的矩陣Y來(lái)表示,如式(1)所示:

(1)

2.1 通信模型

當(dāng)用戶選擇卸載處理任務(wù)時(shí),基站通過(guò)無(wú)線信道與移動(dòng)設(shè)備相互連接,實(shí)現(xiàn)用戶計(jì)算任務(wù)的上傳和下載。采用正交頻分多址OFDMA (Orthogonal Frequency Division Multiple Access)技術(shù)進(jìn)行任務(wù)傳輸,用戶之間的干擾忽略不計(jì)。用戶nj到MEC服務(wù)器mi的上行數(shù)據(jù)傳輸速率如式(2)所示:

i=1,2,…,S,j=1,2,…,K

(2)

2.2 計(jì)算模型

每個(gè)用戶nj的計(jì)算任務(wù)的屬性用一個(gè)二元組表示為Taskj={Dj,Cj}。其中,Dj為用戶nj的任務(wù)執(zhí)行數(shù)據(jù)量;Cj為用戶nj的任務(wù)計(jì)算量,即計(jì)算該任務(wù)所需的CPU周期數(shù),任務(wù)越復(fù)雜所需的周期數(shù)越多。

2.2.1 本地計(jì)算模型

(3)

(4)

2.2.2 卸載邊緣計(jì)算模型

當(dāng)用戶的計(jì)算任務(wù)選擇由MEC服務(wù)器進(jìn)行處理時(shí),首先將計(jì)算任務(wù)傳輸至基站,然后由MEC服務(wù)器執(zhí)行計(jì)算任務(wù)。計(jì)算輸入數(shù)據(jù)包括移動(dòng)系統(tǒng)設(shè)置、程序代碼和輸入?yún)?shù),計(jì)算結(jié)果通常比輸入數(shù)據(jù)要小得多。因此,與許多研究類似,本文忽略MEC服務(wù)器將計(jì)算結(jié)果發(fā)回移動(dòng)設(shè)備的能耗和時(shí)間開(kāi)銷,只分析了卸載至MEC服務(wù)器時(shí)的數(shù)據(jù)傳輸階段和任務(wù)執(zhí)行階段。

根據(jù)式(2),數(shù)據(jù)傳輸階段用戶nj的時(shí)延如式(5)所示:

(5)

其中,tran表示傳輸階段。

(6)

(7)

在上述卸載模型的基礎(chǔ)上,nj執(zhí)行其計(jì)算任務(wù)所需的總時(shí)間Tj如式(8)所示:

(8)

總能量消耗Ej如式(9)所示:

(9)

3 問(wèn)題描述

移動(dòng)邊緣計(jì)算網(wǎng)絡(luò)中,用戶的QoS主要表現(xiàn)為任務(wù)的完成時(shí)間和能量消耗?；谏鲜鱿到y(tǒng)模型,將用戶nj的系統(tǒng)開(kāi)銷定義為時(shí)延和能耗的加權(quán)和,由于系統(tǒng)中時(shí)延和能耗的數(shù)值不在同一數(shù)量級(jí),較大值會(huì)主導(dǎo)優(yōu)化過(guò)程,本文引入λ為歸一化因子對(duì)時(shí)延、能耗進(jìn)行歸一化處理[19]。將λ定義為處理所有任務(wù)的平均時(shí)延與平均能耗之比,即λ=Tj/Ej。則用戶nj的系統(tǒng)開(kāi)銷Zj如式(10)所示:

(10)

本文以最小化所有用戶的系統(tǒng)開(kāi)銷為目標(biāo),構(gòu)造了問(wèn)題P1所表示的計(jì)算卸載和資源分配的聯(lián)合優(yōu)化問(wèn)題,如式(11)所示:

s.t.C1:yj,i∈{0,1},

C3:fj,i≥0,i=1,2,…,S,j=1,2,…,K,

(11)

其中,在目標(biāo)函數(shù)Z(Y,F)中,Y表示計(jì)算卸載決策的矩陣,F表示資源分配的矩陣。通過(guò)聯(lián)合Y和F使總系統(tǒng)開(kāi)銷最小。約束C1 和C2表示每個(gè)用戶任務(wù)只能選擇在本地執(zhí)行或最多卸載到一個(gè)服務(wù)器上執(zhí)行;約束C3表示任務(wù)卸載被分配到的計(jì)算資源是非負(fù)的;C4表示分配給同一服務(wù)器卸載用戶的總計(jì)算資源不能超過(guò)服務(wù)器可用的計(jì)算資源。

4 問(wèn)題求解

問(wèn)題P1包含2個(gè)待求解變量,即卸載決策(為整數(shù)變量和)和資源分配(為連續(xù)變量)。變量之間不僅類型不同,還存在較強(qiáng)的耦合關(guān)系,使得P1是一個(gè)具有NP-hard性質(zhì)的MINLP問(wèn)題,難以在多項(xiàng)式時(shí)間內(nèi)求解。為了解決這個(gè)問(wèn)題,本文將其分為計(jì)算資源分配和計(jì)算卸載決策2個(gè)子問(wèn)題。

4.1 計(jì)算資源分配

計(jì)算資源分配問(wèn)題只需考慮卸載到MEC服務(wù)器的用戶任務(wù)。當(dāng)卸載決策固定,即Y=Yo時(shí),定義卸載至MEC服務(wù)器mi的用戶集合Noff={nj|yj,i=1,i=1,2,…,S,j=1,2,…,K}。計(jì)算資源分配的目的是使任務(wù)在MEC服務(wù)器執(zhí)行的時(shí)延最小化,并且只與約束C3和C4有關(guān),所以問(wèn)題P1可以轉(zhuǎn)換為式(12):

s.t.C3,C4

(12)

將式(12)表示為h(F),計(jì)算關(guān)于fj,i的二階偏導(dǎo)數(shù),如式(13)和式(14)所示:

(13)

(14)

(15)

(16)

4.2 基于改進(jìn)鯨魚(yú)優(yōu)化算法的卸載策略

當(dāng)計(jì)算資源分配確定時(shí),即F=Fo,問(wèn)題P1轉(zhuǎn)換成式(17):

s.t.C1,C2

(17)

智能優(yōu)化算法是求解該問(wèn)題的有效方法。鯨魚(yú)優(yōu)化算法WOA (Whale Optimization Algorithm)應(yīng)用廣泛、參數(shù)少且易于實(shí)現(xiàn)[20,21],但收斂速度慢,容易陷入局部最優(yōu)。為了進(jìn)一步平衡WOA在任務(wù)卸載過(guò)程中的局部開(kāi)發(fā)能力和全局探索能力,提高收斂速度和精度,本文提出了一種改進(jìn)的鯨魚(yú)優(yōu)化算法IWOA (Improved Whale Optimization Algorithm)來(lái)求解卸載決策Y。

4.2.1 種群初始化及編碼

Xl(t)=randn(Num,K×(S+1))

(18)

其中,randn(Num,K×(S+1))表示隨機(jī)產(chǎn)生的一個(gè)Num×(K×(S+1))的均值為0、方差為1的標(biāo)準(zhǔn)正態(tài)分布矩陣。然后按照X1l(n,m)=Xl((S+1)×(n-1)+m)對(duì)Xl(t)中的元素進(jìn)行選取,得到一個(gè)K×(S+1)的矩陣X1l,其中,n=1,2,…,K,m=1,2,…,S+1。然后,將矩陣X1l中每行最大的值改為1,其余改為0,則得到一個(gè)滿足約束的卸載矩陣Y。

如圖2所示,假設(shè)當(dāng)前系統(tǒng)中用戶數(shù)K為3,MEC服務(wù)器數(shù)S為2,鯨魚(yú)種群數(shù)Num為2。鯨魚(yú)種群初始化后進(jìn)行編碼得到對(duì)應(yīng)的卸載決策矩陣。圖2中的卸載決策Y表示用戶n1將任務(wù)卸載至MEC服務(wù)器m1,用戶n2進(jìn)行本地計(jì)算(即m3),用戶n3將任務(wù)卸載至MEC服務(wù)器m2。

Figure 2 Code example

4.2.2 適應(yīng)度函數(shù)

適應(yīng)度函數(shù)用來(lái)評(píng)估解的可行性。WOA適用于解決最小化問(wèn)題,式(17)為最小化問(wèn)題,因此式(17)不需要修改,適應(yīng)度函數(shù)如式(19)所示:

Fitness(Y)=Z(Y,Fo)

(19)

4.2.3 種群更新

(1) 非線性收斂因子。

WOA根據(jù)鯨魚(yú)的進(jìn)食過(guò)程建立了3個(gè)數(shù)學(xué)模型:包圍獵物、泡網(wǎng)攻擊法和尋找獵物。首先,WOA以當(dāng)前最優(yōu)解作為目標(biāo)獵物,以離獵物最近的鯨魚(yú)作為最佳搜索代理。然后,其他個(gè)體鯨魚(yú)會(huì)接近目標(biāo)獵物,并逐漸更新它們的位置。這種行為可表示為式(20)和式(21):

D=|C·X*(t)-X(t)|

(20)

X(t+1)=X*(t)-A·D·I

(21)

其中,D表示搜索代理到目標(biāo)獵物的距離;I為單位向量;t為當(dāng)前迭代次數(shù);X*為局部最優(yōu)解;C、A為系數(shù),分別表示為式(22)和式(23)所示:

C=2·r

(22)

A=2a·r-a

(23)

其中,r是[0,1]的隨機(jī)數(shù),A取值依賴于a,a值隨迭代次數(shù)的增加從2線性下降到0,即a=2-2t/tmax,tmax表示最大迭代次數(shù)。距離控制系數(shù)A決定了WOA的探索和開(kāi)發(fā),當(dāng)|A|≤1時(shí),算法進(jìn)行開(kāi)發(fā)階段,其中,當(dāng)[0,1]的隨機(jī)數(shù)p<0.5時(shí),進(jìn)行包圍捕食,p≥0.5時(shí),進(jìn)行泡網(wǎng)攻擊法,如式(24)所示:

(24)

其中,D′=|X*(t)-X(t)|表示當(dāng)前鯨魚(yú)位置與獵物之間的距離,l′為[-1,1]的隨機(jī)數(shù),b為定義對(duì)數(shù)螺旋形狀的常數(shù)。

當(dāng)系數(shù)|A|>1時(shí)算法進(jìn)行探索階段,即尋找獵物,如式(25)所示:

X(t+1)=Xrand-A·D·I

(25)

其中,Xrand表示通過(guò)隨機(jī)選擇的鯨魚(yú)在當(dāng)前鯨魚(yú)種群中的位置。

然而,WOA的真實(shí)搜索過(guò)程是非線性的,甚至更加復(fù)雜。這種線性下降可能帶來(lái)2個(gè)問(wèn)題:①在早期迭代過(guò)程中,包圍獵物的行為更新較慢,收斂速度較低。如果全局最優(yōu)值出現(xiàn)在早期迭代中,搜索的精度將受到很大的影響;②當(dāng)接近最優(yōu)值時(shí),局部收斂速度會(huì)變慢。因此,本文根據(jù)不同初等函數(shù)的函數(shù)性質(zhì)和圖像特征,采用了基于指數(shù)函數(shù)的非線性收斂因子,數(shù)學(xué)表達(dá)式如式(26)所示:

(26)

其中,η,k是影響算法開(kāi)發(fā)和搜索能力的因子。經(jīng)過(guò)多次實(shí)驗(yàn),η和k分別取值為10和6,會(huì)以更大的概率出現(xiàn)|A|≤1,鯨魚(yú)種群包圍獵物概率也更大,收斂速度也更快。

(2)自適應(yīng)慣性權(quán)重。

改進(jìn)的基于非線性收斂因子的新策略在一定程度上提高了算法的性能。然而,在使用新策略時(shí),僅靠收斂因子無(wú)法平衡群體的全局探索能力和局部開(kāi)發(fā)能力。受PSO啟發(fā),添加慣性權(quán)重并結(jié)合收斂因子來(lái)調(diào)整種群的全局探索能力和局部開(kāi)發(fā)能力;并對(duì)原慣性權(quán)重的線性調(diào)整進(jìn)行了改進(jìn),提出了一種新的自適應(yīng)慣性權(quán)重更新策略,如式(27)所示:

(27)

其中,f(Pnbest)和f(Plbest)表示第t迭代時(shí)最佳位置的適應(yīng)度值和局部最佳位置的適應(yīng)度值,本文設(shè)置自適應(yīng)慣性權(quán)重中的最大慣性權(quán)重wmax=0.9,最小慣性權(quán)重wmin=0.4[22]。

在加入自適應(yīng)慣性權(quán)重更新策略后,將收縮包圍和螺旋更新機(jī)制分別更新為式(28)和式(29):

X(t+1)=w·X*(t)-A·D·T

(28)

X(t+1)=w·X*(t)+D′ebl′cos(2πl(wèi)′)

(29)

慣性權(quán)重w和非線性因子a都加快了收斂速度,但兩者有著本質(zhì)區(qū)別。a通過(guò)增加種群包圍獵物的概率來(lái)提高收斂速度。w通過(guò)改變鯨魚(yú)更新位置X*(t)所占的比例,隨著迭代次數(shù)的增加,當(dāng)目標(biāo)函數(shù)值收斂到局部最優(yōu)時(shí),慣性權(quán)重增大;當(dāng)目標(biāo)函數(shù)值分散時(shí),慣性權(quán)重減小;當(dāng)目標(biāo)函數(shù)值優(yōu)于平均值時(shí),慣性權(quán)重減小,以保留當(dāng)前鯨魚(yú);當(dāng)目標(biāo)函數(shù)值低于平均值時(shí),慣性權(quán)重增大,從而向較好的搜索區(qū)域靠攏。

(3) 反饋機(jī)制。

在WOA中,隨著迭代次數(shù)增加,鯨魚(yú)種群向當(dāng)前最接近獵物的鯨魚(yú)位置靠攏,導(dǎo)致多樣性降低。因此,容易陷入局部最優(yōu)位置。為了跳出局部最優(yōu),本文根據(jù)人工蜂群算法引入了反饋機(jī)制[23]。如文獻(xiàn)[23]所述,如果在一定的迭代次數(shù)內(nèi)最優(yōu)解不變,為了跳出局部最優(yōu)解,所有個(gè)體被再次隨機(jī)放置,并繼續(xù)迭代。按照上述思路對(duì)WOA進(jìn)行修改,若X*(t)在20次迭代中沒(méi)有變化,將隨機(jī)選取的一半鯨魚(yú)再次隨機(jī)放置,剩下的鯨魚(yú)不變化;如果X*(t)發(fā)生變化,則繼續(xù)執(zhí)行IWOA。

綜上所述,IWOA的步驟描述如下:

步驟1初始化鯨魚(yú)種群和所需的參數(shù)a、l′、tmax等,并將種群映射為卸載矩陣;

步驟2根據(jù)式(19)計(jì)算每個(gè)鯨魚(yú)個(gè)體的適應(yīng)度值,根據(jù)最小適應(yīng)度準(zhǔn)則,獲得當(dāng)前最優(yōu)解;

步驟3分別通過(guò)式(26)和式(27)更新改進(jìn)參數(shù)a和wt,隨機(jī)生成參數(shù)p,并計(jì)算|A|;

步驟4當(dāng)參數(shù)|A|≤1時(shí),通過(guò)判斷p是否大于0.5執(zhí)行式(28)包圍獵物或式(29)泡網(wǎng)攻擊法更新當(dāng)前鯨魚(yú)的位置,否則當(dāng)|A|>1時(shí)根據(jù)式(25)執(zhí)行尋找獵物機(jī)制更新當(dāng)前鯨魚(yú)的位置;

步驟5計(jì)算每個(gè)個(gè)體的適應(yīng)度值,如果存在最佳值,則更新鯨魚(yú)的最優(yōu)位置以及目標(biāo)函數(shù)值;

步驟6若最優(yōu)解在20次迭代中沒(méi)有變化,執(zhí)行反饋機(jī)制;

步驟7迭代次數(shù)加1,當(dāng)達(dá)到最大迭代次數(shù)tmax時(shí),停止迭代循環(huán);

步驟8輸出最優(yōu)位置和適應(yīng)度值。

4.3 資源分配與計(jì)算卸載決策的聯(lián)合優(yōu)化

如上所述,本文所提出的算法在每次迭代中采用IWOA求解卸載決策,然后根據(jù)給定的卸載決策,采用拉格朗日乘子法得到相應(yīng)的計(jì)算資源最優(yōu)分配,其中一個(gè)最優(yōu)解作為輸入,參與另一個(gè)求解過(guò)程,在對(duì)解進(jìn)行多次迭代后,可以得到原優(yōu)化問(wèn)題穩(wěn)定收斂的最優(yōu)解,如算法1所示。

算法1 基于鯨魚(yú)優(yōu)化算法的聯(lián)合資源分配和計(jì)算卸載算法輸入:鯨魚(yú)種群數(shù)Num、最大迭代次數(shù)tmax和相關(guān)參數(shù)。輸出:計(jì)算資源分配解、卸載決策以及問(wèn)題P1的最優(yōu)目標(biāo)函數(shù)值Z(Y*,F*)=Z*(t1)。1.初始化:迭代次數(shù)t=0、每個(gè)種群的鯨魚(yú)位置、最大適應(yīng)度值Z(t)=+∞;2.While (t

當(dāng)達(dá)到最大迭代次數(shù)時(shí),聯(lián)合優(yōu)化算法輸出最優(yōu)的卸載決策Y*、相應(yīng)的最優(yōu)計(jì)算資源分配解F*以及最小系統(tǒng)開(kāi)銷解Z(Y*,F*)=Z*(tmax)。其中,求解計(jì)算資源分配問(wèn)題時(shí),在每次迭代中需執(zhí)行|S·Noff|次操作。在IWOA中,鯨魚(yú)種群為Num,鯨魚(yú)個(gè)體的維度為d=K×(S+1),最大迭代次數(shù)為tmax,IWOA復(fù)雜度為O(Num·d·tmax)。因此,本文聯(lián)合優(yōu)化算法復(fù)雜度為O((Num·d+|S·Noff|)·tmax)。

5 實(shí)驗(yàn)仿真

為了驗(yàn)證本文提出的聯(lián)合優(yōu)化算法的有效性,在Intel?CoreTMi5-7300HQ,CPU@ 2.50 GHz,16.0 GB RAM的實(shí)驗(yàn)配置,以及MATLAB R2020b的實(shí)驗(yàn)環(huán)境中進(jìn)行了仿真實(shí)驗(yàn)。

5.1 仿真場(chǎng)景與參數(shù)設(shè)置

將通信場(chǎng)景設(shè)置為一個(gè)1000 m×1000 m的矩形區(qū)域,有10個(gè)MEC服務(wù)器均勻分布在該區(qū)域,100個(gè)用戶隨機(jī)分布在該區(qū)域。相鄰基站之間的間隔為100 m。將系統(tǒng)帶寬B設(shè)為20 MHz,背景噪聲方差N0設(shè)為-130 dBm,發(fā)射功率pn設(shè)為1 W。上行鏈路信道增益通過(guò)與距離相關(guān)的路徑損耗模型產(chǎn)生,信道增益模型為h=140.7+36.7×lgdis,其中,dis是以km為單位的用戶設(shè)備與基站之間的距離。

(1)隨機(jī)卸載方案:用戶將任務(wù)隨機(jī)卸載至本地計(jì)算或任意一個(gè)MEC服務(wù)器上。

(2)全部邊緣計(jì)算方案:所有用戶選擇將任務(wù)卸載至距離最近的MEC服務(wù)器上。

(3)文獻(xiàn)[24]中采用的基于灰狼優(yōu)化GWO(Grey Wolf Optimization)算法和WOA優(yōu)化的混合方法。

(4)文獻(xiàn)[25]中的雙層優(yōu)化方法:上層通過(guò)改進(jìn)的蟻群算法求解,下層優(yōu)化問(wèn)題采用單調(diào)優(yōu)化方法求解。

5.2 性能分析

5.2.1 與窮舉法的性能比較

為了衡量本文所提算法的有效性,本節(jié)將其與窮舉法進(jìn)行比較。窮舉法通過(guò)遍歷、比較所有可行解得到優(yōu)化問(wèn)題的全局最優(yōu)解,但算法的復(fù)雜度會(huì)隨著問(wèn)題規(guī)模的增加呈指數(shù)級(jí)增加。本文由K個(gè)用戶和S個(gè)服務(wù)器組成的系統(tǒng)中,每個(gè)用戶可以選擇在本地執(zhí)行或者卸載到一個(gè)服務(wù)器上,這種情況下窮舉法有(S+1)K種可行解,復(fù)雜度比較高,因此使用窮舉法求解本文中存在大量變量的問(wèn)題會(huì)導(dǎo)致非常長(zhǎng)的運(yùn)行時(shí)間。所以,本文在一個(gè)存在2個(gè)MEC服務(wù)器,移動(dòng)設(shè)備數(shù)量為5～10的小規(guī)模網(wǎng)絡(luò)場(chǎng)景中進(jìn)行比較。

圖3給出了分別應(yīng)用本文算法與窮舉法的系統(tǒng)開(kāi)銷,可以明顯看出,本文算法的系統(tǒng)開(kāi)銷和窮舉法的系統(tǒng)開(kāi)銷非常接近,隨著用戶數(shù)的增加系統(tǒng)開(kāi)銷都在窮舉算法的1%以內(nèi),可見(jiàn)本文的聯(lián)合優(yōu)化算法是切實(shí)可行的。

Figure 3 System overhead comparison of the proposed algorithm and exhaustive method圖3 與窮舉法的系統(tǒng)開(kāi)銷比較

Figure 4 Comparison of Running time comparison of the proposed algorithm and exhaustive method圖4 與窮舉法的運(yùn)行時(shí)間比較

圖4給出了本文所提算法和窮舉法的運(yùn)行時(shí)間隨用戶數(shù)量變化的情況。從圖4可以看出,雖然本文所提算法在最初的執(zhí)行時(shí)間比窮舉法的長(zhǎng),但隨著用戶數(shù)量的增加,窮舉法的執(zhí)行時(shí)間迅速超過(guò)本文所提算法的執(zhí)行時(shí)間。由于本文所提算法的運(yùn)行時(shí)間是線性增加的,而窮舉法的運(yùn)行時(shí)間是呈指數(shù)增長(zhǎng)的,因此在大規(guī)模網(wǎng)絡(luò)中應(yīng)用本文所提算法可以顯著減少任務(wù)卸載過(guò)程執(zhí)行的時(shí)間,提高執(zhí)行效率。

5.2.2 WOA改進(jìn)策略對(duì)性能的影響

為了分析WOA的改進(jìn)策略對(duì)結(jié)果的影響,在WOA中逐步加入本文所提出的方案。首先加入非線性收斂因子a,然后加入自適應(yīng)權(quán)重系數(shù)w,最后加入反饋系統(tǒng)即IWOA。其收斂曲線如圖5所示。

從圖5中可以看出,WOA在加入非線性收斂因子a后,收斂速度有所提高,這是由于非線性收斂因子隨著迭代次數(shù)的增加而減小得更快,從而種群也收斂得更快,但是它的準(zhǔn)確性并沒(méi)有太明顯的提高;當(dāng)同時(shí)加入非線性收斂因子和自適應(yīng)權(quán)重系數(shù)時(shí),收斂速度和精度都有顯著提高;最后,采用反饋系統(tǒng)的IWOA相比WOA減小了53.7%的系統(tǒng)開(kāi)銷,在計(jì)算精度上也得到了進(jìn)一步提高,這是因?yàn)榉答仚C(jī)制的加入增加了整個(gè)算法種群的多樣性,使算法更容易跳出局部最優(yōu)。可見(jiàn),本文的改進(jìn)策略是有效的。

Figure 5 Impact of IWOA improved strategy on system overhead圖5 IWOA改進(jìn)策略對(duì)系統(tǒng)開(kāi)銷的影響

5.2.3 收斂性分析

圖6給出了系統(tǒng)開(kāi)銷隨算法迭代次數(shù)增加的變化趨勢(shì)。由于任務(wù)在選擇隨機(jī)卸載或全部邊緣卸載時(shí)不受迭代次數(shù)的影響,因此解空間較大,且運(yùn)行結(jié)果呈現(xiàn)隨機(jī)性波動(dòng),但任務(wù)卸載至邊緣時(shí),計(jì)算資源會(huì)更豐富,系統(tǒng)開(kāi)銷比隨機(jī)卸載的小38.5%左右。文獻(xiàn)[24]和文獻(xiàn)[25]均使用與本文算法相同的編碼方式,系統(tǒng)開(kāi)銷都隨著迭代次數(shù)的增加而減小,最終收斂到最優(yōu)值。在收斂速度方面,文獻(xiàn)[24]結(jié)合了GWO和WOA,收斂速度較快,以最少的迭代次數(shù)收斂到最終解,但其最終解是最差的;本文則在300次迭代之后才接近全局最優(yōu)解,收斂性略差;文獻(xiàn)[25]由于無(wú)法避免陷入局部最優(yōu),曲線劇烈波動(dòng),多次陷入局部最優(yōu)值。在全局搜索能力方面,本文算法全局搜索能力最強(qiáng),能夠收斂到高質(zhì)量的解,當(dāng)?shù)螖?shù)為300時(shí),本文算法求得最優(yōu)解的系統(tǒng)開(kāi)銷最小,分別比文獻(xiàn)[24]和文獻(xiàn)[25]的系統(tǒng)開(kāi)銷減小了34.5%和13.1%。

Figure 6 Effect of number of iterations on system overhead圖6 迭代次數(shù)對(duì)系統(tǒng)開(kāi)銷的影響

5.2.4 用戶數(shù)量的影響

圖7為用戶數(shù)從 50增加到300時(shí),系統(tǒng)開(kāi)銷的變化情況。所有算法的系統(tǒng)開(kāi)銷都隨著用戶數(shù)的增加而增加。從卸載模型中分析,這是因?yàn)橄到y(tǒng)開(kāi)銷與時(shí)延、能耗呈線性相關(guān)的關(guān)系,當(dāng)用戶總數(shù)增加時(shí),任務(wù)量增加,處理任務(wù)的總時(shí)延和總能耗也增加。在初始用戶數(shù)量較小時(shí),各個(gè)方案的系統(tǒng)開(kāi)銷相近,因?yàn)榇藭r(shí)計(jì)算資源充足,使得開(kāi)銷差異不明顯。隨著用戶數(shù)的增加,差異越來(lái)越大,這是因?yàn)樵谟脩魯?shù)較多時(shí),對(duì)資源的需求也隨著增加,然而系統(tǒng)中可用的計(jì)算資源總量保持不變,分配給每個(gè)任務(wù)的計(jì)算資源量將逐漸減少,用戶無(wú)法選擇合理的卸載位置,導(dǎo)致可使用的計(jì)算資源較少,系統(tǒng)計(jì)算開(kāi)銷更大。當(dāng)用戶超過(guò)系統(tǒng)容量時(shí),多余的用戶只能在本地執(zhí)行,系統(tǒng)開(kāi)銷增長(zhǎng)速度更快。

Figure 7 Impact of number of users on system overhead圖7 用戶數(shù)量對(duì)系統(tǒng)開(kāi)銷的影響

隨機(jī)卸載的增長(zhǎng)速度最快,性能是所有方案中最差的,說(shuō)明了用戶選擇適當(dāng)任務(wù)卸載決策的重要性。本文算法在收斂性和穩(wěn)定性方面都優(yōu)于其他算法的,能夠充分利用移動(dòng)設(shè)備和MEC服務(wù)器上的可用資源,是5種方案中性能最好的,且更適合用于設(shè)備較多的場(chǎng)景。當(dāng)用戶數(shù)為300時(shí),本文算法的系統(tǒng)開(kāi)銷分別比文獻(xiàn)[24]的、文獻(xiàn)[25]的、全部邊緣的和隨機(jī)卸載的降低了18.1%,9.4%,32.1%和44.6%。隨著MEC環(huán)境的變化,本文算法能夠不斷調(diào)整卸載策略以獲得最優(yōu)解,因?yàn)樵黾恿朔答仚C(jī)制,提高了種群多樣性,減少了陷入局部最優(yōu)的可能性;利用非線性收斂因子和慣性權(quán)重系數(shù)改進(jìn)鯨魚(yú)個(gè)體位置更新,提高了收斂速度和精度。

5.2.5 任務(wù)屬性對(duì)系統(tǒng)開(kāi)銷的影響

本文還比較了計(jì)算任務(wù)在不同的輸入數(shù)據(jù)大小和所需的任務(wù)工作量時(shí)的系統(tǒng)開(kāi)銷。考慮了MEC服務(wù)器的2種配置情況,其中,同構(gòu)服務(wù)器的計(jì)算資源為fm=20 GHz,異構(gòu)服務(wù)器的計(jì)算資源為fm=10 GHz,20 GHz,30 GHz。

圖8展示了任務(wù)所需工作量對(duì)不同算法的系統(tǒng)開(kāi)銷的影響?？梢钥闯?隨著所需CPU周期數(shù)的增加,所有方案的系統(tǒng)開(kāi)銷都呈上升趨勢(shì)。這是因?yàn)殡S著任務(wù)所需計(jì)算周期數(shù)的不斷增加,用戶需要更多的計(jì)算資源來(lái)處理任務(wù),導(dǎo)致更大的時(shí)延和能耗,從而系統(tǒng)開(kāi)銷也隨著增加。從曲線變化的程度可以看出,在同一任務(wù)所需工作量的情況下,本文算法能夠?qū)崿F(xiàn)最小的系統(tǒng)開(kāi)銷,且具有更好的穩(wěn)定性,因?yàn)楫?dāng)本地用戶設(shè)備有限的計(jì)算資源無(wú)法滿足任務(wù)需求時(shí)能夠選擇最優(yōu)的MEC服務(wù)器,這是影響系統(tǒng)開(kāi)銷的關(guān)鍵。

Figure 8 Impact of required task workload on system overhead圖8 任務(wù)所需工作量對(duì)系統(tǒng)開(kāi)銷的影響

圖9展示了任務(wù)的輸入數(shù)據(jù)大小對(duì)系統(tǒng)開(kāi)銷的影響,輸入數(shù)據(jù)大小的增加會(huì)導(dǎo)致任務(wù)在傳輸階段的時(shí)延和能耗增加,從而導(dǎo)致任務(wù)在卸載過(guò)程中的系統(tǒng)開(kāi)銷增加。實(shí)驗(yàn)結(jié)果表明,數(shù)據(jù)量小、計(jì)算量大的卸載任務(wù)比數(shù)據(jù)量大、計(jì)算量小的任務(wù)可以獲得更好的結(jié)果。此外,同構(gòu)服務(wù)器設(shè)置中的所有方案的性能與異構(gòu)服務(wù)器設(shè)置中差異微乎其微,說(shuō)明本文提出的方案同樣能夠應(yīng)用于不同的配置中。

Figure 9 Impact of the size of input data of the task on the system overhead圖9 任務(wù)的輸入數(shù)據(jù)大小對(duì)系統(tǒng)開(kāi)銷的影響

5.2.6 用戶偏好的影響

圖10展示了用戶對(duì)時(shí)間的偏好值從0.1變化到0.9時(shí)用戶時(shí)延和能耗的變化情況,同時(shí)對(duì)比了用戶數(shù)為100和150時(shí)的情況?？梢钥闯?平均時(shí)間消耗隨著時(shí)間權(quán)重的增加而減少,且以更高的能量消耗為代價(jià),不同用戶數(shù)量受用戶時(shí)延權(quán)重的影響曲線變化一致。

Figure 10 Impact of user latency weights on latency and energy consumption圖10 用戶時(shí)延權(quán)重對(duì)時(shí)延和能耗的影響

6 結(jié)束語(yǔ)

本文研究了多用戶、多MEC服務(wù)器的計(jì)算卸載和資源分配,以最小化時(shí)延和能耗的加權(quán)和為目標(biāo),提出了一種聯(lián)合資源分配和卸載決策優(yōu)化策略。該策略由基于WOA的任務(wù)卸載決策算法和基于拉格朗日乘子法的計(jì)算資源分配算法組成,能夠獲得最優(yōu)的卸載決策、最優(yōu)分配的MEC服務(wù)器計(jì)算資源,本文的仿真結(jié)果證實(shí)了該算法的有效性及其相對(duì)于其他算法的優(yōu)越性,能夠有效降低系統(tǒng)中的計(jì)算開(kāi)銷。在未來(lái)工作中,將考慮任務(wù)之間的依賴性,進(jìn)一步優(yōu)化系統(tǒng)模型。