移動邊緣計算網絡中的資源分配與定價①

呂曉東,邢煥來,宋富洪,王心漢

1(西南交通大學 信息科學與技術學院,成都 610031)

2(西南交通大學 計算機與人工智能學院,成都 610031)

1 引言

隨著移動應用和物聯網的快速發展,功率和計算資源有限的移動設備(MDs)不再滿足資源密集型應用的嚴格要求,如低延遲、高可靠性、用戶體驗連續性的要求[1].在移動邊緣計算(MEC)中,網絡運營商和服務提供商進行合作,在網絡邊緣提供優秀的通信和計算資源,以增強MD 能力[2].

在MEC 中,計算資源的管理在提高資源利用率和優化系統資源效益方面起著至關重要的作用[3].由MEC服務器處理外部任務會消耗本地計算資源.因此,每個MD 根據某種資源定價機制支付一定的服務費,以激勵邊緣云提供足夠的計算資源.

現有的定價機制,如基于拍賣的,依賴于中間機構的靜態定價[4-6].拍賣雙方都需要向中介提供的服務支付費用.總成本的增加使得雙方都無法從資源交易中獲得最佳的利益.同時,靜態定價也不能適應MD 不斷變化的資源需求.在這種情況下,MEC 服務器很難有效地利用其本地資源.因此,一個關鍵的問題是如何有效地將有限的MEC 資源分配給具有不同需求和偏好的相互競爭的MD.為此,我們將MEC 環境中的多資源分配和定價問題表述為一個包含一個領導者和多個跟隨者的多階段Stackelberg 博弈,其中所有MEC 服務器同時將它們的實時價格發送到一個聚合平臺(AP).在第1 階段,通過MEC 服務器公布的價格,AP 通過解決一個效用最大化問題來找到最優的資源分配解決方案.在第2 階段,基于環境的反饋(即資源如何分配給MDs),我們利用多代理近端策略優化(MAPPO)算法[7]學習每個MEC 服務器的最優定價策略,這種策略不需要MEC 服務器獲取其他MEC 服務器實現的定價策略就可以做出最優的決策.

我們的主要貢獻如下: (1)我們通過構建一個Stackelberg 的領導者-跟隨者博弈,充分考慮了AP 和MEC 服務器之間的互動以及服務器之間的競爭.納什均衡給出了完全競爭的合理結果.(2)該算法基于MAPPO,這是一種具有集中式訓練和分布式執行的深度強化學習算法,能夠適應環境動力學和參數的不確定性.每個MEC 服務器作為一個智能體,不斷地與環境交互,以生成一系列的培訓經驗.智能體既不需要事先了解MEC 資源的折扣成本,也不需要知道其他智能體所采取的行動.因此,信號傳遞的開銷就大大減少了.(3)仿真結果表明,該算法可以為每個MEC 服務器學習一個優秀的策略,以確定其資源的單價.

2 相關工作

邊緣系統的最優資源分配和定價已經引起了越來越多的研究關注.主要有兩個研究方向: 定價導向因素和最優定價策略.

定價導向因素.Dong 等人[8]提出了一種云計算資源定價算法,分析歷史資源使用情況并不斷調整資源價格.但該算法只考慮了資源利用率,沒有分析其他重要因素.Liu 等人[9]提出了一種基于價格的分布式算法,只強調了任務調度.Li 等人[10]提出了云計算的靜態資源定價方案.定價操作簡單,但難以滿足終端設備的動態需求.他們沒有考慮用戶需求與資源價格之間的實時關系,因此不能根據用戶需求動態調整資源價格.

最優定價策略.現有的最優定價策略大多是基于拍賣和博弈論的.Zhang 等人[11]研究了通過基于拍賣的算法對系統效益和多維資源的聯合優化.解決方案是系統性能改進和單位效益的產物.然而,該算法以每一輪拍賣為優化目標,難以接近全局最優.因此,執行成本非常高.Dong 等人[12]采用了一種基于價格的雙層Stackelberg 博弈來模擬一個由單個MEC 服務器和多個用戶組成的MEC 系統.

3 系統模型

3.1 網絡模型

MEC 系統模型由多個利益相關者組成: (1)希望出售免費資源的MEC 服務器; (2)希望購買資源以執行計算任務的MD; (3)AP 作為第三方代理,代表MD 從MEC 服務器購買資源.不失一般性,我們考慮一個通用的“多對多”場景,即每個MEC 都可以將資源出售給多個MD.同時,每個MD 可以購買多個MEC 服務器出售的資源.

我們考慮一個具有多個MD 和具有多種類型資源的多個MEC 服務器的MEC 系統.我們用U={1,2,···,U}和M={1,2,···,M}分別表示MD 和MEC 服務器的集合.R={1,2,···,R}表示資源種類的集合.我們有|U|=U,|M|=M,|R|=R.MEC 服務器和MD 之間的相互作用總結如下:

(1)MEC 服務器i∈M,希望出售空閑資源r∈R,于是向AP 告知它的可用資源數量Qi,r和其單位資源的期望價格pi,r.

(2)給定價格pi,r和可用資源數量Qi,r,MDj∈U決定從每個MEC 服務器購買的資源數量

(3)MDj使用所購買的資源來處理其計算任務.

3.2 多階段Stackelberg 博弈

Stackelberg 領導者-跟隨者博弈是一個策略游戲,其中領導者承諾一個策略,然后跟隨者跟隨[13].一般來說,游戲中的所有玩家都是自私的,因為他們每個人都考慮了他人的策略來最大化自己的利益.具體來說,考慮到跟隨者可能采取的策略,領導者選擇了一種最大化其利益的策略.基于觀察領導者的策略,每個跟隨者都采用了使其利益最大化的策略.然后,我們解釋了跟隨者之間的競爭.通過MAPPO 算法,得到了每個跟隨者的最佳響應.在這個算法中,每個跟隨者都與環境交互,并學習一種策略來優化其長期獎勵,而不需要考慮他人采取的行動.Stackelberg 領導者-跟隨者博弈的定義如下:

玩家: AP 和MEC 服務器都是游戲玩家.AP 是領導者,而所有的MEC 服務器都是跟隨者.

策略: 對于MEC 服務器i∈M,他的策略是確定資源r∈R的單價; 對于AP,策略是確定MDj∈U從MEC服務器處購買的資源r的數量.

收益: MEC 服務器、MD 和AP 的收益函數分別由式(1)-式(3)給出.

令xi.j.r表示MDj∈U從MEC 服務器i∈M處購買的資源r∈R的數量.MEC 服務器i的收益計算如下:

其中,pi,r表示MEC 服務器i的資源r的單價,xi={xi,j,r}j∈U,r∈R,pi={pi,r}j∈U.

MDj的收益定義如下:

其中,xj={xi,j,r}i∈M,r∈R,p={pi,r}i∈M,j∈U,ωi,j,r是MEC 服務器i出售給MDj的資源r的質量.

AP 的收益是所有MEC 服務器和MD 收益的總和(即社會福利),定義如下:

其中,x={xi,j,r}i∈M,j∈U,r∈R.

由于所有資源都有獨立的預算,且彼此不受影響,因此我們可以將多資源分配和定價問題分解為多個單資源分配和定價子問題.因此,我們將優化問題分解為R個獨立的子問題,每個子問題都與特定的資源類型相關聯.與整體處理原始優化問題相比,該分解的主要優點是處理多個子問題顯著降低了計算復雜度.與r∈R相關的子問題表示為:

其中,xi,r={xi,j,r}j∈U,xr={xi,j,r}i∈M,j∈U,pr={pi,r}i∈M.

3.3 AP 社會福利優化

針對與資源r相關的子問題,給定所有MEC 服務器對資源r的單價(即pr),AP 的目標是最大化它的收益.

問題1:

其中,Qi,r是MEC 服務器i中資源r的可售賣數量,Bj,r是MDj購買資源r的預算.

定理1.問題1 的最優解如下:

其中,

證明見附錄A.

4 基于MAPPO 的AP 收益優化

本節將介紹每個MEC 服務器如何選擇其對AP所采用的策略的最佳響應.

4.1 基于深度強化學習的方法

我們使用多智能體強化學習(multi-agent reinforcement learning,MARL)來解決多重單一資源分配和定價子問題.我們將每個子問題描述為一個馬爾可夫決策過程(Markov decision process,MDP),以準確地反映資源分配和定價的決策過程.然后,我們將 MAPPO應用于這些子問題.由于其在全局優化方面的出色性能,MAPPO 可以在需要時快速為每個MEC 服務器獲得接近最優的單一資源分配和定價策略.

對于資源r,給定來自環境的反饋(即資源r如何分配給MD),每個MEC 服務器需要確定資源r的單價以最大化它的收益.

MDP 的元素如下所示,包括狀態空間、動作空間和獎勵函數.

狀態空間: MEC 服務器i在時隙t時刻的狀態空間表示為oti,包括對前面的L個時隙的觀察,如式(12)所述:

全局狀態: MAPPO 基于全局狀態s而不是本地觀察oi學習策略 πθ和值函數V?(s).我們使用所有局部觀測結果的連接來作為critic 網絡的輸入.

動作空間: 在時隙t,MEC 服務器i∈M觀察前L個時隙的資源分配情況,決定在當前時隙的單價,即pti,r.

獎勵函數: 獎勵函數定義如下:

其中,cti是MEC 服務器i的折扣成本.log 函數確保當所獲收益(即)不足以抵扣成本時,獎勵是負的.

4.2 基于MAPPO 的資源分配和定價策略(RAPMAPPO)

MARL 算法可以分為兩種框架: 集中式學習和分散式學習.集中式方法假設合作博弈,并通過學習單一策略直接擴展單智能體強化學習算法,以同時產生所有智能體的聯合動作.在分散學習中,每個智能體都優化自己的獨立獎勵; 這些方法可以解決非零和博弈,但可能會受到非平穩轉換的影響.最近的工作已經開發出兩條研究路線來彌合這兩個框架之間的差距: 集中培訓和分散執行(centralized training and decentralized execution,CTDE)和值分解(value decomposition,VD).CTDE 通過采用actor-critic 結構并學習集中的critic 來減少方差,從而改進了分散的強化學習.代表性的CTDE方法是多智能體深度確定性策略梯度(multi-agent deep deterministic policy gradient,MADDPG)[14].VD 通常與集中式Q 學習相結合,將聯合Q 函數表示為每個代理的局部Q 函數的函數[15],這已被視為許多MARL 基準測試的黃金標準.MAPPO 通過將單個近端策略優化算法(proximal policy optimization algorithms,PPO)[16]訓練與全局值函數相結合,屬于CTDE 類別.不同的是PPO 是一個on-policy 算法,MADDPG 是基于offpolicy 的算法,但是MAPPO 經過簡單的超參數調整就能獲得比較好的成績.

在RAP-MAPPO 中,每個MEC 服務器都被視為一個智能體.每個智能體都有一個參數為θ的actor 網絡和一個參數為?的critic 網絡.RAP-MAPPO 為每個智能體訓練這兩個神經網絡.我們用V?表示critic 網絡,用 πθ表示actor 網絡.我們使用統一的經驗重放緩沖區來存儲歷史數據點以進行訓練.RAP-MAPPO 是一種基于集中式訓練和分布式執行的方法.在集中訓練階段,actor 網絡只從自身獲取觀測信息,而critic 網絡獲取全局狀態.在分布式執行階段,每個代理只需要它的actor 網絡(而不需要critic 網絡).通過與環境的交互,每個代理都可以做出合適的資源分配和定價策略.

Actor 網絡被訓練用來最大化:

Critic 網絡被訓練用來最大化.

其中,是折扣獎勵.RAP-MAPPO 的訓練步驟見算法1.

算法1.RAP-MAPPO 的訓練過程初始化: 初始化actor 網絡和critic 網絡的參數1: 設置學習率step≤stemmax α 2: while 3: 令 data buffer i=1 to batch_size D={}4: for do τ=[]5:6: for t=1 to T do pat=π(ota;θ),uta～pta,vta=V(sta;?)7:utrt,ot+1,st+1 8: 計算動作 ,得到τ+=[st,ot,ut,rt,ot+1,st+1]9:images/BZ_105_405_1460_426_1491.pngA,images/BZ_105_430_1460_451_1491.pngRτ 10: 計算,將分成長度為L 的塊11: for 1=1,2,…,T //L do D=D∪(τ[l:l+L,images/BZ_105_571_1561_592_1592.pngA[l:l+L],images/BZ_105_680_1561_701_1592.pngR[l:l+L]])12:13: 從D 中隨機抽取K 個樣本L(θ)θ L(?)? 14: 通過更新,更新

5 仿真結果

5.1 參數設置

我們考慮一個由多個MEC 服務器和多個MD 組成的MEC 系統.收益最大化問題取決于可用的資源和預算.為簡單起見,我們設置ωi,j,r=1+0.1j+i/10.資源質量在整個實驗過程中都是固定的.我們將長期獎勵的折扣系數設置為零,因為自私的智能體的目標是最大化他們的即時收益.為了加快訓練過程,我們對每個智能體都采用了一個相對較小的網絡.Actor 網絡和critic 網絡都是由1 個輸入層,3 個隱藏層和1 個輸出層組成.這3 個隱藏層分別有128、64 和32 個神經元.此外,actor 網絡和critic 網絡都使用ReLU 作為所有隱藏層的激活函數,參與者網絡采用tanh 函數激活輸出層進行策略生成.其他模擬參數見表1.進行性能比較的算法如下:

表1 仿真參數

質量比例最優定價(quality proportional optimal pricing,QPOP): 我們假設AP 對每個MEC 服務器提供的資源質量有一個先驗的知識.單價設置與服務器的資源質量成正比,同時消耗確定的資源和貨幣預算(即I=0).I=0在實際系統中是不可能的,但由QPOP 找到的解決方案可以作為一個最優的基準.

隨機: 單價在(0,5)區間內隨機產生.

MADDPG: 每個MEC 服務器都被視為一個智能體,狀態空間由前L個時隙的價格和資源分配組成,動作是資源的單價,獎勵函數基于MEC 服務器的資源收入和成本設計.

5.2 收斂性

圖1 為所提出的RAP-MAPPO 和MADDPG 在不同MEC 服務器數量下的收斂曲線.隨著訓練次數的增加,MEC 服務器的平均獎勵逐漸上升,最終變為積極和穩定.我們首先研究了MEC 服務器的數量對收斂性的影響.隨著MEC 服務器的增加,這兩種算法都需要更多的時間來收斂.這是因為更多的服務器會導致更大的狀態空間.這兩種算法需要對狀態空間進行更多的探索,才能獲得可觀的獎勵.此外,MEC 服務器的平均獎勵隨著MEC 服務器的增加而降低.這是因為更多的服務器會在競爭期間降低價格,也就是說,每個服務器都希望出售其資源.然后,我們比較了兩種算法在收斂性方面的性能.我們很容易觀察到,與MADDPG 相比,RAP-MAPPO 具有收斂速度更快、平均獎勵速度更高的特點.

圖1 不同算法的收斂性曲線

5.3 MEC 服務器和MDs 在Stackelberg 均衡下的收益

我們在兩種場景下比較了這4 種算法.在第1 種場景下,Bj,r從5 到40 不等,Qi,r保持不變.在第2 種場景下,Qi,r均勻分布在[5,40]的范圍內,Bj,r固定為20.為了說明預算約束的影響,我們在實驗過程中固定了MD 的質量權重,并將M,U分別設置為4 和8.

在第1 種場景下,RAP-MAPPO 在沒有對MEC 服務器提供的資源質量的先驗知識的情況下,獲得了接近最優的性能,如圖2 所示.當MEC 服務器的資源不足時,MD 之間的激烈競爭導致了賣方市場.同時,RAPMAPPO 在社會福利方面優于MADDPG 和隨機算法(見圖3).這是因為隨機定價不能充分利用MEC 服務器的資源,而RAP-MAPPO 則鼓勵MEC 服務器動態調整其單價,以達到提高資源效率的目的.

圖2 不同MEC 資源數量下MEC 服務器收益

圖3 不同MEC 資源數量下社會福利

在第2 種場景下,從圖4 和圖5 可以看出,在大多數情況下,RAP-MAPPO 在MD 收益和社會福利方面比MADDPG 和隨機算法獲得了更好的性能.隨著MD 的平均貨幣預算的增長,MEC 服務器更有可能提高價格,以響應AP 的資源購買策略.因此,MD 需要降低他們的資源需求或支付更多的費用來鼓勵MEC 服務器銷售更多的資源,從而減少MD 的回報,即賣方市場.

圖4 不同MD 預算下MEC 服務器收益

圖5 不同MD 預算下社會福利

綜上所述,RAP-MAPPO 在MEC 服務器的收益和社會福利方面的表現優于MADDPG 和隨機算法.它的性能與QPOP 類似.QPOP 需要知道MEC 服務器的質量權重信息和MEC 服務器之間的無條件合作,而我們的方法只是基于與環境相互作用的局部觀察.

6 結論

本文研究了基于Stackelberg 博弈的資源分配和定價問題,其中AP 和MEC 服務器是領導者和追隨者.這個問題被分解為多個可以單獨解決的單一資源類型的子問題.我們采用MAPPO 來解決這個問題.對于任意的MEC 服務器,RAP-MAPPO 不需要知道其他MEC 服務器所采取的操作,這有助于減少信令開銷.此外,RAP-MAPPO 可以通過一系列的狀態-行動-獎勵觀察來指導競爭智能體實現收益最大化.仿真結果表明,在RAP-MAPPO 中,MD 和MEC 服務器在滿足前者嚴格的貨幣預算約束的同時,學習了接近最優的回報.此外,RAP-MAPPO 在收益和社會福利方面都優于QPOP、隨機和MADDPG.

附錄A.定理1 的證明

問題1 對應的拉格朗日方程是:

KKT 條件如下:

消去 λi,可得:

因此,問題1 可以被分解為如下兩個子問題.

子問題1:

子問題1 對應的拉格朗日形式的KKT 條件如下:

消去 λi,可得:

由式(25)可知:

另一方面,式(23)的可行解可推出:

因此可知:

子問題2:

子問題2 對應的拉格朗日形式的KKT 條件如下:

消去 μj,可得:

由式(30)可知:

另一方面,式(29)的可行解可推出:

因此可得:

綜上所述,問題1 的解如下: