查易藝 袁 燁 李金湖 柳 歡 陳振興 李 進(jìn)

1(國(guó)網(wǎng)江蘇省電力有限公司信息通信分公司 江蘇 南京 210024)

2(江蘇電力信息技術(shù)有限公司 江蘇 南京 210024)

3(國(guó)網(wǎng)信通億力科技有限責(zé)任公司 福建 福州 350003)

4(江蘇大學(xué)計(jì)算機(jī)學(xué)院 江蘇 鎮(zhèn)江 212013)

0 引 言

移動(dòng)智能手機(jī)的普及使得諸如面部識(shí)別、移動(dòng)健康監(jiān)測(cè)、增強(qiáng)現(xiàn)實(shí)和移動(dòng)游戲等復(fù)雜的交互式應(yīng)用越來(lái)越多地運(yùn)行于移動(dòng)設(shè)備端[1]。此類應(yīng)用的執(zhí)行需要高速的處理資源，從而得到較快的響應(yīng)時(shí)間，提高用戶體驗(yàn)[2-3]。面對(duì)此類需求，移動(dòng)邊緣云計(jì)算及其任務(wù)卸載(Task Offloading)技術(shù)應(yīng)運(yùn)而生[4-5]。應(yīng)用移動(dòng)邊緣計(jì)算技術(shù)，可以將移動(dòng)用戶設(shè)備方復(fù)雜的計(jì)算任務(wù)從移動(dòng)設(shè)備上卸載至資源能力更加強(qiáng)大的邊緣云服務(wù)器上執(zhí)行，借助于邊緣云的資源優(yōu)勢(shì)，得到更快的響應(yīng)時(shí)間，并節(jié)省移動(dòng)設(shè)備能耗[6-8]。然而，移動(dòng)設(shè)備與邊緣云間的無(wú)線通信環(huán)境對(duì)于任務(wù)卸載性能會(huì)產(chǎn)生重要影響[9-10]，且會(huì)直接影響到移動(dòng)用戶設(shè)備進(jìn)行任務(wù)卸載的決策。

目前，任務(wù)卸載問(wèn)題已有一些研究。考慮到5G時(shí)代移動(dòng)設(shè)備計(jì)算需求的巨大增長(zhǎng)，文獻(xiàn)[11]為了改善能效，設(shè)計(jì)了一種基于博弈理論的分布式任務(wù)卸載算法。文獻(xiàn)[12]在多信道環(huán)境下研究了面向多用戶的計(jì)算卸載決策問(wèn)題，但以上文獻(xiàn)均忽略了信道通信時(shí)的干擾問(wèn)題。為了節(jié)省移動(dòng)設(shè)備能耗，滿足應(yīng)用執(zhí)行的延時(shí)約束，文獻(xiàn)[13]提出了一種基于Lyapunov優(yōu)化技術(shù)的動(dòng)態(tài)卸載算法，能以較低的計(jì)算復(fù)雜度獲得近似最優(yōu)解。在大規(guī)模移動(dòng)應(yīng)用環(huán)境下，文獻(xiàn)[14]以最小化平均任務(wù)執(zhí)行延時(shí)為目標(biāo)，研究了多用戶的應(yīng)用分割與卸載問(wèn)題，并設(shè)計(jì)了離線式卸載決策算法。為了解決任務(wù)卸載面臨的傳輸延時(shí)和能耗問(wèn)題，文獻(xiàn)[15]設(shè)計(jì)了一種基于馬爾可夫決策過(guò)程的朵云任務(wù)卸載算法。然而，由于受限的無(wú)線網(wǎng)絡(luò)覆蓋問(wèn)題，朵云環(huán)境無(wú)法確保服務(wù)提供的連續(xù)性，無(wú)法應(yīng)用于移動(dòng)邊緣云中的卸載決策問(wèn)題。類似地，文獻(xiàn)[16]同樣利用馬爾可夫決策過(guò)程對(duì)服務(wù)遷移的序列卸載決策問(wèn)題進(jìn)行了形式化描述，并設(shè)計(jì)了求解算法?？紤]到受限的無(wú)線信道數(shù)量和通信干擾問(wèn)題，文獻(xiàn)[17]基于博弈論設(shè)計(jì)了一種分布式卸載決策算法，文獻(xiàn)[18]聯(lián)合考慮通信資源和計(jì)算資源分配，設(shè)計(jì)了迭代式任務(wù)卸載算法。

然而，以上方法在其性能和靈活性上有一定限制，算法的復(fù)雜性導(dǎo)致其不一定適應(yīng)于大規(guī)模無(wú)線網(wǎng)絡(luò)環(huán)境。移動(dòng)邊緣云環(huán)境下，無(wú)線訪問(wèn)點(diǎn)(基站)通常在多信道環(huán)境下，若過(guò)多的移動(dòng)設(shè)備同步選擇相同信道進(jìn)行任務(wù)卸載，通信干擾將嚴(yán)重影響數(shù)據(jù)傳輸性能，進(jìn)而導(dǎo)致任務(wù)執(zhí)行延時(shí)增加和移動(dòng)設(shè)備能耗增加。此時(shí)，任務(wù)卸載將得不償失，即：任務(wù)卸載決策必須同步考慮通信資源和計(jì)算資源的分配。為了解決此問(wèn)題，本文將設(shè)計(jì)基于能效的任務(wù)卸載決策算法，并重點(diǎn)解決：1) 考慮能效和延時(shí)的情況下，哪些移動(dòng)用戶任務(wù)適合于進(jìn)行卸載；2) 從全局最優(yōu)的角度，對(duì)于需要進(jìn)行卸載的任務(wù)，如何選擇合適的無(wú)線信道進(jìn)行任務(wù)卸載。

1 系統(tǒng)模型與優(yōu)化目標(biāo)

移動(dòng)邊緣云計(jì)算(Mobile Edge Computing, MEC)包括三個(gè)組成部分：移動(dòng)邊緣云服務(wù)器，無(wú)線訪問(wèn)點(diǎn)AP和移動(dòng)用戶設(shè)備。結(jié)構(gòu)如圖1所示。移動(dòng)用戶可將本地任務(wù)通過(guò)Wi-Fi、4G或5G通信方法通過(guò)無(wú)線訪問(wèn)點(diǎn)提交至邊緣云服務(wù)器執(zhí)行，即任務(wù)卸載。假設(shè)N={1,2,…,N}表示移動(dòng)用戶集合，M={1,2,…,M}表示無(wú)線訪問(wèn)點(diǎn)AP可提供的無(wú)線信道集合，且每個(gè)移動(dòng)用戶擁有一個(gè)任務(wù)執(zhí)行需求。用戶任務(wù)具有兩個(gè)屬性，表示為Ti=(Oi,Di)，i=1,2,…,N，其中，Oi表示完成用戶i的任務(wù)需要的總CPU周期數(shù)，Di表示用戶i任務(wù)的數(shù)據(jù)量。用戶任務(wù)Ti可在移動(dòng)設(shè)備上本地執(zhí)行，也可以通過(guò)卸載方式傳輸至邊緣云端執(zhí)行。

圖1 移動(dòng)邊緣云計(jì)算結(jié)構(gòu)

(1)

根據(jù)移動(dòng)設(shè)備的CPU能量模型[19]，任務(wù)本地執(zhí)行的能耗可表示為：

(2)

式中：αi、βi、χi均表示CPU能量模型的參數(shù)，不同類型和處理能力的CPU擁有不同的取值。

若移動(dòng)用戶將任務(wù)通過(guò)無(wú)線信道卸載至邊緣云執(zhí)行，則整個(gè)任務(wù)執(zhí)行過(guò)程由三個(gè)部分組成。

(3)

令ψ=(ψ1,j,ψ2,j,…,ψN,j)表示所有移動(dòng)用戶的卸載決策解，移動(dòng)用戶i選擇無(wú)線信道j上傳數(shù)據(jù)的速率計(jì)算為：

(4)

(5)

(6)

2) 無(wú)線訪問(wèn)點(diǎn)AP通過(guò)高速有線網(wǎng)絡(luò)將任務(wù)負(fù)載數(shù)據(jù)傳輸至邊緣云服務(wù)器，該部分的傳輸延時(shí)可忽略不計(jì)。

(7)

若任務(wù)在邊緣云執(zhí)行，移動(dòng)用戶設(shè)備需要等待返回結(jié)果，此時(shí)移動(dòng)設(shè)備的空閑能耗計(jì)算為：

(8)

因此，任務(wù)卸載至邊緣云執(zhí)行的總體能耗為：

(9)

任務(wù)卸載至邊緣云執(zhí)行的總時(shí)間為：

(10)

為了優(yōu)化任務(wù)卸載執(zhí)行的能效，需要合理地進(jìn)行通信資源和計(jì)算資源的分配。故任務(wù)卸載決策的能效最優(yōu)化可形式化為：

(11)

約束條件為：

(12)

(13)

(14)

(15)

ψi,j={0,1} ?i∈N,j∈M

(16)

其中：式(12)確保任務(wù)卸載執(zhí)行的能耗應(yīng)小于或等于任務(wù)本地執(zhí)行能耗；式(13)確保任務(wù)卸載執(zhí)行的時(shí)間應(yīng)小于或等于任務(wù)本地執(zhí)行時(shí)間；式(14)確保無(wú)線信道的通信質(zhì)量，為信道設(shè)置門限值π可以避免過(guò)多的移動(dòng)用戶方同時(shí)訪問(wèn)同一信道，增加數(shù)據(jù)沖突；式(15)表明移動(dòng)用戶僅能選擇訪問(wèn)一條無(wú)線信道；式(16)表明任務(wù)僅能在本地執(zhí)行或邊緣云上執(zhí)行。

2 能效任務(wù)卸載算法

為了求解式(11)的最優(yōu)化問(wèn)題，本文設(shè)計(jì)了一種能效任務(wù)卸載算法。算法由兩個(gè)部分組成：(1) 決定移動(dòng)用戶分類和優(yōu)先級(jí)；(2) 根據(jù)優(yōu)先級(jí)，移動(dòng)用戶依次獲得通信資源分配。

2.1 移動(dòng)用戶分類和優(yōu)先級(jí)確定

根據(jù)任務(wù)數(shù)據(jù)量、負(fù)載密度、計(jì)算能力以及能耗，移動(dòng)用戶可劃分為兩類。第一種類型的移動(dòng)用戶為本地執(zhí)行任務(wù)的移動(dòng)用戶，令Ul表示該類型用戶。當(dāng)移動(dòng)用戶單獨(dú)占用一個(gè)信道時(shí)，該移動(dòng)用戶設(shè)備的數(shù)據(jù)傳輸速率可表示為：

(17)

(18)

換言之，若任務(wù)卸載執(zhí)行的能耗大于本地執(zhí)行能耗，則移動(dòng)用戶劃分為第一類用戶Ul。

令Uo表示為第二種類型用戶，為除了第一種類型用戶外的其他用戶。屬于Uo的移動(dòng)用戶可選擇在本地執(zhí)行任務(wù)或卸載至邊緣云執(zhí)行，其最終決策取決于信道的通信質(zhì)量。對(duì)于該類型移動(dòng)用戶，在卸載決策過(guò)程中需設(shè)置不同的優(yōu)先級(jí)，按其優(yōu)先級(jí)依次作出卸載決策，將優(yōu)先級(jí)定義為：

(19)

算法1為移動(dòng)用戶分類與優(yōu)先級(jí)確定過(guò)程。

算法1移動(dòng)用戶分類與優(yōu)先級(jí)計(jì)算

2. 輸出：移動(dòng)用戶分類集合Ul和Uo，移動(dòng)用戶優(yōu)先級(jí)η={ηi},i∈Uo

3. For 移動(dòng)用戶i=1 toNdo

4. For 信道j=1 toMdo

5. 根據(jù)式(17)和式(18)分別計(jì)算移動(dòng)用戶獨(dú)占用一條信道時(shí)的數(shù)據(jù)傳輸速率和能耗

7. 移動(dòng)用戶i歸屬于類型Ul

8. else

9. 移動(dòng)用戶i歸屬于類型Uo

11. end if

12. end for

2.2 基于拍賣的卸載機(jī)制

圖2 拍賣示意圖

傳統(tǒng)的拍賣過(guò)程中，資源分配是通過(guò)多輪的競(jìng)標(biāo)過(guò)程確定最終的贏家。然而，這種多輪拍賣并不適用于本文的場(chǎng)景，因?yàn)檫@會(huì)導(dǎo)致移動(dòng)用戶任務(wù)執(zhí)行中過(guò)多的等待延時(shí)。本文采用單輪拍賣以改進(jìn)能效，降低任務(wù)卸載延時(shí)。

資源分配中，結(jié)合資源和競(jìng)標(biāo)者給出的價(jià)格信息，移動(dòng)用戶可以決定哪條信道成為拍賣贏家，并確定最終的資源交易價(jià)格bj。因此，此時(shí)的最優(yōu)化問(wèn)題即可轉(zhuǎn)換為拍賣問(wèn)題，ψi,j表示拍賣結(jié)果，ψi,j=0表示無(wú)拍賣贏家，ψi,j=1表示信道j贏得拍賣。而算法目標(biāo)也相應(yīng)地可轉(zhuǎn)化為是最大化移動(dòng)用戶的效用，形式化為：

(20)

為了確定拍賣贏家和資源分配關(guān)系，首先需要計(jì)算拍賣參與者的競(jìng)標(biāo)密度并對(duì)其排序。對(duì)于給定的無(wú)線信道，無(wú)線信道可根據(jù)其競(jìng)標(biāo)密度進(jìn)行降序排列。對(duì)于移動(dòng)用戶，最低的競(jìng)標(biāo)密度即表示最優(yōu)的通信質(zhì)量。定義作為賣方的信道的競(jìng)標(biāo)密度為：

(21)

移動(dòng)用戶向賣方支付的最終交易價(jià)格為bj，即為贏家無(wú)線信道發(fā)送的競(jìng)標(biāo)價(jià)格。此時(shí)，移動(dòng)用戶的效用函數(shù)為：

(22)

若移動(dòng)用戶沒(méi)有參與拍賣，其效用值為0。換言之，若ψi,j=0，則U=0。而作為賣方的無(wú)線信道的效用函數(shù)可表示為：

(23)

若無(wú)線信道沒(méi)有贏得拍賣，則ψi,j=0，顯然其效用也為0。

拍賣過(guò)程如算法2所示。

算法2基于拍賣的任務(wù)卸載決策算法

1. 輸入：分類移動(dòng)用戶Ul和Uo，及優(yōu)先級(jí)η

2. 輸出：移動(dòng)用戶的卸載決策解ψ=(ψ1,j,ψ2,j,…,ψN,j)

3. 設(shè)置臨時(shí)集合U’o=Uo

4. whileU’o≠

5. 選擇移動(dòng)用戶i,i=argmax{ηi}i,i∈Uo}

6. for 信道j=1 toM

8. ifπj>0 then

9. 根據(jù)二元組(bj,sj)計(jì)算信道j的競(jìng)標(biāo)密度bdj(式(21))

10. 設(shè)置競(jìng)標(biāo)密度bd={bdj}

11. whilebd≠

12. 選擇信道j,j=argmin{bdj}j

14.ψi,j=1

//更新信道門限值

16. else

17.ψi,j=0

18. end if

19.bd=bdj

//計(jì)算競(jìng)標(biāo)密度時(shí)將信道j移出集合bd

20. end while

21. else

22.ψi,j=0

23. end if

24. end for

25.U’o=U’oi

//移出信道j，更新第二種類型移動(dòng)用戶

26. end while

3 實(shí)驗(yàn)分析

通過(guò)仿真實(shí)驗(yàn)評(píng)估算法性能，選擇基于競(jìng)爭(zhēng)的博弈卸載算法GOCA[20]、基于用戶滿意度的卸載算法USOA[21]以及本地執(zhí)行算法LA作為對(duì)比算法。GOCA將任務(wù)卸載問(wèn)題建立了任務(wù)執(zhí)行期限和信道速率約束的競(jìng)爭(zhēng)博弈模型，在競(jìng)爭(zhēng)有限的通信資源的同時(shí)，最小化能耗，通過(guò)一種基于納什均衡的方式得到了移動(dòng)用戶的卸載決策解。USOA引入一種效用函數(shù)，根據(jù)系統(tǒng)吞吐量、能耗以及執(zhí)行延時(shí)描述的用戶滿意度進(jìn)行最優(yōu)的通信資源選擇，并最終得到其卸載決策解。LA選擇將所有任務(wù)均在本地設(shè)備上執(zhí)行，以此衡量任務(wù)卸載執(zhí)行的優(yōu)勢(shì)。選取平均能耗、延時(shí)和移動(dòng)用戶設(shè)備上的系統(tǒng)吞吐量作為性能評(píng)估指標(biāo)。

3.1 實(shí)驗(yàn)環(huán)境搭建

在MATLAB環(huán)境中搭建以下實(shí)驗(yàn)環(huán)境：無(wú)線訪問(wèn)點(diǎn)AP的覆蓋半徑設(shè)置為2 km，并擁有4條無(wú)線信道，信道帶寬設(shè)置為1 MHz，信道噪聲功率σ2=-100 dBm，路徑衰減因子設(shè)置為2。若干移動(dòng)用戶設(shè)備隨機(jī)分布無(wú)線訪問(wèn)點(diǎn)的覆蓋區(qū)域中，邊緣云服務(wù)器位于無(wú)線訪問(wèn)點(diǎn)附近。實(shí)驗(yàn)利用四種類型的移動(dòng)設(shè)備進(jìn)行仿真分析，包括Galaxy Note、Galaxy Note2、Nexus S和Galaxy Nexus，不同的移動(dòng)設(shè)備其CPU處理能力均不相同，相關(guān)參數(shù)配置如表1所示。實(shí)驗(yàn)將隨機(jī)選擇若干臺(tái)移動(dòng)設(shè)備部署于無(wú)線訪問(wèn)點(diǎn)附近，且每臺(tái)移動(dòng)設(shè)備均有一個(gè)任務(wù)執(zhí)行需求。任務(wù)類型包括面部識(shí)別、病毒掃描、在線游戲和虛擬現(xiàn)實(shí)等。每臺(tái)移動(dòng)設(shè)備上隨機(jī)分配一種任務(wù)類型，不同類型的移動(dòng)設(shè)備處理不同類型任務(wù)時(shí)具有不同的處理能力和速度，對(duì)應(yīng)參數(shù)配置如表2所示，包括負(fù)載密度、數(shù)據(jù)大小及分配的處理能力。

表1 移動(dòng)設(shè)備類型及參數(shù)

表2 任務(wù)類型及參數(shù)

3.2 實(shí)驗(yàn)結(jié)果

圖3為四種算法的移動(dòng)設(shè)備的平均能耗結(jié)果，移動(dòng)設(shè)備數(shù)量選擇200、400、600、800、1 000進(jìn)行結(jié)果觀察。可以看到，本地執(zhí)行算法LA的平均能耗約為22.1 J，其他三種基于任務(wù)卸載的算法得到的能耗均小于LA，說(shuō)明任務(wù)卸載可以帶來(lái)能效的優(yōu)化。在200個(gè)移動(dòng)設(shè)備情況下，三種卸載算法的能耗分別為6.42、6.5和6.95。隨著移動(dòng)設(shè)備數(shù)量的逐步增加，平均能耗分別增加至11、12.6和14.5 J，這是由于此時(shí)過(guò)多的移動(dòng)設(shè)備同步選擇訪問(wèn)相同的無(wú)線信道進(jìn)行任務(wù)卸載，進(jìn)而導(dǎo)致了過(guò)多的信道沖突。由信道速率的計(jì)算公式可知，過(guò)多的信道沖突會(huì)降低信道通信質(zhì)量和計(jì)算卸載的數(shù)據(jù)傳輸速率。因此，在1 000個(gè)移動(dòng)設(shè)備情況下，會(huì)有越來(lái)越多的用戶選擇本地執(zhí)行方法，進(jìn)而導(dǎo)致平均能耗逐漸增加?？傮w來(lái)說(shuō)，本文算法可節(jié)省約56%的能耗。而在三種基于卸載的算法中，本文算法也具有一定的優(yōu)勢(shì)，原因在于基于拍賣機(jī)制的任務(wù)卸載決策方法是以更長(zhǎng)周期的方式得到任務(wù)卸載決策，以更加合理的方式在滿足用戶質(zhì)量需求的情況下為移動(dòng)用戶分配通信資源。同時(shí)，在移動(dòng)設(shè)備相對(duì)較少時(shí)，能耗節(jié)省效果也更加明顯。隨著移動(dòng)設(shè)備數(shù)量的顯著增加，由于負(fù)載擁塞，本文算法性能有所下降，但仍優(yōu)于GOCA和USOA。

圖3 平均能耗

圖4為移動(dòng)用戶執(zhí)行任務(wù)的平均延時(shí)情況。本地執(zhí)行算法的平均延時(shí)約為27.5 s，在移動(dòng)設(shè)備數(shù)為200時(shí)，另外三種算法的平均延時(shí)分別約為14.6、14.7和15.5 s。比較本地執(zhí)行算法，卸載算法至少可節(jié)省約45.6%的延時(shí)。在1 000個(gè)移動(dòng)設(shè)備情況下，四種算法得到的延時(shí)分別為19.6、20.06、20.84和27.5 s。本文算法依然是所有算法所用延時(shí)最少的。

圖4 平均延時(shí)

圖5為三種任務(wù)卸載算法的移動(dòng)設(shè)備上吞吐量的變化情況，由于LA算法僅在本地進(jìn)行任務(wù)執(zhí)行，無(wú)需進(jìn)行數(shù)據(jù)傳輸，其吞吐量始終為0。從結(jié)果可以看出，盡管本文算法在初始情況下吞吐量更低，但隨著移動(dòng)設(shè)備的增加，其吞吐量下降的趨勢(shì)要慢于對(duì)比算法，最終超過(guò)對(duì)比算法。隨著移動(dòng)設(shè)備數(shù)的增加，相應(yīng)的信道通信干擾也將增加。相應(yīng)地，數(shù)據(jù)傳輸速率有所下降，導(dǎo)致卸載能耗高于本地執(zhí)行能耗。因此，更多的移動(dòng)設(shè)備將傾向于采用本地執(zhí)行策略取代任務(wù)卸載?？傮w來(lái)說(shuō)，本文算法在大規(guī)模移動(dòng)設(shè)備的測(cè)試中得到的吞吐量高于兩種對(duì)比算法。

圖5 平均吞吐量

綜合仿真實(shí)驗(yàn)來(lái)看，在無(wú)線訪問(wèn)點(diǎn)及其無(wú)線信道數(shù)量固定的情況下，可以支持仿真實(shí)驗(yàn)環(huán)境設(shè)置的不同規(guī)模移動(dòng)設(shè)備量的任務(wù)執(zhí)行與卸載需求。但在有限的無(wú)線信道條件下，勢(shì)必會(huì)導(dǎo)致任務(wù)執(zhí)行延時(shí)和平均能耗的增加，以及平均吞吐量的降低。原因在于：移動(dòng)設(shè)備量越多，負(fù)載將出現(xiàn)擁塞，信道爭(zhēng)用將越劇烈，數(shù)據(jù)傳輸時(shí)間勢(shì)必變長(zhǎng)，相應(yīng)傳輸能耗也將增加，單位時(shí)間內(nèi)系統(tǒng)完成的任務(wù)量則相應(yīng)減少。在實(shí)際應(yīng)用環(huán)境中，單個(gè)無(wú)線訪問(wèn)點(diǎn)在其覆蓋范圍內(nèi)所能支持的移動(dòng)設(shè)備數(shù)量則與訪問(wèn)點(diǎn)自身的處理能力和支持的無(wú)線信道數(shù)量相關(guān)。

4 結(jié) 語(yǔ)

為了優(yōu)化移動(dòng)設(shè)備的能耗，本文基于移動(dòng)邊緣云計(jì)算環(huán)境提出了一種基于能效的任務(wù)卸載決策算法。算法綜合考慮信道干擾、任務(wù)本地執(zhí)行延時(shí)以及執(zhí)行能耗，將任務(wù)卸載決策問(wèn)題形式化為0-1非線性整數(shù)規(guī)劃問(wèn)題。為求解該問(wèn)題，設(shè)計(jì)了移動(dòng)用戶分類和優(yōu)先級(jí)確定機(jī)制，利用拍賣理論求解了任務(wù)卸載決策，并確定了所選任務(wù)卸載信道。仿真實(shí)驗(yàn)表明，在能耗、延時(shí)以及吞吐量三個(gè)指標(biāo)上，本文算法均優(yōu)于對(duì)比算法。