移動邊緣網絡中基于強化學習的部分卸載分析

王景弘, 陳 昱, 胡建強

（廈門理工學院計算機與信息工程學院,福建 廈門 361024）

隨著移動邊緣網絡的普及，自動語音識別（automatic speech recognition, ASR）、自然語言處理（natural language processing, NLP）和計算機視覺（computer vision, CV）[1-3]等應用都需要計算資源來保證體驗質量（quality of experience, QoE）和服務質量（quality of service, QoS）.由于智能移動設備的計算能力和電池電量有限，從用戶到服務器的計算卸載成為移動邊緣計算（mobile edge computing, MEC）優化資源利用率、能耗和網絡延遲的重要支撐技術[4].

移動邊緣計算MEC 環境中，由于用戶設備存在各異的通信條件和計算要求，在滿足最小時延要求下協調多個用戶間的計算卸載較為困難.在移動邊緣計算環境中，任務卸載通常被設置為二進制計算卸載[5]，即計算任務只能在用戶設備（user equipment, UE）上本地計算，或完全卸載給MEC 服務器計算，任務卸載過于簡單化而且決策的準確性不高.特別是，不同的用戶設備通常處于移動狀態，各用戶之間的通信情況會時刻變化.采用強化學習（reinforcement learning, RL）[6]在移動邊緣計算卸載有許多應用，但狀態空間和動作空間的需求增強使得求取Q值困難[7].

假定在供能充足、不需過度考慮能耗條件的移動邊緣網絡環境下，優化卸載決策的延遲，從而降低總的服務延遲，提高用戶的體驗質量.為此，提出了一種基于強化學習的部分任務卸載方法，即采用Q-learning算法手動設置卸載率用于離散卸載決策，并使用深度確定性策略梯度算法DDPG-PO進行連續卸載決策，解決Q表的維數較大而導致搜索困難的問題.最后，采用實驗驗證上述方法的有效性.

1 相關工作

近年來有很多人工智能算法應用到移動邊緣計算卸載領域.文獻[8]提出了一種基于深度RL 的在線卸載（DROO）框架，DROO在網絡上的輸出使用S形激活函數來限制輸出.當輸出結果大于0.5時，任務將被完全卸載到MEC 服務器.否則，任務將在UE 上本地計算.文獻[9]使用Q學習和深度Q網絡（DQN）算法來尋找計算卸載策略.Q學習和DQN 算法比較了本地計算方案和計算卸載方案的長期回報大小，選擇了與更大的長期回報相對應的計算卸載策略.文獻[10]研究了霧計算中的遷移機制，并對容器遷移和虛擬機遷移兩種方案進行了比較，得出了容器遷移比虛擬機遷移方案更輕量級的結論.其在計算卸載策略中使用了深度Q學習方法，以減少計算任務的延遲和能耗，以及容器遷移的成本.文獻[11]研究了物聯網場景中的計算卸載策略，并使用DQN 學習計算卸載策略.其中動作空間是離散物聯網設備的傳輸功率，如果傳輸功率為零，則表示本地計算.然而，離散傳輸功率存在動作空間過大的問題.文獻[12]研究了物聯網場景下邊緣計算的帶寬資源分配問題，并使用DQN 學習帶寬資源分配策略，以優化物聯網設備的服務延遲和能耗.但由于離散域中的帶寬資源分配不均，也存在帶寬資源利用率不足的問題.

根據上述研究，啟發式算法和RL算法是解決計算卸載時延優化問題的常用方法.但啟發式算法很容易陷入局部最優解，算法的性能與具體問題和設計者的經驗密切相關.深度強化學習結合了深度學習和RL 的優勢，從高維原始數據學習控制策略，擴充系統的狀態空間和可能發生的動作空間，并獲得長期的回報，加強決策的準確性和時效性.

2 系統模型與問題建模

從網絡模型、計算任務模型、本地計算模型和部分卸載邊緣計算模型等方面介紹系統模型，并提出了問題框架.表1列出了主要符號.

表1 主要符號Tab.1 Main symbols

2.1 網絡模型

MEC系統含有n個UE 和1 個與基站部署在一起的服務器，UE 的集合表示為N= {1，2，…，n}. UE 可以把任務卸載給邊緣服務器，利用服務器的高算力來減少計算延遲. 根據參考文獻[9]的描述, 假設每個UE的任務優先級是相同的，每個UE可以獲得相同的傳輸帶寬資源，UEn的傳輸速率為

其中：W是無線信道的帶寬；K是正在計算卸載的UE 的數量；pn是UEn的上傳數據的傳輸功率；hn是UEn和基站之間的無線信道增益；G0是高斯白噪聲的方差[9].

2.2 計算任務模型

定義Taskn?(Dn，Cn，tn)作為UEn需要執行的任務.該任務可以在本地計算，也可以通過計算卸載在MEC 服務器上計算[13].Dn表示完成此任務所需的數據量，包括需要處理的相關數據.Cn表示完成任務Taskn所需的CPU 周期的數量.通常Dn和Cn的大小是正相關的，并且Cn的大小不會由于計算卸載而改變.tn是任務Taskn的最大可容忍延遲，表示完成任務Taskn所需的時間不應大于tn.

定義λn∈[0，1]作為UEn的卸載策略，UEn將λn的部分卸載到服務器計算，而(1-λn)的部分是由UE本地計算的.UE集合N的整體卸載策略A表示為A=[λ1，λ2，…，λn].當λi=0時，表明Taski由UE本地計算；當λi=1 時，表明Taski被UE 完全卸載給服務器計算；當0 ＜λi＜1 時，表明Taski的λi部分卸載給服務器計算，(1-λi)部分由UE計算.

2.3 本地計算模型

當UE 在本地執行任務時，任務完成過程完全使用本地計算資源與MEC 服務器無關.定義dln來表示任務Taskn的本地計算中的延遲.dln的計算方法為

其中：fln表示UEn的計算能力（UEn每秒的CPU周期數）.

2.4 部分卸載邊緣計算模型

當UE 請求計算卸載時，任務Taskn的λn部分被卸載到MEC 服務器，(1-λn)部分則是本地計算的.Taskn的λn部分的總延遲包括數據上傳延遲、MEC計算延遲和數據下載延遲；(1-λn)部分的延遲類似于上一小節中介紹的本地計算延遲.

其中：fn是MEC服務器分配給Taskn的計算資源.定義COM 為MEC服務器的計算能力（MEC服務器每秒的CPU 周期數）.MEC 服務器分配給所有卸載任務的計算資源不應超過總計算資源，這表明應滿足條件

其中：Bn是MEC 服務器返回的執行結果的數據大小；downn是UEn從MEC 服務器下載執行結果的下載速率.根據文獻[14]，上傳數據Dn的大小遠大于返回數據的大小Bn，下載速率遠大于上傳速率，因此可以忽略數據下載延遲的影響.

由于Taskn的(1-λn)部分是UE計算的，所以它的計算延遲類似于上一節中的本地延遲.定義來表示Taskn的(1-λn)部分的計算延遲，計算方法為

基于上述公式（3）～（6），定義don為執行部分卸載策略時任務Taskn的總時延.由于各個Taskn之間并行執行，UEn進行部分卸載時的總時延應該是部分卸載時延和本地計算時延中更大的那一個.don的計算方法為

2.5 問題定義

公式（7）中，當λn=0 時可以得到don==dln；當λn=1 時可以得到=0.因此可以使用公式（7）來綜合考慮本地計算、部分卸載和完全卸載三種策略的時間延遲.以最小化整個MEC 系統中所有UE 的任務執行時間作為優化目標，結合上述網絡模型、計算任務模型、局部計算模型和邊緣計算模型，優化目標和約束條件定義為

在優化問題（8）中，如果λn的值只能是0或1，搜索最優解的時間復雜度將隨著UE數量的增加而呈指數級增加.文獻[9]證明這類問題是一個NP-hard 問題.為了解決這個NP-hard 問題，引入了一種基于DRL的部分卸載方案，把λn的值從離散域變為連續域，有效地減少了MEC 系統的總時延.約束（9）表示每個Taskn既可以本地計算，也可以完全卸載到MEC 服務器，還可以進行任意比例卸載；約束（10）表示各個任務被服務器分配到的算力之和不能超過服務器總算力；約束（11）表示對于被卸載的任務都必須被分配到算力資源；約束（12）表示每個任務的完成時間don不應超過最大可容忍時延tn，否則會影響用戶的體驗質量.

3 基于Q-learning和DDPG的卸載算法

多用戶多任務MEC 系統中結合邊緣服務器資源分配、部分任務卸載和緩存決策的問題進行建模,目標是最小化整個MEC 系統中所有UE 的任務執行時間.為求解這個混合整數非線性規劃問題，引入Qlearning算法并提出基于DDPG的優化算法DDPG-PO,盡可能地優化QoS并減小系統總時延.

3.1 深度強化學習框架

1）狀態空間.為了將DRL 解決方案應用于系統模型和問題框架，需要定義狀態空間、行動空間和獎勵函數.理論上需要觀察整個MEC系統來確定狀態空間，包括用戶數量、任務情況、計算資源的使用情況等.但事實上，完成這件事會造成額外的系統開銷.隨著MEC 服務器中UE 數量的增加，額外的系統開銷將更大.考慮到優化目標是MEC 系統的總時延，所以將狀態定義為，作為整個MEC 系統的時延.

2）動作空間.為了描述每個UE的計算卸載策略，將動作空間定義為MEC系統中所有UE的動作空間之和.對于每個UEn，定義它的動作空間為A=[λ1，λ2，…，λn]滿足λi∈[0，1]，這意味著卸載方案不必局限于傳統的二元卸載，進而擴展了傳統DRL 的動作空間，并在更大程度上帶來了優化MEC 系統總延遲的可能性.

3） 獎勵函數.定義R(S，A)為獎勵函數，表示代理在狀態S下執行計算卸載策略A時獲得的獎勵.為了評估卸載策略的優缺點，獎勵函數應該與所有UE 的總時延成反比.因此定義獎勵函數為R(S，A) =，這表明卸載策略越好，系統時延越低，回報也就越大.

3.2 算法設計

1）Q-Learning 算法：Q-Learning 算法是一種傳統且廣泛使用的RL 算法，它包含與狀態和動作對相對應的Q函數.Q函數表示在狀態S和動作A下可獲得的長期獎勵的估計，用來選擇具有最長獎勵的最佳策略.Q函數的計算方法為

其中：s′是在狀態s下采取行動a時達到的狀態；α 是學習率；γ 是未來獎勵的折現系數，0 ≤γ≤1，用來表示未來獎勵的重要性.

根據以上對Q-learning算法的描述，還需要對狀態空間和動作空間進行微調后才能應用該算法.對于狀態空間，將狀態四舍五入為一個整數；對于動作空間，則預定義了X+1個離散部分的計算卸載比率.定義UEn的卸載策略為，其中X的大小可以調整，X越大卸載策略越好，但與之對應的是更高的復雜度.每個UE 都有各自的動作空間，所以需要在Q函數中添加一個用戶維度，用Q(S，N，X+1)表示.改進后的Q函數為

在公式（14）中，Q(s，i，λi)表示當MEC 系統處于狀態s時，第i個UEi采用計算卸載策略λi時可以獲得的長期獎勵的估計.由于Q-table要求其索引為非負整數，因此在Q函數中的λi需要乘以X.公式（14）中的s'表示MEC系統中的所有UE采用卸載策略A之后的狀態，其中A包含此時第i個UE的計算卸載策略.簡而言之，MEC系統中所有UE都具有相同的狀態s'.算法1展示了改進后的Q-learning算法.

算法1 預定義離散卸載率的Q學習算法1:初始化Q函數 Q(S，N，X+1);2:for occasion=1 do 3: 用隨機計算卸載策略初始化狀態s;4: repeat 5: 基于貪心策略從 Q-table 中選擇執行動作 A=[λ1，λ2，…，λn];6: 執行動作 A;7: 得到獎勵 r 和下一個狀態 s';8: for i=1,N do 9: 用公式(14)更新 Q(s，i，λi X);10: end for 11: s ←s′12: until 達到期望狀態 sterminal 13: end for

2）DDPG-PO 算法.在上一節中使用Q-Learning 算法通過手動設置X+1 部分的卸載率來實現部分卸載，但因為使用的是Q-table來儲存所有Q值，隨著UE數量的和預定義卸載率的增加，找全整個Q-table的難度也越來越大.所以引入DDPG-PO算法來解決這個問題.DDPG-PO算法包括actor網絡和critic網絡兩部分.actor網絡負責根據觀察到的狀態信息生成策略，而critic網絡負責收集獎勵值以評估和糾正策略.

DDPG-PO 算法將動作空間擴展到一個連續域，并使用一個特殊的重放緩沖器，該容器存儲一定數量的記錄，而不是傳統RL算法中的Q-table.每個記錄由[st，at，rt，st+1]組成，并使用該記錄中的一個小批元組更新參數.

DDPG-PO 算法包含四個DNN.它們分別是actor 網絡μ(s|λμ)，其網絡參數用λμ表示；critic 網絡Q(s，a|λQ)，其網絡參數用λQ表示；目標actor 網絡μ'(s|λμ')，其網絡參數用λμ'表示；以及目標critic 網絡Q'(s，a|λQ')，其網絡參數由λQ'表示.actor網絡負責根據狀態選擇要進行計算卸載的動作.目標critic網絡和目標actor網絡使用重放緩沖器來評估目標Q值，而critic網絡負責計算Q值.目標Q值的計算方法為

對于critic網絡的參數更新，使用梯度下降法來最小化目標Q值和critic網絡輸出之間的差異.損失函數是一個平方損失函數，其計算方法為

其中：N是批次號大小.使用Adam優化器[15]來最小化損失函數.actor網絡使用梯度上升法更新策略，策略梯度為

對于目標網絡參數更新，DDPG-PO 算法使用actor網絡和critic網絡的參數對目標網絡執行軟目標更新.軟目標更新的方式為

其中：TOU 是目標網絡的軟更新因子.參數TOU 滿足0 ＜TOU ＜1.TOU 越小，表明目標網絡參數更新越慢.算法2展示了MEC系統的DDPG-PO算法的過程.

算法2 DDPG-PO (partial-offloading) 算法1: 將actor網絡和critic網絡的參數分別隨機初始化為λμ和λQ;2: 設置λμ′←λμ;3: 設置λQ′←λQ;4: 初始化重放緩沖器R;5: for occasion=1 do 6: 隨機初始化動作A以獲得相對應的狀態s1;7: for t=1, T do 8: 根據actor網絡和附加噪聲,選擇相應的計算卸載策略 At=μ(st|λμ) +Nt, 其中 Nt 是正態分布的噪聲擾動;9: 執行計算卸載策略At,得到獎勵rt和下一個狀態st+1;10: 將記錄(st，at，rt，st+1)存儲在重放緩沖區R中;11: 從重放緩沖區R中隨機抽取記錄;12: 用公式(15)計算目標Q值;13: 通過最小化損失函數公式(16)來更新critic網絡的參數;14: 使用基于公式(17)的采樣的策略梯度來更新actor策略;15: 基于公式(18)和(19)對目標網絡的參數進行軟更新;16: end for 17: end for

在DDPG-PO 算法的神經網絡設計中，把actor 網絡的輸入層的維度設為1，用于MEC 系統的狀態輸入；把actor網絡的輸出層的維度設為N，表示所有UE的卸載策略.因為actor網絡需要根據卸載策略進行動作，所以引入Sigmoid激活函數來縮放其輸出.Sigmoid激活函數為

critic 網絡的輸入層由兩個部分組成，一個是系統狀態S，另一個是每個UE 的卸載策略向量；輸出層的維度設為1，表示Q 值的預測.另外使用全連接層分別組成actor 網絡和critic 網絡的隱藏層.目標actor網絡的結構與actor 網絡的網絡結構相同，目標critic 網絡也與critic 網絡結構相同.圖1 展示了基于DDPG-PO的卸載架構.

圖1 基于DDPG-PO的卸載架構Fig.1 Offloading architecture based on DDPG-PO

4 實驗評估

為了驗證所提出卸載策略的優勢，將其與文獻[8]中的本地UE 計算（local computing）方案、完全卸載（full offloading）方案和DQN卸載策略進行了比較.

在實驗設置中，用戶數量可變并且均勻分布在距離服務器200 m的范圍內.UE和MEC服務器之間的信道增益與距離成反比.無線信道增益設置為hn=dis-ns，其中s=3，disn是UEn和基站之間的距離.無線信道的帶寬設置為W=10 MHz，背景噪聲G0=-174 dBm/Hz，UE 上傳功率pn=500 mW[16].MEC 服務器的計算能力設置為COM=5 GHz/s，并根據λnCn的大小均勻分布給每個任務.每個UE 的計算能力被設置為=1 GHz/s.UE 上的任務量Dn均勻分布為（300 Kbits，500 Kbits），Cn均勻分布為（900 兆周期，1 100 兆周期）[9].最大可容忍延遲設置為tn=dnl，表明如果計算卸載不能有效減少任務時延，則不需要把任務卸載給MEC 服務器，否則會帶來額外負擔.預定義的離散部分計算卸載率X=3，學習率α=0.1，折現系數γ=0.8.DDPG-PO算法中的相關參數如表2所示.

表2 DDPG-PO算法中的參數設置Tab.2 Parameter settings in DDPG-PO algorithm

圖2展示了UE數量對系統總時延的影響.橫坐標表示UE的數量，縱坐標表示所有UE的任務完成時間之和.MEC 服務器的計算能力為COM=5 GHz/s.在通常情況下，所有方案的總延遲都隨著UE 數量的增加而增加.可以發現用戶數量超過5時，完全卸載方案的總時延是最高的.這是因為此方案中所有任務都被卸載給MEC服務器，且由于計算能力有限，無法滿足所有UE的計算需求.此時只有提高服務器的算力才能降低整體的時延.由實驗結果可知這兩種算法與其他策略相比更好地減少了時延.

圖2 不同UE數量下的總時延Fig.2 Total delay under different UE numbers

圖3展示了MEC服務器的計算能力對系統總時延的影響.橫坐標是MEC服務器的計算能力，縱坐標是所有UE的任務完成時間之和.UE的數量為N=5.由于本地計算不需要服務器參與，因此其結果是在圖上是一條直線.通常隨著MEC服務器計算能力的提高，系統總時延會減少，提高MEC服務器的計算能力有助于提高系統性能.隨著邊緣服務器計算能力提高，DQN接近完全卸載.Q-learning算法和DDPG-PO算法的時延總是低于DQN，這是因為Q-learning算法和DDPG-PO算法包含本地資源，但它們之間的差距逐漸減小.當COM ≥7 GHz/s時，系統的總延遲緩慢下降，這是因為此時限制系統總延遲的主要因素是傳輸時延.

圖3 MEC服務器的計算能力對系統總時延的影響Fig.3 The impact of MEC server's computing power on the total delay

當卸載策略A是二進制，即采用本地計算或者完全卸載時，在UE 數量少的情況下，可以通過列舉在可接受的搜索時間內所有UE 的決策情況來找到最佳的卸載策略A′，從而獲得二進制計算卸載的最小時延.歸一化時延定義為

其中：D*(A)表示采用計算卸載策略A的時延.

為了驗證所提出算法的優勢，對比對象采用了文獻[8]中提出的DROO策略.圖4展示了不同UE數量下三種算法的歸一化時延，橫坐標是UE 的數量，縱坐標是歸一化時延，MEC 服務器的計算能力設置為COM=5 GHz/s.對比了DROO算法之后可以發現，這是一種只支持本地計算或者完全卸載的二元卸載算法.DROO 算法的歸一化時延均為1，這說明它可以得出在本地計算或者完全卸載中的最佳卸載策略.但本文提出的部分卸載策略的歸一化時延均低于1，這說明部分卸載策略的時延要低于本地計算或者完全卸載.平均下來，Q-learning算法和DDPG-PO算法分別比DROO算法的時延低了21%和28%.由此也可以看出部分卸載相對于二元卸載而言，可以更好地減少系統總時延，提升用戶體驗質量.

圖4 Q-learning算法和DDPG-PO算法的歸一化時延Fig.4 Normalized delay of Q-learning algorithm and DDPG-PO algorithm

圖5展示了不同CPU周期對系統總時延的影響.橫坐標是完成Taskn所需的CPU周期數，縱坐標是所有UE的任務完成時間之和.UE的數量為N=5，MEC服務器的計算能力為COM=5 GHz/s.橫坐標的增加表明任務需要更多的計算資源.通常隨著每個任務所需CPU 周期的增加，所有卸載方案的總時延都會增加.從實驗結果可以發現，完全卸載的時延最高，本地計算次之，DQN 算法的時延相比它們而言低了很多，而這兩種算法的時延最低，表現優于其他幾種卸載策略.實驗結果也從另一方面印證了所提出的卸載方案可以適應高計算量任務.

圖5 不同CPU周期下的總時延Fig.5 Total delay under different CPU cycles

圖6展示了兩種算法的收斂性.橫坐標是主循環的迭代次數，縱坐標為偶發性獎勵，表示MEC系統在一個偶發情況中獲得的總獎勵.UE 的數量N=5，MEC 服務器的計算能力為COM=5 GHz/s.由獎勵函數，偶發性獎勵越大，系統總時延越低.根據實驗結果可知，兩種卸載策略隨著迭代次數的增加，MEC 系統所獲得的偶發性獎勵也隨之增加，這證明了所提出的兩種策略在減少時延方面是有效的.在算法收斂速度方面，基于Q-learning 的離散計算卸載策略比基于DDPG-PO 算法的連續計算卸載策略收斂更快.在迭代了60次之后，Q-learning算法已經達到穩定狀態.其收斂速度與X的值有關，通常X值越大收斂越慢.相比于Q-learning算法，DDPG-PO算法收斂得更慢但具有更強的降低總時延的能力.

圖6 Q-learning算法和DDPG-PO算法的收斂性Fig.6 Convergence of Q-learning algorithm and DDPG-PO algorithm

5 結語

研究物聯網中多用戶MEC 系統的部分計算任務卸載問題，優化的目標是盡最大可能減少MEC 系統的總時延.建立了一個適用于部分計算卸載的深度RL 模型，并提出了Q-learning 算法和DDPG-PO 算法的結合作為部分計算卸載策略，將二進制計算卸載方案擴展到連續動作域.仿真結果表明，與傳統的本地計算和邊緣計算相比，Q-learning算法和DDPG-PO算法可以有效地降低MEC系統的總時延.與最佳二進制計算卸載策略相比，Q-learning算法和DDPG-PO算法還將系統時延分別降低了21%和28%.