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

（云南大學，云南 昆明 650500）

0 引 言

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

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

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

1 系統(tǒng)模型

1.1 多用戶多MEC服務器模型

首先，對多用戶多MEC服務器模型做如下假設：

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

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

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

3）模型為一個離散時間模型，τ表示一個時隙的長度；

4）每個服務器的位置是固定的，每個移動設備在相同的時隙內位置不變，在不同時隙之間隨機變化；

5）信道獨立同分布（Independently Identically Distribution，IID），用戶通過無線信道訪問服務器，在時隙信道增益為h ，信道增益在同時隙內保持不變，在不同時隙之間隨機變化。

1.2 系統(tǒng)模型

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

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

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

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

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

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

在第時隙中任務卸載至MEC服務器消耗的能量表示為：

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

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

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

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

1.3 執(zhí)行代價模型

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

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

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

2 任務卸載決策

2.1 Lyapunov優(yōu)化算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 仿真實驗分析

3.1 仿真實驗環(huán)境

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

表1 參數(shù)說明

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

3.2 實驗結果與分析

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

圖3 用戶數(shù)與時間關系

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

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

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

圖5 各用戶能量收集與時間關系

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

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

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

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

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

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

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

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

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

4 結 語

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