終端直通輔助的移動邊緣計算任務動態卸載方案

李 斌，徐天成

(南京信息工程大學 計算機學院，江蘇 南京 210044)

0 引言

隨著5G、物聯網和人工智能的融合與快速發展，以及日益增長的用戶計算資源需求，利用移動邊緣計算(Mobile Edge Computing，MEC)在網絡邊緣卸載任務，已成為未來互聯網發展的重要方向[1-2]。其優勢在于能夠為網絡邊緣用戶提供近距離通信，并且有效減輕用戶設備的壓力，同時有利于與物聯網和云計算等新技術的融合應用。

為了解決用戶資源和計算能力有限的問題，提出了基于終端直通(Device-to-Device，D2D)技術的卸載模式作為MEC的一種有效增補[3]，旨在將大量的計算和存儲資源協同控制和管理起來，以完成密集型應用任務[4-6]。同時，未來物聯網、邊緣計算網絡等新網絡場景高速發展，智能設備數量和用戶需求也隨之大幅增長，如何將有限的計算、帶寬和存儲等網絡資源最大程度利用起來，并在大量的終端數據上實現自動管理，以獲得更高效的網絡傳輸性能和通信質量是實現5G應用急需解決的熱點研究問題之一。

關于D2D和MEC集成化的任務卸載方案已有相關研究[7-9]。文獻[10]提出了具有邊緣計算和D2D通信的5G蜂窩網絡節能計算卸載方案，采用Lyapunov優化技術框架解決問題。文獻[11]將用戶的卸載決策問題表述為序列博弈，為了實現納什均衡，提出了一種多用戶多目的地計算卸載方案。文獻[12]將任務調度和功率分配作為一個隨機優化問題，其研究目標是最小化協作設備在無線通信和計算方面的平均費用。通過對優化變量的解耦，提出了一種次優化算法。為了最小化單用戶多任務協作MEC網絡的時延，文獻[13]將任務分配和無線資源分配共同定義為MINLP問題。在松弛凸問題最優解的基礎上，提出了一種次優解方案。

用戶的移動性使得卸載決策高度動態。因此，如何通過考慮用戶移動性驅動的網絡狀態不確定性來設計高效的任務調度和資源分配策略，以增強分布式系統中移動用戶的任務卸載體驗，成為了一個重要的研究方向?；诖?，文獻[14]提出了一個基于連續時間馬爾可夫鏈的連接概率模型，以最小化在D2D網絡中協作任務的執行時間。目前，越來越多的學者試圖用深度強化學習(Deep Reinforcement Learning，DRL)的方法來解決這一問題，通過構建自學習能力更強的神經網絡來近似表示Q值。作為智能體的每個卸載節點學會基于與環境的交互做出計算卸載的決定。從長遠來看，通過從經驗中優化計算卸載策略，系統能耗被最小化。

本文提出了一種基于D2D通信和MEC的2層任務卸載框架。在所提框架下，用戶自低到高依次具有設備層(本地設備和D2D協作設備)和邊緣層(邊緣服務器)2個卸載層級可選。層級越高的卸載模式具有越充裕的計算資源，而將任務卸載到更高層級處理所付出的傳輸代價也更高。同時，所提框架還利用D2D協作中繼技術協助移動用戶連接更高卸載層級。為了實現動態、智能的任務卸載模式，提出了一種基于DRL的任務卸載策略。首先，對D2D輔助多任務用戶卸載數據的場景進行建模，并考慮用戶的移動性構建能耗最小化優化問題；然后，基于強化學習思想，設計了雙深度Q網絡(Double DQN,DDQN)算法對多任務卸載做出實時決策；最后，利用所提DDQN算法對本文所考慮的場景進行仿真，其優化決策的收斂性較好，并與其他基線方案進行對比，證實了本文所提方案的優越性。

1 系統模型

本文考慮一個支持D2D通信的協同MEC網絡，該系統模型由單個用戶、單個基站和M個D2D設備組成，如圖1所示。其中空閑且資源充裕的設備(如筆記本、平板電腦和手機等可以作為邊緣節點)通過與資源有限的用戶設備(User Device，UD)建立直接的D2D鏈路[15]，以促進計算卸載。假設UD有J個獨立的計算密集型任務要執行，用集合J={1,2,…,i}表示。移動用戶的任務沿著用戶的軌跡被卸載到D2D設備或基站上。在UD行走的道路上，分布著M個D2D設備，用集合M={1,2,…,m}表示。考慮一種網絡輔助架構，其中基站擁有全局網絡信息，包括關于用戶移動性和任務的細節。

圖1 系統模型Fig.1 System model

對于任務卸載，UD可以在基站的幫助下通過建立直接的D2D鏈路(使用WiFi或藍牙等技術)連接到附近的D2D設備?；究蓹z測出UD的位置，以便將其任務調度到D2D設備，使計算卸載總能耗最小化。為了簡化計算模型，UD、基站和D2D設備均只考慮裝配一根天線。

1.1 用戶移動模型

假設UD的軌跡在[0,T]可獲得，小區空間劃分為二維空間，λ(t)={x(t),y(t)}，T={1,2,…,t}表示用戶在t時隙所在的位置。由于其有限的處理能力，UD可以選擇將任務卸載到附近的D2D進行計算。λm={xm,ym}，M={1,2,…,m}表示第m個D2D的位置。

與文獻[16-17]中的類似，假設系統在一個持續時間T內工作，以精確捕獲用戶的移動性。因此，將移動軌跡劃分為時間τ相等的時間段，滿足T=nτ。記時間段的集合為N={1,2,…,n}。對于每一個選擇的n，UD在每個時隙內的位置近似不變。假設UD的移動速度相對較慢，短時間內所走的距離不會有很大的變化。記UD在時隙n∈N中的水平位置為λo(n)=λ(nτ)。根據UD在時隙n∈N中的位置，可以得到UD與第m個D2D設備之間的距離為dm(n)=‖λo(n)-λm‖。

1.2 任務卸載模型

在每個時隙，UD以一個確定概率隨機生成i個任務(i∈J)。本文用Υt來表示是否有任務請求，Υt=1表示在t時隙有一個任務請求，Υt=0表示在t時隙沒有任務請求。UD的計算任務可由TKi(ci,ai,dli)表示，其中ci表示任務卸載時本地設備需向外傳輸的數據量，ai表示處理該任務所需的機器語言指令數，dli表示執行任務的最大時延。對于時間密集型任務，每個任務必須在dli內完成，所以每個任務執行時間應該小于時隙長度τ。

(1)

(1) 本地計算模式

(2)

UD在本地計算模式下的能耗定義為：

(3)

式中，ko表示有效電容系數，它取決于UD使用的芯片結構[18]。為了現實，假設CPU頻率小于最大CPU頻率。

(2) D2D卸載模式

(4)

UD在D2D卸載模式下的上傳任務所需能耗定義為：

(5)

此時，UD在D2D卸載模式下的處理時延定義為：

(6)

UD在D2D卸載模式下的計算能耗定義為：

(7)

式中，kD表示有效電容系數，它取決于D2D使用的芯片結構。

根據式(4)～式(7)，UD在D2D卸載模式下的執行時延和能耗分別為：

(8)

(9)

(3) D2D輔助中繼卸載模式

由此，任務上傳到邊緣服務器執行所需時間定義為：

(10)

UD在D2D輔助邊緣計算模式下的上傳任務所需能耗定義為：

(11)

UD在D2D輔助邊緣計算模式下的處理時延定義為：

(12)

UD在D2D輔助邊緣計算模式下的計算能耗定義為：

(13)

式中，kBS表示有效電容系數，它取決于邊緣服務器使用的芯片結構。

根據式(10)～式(13)，UD在D2D輔助邊緣計算模式下的執行時延和能耗分別為：

(14)

(15)

2 問題描述

在這項工作中，本文的研究目標是最小化時延約束下任務執行的總能耗，包括本地執行能耗、D2D卸載能耗和卸載到基站能耗，可表示為：

(16)

為了減少卸載能耗，利用UD移動過程中不同時隙的位置信息進行任務卸載決策。故本文的研究問題形式化描述為：

(17)

式(17)給出了以任務卸載決策為優化變量的目標函數。約束C1表明用戶最多只能選擇一種模式來完成它的任務。約束C2表明任務只能全部卸載。約束C3表明分配給移動用戶的計算資源不能超過MEC服務器擁有的資源。約束C4表明如果用戶選擇3種模式中的一種來完成它的任務，其時延不能超過最大時延。約束C5表明移動用戶最多同時連接一個D2D設備。約束C6表示UD，D2D的傳輸功率和MEC服務器的計算資源分配分別是非負的?？梢姡瑑灮?17)含有多個離散的決策變量，是一個混合整數非線性規劃問題，很難快速求得最優解。本文提出了基于DRL的DDQN算法來解決此問題。

3 基于DRL的算法設計

由于在高維場景下，創建出來的Q-table會過于龐大，導致無法建立。為解決具有高維狀態空間的環境問題，DRL將深度神經網絡與強化學習的決策能力相結合，通過使用卷積神經網絡對Q-table做函數擬合。

由于本文研究的問題是移動場景下任務卸載的決策，隨著用戶的不斷移動，環境也開始發生動態變化。傳統的方案使用Q-learning算法來探索未知環境，移動用戶通過嘗試不同的行動，從反饋中學習，然后強化動作，直到動作提供最佳結果。由于Q-learning算法通過計算每個動作的Q值進行決策，所以會在某些條件下高估動作值。因此，本文提出使用DDQN方案是一種有效的改進，通過選擇預測網絡中最大Q值對應的動作來計算目標Q值，從而解決過估計的問題。

3.1 基于DDQN的計算卸載

為了使用DDQN算法，先將計算卸載問題轉化為一個優化問題。通過優化任務卸載，實現了系統能耗的最小化。由于優化問題是馬爾可夫問題，先將其建模為MDP問題。

(1) 狀態空間:S={x,y}

UD在第t個時隙內的狀態為其自身的位置。其中，xt為UD的橫坐標，yt為UD的縱坐標。

(2) 動作空間:A={a}

(3) 獎勵函數

獎勵是對從先前動作中獲得的利益的評估。在這個問題中，優化目標是使系統的能耗最小，而強化學習的目標是獲得最大回報。如果借助強化學習來解決問題，就必須將獎勵函數與優化目標函數關聯起來。因此，將獎勵函數定義為優化目標函數的負函數。

(18)

對于DDQN，不是在目標網絡里面直接搜索最大Q值的動作，而是先在預測網絡中找出最大Q值對應的動作，即：

(19)

然后利用選取出來的動作在目標網絡里面計算目標Q值：

(20)

式中，γ為折扣因子。

綜合定義為：

(21)

損失函數為：

(22)

式中，E[·]為隨機變量期望。

3.2 基于DDQN的能耗最小化算法

本文所提DDQN算法的執行架構如圖2所示。

圖2 DDQN算法執行架構Fig.2 DDQN algorithm execution architecture

具體實現過程如下：首先，初始化預測網絡、目標網絡和回放空間(算法1中的第1行)。其次，輸入UD初始位置。接下來，利用ε-greedy選擇并執行動作at(算法1中的第5行)。在執行動作at后，獲得即時獎勵rt和新狀態st+1(算法1中的第6～7行)，并將記憶(st,at,rt,st+1)存儲到D(算法1中的第8行)。然后，從回放空間中隨機抽取K個樣本，通過計算損失函數更新目標網絡的參數(算法1中的第10～13行)。

算法1 基于DDQN的能耗最小化算法輸入 UD初始位置輸出 移動過程中使得系統能耗最小化的卸載決策1.初始化回放空間D,θt和θ-t;2.for episode=1:N3. 獲取初始狀態s;4. for episode=0:T-15. 將st輸入到預測網絡中,采用ε-greedy獲得動作at;6. 執行動作at,利用式(18)計算即時獎勵rt;7. 然后獲得即時獎勵rt和新狀態st+1;8. 存儲記憶(st,at,rt,st+1)到D;9. 從D隨機抽取K個樣本;10. 根據式(20)計算目標Q值;11. 根據式(22)計算損失函數以更新θ;12. 更新目標網絡參數;end for

4 仿真結果與分析

4.1 參數設置

4.2 數值分析

為了評估本文方案，比較4種方案：① 本地計算方案，任務都在本地執行；② 隨機卸載方案，任務隨機選擇卸載；③ 無D2D卸載方案，任務通過中繼卸載到MEC服務器；④ 本文所提方案，任務可以在本地計算，也可以卸載到D2D設備或者卸載到MEC服務器。

DDQN算法的收斂性如圖3所示。折扣因子是對未來獎勵的衰減值，代表了當前獎勵與未來獎勵的重要性。DDQN算法曲線隨著迭代次數的增加遞減，逐漸收斂。算法訓練200個周期，獲得了訓練回報。

圖3 所提算法收斂性Fig.3 Convergence of the proposed algorithm

分別模擬0.1～0.9的任務產生概率(以0.2遞增)，比較4種算法的系統能耗。任務產生概率對平均能耗的影響如圖4所示，可見系統能耗隨著任務產生概率的增加而增加，這是由于任務數量的增大，導致系統需要更大的能耗開銷，從而使得系統能耗增加。本地計算、隨機卸載與D2D卸載算法系統能耗較高，DDQN算法的實驗結果更優。

圖4 任務產生概率對平均能耗的影響Fig.4 Influence of task generation probability on average energy consumption

不同時隙大小對本文方案系統能耗的影響情況如圖5所示?？梢钥闯?，隨著時隙的增大，任務量減少，從而系統能耗不斷降低。

圖5 平均能耗與時隙大小的關系Fig.5 Relationship between average energy consumption and time slot length

分別模擬0.2～1.0的最大時延(以0.2遞增)，比較4種算法的系統能耗。最大時延對平均能耗的影響如圖6所示?？梢钥闯?，系統能耗隨著最大時延的增加而減少，這是由于最大時延的增加，導致設備有充足的計算任務時間。本文方案比其他3種方案能耗更低，進一步說明了本文方案的有效性。

圖6 最大時延對平均能耗的影響Fig.6 Influence of maximum latency on average energy consumption

D2D數量對不同方案的系統能耗的影響情況如圖7所示。可以看出，隨著D2D數量的增加，本文所提方案的能耗在不斷減少。這是因為，D2D數量的增加豐富了用戶卸載的選擇，可以有效減少傳輸能耗。

圖7 平均能耗與D2D數量的關系Fig.7 Relationship between average energy consumption and the number of D2D

5 結束語

本文提出了一種融合D2D和MEC的2層邊緣云計算架構，并引入D2D協作中繼技術用于輔助用戶接入遠端邊緣服務器。考慮到用戶移動性、分布式計算能力和任務卸載時延約束的特性，將任務卸載問題表述為能耗最小化的混合整數非線性規劃問題，并進一步提出了基于DRL的DDQN算法來實時優化任務卸載決策變量。仿真數據表明，提出的協同計算方案在計算資源緊張的情況下，能有效降低移動用戶的任務執行能耗且優化決策的收斂性較好。在未來的工作中，將研究D2D輔助的計算任務動態卸載方案中的激勵機制。