移動(dòng)邊緣計(jì)算中支持能量收集的計(jì)算卸載策略

蔣欣秀，楊俊東，楊志軍，李 波，丁洪偉

（云南大學(xué)，云南 昆明 650500）

0 引 言

隨著互聯(lián)網(wǎng)的興起，網(wǎng)絡(luò)技術(shù)和應(yīng)用服務(wù)的發(fā)展使網(wǎng)絡(luò)流量呈現(xiàn)爆炸式增長(zhǎng)，面對(duì)來勢(shì)兇猛的流量增長(zhǎng)，業(yè)界提出了移動(dòng)邊緣計(jì)算（Mobile Edge Computing，MEC）的概念。移動(dòng)計(jì)算在一定程度上解決了用戶終端計(jì)算能力不足的問題，但是對(duì)于具有時(shí)延敏感、計(jì)算密集、能耗巨大的新興應(yīng)用不斷涌現(xiàn)，MEC服務(wù)器的局限性也日益凸顯，因此，如何在邊緣計(jì)算系統(tǒng)中設(shè)計(jì)合理的計(jì)算卸載策略滿足用戶需求具有現(xiàn)實(shí)的意義。

計(jì)算卸載在邊緣計(jì)算網(wǎng)絡(luò)中作為一種節(jié)約設(shè)備能源的有效手段和減少時(shí)延的重要方法，國內(nèi)外很多學(xué)者對(duì)其做了大量研究，對(duì)于計(jì)算卸載的模式主要有三種方式：二進(jìn)制卸載、部分卸載、隨機(jī)卸載。文獻(xiàn)[5]采用二進(jìn)制卸載有效解決了任務(wù)時(shí)延和能耗均衡的問題，但任務(wù)的決策取決于終端設(shè)備的運(yùn)行狀態(tài)，系統(tǒng)的性能對(duì)設(shè)備的要求較高。任務(wù)卸載對(duì)于計(jì)算卸載的場(chǎng)景目前有單用戶單個(gè)MEC服務(wù)器、多用戶單個(gè)MEC服務(wù)器以及最復(fù)雜的多用戶多個(gè)MEC服務(wù)器。文獻(xiàn)[8]研究了多個(gè)任務(wù)之間卸載的順序，提出一種優(yōu)化算法均衡時(shí)延和能耗，但需要消耗大量的內(nèi)存。文獻(xiàn)[9]中利用整數(shù)規(guī)劃的優(yōu)化算法將部分卸載的計(jì)算任務(wù)建模為圖模型，但對(duì)于接入的用戶數(shù)增多，模型的復(fù)雜度也會(huì)隨之增加。上述工作雖在一定程度均衡了時(shí)延和能耗，但處理器的能耗隨其頻率呈線性增長(zhǎng)，導(dǎo)致其能耗過大。

基于上述分析，本文以多用戶多MEC服務(wù)器為場(chǎng)景，建立了一種基于能量收集技術(shù)獲取能源的移動(dòng)邊緣計(jì)算系統(tǒng)模型，采用動(dòng)態(tài)電壓頻率調(diào)節(jié)（Dynamic Voltage and Frequency Scaling，DVFS）技術(shù)調(diào)節(jié)移動(dòng)設(shè)備和MEC服務(wù)器的CPU最佳頻率，使本地執(zhí)行能耗和MEC服務(wù)器執(zhí)行能耗降至最低。對(duì)于卸載策略存在時(shí)域耦合的問題，采用Lyapunov理論將問題轉(zhuǎn)化為逐時(shí)隙定性問題求解，并將問題分解為能量收集和最優(yōu)決策兩個(gè)子問題，對(duì)于求解最優(yōu)決策問題提出了一種改進(jìn)的灰狼算法對(duì)CPU最佳頻率和發(fā)射功率進(jìn)行迭代以獲取最小的任務(wù)執(zhí)行代價(jià)。

1 系統(tǒng)模型

1.1 多用戶多MEC服務(wù)器模型

首先，對(duì)多用戶多MEC服務(wù)器模型做如下假設(shè)：

1）本模型由個(gè)移動(dòng)用戶和個(gè)MEC服務(wù)器組成，其中∈{1,2,…,,…,}，∈{1,2,…,,…,}。MEC系統(tǒng)模型如圖1所示；

圖1 MEC系統(tǒng)模型

2）移動(dòng)用戶配備了能量收集組件收集可再生能源，供用戶端計(jì)算和卸載使用；

3）模型為一個(gè)離散時(shí)間模型，τ表示一個(gè)時(shí)隙的長(zhǎng)度；

4）每個(gè)服務(wù)器的位置是固定的，每個(gè)移動(dòng)設(shè)備在相同的時(shí)隙內(nèi)位置不變，在不同時(shí)隙之間隨機(jī)變化；

5）信道獨(dú)立同分布（Independently Identically Distribution，IID），用戶通過無線信道訪問服務(wù)器，在時(shí)隙信道增益為h ，信道增益在同時(shí)隙內(nèi)保持不變，在不同時(shí)隙之間隨機(jī)變化。

1.2 系統(tǒng)模型

定義指標(biāo)變量ζ用以描述移動(dòng)用戶的任務(wù)請(qǐng)求，當(dāng)用戶在第個(gè)時(shí)隙內(nèi)有請(qǐng)求時(shí)，ζ=1，否則，ζ=0，U (D ,B ,)表示用戶在第個(gè)時(shí)隙產(chǎn)生計(jì)算密度為D 的任務(wù)，B 為卸載至MEC服務(wù)器的數(shù)據(jù)量，計(jì)算任務(wù)執(zhí)行時(shí)間不能超過單個(gè)時(shí)隙的長(zhǎng)度。每個(gè)被請(qǐng)求的計(jì)算任務(wù)可以在移動(dòng)設(shè)備上執(zhí)行，并將任務(wù)在本地成功執(zhí)行表示為；電池電量不足時(shí)任務(wù)會(huì)被丟棄，把本地丟棄的任務(wù)表示為；任務(wù)也可以卸載到MEC服務(wù)器上執(zhí)行，并將成功執(zhí)行的任務(wù)表示為；由于受到信道深衰落的影響會(huì)造成任務(wù)丟棄，把傳輸丟棄的任務(wù)表示為；計(jì)算模式選擇應(yīng)滿足以下約束：

若在時(shí)隙用戶有任務(wù)U (D ,B ,)請(qǐng)求在本地執(zhí)行任務(wù)，將用戶的CPU周期頻率表示為 ()，因此，第時(shí)隙用戶在本地執(zhí)行的時(shí)延表示為：

本地執(zhí)行任務(wù)時(shí)用戶所消耗的能量為：

式中： ?( ())表示本地計(jì)算的消耗功率，為有效開關(guān)系數(shù)，為常系數(shù)，一般為2，執(zhí)行頻率受到CPU周期頻率上限的約束，即 ()≤。

為計(jì)算卸載到MEC上的任務(wù)，本模型假設(shè)MEC服務(wù)器計(jì)算資源充足，且計(jì)算輸出很小，因此不考慮回傳的傳輸時(shí)延。將衰落信道功率增益表示為γ()，服從均值為1的指數(shù)分布，信道功率增益表示為h ()=γ()(d ())，其中為傳遞損失指數(shù)，表示路徑損耗常數(shù)，d 表示第時(shí)隙用戶與MEC服務(wù)器之間的距離。假設(shè)每個(gè)用戶都有相同的帶寬和噪聲功率，根據(jù)香農(nóng)公式，在時(shí)隙傳輸率表示為：

式中：是系統(tǒng)帶寬；表示噪聲功率；P ()表示用戶的發(fā)射功率。如果任務(wù)由MEC服務(wù)器執(zhí)行，傳輸時(shí)延表示為：

在第時(shí)隙中任務(wù)卸載至MEC服務(wù)器消耗的能量表示為：

在第時(shí)隙MEC服務(wù)器需要處理上傳數(shù)據(jù)量為B 的任務(wù)，表示計(jì)算每bit數(shù)據(jù)所需的周期數(shù)，因此，第時(shí)隙MEC處理卸載任務(wù)的計(jì)算時(shí)延表示為：

受到周圍環(huán)境狀態(tài)的影響，為了模擬能量收集過程中的間接性，把每個(gè)時(shí)隙到達(dá)移動(dòng)用戶的能量表示為e ()，且滿足0≤e ()≤，收集的能量存儲(chǔ)到電池中用于下一個(gè)時(shí)隙的本地執(zhí)行或卸載。在時(shí)隙開始時(shí)移動(dòng)用戶能量水平表示為C ()，第時(shí)隙用戶消耗的能量表示為?()，考慮到移動(dòng)用戶維護(hù)基本運(yùn)行需要一定的功耗，將其表示為，當(dāng)有任務(wù)請(qǐng)求計(jì)算ζ()=1時(shí)消耗的能量表示為：

式（8）服從能量因果約束?()≤C ()<+。

根據(jù)式（8），用戶的電池能量級(jí)按照式（9）進(jìn)行迭代：

1.3 執(zhí)行代價(jià)模型

由于能量收集存在隨機(jī)性和中斷性，當(dāng)本地缺乏能量時(shí)會(huì)造成一些任務(wù)被丟棄，本模型對(duì)丟棄的任務(wù)給予執(zhí)行代價(jià)懲罰。因此執(zhí)行代價(jià)表示本地計(jì)算時(shí)延、任務(wù)上傳時(shí)延和服務(wù)器計(jì)算時(shí)延三個(gè)部分，定義為：

式中：為任務(wù)丟棄的懲罰權(quán)重；()為指標(biāo)函數(shù)。因此，對(duì)于本模型的平均執(zhí)行成本最小化問題可以表示為：

約束條件說明：S表示在同一個(gè)時(shí)隙中每個(gè)用戶只能選擇1或0兩種模式；S表示每個(gè)用戶在同一個(gè)時(shí)隙中有且只有一種模式；S為電池電量的上限約束；S表示本模型在每個(gè)時(shí)隙時(shí)消耗的能量不超過開始時(shí)隙的電量；S表示用戶和MEC服務(wù)器CPU周期頻率的上限；S表示用戶發(fā)射功率不超過最大發(fā)射功率。

2 任務(wù)卸載決策

2.1 Lyapunov優(yōu)化算法

Lyapunov優(yōu)化算法是一種通過控制系統(tǒng)穩(wěn)定性來解決多目標(biāo)優(yōu)化的問題，多用于獨(dú)立同分布模型。由于系統(tǒng)的決策、電池能量水平均與時(shí)間相關(guān)，不能直接使用Lyapunov優(yōu)化技術(shù)，因此，提出了加權(quán)擾動(dòng)方法將與時(shí)間相關(guān)的問題轉(zhuǎn)化為逐時(shí)隙確定性問題，移動(dòng)用戶的擾動(dòng)參數(shù)定義為、虛擬能量隊(duì)列φ()，并將兩者的關(guān)系定義為：

式中 ：擾動(dòng)參數(shù)滿足≥+?，=min{max{(),τ},}表示在第個(gè)時(shí)隙用戶實(shí)際消耗能量的上限。在時(shí)隙將不同的用戶頻率和服務(wù)器頻率標(biāo)準(zhǔn)化為 ()=f ()，f ()=f ()，針對(duì)虛擬隊(duì)列表達(dá)式（12）將二次型Lyapunov函數(shù)定義為：

式（13）通過對(duì)更新隊(duì)列求平方和，表示在時(shí)隙各隊(duì)列中電池能量的多少，該函數(shù)值越大說明電池中能量越多，在時(shí)隙τ下的單步Lyapunov漂移函數(shù)表示為：

式中=2(+)。本模型的Lyapunov漂移加罰函數(shù)定義為單時(shí)隙Lyapunov偏移與執(zhí)行成本的加權(quán)差為：

式中是控制系數(shù)，用于權(quán)衡代價(jià)函數(shù)和虛擬隊(duì)列的穩(wěn)定性。

根據(jù)Lyapunov漂移加罰函數(shù)的上限值可將最優(yōu)的執(zhí)行代價(jià)模型表示為：

2.2 能量收集和最優(yōu)卸載決策

R是一種由Lyapunov理論優(yōu)化的優(yōu)化格式，根據(jù)文獻(xiàn)[15]，R問題可分解為能量收集和卸載決策兩個(gè)子問題。

本模型假設(shè)每個(gè)移動(dòng)設(shè)備都配備一個(gè)EH模塊且每個(gè)用戶在每個(gè)時(shí)隙收集的能量是獨(dú)立的，每一個(gè)EH模塊的充放電過程可以同時(shí)進(jìn)行。設(shè)定一個(gè)充電閾值M =0，當(dāng)設(shè)備的能量低于閾值時(shí)，電池與負(fù)載斷開以保護(hù)系統(tǒng)，在第時(shí)隙內(nèi)可收集的能量表示為Q ()，成功收集的能量為q ()，EH成功收集到的能量約束為q ()∈[ 0,Q ()]，由于電池容量有限，成功收集的能量q ()受最大電池容量約束q ()≤，由于配備EH模塊的模型執(zhí)行卸載策略較為復(fù)雜，本模型理想化考慮通過獲得各個(gè)用戶的所有時(shí)隙中最優(yōu)的e ()，即可得出最優(yōu)的能量收集。根據(jù)式（17）可將用戶收集能量的問題表示為：

在與目標(biāo)函數(shù)式（17）解耦之后，可以將過時(shí)隙的問題簡(jiǎn)化為：

當(dāng)ζ()=1時(shí)，R包括了本地執(zhí)行、卸載執(zhí)行、任務(wù)丟棄三個(gè)部分，根據(jù)式（8）、式（10），通過求解R的最小值以獲得最優(yōu)卸載決策M ()，其數(shù)學(xué)模型表示為：

式中：m (f )表示本地執(zhí)行代價(jià)函數(shù)的最小值；m (f ,P )表示卸載執(zhí)行代價(jià)的最小值。通過比較m (f )，m (f ,P )，m 的大小，選取其最小值為最優(yōu)卸載決策，當(dāng)任務(wù)被丟棄時(shí)有m =+φ，如果任務(wù)選擇在本地執(zhí)行，根據(jù)式（8）、式（10）、式（17）可將本地執(zhí)行代價(jià)模型表示為：

如果任務(wù)卸載至邊緣服務(wù)器執(zhí)行時(shí)，根據(jù)式（8）、式（10）、式（17）把卸載執(zhí)行代價(jià)模型表示為：

2.3 基于改進(jìn)灰狼算法的模式?jīng)Q策

為了求解本地執(zhí)行代價(jià)和卸載執(zhí)行代價(jià)模型的最小值，獲得最優(yōu)卸載決策，根據(jù)式（21）和式（22）需對(duì)CPU頻率和發(fā)射功率在多約束條件下進(jìn)行尋優(yōu)，因此，引入一種灰狼算法對(duì)模型進(jìn)行迭代，通過獲取最佳CPU頻率和發(fā)射功率，實(shí)現(xiàn)最優(yōu)模式的選擇。

灰狼優(yōu)化（Grey Wolf Optimization，GWO）算法是一種仿生群智能算法，模擬了狼群的等級(jí)制度和捕獵行為，種群按照其嚴(yán)格的等級(jí)制度進(jìn)行尋優(yōu)，每一頭狼個(gè)體代表一個(gè)優(yōu)化值，最優(yōu)解為狼，次優(yōu)解為狼，第三優(yōu)解為狼，優(yōu)化過程可建模為：

式中：X 表示獵物的位置；表示灰狼的位置；=|?X ()-()|表示灰狼和獵物之間的距離，其中2?，，為系數(shù)向量，且有=2?-，=2-?2，,為[0，1]之間的隨機(jī)矢量，是平衡全局搜索和局部搜索的參數(shù)，在每次迭代中保留最優(yōu)的三個(gè)解，利用這三個(gè)解進(jìn)行最優(yōu)位置的更新，可表示為：

式（24）表示，，與其他狼之間的距離，式（25）表示狼在，，狼的引導(dǎo)下進(jìn)行位置更新，由式（26）可得出全局最優(yōu)的位置。

在基本GWO中，參數(shù)對(duì)灰狼群體的尋優(yōu)過程有重要影響，利用GWO迭代計(jì)算最優(yōu)頻率和最優(yōu)發(fā)射功率時(shí)，控制參數(shù)線性遞減策略很難適用于該尋優(yōu)過程。針對(duì)這一問題，本模型基于指數(shù)規(guī)律變化的非線性收斂因子，提出一種改進(jìn)的灰狼PGWO（Parameter Grey Wolf Optimization）算法，其數(shù)學(xué)模型為：

式中：為當(dāng)前迭代次數(shù)；為最大迭代次數(shù)；為調(diào)節(jié)參數(shù)。在卸載中灰狼每一個(gè)個(gè)體代表一個(gè)頻率值，獵物代表全局最小值，為了求解m (f )和m (P )的最小值以獲得最優(yōu)卸載決策，可將求解流程表示為圖2。

圖2 基于PGWO的模式選擇流程圖

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

3.1 仿真實(shí)驗(yàn)環(huán)境

為了驗(yàn)證本模型的有效性和優(yōu)越性，使用Matlab R2018b軟件進(jìn)行仿真，計(jì)算機(jī)仿真操作環(huán)境為：IntelCore?i7?7700 CPU@3.6 GHz，仿真參數(shù)如表1所示。

表1 參數(shù)說明

本模型考慮5個(gè)MEC服務(wù)器和5個(gè)用戶，用戶在距離每個(gè)服務(wù)器半徑50 m的范圍內(nèi)隨機(jī)分布，仿真執(zhí)行400個(gè)時(shí)隙，每個(gè)時(shí)隙的長(zhǎng)度設(shè)為2 ms。

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

在不同種群數(shù)量下對(duì)改進(jìn)的灰狼算法進(jìn)行驗(yàn)證，結(jié)果如圖3所示，在不同的計(jì)算規(guī)模下，改進(jìn)的灰狼算法運(yùn)行時(shí)長(zhǎng)明顯低于其余兩種算法。為了驗(yàn)證該改進(jìn)算法適用于本模型，對(duì)三種算法在適用函數(shù)相同的情況下進(jìn)行了對(duì)比，結(jié)果如圖4所示。

圖3 用戶數(shù)與時(shí)間關(guān)系

由圖4可知，改進(jìn)的灰狼算法和灰狼算法趨勢(shì)相似，但改進(jìn)的灰狼算法在迭代300次時(shí)開始趨于收斂，且執(zhí)行代價(jià)較小，可用于本模型的分析。

圖4 迭代次數(shù)和執(zhí)行成本關(guān)系

由于自然界中的可再生資源（風(fēng)能、太陽能）存在不連續(xù)的問題，移動(dòng)用戶用于卸載任務(wù)和本地計(jì)算任務(wù)的能量需要連續(xù)性，以保證用戶體驗(yàn)質(zhì)量。因此基于上述問題，對(duì)本算法的移動(dòng)用戶電池能級(jí)進(jìn)行了測(cè)試，結(jié)果如圖5所示。隨著時(shí)隙的推移，各個(gè)移動(dòng)用戶電池能級(jí)在前期不斷進(jìn)行積累，最終穩(wěn)定在擾動(dòng)能級(jí)附近，在當(dāng)前的參數(shù)下，各個(gè)移動(dòng)用戶的電池能級(jí)在第200時(shí)隙開始穩(wěn)定，穩(wěn)定后的電池電量將完全用于下一個(gè)時(shí)隙的任務(wù)卸載和本地任務(wù)計(jì)算，有效地驗(yàn)證了能量收集的可行性。

圖5 各用戶能量收集與時(shí)間關(guān)系

計(jì)算模式的選擇決定了系統(tǒng)代價(jià)的大小并影響了用戶體驗(yàn)質(zhì)量。在本模型中，當(dāng)電池能級(jí)不足以支持任務(wù)的計(jì)算，任務(wù)將被丟棄，用戶體驗(yàn)質(zhì)量會(huì)隨著丟棄的任務(wù)增多而變低，同時(shí)用戶體驗(yàn)質(zhì)量與執(zhí)行時(shí)延有關(guān)，執(zhí)行時(shí)延基于對(duì)卸載代價(jià)、本地計(jì)算代價(jià)的比較選擇代價(jià)較小的模式。

圖6比較了多用戶多MEC服務(wù)器各模式選擇的比例，在開始階段，由于能量級(jí)別較低，大量的任務(wù)被丟棄，隨著電池能級(jí)趨于穩(wěn)定，任務(wù)丟棄率下降至0，在前100個(gè)時(shí)隙中，平均丟棄率為2.7%，平均卸載率達(dá)到90.6%，表明卸載到MEC服務(wù)器上的執(zhí)行代價(jià)是最小的。

圖6 任務(wù)執(zhí)行的模式選擇比例

執(zhí)行代價(jià)是任務(wù)處理的時(shí)延和能耗任務(wù)丟棄率的評(píng)價(jià)指標(biāo)，從圖7中可以看出，每個(gè)移動(dòng)用戶在開始時(shí)隙執(zhí)行代價(jià)很高，這表明開始時(shí)隙電量能級(jí)較低，時(shí)延和能耗以及被丟棄的任務(wù)會(huì)增加，隨著時(shí)隙的推移，執(zhí)行代價(jià)趨于一個(gè)穩(wěn)定的區(qū)間[0.05,0.09]，可說明本算法經(jīng)過迭代尋找到執(zhí)行代價(jià)最優(yōu)值。

圖7 各用戶平均執(zhí)行成本與時(shí)間關(guān)系

圖8描述了不同算法下的執(zhí)行代價(jià)隨時(shí)隙變化的情況，其中三種算法都隨著時(shí)隙的推移趨于一個(gè)穩(wěn)定的值，都能尋找到執(zhí)行代價(jià)最優(yōu)的值，然而改進(jìn)的灰狼算法比灰狼算法和遺傳算法收斂更快，因此，在時(shí)間收益上優(yōu)于其余兩種算法。

圖8 不同算法平均執(zhí)行成本與時(shí)間關(guān)系

根據(jù)圖9可以看出，在MEC服務(wù)器數(shù)目不變的情況下，用戶數(shù)量的增多會(huì)導(dǎo)致執(zhí)行代價(jià)的增長(zhǎng)，但是遺傳算法和灰狼算法在用戶數(shù)量增加時(shí)的執(zhí)行代價(jià)均大于改進(jìn)的灰狼算法，因此，本模型的算法具有較好的性能。

圖9 三種算法執(zhí)行成本與用戶數(shù)量的關(guān)系

4 結(jié) 語

本文研究了在多用戶多MEC服務(wù)器場(chǎng)景下，支持用戶收集能量的邊緣計(jì)算卸載問題，意在通過選擇合適的負(fù)載均衡模式和最大化能量收集策略，改善移動(dòng)邊緣計(jì)算表現(xiàn)，以提升系統(tǒng)用戶體驗(yàn)質(zhì)量。本模型基于能量收集技術(shù)，將收集的能量用于任務(wù)的執(zhí)行，節(jié)省了大部分的能源，以任務(wù)執(zhí)行代價(jià)為目標(biāo)，將最優(yōu)卸載策略抽象為時(shí)延、能耗和丟棄懲罰均衡問題，利用Lyapunov理論解決了時(shí)域耦合問題且將問題分解為能量收集和最優(yōu)決策問題，并基于改進(jìn)的灰狼算法對(duì)最優(yōu)決策問題進(jìn)行求解。實(shí)驗(yàn)證明，本文提出的可支持能量收集的邊緣計(jì)算卸載策略對(duì)于多用戶多MEC服務(wù)器的場(chǎng)景具有很好的魯棒性。