基于深度強化學習的邊云協同串行任務卸載算法

張鳳荔，趙佳君，劉 東，王瑞錦

(1.電子科技大學信息與軟件工程學院 成都610054；2.網絡與數據安全四川省重點實驗室 成都610054)

近年來，移動應用程序在各行各業都有著廣泛的應用，但在實現諸如媒體處理、在線游戲、增強現實、虛擬現實和在移動設備中執行各種創新移動應用程序的時間、能量、成本和安全性等相關方面仍存在一些困難和挑戰。由于這些移動設備的資源限制，為了滿足應用程序運行的低延遲和高數據速率的需求，產生了一種新的計算模式——移動邊緣計算(mobile edgecomputing,MEC)[1]。

在MEC場景中，通過在用戶設備周圍的無線基站部署MEC服務器，將處于遠距離云端的計算資源延伸至網絡邊緣，為用戶設備提供物理距離更近的服務，降低由網絡延遲造成的任務時延，同時也可以緩解應用數據傳輸對核心網造成的壓力。當進行任務卸載操作時，用戶設備將計算任務數據通過無線基站傳輸至MEC服務器上進行計算，MEC服務器完成計算后將計算結果返回至用戶設備，從而完成一次任務卸載操作，如此可以使得用戶應用獲得更低的延遲體驗，變相地增加用戶設備應用程序擁有的計算能力。

目前大量的研究是基于用戶設備與MEC服務器之間的任務卸載，并未考慮云端依舊擁有大量的計算資源，且能夠針對特定場景優化計算環境的情況。在大量移動設備和物聯網設備的高度計算資源需求下，僅依靠MEC服務器進行計算是難以完成的，仍然會出現資源瓶頸。在考慮用戶設備與MEC服務器之間的網絡邊緣任務卸載的同時，還需要云端的強大計算能力來輔助MEC服務器，通過邊云協同來共同為移動設備提供相對低時延、高計算能力的服務。由于云端需要考慮網絡傳輸時延和特定任務需求，在進行任務細粒度卸載時，對任務不同的環節需要有優先級考量，這也使得整個任務卸載工作的復雜程度增加。

近幾年，移動邊緣計算任務卸載問題一直是研究熱點問題，因為任務卸載在決策時需要考慮諸多因素，在尋找最優解的過程中充滿挑戰。其中文獻[2]針對MEC服務器和用戶設備間通信和資源分配，提出了hJTORA啟發式算法，在小規模的任務卸載中，實現了相對基線算法的更優解。文獻[3]提出一種基于匈牙利和貪心算法的啟發式算法，對密集網絡下信道分配進行了優化。文獻[4]針對資源受限的串行任務，提出一種基于化學反應優化算法的MSTDOS算法，實現對串行任務細粒度卸載的優化。文獻[5]提出一種基于組合拍賣模型的算法，解決車聯網中的任務卸載問題。文獻[6]中提出了一種基于博弈論的啟發式算法，從云?邊?用戶3層結構中尋找任務卸載策略。以上文獻采用的是傳統的啟發式算法，在面對復雜環境時，計算能力會大幅下降，更好的解決辦法是采用深度學習或強化學習的方式來處理高度復雜的場景中任務卸載問題。文獻[7]提出一種AHP和DQN相結合的任務卸載算法，解決在車輛網環境下車載設備與MEC服務器間的任務卸載問題。文獻[8]基于LSTM和HER改進深度學習算法，解決單用戶多服務器的任務卸載問題，對能耗時延費用等多種指標進行比較。文獻[9]提出了一種基于DQN的MEC環境下的多任務卸載和資源分配算法。通過此方法，將混合整數非線性規劃轉變為一個RL問題，找到了更優的解決方案。

但上述研究仍存在以下不足：1)沒有考慮云邊協同問題；2)粗粒度的卸載算法缺乏靈活性。本文算法基于云?邊?用戶的3層結構，針對邊云協同場景下的任務卸載資源分配進行研究，基于Rainbow DQN[10]算法提出了一種面向邊云協同帶有權重串行任務卸載算法(edge-cloud weighted serial task offloading algorithm based on rainbow DQN,ECWS-RDQN)，考慮多用戶的串行任務卸載對MEC服務器和云端的計算資源競爭，以及不同用戶應用的優先級，以任務延遲時間、任務能量消耗和服務質量保證作為評價標準。

1 系統模型及問題定義

本文的任務卸載模型由多個移動用戶設備(UE)、擁有MEC服務器的無線基站(BS)和云端服務器(CS)組成，構成一個云?邊?用戶的3層結構，如圖1所示。用戶設備產生串行任務，MEC服務器在中間層為用戶和云端提供任務的資源分配、任務卸載調度工作，同時可以為用戶分擔一定程度的計算任務，云端則擁有強大的計算能力，可以更加快速地解決復雜計算問題，但相對邊緣服務器會擁有更高的網絡延遲。

圖1 邊云協同系統模型

其中，用戶設備用集合{1,2,···,U}表示，用戶設備擁有有限的計算資源，并且僅帶有一個串行任務Wi；每個用戶u可 以用一個5元組表示u={i,Wi,Ti,Ri,Qi}，i∈{1,2,···,u}為用戶編號；Wi是該用戶設備當前擁有的串行任務；Tu是該用戶設備當前任務的預計完成時間；Ru表示為用戶設備與無線基站的通信帶寬；Qu表示為該用戶設備的服務質量保證，該值越高代表該用戶的服務優先級越高；系統中MEC服務器用M表示，M={Cm,Tm,Rc}，其中Cm為 該MEC服務器的計算能力，Tm為該服務器當前任務的預計完成時間；云端服務器用C表示，C={Cc,Tc}，其中Cc為 該云服務器的計算能力，Tc為該服務器當前任務的預計完成時間。

用戶設備在產生任務后，會將任務卸載決策請求發送至MEC服務器，MEC服務器會根據當前系統狀態決定任務是在本地執行還是上傳至MEC服務器或是云端執行。卸載策略由X表示，其中X∈{0,1,2,3}，0表示本次策略為空操作，1表示任務將會在本地執行，2表示任務將會卸載至MEC服務器執行，3表示任務將會卸載至云端服務器執行。

1.1 串行任務模型

本文中的任務假設為多個微任務串行組成的任務，一個任務應用由多個串行微任務組成，其中微任務中的起始和末尾代表該任務中的輸入和輸出部分，并且輸入必須由本地完成。本文使用鏈表Wi={t,l},i∈{1,2,···,u}表示任務，t為當前微任務，l為下一個任務指針，其中用三元組來表示微任務t，ct為該任務計算所需的CPU周期數(cycle)，dt為該任務卸載時需要傳輸的數據量(kb)，m axT為該任務的時延上限要求(ms)。

串行任務的特點在于其任務之間的依賴關系，微任務i?1項完成才可以執行微任務i，直至執行至最后一個微任務，該項串行任務才全部執行完成。在實際應用場景中，串行任務也是最為常見的任務類型之一，如圖像識別等應用。

1.2 時延模型

時延在各種任務場景中都是一項至關重要的指標，時延表示一項任務從任務請求開始至任務全部完成的時間，并且時延大小決定了一項任務的完成時間是否可以滿足應用需求。本節中的時延為用戶設備完成其當前微任務的時延，分別從本地、邊緣和云端3個部分討論其任務時延的組成。

1.2.1本地執行

在本地執行策略中，代表該微任務會在本地進行計算，不會將數據傳輸至MEC服務器，所以當前的任務時延d Tu表示為：

式中，ct為該任務所需的CPU周期數(cycle)；fu為用戶設備的CPU頻率(Hz)。

1.2.2邊緣服務器執行

在邊緣服務器執行策略中，代表該微任務將會通過無線傳輸進行任務卸載，把計算該微任務的必要數據傳輸至MEC服務器中。在此策略中，時延由計算時延、傳輸時延、排隊時延組成，所以當前的任務時延d Tu表示為：

式中，fs為邊緣服務器的CPU周期數；為回傳數據的數據量；Ru為用戶設備和MEC服務器的傳輸速率。

1.2.3云端執行

在云端執行策略中，代表該任務將會通過無線傳輸和主干網將任務所需的數據提交至云端服務器。在此策略中，時延由計算時延、傳輸時延、傳播時延、排隊時延組成，所以當前的任務時延dTu表示為：

式中，fc為云服務器的CPU周期數；Rc為MEC服務器與云端服務器的傳輸速率；dt為MEC服務器與云端的傳播時延。

1.3 能耗模型

能耗在實際場景中也是十分重要的指標之一，采用電池供電的用戶設備會對能耗大小更加敏感。在此場景中，能耗由CPU的計算和閑置消耗、無線傳輸時的能量消耗構成，以下將會從本地、邊緣和云端3部分分別討論系統能耗的組成。

1.3.1本地執行

在本地執行策略中，將會使用本地用戶設備的CPU執行計算任務，所以該策略的執行能耗為：

式中，κ為CPU的能量效率系數[11]；fu為用戶設備的CPU周期數。

1.3.2邊緣服務器執行

在邊緣服務器執行策略中，計算任務將會提交至MEC服務器進行計算，在提交和計算的過程中，能耗由用戶設備的傳輸能耗和空閑能耗組成：

式中，Pup為用戶設備在無線傳輸時消耗的能量；Pidle為用戶設備空閑時消耗的能量。

1.3.3云端執行

在云端執行策略中，計算任務數據將會通過無線和主干網傳輸至云端服務器，能耗由用戶設備的傳輸能耗和空閑能耗組成：

1.4 服務質量保證

服務質量保證在任務調度場景中是決定不同優先級的用戶服務質量的關鍵，使得具有更低時延或能耗要求的用戶在資源競爭時會在請求中更有優勢。在此場景中，服務質量保證的組成為：

式中， α+β=1,α,β≥0；α為 基礎值；β為該目標函數中服務質量占比；qu為各用戶的優先級。

1.5 問題定義

本文的目標是使用RainbowDQN生成決策實現時延和能耗的降低，前文已經給出了時延和能耗模型，采用線性加權的方式來規劃目標函數。因此，原問題可以定義為：

式中， λe,λt,λq∈[0,1]， 并且 λe+λt+λq=1，分別表示能耗、時延和服務質量保證在目標函數中的占比。

2 算法模型

本文研究的任務卸載問題根本上是一個多目標優化問題，通常使用啟發式算法或機器學習方法。在啟發式算法中一般使用遺傳算法、粒子群算法、化學反應算法等；在機器學習領域更多采用的是強化學習方法[12]，如Q學習、DQN等[13]。在系統環境相對復雜的條件下，往往采用DQN來進行更高效的任務卸載分配工作處理。本文基于改進后的DQN?rainbow DQN。rainbow DQN是在原始DQN的基礎上結合了Double DQN、優先經驗回放(prioritized experience replay)、決 斗 網 絡(duelling network)、多步學習(multi-step learning)、分布式網絡(distributional network)、噪聲網絡(noisy network)[14-18]后改進的DQN算法，在訓練速度、樣本效率和性能方面與初始DQN算法相比有顯著的增強。

DQN作為強化學習的一種，其核心思想是通過獲取環境狀態和輸出動作互動后的獎勵，使用神經網絡來近似值函數，使用經驗回放來儲存之前經歷的數據，在更新參數時在其中選取一部分來使用。rainbowDQN采用multi-step learning更新Loss函數：

式中，A和S分別為系統狀態和動作；γ為折扣因子；R為 獎勵函數；θ為目標網絡參數；θ根據損失來更新；St為迭代時動作A t的 觀測值；a′為在St+n狀態下獎勵最優解。之后最小化Loss函數來更新網絡參數θ。

在更新后存入經驗池時，采用的是優先經驗值回放，根據損失函數來決定該項采樣的權值pt：

式中，pt將 會從損失函數中獲??；w為優先經驗回放的優先級因子?；谏鲜龈倪M以及其余擴展，在本文提出的ECWS-RDQN中，還需根據系統需求重新定義狀態空間、動作空間以及獎勵函數，在獎勵函數中引入權重來更加貼合實際的運行場景，優化串行任務調度策略。

其中動作決策值X∈{0,1,2,3}，表示對任務w做出的決策，0表示該次請求暫時跳過；1表示該任務將在本地執行；2表示該任務將卸載至MEC服務器執行；3表示該任務將卸載至云端執行。

在獎勵函數設計中，考慮到能耗、時延和服務質量等優先級問題，不同的用戶設備本身的優先級、任務組中某些微任務在不同計算場景下的效率或是系統的費用成本，都會影響每個微任務的權重。并且由于串行任務的特殊性，會導致多個任務交叉進行，僅對單個微任務的優化可能會導致某些串行任務總時延或總成本升高，所以在對單個微任務計算時延、能耗的同時，也需要對串行任務進行約束。

本文確定各項串行任務權重時，考慮當前任務計算成本標準du、參考容忍時延標準tu、用戶設備服務質量保證優先級qu這3項評價因素。權重矩陣A表示為：

計算成本和參考容忍時延使用z-score標準化所有用戶的實際使用情況作為參考標準，質量保證為用戶預設優先級。成本計算和容忍時延計算標準化如下：

利用式(12)求得當前用戶正規化值，即得到該用戶與該環境中其余用戶在時延要求和成本要求的相對值。再根據此相對值進行歸一化和區間調整，即可獲取各個用戶的權重向量，從而優化系統中串行任務的卸載執行效率，使得偏離標準的用戶可以在下一次請求中擁有更高的優先級，從而提升系統的穩定性。

結合目標函數，采用min-max標準化方法對綜合能耗、時延和服務質量3項評價指標進行歸一化，最后得到獎勵函數為：

在ECWS-RDQN算法中，當MEC服務器接收到用戶設備發送的任務卸載請求后，獲取當前系統狀態，通過計算獲得權重向量，可以根據當前狀態得到最優的卸載策略輸出。綜合以上模型，ECWSRDQN算法如下。

3 實驗設計與結果分析

本節通過python語言對本文提出算法進行仿真以評估其性能，仿真場景為云?邊?用戶3層結構，由一個云端服務器、一個帶有MEC服務器的無線基站和多個用戶設備組成。主要通過與本地計算(local)、全卸載至邊緣(MEC)、全卸載至云端(cloud)、隨機(平均)分配(random)方案、文獻[8]中的DQN方案和僅使用基于RainbowDQN算法對比本文給出的ECWS-RDQN算法。在時延、能量、服務質量等約束條件下的策略對比，來驗證算法的有效性。其中環境參數設置參考文獻[3,8]，如表1所示。

表1 環境參數設置

ECWS-RDQN算法首先針對Rainbow DQN進行優化，將串行任務拆解成多個微任務后需對獎勵值獲取頻率以及數值標準化進行處理。其中考慮環境復雜度和學習速度，學習速率設置為r=0.001，multi-step值為10；考慮其經驗-探索策略，折扣因子γ=0.99，優先經驗回放參數采用α =0.5、β =0.4[16]，噪聲網絡標準差為σ=0.01。最終本文算法的loss值收斂如圖2所示，在150 000步時基本收斂，因評估中仍會使用貪婪策略跳出，因此在步數較高等情況下還會出現波動。

圖2 Loss值隨學習步數的變化

在實驗中使用表1給出的環境配置，使用10個用戶設備來生成串行任務，總計需完成100個串行任務，每個串行任務由5個微任務組成，通過調整串行任務的生成速率和計算復雜度進行對比。

在圖3中，y軸目標函數值由目標函數歸一加權后得到，x軸為串行任務卸載請求的間隔時間，以10 ms為單位時間。對比發現在任務生成間隔較大、總的任務計算壓力較低時，卸載至邊緣服務器的效果較好。隨著間隔變短，計算傳輸量都增加的情況下，僅靠邊緣服務器已經無法承載。而使用本文提供的ECWS-RDQN算法后，各種情況下的表現都遠優于傳統策略，相較于DQN算法也有一定優勢。

圖3 目標函數值隨串行任務生成速度的變化

同樣，在固定任務間隔的情況下，改變串行任務中高計算復雜度的占比，如圖4給出的目標函數數值曲線，在計算復雜度快速升高的情況下，計算能力較低的本地設備難以完成任務；邊緣服務器由于計算量超過承載能力出現任務堆積，擁有高計算能力和高網絡延遲的云端幾乎不受影響。圖5和圖6分別從系統時延和能耗開銷兩方面進行評價，針對串行任務的權值分配策略也在任務復雜度較高的情況下，有效降低了平均時延和成本。相較于其他策略和算法，本文給出的ECWS-RDQN算法總體穩定，能夠提供更低時延、更低能耗的服務，有效提升了服務質量。

圖4 目標函數隨任務計算復雜度的變化

圖5 串行任務完成時延隨任務計算復雜度的變化

圖6 串行任務能耗成本隨任務計算復雜度的變化

而在圖7中，改變不同的計算復雜度觀察ECWSRDQN算法在不同情況下對不同優先級的用戶組的調度優化，其中獎勵值為時延、能耗的獎勵值歸一化得到?？梢钥闯鲭S著優先級的提高，更高優先級的用戶可以在時延和能耗上獲得更好的服務。

圖7 不同優先級用戶組隨計算復雜度的目標函數值變化

4 結束語

為面對邊云協同串行任務卸載調度場景，本文提出了ECWS-RDQN算法，并且針對串行任務特點進行優化，在時延、能量和服務質量的約束條件下能夠實現智能任務卸載，并且通過實驗驗證了其有效性，本算法在各項參數下均有較明顯優勢。今后將會考慮算法的細節優化，同時在通信資源分配和多服務器調度等方面進行研究。