葛海波，陳旭濤，劉林歡，李 順

(西安郵電大學 電子工程學院，陜西 西安 710121)

0 引 言

過去十年移動通信設備和移動應用程序快速發(fā)展成為人們生活中不可或缺的一部分。手機、掌上電腦等設備為用戶提供多種數(shù)字服務如增強現(xiàn)實[1]、虛擬現(xiàn)實[2]等，這些任務往往需要大量的計算資源和較高的服務質(zhì)量。移動設備由于自身的電池和計算能力的限制，計算任務需要通過網(wǎng)絡傳輸?shù)竭h程服務器，經(jīng)過處理后傳回移動設備，這就是云計算[3]。由于移動設備的數(shù)量瘋狂增長和網(wǎng)絡帶寬資源的不足，這種方法存在較高的延遲和不穩(wěn)定性。針對這些問題，移動邊緣計算[4](mobile edge computing，MEC)應運而生。MEC將移動用戶所需的計算資源下沉到接近用戶的位置，在移動設備附近部署邊緣服務器，MEC網(wǎng)絡中的移動設備可以將其任務卸載到附近的邊緣服務器，并在處理后立即收到結(jié)果。

現(xiàn)在我們已經(jīng)進入到第五代(5G)移動網(wǎng)絡，需要進行超密集組網(wǎng)(ultra-dense network，UDN)部署超密集小蜂窩網(wǎng)絡。每個移動設備的通信范圍內(nèi)會有密集的小型基站，可以為MEC網(wǎng)絡提供邊緣服務器和通信條件[5]。然而當移動設備附近有多個MEC服務器時，移動用戶的計算任務是否需要卸載？如何進行卸載？選擇哪個MEC服務器進行卸載？不同的卸載決策會導致移動設備的不同服務質(zhì)量。因此，如何在密集基站下對移動設備進行卸載決策制定非常重要。當大量的計算任務卸載到同一個邊緣服務器時，會造成信道堵塞，服務器負載過高，導致任務的處理時間和等待時間更長造成較差的服務質(zhì)量。因此我們在考慮卸載決策的制定時，不可簡單將計算任務卸載到距移動設備較近的邊緣服務器，需要充分考慮移動設備、邊緣服務器計算能力、信道帶寬大小等。

1 相關工作

考慮MEC網(wǎng)絡單邊緣服務器。對于單個移動用戶的MEC網(wǎng)絡，文獻[6]建立了以分時傳輸和截止時間為約束條件的優(yōu)化問題，最小化系統(tǒng)總能耗，使用塊坐標下降法求解優(yōu)化問題。文獻[7]聯(lián)合優(yōu)化了無線電和計算資源的分配，最小化用戶的能量消耗。對于具有多個移動用戶的MEC網(wǎng)絡，文獻[8]針對資源受限的MEC卸載問題，聯(lián)合時延、能耗及卸載費用建立卸載效益模型，提出一種基于遺傳算法優(yōu)化的卸載決策與計算資源分配方法對其進行求解。文獻[9]提出了一種基于分布式深度學習的卸載算法，可以有效地為該MEC網(wǎng)絡提供幾乎最優(yōu)的卸載決策。文獻[10]研究了具有能量收集功能的多用戶MEC系統(tǒng)中的能耗問題，將電池隊列穩(wěn)定性和服務質(zhì)量約束下的功耗最小化問題表示為隨機優(yōu)化程序，使用李雅普諾夫優(yōu)化方法解決穩(wěn)定性約束問題。

考慮到具有多個邊緣服務器的MEC網(wǎng)絡。文獻[11]為提高移動邊緣計算任務卸載方案性能，構(gòu)建云、邊、端三層MEC網(wǎng)絡架構(gòu)，提出一種基于二進制粒子群優(yōu)化算法的任務卸載策略。文獻[12]考慮了具有多個邊緣服務器的MEC系統(tǒng)，并提出了兩種方法，基于線性松弛和基于半定義松弛的方法來最小化總?cè)蝿盏膱?zhí)行延遲和用戶的能量消耗。文獻[13]還考慮了多個邊緣服務器的情況，得到了服務器之間的最優(yōu)計算分布。

我們根據(jù)表1中的任務、用戶和服務器的數(shù)量對這些相關工作進行了分類。

表1 移動邊緣計算中計算卸載的相關工作

上述研究部分考慮的是單邊緣服務器對行單一任務卸載的情況，部分考慮了多邊緣服務器對多用戶進行多任務或單任務卸載的情況，但是都沒有考慮到基站重復區(qū)域下用戶的邊緣計算服務器選擇問題以及多用戶多任務的卸載問題。本文針對多基站、多用戶、多任務場景，提出了用戶基站選擇、卸載決策聯(lián)合優(yōu)化算法。針對該場景下的用戶基站選擇，本文采用基于博弈論的匹配算法，在得到用戶接入的基站以及卸載問題的優(yōu)化目標后，采用基于深度強化學習的雙延遲深度確定性策略梯度(twin delayed deep deterministic policy gradient，TD3)算法對其求解。仿真結(jié)果表明本文所提出的與匹配博弈論結(jié)合的雙延遲深度確定性策略梯度(game theory-twin delayed deep deterministic policy gradient，GT-TD3)算法能有效降低用戶進行任務卸載時的能耗及時延。

2 系統(tǒng)模型

如圖1所示，我們考慮由邊緣服務器(基站)K，移動用戶N組成的MEC網(wǎng)絡。我們假設每個移動用戶有獨立的任務M，其中每個任務可以由移動用戶進行本地計算，或者卸載到邊緣服務器處理。我們將移動用戶的集合表示為N={1，2，3，…，N}， 任務集合為M={1，2，3，…，M}， 邊緣服務器集合為K={1，2，3，…，K}。

圖1 系統(tǒng)模型

卸載決策變量αnm∈{0，1} 表示用戶N是否決定卸載其中任務M，αnm=1表示用戶N決定將其任務M卸載至邊緣服務器，αnm=0表示用戶N中的任務M只能在本地終端進行處理。用戶N將任務M進行卸載時需要在基站K中選擇一個作為其任務處理基站，定義K=(k1，k2，…，kn×m) 為用戶需要卸載時的最佳服務器列表。

假如用戶N選擇將任務M進行卸載處理，則其接入基站k的數(shù)據(jù)傳輸速率表示為

(1)

式中：移動用戶向基站k發(fā)送計算任務數(shù)據(jù)時的高斯白噪聲為σ2；移動用戶與其連接的基站k之間的信道帶寬為Bk；移動用戶向基站k傳輸計算任務數(shù)據(jù)時的功率為Pnk；通信信道增益為hnk。

2.1 計算模型

(1)本地計算

(2)

(3)

本地計算總花費表示為

(4)

其中，λ1和λ2表示為完成用戶N任務M的時延和能耗成本的權重。任務計算過程中權重保持不變，0≤λ1≤1、 0≤λ2≤1、λ1+λ2=1。

(2)卸載計算

移動用戶N選擇將計算任務M進行卸載處理，則所消耗時間分為3部分：計算任務M上傳時間、MEC服務器處理任務M時間、處理結(jié)果回傳到移動用戶時間。通常情況處理結(jié)果遠小于計算任務上傳大小，所以忽略第三步所耗時間。

根據(jù)上述步驟，卸載計算第一步所需的時間是傳輸時延

(5)

完成第一步的能耗為

(6)

對于卸載計算的第二步所需時間為MEC服務器的計算任務M的時延

(7)

其中，fnmk是邊緣計算服務器為計算任務M所分配的計算資源。

(8)

根據(jù)式(5)～式(8)用戶N將其任務M進行卸載計算所需的時延和能耗分別為

(9)

(10)

結(jié)合時延和能耗公式可以得出卸載計算的總花費為

(11)

最后可以得出MEC系統(tǒng)計算任務M的總代價為

(12)

2.2 優(yōu)化問題

將MEC系統(tǒng)的卸載決策向量和資源分配向量結(jié)合得到一個優(yōu)化問題。優(yōu)化目標是最小化所有任務的總延遲以及執(zhí)行這些任務的總能耗。該優(yōu)化問題如下

(13)

在求解這個優(yōu)化問題之前，我們首先需要計算出用戶與基站的最佳匹配關系即用戶最佳卸載服務器策略K=(k1，k2，…，kn×m) 將其代入到優(yōu)化問題(13)中，這樣可以將該優(yōu)化問題改寫為

(14)

其中，A={α11…，α1M，α2M，…，αNM} 為卸載決策向量，F(xiàn)=(f1，f2，…，fN) 為邊緣計算服務器的資源分配向量。約束C1表示無論是通過本地計算還是卸載計算處理其計算任務，計算時間都不可以超過最大可容忍時延；約束C2表示計算任務只能在本地計算或者卸載到服務器進行計算；約束C3表示分配給處理每個任務的計算資源都是非負的；約束C4表示分配到所有任務的總體計算資源小于所有MEC服務器的計算資源之和。P定義為所有服務器的計算資源之和。

3 基于博弈論的用戶與服務器匹配策略

在MEC系統(tǒng)中移動用戶往往會選擇距離較近的邊緣計算服務器進行卸載，但是這種情況會使邊緣計算服務器群中一部分服務器負載較高，另一部分服務器空載，這樣會降低移動用戶的服務質(zhì)量。為了讓系統(tǒng)的總花費在約束條件下達到最小，我們需要讓移動用戶與基站之間達到最佳的匹配。

匹配博弈論是一種非常有效的方法，可以讓兩個參與者在某種條件下達成有利于雙方的策略。移動用戶N和邊緣服務器K往往會在有利于自身條件的情況下選擇用戶任務或服務器進行任務卸載，應用匹配博弈論可以使雙方在某些限制條件下達到雙贏，找到對移動用戶及邊緣服務器都有利的匹配策略[14]。在本文的MEC網(wǎng)絡系統(tǒng)中，移動用戶只可選擇一個服務器進行卸載，邊緣服務器可以接收多個用戶的卸載請求。定義移動用戶n與邊緣服務器k滿足以下條件

(1)ψ(n)∈Kn
(2)ψ(k)∈N
(3)ψ(n)≤1
(4)k∈ψ(n)?n∈ψ(k)

(15)

條件(1)表示移動用戶n所連接的服務器屬于邊緣計算服務器Kn之一；條件(2)表示連接到服務器k的用戶n必須是所有移動用戶N中的某一位；條件(3)表示移動用戶與服務器必須保證一對一連接；條件(4)表示移動用戶可以選擇邊緣服務器同樣邊緣服務器也可以選擇用戶建立連接。

在移動用戶與移動邊緣計算服務器進行匹配時需要考慮到移動用戶和服務器自身的偏好因素，為了達到最佳匹配需要根據(jù)各自偏好因素進行匹配。

移動用戶效用函數(shù)：移動用戶在多個服務器中選擇卸載時，會綜合自身情況比如用戶與基站之間的距離、信道帶寬、環(huán)境中噪聲干擾等。用戶會首先選擇信道帶寬較高、干擾較少，傳輸速率相對最快的服務器，這樣可以降低卸載計算中第一步的時延

(16)

邊緣計算服務器效用函數(shù)：移動用戶與邊緣計算服務器的選擇是雙向的。服務器在選擇用戶時，為了有效降低系統(tǒng)的總花費，會選擇卸載任務較小的用戶。這樣可以降低服務器處理任務的時間，并且可以降低后續(xù)卸載任務的等待時間

(17)

多基站博弈算法具體描述如下：

多基站博弈算法具體實現(xiàn)步驟見表2。

4 基于深度強化學習的卸載策略優(yōu)化算法

由于優(yōu)化變量之間的耦合關系，必須將原始問題分解為子問題，然后利用一些替代的凹面搜索算法來解決這些問題。然而，由于子問題之間的交替處理，導致解決時間過長，隨著MEC服務器服務區(qū)域下的用戶數(shù)量和任務數(shù)量的增加，求解時間將進一步增加。因此，我們將上述問題建模為馬爾可夫決策過程(Markov decision process，MDP)，然后采用深度強化學習(deep reinforcement lear-ning，DRL)方法進行求解。DRL體系結(jié)構(gòu)由代理和環(huán)境相互交互組成。該代理由安裝在每個MEC服務器上的控制器實現(xiàn)，并且控制器之外的所有內(nèi)容都被視為環(huán)境。通過學習最佳策略(稱為將環(huán)境狀態(tài)映射到資源分配決策的資源分配策略)以最大化累積的總獎勵，可以直接解決上述問題。

本文建模了多用戶多任務多服務器移動邊緣計算系統(tǒng)中任務卸載、服務器資源分配問題，目標是最大化用戶對服務的體驗質(zhì)量，最小化移動用戶成本。由于這是一個混合整數(shù)非線性規(guī)劃問題，為了求解這個問題，本節(jié)提出一個基于TD3算法的多基站多用戶卸載算法，最小化移動用戶總花費。

TD3算法是一種面向連續(xù)動作空間基于Actor-Critic架構(gòu)的深度強化學習算法[15]，在深度確定性策略梯度(deep deterministic policy gradient，DDPG)算法基礎上，對policy網(wǎng)絡和value網(wǎng)絡進行改進，優(yōu)化了Q-Value的過高估計問題。算法由Critic網(wǎng)絡和Actor網(wǎng)絡組成。TD3算法框架如圖2所示。

圖2 TD3算法框架

TD3算法中定義四元組 (S，A，rt，γ)， 把連續(xù)的時間分為離散的多個時刻t，每個狀態(tài)s都儲存在狀態(tài)空間集合S中，每個動作都儲存在動作空間集合A中，rt表示當前時刻的獎勵。每個時刻采用π策略的智能體都會根據(jù)狀態(tài)s選擇相應的動作a，然后與環(huán)境交互，得到這一步的收益r，以及下一步的狀態(tài)s′。總回報被定義為收益的折扣總和

(18)

γ∈(0，1) 是一個用于確定短期獎勵優(yōu)先級的折扣因子。

考慮到必須處理連續(xù)的本地執(zhí)行權和卸載傳輸權，因此采用確定性策略，將動作-狀態(tài)值函數(shù)的Bellman方程寫為

Qπ(s，a)=E[r(s，a)+γQπ(s′.μ(s′))]

(19)

為了最大化長期預期的折價報酬，采用相同的時差方法以直接從原始經(jīng)驗中學習，我們可以在每個時間步長t處更新狀態(tài)-作用函數(shù)

Qπ(s′，a′)=Qπ(s，a)+α(r(s，a)+γQπ(s′，a′)-Qπ(s，a))

(20)

式中：r(s，a)+γQπ(s′，a′)-Qπ(s，a) 表示時間差誤差，0<α<1表示學習率。

TD3算法使用單獨的DNN網(wǎng)絡來分別近似Critic網(wǎng)絡的估值函數(shù)Qθ1，Qθ2和Actor網(wǎng)絡中的策略函數(shù)πφ。

為了避免估值函數(shù)對Q值的過高估計，選擇兩個估值函數(shù)中較小的作為估計值

(21)

在計算Q值時，給Action目標網(wǎng)絡加入一個小的隨機噪音ε，并采取截斷來避免其過多的偏離原始值，經(jīng)過多個采樣后這些噪音會取得近似的平均，在加入噪音后，對干擾因素的抵抗力更強，Critic就能給出更高的Q值，從而讓策略輸出的更加穩(wěn)定平滑

(22)

(23)

在Critic網(wǎng)絡中，使用時差誤差法更新參數(shù)θ其損失函數(shù)定義為

L(θ)=argminθN-1∑(y-Qθ(s，a))2

(24)

最小化L(θQ) 對Critic網(wǎng)絡進行更新。Q(s，a) 代表在s狀態(tài)下執(zhí)行動作a得到的最大未來回報。r(s，a) 是在s狀態(tài)下執(zhí)行動作a得到的環(huán)境所給的現(xiàn)實獎勵。Q(s′，π(s′)|θ) 表示在s狀態(tài)下執(zhí)行動作a到達下一狀態(tài)s′后，繼續(xù)執(zhí)行下一動作π(s′)，得到的下一個狀態(tài)s′的最大未來回報。y表示在s狀態(tài)下執(zhí)行動作a后，得到的最大未來回報。

將優(yōu)化問題中各項參數(shù)轉(zhuǎn)化為馬爾可夫決策過程的三元組 (S，A，R)。S={dnm，cnm，fnmk，P}，A={α11…，α1M，α2M，…，αNM，f1，f2，…，fN} 分別表示狀態(tài)空間和動作空間。優(yōu)化問題是求解總成本最小化而強化學習目標是最大化獎勵，所以獎勵函數(shù)R為系統(tǒng)成本加權和的相反數(shù)R=-Z。

GT-TD3算法具體步驟見表3。

表3 GT-TD3算法執(zhí)行流程

5 仿真實驗分析

采用python仿真平臺對本文所提出的算法進行仿真分析驗證?？紤]到多用戶多基站的移動邊緣計算場景，所設環(huán)境中用戶隨機分布信道建模采用l-α， 其中l(wèi)為用戶到基站的距離，α為路徑損耗因子，此處取α=3[16]。優(yōu)化目標中的能耗和時延權重為λ1=λ2=0.5。 MEC服務器的計算能力為10(GHz)，MEC服務器計算1 bit數(shù)據(jù)所需周期數(shù)為200/bit；假設移動用戶設備的計算能力相同，移動用戶設備的計算能力為1(GHz)，計算1 bit數(shù)據(jù)所需的CPU周期數(shù)為1000/bit。其它仿真參數(shù)設置見表4。

表4 參數(shù)設置

本文所求系統(tǒng)開銷為用戶處理任務的時延和能耗的加權和，因此開銷無量綱。為驗證算法優(yōu)劣性，將本文所提出算法與TD3算法、LOCAL(用戶在本地盡可能多貪婪地執(zhí)行任務)算法、OFFLAND(用戶盡可能多貪婪地將任務卸載執(zhí)行)算法和DDPG算法在不同場景下進行比較。

圖3是在移動設備用戶數(shù)量不斷增加時，LOCAL算法、OFFLAND算法、TD3算法和本文所提出的GT-TD3算法的性能比較。系統(tǒng)中基站內(nèi)的MEC服務器計算能力為10 GHz，可接入基站數(shù)量為15，用戶數(shù)量從10增加到70。可以看出隨著用戶數(shù)量的增加，系統(tǒng)的總花費呈現(xiàn)上升趨勢，在相同用戶數(shù)量的情況下，本文所提出的GT-TD3算法的系統(tǒng)總花費最小。在用戶數(shù)量較少時，OFFLAND算法的總花費明顯低于LOCAL算法，相較于DDPG算法略高。當用戶數(shù)量逐漸上升時，OFFLAND算法總花費迅速升高，這表明在用戶數(shù)量較多的情況下，MEC服務器無法在最大可允許時延條件下完成任務，無線信道也會變得十分擁擠，僅用MEC服務器無法提供有效的計算卸載服務，所以選擇合適的卸載決策十分重要。

圖3 系統(tǒng)總花費與用戶數(shù)量的關系

圖4是在移動用戶可連接基站數(shù)量不斷增加時，LOCAL算法、OFFLAND算法、TD3算法和本文所提出的GT-TD3算法的性能比較。系統(tǒng)中基站內(nèi)的MEC服務器計算能力為10 GHz，移動設備用戶數(shù)量為30，基站數(shù)量從5增加到25。可以看出在基站數(shù)量為5時，TD3算法和本文所提出的GT-TD3算法的總花費基本相近，OFFLAND算法和LOCAL算法所花費較大，其中LOCAL算法在基站數(shù)量不斷上升時系統(tǒng)總花費不變。這是因為貪婪本地卸載計算時不將任務卸載到MEC服務器，所以無論可接入基站數(shù)量如何變化其系統(tǒng)總花費保持不變。隨著可接入基站數(shù)量的不斷增加，OFFLAN算法和TD3算法和GT-TD3算法的系統(tǒng)總花費呈下降趨勢，這是因為更多的基站和服務器選擇使得用戶的卸載任務可進行卸載處理的最佳服務器的選擇更好，使得系統(tǒng)的總花費不斷減小。

圖4 系統(tǒng)總花費與基站數(shù)量的關系

圖5是在移動設備用戶所需要處理的任務數(shù)量不斷增加時，LOCAL算法、OFFLAND算法、TD3算法和本文所提出的GT-TD3算法的性能比較。系統(tǒng)中基站內(nèi)的MEC服務器計算能力為10 GHz，可接入基站數(shù)量為15，移動設備用戶數(shù)量為10，用戶所需要處理的任務數(shù)量從10增加到50?？梢钥闯鲭S著任務數(shù)量的增加，系統(tǒng)的總花費也在逐步上升。這是因為在移動設備用戶數(shù)量和MEC服務器計算能力保持不變時，隨著任務數(shù)量的增加，無線信道干擾增大，信道傳輸效率下降，這樣不可避免地導致較長的傳輸時間和較高的能耗，系統(tǒng)總花費隨之升高。本文所提出的GT-TD3算法在4種算法中的系統(tǒng)總花費為最小，這是因為本文提出的算法可以在用戶所有可接入的基站中預先選擇出最佳基站，每個用戶的任務都最佳分配給基站中的MEC服務器，不會造成用戶的任務在需要進行卸載處理時還需等待基站中MEC服務器處理上一個用戶的任務，這樣可以很好地降低系統(tǒng)的總花費。

圖5 系統(tǒng)總花費與任務數(shù)量的關系

圖6是在移動設備用戶所需要處理的計算任務大小不斷增加時，LOCAL算法、OFFLAND算法、TD3算法和本文所提出的GT-TD3算法的性能比較。系統(tǒng)中基站內(nèi)的MEC服務器計算能力為10 GHz，可接入基站數(shù)量為15，移動設備用戶數(shù)量為10，用戶所需要處理的任務數(shù)為15，任務的大小從300增加到1500?？梢钥闯鲭S著用戶發(fā)送任務的數(shù)據(jù)逐漸變大時，系統(tǒng)處理這些任務的總花費呈現(xiàn)全體上升趨勢。由于任務的數(shù)據(jù)變大，無線信道接收數(shù)據(jù)，系統(tǒng)處理數(shù)據(jù)需要花費更多的能量和時間，從而導致系統(tǒng)總花費升高。其中LOCAL算法在任務較大時所需的總花費明顯高于另外3種算法，這是由于移動設備本身的處理能力時有限的在任務大小一直增加時其所需要的總花費相對于其它算法上升地更快。這表明，在任務數(shù)據(jù)量較大時，對任務進行卸載處理收益較高。

圖6 系統(tǒng)總花費與用戶任務數(shù)據(jù)大小的關系

6 結(jié)束語

隨著5G超密集基站的部署，移動用戶在進行卸載計算時面臨基站選擇問題。針對多用戶、多基站場景下移動用戶的計算卸載及資源分配問題，本文提出一種與匹配博弈論相結(jié)合的雙延遲深度確定性策略梯度算法GT-TD3。以最小化MEC系統(tǒng)總代價為優(yōu)化目標，首先運用多基站博弈算法解決用戶與基站互相匹配問題，然后使用TD3算法對優(yōu)化問題進行求解，得到最優(yōu)的卸載策略。仿真結(jié)果表明本文所提出的算法相較于4種對比算法可以有效減小MEC系統(tǒng)總花費。并且隨著MEC系統(tǒng)中可接入基站數(shù)量增多，本文算法的總花費會逐漸減小。

深度強化學習算法由于深度神經(jīng)網(wǎng)絡導致所占內(nèi)存空間較大，如何減小其所占內(nèi)存空間，加速算法迭代，使其可以更加方便地在MEC服務器中進行部署，這將是下一步的研究重點。