劉婷，羅喜良

(1 上?？萍即髮W 信息科學與技術學院，上海 201210；2 中國科學院上海微系統(tǒng)與信息技術研究所，上海 200050；3 中國科學院大學，北京 100049)(2020年1月15日收稿；2020年5月5日收修改稿)

隨著物聯網時代信息的快速增長，用戶對數據處理速率、服務質量(quality of service, QoS)與體驗質量(quality of experience, QoE)的要求在不斷提高。然而大批提升用戶體驗的智能應用服務，如增強現實(augmented reality, AR)、虛擬現實(virtual reality, VR)、交互游戲等往往伴隨著高計算復雜度和低時延的要求。因此即使移動設備的處理能力在不斷提高，但智能手機作為便攜性設備，由于其固有的缺點，如有限的計算資源、存儲資源，仍然無法滿足此類任務的要求。移動邊緣計算能夠有效平衡設備能力和用戶體驗的困境，同時，移動邊緣計算的安全性能夠得到保障，如文獻[1]中作者從服務器安全、用戶隱私等多方面來保證系統(tǒng)的穩(wěn)定。因此移動邊緣計算技術被廣泛研究。在移動邊緣計算(mobile edge computing,MEC)網絡中[2-4]，將高計算復雜度的任務卸載至網絡邊緣端，利用分布式的計算資源和存儲資源，能夠有效減少任務的處理時延。因此，如何實現更高效的任務卸載吸引了大量學者的關注。

在許多文獻中，任務卸載被建模為確定性優(yōu)化問題。You等[5]在任務計算時延的約束下，通過任務卸載實現最小化能量消耗，并將該任務卸載問題定義為確定性優(yōu)化問題。然而一個實用的任務卸載策略應該能夠根據系統(tǒng)的實時狀態(tài)進行自主調整，例如用戶設備的隊列信息、幫助節(jié)點的計算能力等?；谠摽紤]，Mao等[6]將任務卸載建模為隨機規(guī)劃問題，利用李雅普諾夫優(yōu)化方法，將復雜的隨機規(guī)劃問題轉換為一系列簡單的順序決策問題。上述文獻提出的任務卸載策略都是基于系統(tǒng)參數信息已知的假設，但在實際場景中用戶難以獲得系統(tǒng)信息，或者需要大量開銷來獲取信息，因此需要一個能夠自主在線學習的策略實現任務卸載。此外，在文獻[5-6]中，作者只根據系統(tǒng)的短期利益更新任務卸載策略，而忽略了系統(tǒng)的長遠利益。本文將針對這2個因素來建立任務卸載模型。

強化學習作為一種在線學習方法，能夠從系統(tǒng)歷史反饋中學習系統(tǒng)信息，從而處理系統(tǒng)的未知性。近期許多文獻利用強化學習技術在任務卸載方面取得進展。Chen等[7]利用強化學習得到更優(yōu)的任務卸載策略，從而實現系統(tǒng)長期效用的最大化。Min等[8]將能量收集技術應用到MEC網絡，通過強化學習來選擇卸載節(jié)點和速率以提高用戶體驗。Huang等[9]將無線供電MEC網絡的任務卸載建模為組合優(yōu)化問題，利用強化學習得到近似最優(yōu)解。然而，上述文獻都是基于靜止的用戶設備，忽視了移動用戶的需求，無法應用于移動場景，如現在的車聯網(vehicle-to-everything, V2X)應用、AR的場景導覽、移動機器人[10]等，因此針對于移動用戶的任務卸載的研究具有重要意義。

相較于移動的用戶，靜止用戶所處的MEC網絡環(huán)境中的信道環(huán)境、周圍節(jié)點的拓撲結構等比較穩(wěn)定，這也是之前大部分研究任務卸載的文獻中考慮的場景[4-8]。而相比于傳統(tǒng)有線網絡，如今很多使用無線網絡、蜂窩網絡的用戶通常處于移動狀態(tài)，因此不僅用戶周圍的幫助節(jié)點會隨著變化，信道狀態(tài)也會發(fā)生改變?；诖丝紤]，本文參照文獻[11]中MEC網絡的拓撲結構和用戶移動模式，假設用戶按照馬爾科夫性質在網絡中移動，利用強化學習技術對任務卸載進行研究。文獻[11]中，在一個蜂窩網絡完全覆蓋、Wi-Fi局部覆蓋的場景中，作者探究在昂貴的蜂窩網絡和便宜的Wi-Fi下，移動用戶通過Wi-Fi卸載來減少開銷從而完成長時間的文件傳輸。他們將卸載模型定義為馬爾科夫決策過程(Markov decision process, MDP)，并在用戶移動模式已知時提供系統(tǒng)最優(yōu)解。MDP被廣泛應用于隨機規(guī)劃問題中，它能夠有效地刻畫系統(tǒng)的動態(tài)變化，并將系統(tǒng)的長期表現作為目標。

本文將移動用戶的任務卸載問題建模為MDP，并在系統(tǒng)信息為先驗知識時，提供系統(tǒng)的最優(yōu)解。同時，在系統(tǒng)信息未知，即用戶移動模式未知時，通過基于Q-learning和DQN的在線學習方法，得到收斂速度快，且效果逼近最優(yōu)解的算法。

符號說明：指示函數1{A}表示事件A發(fā)生(不發(fā)生)時取值為1(0)。[·]為期望。[x]+=max{0,x}。{0}代表集合中除{0}以外的所有元素的集合。

1 系統(tǒng)模型

1.1 網絡模型

在移動邊緣計算網絡中(參見圖1)，存在移動用戶(本地節(jié)點)和一些固定節(jié)點。固定節(jié)點可以是宏基站、微基站和家庭基站等，它們能夠為用戶設備提供計算資源和存儲資源等，后文將其稱為幫助節(jié)點。

圖1 移動邊緣計算的網絡拓撲結構圖

圖2 任務卸載模型時間線

1.2 問題建模

本文的目標是最小化移動用戶的長期任務時延。為刻畫用戶移動性帶來的系統(tǒng)隨機性，將問題定義為一個馬爾科夫決策過程，利用系統(tǒng)轉移概率來刻畫用戶的移動模式。該問題可以由4個元素完全表征，下面將分別介紹。

其中：m,n為正整數，f0為本地節(jié)點計算能力，即每時隙處理的任務大小。當任務在本地計算時，隊列會增加大小為μ的任務，同時本地節(jié)點以f0的速度處理任務。當任務卸載到其他幫助節(jié)點時，本地節(jié)點不增加任務，同時以f0的速度處理任務。

(1)

其中bt+1的轉移概率服從

(2)

4)開銷c(s,a)：系統(tǒng)的開銷定義為完成任務需要的時延，c(st,at)為完成任務t所需要的時延

(3)

為最小化移動用戶的長期任務的時延，將問題定義為

(4)

2 任務卸載策略

2.1 系統(tǒng)已知時的最優(yōu)任務卸載策略

Vπ(s)=,

(5)

其中：si代表初始狀態(tài)，[·]為對策略π和轉移概率(s′|s,a)的期望。

最優(yōu)策略π*的狀態(tài)值函數Vπ*(s)稱為最優(yōu)狀態(tài)值函數，下文簡寫為V*(s)。最優(yōu)狀態(tài)值函數滿足貝爾曼最優(yōu)性條件[14]，以系統(tǒng)狀態(tài)st為例：

(6)

其中Q*(st,a)為狀態(tài)-動作對(st,a)的動作值函數，滿足

Q*(st,a)=[c(st,a)+γV*(s′)|st,a]

(7)

其中s′為系統(tǒng)在狀態(tài)st執(zhí)行動作a后，系統(tǒng)可能轉移的下一狀態(tài)。式(7)中第2個等式的第1項為任務t的即時開銷c(st,a)，第2項為對未來所有任務的折扣開銷的期望的估計，γ是1.2節(jié)中的折扣因子，滿足γ<1。在貝爾曼最優(yōu)性方程中，即時開銷的比重為1，高于對未來開銷的估計的比重γ。

動作值函數Q*(s,a)的定義與狀態(tài)值函數V*(s)相似，為系統(tǒng)在狀態(tài)s執(zhí)行動作a后，按照策略π*實現的長期折扣開銷的期望。從式(6)可以看出，若已知最優(yōu)動作值函數Q*(s,a)，采用貪婪算法執(zhí)行任務卸載，即最低動作值函數對應的動作為最優(yōu)卸載決策

(8)

基于以上研究，當系統(tǒng)信息已知時，通過數值迭代能夠求解所有狀態(tài)-動作對的最優(yōu)動作值函數，再基于貪婪算法獲得最優(yōu)策略。具體流程見算法1。

算法1最優(yōu)任務卸載算法

步驟5)根據式(7)更新Q*(s,a)，根據式(8)更新π*(s)，按照式(6)設置V*(s)。

步驟6)若V*(s)收斂，算法結束；否則跳轉至步驟2。

算法1通過離線地對貝爾曼最優(yōu)性條件，式(6)和式(7)，進行數值迭代，從而得到最優(yōu)卸載策略π*。當系統(tǒng)需要進行在線任務卸載時，觀測到狀態(tài)s后，可以直接通過π*(s)獲得最優(yōu)卸載決策。

2.2 在線任務卸載算法

然而系統(tǒng)信息一般難以獲得，雖然能夠根據用戶的歷史移動軌跡，對用戶移動模式進行預測[12-13]，但會引入大量額外開銷。為解決用戶移動性帶來的系統(tǒng)未知性，基于在線學習，提出能夠應對用戶移動性的任務卸載算法。

2.2.1 基于Q-learning的任務卸載

由于用戶移動模式為后驗知識，無法通過2.1節(jié)中的算法得到最優(yōu)任務卸載策略，因此需要在線學習的算法來處理未知信息。Q-learning作為一種無模型方法，可以根據系統(tǒng)的歷史反饋，對動作值函數Q(s,a)進行預測。

在系統(tǒng)狀態(tài)st時執(zhí)行動作at后，觀測系統(tǒng)開銷c(st,at)，同時系統(tǒng)轉移到下一狀態(tài)st+1，可以將這些信息稱為一組經驗值et=(st,at,c(st,at),st+1)。之后動作值函數Q(st,at)利用這一組經驗值，按照下式更新：

Qt(st,at)=(1-αt)Qt-1(st,at)+

(9)

式中：Qt為動作值函數的第t次迭代，αt為第t次迭代的學習率，也代表此次經驗值et的重要性。在每個時隙，系統(tǒng)利用經驗值更新動作值函數，獲得新的動作值函數后，在下一時隙根據新的動作值函數按照式(8)執(zhí)行卸載決策。

1)即時開銷有界，|c(s,a)|≤C;

2)學習率αt滿足隨機逼近條件

(10)

我們的任務卸載模型符合條件1)。同時通過對學習率的設定，如設置αt=1/t，條件2)也可以得到滿足。因此本文的任務卸載模型能夠通過Q-learning方法收斂到最優(yōu)解?；赒-learning的在線任務卸載策略的流程見算法2。

算法2基于Q-learning的任務卸載

步驟3)觀測系統(tǒng)開銷c(st,at)以及新狀態(tài)st+1；

步驟4)存儲經驗值et=(st,at,c(st,at),st+1)；

步驟5)按照式(9)更新Qt(st,at)；

步驟6)設置t=t+1；

步驟7)若t>T，算法結束；否則跳轉步驟2)。

Q-learning是一個基于表格的策略，表格橫軸為狀態(tài)空間，縱軸為動作空間，表格內為所有狀態(tài)-動作對的Q值。為達到收斂，表格中每一個數據都需要得到多次更新。但在算法2中，每個時隙只能更新表格中的一個數據，如果狀態(tài)空間和動作空間非常大，將面臨維度災難并難以收斂。為應對這種情況，加快收斂速度，將采用基于擬合的方式，實現在單個時隙中批量更新Q值。

2.2.2 基于DQN的任務卸載

(11)

其中：Q(s,a;θ)為深度神經網絡的輸出，θ為神經網絡的參數，將深度神經網絡與Q-learning的結合稱為DQN[16]。

(12)

(13)

算法3基于DQN的任務卸載

步驟1)初始化神經網絡參數θ0，設置t=1；

步驟5)按照式(13)更新yt，在θ方向對損失函數執(zhí)行梯度下降，更新θt；

步驟6)設置t=t+1；

步驟7)若t>T，算法結束；否則跳轉步驟2)。

3 仿真實驗

3.1 參數設置

移動邊緣計算網絡的參數設定主要參照文獻[17]。除位于場景中心的宏基站外，網絡中還有N=20個幫助節(jié)點。本地節(jié)點的傳輸功率為20 dBm，到宏基站和其他幫助節(jié)點的路徑損耗分別為(35.7+lgd+33.4)dB和(35.7+lgd+18.4)dB，d為本地節(jié)點到幫助節(jié)點的距離，單位為m。系統(tǒng)帶寬為20 MHz，功率頻譜密度為-174 dBm/Hz。本地節(jié)點和宏基站的處理速度分別為10和35 Mbps，其他幫助節(jié)點的處理速度均勻分布于(10,40)Mbps。

在對DQN任務卸載策略進行仿真時，采用TensorFlow框架來搭建深度神經網絡[18]。在神經網絡中包含2層隱藏層，分別含有128和64個神經元，采用ReLU作為激活函數[19]。其他參數列在表1中。

表1 DQN參數設置

3.2 仿真結論

這一節(jié)驗證基于Q-learning和DQN的任務卸載策略的表現，并與最優(yōu)卸載方案進行比較。由于在實際中系統(tǒng)信息難以獲得，最優(yōu)卸載方案無法應用，因此本文將最優(yōu)任務卸載算法作為基準來驗證其他2個算法的效果。

1)收斂性：圖3通過展示動作值函數的累計平均值來驗證基于Q-learning和DQN的任務卸載策略的收斂性。不失一般性地，選擇系統(tǒng)狀態(tài)s=(7, 30)和動作a=1的動作值函數作為示例，即Q((7, 30), 1)。

圖3 算法收斂性比較

2)近優(yōu)性：在2.2.1節(jié)中提到，本文中的任務卸載模型采用的Q-learning算法能夠以概率1收斂到最優(yōu)解。為驗證該結論，將通過長期任務的時延來驗證算法的近優(yōu)性。圖4和圖5的縱坐標為系統(tǒng)回報Rt，定義為Rt=C-c(st,at)，C為開銷的上界。

圖4 算法性能比較

圖5 預訓練后算法性能比較

同樣的，圖中的最優(yōu)解是基于系統(tǒng)信息已知的假設，因此只作為其他算法的表現基準，而基于Q-learning和DQN的任務卸載策略中，系統(tǒng)信息為后驗知識，系統(tǒng)利用歷史反饋以實現自主在線學習。同時，我們還將算法同“不卸載”進行比較，它忽略了用戶的移動性，對所有任務都不執(zhí)行任務卸載，只在本地節(jié)點進行處理。我們將觀察不考慮用戶移動性時的系統(tǒng)表現。

在圖4中，基于Q-learning和DQN的算法對系統(tǒng)信息沒有先驗知識，從時隙t=0開始在線學習。因此在仿真的前期時隙中，Q-learning由于學習數據的不足，導致算法對系統(tǒng)信息掌握較少，表現較差。此時基于Q-learning的任務卸載策略實現的系統(tǒng)回報，甚至低于不執(zhí)行任務卸載的策略。但值得注意的是，基于Q-learning策略的回報始終保持著上升的趨勢，并且從第800個時隙開始，表現超過不執(zhí)行任務卸載的策略，且一直維持著上升的趨勢。而基于DQN的任務卸載有著明顯的優(yōu)勢，不論是仿真前期還是后期，獲得的利益始終高于Q-learning和不執(zhí)行卸載的策略，同時也維持著最為明顯的系統(tǒng)回報上升的趨勢。在短時間內，不考慮用戶移動性的策略表現似乎與提出的算法相差不多，但從長時間尺度來看，考慮移動性的任務卸載策略，在后期表現更為優(yōu)異。下面將進一步展示算法對長期任務的表現。

圖5將經過預訓練的Q-learning和DQN的算法與最優(yōu)解進行比較，從而驗證2個算法的近優(yōu)性。其中基于Q-learning和DQN的任務卸載分別經過200 000和2 000個時隙的預訓練，已經接近收斂。從時隙t=0開始進行在線的任務卸載?？梢钥闯?，與圖4的未經預訓練相比，2個算法經過預先學習后已經對系統(tǒng)掌握大量信息，Q-learning的表現已經非常接近最優(yōu)解，證明它的確能夠在系統(tǒng)信息未知的情況下，通過在線學習達到接近最優(yōu)解，并高效地完成任務卸載。而DQN的表現雖然略遜于Q-learning，但相差不大。然而值得注意的是，相比于Q-learning，基于DQN的任務卸載只需要1%的預訓練時間就能夠達到接近Q-learning的效果，這也再一次驗證了基于DQN的任務卸載策略快速的收斂速度?？梢钥闯觯陂L期任務中，提出的算法在表現上一直明顯優(yōu)于不考慮用戶移動性的不卸載策略，這也驗證了上一段的討論，考慮用戶的移動性在長時間尺度上可以實現更高的系統(tǒng)利益。

4 結束語

本文研究MEC網絡中高效的在線任務卸載策略。為最小化移動用戶在系統(tǒng)中的長期任務時延，利用馬爾科夫決策過程建立任務卸載模型。在假設系統(tǒng)信息已知的前提下，提供了系統(tǒng)的最優(yōu)解。在系統(tǒng)信息未知時，提出2個在線學習的算法，基于Q-learning和DQN的任務卸載。其中基于Q-learning的任務卸載在本文的模型中能夠收斂到最優(yōu)解，而基于DQN的算法能夠快速收斂，并且達到接近最優(yōu)解的表現。