基于binAD算法的邊緣計(jì)算卸載決策

王 澤，郭榮佐

(四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院，四川 成都 610101)

0 引 言

隨著物聯(lián)網(wǎng)的出現(xiàn)和移動(dòng)終端設(shè)備的普及，諸多物聯(lián)網(wǎng)應(yīng)用正在影響和改變著生活，例如圖像識(shí)別、車聯(lián)網(wǎng)、虛擬現(xiàn)實(shí)、智能家居等[1-4]。計(jì)算這些應(yīng)用程序內(nèi)存占用率高、能耗高、計(jì)算資源需求大，且對(duì)及時(shí)性要求嚴(yán)格。盡管目前移動(dòng)終端設(shè)備的處理器、電池容量和其它軟硬件持續(xù)更新?lián)Q代，但是對(duì)于單個(gè)設(shè)備來(lái)說(shuō)，物理設(shè)計(jì)仍受限，無(wú)法處理計(jì)算密集型和時(shí)間敏感型應(yīng)用程序。

計(jì)算卸載技術(shù)[5]可以解決上述問(wèn)題，將計(jì)算密集型或時(shí)間敏感型應(yīng)用程序任務(wù)卸載到其它服務(wù)器端執(zhí)行。以移動(dòng)云計(jì)算[6](MCC)為例，用戶端的移動(dòng)終端設(shè)備將計(jì)算任務(wù)卸載到云服務(wù)器上執(zhí)行計(jì)算，以此可以解決移動(dòng)終端設(shè)備算力、電池、內(nèi)存不足等問(wèn)題。目前大量的移動(dòng)終端設(shè)備、工業(yè)物聯(lián)網(wǎng)設(shè)備都需要云計(jì)算服務(wù)，而云計(jì)算存在傳輸時(shí)延大、帶寬不足、數(shù)據(jù)隱私泄漏等缺點(diǎn)。邊緣計(jì)算[7](EC)在靠近移動(dòng)終端設(shè)備的無(wú)線接入網(wǎng)絡(luò)邊緣部署分布式計(jì)算和緩存資源。與MCC相比，EC的計(jì)算能力較小，但是EC具有低延遲、高寬帶、訪問(wèn)距離短、地理分布靈活以及數(shù)據(jù)隱私保護(hù)等優(yōu)點(diǎn)。

在實(shí)際通信場(chǎng)景中，不同的卸載任務(wù)對(duì)能耗和時(shí)延的要求各不相同，例如，AR、VR等應(yīng)用任務(wù)對(duì)時(shí)延有嚴(yán)格要求；移動(dòng)終端設(shè)備電量低時(shí)應(yīng)對(duì)能耗問(wèn)題更加關(guān)注。因此，如何平衡計(jì)算卸載中的能耗和時(shí)延是一個(gè)關(guān)鍵問(wèn)題。

由于邊緣服務(wù)器端通常電源充足，故在本文中主要對(duì)電量、內(nèi)存、計(jì)算資源不足的移動(dòng)終端設(shè)備進(jìn)行研究。本文主要研究方向是通過(guò)優(yōu)化算法尋找到一個(gè)最優(yōu)任務(wù)卸載決策方案，使得任務(wù)卸載過(guò)程中，移動(dòng)智能設(shè)備系統(tǒng)效用最大化。

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

本文考慮搭建多用戶單邊緣服務(wù)器組成的網(wǎng)絡(luò)模型，邊緣計(jì)算卸載決策網(wǎng)絡(luò)模型如圖1所示，網(wǎng)絡(luò)模型主要分為3個(gè)部分：邊緣云、邊緣中間層、移動(dòng)終端設(shè)備。邊緣云中包括一個(gè)邊緣服務(wù)器和一個(gè)基站(base station，BS)，BS都有一定的存儲(chǔ)容量和任務(wù)處理能力，邊緣服務(wù)器部署在BS附近且位置固定，邊緣服務(wù)器處理從移動(dòng)終端設(shè)備傳輸來(lái)的計(jì)算密集型或時(shí)間敏感型任務(wù)。邊緣中間層是邊緣云與移動(dòng)終端設(shè)備的中間樞紐，其中包括一個(gè)邊緣網(wǎng)關(guān)和一個(gè)邊緣調(diào)度器，邊緣網(wǎng)關(guān)主要實(shí)現(xiàn)網(wǎng)絡(luò)接入、數(shù)據(jù)采集與轉(zhuǎn)發(fā)，邊緣調(diào)度器根據(jù)邊緣網(wǎng)關(guān)采集的數(shù)據(jù)得出卸載決策，并將卸載決策傳輸給邊緣網(wǎng)關(guān)。

圖1 邊緣計(jì)算卸載決策網(wǎng)絡(luò)模型

卸載決策過(guò)程簡(jiǎn)單描述為：邊緣網(wǎng)關(guān)收集移動(dòng)終端設(shè)備的待處理計(jì)算任務(wù)以及相關(guān)信息，然后將這些信息處理轉(zhuǎn)發(fā)給邊緣調(diào)度器。邊緣調(diào)度器接收到信息后對(duì)任務(wù)卸載做出決策，再將卸載決策回傳給邊緣網(wǎng)關(guān)，邊緣網(wǎng)關(guān)再傳輸給移動(dòng)終端設(shè)備和邊緣服務(wù)器。

假設(shè)當(dāng)前場(chǎng)景中有K個(gè)移動(dòng)終端設(shè)備，k∈{1，2，…，K}， 所有移動(dòng)終端設(shè)備表示為L(zhǎng)={L1，L2，…，LK} 集合，移動(dòng)終端設(shè)備在固定時(shí)間段內(nèi)只能產(chǎn)生一個(gè)計(jì)算任務(wù)，且計(jì)算任務(wù)不可分割。那么，在固定時(shí)間段內(nèi)會(huì)產(chǎn)生K個(gè)待處理的計(jì)算任務(wù)，定義移動(dòng)終端設(shè)備編號(hào)與計(jì)算任務(wù)編號(hào)相同。每個(gè)計(jì)算任務(wù)定義為一個(gè)四元組κk={Bk，Sk，Tmaxk，ak}，k∈{1，2，…，K}，Bk， B表示任務(wù)k數(shù)據(jù)量大??；Sk， MHz表示任務(wù)k需要的計(jì)算資源大小(機(jī)器周期數(shù))；Tmaxk， s表示時(shí)延容忍度。ak∈{0，1} 表示對(duì)計(jì)算任務(wù)k的卸載決策，當(dāng)ak=1表示計(jì)算任務(wù)k卸載到邊緣服務(wù)器進(jìn)行處理計(jì)算；ak=0表示計(jì)算任務(wù)k在本地的移動(dòng)終端設(shè)備執(zhí)行計(jì)算。本文中若任務(wù)k被選中卸載則全部卸載，即對(duì)每個(gè)計(jì)算任務(wù)作整體處理。為了便于分析，假設(shè)系統(tǒng)是一個(gè)準(zhǔn)靜態(tài)場(chǎng)景，即在一個(gè)卸載決策周期內(nèi)，移動(dòng)終端設(shè)備集合L保持不變。

2 計(jì)算模型

本節(jié)根據(jù)邊緣計(jì)算中的計(jì)算卸載過(guò)程對(duì)問(wèn)題進(jìn)行抽象建模，最后得到計(jì)算卸載中移動(dòng)終端設(shè)備的系統(tǒng)效用函數(shù)。

2.1 通信模型

在邊緣計(jì)算卸載決策網(wǎng)絡(luò)模型中，假設(shè)每個(gè)移動(dòng)終端設(shè)備的上行傳輸鏈路均采用正交頻分多址方法，因此，所有移動(dòng)終端設(shè)備在上傳卸載任務(wù)相關(guān)數(shù)據(jù)時(shí)，不會(huì)造成設(shè)備之間同頻干擾。

假設(shè)應(yīng)用于移動(dòng)終端設(shè)備Lk的上行鏈路帶寬為Wk， Hz，系統(tǒng)的上行鏈路總帶寬為Wtotal=∑Kk=1Wk。 若移動(dòng)終端設(shè)備以Pk的上傳功率傳輸數(shù)據(jù)，根據(jù)香農(nóng)公式可得計(jì)算任務(wù)k卸載時(shí)的上行傳輸速率

Rk=Wklog(1+PkHkσ2k)

(1)

式中：Hk表示Lk與BS之間的上行鏈路信道增益，σ2k表示Lk與BS之間上行鏈路噪聲功率。

2.2 計(jì)算模型

2.2.1 本地計(jì)算模型

當(dāng)ak=0， 計(jì)算任務(wù)k在本地執(zhí)行，若flock表示Lk提供給計(jì)算任務(wù)k的計(jì)算資源大小，則計(jì)算任務(wù)k在Lk完成計(jì)算的時(shí)延可表示為

tlock=Skflock

(2)

式中：Sk表示任務(wù)k需要的計(jì)算資源大小(機(jī)器周期數(shù))。

根據(jù)文獻(xiàn)[8]，計(jì)算任務(wù)k在Lk執(zhí)行計(jì)算的能耗可表示為

elock=γSk(flock)2

(3)

式中：能耗系數(shù)γ是與移動(dòng)終端設(shè)備CPU芯片結(jié)構(gòu)相關(guān)的常數(shù)，本文γ取值為10-17。若全部在Lk執(zhí)行計(jì)算的任務(wù)總能耗表示為Eloc， 總時(shí)延表示為Tloc， 則有

Eloc=∑Kk=1(1-ak)elock

(4)

Tloc=∑Kk=1(1-ak)tlock

(5)

2.2.2 卸載計(jì)算模型

假設(shè)邊緣服務(wù)器的計(jì)算資源足夠大，且能同時(shí)處理多個(gè)計(jì)算任務(wù)。邊緣服務(wù)器返回計(jì)算結(jié)果給移動(dòng)終端設(shè)備的數(shù)據(jù)量較小且傳輸速率大，故在本文中忽略回傳時(shí)延與能耗。

當(dāng)ak=1， 計(jì)算任務(wù)k卸載到邊緣服務(wù)器執(zhí)行。若toffk表示任務(wù)k卸載到邊緣服務(wù)器執(zhí)行的時(shí)延，則toffk可表示為

toffk=tupk+twaitk

(6)

式中：tupk表示Lk上傳計(jì)算任務(wù)k的傳輸時(shí)延；twaitk表示任務(wù)k卸載計(jì)算時(shí)，Lk等待時(shí)延。根據(jù)上傳時(shí)間=數(shù)據(jù)量/速率可得tupk， 即

tupk=BkRk=BkWklog(1+PkHkσ2k)

(7)

式中：Bk表示任務(wù)k數(shù)據(jù)量大??；Rk是根據(jù)式(1)計(jì)算得到的傳輸速率。

當(dāng)計(jì)算任務(wù)k卸載到邊緣服務(wù)器后，邊緣服務(wù)器為其分配的計(jì)算資源為fECk， 則twaitk可表示為

twaitk=SkfECk

(8)

本文邊緣計(jì)算卸載決策系統(tǒng)的主要考慮移動(dòng)終端設(shè)備端的能耗和時(shí)延，因此，任務(wù)卸載計(jì)算時(shí)，邊緣服務(wù)器的計(jì)算能耗忽略。若eoffk表示任務(wù)k卸載到邊緣服務(wù)器執(zhí)行的能耗，則eoffk可表示為

eoffk=eupk+ewaitk

(9)

式中：eupk表示Lk上傳計(jì)算任務(wù)k的傳輸能耗；ewaitk表示任務(wù)k卸載計(jì)算時(shí)，Lk空閑能耗。根據(jù)傳輸能耗=上傳功率*時(shí)間可得eupk， 即

eupk=Pktupk=PkBkWklog(1+PkHkσ2k)

(10)

當(dāng)計(jì)算任務(wù)k卸載到邊緣服務(wù)器后，Lk空閑時(shí)功率表示為Pwaitk， 則ewaitk可表示為

ewaitk=Pwaitktwaitk=PwaitkSkfECk

(11)

若全部卸載到邊緣服務(wù)器執(zhí)行計(jì)算的任務(wù)總能耗表示為EEC， 總時(shí)延表示為TEC， 則有

EEC=∑Kk=1akeoffk=∑Kk=1ak(eupk+ewaitk)

(12)

TEC=∑Kk=1aktoffk=∑Kk=1ak(tupk+twaitk)

(13)

根據(jù)式(4)和式(12)可得移動(dòng)終端設(shè)備的總能耗Etotal， 即

Etotal=Eloc+EEC=∑Kk=1(1-ak)elock+∑Kk=1ak(eupk+ewaitk)

(14)

根據(jù)式(5)和式(13)可得移動(dòng)終端設(shè)備的總時(shí)延Ttotal， 即

Ttotal=Tloc+TEC=∑Kk=1(1-ak)tlock+∑Kk=1ak(tupk+twaitk)

(15)

2.3 優(yōu)化問(wèn)題制定

假設(shè)計(jì)算任務(wù)全部都在本地執(zhí)行計(jì)算，總能耗設(shè)置為El、總時(shí)延設(shè)置為Tl。通過(guò)以上對(duì)計(jì)算模型的分析，移動(dòng)終端設(shè)備在整個(gè)計(jì)算卸載過(guò)程中的系統(tǒng)效用函數(shù)SQ定義為

SQ=αEl-EtotalEl+βTl-TtotalTl

(16)

式中：系數(shù)α和β分別表示在進(jìn)行卸載決策時(shí)，任務(wù)執(zhí)行計(jì)算能耗和時(shí)延之間的權(quán)衡因子，α，β∈[0，1]，α+β=1。 若該系統(tǒng)應(yīng)用于能耗不足的移動(dòng)終端設(shè)備時(shí)，需適當(dāng)調(diào)整α的值，且α>β；若該系統(tǒng)應(yīng)用于時(shí)延敏感型任務(wù)時(shí)，需適當(dāng)調(diào)整β的值，且α<β。 在本文中考慮時(shí)延和能耗同等重要，則α和β的取值均為0.5。在函數(shù)SQ中，若Etotal和Ttotal的值越小，則SQ的值越大，即在卸載過(guò)程中，移動(dòng)終端設(shè)備系統(tǒng)效用越大；若Etotal和Ttotal的值越大，則SQ的值越小，即在卸載過(guò)程中，移動(dòng)終端設(shè)備系統(tǒng)效用越小。因?yàn)?，Etotal值越小，有利于延長(zhǎng)移動(dòng)智能設(shè)備的電池壽命；Ttotal值越小，有利于提高用戶的服務(wù)體驗(yàn)質(zhì)量，所以，為了實(shí)現(xiàn)計(jì)算卸載中移動(dòng)終端設(shè)備系統(tǒng)效用最大化，將計(jì)算任務(wù)卸載的優(yōu)化目標(biāo)函數(shù)表示為

C1：ak∈{0，1}，?k∈K

C2：fECk>0，?k∈K

C3： ∑KkakfECk≤Fmax

C4：tlock≤Tmaxk，?k∈K

C5：toffk≤Tmaxk，?k∈K

C6：α，β∈[0，1]，α+β=1

(17)

其中，C1表示計(jì)算任務(wù)k的卸載決策；C2表示任務(wù)k得到的邊緣服務(wù)器計(jì)算資源是一個(gè)大于0的正數(shù)，C3表示邊緣服務(wù)器已被占用的計(jì)算資源之和不能超過(guò)自身最大計(jì)算資源Fmax； C4、C5都表示任務(wù)k的計(jì)算時(shí)延不能超過(guò)用戶對(duì)時(shí)延的容忍度；C6中α和β是能耗和時(shí)延的權(quán)重因子。

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

人工蜂群算法(artificial bee colony algorithm，ABC)是一種群智能算法，相比常見(jiàn)的遺傳算法、蟻群算法等啟發(fā)式算法，它的控制參數(shù)少、魯棒性強(qiáng)、局部收斂性強(qiáng)、算法復(fù)雜度低、易于實(shí)現(xiàn)，但ABC易陷入局部最優(yōu)解、開(kāi)發(fā)能力弱[9，10]、收斂速度慢。為使ABC性能更好，每次優(yōu)化更多變量，可以通過(guò)有效的變異和交叉組合來(lái)實(shí)現(xiàn)[11]。

差分進(jìn)化算法(differential evolution，DE)是一種基于種群的全局隨機(jī)搜索算法，具有較強(qiáng)的全局收斂性、穩(wěn)定性、魯棒性強(qiáng)等優(yōu)點(diǎn)，但在算法執(zhí)行后期收斂速度慢、可能會(huì)陷入局部最優(yōu)解。

當(dāng)研究基于群體智能或進(jìn)化算法時(shí)，對(duì)于不同類型的問(wèn)題，沒(méi)有一種算法能夠產(chǎn)生比所有其它算法都更好的解決方案[12]。本文提出優(yōu)化問(wèn)題P屬于二進(jìn)制0-1規(guī)劃問(wèn)題，而ABC和DE都是針對(duì)連續(xù)變量的算法，為了算法適用于本文的二進(jìn)制優(yōu)化問(wèn)題，故采用離散二進(jìn)制人工蜂群算法(BABC)和二進(jìn)制差分進(jìn)化算法(BDE)相結(jié)合來(lái)求解優(yōu)化問(wèn)題P。

3.1 二進(jìn)制人工蜂群算法

BABC算法主要包括3種蜜蜂：雇傭蜂、跟隨蜂、偵察蜂，每種蜜蜂負(fù)責(zé)一個(gè)階段。在雇傭蜂階段，每只雇傭蜂都試圖改善自己的蜜源；在跟隨蜂階段，每只跟隨蜂會(huì)根據(jù)蜜源的質(zhì)量更新自己的蜜源；在偵察蜂階段，如果跟隨蜂不能改善蜜源，偵察蜂就會(huì)開(kāi)始尋找新蜜源。

3.1.1 雇傭蜂階段

雇傭蜂對(duì)蜜源位置更新，位置更新公式采用Kiran and Gündüz(2013)提出的邏輯運(yùn)算公式

vi，j=Xi，j⊕?(Xi，j⊕Xn，j)

(18)

其中，Xi，j表示是種群中的第i個(gè)蜜源，第j個(gè)問(wèn)題維度的卸載決策，假設(shè)種群規(guī)模為N，i，n∈{1，2，…，N}，j={1，2，…，K}，i≠n；⊕表示異或運(yùn)算，數(shù)值相同為0；相異為1；?∈[0，1]。 表1中給出了式(18)的運(yùn)算真值，對(duì)于狀態(tài)1 (?<0.5)， 如果輸入位相同，則反轉(zhuǎn)輸出結(jié)果；否則輸出值和輸入位保持一致。

表1 邏輯運(yùn)算真值

若新蜜源Vi={vi，1，vi，2，……，vi，K} 的適應(yīng)度值大于Xi適應(yīng)度值，采用貪婪選擇的方式用Vi代替Xi， 否則保留Xi。

3.1.2 跟隨蜂階段

在跟隨蜂階段，采用輪盤賭方法選擇跟隨蜂。對(duì)于個(gè)體Xi， 若它的選擇概率為pi， 產(chǎn)生一個(gè)r1∈[0，1] 的隨機(jī)數(shù)，如果選擇概率pi大于r1， 則根據(jù)式(18)重新產(chǎn)生一個(gè)新蜜源X_newi， 且采用雇傭蜂階段相同的貪婪選擇方法確定保留蜜源。

3.1.3 偵察蜂階段

如果蜜源Xi經(jīng)過(guò)trial次迭代沒(méi)有找到更好的蜜源，且trial達(dá)到搜索閾值limit，則將蜜源Xi拋棄，與之對(duì)應(yīng)的雇傭蜂轉(zhuǎn)變?yōu)閭刹旆洌瑐刹旆潆S機(jī)產(chǎn)生一個(gè)新的蜜源代替Xi。

3.2 二進(jìn)制差分進(jìn)化算法

BDE算法與遺傳算法相似，但比遺傳算法易于實(shí)現(xiàn)，且具體操作不同，其主要包括3個(gè)步驟：變異、交叉、選擇。

3.2.1 變 異

變異操作是根據(jù)變異公式把幾個(gè)不同的個(gè)體融合成一個(gè)變異個(gè)體。Xingshi和Lin(2007)提出的二元突變方程

muti，j=Xr1，j⊙f?(Xr2，j?Xr3，j)

(19)

其中，Xr1，j、Xr2，j、Xr3，j是不同的3個(gè)個(gè)體，同一問(wèn)題維度的卸載決策，且i≠r1≠r2≠r3，r1，r2，r3∈{1，2，…，N}，j={1，2，…，K}；f是變異算子，f∈[0，1]； 使用邏輯運(yùn)算?(與)、⊙(或)可以使二進(jìn)制字符串直接進(jìn)化個(gè)體。

3.2.2 交 叉

定義r2∈[0，1] 的隨機(jī)數(shù)，CR是交叉算子，CR∈[0，1]。 對(duì)于交叉向量cori的每個(gè)值都有如下交叉方法

cori，j={muti，j，ifr2≤CR，

Xi，j，otherwise.

(20)

其中，Xi，j表示第i個(gè)個(gè)體，第j個(gè)問(wèn)題維度的卸載決策，j={1，2，…，K}。

3.2.3 選 擇

采用貪婪選擇的方式，在cori和Xi中選擇適應(yīng)度值較大的作為新的Xi。

3.3 binAD算法

提出基于BABC和BDE的新算法：binAD算法。binAD算法中將BABC和BDE相結(jié)合，并且對(duì)其中的變異操作和交叉操作進(jìn)行改進(jìn)。以下是binAD算法的詳細(xì)介紹。

3.3.1 編碼與初始種群

由于本文中的有K個(gè)待處理的計(jì)算任務(wù)，則種群的維度設(shè)為K，假設(shè)初始種群的規(guī)模為N，并采用式(21)生成初始種群。初始種群如圖2所示，每一行表示一個(gè)個(gè)體，每個(gè)個(gè)體代表一個(gè)卸載決策向量Xi，i∈{1，2，……，N}， 則Xi，j表示第i個(gè)決策向量中第j個(gè)問(wèn)題維度的卸載決策，j∈{1，2，…，K}

圖2 初始種群

Xi，j={0，ifrand()<0.5，

1，otherwise.

(21)

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

由于本文主要研究方向是通過(guò)優(yōu)化算法尋找到一個(gè)最優(yōu)任務(wù)卸載決策方案，使得任務(wù)卸載過(guò)程中，移動(dòng)智能設(shè)備系統(tǒng)效用最大化，所以根據(jù)式(16)將定義適應(yīng)度函數(shù)為

Fitness(i)=SQ(i)

(22)

式(22)中取系統(tǒng)效用函數(shù)值直接作為算法中的適應(yīng)度函數(shù)值，那么個(gè)體Xi的適應(yīng)度函數(shù)值越大，則說(shuō)明系統(tǒng)效用函數(shù)值越大，產(chǎn)生的能耗和時(shí)延，即該卸載決策越優(yōu)。

3.3.3 引入最優(yōu)個(gè)體的變異操作

在變異操作中引入最優(yōu)個(gè)體，可以跳出局部最優(yōu)解，向全局最優(yōu)解靠近，且可以增大算法在解空間中的搜索范圍。對(duì)式(19)改進(jìn)得到如下變異公式

muti=f1?(Xbest⊕Xr1)⊙

f2?(Xr2?Xr3)

(23)

其中，Xbest表示全局最優(yōu)個(gè)體；Xr1、Xr2、Xr3是不同于Xi的3個(gè)個(gè)體，且i≠r1≠r2≠r3，r1，r2，r3∈{1，2，…，N}；f1，f2∈[0，1]。

3.3.4 適應(yīng)性交叉概率因子

BABC中的交叉概率對(duì)算法的性能影響很大，例如，收斂速度、搜索能力等，因此在本文中修改交叉概率為適應(yīng)性交叉概率因子，如式(24)所示，以此提高算法的全局搜索能力

CR=0.6(iterMaxIt)2+0.3

(24)

其中，iter表示算法的當(dāng)前迭代次數(shù)，MaxIt表示最大迭代次數(shù)。

binAD算法流程如圖3所示。

圖3 binAD算法流程

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

在本節(jié)中，通過(guò)Matlab R2016a工具軟件進(jìn)行仿真和對(duì)比實(shí)驗(yàn)，并評(píng)估binAD算法的性能。

4.1 參數(shù)設(shè)置

本文中的相關(guān)仿真參數(shù)設(shè)置見(jiàn)表2。

表2 仿真參數(shù)設(shè)置

4.2 仿真實(shí)驗(yàn)與性能分析

為了驗(yàn)證算法的性能，將本文提出的binAD卸載決策與All-Local(計(jì)算任務(wù)全在本地執(zhí)行)、Full-Off(計(jì)算任務(wù)全卸載到邊緣服務(wù)器執(zhí)行)、Random算法(隨機(jī)卸載方法)、BABC算法(二進(jìn)制人工蜂群算法)、IbinABC算法[13]的卸載決策進(jìn)行比較，比較指標(biāo)主要有：迭代次數(shù)、任務(wù)量、種群數(shù)量、能耗、時(shí)延、系統(tǒng)效用。

4.2.1 迭代次數(shù)的影響

設(shè)任務(wù)量為10，種群數(shù)量為100。如圖4所示，展示了6種卸載決策在迭代次數(shù)從10增加到120，其系統(tǒng)效用的變化情況。當(dāng)計(jì)算任務(wù)全部在本地執(zhí)行(All-Local)時(shí)，系統(tǒng)效用全為0，這和系統(tǒng)效用函數(shù)的設(shè)計(jì)有關(guān)，同時(shí)也代表任務(wù)全部在本地執(zhí)行是最不理想的卸載方案。當(dāng)?shù)螖?shù)小于等于30時(shí)，binAD算法對(duì)應(yīng)的系統(tǒng)效用值有所波動(dòng)，這是因?yàn)榈螖?shù)較小，算法的搜索能力較弱，但當(dāng)?shù)螖?shù)大于30時(shí)，系統(tǒng)效用就趨于穩(wěn)定，維持在0.32～0.35之間?？傮w來(lái)說(shuō)，binAD算法在迭代次數(shù)對(duì)系統(tǒng)效用的影響中表現(xiàn)比BABC、Random、Full-Off、All-Local都好。

圖4 迭代次數(shù)對(duì)系統(tǒng)效用的影響

4.2.2 種群數(shù)量的影響

本小節(jié)主要分析種群數(shù)量對(duì)時(shí)延、能耗、系統(tǒng)效用的影響。設(shè)置迭代次數(shù)為100，任務(wù)量為50。

種群數(shù)量對(duì)時(shí)延的影響如圖5所示。從圖5可知，All-Local的時(shí)延遠(yuǎn)遠(yuǎn)大于另外5種方案，這是因?yàn)楸镜匾苿?dòng)終端設(shè)備自身?xiàng)l件受限，若執(zhí)行大量任務(wù)會(huì)帶來(lái)高時(shí)延。IbinABC、BABC和Random這3種算法的時(shí)延差距不太明顯，但I(xiàn)binABC相較于BABC和Random表現(xiàn)略好，且隨著種群數(shù)量的增加，時(shí)延變化不大，比較平穩(wěn)。Full-Off和binAD的時(shí)延明顯低于另外4種方案，F(xiàn)ull-Off時(shí)延較小是因?yàn)槿蝿?wù)全部卸載到高性能的邊緣服務(wù)計(jì)算，大大減少了任務(wù)計(jì)算時(shí)間，而binAD算法的時(shí)延和Full-Off接近，說(shuō)明卸載決策偏向于將任務(wù)卸載，但是并不是完全卸載，是因?yàn)閷さ阶顑?yōu)的卸載方案。binAD算法的時(shí)延沒(méi)有隨著種群數(shù)量的增加而波動(dòng)，說(shuō)明算法的穩(wěn)定好，全局搜索能力強(qiáng)。

圖5 種群數(shù)量對(duì)時(shí)延的影響

種群數(shù)量對(duì)能耗的影響如圖6所示。從圖中可以看出，All-Local的能耗較大，且遠(yuǎn)遠(yuǎn)高于另外5種方案，這是因?yàn)楸镜匾苿?dòng)終端設(shè)備計(jì)算能力、內(nèi)存等自身?xiàng)l件不足。相比binAD、IbinABC、BABC、Random算法，F(xiàn)ull-Off的能耗也較高，因?yàn)樾遁d的任務(wù)數(shù)據(jù)量太大，導(dǎo)致上傳數(shù)據(jù)的能耗增大。種群數(shù)量的變化對(duì)Random的能耗影響不大，隨機(jī)算法具有盲目性且沒(méi)有收斂性。當(dāng)種群數(shù)量小于120時(shí)，BABC的能耗有下降趨勢(shì)，但當(dāng)種群數(shù)量大于120時(shí)，最優(yōu)解的搜索范圍增加，反而使BABC找尋最優(yōu)解的能力降低。binAD和IbinABC隨著種群數(shù)量的增加，能耗都明顯低于另外4種方案，且表現(xiàn)穩(wěn)定，說(shuō)明這兩個(gè)算法的全局搜索能力和穩(wěn)定性都較好，只是IbinABC在種群數(shù)量大于160時(shí)，能耗的波動(dòng)較大。

圖6 種群數(shù)量對(duì)能耗的影響

種群數(shù)量對(duì)系統(tǒng)效用的影響如圖7所示。由于系統(tǒng)效用函數(shù)的設(shè)計(jì)，任務(wù)全部在本地執(zhí)行計(jì)算方案的系統(tǒng)效用依然為0。隨著種群數(shù)量的增加，BABC和Random的系統(tǒng)效用都呈上升趨勢(shì)，且差距不大，但是相較于binAD、IbinABC和Full-Off系統(tǒng)效用表現(xiàn)不好。IbinABC和Full-Off的系統(tǒng)效用雖然優(yōu)于All-Local、BABC和Random，但binAD算法的系統(tǒng)效用表現(xiàn)更好，且明顯高于另外5種卸載方案。當(dāng)種群數(shù)量大于120時(shí)，binAD算法表現(xiàn)非常穩(wěn)定，沒(méi)有隨著種群數(shù)量的增大而波動(dòng)。綜上，binAD算法算法的穩(wěn)定好，且全局搜索能力強(qiáng)，全局尋優(yōu)能力強(qiáng)。

圖7 種群數(shù)量對(duì)系統(tǒng)效用的影響

4.2.3 任務(wù)量的影響

本小節(jié)主要分析任務(wù)量對(duì)時(shí)延、能耗、系統(tǒng)效用的影響。設(shè)置迭代次數(shù)為100，種群數(shù)量為50。

從圖8任務(wù)量對(duì)時(shí)延的影響可以看出，隨著任務(wù)量的增加，各種方法生成的計(jì)算卸載決策在時(shí)延上都隨之增大。由于移動(dòng)終端設(shè)備的計(jì)算能力有限，隨著任務(wù)量的增加，移動(dòng)終端設(shè)備的負(fù)載增加，所以All-Local的時(shí)延明顯高于另外5種卸載方案。在任務(wù)量小于40時(shí)，binAD、IbinABC、BABC、Random、Full-Off的時(shí)延差距不大，但當(dāng)任務(wù)量大于40時(shí)，binAD和Full-Off的時(shí)延明顯低于IbinABC、BABC、Random。binAD算法的時(shí)延和Full-Off接近，這里再次說(shuō)明binAD卸載決策偏向于將任務(wù)卸載，但是并不是完全卸載，是因?yàn)閷さ阶顑?yōu)的卸載方案。

圖8 任務(wù)量對(duì)時(shí)延的影響

從圖9任務(wù)量對(duì)能耗的影響可以看出，隨著任務(wù)量的增加，各種方法生成的計(jì)算卸載決策在能耗上都隨之增大。其中，All-Local的能耗明顯高于另外5種卸載方案。而binAD、IbinABC、BABC、Random、Full-Off這5種卸載的方案的能耗差距不明顯。隨著任務(wù)量的增加，binAD算法在能耗方面表現(xiàn)一般。

圖9 任務(wù)量對(duì)能耗的影響

如圖10任務(wù)量對(duì)系統(tǒng)效用的影響所示。由圖可知，除了All-Local其余5種卸載方案的系統(tǒng)效用都有降低趨勢(shì)，這是因?yàn)楦鞣N方法生成的計(jì)算卸載決策在時(shí)延和能耗都隨任務(wù)量的增加而增大，則系統(tǒng)效用函數(shù)值隨之降低。其中，binAD算法在任務(wù)量大于50時(shí)，其系統(tǒng)效用表現(xiàn)平穩(wěn)，說(shuō)明該算法在大量計(jì)算任務(wù)情況下，全局搜索能力強(qiáng)。binAD算法雖然在圖9能耗方面表現(xiàn)一般，但是在圖8時(shí)延方面表現(xiàn)不錯(cuò)，因此binAD算法在系統(tǒng)效用優(yōu)于其它5種卸載方案。

圖10 任務(wù)量對(duì)系統(tǒng)效用的影響

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

本文采用binAD算法解決邊緣計(jì)算中的卸載決策問(wèn)題。以最大化移動(dòng)終端設(shè)備系統(tǒng)效用為目標(biāo)，制定邊緣計(jì)算卸載決策優(yōu)化問(wèn)題。為了克服BABC和BDE兩種算法的缺點(diǎn)，將二者相結(jié)合，并改進(jìn)其中的變異操作和交叉概率因子，得到binAD算法，該算法擴(kuò)大了可行解范圍、全局搜索能力強(qiáng)、穩(wěn)定性好。binAD算法在時(shí)延和系統(tǒng)效用方面可以取得較好的結(jié)果，但在能耗方面表現(xiàn)一般。由于本文提出的binAD算法在能耗方面表現(xiàn)一般，未來(lái)可在能耗方面繼續(xù)研究，實(shí)現(xiàn)更優(yōu)的邊緣計(jì)算卸載決策。