基于DDPG 的邊緣計算任務卸載和服務緩存算法

陳清林，鄺祝芳

（中南林業科技大學 計算機與信息工程學院，長沙 410018）

0 概述

移動互聯網中各種數據流量的爆發式增長和用戶設備使用率的不斷增高，極大地推動了無線通信和移動網絡技術的發展［1］。此外，隨著物聯網、人工智能、第五代移動通信（5G）等技術的普及，也使移動用戶對數據處理速率和服務質量（Quality of Service，QoS）的要求不斷提高［2］。目前，移動邊緣計算（Mobile Edge Computing，MEC）是產業界和學術界研究的重點［3］，旨在解決價值與應用之間的矛盾，并且應用場景十分豐富［4］，如智能交通［5］、車聯網等。MEC 是無線接入網中的一種新模式，其通過部署高性能的服務器來提高移動網絡邊緣的計算能力［6］。MEC 服務器密集分布在移動用戶附近，用戶設備可以通過無線鏈接將計算任務卸載到MEC 服務器［7］。計算卸載可以幫助移動用戶顯著降低應用程序的體驗延遲［8］。將移動邊緣服務器部署在離數據源較近的范圍內，可以避免數據上傳到較遠的云服務器，從而減少數據往返的等待時延和消耗成本［9］。

本文針對單用戶MEC 系統，設計基于深度確定性策略梯度（Deep Deterministic Policy Gradient，DDPG）算法的數據緩存優化機制，對服務緩存放置、計算卸載決策和系統資源分配（即移動用戶的CPU 處理頻率和傳輸功率）進行聯合優化。

1 相關研究

隨著各種移動應用程序高度普及［10］，設備以非常快的速度產生大量數據，這給移動核心網絡和回程鏈路帶來了很大的負擔。移動邊緣緩存使數據能夠在MEC服務器中進行存儲，是緩解這一問題的有效方法［11-12］。與此同時，緩存在移動數據流量激增的情況下也表現出極大的優勢［13］。

針對單用戶MEC 系統，目前已有很多優化方法。文獻［14］研究了任務卸載調度和傳輸功率分配的聯合問題。文獻［15］以最小化超低功耗單天線設備的能耗為目標，優化了用于能量收集、信息解碼和本地計算的時隙，以及卸載所需的時隙和功率。文獻［16］考慮到功率受限和不可預測的任務，以單用戶處理能力最大化為目標的功率分配問題對MEC 系統進行研究，提出一種二分搜索算法。文獻［17］設計一種迭代啟發式的MEC 資源分配算法實現動態卸載決策。然而上述研究沒有考慮數據緩存，單用戶MEC 系統中的聯合任務卸載決策、數據緩存和資源分配仍然是一個有待解決的問題。

針對多用戶MEC 場景也出現了很多優化方法。文獻［18］考慮具有多個用戶和單個MEC 服務器的場景，提出NOMA-MEC 系統，通過使用強化學習中的深度Q 網絡（Deep Q-Network，DQN）算法，在事先未知其他用戶動作的情況下選擇同時卸載的用戶，得到最優組合狀態，使系統卸載延遲最小。文獻［19］研究了多用戶MEC 系統中的資源分配問題，利用回歸算法求解通信資源（子載波）的分配問題并合理分配通信和計算資源，在延遲約束下達到了系統能量消耗最小的目標。文獻［20］利用頻譜效率較優的非正交多路訪問（Non-Othogonal MultipleAccess，NOMA）技術共同優化計算卸載決策、通信和計算資源分配，提高了MEC 的訪問能力，并使所有用戶的計算成本最小化。文獻［21］針對NOMA 用戶研究不同上傳時延與共信道干擾之間的相互作用，提出一種計算卸載方案，通過對卸載決策和資源分配的聯合優化降低了用戶的平均卸載延遲。文獻［22］針對如何在滿足時延約束下縮短MEC 計算任務的完成時間并降低終端能耗的問題，提出一個卸載決策與資源分配聯合優化的方法。文獻［23］提出一種基于強化學習的狀態-動作-獎賞-狀態-動作（RL-SARSA）算法解決邊緣服務器的資源管理問題，并通過優化卸載決策來最小化系統成本（包括能量消耗和計算時延）。文獻［24］研究了MEC 中任務卸載決策、卸載調度和功率分配的聯合問題，設計一種節能、低延遲的MEC 卸載調度機制，實現了最小化系統能耗同時降低系統時延的目標。文獻［25］研究MEC 中的卸載策略與功率分配問題，采用二分搜索法求解傳輸功率，利用非合作博弈論解決多用戶卸載決策問題。

以上研究主要考慮MEC 系統卸載和資源分配場景，以最小化能源消耗或延遲為目標，但沒有考慮任務數據緩存在系統中的情況。在邊緣計算系統場景下聯合卸載、緩存決策和傳輸能力以及CPU 頻率分配是一個具有挑戰性的問題。

近年來，邊緣緩存受到較多關注。文獻［26］將緩存問題視為一個優化問題進行建模，探討不同算法的優化性能和復雜度。文獻［27］設計了一個以信息為中心的異構網絡框架，旨在支持內容緩存和計算。此外，由于整個系統的虛擬化，通信、計算和高速緩存資源都可以在與不同虛擬服務提供者關聯的所有用戶之間共享。文獻［28］引入一種新的基于體驗質量（Quality of Experience，QoE）的效用優化方法來解決MEC 系統中聯合服務緩存和任務卸載的問題，反映了用戶對服務延遲的感知和用戶為分配的計算資源所支付的成本之間的權衡，但未深入研究單用戶MEC 系統中任務卸載、數據緩存和資源分配的聯合問題。本文設計一種基于DDPG 的數據緩存優化機制，以期優化用戶對服務延遲的體驗質量和用戶使用計算資源所節約的成本。

2 MEC 任務卸載模型

2.1 系統模型

本文考慮單用戶多任務MEC 系統，如圖1所示，其中包含1 個無線無線接入點（Access Point，AP）和1 個移動用戶（Mobile User，MU），AP配備1個MEC服務器，MU 有M個計算任務。在此系統中，每個任務由N個程序中的1 個處理，如果1 個任務需要由第j個程序處理，則將其稱為類型j任務，j?Γ={1，2，…，N}。以ui，j=1表示第i個任務由第j個程序執行，否則ui，j=0。以φi?Γ表示第i個任務的類型。MEC 服務器具有計算資源F和緩存容量R，緩存在MEC 中的計算結果可以讓其他需要的任務共享。從用戶卸載的計算任務通常與特定的服務相關聯，這些服務需要緩存在MEC 中以實現任務的執行。在每個資源有限的MEC 節點上緩存哪些服務和執行哪些任務的決策，對于最大限度地提高卸載效率至關重要。此外，體驗質量和計算資源的成本效益也是驅動卸載決策的關鍵因素。為有效利用有限的計算資源，提升用戶對服務的體驗質量，本文研究基于QoE 的服務緩存和任務卸載聯合優化問題，實現用戶對服務延遲的體驗質量與用戶使用計算資源所節約的成本之間的最優權衡。

圖1 MEC 系統模型Fig.1 MEC system model

在圖1 所示系統中，第i個任務輸入和輸出數據的大小分別表示為Ii和Oi。由于這M個任務是相互依賴的，因此第i個任務的輸入需要第i－1 個任務的輸出，則Ii=Oi-1，i=1，2，…，M+1。Li為計算任務i所需的CPU 計算周期數。任務模型如圖2 所示。

圖2 任務模型Fig.2 Task model

假設MU通過上傳自己的程序數據（如通過C/C++代碼生成程序），在MEC 平臺上運行自己的定制程序，第j個程序的數據大小表示為sj。邊緣服務器接收到程序數據后，生成相應的程序（如二進制可執行文件.exe），用于處理以后卸載的任務數據，用rj表示生成的第j個程序的大小，rj通常比sj大得多。Dj為第j個程序在邊緣服務器中的生成時間。

邊緣服務器與MU 之間的數據傳輸包括上傳程序和（或）任務數據以及下載計算結果。第i個任務輸入數據的上行傳輸速率和所需程序數據的上行傳輸速率分別如式（1）和式（2）所示：

其 中：gi表示信道功率增益；di，c表示AP 與用戶之間的距離；Gi=gi表示通道增益；δ表示通道損失系數；B表示可用的頻譜帶寬表示第i個任務卸載任務數據的傳輸功率表示第i個任務卸載程序數據的傳輸功率；σ2表示噪聲功率。

每個任務都可以在本地或邊緣服務器上執行計算。令ai?{0，1}表示卸載決策，ai=0 表示第i個任務在本地執行，ai=1 表示第i個任務在邊緣服務器上執行。

假設MU 只能上傳用于處理當前在邊緣執行的任務的程序數據，即：如果ui，j=1 和ai=1，則MU 在邊緣執行第i個任務時只能上傳第j個程序數據。xi，j表示緩存決策，xi，j=1 表示執行第i個任務的第j個程序數據緩存到邊緣服務器上，但只有在以下2 個條件中至少有1 個成立時才能實現，否則xi，j=0：

1）第j個程序在上個任務執行之前已經在緩存中，即xi-1，j=1。

2）第j個程序數據在上個任務執行時間內上傳到邊緣服務器，這需要ui-1，j=1 和ai-1=1，或者等價于ai-1ui-1，j=1，因此，緩存決策的約束條件如式（3）所示：

此外，在整個系統任務的處理過程中，需要滿足式（4）所示的緩存容量約束：

2.2 計算模型

2.2.1 本地計算

假設MU 擁有處理其任務所需的所有程序，如預安裝在本地磁盤上，這樣本地處理任務i所花費的時間只包括計算時間。第i個任務在本地計算所消耗的時間和能量如式（5）所示：

其中：為本地CPU 頻率為本地服務器分配為任務的最大計算頻率；k為計算能效參數，k>0；α為指數參數，α≥2。

若第i?1 個任務卸載到MEC 計算，則第i個任務的輸入數據從MEC 下載到MU 進行本地計算的傳輸時間如式（6）所示：

因此，第i個任務在本地執行的總時延如式（7）所示：

2.2.2 卸載計算

每個任務可以在MU 本地計算，也可以卸載到邊緣服務器上進行遠程執行。當任務i在邊緣上執行時，計算時間包括任務計算時間和程序生成時間兩部分。

任務計算時間如式（8）所示：

如果計算任務所需程序沒有在緩存中，則服務器可能需要生成一個新的程序（如程序編譯和加載函數庫）。

程序生成時間wi如式（9）所示：

其中：Dj為第j個程序生成時間。

第i個任務卸載程序數據上傳所消耗的時間和能量分別如式（10）和式（11）所示：

能量函數對于時間是凸的。因此，第i個任務卸載任務數據所花費的時間和能量分別如式（12）和式（13）所示：

綜上所述，第i個任務卸載執行的總延遲和MU所消耗的能量分別如式（14）和式（15）所示：

本文研究的目標是優化用戶的QoE 和用戶使用計算資源所節約的成本，其中計算時間和能耗由本地執行和卸載執行兩部分組成，第i個任務的執行時間和總能耗如式（16）和式（17）所示：

通過使用具有2 個預定義閾值Tmin和Tmax的QoE映射函數，將服務延遲映射到一個平均意見評分量表中，以優秀、良好、合格、差、不滿意或阻塞評價，如式（18）所示：

當任務i的執行時間小于閾值Tmin，屬于極佳的完成時間，則此時的服務可以評為滿分為1 分；當任務i的執行時間處于閾值Tmin和Tmax之間，此時的完成時間在可接受的范圍內，服務可以評分為越接近Tmax，表明所需的完成時間越久，此時的評分越低；當任務i的執行時間大于閾值Tmax，屬于不可接受的完成時間，此時的服務評得分為Wb。

定義一個可選點Tfair?(Tmin，Tmax)，從這個點開始，當服務質量下降到較差程度時，用戶就會對服務感到失望。這些閾值可以由服務提供者根據每個服務的需求在其清單中確定，用戶體驗質量映射函數如圖3 所示。

圖3 用戶體驗質量映射函數Fig.3 User experience quality mapping function

除了用戶的QoE，本文模型還考慮了使用計算資源節約的成本。基本上，更小的服務延遲是以更高的計算資源使用成本為代價的。用ε表示邊緣服務器計算任務i的單位成本，設Hi為任務i使用計算資源的預算，移動邊緣服務器分配給任務i的計算資源，必須滿足式（19）所示的預算約束：

邊緣服務器分配給任務i的計算資源成本如式（20）所示，任務i節約的預算成本如式（21）所示，則任務i的效用函數如式（22）所示：

上述模型的目標是最大化用戶的總效用以及聯合優化服務緩存、任務卸載和資源分配問題，是一個混合整數非線性規劃問題，如式（23）所示：

其中：式（23b）表示卸載和緩存決策分別為0～1 整數優化變量；式（23c）表示緩存的計算結果不能超過MEC 服務器的緩存容量；式（23d）表示用戶i分配給任務j的數據傳輸功率不能超過最大傳輸功率；式（23e）表示用戶分配給任務j的CPU 頻率不能超過最大本地CPU 頻率；式（23f）表示任務i執行的能量消耗不能超過最大能源消耗限制。

3 基于DDPG 的策略優化和資源分配算法

本文對單用戶多任務MEC 系統中聯合任務卸載、緩存決策和本地服務器資源分配的問題進行建模，目標是最大化用戶對服務的體驗質量和用戶使用計算資源所節約的成本。為求解這個混合整數非線性規劃問題，提出基于DDPG 的優化算法DADDPG，最大程度地優化用戶的體驗質量和節約的成本。算法框架如圖4所示。

圖4 DADDPG 算法框架Fig.4 Framework of DADDPG algorithm

深度強化學習方法求解問題的關鍵要素為狀態、動作和獎勵，具體到本節的模型定義如下：

3）系統Reward。在本文研究的MEC 系統中，優化的目標是最大化用戶的總效用，在每一步，智能體在執行一個動作A之后，都會在這個動作對應的狀態S下獲得獎勵值R。一般來說，獎勵函數應與目標函數相關。因此，本文的優化目標是獲得最大的用戶總效用，而深度學習的目標是獲得最大的獎勵回報，獎勵值應與系統總效用的大小呈正相關。因此，將獎勵定義為目標值，即R=Qi。

如圖4 所示，DADDPG 算法由Actor 部分和Critic 部分組成，Actor 部分的角色是根據所觀察到的環境狀態定義參數化的策略并生成行動，而Critic部分則負責通過處理從環境中獲得的獎勵來評估和批評當前的策略。簡單來說，Actor 負責策略網絡，進行動作選擇，Critic 負責值網絡。

Critic 使用經驗回放技術。回放內存使用(St，At，Rt，St+1)元組將任何軌跡保存為一條記錄，并使用記錄中的一個小批元組更新參數。評判過程中的損失函數定義如式（24）所示：

其中：w-為目標Q 網絡參數，與當前onlineQ 網絡相比相對固定；D為回放內存，即(St，At，Rt，St+1)～D。每次迭代時，使用固定參數的目標神經網絡計算損失函數。為了使損失函數最小化，使用梯度下降法更新參數，如式（25）所示：

策略π(S，A)表示Agent 的Action，其輸出不是單個的Action 動作，而是選擇動作的概率分布，所以，一個狀態下的所有動作概率加和應當為1。Actor 采用梯度上升法對策略進行維護和改進。設置策略π(S，A)如式（26）所示：

其中：θ為online 策略網絡參數；?(S，A)為狀態和動作的特征向量。該策略以優化性能指標為目標，通常以目標函數的形式給出：

θ的梯度可以通過偏微分法得出：

使用隨機梯度上升方法優化目標，更新采樣梯度：

DADDPG 算法具體描述如下：

4 仿真實驗

4.1 參數設置

利用python3.7 進行仿真實驗。設置1 個MEC服務器和1 個用戶的場景，該用戶有一個任務序列需要執行。設置-B=B，σ-=σ。仿真實驗中使用的初始參數如表1 所示。

表1 仿真實驗初始參數Table 1 Initial parameters of simulation experiment

4.2 實驗結果分析

選取以下3 種算法，通過仿真結果對比驗證DADDPG 算法的有效性和優越性。

1）無緩存策略的DADDPG 算法DADDPGno：每個任務可以選擇卸載執行和本地執行，但MEC 不提供緩存功能。

2）隨機選擇策略算法DARAND：每個任務隨機選擇卸載執行和本地執行，也隨機選擇緩存與不緩存相應數據到MEC。

3）無緩存隨機選擇策略算法DARANDno：每個任務隨機選擇卸載執行和本地執行，但MEC 不提供緩存功能。

圖5 展示了不同算法下總效用隨任務數的變化情況，設置目標函數的權重系數w=0.5。可以看出：隨著任務數的累加，各個算法的總效用均隨之增加，這是因為隨著任務數增多，執行任務的時間和用戶利用計算資源的成本也相應增加；本文提出的DADDPG 算法在不同的權重影響下總效用均為最大，這是因為該算法采用了雙層網絡，可以更穩定地優化變量，即卸載策略、緩存策略和本地計算頻率、本地上傳功率，可以獲得更優的目標值；DARAND算法是隨機選擇卸載策略和緩存策略，DARANDno算法是隨機選擇卸載策略，這樣獲得的目標值不是穩定的，優化性能不如本文提出的DADDPG 算法。

圖5 不同任務數對總效用的影響Fig.5 The total utility versus different numbers of tasks

圖6 展示了DADDPG 算法下總體驗質量（QoE）和為用戶節省成本的情況。通過改變權重參數，在總用戶體驗質量和為用戶節省成本之間的最佳性能權衡。正如預期，當w增加時，總用戶體驗質量的值增加，此時用戶節省的成本同步下降。可以看出：總體驗質量在0.10.7 時，總體驗質量增加比較緩慢，而總節約成本降低較快。由此可見，對于用戶來說，即使利用了更多的計算資源來減少延遲，其體驗質量也不會在超過某個閾值后得到改善。

圖6 不同權重對QoE 和節約成本的影響Fig.6 QoE and cost savings versus different weights

圖7 展示了改變平均預算時本文DADDPG 算法和3 個基線之間的總效用（w=0.5）。此實驗中比較了3 種情況下用戶總效用的變化情況：1）比較平均預算的一半/2 對各個算法的總效用的影響；2）比較平均預算對各個算法的總效用的影響；3）比較平均預算的2 倍×2 對各個算法的總效用的影響。可以看出，隨著平均預算的增加，所有算法的總效用都有所增加。其中，DARANDno 算法對所有預算值的總效用是最差的，因為用戶的體驗質量非常低，特別是那些需要低延遲VR 服務的用戶。通過共享資源和平衡在計算MEC 節點間的負載時，擁有緩存功能的DARAND 算法比沒有緩存功能的算法獲得了更高的總效用。而本文算法在沒有緩存功能的情況下通過優化服務緩存和任務卸載決策以及資源分配，獲得的總效用高于DARAND 算法。

圖7 不同預算成本對總效用的影響Fig.7 The total utility versus different weighted budgets

圖8 展示了不同權重下DADDPG 算法的訓練性能。可以看出，在3 種不同權重參數下，DADDPG 算法最終都可以收斂。當調整系數w=0.1 和w=0.9 時，累計獎勵值大于w=0.5 的情況，這是因為w=0.1 時解決方案側重總節約成本，w=0.9 時解決方案側重總體驗質量使得目標值會偏向總節約成本或者總節約成本的值，而w=0.5 時總體驗質量和總節約成本會達到平衡狀態。同時由圖8 可以看出，3 種不同權重參數下的累計獎勵值均在第510 episode 左右達到收斂狀態。

圖8 DADDPG 算法的訓練性能Fig.8 Training performance of DADDPG algorithm

5 結束語

本文基于深度確定性策略梯度算法對MEC 中服務緩存、任務卸載和資源分配進行聯合優化，提出DADDPG 算法，并通過仿真分析各變量在實驗過程中對服務質量和節約成本的影響。實驗結果表明，DADDPG 算法能夠有效地優化目標值。然而在任務卸載過程中，需要選擇任務數據卸載與存儲的MEC，而在快速移動時可能會使移動用戶在MEC 之間進行快速切換，這會導致任務中斷，進而影響用戶的QoE。因此，下一步將考慮用戶的移動性，完善MEC 系統中任務卸載和服務緩存結構。