徐永杰,李 暉,2,蘭 松,徐文校,于心遠(yuǎn),楊山山

(1.南京信息工程大學(xué) 電子與信息工程學(xué)院,南京 210044;2.無錫學(xué)院 電子信息工程學(xué)院,江蘇 無錫 214105)

0 引 言

隨著物聯(lián)網(wǎng)的快速發(fā)展,網(wǎng)絡(luò)邊緣設(shè)備已經(jīng)產(chǎn)生了海量的數(shù)據(jù),給通信帶寬資源帶來了巨大的挑戰(zhàn)。與此同時,應(yīng)用對數(shù)據(jù)速率和服務(wù)質(zhì)量的要求也越來越高,傳統(tǒng)的云計算模型已經(jīng)無法有效應(yīng)對,因此移動邊緣計算(Mobile Edge Computing,MEC)應(yīng)運(yùn)而生[1]。MEC并不是取代云計算,而是云計算的補(bǔ)充和拓展。MEC更加靠近用戶層,不僅可以向用戶提供任務(wù)計算和內(nèi)容緩存等服務(wù),還可以減少終端的能耗和降低用戶與云服務(wù)器之間頻繁地交互,減輕了云層的壓力[2]。其中,計算卸載技術(shù)是MEC中最為關(guān)鍵的技術(shù),主要包括卸載策略和資源分配兩個方面[3]。一般來說,計算卸載的優(yōu)化目標(biāo)有三種,分別是以時延為優(yōu)化目標(biāo)、以能耗為優(yōu)化目標(biāo)和綜合時延和能耗的方式作為優(yōu)化目標(biāo)。Li等人[4]在單終端單邊緣服務(wù)器的排隊任務(wù)場景下,使用了梯度策略算法,與貪心算法和窮舉法相比較,可以通過更短的決策時間獲得高質(zhì)量的卸載方案,仿真結(jié)果表明梯度策略算法減少了50%的時間開銷。Liu等人[5]將給定順序的有向無環(huán)的任務(wù)序列切割成基本單元,再根據(jù)不同的場景將基本單元分解成子問題來解決,結(jié)果表明該方法與比較算法相比,實現(xiàn)了最少的消耗時間。Ketykó等人[6]將多用戶卸載問題建模為NP-hard 問題,并采用背包模型去優(yōu)化整個資源分配和負(fù)載均衡的問題。Wang等人[7]提出了干擾管理的方案,在最小化干擾的條件下進(jìn)行通信資源分配、計算資源分配的方案。Ndikumana等人[8]為使得資源利用率最大化,將MEC服務(wù)器組合起來使用,提出了一種協(xié)作式緩存的卸載策略。Xu等人[9]提出了一種非靜態(tài)的卸載策略,使用了深度學(xué)習(xí)的方法來對有限的資源進(jìn)行分配。Mehrabi等人提出了一個三節(jié)點(diǎn)的MEC架構(gòu),在滿足任務(wù)完成期限和任務(wù)依賴性的要求下最小化系統(tǒng)能耗,結(jié)果表明該架構(gòu)優(yōu)于比較的卸載方式[10]。Guo等人[11-12]建立了兩個計算效率髙的模型,分別具有可忽略和不可忽略的邊緣服務(wù)器執(zhí)行時間以封閉形式獲得了最優(yōu)解,利用Johnson算法來獲得低復(fù)雜度的次優(yōu)解決方案。Zhang等人[13]基于人工魚群算法,將前傳網(wǎng)絡(luò)和回傳網(wǎng)絡(luò)的鏈路狀態(tài)考慮在內(nèi),與對比算法相比節(jié)約了30%的能耗。鮮永菊等人[14]提出了一種主從MEC的系統(tǒng)架構(gòu),采用了貪婪選擇算法完成計算資源的合理分配,實驗結(jié)果表明該卸載策略減少了系統(tǒng)總代價。Huang等人[15]提出了一種基于深度強(qiáng)化學(xué)習(xí)的在線卸載框架,可以有效地減少計算復(fù)雜度,使得CPU計算時延小于0.1 s。

以上篇幅針對時延和能耗進(jìn)行了一定程度的優(yōu)化,但大多只考慮了單邊緣或者邊云協(xié)同的方式。本文采用了多邊緣的網(wǎng)絡(luò)架構(gòu),通過免疫粒子群算法對任務(wù)的卸載方式進(jìn)行求解,得到最佳的卸載策略,使得能耗和時延的加權(quán)求和最小化。

1 系統(tǒng)模型

1.1 網(wǎng)絡(luò)架構(gòu)

經(jīng)典的邊緣計算系統(tǒng)架構(gòu)是由用戶層、邊緣層、云層組成的。用戶層是由各種終端物聯(lián)網(wǎng)設(shè)備構(gòu)成;邊緣層是三層架構(gòu)的核心,一般由蜂窩塔、路側(cè)單元[16]等構(gòu)成,具有比用戶層更加強(qiáng)大的計算和存儲能力;云層可以處理和存儲大量的數(shù)據(jù)。用戶終端產(chǎn)生的任務(wù)可以選擇在本地計算、卸載到邊緣服務(wù)器計算或者卸載到云端處理。傳統(tǒng)的三層架構(gòu)共同協(xié)作來對終端的任務(wù)進(jìn)行卸載處理,再將處理后的結(jié)果數(shù)據(jù)返回,通過合理的卸載策略可以有效地減少系統(tǒng)的能耗和任務(wù)處理的延時。

盡管上述的系統(tǒng)架構(gòu)已經(jīng)取得了顯著的效果,但是現(xiàn)有的卸載方案往往忽略了異地閑置邊緣服務(wù)器的作用,造成了資源的不充分利用。因此,本文提出了一種多邊緣協(xié)作的“物-邊-云”卸載系統(tǒng),根據(jù)產(chǎn)生任務(wù)的終端與邊緣服務(wù)器物理距離的遠(yuǎn)近,在原有系統(tǒng)的基礎(chǔ)上,將邊緣服務(wù)器分為本地邊緣服務(wù)器和異地邊緣服務(wù)器。在此系統(tǒng)上,任務(wù)除了可以選擇卸載到本地邊緣服務(wù)器和云端上,還可以卸載到異地邊緣服務(wù)器上。因為異地邊緣服務(wù)器相對于云端來說距離用戶終端更近,這樣就大大地減少了傳輸延遲,也對閑置的計算資源進(jìn)行了充分地利用。具體的通信場景如圖1所示。

1.2 卸載計算模型

以往的有些研究不考慮任務(wù)間的依賴關(guān)系,但是實際應(yīng)用中某些任務(wù)在執(zhí)行時需要有前置任務(wù),因此本文研究的任務(wù)卸載時要考慮任務(wù)之間的優(yōu)先關(guān)系。圖2描述了終端產(chǎn)生的任務(wù)之間的關(guān)系。圖中的單位圓代表了一個任務(wù),任務(wù)之間的約束關(guān)系用箭頭來表示,箭頭末端的任務(wù)是前置任務(wù),如任務(wù)1指向任務(wù)2,則表示任務(wù)1是任務(wù)2的前置任務(wù)。必須把前置任務(wù)1執(zhí)行了才能繼續(xù)執(zhí)行新任務(wù)2。

圖2 任務(wù)關(guān)系

1.2.1 本地計算

當(dāng)任務(wù)被選擇在本地進(jìn)行計算時,則造成的時延主要為計算延時,不存在傳輸延時;能量消耗則為計算任務(wù)時處理器的能量消耗。

(1)

(2)

1.2.2 卸載到本地服務(wù)器計算

當(dāng)任務(wù)卸載到本地服務(wù)器計算時,造成的時延主要是由傳輸延時、卸載到本地服務(wù)器的計算延時和將數(shù)據(jù)返回的延時造成的。能耗主要是上傳和下載數(shù)據(jù)產(chǎn)生的和服務(wù)器處理任務(wù)時產(chǎn)生的。

由香農(nóng)公式可得,本地設(shè)備和服務(wù)器無線傳輸速率為

(3)

式中:B1是本地設(shè)備與本地服務(wù)器的通信帶寬;ρ1和ρ2為路徑的衰落因子和損耗因子;ρ0是噪聲密度;d1是本地設(shè)備與本地邊緣服務(wù)器的最近距離。

(4)

(5)

式中:pe為本地服務(wù)器的計算功率。

1.2.3 卸載到異地服務(wù)器計算

當(dāng)把任務(wù)從本地服務(wù)器卸載到異地服務(wù)器時,延遲主要包括傳輸延時、計算延遲和返回延時,能耗包括計算能耗、上傳能耗和下載能耗。

由香農(nóng)公式可得,本地設(shè)備和服務(wù)器無線傳輸速率為

(6)

式中:d2為兩個服務(wù)器之間的直線距離。任務(wù)卸載到異地服務(wù)器的時延為

(7)

任務(wù)卸載到異地服務(wù)器的能耗為

(8)

1.2.4 卸載到云層計算

當(dāng)把任務(wù)卸載到云層時,延遲主要包括傳輸延時、計算延遲和返回延時,能耗包括計算能耗、上傳能耗和下載能耗。

由香農(nóng)公式可得,本地設(shè)備和云服務(wù)器無線傳輸速率為

(9)

式中:B3為本地設(shè)備與云端的通信帶寬;d3為本地設(shè)備與云端的距離。任務(wù)卸載到云端的時延為

(10)

任務(wù)卸載到云端的能耗為

(11)

1.2.5 合作計算成本

當(dāng)計算任務(wù)所需要的計算資源較大時,若將任務(wù)選擇在本地執(zhí)行,則會使得終端能耗增大;若將任務(wù)選擇卸載到云層執(zhí)行,由于云層距離用戶層較遠(yuǎn),則會導(dǎo)致任務(wù)完成的時延較大,因此本文將協(xié)作計算引入到卸載計算的模型中。為了鼓勵更多的邊緣服務(wù)器可以將計算資源共享,則終端用戶應(yīng)該付出一定的成本來吸引服務(wù)器幫助用戶完成任務(wù)。對于數(shù)據(jù)量越大的任務(wù)需要更多的傳輸時間,所以合作計算成本coi與任務(wù)數(shù)據(jù)量成正比。因此合作計算成本coi的計算范式為

coi=ktdi。

(12)

式中:k為比例系數(shù),表示用戶請求服務(wù)器協(xié)作完成任務(wù)的單價。

1.2.6 目標(biāo)函數(shù)定義

綜上所述,任務(wù)卸載的總時延和總能耗可以表示成

(13)

(14)

定義系統(tǒng)總代價為目標(biāo)函數(shù),其表示為時延和能耗的加權(quán)和?？紤]了合作成本,因此目標(biāo)函數(shù)便遵循一定的約束,所以完整的目標(biāo)函數(shù)如下:

g=wtTsum+(1-wt)Esum,

(15)

(16)

式(15)是本文的優(yōu)化目標(biāo),式(16)表示任務(wù)卸載到邊緣計算服務(wù)器上用戶付出的成本約束。若計算任務(wù)對時延比較敏感,則可適當(dāng)?shù)貙r間權(quán)重wt調(diào)大;若希望能耗減少,則可將wt調(diào)小。

2 算法設(shè)計

粒子群(Particle Swarm Optimization,PSO)算法在解決目標(biāo)優(yōu)化問題時一直以來都頗受學(xué)者們的青睞,但傳統(tǒng)的粒子群算法在實際工程優(yōu)化中容易出現(xiàn)早熟收斂和陷入局部最優(yōu)。為克服這些缺點(diǎn),本文將生物學(xué)中免疫機(jī)制引入到粒子群算法中,基于免疫粒子群算法來完成對目標(biāo)函數(shù)的優(yōu)化。

2.1 傳統(tǒng)的粒子群算法

粒子是優(yōu)化問題的候選解,粒子有兩個參數(shù),分別是速度和位置。每個粒子都有其適應(yīng)度函數(shù),一般是目標(biāo)優(yōu)化函數(shù),其用于評價粒子的質(zhì)量。在一次次的迭代中,粒子通過個體極值pbest和全局極值gbest來更新自己,直到達(dá)到滿足條件。以下兩式描述了粒子速度和位置更新:

(17)

(18)

式中:w代表慣性因子,表示粒子對自身運(yùn)動狀態(tài)的信任;c1和c2代表學(xué)習(xí)因子;r1和r2是兩個相互獨(dú)立的取值都在[0,1]的隨機(jī)數(shù)[17]。

2.2 編碼方式

本文有4種卸載方式,分別用1,2,3,4代表本地卸載、本地服務(wù)器卸載、異地服務(wù)器卸載和云層卸載。因為有N個任務(wù)且需要體現(xiàn)任務(wù)之間的優(yōu)先級,所以本文采用兩位浮點(diǎn)數(shù)編碼方式。其中,整數(shù)部分表示任務(wù)編號,小數(shù)第一位表示卸載方式,小數(shù)第二位表示任務(wù)的優(yōu)先級(數(shù)值越大,任務(wù)越優(yōu)先被執(zhí)行)。

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

由系統(tǒng)模型可知,優(yōu)化目標(biāo)是使得系統(tǒng)總代價最小,因此本文將目標(biāo)函數(shù)取反,作為適應(yīng)度函數(shù)。適應(yīng)度函數(shù)越大,則系統(tǒng)總代價越小,卸載方案越有效。

fitness=-[wTsum+(1-w)Esum] 。

(19)

2.4 免疫粒子群算法(Immune Particle Optimization,IPSO)

本文在粒子群算法的基礎(chǔ)上,引入了人工免疫算法,特別是結(jié)合了免疫系統(tǒng)中的免疫記憶機(jī)制和濃度調(diào)節(jié)機(jī)制。免疫記憶機(jī)制指的是在免疫系統(tǒng)中分泌能夠與抗原結(jié)合的抗體的漿細(xì)胞作為記憶細(xì)胞儲存下來,當(dāng)機(jī)體再次遇到相同抗原入侵時,記憶細(xì)胞就會分化為漿細(xì)胞,產(chǎn)生大量抗體。本文將這種思想引入了粒子群算法中,將每次迭代產(chǎn)生的適應(yīng)度較高的粒子作為記憶細(xì)胞保存下來。當(dāng)遇到適應(yīng)度較低的粒子時,可以將記憶細(xì)胞代替。濃度調(diào)節(jié)機(jī)制是指與濃度低的抗體會被促進(jìn),濃度高會被抑制。在算法中應(yīng)用則保證了粒子的多樣性,有利于避免陷入局部最優(yōu)解。

與傳統(tǒng)的粒子群算法不同,評價粒子(抗體)的質(zhì)量是由親和力決定的,其由式(20)計算:

p(xi)=αf(xi)+(1-α)d(xi) 。

(20)

式中:α是比例因子;p(xi)代表親和度值;f(xi)代表適應(yīng)度值;d(xi)代表濃度值。為了避免陷入局部最優(yōu)解,研究中應(yīng)該盡量地保證種群的多樣性,防止高親和度值的粒子大量存在,因此,引入了d(xi)濃度這一變量,計算方式如式(21)和式(22)所示:

(21)

(22)

式中:ρ(xi)代表相似度,若粒子的每個維度都相近時,則判斷為相似粒子;N代表解空間里所有的粒子數(shù)量。

本文將粒子種群根據(jù)粒子最大濃度分為兩個種群a和b。種群a是親和度高的粒子,讓這些粒子按照傳統(tǒng)的粒子群方法迭代;種群b則是親和度低的粒子,將種群b的粒子進(jìn)行疫苗接種,讓記憶細(xì)胞中親和度高的粒子增值代替它們。這里種群a和b粒子數(shù)量由下面兩式計算得出:

N(a)=dmaxN,

(23)

N(b)=N-N(a) 。

(24)

式中:N(a)和N(b)分別代表種群a和b的粒子數(shù)量;dmax式粒子的最大濃度。控制兩個種群的粒子數(shù)量,有利于保持粒子的多樣性,使得種群朝著好的方向進(jìn)化。

2.5 算法流程

表1給出了免疫粒子群算法與卸載問題的對應(yīng)關(guān)系。在使用免疫粒子群算法求解問題時,把目標(biāo)優(yōu)化問題抽象為抗原,把問題的候選解抽象為抗體(粒子),通過求解親和度在解空間中進(jìn)行啟發(fā)式搜索來尋找最優(yōu)抗體,解碼最優(yōu)抗體輸出目標(biāo)問題的最優(yōu)解,使用抗體(粒子)X={x1,x2,…,xi,…,xN}表示任務(wù)調(diào)度的結(jié)果,xi=1時表示任務(wù)在本地執(zhí)行,xi=2時任務(wù)在本地服務(wù)器執(zhí)行,xi=3時任務(wù)在異地服務(wù)器執(zhí)行,xi=4在云端執(zhí)行。

表1 算法參數(shù)與卸載策略參數(shù)的對應(yīng)關(guān)系

免疫粒子群算法流程如下:

輸入:計算任務(wù)集的各個參數(shù)

輸出:計算任務(wù)卸載策略

1 初始化種群數(shù)量為N的粒子群包括位置和速度。

2 根據(jù)式(20)計算每一個粒子的親和度,并將個體極值的粒子視為記憶細(xì)胞作為疫苗。

3 根據(jù)粒子親和度由大到小排序。

4 根據(jù)粒子最大濃度分為兩個種群a和b,種群a按照式(17)和式(18)進(jìn)行迭代,種群b進(jìn)行疫苗接種。

5 種群a和種群b合并為種群c。

6 種群根據(jù)粒子群算法的速度和位置公式更新。

7 判斷群體極值是否滿足循環(huán)退出條件,若滿足則輸出結(jié)果,否則跳轉(zhuǎn)到第2步。

2.6 算法復(fù)雜度分析

假設(shè)IPSO算法的種群數(shù)量為N,迭代次數(shù)為K,先對單次迭代的操作進(jìn)行時間復(fù)雜度分析,然后擴(kuò)展到整個過程。初始化種群并計算每個抗體的親和度,其時間復(fù)雜度為O(N);將抗體親和度值從大到小按選擇排序的方式排序,其時間復(fù)雜度為O(N2);每個抗體的速度和位置按式(17)和式(18)更新,其時間復(fù)雜度也是O(N);其余操作均為常數(shù)時間復(fù)雜度。綜上所述,IPSO算法的復(fù)雜度為O(KN2)。

3 仿真與分析

本節(jié)通過Java語言仿真平臺來對本文提出的卸載策略進(jìn)行驗證,并與本地卸載策略、基于免疫算法(Immune Algorithm,IA)和基于傳統(tǒng)的粒子群算法策略進(jìn)行了對比。

本地卸載(LOCAL):終端產(chǎn)生的任務(wù)都集中在本地執(zhí)行。

免疫算法[17](Immune Algorithm,IA):基于免疫優(yōu)化算法卸載策略。

PSO[18](Particle Swarm Optimization)算法:基于傳統(tǒng)的粒子群算法卸載策略。

IPSO(Immune Particle Optimization)算法:基于免疫粒子群算法卸載策略。

與真實場景不同的是,沒有考慮服務(wù)器計算資源和通信資源的有限性。在文獻(xiàn)[17]的基礎(chǔ)上設(shè)定任務(wù)傳輸?shù)臄?shù)據(jù)量在[1,600]KB隨機(jī)生成,結(jié)果返回的數(shù)據(jù)量在區(qū)間[0.1,100]KB上隨機(jī)生成。算法的基本參數(shù)設(shè)定基于文獻(xiàn)[19-21]中提供的參數(shù)示例,并且本文根據(jù)仿真環(huán)境進(jìn)行了一定的調(diào)整。算法和任務(wù)卸載相關(guān)參數(shù)在表2和表3中給出。

表2 算法相關(guān)參數(shù)

表3 任務(wù)卸載相關(guān)參數(shù)

3.1 用戶設(shè)備數(shù)量對系統(tǒng)總代價的影響

圖3描述了用戶設(shè)備數(shù)量的增多對于系統(tǒng)總代價的影響。圖3中,橫坐標(biāo)代表用戶數(shù)量,單位為用戶個數(shù);縱坐標(biāo)表示的是系統(tǒng)總代價其值代表時延和能耗的加權(quán)和,是一個無量綱的物理量,圖4～6的縱坐標(biāo)也是如此。本文在設(shè)置仿真環(huán)境時設(shè)備服務(wù)器待機(jī)狀態(tài)下存在少量的能量消耗,所以曲線并不歸于原點(diǎn)。用戶產(chǎn)生的任務(wù)數(shù)量的增加會使得在任務(wù)卸載過程中系統(tǒng)消耗的能量和時延都會增加,但從圖中可以看出,本文使用的IPSO算法相比本地卸載策略、IA算法和傳統(tǒng)的PSO算法來說,系統(tǒng)的總代價是最小的,相比較其他三種策略分別提升了66.7%,54%和45.5%,證明了該策略的有效性。

圖3 用戶數(shù)量的影響

圖4 任務(wù)計算量的影響

3.2 任務(wù)計算量對于系統(tǒng)總代價的影響

圖4描述了任務(wù)計算量的增大對于系統(tǒng)總代價的影響。任務(wù)數(shù)量取值為50,隨著任務(wù)計算量的增大,系統(tǒng)總代價也在增大,但本文提出的IPSO算法總代價始終是最小的。在任務(wù)計算量低于60 GHz時,PSO算法的系統(tǒng)總代價與IPSO算法和IA算法相差不大,但大于60 GHz后,IPSO算法就明顯優(yōu)于PSO算法和IA算法。這是因為PSO算法容易收斂于局部最優(yōu),并且在以后的搜索過程中卸載效果不理想。

3.3 異地服務(wù)器數(shù)量對于系統(tǒng)總代價的影響

為了探究異地邊緣服務(wù)器的數(shù)量對于系統(tǒng)總代價,本次實驗設(shè)置本地服務(wù)器的數(shù)量為1臺。從圖5可以看出,在邊緣服務(wù)器為5臺時,系統(tǒng)總代價最低。與此同時,當(dāng)服務(wù)器大于5臺時,隨著異地服務(wù)器數(shù)量的增加,系統(tǒng)總代價卻略微增加。這是因為較多的異地邊緣節(jié)點(diǎn)會使得計算任務(wù)卸載較為分散,系統(tǒng)的能耗和傳輸延時成本會增加,所以曲線會出現(xiàn)少許的波動,而本地卸載幾乎不受服務(wù)器數(shù)量增多的影響。

圖5 服務(wù)器數(shù)量的影響

3.4 用戶最大合作成本的影響

圖6描述了用戶最大合作成本對于系統(tǒng)總代價的影響,本次實驗任務(wù)的比例系數(shù)K取值為0.1。由式(16)可知,用戶請求邊緣服務(wù)器協(xié)作完成任務(wù)時需要付出的成本與任務(wù)數(shù)據(jù)量相關(guān),任務(wù)數(shù)據(jù)量在[1,600]KB隨機(jī)生成,因此設(shè)置橫坐標(biāo)用戶所能承受的最大成本在區(qū)間[10,60]遞增。圖中橫坐標(biāo)表示用戶付出的最大成本,與任務(wù)的數(shù)據(jù)量有關(guān),但它是一個無量綱的物理量,因為它的物理含義表示的是用戶購買服務(wù)器資源所付出的代價。由圖可知,隨著用戶能承受的最大成本的增加,系統(tǒng)總代價在不斷地減少。這是因為用戶可以把更多的任務(wù)卸載到邊緣服務(wù)器執(zhí)行,減少了計算時延和能耗。而本地卸載任務(wù)基本保持不變是因為任務(wù)都在本地處理,不需要請求邊緣服務(wù)器合作計算,系統(tǒng)總代價在本地執(zhí)行任務(wù)幾乎不受到影響。

圖6 用戶最大成本的影響

4 結(jié)束語

本文基于用戶設(shè)備、本地邊緣設(shè)備、異地邊緣設(shè)備和云服務(wù)器協(xié)作的任務(wù)計算卸載模式,將時延和能耗建模成為系統(tǒng)總代價,采用免疫粒子群優(yōu)化算法。仿真結(jié)果表明,該任務(wù)卸載策略可以提高任務(wù)的執(zhí)行效率,有效地減少系統(tǒng)地總代價。但是本文沒有考慮通信鏈路的干擾,也沒有考慮邊緣服務(wù)器的通信和計算資源的有限性。在后續(xù)的工作中,將會考慮以上不足,采用深度強(qiáng)化學(xué)習(xí)的方式繼續(xù)研究任務(wù)卸載策略。