移動邊緣計算中計算卸載與資源分配聯合優(yōu)化策略*

劉向舉,李金賀,方賢進,王 宇

(安徽理工大學計算機科學與工程學院,安徽 淮南 232001)

1 引言

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

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

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

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

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

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

(1)考慮了多用戶、多基站和多MEC服務器的移動邊緣計算網絡模型,對通信資源和計算資源進行建模,量化了用戶執(zhí)行任務的時延和能耗,并將用戶的時延和能耗的加權和作為優(yōu)化目標。

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

(3)通過與其他基準方案進行對比,以及在相關參數的變化下對本文所提算法的性能評估,驗證了本文所提算法的性能增益。

2 系統(tǒng)模型

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

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

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

(1)

2.1 通信模型

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

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

(2)

2.2 計算模型

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

2.2.1 本地計算模型

(3)

(4)

2.2.2 卸載邊緣計算模型

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

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

(5)

其中,tran表示傳輸階段。

(6)

(7)

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

(8)

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

(9)

3 問題描述

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

(10)

本文以最小化所有用戶的系統(tǒng)開銷為目標,構造了問題P1所表示的計算卸載和資源分配的聯合優(yōu)化問題,如式(11)所示:

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

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

(11)

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

4 問題求解

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

4.1 計算資源分配

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

s.t.C3,C4

(12)

將式(12)表示為h(F),計算關于fj,i的二階偏導數,如式(13)和式(14)所示:

(13)

(14)

(15)

(16)

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

當計算資源分配確定時,即F=Fo,問題P1轉換成式(17):

s.t.C1,C2

(17)

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

4.2.1 種群初始化及編碼

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

(18)

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

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

Figure 2 Code example

4.2.2 適應度函數

適應度函數用來評估解的可行性。WOA適用于解決最小化問題,式(17)為最小化問題,因此式(17)不需要修改,適應度函數如式(19)所示:

Fitness(Y)=Z(Y,Fo)

(19)

4.2.3 種群更新

(1) 非線性收斂因子。

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

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

(20)

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

(21)

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

C=2·r

(22)

A=2a·r-a

(23)

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

(24)

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

當系數|A|>1時算法進行探索階段,即尋找獵物,如式(25)所示:

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

(25)

其中,Xrand表示通過隨機選擇的鯨魚在當前鯨魚種群中的位置。

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

(26)

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

(2)自適應慣性權重。

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

(27)

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

在加入自適應慣性權重更新策略后,將收縮包圍和螺旋更新機制分別更新為式(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)

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

(3) 反饋機制。

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

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

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

步驟2根據式(19)計算每個鯨魚個體的適應度值,根據最小適應度準則,獲得當前最優(yōu)解;

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

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

步驟5計算每個個體的適應度值,如果存在最佳值,則更新鯨魚的最優(yōu)位置以及目標函數值;

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

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

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

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

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

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

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

5 實驗仿真

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

5.1 仿真場景與參數設置

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

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

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

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

(4)文獻[25]中的雙層優(yōu)化方法:上層通過改進的蟻群算法求解,下層優(yōu)化問題采用單調優(yōu)化方法求解。

5.2 性能分析

5.2.1 與窮舉法的性能比較

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

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

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

Figure 4 Comparison of Running time comparison of the proposed algorithm and exhaustive method圖4 與窮舉法的運行時間比較

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

5.2.2 WOA改進策略對性能的影響

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

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

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

5.2.3 收斂性分析

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

Figure 6 Effect of number of iterations on system overhead圖6 迭代次數對系統(tǒng)開銷的影響

5.2.4 用戶數量的影響

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

Figure 7 Impact of number of users on system overhead圖7 用戶數量對系統(tǒng)開銷的影響

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

5.2.5 任務屬性對系統(tǒng)開銷的影響

本文還比較了計算任務在不同的輸入數據大小和所需的任務工作量時的系統(tǒng)開銷?？紤]了MEC服務器的2種配置情況,其中,同構服務器的計算資源為fm=20 GHz,異構服務器的計算資源為fm=10 GHz,20 GHz,30 GHz。

圖8展示了任務所需工作量對不同算法的系統(tǒng)開銷的影響。可以看出,隨著所需CPU周期數的增加,所有方案的系統(tǒng)開銷都呈上升趨勢。這是因為隨著任務所需計算周期數的不斷增加,用戶需要更多的計算資源來處理任務,導致更大的時延和能耗,從而系統(tǒng)開銷也隨著增加。從曲線變化的程度可以看出,在同一任務所需工作量的情況下,本文算法能夠實現最小的系統(tǒng)開銷,且具有更好的穩(wěn)定性,因為當本地用戶設備有限的計算資源無法滿足任務需求時能夠選擇最優(yōu)的MEC服務器,這是影響系統(tǒng)開銷的關鍵。

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

圖9展示了任務的輸入數據大小對系統(tǒng)開銷的影響,輸入數據大小的增加會導致任務在傳輸階段的時延和能耗增加,從而導致任務在卸載過程中的系統(tǒng)開銷增加。實驗結果表明,數據量小、計算量大的卸載任務比數據量大、計算量小的任務可以獲得更好的結果。此外,同構服務器設置中的所有方案的性能與異構服務器設置中差異微乎其微,說明本文提出的方案同樣能夠應用于不同的配置中。

Figure 9 Impact of the size of input data of the task on the system overhead圖9 任務的輸入數據大小對系統(tǒng)開銷的影響

5.2.6 用戶偏好的影響

圖10展示了用戶對時間的偏好值從0.1變化到0.9時用戶時延和能耗的變化情況,同時對比了用戶數為100和150時的情況。可以看出,平均時間消耗隨著時間權重的增加而減少,且以更高的能量消耗為代價,不同用戶數量受用戶時延權重的影響曲線變化一致。

Figure 10 Impact of user latency weights on latency and energy consumption圖10 用戶時延權重對時延和能耗的影響

6 結束語

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