移動邊緣計算中基于Lyapunov 的任務(wù)卸載與資源分配算法

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

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

0 概述

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

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

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

1 系統(tǒng)模型與問題建模

1.1 系統(tǒng)場景

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

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

1.2 用戶任務(wù)隊列模型

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

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

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

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

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

1.3 MEC 服務(wù)器任務(wù)隊列模型

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

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

1.4 問題建模

1.4.1 時間平均吞吐量

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

進一步定義MEC 系統(tǒng)的時間平均收入為：

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

1.4.2 時間平均功耗

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

其中，κ是與芯片結(jié)構(gòu)相關(guān)的有效系數(shù)［17］。用戶i的時間平均功耗可表示為：

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

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

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

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

1.4.3 優(yōu)化模型

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

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

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

2.1 概率混合問題轉(zhuǎn)化

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

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

利用定義1 可將約束C8 和C9 轉(zhuǎn)化為：

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

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

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

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

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

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

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

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

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

3 計算資源與無線資源聯(lián)合分配方案

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

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

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

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

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

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

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

當Φi(t)-Ψji(t)≤0 時，問題P2.2 的目標函數(shù)隨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′的目標函數(shù)中含有2 個變量，若利用一般的凸優(yōu)化方法，算法有較高的復(fù)雜性。因此，本文將子問題P2.2′解耦為功率分配與帶寬分配2 個子問題，通過多次迭代得到最優(yōu)資源分配方案。

3.2.1 功率分配子問題

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

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

3.2.2 帶寬分配子問題

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

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

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

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

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

3.3 MEC 服務(wù)器計算資源分配問題

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

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

算法1MEC 服務(wù)器計算資源分配算法

3.4 本文算法描述

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

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

4 仿真結(jié)果與分析

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

表1 仿真參數(shù)設(shè)置Table 1 Simulation parameters setting

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

圖2 系統(tǒng)時間平均收益和控制參數(shù)V 的關(guān)系Fig.2 The relationship between system time average profit and control parameter V

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

圖3 系統(tǒng)時間平均收益和任務(wù)到達率的關(guān)系Fig.3 The relationship between system time average profit and task arrival rate

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

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

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

圖5 系統(tǒng)時間平均收益與用戶數(shù)的關(guān)系Fig.5 The relationship between system time average profit and the number of users

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

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

5 結(jié)束語

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