基于深度強化學習的邊云協同任務卸載策略

鄧文貴，文志誠，歐 靜

(湖南工業大學 計算機學院，湖南 株洲 412000)

0 引 言

移動云計算(mobile could computing，MCC)是一種集中式部署計算模式，可以利用云計算中心豐富的計算、儲存、網絡等資源提高移動終端的計算處理能力[1]。但是，移動終端設備和計算任務的增加，以及有限的網絡帶寬和較遠的傳輸距離，嚴重影響計算任務的數據傳輸，使得傳輸過程中的能耗和時延增大[2]，從而無法滿足延遲敏感型的計算任務，降低了用戶的體驗質量。

為了彌補移動云計算的不足，移動邊緣計算(mobile edge computing，MEC)作為一種新的卸載方案被提出[3]。MEC采用分布式部署方式，將MEC服務器部署在移動設備網絡邊緣的基站，并在邊緣服務器上部署云計算中的計算、存儲等資源，相比于MCC，終端設備可以直接與MEC服務器進行數據傳輸，能夠更快速響應用戶的計算任務卸載請求，減少訪問云計算中心的頻率，降低計算任務上傳時的能耗、傳輸延遲和網絡擁塞[4-6]。MEC系統的效率主要取決于任務卸載策略，而目前大多數研究將卸載問題描述為NP問題并通過啟發式算法進行求解。但這些算法不能保證其魯棒性，只能應用于特定場景，難以適用于復雜的現實場景。

近些年，深度強化學習(deep reinforcement learning，DRL)[7]因其具有很好的環境適應性而被廣泛應用到各個領域以解決實際問題。DRL最顯著的算法之一是深度Q學習(DQN)，多用于處理連續狀態空間中的問題[8]，通過將深度學習模型與強化學習結合，實現直接從高位輸入學習的控制策略，進而提高算法收斂性能并解決當前任務計算卸載所面臨的局限性。

1 相關工作

MEC系統的效率很大程度依賴于其任務卸載策略，因此MEC任務卸載策略成為了當前研究的熱點。文獻[9]為降低細粒度任務遷移模型下的任務執行時間，提出了基于遺傳算法的MEC任務緩存和遷移策略。文獻[10]提出了一種基于遺傳算法的聯合資源優化方法，以優化MEC服務器中的卸載比例、信道帶寬和計算資源分配，從而得到任務完成時間最小的卸載策略。文獻[11]將移動應用程序建模為有向無環圖提出基于元強化學習的任務卸載策略，以降低任務執行時延。文獻[12]提出了一種滿足不同任務延遲要求的啟發式任務卸載策略，通過合理分配MEC服務器無線電資源和計算資源來提高系統的執行效率。文獻[13]針對邊云場景提出了一種智能蟻群任務卸載策略，以降低服務延遲，提高用戶服務質量。文獻[14]為最小化所有系統實體的開銷，從任務計算和通信方面對卸載的消耗進行建模，提出了一種基于人工魚群算法的卸載方案，以優化系統整體開銷。

此外，移動設備的任務計算卸載決策受限于網絡帶寬和存儲計算資源，因此研究人員開始嘗試通過深度學習和強化學習來解決計算卸載問題。文獻[15]將計算卸載視為一種游戲，由玩家(即移動設備)、策略(即本地或遠程執行任務)和獎勵值組成，然后采用Q-學習算法來解決此問題。文獻[16]提出了基于深度Q網絡的半在線計算卸載模型，通過強化學習來探索復雜動作空間中的用戶行為捕捉未知的環境信息。文獻[17]考慮了一個多用戶MEC系統，并提出基于RL的優化框架來解決任務卸載的計算卸載和資源分配問題。文獻[18]采用深度強化學習來優化虛擬邊緣計算系統從而提高計算卸載性能，但作者只是做了假設，而沒有在許多細節上探索事實。當然，將強化學習應用于邊緣計算的技術也在不斷趨于成熟。文獻[19]提出了一種新的基于狀態自適應和深度強化學習的服務遷移方法來克服網絡故障，并利用滿足度理論來求解遷移策略的候選空間。文獻[20]提出了基于DRL的經驗驅動網絡，它顯著減少了端到端延遲，并持續提高了網絡利用率。

2 系統模型

2.1 網絡架構模型

我們考慮多用戶多MEC服務器邊云協同的場景，并考慮一個實時多用戶計算場景。利用云服務器和邊緣服務器的相互協同來完成移動設備的計算任務，具有云計算和存儲能力的移動基站密集分布在移動用戶附近，云服務器部署在遠離終端設備的網絡層。在本文中，我們考慮邊云協同，當計算任務卸載時根據不同的卸載決將任務卸載到本地、該區域內的MEC服務器和云服務器上進行計算。

移動邊緣計算系統架構模型如圖1所示。卸載模型由多個終端設備、多個邊緣服務器和一個云服務器組成，構成一個云-邊-終端的三層結構。在該移動邊緣計算網絡架構中，最上端的云服務器，利用交換機和基站聯系，整個互聯網由多個基站組成，多個小型MEC服務器部署在各個基站周圍，MEC服務器之間能夠實現數據通信。在終端智能設備側，其產生的任務可直接在本機的CPU上進行，也可通過傳輸單元發送到其所在區域中的MEC服務器中實現遠程運算，甚至上傳到遠端的云服務器中實現運算。

圖1 移動邊緣計算系統架構模型

整個移動邊緣計算系統網絡架構，由若干個小區域組成，區域之間相互獨立。在一個區域中，假設用戶終端設備用集合 {1，2，…i，…，U} 表示，終端設備所在區域的MEC服務器用集合 {1，2，…j，…，M} 表示，用戶設備擁有有限的計算資源，智能設備Ui(i∈{1，2，…，U}) 通過5G無線通信技術將自己的計算任務卸載到MECj服務器 (j∈{1，2，…j，…，M}) 中，也可以選擇卸載到遠端的云服務器上進行計算，或者選擇在本地進行計算。

2.2 任務模型

每個終端設備都有一個計算密集型任務需要執行，智能設備Ui產生的任務用Ai來表示，由3部分組成，Ai定義如式(1)所示

Ai={wk，dk，τk}

(1)

2.3 通信模型

用戶可以選擇將自己的任務在本地執行，也可以卸載到邊緣服務器或遠端云服務器中執行，在整個系統中，主要存在兩部分通信。包括用戶將任務傳輸到MEC服務器的通信和MEC服務器與云服務器之間的通信。根據瑞利衰落信道模型，定義通信模型如下：

用戶Ui將任務Ti上傳到MECj的傳輸速率為

(2)

其中，B代表傳輸帶寬，pi，j為用戶Ui的傳輸功率，hi，j為信道增益，di，j代表用戶i與服務器j之間的距離，θ代表路徑損耗指數，N為高斯加白噪聲。

任務Ti從邊緣服務器MECj上傳到云服務器Cloud傳輸速率為

(3)

同理，其中B代表傳輸帶寬，pj，c為MECj到云服務器的傳輸功率，hj，c為信道增益，dj，c代表服務器j和云服務器之間的距離，θ代表路徑損耗指數，N為高斯加白噪聲。

2.4 計算模型

在這一小節，介紹了計算模型。本地服務器、邊緣服務器和云服務器都可以進行任務計算因此計算模型由本地計算、邊緣服務器計算和云服務器計算3種模型組成。本地計算模型即智能設備將任務卸載在本地進行計算，邊緣服務器和云服務器計算模型分別指的是將計算任務卸載到邊緣服務器和云服務器進行計算。

(1)本地計算模型

根據上面定義的任務模型，wk為該任務的負載，即執行該任務需要花費的總CPU周期數，fi為用戶Ui的計算能力，則用戶i的任務k在本地的執行時延為

(4)

(5)

用戶i的任務k在本地運行的總能耗為

(6)

其中，ki是設備芯片結構的系數因子。

(2)邊緣服務器計算模型

當用戶選擇卸載到邊緣服務器上進行計算時，用戶i向MEC服務器j傳輸任務的時延為

(7)

MECj的執行時延為

(8)

其中，wk為任務的負載，即執行該任務需要花費的總CPU周期數，服務器的計算能力為fj。

因此，用戶i的任務在MECj運行的總時延

(9)

用戶i的任務在MECj運行的能耗

(10)

(3)云服務器計算模型

當用戶選擇卸載到云服務器上進行計算時，終端設備i需要先將任務上傳到臨近的MEC服務器，再上傳到云服務器。

用戶i向鄰近MEC服務器MECj傳輸任務的時延為

(11)

任務從MEC服務器j上傳到遠端云服務器的傳輸時延為

(12)

所以總傳輸時延為

(13)

執行時延為

(14)

其中，wi為任務的負載，即執行該任務需要花費的總CPU周期數，云服務器的計算能力為Fcloud。因為云端計算速度特別快，所以我們忽略等待時延。

因此，執行總時延為

(15)

整個過程產生的總能耗為

(16)

2.5 系統目標建立

在本文，我們綜合考慮時延和能耗兩個開銷指標，以能耗和時延的加權定義任務Ai的總開銷為Ci=β*Ei+(1-β)*Ti， 其中β∈[0，1] 代表設備的能量消耗權衡參數。假設Ii，j為任務所選擇的卸載策略，則用戶執行任務的時延開銷為

(17)

用戶執行任務的能耗開銷為

(18)

因此，用戶產生的總代價為

Ctotal=β*Etotal+(1-β)*Ttotal

(19)

在本文中，綜合考慮應用程序執行所產生的時延與能耗兩方面，從而使應用程序的總執行開銷達到最小。因此問題描述可以表示為

(20)

其中，I為用戶的卸載決策集。C1是應用程序的時延約束，要求時延不能超過所要求的最大延遲。C2表示任務只能執行在一個地方。根據P1，我們可以知道，該問題是一個混合整數規劃和NP難問題。

3 算法設計

如上所述，為了減少任務計算完成所產生的能耗與時延，在本節中，提出了深度強化學習算法來解決資源分配和任務調度策略。

3.1 強化學習設計

在本小節中，我們將計算卸載優化問題表述為深度強化學習(DRL)過程。在獲得當前移動邊緣計算網絡狀態之后，我們的目標是通過最小化整個網絡架構下的時延和能耗開銷來提高計算卸載效率。由于變量、環境狀態和系統動作的巨大空間隨時間動態變化，用傳統的優化方法幾乎不可能解決這個復雜的問題，但是，深度強化學習方法卻能很好的解決這個問題。由于移動邊緣計算網絡架構用戶動態請求和資源隨機分配，計算卸載策略算法應該考慮MEC環境的狀態來做出有利的決策。因此，在本節中，我們提出了一種基于DQN的資源分配算法，以最小化時延和能耗的開銷并以自適應的方式平衡資源分配。

RL系統可以通過探索環境和接收反饋來形成自適應模型，而無需大量標記數據。它只是適應我們考慮的多變的MEC環境。如第2節所述，傳統的Q-learning使用Q-table來存儲Q值，當環境的狀態復雜多變時，將所有Q值存儲在一張表中是不切實際的，而且在一張大表中頻繁搜索狀態也很耗時。因此，我們采用上述DQN來實現我們的DRLRA，其直接通過神經網絡生成對應的Q值，即以MEC環境狀態作為輸入，每個可能動作的Q值作為輸出。我們提出的算法的訓練階段如下所述。我們的DRLRA使用的DRL系統包含狀態、動作和獎勵等3個關鍵要素，應首先定義：

狀態：強化學習目的是不斷從歷史信息中學習策略，考慮到用戶產生的任務、網絡情況、可用計算資源，狀態空間由應用產生的任務列表及當前產生的開銷組成，定義時刻t狀態向量可以表示為St=[c，n]t動作：在我們的DRL系統中，將終端用戶看作是一個決策者，決定在當前的狀態下應該選取怎樣的策略。動作由用戶任務可卸載的位置組成，動作向量可以給出為At=[Etar]t，Etar∈{-1，M}， 其中M為邊緣服務器的個數。Etar的值表示當前用戶的任務請求所采取的動作，即決定卸載的位置。

3.2 基于深度強化學習的卸載策略算法設計

基于上一節的強化學習狀態空間、動作空間以及獎勵值的設計，設計基于深度強化學習的卸載策略算法。算法首先初始化深度強化學習的相關參數和移動邊緣計算網絡下的用戶、邊緣服務器以及云服務器，每個用戶通過訓練獲得卸載策略。先生成初始狀態，并開始一個時間段的訓練，通過運行當前的決策網絡選擇當前狀態的動作值at，執行at并獲得獎勵rt和新的狀態st+1，并將狀態轉移過程存儲到經驗池中，并從經驗池中隨機采取一個小批量的樣本 (sj，aj，rj，sj+1) 進行訓練，根據損失函數不斷優化神經網絡參數，最終得到卸載策略。具體的算法如算法1所示。

算法1：基于DQN的計算卸載策略

初始化經驗池的大小為D，目標Q網絡的更新頻率為C

初始化邊緣服務器M，云服務器，用戶數量N

隨機初始化Q網絡的權值θ，目標Q網絡的權值θ-=θ

Forepisode= 1，Edo

初始化初始狀態s1

Fort=1，Tdo：

以概率ε隨機選擇動作at

若上一步中的概率ε沒有發生，則利用貪婪策略選擇當前函數值最大的動作at=maxaQ*(st，a；θ)

執行at并獲得獎勵rt和新的狀態st+1

將狀態轉移過程即經驗 (st，at，rt，st+1) 存儲在D中

從D中隨機采取一個小批量的樣本 (sj，aj，rj，sj+1) 進行訓練

根據損失函數 (yj-Q(sj+1，at；θ)))2對參數θ進行梯度下降更新

每間隔C個步長更新一次目標網絡權值θ-=θ

End for

End for

4 實驗結果分析

4.1 實驗設置

在本節中，考慮多用戶多邊緣服務器基站的移動邊緣計算網絡環境，所以考慮了本地卸載策略、MEC隨機卸載策略、云端卸載策略、貪婪卸載策略4種算法與本文提出的算法進行對比，并對它們的實驗結果進行比較分析。

本地卸載策略指的是終端設備選擇將任務全部卸載在本地進行計算，MEC隨機卸載策略指的是隨機將任務卸載在所在區域的邊緣服務器上進行計算，云端卸載策略指的是將任務全部卸載在云服務器上，貪婪卸載策略指的是將任務卸載在當前網絡中的最佳卸載位置。算法的參數設置見表1。

表1 仿真參數

4.2 結果分析

在本節中，先分析了算法的收斂性，接著通過將本文所提出的算法與其它的基準算法進行對比，驗證了算法的有效性。

系統獎勵值變化如圖2所示，隨著迭代次數變化獎勵值也不斷變化，它代表著算法的收斂性，從圖中可以看到隨著迭代次數的不斷增加，強化學習訓練所獲得的獎勵回報值不斷增大且最終趨向于平穩，大概200次迭代時候，獎勵值收斂到一個相比較穩定的值，網絡參數達到相對穩定狀態，表明網絡達到了穩定最優狀態，所有網絡輸出的卸載策略不再存在隨機性，而是根據當前的狀態空間、網絡環境擇優選擇。

圖2 系統獎勵值變化

不同的MEC服務器個數設置對設備開銷的影響如圖3所示。橫坐標是MEC服務器的個數，縱坐標是整個移動邊緣計算網絡環境中所有用戶的總開銷。設置MEC服務器的個數為5、6、7，然后采用本地卸載策略、MEC隨機卸載策略、云端卸載策略、貪婪卸載策略及DQN卸載策略算法進行卸載，并進行對比查看性能，首先可以看到在這5種卸載策略中，DQN卸載策略算法可以更好降低系統的開銷，以MEC數量為5進行實驗結果分析，本文所提出的DQN卸載策略算法與本地卸載策略、MEC隨機卸載策略、云端卸載策略以及貪婪卸載策略相比，優化率分別達到了79.5%、55%、65.3%、31.2%。因為本地卸載策略是用戶全部選擇在本地計算，所以沒有利用邊緣計算服務器的計算能力強的優勢，導致開銷很大。MEC隨機卸載策略，因為是隨機選取卸載位置，所以卸載位置隨機，且邊緣服務器如果位置不當，也會產生較高的排隊時延和傳輸時延，所以整體開銷也較高。云端卸載策略選擇全部在云服務器計算，傳輸距離較遠，沒有綜合考慮任務特點和MEC服務器的優勢，因此開銷也很大。貪婪算法是針對當前用戶的任務去選擇局部的最優卸載位置，但沒有全局考慮，雖然相比較前3種算法有所改進，但產生的時延也較高，而DQN采用強化學習的獎勵機制，以貪婪算法作為基線進行正向激勵的學習，所以產生的開銷較小，所以本文提出的卸載策略算法更優。

圖3 不同的MEC服務器個數下的設備開銷

不同用戶數下的用戶開銷如圖4所示，分別測試了用戶數量為50、60、70的情況，且設置任務的數據大小隨即生成。因為當設備數目越多時，其產生的任務越多，所需要的計算資源就越多，而MEC服務器、云服務器以及終端的智能設備的計算資源并非無限，所以如何分配資源，智能設備如何進行卸載，卸載策略顯得尤為重要。而在卸載策略選取上，可以看到DQN卸載策略有著更大的優勢。以用戶數量50為例分析該算法的性能，與本地卸載策略、MEC隨機卸載策略、云端卸載策略、貪婪卸載策略相比，其優化率分別為：79.7%、61.7%、70.2%、39.1%。

圖4 不同用戶數下的設備開銷

5 結束語

本文研究邊云協同架構下基于多設備多MEC模型的任務卸載策略。首先，建立基于邊云協同架構的系統模型，并基于該系統模型提出網絡模型、通信模型和計算模型。其次，為了滿足低能耗、低延遲的服務需求，我們以最小化系統開銷為目的，提出了聯合優化時延和能耗的目標。然后基于深度強化學習算法，設計DQN卸載策略，為每個移動用戶制定獨立高效的計算卸載策略，最終可以自適應決定將當前產生的任務放置在本地、服務器或者云端進行計算。最后，通過仿真驗證了DQN卸載策略算法的收斂性和有效性。

在未來研究中，我們將考慮用戶的移動性以及MEC服務器的存儲資源，為用戶實時提供更高效的卸載服務。