劉向舉,李金賀,蔣社想

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

為了彌補(bǔ)移動(dòng)云計(jì)算(Mobile Cloud Computing,MCC)的不足,移動(dòng)邊緣計(jì)算(Mobile Edge Computing,MEC)作為一種有效的計(jì)算范例出現(xiàn)。MEC將計(jì)算和存儲(chǔ)資源從云數(shù)據(jù)中心地理分布部署到網(wǎng)絡(luò)的邊緣,可以在物理上接近用戶(hù)設(shè)備對(duì)數(shù)據(jù)進(jìn)行分析和處理,從而大大降低任務(wù)執(zhí)行的延遲和能耗,有效減輕核心網(wǎng)的流量負(fù)荷,延長(zhǎng)移動(dòng)設(shè)備的使用壽命。雖然與MCC相比,MEC具有更短的延遲和更強(qiáng)的可靠性,但它所能提供的資源量仍然遠(yuǎn)遠(yuǎn)小于MCC。因此,將移動(dòng)設(shè)備生成的所有任務(wù)都卸載到MEC服務(wù)器上是不合理的,將云資源與邊緣資源相結(jié)合,利用云資源作為邊緣資源的輔助,形成云邊協(xié)作的卸載場(chǎng)景,可以充分利用網(wǎng)絡(luò)中的現(xiàn)有資源,為不同需求的任務(wù)提供更多的卸載選擇。

計(jì)算卸載一直是一個(gè)熱門(mén)的研究焦點(diǎn)。He W等人[1]研究了一個(gè)多用戶(hù)全雙工通信的MEC系統(tǒng),考慮了功率控制、時(shí)間調(diào)度、卸載決策和用戶(hù)配對(duì)策略,提出的最優(yōu)算法有效的解決了系統(tǒng)延遲最小化問(wèn)題。羅馨玥等人[2]針對(duì)多個(gè)移動(dòng)設(shè)備的MEC系統(tǒng),考慮了在系統(tǒng)時(shí)延的約束下,提高系統(tǒng)的能量效率。然而,這些工作只考慮了如何利用邊緣服務(wù)器的資源,沒(méi)有考慮到結(jié)合云服務(wù)器的資源。因此,現(xiàn)有的工作研究了云邊緣協(xié)作環(huán)境中與計(jì)算卸載相關(guān)的問(wèn)題,張帆等人[3]針對(duì)云邊協(xié)同的計(jì)算卸載模型,以最小化時(shí)延為目標(biāo),設(shè)計(jì)了一種多任務(wù)計(jì)算卸載方法。楊君等人[4]提出了一種邊云協(xié)同計(jì)算的能耗感知資源調(diào)度方法,能夠在實(shí)時(shí)性的前提下有效降低能耗。于濱等人[5]考慮了多移動(dòng)設(shè)備組成的邊云協(xié)同系統(tǒng),為了降低移動(dòng)設(shè)備的時(shí)延,提出了基于深度強(qiáng)化學(xué)習(xí)的任務(wù)卸載算法。

上述工作只針對(duì)單一目標(biāo)進(jìn)行優(yōu)化,沒(méi)有考慮到時(shí)延和能耗的聯(lián)合優(yōu)化。因此,本文研究以時(shí)延和能耗的加權(quán)和為目標(biāo),提出了一種基于改進(jìn)的粒子群算法的卸載方法,能夠?yàn)檫呍茀f(xié)同場(chǎng)景范圍內(nèi)的所有移動(dòng)設(shè)備制定計(jì)算卸載策略。

1 系統(tǒng)模型和問(wèn)題描述

1.1 網(wǎng)絡(luò)模型

本文考慮了一個(gè)具有1個(gè)云服務(wù)器、多個(gè)MEC服務(wù)器和多個(gè)用戶(hù)的云-邊緣協(xié)作網(wǎng)絡(luò)框架,如圖1所示。其中在基站上配置了可以執(zhí)行計(jì)算密集型和數(shù)據(jù)敏感性任務(wù)的邊緣服務(wù)器,每個(gè)移動(dòng)用戶(hù)通過(guò)無(wú)線(xiàn)信道關(guān)聯(lián)到相應(yīng)基站,可以在唯一的MEC服務(wù)器上執(zhí)行計(jì)算卸載,或者邊緣節(jié)點(diǎn)通過(guò)回程鏈路將任務(wù)卸載到遠(yuǎn)程云服務(wù)器。

基站或MEC服務(wù)器集合可以表示為N={1,2,…,n,…,N},用戶(hù)移動(dòng)設(shè)備任務(wù)集合為U={1,2,…,u,…,U}。每個(gè)移動(dòng)用戶(hù)u每次都有一個(gè)不可分割任務(wù)需要執(zhí)行,任務(wù)屬性采用二元組表示為Qu={su,wu},其中su表示上傳計(jì)算的任務(wù)數(shù)據(jù)大小,wu表示處理任務(wù)所需的計(jì)算量。

1.2 通信模型

假設(shè)系統(tǒng)內(nèi)的所有移動(dòng)設(shè)備采用正交方式接入,移動(dòng)設(shè)備之間不存在干擾。系統(tǒng)中每個(gè)用戶(hù)在一定時(shí)間間隔內(nèi)位置不變,根據(jù)香農(nóng)信道容量公式,移動(dòng)用戶(hù)u與邊緣服務(wù)器n之間的上行傳輸速率可表示為

(1)

1.3 計(jì)算模型

(1) 本地計(jì)算:假設(shè)每個(gè)用戶(hù)設(shè)備具有固定且不同的CPU頻率,則用戶(hù)任務(wù)Qu在本地計(jì)算的執(zhí)行時(shí)間和能耗分別為

(2)

(3)

(2) 移動(dòng)邊緣計(jì)算:用戶(hù)將任務(wù)卸載至MEC服務(wù)器的處理主要包括3個(gè)階段:上傳數(shù)據(jù)、在MEC服務(wù)器上執(zhí)行任務(wù)和結(jié)果返回。由于任務(wù)結(jié)果數(shù)據(jù)量相對(duì)較小,任務(wù)結(jié)果在下行傳輸中的能耗和延遲可以忽略不計(jì),所以本文主要關(guān)注前2個(gè)階段。

根據(jù)式(1),移動(dòng)用戶(hù)u卸載任務(wù)Qu上行傳輸?shù)交緉時(shí)的傳輸時(shí)延和能耗分別為

(4)

(5)

(6)

(7)

式中:pedge為與MEC服務(wù)器n相聯(lián)的基站平均功率。則任務(wù)Qu卸載至邊緣計(jì)算的時(shí)延和能耗分別為

(8)

(9)

(3) 云服務(wù)器計(jì)算:當(dāng)任務(wù)卸載至云計(jì)算時(shí),任務(wù)需要先卸載至MEC服務(wù)器,再傳輸至云服務(wù)器進(jìn)行云計(jì)算和結(jié)果返回。由于云距離邊緣節(jié)點(diǎn)較遠(yuǎn),本文將不同的邊緣節(jié)點(diǎn)和云服務(wù)器之間的距離視為相等,同樣忽略了結(jié)果返回的延遲。假設(shè)邊緣節(jié)點(diǎn)上傳任務(wù)到云服務(wù)器的傳輸速率為常量Rc。任務(wù)Qu的傳輸延遲和能耗分別為

(10)

(11)

任務(wù)Qu在云服務(wù)器的執(zhí)行時(shí)間和能耗分別為

(12)

(13)

(14)

(15)

1.4 問(wèn)題優(yōu)化模型

根據(jù)上述模型,處理任務(wù)Qu的總延遲和總能耗分別為

(16)

(17)

式中:αu,βu,γu取值為0,1整數(shù)的二元變量卸載決策,當(dāng)取1時(shí)分別表示任務(wù)Qu在移動(dòng)設(shè)備本地、MEC服務(wù)器或云服務(wù)器進(jìn)行計(jì)算,由于任務(wù)只能在一個(gè)地方執(zhí)行,需滿(mǎn)足約束條件αu+βu+γu=1。

在MEC系統(tǒng)中,執(zhí)行計(jì)算任務(wù)的時(shí)延和能耗決定了QoS,由于不能同時(shí)最小化平衡2個(gè)因素,本文將系統(tǒng)總成本定義為執(zhí)行任務(wù)時(shí)延和能耗的加權(quán)和,則有

(18)

式中:λ為時(shí)間成本和能量消耗的加權(quán)系數(shù),可以根據(jù)實(shí)際需求進(jìn)行調(diào)整。

本文優(yōu)化目標(biāo)是通過(guò)優(yōu)化卸載決策來(lái)最小化所有任務(wù)在邊緣云之間執(zhí)行總成本C,優(yōu)化問(wèn)題表述如下

s.t.C1:αu,βu,γu∈{0,1}

C2:αu+βu+γu=1

C4:0≤λ≤1

(19)

式中:約束C1、C2表示任務(wù)只能在一個(gè)地方被處理,約束C3為給移動(dòng)設(shè)備任務(wù)分配的計(jì)算資源約束;約束C4限制時(shí)延和能耗的權(quán)重和為1。當(dāng)用戶(hù)數(shù)和基站數(shù)目較大時(shí),問(wèn)題(19)為大規(guī)?；旌险麛?shù)非線(xiàn)性規(guī)劃問(wèn)題,窮舉搜索方法雖然能夠得到最優(yōu)解,但是不實(shí)際和不可行,因此本文使用改進(jìn)粒子群算法解決該問(wèn)題。

2 基于改進(jìn)粒子群算法的移動(dòng)邊緣計(jì)算卸載方法

粒子群優(yōu)化算法(Particle Swarm Optimization Algorithm,PSO)是一種廣泛使用的啟發(fā)式優(yōu)化算法[7],不需目標(biāo)函數(shù)的連續(xù)性和凸性,但容易出現(xiàn)早熟,導(dǎo)致局部收斂。模擬退火算法(Simulated Annealing Algorithm,SA)收斂效率較低,但其收斂到全局最優(yōu)解的概率為1[8]。結(jié)合2種算法的優(yōu)點(diǎn),可以提高算法的靈活性和粒子多樣性,獲得較強(qiáng)的全局優(yōu)化能力,從而提高參數(shù)優(yōu)化的精度。因此,本文將SA與PSO結(jié)合,使用改進(jìn)粒子群算法(Improve Particle Swarm Optimization Algorithm,IPSO)的方法解決問(wèn)題P1。

2.1 編碼和初始化

本文采用整數(shù)編碼,粒子收斂的位置表示最終的卸載決定。用戶(hù)任務(wù)可以在本地、N個(gè)MEC服務(wù)器、1個(gè)云服務(wù)器的場(chǎng)景中執(zhí)行,因此位置范圍定義為N={0,1,…,N,N+1},其中0表示在本地計(jì)算,1～N表示在邊緣服務(wù)器1～N中計(jì)算,N+1為云計(jì)算。PSO在每次迭代中,使用式(22)和式(23)更新粒子的位置和速度,但每個(gè)粒子的位置值由式(20)轉(zhuǎn)換為離散數(shù)值。

(20)

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

在PSO中每個(gè)粒子都通過(guò)一個(gè)適應(yīng)度函數(shù)來(lái)評(píng)估,本文適應(yīng)度值由式(21)計(jì)算,表示為

(21)

2.3 粒子更新策略

(22)

(23)

式中:k表示迭代次數(shù);c1和c2為學(xué)習(xí)因子;ω為速度慣性權(quán)重;rand()表示在[0,1]之間的均勻分布的隨機(jī)數(shù)。

為了更好的平衡算法的全局搜索能力和局部改進(jìn)能力,慣性權(quán)重ω應(yīng)合理設(shè)置,一些研究者提出了改進(jìn)的慣性權(quán)值的PSO算法[9-10]。但是,這些方法并沒(méi)有充分限制動(dòng)態(tài)求解過(guò)程中慣性權(quán)值的取值范圍,并且與每一代粒子的適應(yīng)度的相關(guān)性還有改進(jìn)的空間。本文采用基于適應(yīng)度值和迭代次數(shù)的慣性權(quán)重策略。

(24)

(25)

式中:當(dāng)f(Xi)≥favg時(shí),如果ω>0.99,則ω=0.99。當(dāng)f(Xi)

IPSO算法優(yōu)化卸載決策的主要過(guò)程如下:

步驟1:設(shè)置PSO算法的迭代次數(shù)kmax、種群大小Num、加速度因子c1和c2,設(shè)置SA算法的初始溫度T、退火系數(shù)h和馬爾可夫鏈長(zhǎng)度s,初始化每個(gè)粒子的速度和位置。

步驟2:選擇式(21)作為適應(yīng)度函數(shù),計(jì)算所有粒子的適應(yīng)度值,確定初始最優(yōu)種群位置。

步驟3:根據(jù)式(25)更新慣性權(quán)值ω,式(22)和(23)更新速度和位置,根據(jù)適應(yīng)度函數(shù)找到新的最優(yōu)個(gè)體位置pbesti和最優(yōu)群體位置gbesti。如果PSO算法收斂,找到當(dāng)前最優(yōu)位置pbesti,則繼續(xù)執(zhí)行步驟4,否則重復(fù)步驟3,直到算法收斂。

步驟4:引入SA算法,將步驟3中得到的當(dāng)前最優(yōu)位置pbesti作為SA算法的初始位置z,即z(t)=pbesti(t),并在其鄰域內(nèi)隨機(jī)選取一個(gè)新的位置z′。分別計(jì)算2個(gè)適應(yīng)度J(z)和J(z′),并用Metropolis準(zhǔn)則來(lái)判斷是否接受替換新的最優(yōu)種群位置。

更新溫度T(t+1)=hT(t),迭代至s后,繼續(xù)執(zhí)行步驟5。

步驟5:如果SA算法搜索的最終位置z的適應(yīng)度小于PSO算法搜索的當(dāng)前最優(yōu)種群位置Pg(t),則z作為PSO算法新的最優(yōu)種群位置。

步驟6:判斷適應(yīng)度值是否滿(mǎn)足條件,如果滿(mǎn)足,輸出種群的最優(yōu)位置;否則,返回步驟3,直到PSO算法完成kmax次迭代。

3 試驗(yàn)結(jié)果與分析

3.1 試驗(yàn)環(huán)境配置

為了評(píng)估提出算法的有效性,本文試驗(yàn)使用MATLAB R2022b。仿真環(huán)境為30個(gè)用戶(hù)和5個(gè)MEC服務(wù)器在1 000×1 000 m2的區(qū)域中隨機(jī)分布,其中云服務(wù)器位于中心。其他仿真參數(shù)如表1～2所示。

表1 IPSO算法參數(shù)設(shè)置

表2 仿真環(huán)境參數(shù)設(shè)置

3.2 對(duì)比方法

將本文提出的基于IPSO的邊云協(xié)同算法與以下算法性能進(jìn)行對(duì)比:

(1) 本地計(jì)算(Local Offloading,LO):計(jì)算任務(wù)由本地設(shè)備計(jì)算,不進(jìn)行任務(wù)卸載。

(2) 邊緣卸載(Edge Offloading,EO):所有任務(wù)由邊緣服務(wù)器完成。

(3) 隨機(jī)卸載:(Random Offloading,RO):所有任務(wù)進(jìn)行隨機(jī)卸載。

3.3 試驗(yàn)結(jié)果及分析

首先評(píng)估提出的算法的收斂性,然后驗(yàn)證提出的算法與其他基線(xiàn)算法的性能比較。

3.3.1 算法收斂性

圖2為30個(gè)移動(dòng)用戶(hù)數(shù)下的算法收斂性。從收斂曲線(xiàn)可知,PSO需要約50次迭代才能收斂,IPSO只需20次左右迭代即可收斂,能夠快速求解到最小系統(tǒng)成本,比PSO降低了8.7%的系統(tǒng)成本,這表明IPSO具有良好的收斂性,能夠克服PSO算法容易陷入局部極值點(diǎn)的缺點(diǎn)。

圖2 算法收斂性

3.3.2 移動(dòng)用戶(hù)數(shù)的影響

對(duì)IPSO算法及對(duì)比算法在不同移動(dòng)用戶(hù)數(shù)量下的性能進(jìn)行了評(píng)估,如圖3所示。在此試驗(yàn)中所有用戶(hù)卸載同一個(gè)任務(wù),即su=700 kB。結(jié)果表明,相對(duì)于其他方案,IPSO算法一直是最優(yōu)策略,實(shí)現(xiàn)了最低的總計(jì)算成本。這是因?yàn)楸疚乃岢龅乃惴ㄊ且环N邊云協(xié)同卸載方案,用戶(hù)可以在本地、邊緣服務(wù)器和云服務(wù)器處理任務(wù),可以充分利用計(jì)算能力較強(qiáng)的邊緣節(jié)點(diǎn)的計(jì)算資源,同時(shí)分配更多的云計(jì)算資源來(lái)輔助計(jì)算能力較弱的邊緣節(jié)點(diǎn),使得卸載決策更合理的分配任務(wù),減小任務(wù)執(zhí)行成本。當(dāng)用戶(hù)數(shù)為30時(shí),與EO、RO、LO算法相比,IPSO算法的系統(tǒng)總成本平均分別降低了24.1%、53.9%、72.3%。

圖3 用戶(hù)數(shù)量對(duì)系統(tǒng)成本的影響

3.3.3 任務(wù)數(shù)據(jù)大小的影響

將每個(gè)任務(wù)的數(shù)據(jù)大小從500 kB到2 500 kB遞增,給出的不同算法下任務(wù)數(shù)據(jù)大小對(duì)系統(tǒng)總成本的影響如圖4所示。結(jié)果表明,增加數(shù)據(jù)大小不會(huì)改變LO算法總計(jì)算成本。其余算法成本隨著任務(wù)數(shù)據(jù)大小的增加而增加,這是因?yàn)橄到y(tǒng)中通信資源是固定的,輸入數(shù)據(jù)量的增加會(huì)直接影響到卸載任務(wù)的上行傳輸延遲和能耗。這說(shuō)明,計(jì)算少量數(shù)據(jù)的卸載任務(wù)可以獲得更好的結(jié)果。

圖4 任務(wù)數(shù)據(jù)大小對(duì)系統(tǒng)成本的影響

3.3.4 用戶(hù)偏好的影響

用戶(hù)時(shí)延偏好λ從0.1變化到0.9對(duì)IPSO的任務(wù)平均時(shí)延和能耗的影響如圖5所示。結(jié)果表明,隨著λ的增加,平均時(shí)間消耗降低,能量消耗增加,表明IPSO能夠根據(jù)用戶(hù)需求進(jìn)行動(dòng)態(tài)調(diào)整卸載決策,求解最小的系統(tǒng)成本。

圖5 用戶(hù)偏好的影響

4 結(jié)語(yǔ)

為了充分利用云服務(wù)器、用戶(hù)移動(dòng)設(shè)備和MEC服務(wù)器的異構(gòu)計(jì)算能力,本文提出了一種基于改進(jìn)粒子群算法的邊云協(xié)同任務(wù)卸載策略。該策略實(shí)現(xiàn)了網(wǎng)絡(luò)資源的協(xié)同和管理,能夠滿(mǎn)足在多種約束下處理用戶(hù)任務(wù)的系統(tǒng)成本最小化的需求。試驗(yàn)結(jié)果表明,該算法有效且能夠在有限迭代次數(shù)內(nèi)收斂。與基準(zhǔn)算法相比,本文算法具有最低的系統(tǒng)成本、能量消耗和延遲,并且隨著任務(wù)數(shù)量的增加,優(yōu)勢(shì)更加明顯。然而,本文研究的MEC場(chǎng)景為準(zhǔn)靜態(tài)系統(tǒng),在未來(lái)的研究中,將考慮到用戶(hù)移動(dòng)性、環(huán)境參數(shù)的時(shí)變性等問(wèn)題,為動(dòng)態(tài)多變的場(chǎng)景提供更好的卸載策略。