唐 倫，胡彥娟，劉 通，陳前斌

（重慶郵電大學通信與信息工程學院移動通信技術重點實驗室，重慶 400065）

0 概述

隨著移動通信技術和互聯網的快速發(fā)展，虛擬現實、增強現實和人臉識別等具有計算密集、時延敏感等特性的應用不斷出現［1-2］。然而，由于終端設備在計算能力和電池壽命方面存在一定的局限性，導致它們難以支持上述應用［3］。受軟件定義網絡（Software Defined Network，SDN）和網絡功能虛擬化（Network Function Virtualization，NFV）的驅動，移動云計算（Mobile Cloud Computing，MCC）技術應運而生，其允許用戶將計算密集型任務卸載到資源豐富的遠端云服務器執(zhí)行，以緩解終端設備資源受限與高性能任務處理需求之間的沖突［4-5］。但是，在實際情況中，云服務器一般距離用戶較遠，云計算方案難以適用一些時延敏感的應用。為了解決這一問題，移動邊緣計算（Mobile Edge Computing，MEC）技術被提出［6］，它能夠在靠近移動設備的網絡邊緣提供云資源，不僅可以滿足時延敏感型應用的QoS 需求，而且還在一定程度上降低了計算密集型應用所帶來的網絡負載和設備終端能耗［7-8］。

目前，已有學者針對MEC 任務卸載與資源分配問題進行研究。文獻［9］考慮信道狀態(tài)和任務到達的隨機性，研究MEC 系統中能量效率與時延的權衡問題。文獻［10］針對正交頻分多址的移動邊緣網絡，設計一種基于計算能效的資源分配方案。文獻［11］以最小化移動設備和MEC 服務器的平均總功耗為目標，提出一種在線無線資源和計算資源管理算法。文獻［12］引入能量和時延加權因子，提出一種能量感知的卸載方案。雖然上述研究在一定程度上降低了任務時延和系統能耗，但考慮的均是單MEC 服務器場景下的資源分配問題，存在一定的局限性。在多服務器的MEC 系統場景下，文獻［13］提出一種以最小化服務成本、最大化服務終端數量為目標的任務卸載和資源分配算法，文獻［14］以最小化設備能耗和任務時延為目標，提出一種兩層博弈論的貪婪卸載方案，文獻［15］研究任務卸載和資源分配的聯合優(yōu)化問題，以降低設備能耗為目標，分別設計基于分支界定算法的最優(yōu)方案以及基于組合算法的次優(yōu)方案，這些方案更適用于實際邊緣計算網絡場景。此外，文獻［16-17］將MEC 與能量收集技術相結合，研究卸載策略與資源分配問題。然而，上述基于平均值設計的MEC 系統難以滿足低時延、高可靠的業(yè)務需求。文獻［18］雖然保證了用戶低時延、高可靠的需求，但是其忽略了對MEC 服務器計算資源的優(yōu)化，從而提高了執(zhí)行任務所消耗的功率成本并最終影響MEC 的系統收益。

考慮到任務到達的隨機性，本文建立一種任務隊列動態(tài)調度模型。為了滿足用戶對時延和可靠性的需求，對任務隊列施加概率約束并建立最大化MEC 系統平均收益的資源優(yōu)化模型。在此基礎上，利用馬爾科夫不等式［19］將概率混合優(yōu)化問題轉化為非概率優(yōu)化問題，通過Lyapunov 優(yōu)化理論將不同時隙下的耦合優(yōu)化問題轉化為3 個子問題并分別進行求解，以得到最優(yōu)任務卸載與資源分配方案。

1 系統模型與問題建模

1.1 系統場景

MEC 系統場景如圖1 所示，其由M個用戶、S個基站和多個MEC 服務器組成。其中，每個用戶通過無線鏈路關聯到距離其最近的基站，每個基站通過有線鏈路連接一個配備多CPU 內核的MEC 服務器［11，18］。為了方便分析，本文假定用戶計算任務由一個MEC 服務器處理，不考慮任務在服務器之間轉發(fā)。本文將網絡運行時間劃分為若干個時隙，用Γ={0，1，…}表示網絡運行的時隙集合，其中，定義每個時隙t的時間長度為τ?？紤]到任務到達的隨機性，本文建立兩級任務隊列模型，即用戶任務隊列模型和MEC 服務器任務隊列模型，以對計算任務的狀態(tài)進行刻畫。

圖1 移動邊緣計算系統場景Fig.1 The system scenarios of mobile edge computing

1.2 用戶任務隊列模型

假設每個用戶都有一個隊列緩沖區(qū)，存儲到達但未處理的計算任務。在每個時隙內，用戶計算任務的到達過程是獨立同分布的，且平均到達率為λi=E[Ai(t)]。同時，對于每個計算任務都可以選擇在用戶本地或者卸載到MEC 服務器進行處理。因此，本文定義時隙t時用戶任務隊列長度向量為Q(t)=[Q1(t)，Q2(t)，…，QM(t)]，Qi(t)的更新過程為：

其中，DΣ，i(t)為t時刻用戶i所處理的總計算任務量，其具體表達式為：

式（2）等號右側的第一部分為用戶本地處理的計算任務量，fi(t)是用戶i處理計算任務所分配的計算資源，即CPU 周期頻率，Li表示執(zhí)行每比特計算任務所需的CPU 周期；第二部分為卸載到MEC 服務器處理的計算任務量，R ij(t)是t時刻用戶i卸載計算任務到MEC 服務器j時的傳輸速率，其表達式為：

其中，W為MEC 服務器的帶寬，ξij(t)表示MEC 服務器j為用戶i分配的帶寬比例，pij(t)和hij(t)分別表示從用戶i到MEC 服務器j的傳輸功率和信道增益，N0為高斯白噪聲的功率譜密度。另外，由于每個基站都連接一個MEC 服務器，因此在本文中j∈S同時表示MEC 服務器。

任務請求具有動態(tài)性，可能出現任務隊列長度超出用戶緩存空間的情況，從而導致數據包的丟失。因此，為了滿足低時延、高可靠的任務需求，本文對用戶隊列長度添加概率約束［20］，即：

1.3 MEC 服務器任務隊列模型

每個MEC 服務器中有多個隊列緩沖區(qū)，可以同時存儲多個用戶卸載但尚未由MEC 服務器處理的計算任務。本文定義MEC 服務器j中用戶i的任務隊列為Xji(t)，其更新過程為：

本文同樣對MEC 服務器任務隊列長度添加概率約束，即：

1.4 問題建模

1.4.1 時間平均吞吐量

由式（1）可得t時刻用戶i所處理的計算任務量為DΣ，i(t)，將其記為t時刻系統用戶i的吞吐量，相應的用戶i時間平均吞吐量定義為Di，其表達式為：

進一步定義MEC 系統的時間平均收入為：

其中，αi表示處理用戶i任務的單位收入。

1.4.2 時間平均功耗

由式（2）、式（3）可知，用戶i在t時刻的處理功耗和傳輸功耗分別為：

其中，κ是與芯片結構相關的有效系數［17］。用戶i的時間平均功耗可表示為：

由式（5）可知，MEC服務器j在t時刻的處理功耗為：

則MEC 服務器j的時間平均功耗可表示為：

基于上述用戶和MEC 服務器的時間平均功耗，可定義用戶和MEC 服務器的時間平均功率消耗成本分別為：

其中，β和γ分別表示用戶和MEC 服務器的功率單位成本。

1.4.3 優(yōu)化模型

本文設計一種聯合功率、帶寬以及計算資源的分配算法，以在滿足低時延、高可靠業(yè)務需求的同時最大化MEC 系統的時間平均收益。時間平均收益指系統中所有用戶任務的時間平均收入與用戶和MEC 服務器時間功率消耗成本的差值，其優(yōu)化模型如下：

約束條件說明：C1 表示為用戶分配的計算資源不能超過總的計算資源C2 和C3 表示用戶的傳輸功率約束；C4 和C5 表示MEC 服務器j分配給用戶i的帶寬比例約束；C6 表示在MEC 服務器中并行處理用戶任務隊列的數量不能超過CPU 總核數N；C7 表示MEC 服務器j分配給用戶i的計算資源不能超過單個CPU 核的最大資源值；C8 和C9 分別表示用戶任務隊列上溢概率和MEC 服務器任務隊列上溢概率。

2 資源優(yōu)化問題轉化

2.1 概率混合問題轉化

由上述優(yōu)化模型可得問題P1 是一個概率混合優(yōu)化問題，其分析處理具有一定難度。因此，本文引入馬爾科夫不等式，對概率約束進行轉化［20］。

定義1（馬爾科夫不等式）若X是一個非負隨機變量，a＞0，則

利用定義1 可將約束C8 和C9 轉化為：

其中，C8′和C9′為連續(xù)時隙的平均約束，而C1～C7 是單時隙的瞬時約束。傳統方法難以處理不同時隙下的耦合問題，因此，本文利用Lyapunov 優(yōu)化理論設計一種基于單時隙狀態(tài)的資源分配方案。

2.2 基于Lyapunov 的優(yōu)化理論分析

本文引入虛擬隊列Yi(t)和Zji(t)對時間平均約束進行轉化，虛擬隊列更新方程分別為：

在t時刻系統的隊列狀態(tài)向量可表示為Θ(t)=[Yi(t)，Zji(t)]，進而定義Lyapunov 函數為：

式（21）表征了系統中的隊列擁塞程度，函數值越大，隊列越長，相應的用戶任務處理等待時間就越長。因此，為了縮短用戶的等待時延，保持系統的穩(wěn)定性，本文定義單時隙Lyapunov 偏移為：

在優(yōu)化理論中，Lyapunov 偏移通常用來進行資源分配策略選擇，為其添加一個加權代價函數，從而得到Lyapunov 偏移加罰。本文的Lyapunov 偏移加罰定義為單時隙Lyapunov 偏移與該時隙MEC 系統時間平均收益期望的加權差，即：

其中，V為權衡偏移函數與代價函數的非負控制參數，ζ為一個有限正常數，Dji(t)大小為

進一步將問題P1 轉化為最小化Lyapunov 偏移加罰上界的問題，即最小化式（23）的右側，得到：

在優(yōu)化問題P2中，Φi(t)=Vαi+Qi(t)+Yi(t)，Ψji(t)=Xji(t)+Zji(t)。

3 計算資源與無線資源聯合分配方案

由文獻［11，21］可知，問題P2 可以轉化成3 個子問題，即用戶本地計算資源分配問題P2.1、功率與帶寬資源分配優(yōu)化問題P2.2 以及MEC 服務器的計算資源分配問題P2.3。

3.1 用戶本地計算資源分配問題

根據式（24）可得用戶本地計算資源分配問題如下：

從式（25）可以看出，問題P2.1 是一個凸優(yōu)化問題，而且其目標函數和約束條件都可以對fi(t)進行分解，因此，可對每個fi(t)進行優(yōu)化。本地計算資源最優(yōu)解(t)可表示為：

3.2 功率與帶寬資源分配優(yōu)化問題

與無線資源相關的系統決策包括任務卸載的發(fā)射功率分配和帶寬分配，因為兩者為常數，所以難以適應時變的系統狀態(tài)［11］，因此，本文對問題P2 中的帶寬約束C5 進行修改，如下：

其中，δ為帶寬分配的最小比例，其取值范圍為Mj表示接入基站j的用戶數量。根據式（24）、式（27）可將P2.2 優(yōu)化問題轉化為：

當Φi(t)-Ψji(t)≤0 時，問題P2.2 的目標函數隨pij(t)的增大而增大。當pij(t)=0 時，問題P2.2 取最小值。令M′(t)表示Φi(t)≤Ψji(t)的用戶集合，最優(yōu)功率為(t)=0，最優(yōu)帶寬比例為(t)=δ。

當Φi(t)-Ψji(t)＞0 時，優(yōu)化問題變成一個凸優(yōu)化問題。令(t)表示Φi(t)＞Ψji(t)的用戶集合，因此，子問題P2.2 可簡化為：

子問題P2.2′的目標函數中含有2 個變量，若利用一般的凸優(yōu)化方法，算法有較高的復雜性。因此，本文將子問題P2.2′解耦為功率分配與帶寬分配2 個子問題，通過多次迭代得到最優(yōu)資源分配方案。

3.2.1 功率分配子問題

給定帶寬分配比例，用戶的功率資源分配問題可表示為：

類似于問題P2.1，本文對每個用戶的功率進行優(yōu)化，得到：

3.2.2 帶寬分配子問題

給定功率分配方案，用戶的帶寬資源分配問題可表示為：

子問題P2.2′.2 是一個凸優(yōu)化問題，聯合目標函數和約束條件可得到對應的拉格朗日函數，表示為：

其中，μ為約束條件對應的非負拉格朗日乘子。進一步，通過L(ξ，μ)對ξ求偏導數得到：

定義Gi(μ)為式（34）的解，因此，可以利用KKT條件得出最優(yōu)解，其中，最優(yōu)帶寬分配ξ*和最優(yōu)拉格朗日乘子μ*滿足：

進一步利用二分搜索法得到μ的最優(yōu)解并代入式（35）中，從而得到帶寬分配方案。

3.3 MEC 服務器計算資源分配問題

根據式（24）可以得到MEC 服務器的計算資源分配問題，如下：

由于約束條件C6 是一個離散約束，導致P2.3 問題是一個非凸優(yōu)化問題，但是，當忽略約束條件C6時，該問題是一個線性問題且目標函數和約束條件都可以對fji(t)進行分解。因此，本文首先對fji(t)進行優(yōu)化，得到初始計算資源分配方案，然后將得到的資源分配方案代入約束C6 中，判斷是否滿足約束，若滿足即得到最終解；否則，在初始解中依次選擇對目標函數貢獻最小的用戶，收回計算資源，即將fji(t)設置為0，直到滿足約束C6。MEC 服務器計算資源分配算法描述如算法1 所示。

算法1MEC 服務器計算資源分配算法

3.4 本文算法描述

結合3.1 節(jié)～3.3 節(jié)的分析，基于Lyapunov 的任務卸載與資源分配算法描述如算法2 所示。該算法是一個2 層迭代算法：外層循環(huán)是移動邊緣計算系統內的用戶隊列、MEC 服務器隊列以及虛擬隊列的更新；內層循環(huán)是對任務卸載與資源分配的3 個子問題求解。

算法2基于Lyapunov 的任務卸載與資源分配算法

4 仿真結果與分析

為了驗證本文所提算法的有效性，在一個400 m×400 m 的區(qū)域內均勻部署4 個基站和N個用戶，其中，每個基站都配備一個CPU 核數為8 的MEC 服務器。將本文算法與基于Lyapunov 優(yōu)化的在線聯合任務卸載與資源分配（OJ-TORA）算法［13］、基于時延與可靠性感知的任務卸載與資源分配（LRA-TORA）算法［18］以及任務全部本地執(zhí)行（Non-MEC）算法和任務全部卸載到MEC 服務器執(zhí)行（Fully-MEC）算法2 個基線算法進行比較。參考文獻［22］，本文的路徑損耗模型定義為h=127+30 logad，d的單位為km?？紤]到用戶所到達的任務與用戶所消耗功率以及MEC 所消耗功率的量級不同，因此，在文獻［21］收益和成本參數的基礎上對本文參數進行設置，單位任務收入為1×10-3unit/bit，單位功率成本為0.2 unit/W。本文其他仿真參數設置如表1 所示。

表1 仿真參數設置Table 1 Simulation parameters setting

圖2 所示為用戶數為40 時MEC 系統時間平均收益隨控制參數V的變化情況。從圖2 可以看出，時間平均收益隨控制參數V的增加而逐漸增大并趨于平穩(wěn)，這是因為在Lyapunov 優(yōu)化過程中，控制參數V越大，則系統越傾向于優(yōu)化罰函數，即系統時間平均收益，該結果驗證了本文所提算法的有效性。

圖2 系統時間平均收益和控制參數V 的關系Fig.2 The relationship between system time average profit and control parameter V

圖3 所示為不同算法下任務到達率與系統時間平均收益的關系。從圖3 可以看出，系統時間平均收益隨著任務到達率的增大而增大，而且對于任意任務到達率，本文算法在所有算法中收益最高。這是因為本文綜合考慮功率、帶寬資源以及計算資源并進行優(yōu)化，能在滿足用戶QoS 需求的同時合理地分配任務資源。

圖3 系統時間平均收益和任務到達率的關系Fig.3 The relationship between system time average profit and task arrival rate

從圖4 可以看出，本文算法相比其他3 種算法平均端到端時延更短，說明本文算法在當前業(yè)務激增的網絡環(huán)境下具有較好的時延性能。此外，Fully-MEC 算法相比其他算法平均端到端時延最長，這是因為其他3 種算法考慮了用戶本地執(zhí)行，在一定程度上縮短了時延。

圖4 平均端到端時延和任務到達率的關系Fig.4 The relationship between average end-to-end delay and task arrival rate

圖5 所示為不同算法下系統時間平均收益與用戶數的關系，從圖5 可以看出，4 種算法的系統時間平均收益都隨用戶數的增加而增加，但是當用戶數大于40后，收益的增長速率變緩。由于本文算法在分配帶寬資源時根據用戶實際需求動態(tài)分配而非均等劃分，提高了系統任務的收入，另一方面，該算法根據任務隊列狀態(tài)對MEC 服務器的計算資源進行分配，提高了資源利用率，節(jié)約了系統成本。因此，本文算法在系統時間平均收益上明顯優(yōu)于其他3 種算法。

圖5 系統時間平均收益與用戶數的關系Fig.5 The relationship between system time average profit and the number of users

由于隊列長度是評估用戶時延和數據可靠性的關鍵因素，因此本文對任務隊列長度的互補累積分布函數（CCDF）進行仿真，并將本文算法與LRATORA 和OJ-TORA 算法進行對比。當任務到達率為3 kb/slot 時，定義用戶隊列閾值和MEC 服務器隊列閾值分別為6×104bit 和5×105bit，平均隊列長度CCDF 如圖6 所示。從圖6 可以看出，OJ-TORA 算法用戶隊列和MEC 服務器任務隊列長度CCDF 都高于本文算法和LRA-TORA 算法，其可靠性最差。本文算法用戶任務隊列長度CCDF 均小于其他2 種算法，而MEC 服務器任務隊列長度CCDF 略高于LRA-TORA 算法，但并未超過隊列閾值，因此，本文算法仍具有較好的可靠性。

圖6 3 種算法的任務隊列長度CCDF 對比Fig.6 Comparison of task queue length CCDF of three algorithms

5 結束語

本文基于Lyapunov 優(yōu)化理論，提出一種最大化MEC 系統時間平均收益的任務卸載與資源分配算法。該算法在多MEC 服務器多用戶系統模型下，建立任務隊列動態(tài)調度模型并為隊列施加概率約束，在保證用戶時延和可靠性需求的同時對無線資源和計算資源實現聯合分配。同時，利用馬爾科夫不等式以及Lyapunov 優(yōu)化理論將優(yōu)化問題轉化為3 個子問題并進行求解。仿真結果表明，該算法在時延、可靠性以及系統收益方面均具有較好的性能表現。下一步將對動態(tài)場景下的任務卸載與資源分配問題進行研究。