基于DRL的MEC卸載網絡競爭窗口優化

詹 御，張郭健，彭麟杰，文 軍

(電子科技大學 信息與軟件工程學院，四川 成都 610054)

0 引 言

智能手機、平板電腦、可穿戴設備等個人智能設備和物聯網設備的日新月異正在推動新服務、應用的出現，如虛擬現實(virtual reality，VR)、增強現實(augmented reality，AR)、人臉識別和移動醫療等，這些服務和應用都具有較高的計算要求。盡管現今的智能設備擁有更多的計算能力，但它們仍然無法有效地運行計算密集型的應用程序或提供穩定有效的服務。為了應對這一挑戰，多接入邊緣計算(multi-access edge computing，MEC)[1]被提出來，它將計算和存儲資源從遠程云中分出，部署在更靠近設備的一端。因此，設備的計算密集型應用任務可以被卸載到臨近的MEC服務節點上，以實現高質量的服務(quality-of-service，QoS)。物聯網設備主要通過接入點(access point，AP。例如Wi-Fi連接)請求MEC服務，如圖1所示。AP關聯到一個或多個MEC服務器，多個用戶設備(user m)接入并請求MEC服務。在物聯網中，智能設備主要用于數據采集和提供簡單的服務，其計算資源有限，需要MEC提供算力支持以達到較好的QoS。但大量的設備接入會導致接入點的競爭沖突，尤其是在公共場所、人群聚集和大量部署物聯網設備的地方，智能設備在請求MEC服務時必須要和該AP連接的其他設備競爭連接服務[2]，即競爭網絡資源把任務卸載到MEC服務器獲取計算服務。

圖1 MEC卸載網絡

MEC網絡的接入主要是無線網絡的方式，例如Wi-Fi。針對Wi-Fi的無線訪問接入協議，IEEE在2020年發布的802.11ax協議相比于之前的802.11協議較好地提高了Wi-Fi網絡效率[3]。然而，802.11ax為了確保向后兼容，基本的網絡接入傳輸數據方法保持不變[4]。這種無線網絡接入方法被稱為載波感應多路接入與避免碰撞(CSMA/CA)算法：每個待接入設備隨機“退后(backs-off)”，即在接入網絡前等待一定數量的時隙(back-off slots)。這個時隙被稱為競爭窗口(contention window，CW)。為了減少多個設備相同的隨機退避的概率，IEEE 802.11退避算法規定每次傳輸超時(碰撞)后CW會翻倍，并定義了CW的最小值和最大值。盡管這種默認的方法需要很少的計算，但是會導致低效的網絡接入，特別是在有密集接入設備的MEC網絡中，無法高效、穩健地應對網絡的快速變化[5]。

CW的選取大小對網絡性能有直接的影響，因此CW優化一直是網絡優化研究分析的主題。常規的優化方法包括使用控制理論[6]和監測活躍用戶的數量[7]。隨著具有高計算能力的網絡設備的普及，現在可以使用機器學習(machine learning，ML)方法來分析優化CW[8-10]。但ML方法的選擇受到網絡優化問題本身性質的很大限制。如分析模型[11]，可以提供最佳的CW值，但只在某些假設和準靜態設置下，所以無法依賴它們來訓練模型。無導數優化算法是較合適的選擇，強化學習(reinforcement learning，RL)就是無倒數優化算法，是較為適合用來改善無線網絡性能的ML方法[12]。因為RL涉及到智能軟件代理(網絡節點，AP)在環境(MEC卸載網絡)中采取行動(設置CW值)，以最大化獎勵(網絡吞吐量)。RL的無導數、無模型的特性，比傳統的、基于模型的優化方法有更好的泛化能力。近年來，已經有在計算機無線網絡中使用強化學習的研究：文獻[8,13]將RL應用于無線局域網的干擾對策；文獻[14]提出基于RL的通用適應性介質訪問控制(MAC)算法；用于水聲傳感器網絡的MAC方法[15]、無線網絡資源調度算法[16]以及用于調整可重新配置無線天線的方法[17]都使用了強化學習。文獻[18]也使用了RL用于網絡傳輸優化。但他們大部分使用的是Q-learning，是表格型的RL求解方法，這不適合應用在具有密集連接、網絡拓撲動態變化的MEC卸載網絡環境中。因為Q-learning存在維數災難——查找和存儲都需要消耗大量的時間和空間。文獻[19]指出，通過使用深度人工神經網絡(deep neural networks，DNN)構建深度強化學習(DRL)，可以進一步提高RL的性能，使其具有更優越的可擴展性。

因此，該文提出將DRL改進并應用于優化物聯網的MEC卸載網絡中，通過合理預測、設置CW值來優化提高MEC卸載網絡的吞吐量。改進兩種DRL方法，深度Q網絡(deep q-network，DQN)[19]和深度確定性策略梯度[20](deep deterministic policy gradient，DDPG)，使其應用在Wi-Fi作為MEC的AP的環境中。仿真實驗表明這兩種方法都提升了MEC卸載網絡的性能，特別是在密集設備接入的動態場景中，且沒有破壞網絡的公平性。

1 基于深度強化學習的MEC卸載網絡優化方法

本節研究了強化學習、深度強化學習理論方法；然后基于WiFi物聯網的MEC卸載網絡模型，建立出深度強化學習優化CW算法。

1.1 強化學習和深度強化學習

RL源自于馬爾可夫決策過程(Markov decision process，MDP)，RL的基本理論是：使用一個可以自我學習的代理agent來替代模型分析的方式去尋找最優解。agent能夠通過相應的行動action與環境environment互動(采樣state，如圖2)，每一步行動都會使agent更接近(或更遠離)其目標(獎勵，reward)。通過訓練，代理增強了其決策策略(執行什么action)，直到代理學會(獲得獎勵)了在環境的每個狀態下的最佳決策(動作順序)。在DRL中，代理的決策是由一個DNN訓練得到的。該文考慮了兩種不同行動空間的DRL方法：DQN的離散動作策略和DDPG的連續動作策略。DQN試圖預測每個動作的預期獎勵，即是基于價值(獎勵，reward)的方法。與基本的RL相比，DQN附加了深度神經網絡，可以更有效地推斷出尚未觀察到的狀態的獎勵。與DQN不同，DDPG是基于策略(動作，action)的方法，它試圖直接學習最優策略，可以產生連續的動作輸出。DDPG包括兩個神經網絡：一個行動者(actor)網絡和一個評判者(critic)網絡。行動者根據環境狀態做出決定動作，而評判者是一個類似DQN的神經網絡，試圖學習行動者行動的預期獎勵收益。

圖2 強化學習模型

為了將DRL應用于MEC計算卸載網絡，該文做了一個映射，一個代理(部署在AP上)、環境狀態(網絡環境)、可用的行動(設置相應的CW值)和收到的獎勵(網絡吞吐量)。AP上的代理是觀察網絡的狀態，設置CW值(動作)，以使網絡性能(獎勵)最大化。

1.2 MEC卸載網絡優化的DRL原理

作為MDP的改進版，RL是在不知道可觀察到的狀態以及不知道每個狀態的轉移概率時解決MDP問題的方法。實際上，RL是一個部分可觀察的馬爾可夫決策過程(partially observable Markov decision process，POMDP)，它假定不可以完全觀察到環境的所有狀態，從部分狀態和歷史經驗中推測新狀態和預期的獎勵。POMDP表示為(S,A,T,R,Ω,O,λ):

S:狀態(state)集合；

A:動作(action)集合；

T:狀態之間轉換的概率集合；

R:獎勵函數，R=f(S,A)；

Ω:觀測結果集合；

O:觀測概率集合；

λ:折扣系數。

因為AP能觀察到網絡的全部接入，并可以通過信標數據幀(beacon frames)以集中的方式控制接入的設備，還具有處理DRL優化的計算要求，所以把代理agent部署在接入點AP上。此外，AP能夠與其他AP交換信息，可以成為基于軟件定義網絡(SDN)的多代理MEC架構的一部分[5]。

環境狀態s∈S是當前連接到網絡的所有設備的確切狀態。由于網絡的接入設備是動態變化的，不可能收集到確切的信息。因此,該問題被表述為POMDP而不是MDP。

代理的行動a∈A直接對應于設置新的CW值。在基于Wi-Fi AP的MEC中，CW有默認的最大值和最小值(CWmin=25-1=31，CWmax=210-1=1 023)[21]，在最大值和最小值的區間，如果設置一個較小的CW值，當許多設備試圖在同一時間傳輸數據，很有可能其中一些設備有相同的退避間隔。這意味著將不斷出現碰撞，對網絡性能產生嚴重影響。另一方面，如果設置較大的CW，當很少有設備傳輸數據時，它們可能會有很長的退避延遲，導致網絡性能下降。該文提出的兩方法的動作策略分別為離散的和連續的。離散的動作會輸出正整數a∈{0,1,2,3,4,5}，即agent根據環境狀態在0到5取一個整數；連續的動作會輸出一個0到5之間的實數a∈[0,5]。動作的輸出a值將被用來更新網絡的CW值，根據以下公式：

CW=?25+a」-1

(1)

即可能的動作集合A=[0,5]，每個動作執行后會更新網絡的CW值，并伴隨著網絡環境狀態s∈S的改變，產生新的環境s'∈S，環境s→s'會有一個概率轉移T(s'|s,a)。

該文對于獎勵r∈R，設置為與網絡性能——網絡吞吐量(network throughput，NT，每秒成功傳輸的比特數bits/s)，相關的變量。因為在部署了agent的AP上，可以較為容易、及時地獲取到當前時間的網絡吞吐量。其次，對于標準的DRL的獎勵是在0到1之間的一個實數，因此對獎勵r做歸一化處理，用觀察到的每秒比特數除以預期的最大吞吐量：

(2)

每次觀察環境狀態為ω∈Ω，它表示為agent根據觀察信息所得的網絡當前最大可能的狀態。對每個觀察到的環境有一個觀測概率o∈O，表示在網絡中觀察到的當前碰撞概率pcollision(傳輸失效概率)，該概率根據傳輸的數據幀的數量Nt和正確接收的數據幀的數量Nr來計算：

(3)

pcollision的值直接反映了動作action選取的CW值的優劣性。一般的，AP上的agent不能直接獲取，但是AP作為總的接入點，作為發送方或接收方參與了所有數據幀的傳輸，通過數據幀的數據位綁定Nt，AP能夠獲取到設備的Nt，對于Nr可以直接在AP端統計得到。

1.3 DRL優化MEC卸載網絡

對于該文的兩種DRL(DQN和DDPG)的理論推導和性質，就不做展開，讀者可以參考文獻[20-21]來輔助理解兩種DRL的性質和異同。使用Wi-Fi作為AP，默認的CW設置按照標準的802.11協議規則，即指數退避算法(exponential back-off algorithm，EBA)[21]，在[0-CW]中選擇隨機退避時隙，當沖突發生時，CW在限制大小內以2的指數遞增(CW∈[CWmin,CWmax]) 。參考標準EBA，該文改進兩個DRL方法——DQN和DDPG，用于優化MEC計算卸載網絡。通過DRL優化網絡的CW值，最大化全局網絡吞吐量為獎勵——優化目標，以提升網絡的效率。如圖3所示，agent部署在AP上，獲取網絡環境狀態，設置相應的CW值來獲取最大化全局網絡吞吐量。

圖3 DRL優化MEC卸載網絡模型。

agent分別基于DQN和DDPG，它們的區別在于：DDPG實質上是DQN的一種在連續動作上的擴展算法，DDPG在DQN的基礎上多了一些決策(policy)系列的操作。因此對于DQN和DDPG，該文設計了同樣的CW優化算法：

DRL-CW優化算法:

1.初始化觀測Bobs，長度為h

2.獲取agent的動作函數參數θ

3.獲取agent的動作函數Aθ

4.定義變量收、發幀數Nr，Nt

5.設置交互時間周期Δt

6.獲取訓練標志位isTrain

7.設置重放緩存B

8.最新更新時間設置為當前時間:

lastupdate←currenttime

9.初始化CW←31

10.初始化狀態向量s

11.fort=1,2,…,∞ do:

12.獲取Nt，Nr

13.把Nt，Nr放入Bobs中

14.if (lastupdate+Δt)≤currenttime:

15.obs←getObs(Bobs)#生成觀察值

16.a←Aθ(obs)#生成執行動作值

17.CW←(?25+a」-1)#更新CW

18.if isTrain :

19.NT←(Nr/Δt)#計算有效網絡吞吐量

20．r←normailization(NT)#獎勵

21.把(obs,a,r,s)放入B中

22.s←obs

23.b←從B中小批量取樣

24.用b訓練優化Aθ的參數θ

getObs()根據當前網絡的收發狀態生成相應的狀態值。

normailization()的功能是歸一化獎勵值，參考公式(2)。

模塊getObs()用于計算最近觀察到的碰撞概率H(pcollision)歷史的平均值和標準偏差，由一個固定大小(h/2)和步長(h/4)滑動窗口決定。滑動窗口的采樣將Bobs數據從一維變為二維(滑動窗口的每一步產生兩個數據點)。這樣產生的數據可以被看作是一個時間序列(窗口的每一步對應一組數據，每組數據具有前后的時間順序，且狀態的觀測值也在不斷更新)，意味著可以用循環神經網絡(RNN)分析它。因為，與使用全連接神經網絡進行訓練分析優化相比，RNN的設計[22]可以更深入地學習到agent的行為與網絡性能之間的直接和間接關系。

2 仿真實驗設置

實驗是基于ns3-gym[23]網絡仿真平臺實現的，ns3-gym融合了強化學習RL的開發分析工具OpenAI Gym。另外，基于ns3-gym，使用Python開發實現了DQN和DDPG的神經網絡。實驗在Ubuntu 18.04.5 LTS下進行，軟件版本：Python (3.6.5)；TensorFlow (1.14.0)；Torch (0.4.1)。

2.1 仿真平臺的網絡模型設置

在ns3-gym網絡仿真平臺，搭建如圖3所示的MEC計算卸載網絡模型，其相關參數如下：Radio Channels：error-free, 20 MHz；Protocol：IEEE 802.11ax；Modulation：1024-QAM；Coding Rate：5/6；Transmissions：single-user；Frame-Aggregation：Disabled；Transport Layer：UDP, 1500 byte packets。

為了方便DRL的訓練和應用，做了如下的實驗條件假設：(1)連接到AP的設備能完整、快速地把自身網絡狀態信息傳遞給AP，即AP可以立即得到Nt，Nr；(2)agent可以立即更新設置各個連接設備的CW值。這樣的假設是合理的，因為基于Wi-Fi作為AP的MEC計算卸載網絡類似小范圍的局域網，傳輸延遲可以忽略不計。如果考慮了傳輸延遲，會導致DRL的學習周期較長，收斂較慢。因此，在該實驗中，不考慮延遲的因素，但這不影響實際的應用。總的來說就是忽略延遲影響，但這樣的假設不會導致在實際的網絡中的應用與實驗偏差較大。

2.2 DRL的訓練過程優化

該文優化應用DQN和DDPG與MEC計算卸載網絡主要分為三個階段：(1)預訓練學習；(2)訓練學習；(3)應用階段。預學習階段先使用標準的EBA，讓整個MEC網絡環境運行起來，作為DRL訓練前的熱身階段；訓練學習階段，DQN和DDPG分別利用提出的CW優化算法來優化CW的設置；在訓練完成后是應用階段，即將訓練好的agent部署到MEC網絡中替代標準的EBA算法。

為了讓DQN和DDPG訓練穩定，學習到有效的參數，該文對這兩種方法的參數更新均采用局部(local)和目標(target)神經網絡的訓練學習方法。action的參數學習用兩個神經網絡同時學習的辦法，但CW優化算法使用在目標神經網絡的結果，目標神經網絡定期獲取局部神經網絡的參數wlocal來更新自己的網絡參數wtarget:

wtarget=τ×wlocal+(1-τ)×wtarget

(4)

通過這樣的訓練方式，在一個時間段內固定目標網絡中的參數，定期按公式(4)來更新參數，達到穩定學習目標的效果，τ是軟更新系數，確保目標網絡參數的穩定更新。

對于DQN和DDPG方法的訓練參數，設置的參數如表1所示。

這些超參數設定是根據多次實驗，采用隨機網格搜索和貝葉斯優化得出的訓練、測試效果較好的參數，具備一定的參考價值。兩種算法的神經網絡使用相同的結構:一個循環的長短期記憶層(long short-term memory，LSTM)，然后是兩個密集層，形成8×128×64的網絡結構用于action的生成，即a=Aθ(st|θμ)，在t時刻狀態st決定了action的值a;μ是上述的網絡(確定性策略網絡)，θμ是它的參數，用于生成在st下的action。

表1 DRL訓練參數設置

使用LTM這類RNN可以讓agent把之前的觀察訓練經驗考慮進去。在agent的動作和網絡仿真中都加入了隨機性。每個實驗進行15輪(epoch)，前14輪為訓練學習階段，最后一輪為應用測試階段，每輪60秒(60/0.01=6 000個episodes)。每個agent與環境交互周期為0.01 s(即10 ms)，在交互周期之間執行CW優化算法。

為了讓agent盡可能的探索(exploration)，在執行每個action前都會加入一個噪聲因子(noise factor)，該噪聲因子在學習階段中逐漸衰減。對于DQN，噪聲是指用隨機的action替代agent行為的概率。對于DDPG，噪聲從高斯分布采樣并加入到代理的決策中。這樣做的目的是為了緩解DRL的本身的exploration-exploitation的問題——尋找新經驗(exploration)和通過已知策略獲得最大化獎勵(exploitation)是矛盾的，不能兼得。具體實現如下：

噪聲幫助DRL進行explorationDQN:A'θ(st)=random(Aθ(st|θμ),random(A))DDPG:A'θ(st)=Aθ(st|θμ)+noise#A'θ(st)是由確定性策略(DPG)加噪音得到的

在DQN執行動作a之前，加入一個隨機噪音，即有較小的概率選擇從動作庫A中隨機選擇一個動作來執行，保證了算法的exploration。在DDPG中也是類似的，不過因為DDPG是連續動作，不適合隨機選取，就在其后加上一個較小的noise來實現。同樣保證了agent的exploration性，以適應新的環境狀態。

2.3 實驗基線與訓練周期

該文使用802.11默認的退避算法作為實驗基線對照：標準的EBA。實驗的MEC卸載網絡拓撲環境分兩種，固定設備數量的(靜態網絡拓撲)和設備數量動態變化的(動態網絡拓撲)。接入設備數量為5到50個。上一節中，之所以設置15個epoch的訓練周期是實驗分析得到的，參考圖4：

圖4 DRL訓練獎勵變化

圖4中CR為cumulative-reward(最大化累積獎勵)，PER為per-episode-reward(是每個episode中的步進獎勵)。NX的意思是多少個設備(N15即15個設備接入)。圖中展示了DQN和DDPG在15、30個設備接入的靜態網絡拓撲結構下，經過12個epoch左右的訓練便可獲得基本趨于穩定的獎勵，即在12個epoch的訓練學習后可以使模型收斂。后續實驗統一使用15個epoch的實驗周期，即保障在12個以上使模型收斂，且無需更多的epoch。

3 實驗結果與分析

3.1 靜態網絡拓撲實驗結果

在靜態網絡拓撲結構中，整個實驗過程中都有固定數量的站點連接到AP。從理論上講，恒定的某個CW值是可以達到最佳的網絡性能[5]。靜態場景的實驗是為了測試DRL算法經過訓練學習是否能夠實現最佳的CW設定，以及與標準802.11的EBA基線相比有什么差異。圖5(a)是在不同數量{5,15,30,50}連接設備下多次實驗的統計平均結果，置信區間為95%。

圖5 靜態(a)和動態(b)網絡拓撲中各 方法網絡性能的對比

從圖中的結果可見，標準的EBA的性能在較多的設備接入MEC計算卸載網絡時，網絡的整體性能有明顯的下降，但DDPG和DQN可以在靜態網絡條件下優化CW值以應對網絡拓撲的變化。與標準的EBA相比，在較少的設備連接時(5個)，DRL能提升約6%的性能；在較多設備連接時(50個)，約有46%的提升。

3.2 動態網絡拓撲實驗結果

在動態網絡拓撲的環境下，每次實驗過程中，接入設備的數量從5個以每次5個的速度遞增，這樣做的目的是為了增加MEC計算卸載網絡中的碰撞率，測試算法是否能夠對網絡變化，做出合適的反應來穩定網絡性能。

在圖6(a)中，左邊的縱坐標展示的是網絡性能，右邊的縱坐標展示的是接入設備的數量，橫坐標是實驗時間。接入設備數量從5增加到50，各個方法的性能變化如圖中各線所示，各方法對CW的設定效果反映在網絡的瞬時吞吐量上；兩種DRL方法與EBA對比可見，有較好的穩定性，在設備數量增加到50時，DQN和DDPG都可以保持網絡性能的穩定，網絡吞吐量沒有明顯的下降。再參考動態網絡拓撲的多次實驗均值結果圖5(b)(類似于圖5(a))，可見DRL優化CW值的方法可以較好地優化MEC卸載網絡多接入情景下的網絡性能，且具有優于標準EBA方法的效果(50個接入設備時DRL約有36%的相對提升)。

圖6 動態網絡拓撲中各方法的瞬時 性能對比(a)與CW設置(b)

對于DRL如何設置相應的CW，該文給出動態網絡拓撲中一個接入設備的CW值變化情況，如圖6(b)所示。不同的DRL方法所展現的CW不一樣，因為DQN是離散動作類型的RL方法，而DDPG是連續動作型的，其本質原理可參考公式(1)及其說明。DDPG的連續動作機制可以比DQN優化的CW值更快速變化，可以更好地適應網絡的動態變化；標準的指數退避EBA作為參考，但其被DQN的畫線所覆蓋。

3.3 DRL是否有失公平

因為設備都是相互競爭地接入AP請求MEC計算卸載服務，針對CW值的優化算法是否會導致接入設備的不公平競爭也是需要考慮的問題。該文使用Jain’s fairness index[24]來評價網絡的公平性，計算公式如下(0

(5)

其中，Ti為第i個設備的平均網絡吞吐量，n為設備的總個數。

實驗計算結果如圖7所示。

從圖7的實驗結果來看，DRL方法并沒有讓網絡失去公平性，幾乎與標準的BEA保持一致。

圖7 動態網絡拓撲下各方法的公平性

4 結束語

該文提出兩種DRL：DQN和DDPG方法，用于解決IoT的MEC卸載網絡場景下面對大量接入設備時使用標準EBA導致網絡性能下降的問題。提出針對Wi-Fi作為MEC卸載網絡AP的CW值優化算法，應用DRL方法訓練CW優化算法后在不同網絡拓撲下可以有效地設置合理的CW值以穩定網絡的吞吐量。實驗結果表明，DRL可以解決CW優化問題：即使在快速變化的網絡拓撲結構下，兩種算法都具有穩定網絡性能的能力，DDPG連續動作的方法略優于離散動作的DQN。最后，實驗在靜態和動態網絡拓撲環境下的結果都表明了DRL方法優于默認的退避算法，且沒有破壞網絡的公平性。