面向移動邊緣計(jì)算基于強(qiáng)化學(xué)習(xí)的計(jì)算卸載算法*

楊 戈 ，張 衡

(1.北京師范大學(xué)珠海分校 智能多媒體技術(shù)重點(diǎn)實(shí)驗(yàn)室，廣東 珠海519087；2.北京大學(xué)深圳研究生院 深圳物聯(lián)網(wǎng)智能感知技術(shù)工程實(shí)驗(yàn)室，廣東 深圳518055)

0 引言

隨著萬物互聯(lián)趨勢不斷加深，網(wǎng)絡(luò)邊緣的智能終端設(shè)備不斷增加[1-10]。 移動邊緣計(jì)算是為提升移動設(shè)備服務(wù)質(zhì)量而提出的一種具有前景的新范式[11-20]。

(1)以降低時延為優(yōu)化目標(biāo)

文獻(xiàn)[3]將卸載決策歸結(jié)為兩種時間尺度下的隨機(jī)優(yōu)化問題， 并采用馬爾科夫決策過程來處理這個問題。通過分析每個任務(wù)的平均時延和設(shè)備的平均能耗，提出了一個能量約束的時延最小化問題，并設(shè)計(jì)了一個有效的一維搜索算法找到了最優(yōu)的任務(wù)卸載策略。

文獻(xiàn)[4]提出了一種低復(fù)雜度的漸近最優(yōu)在線算法，該算法在每個時隙中通過封閉形式或二等分搜索獲得最優(yōu)解，共同決定卸載決策、移動執(zhí)行的CPU 周期頻率和計(jì)算卸載的發(fā)射功率。

文獻(xiàn)[5] 提出了一種基于云的分層車輛邊緣計(jì)算(VEC)卸載框架，在該框架中引入了附近的備用計(jì)算服務(wù)器來彌補(bǔ)MEC 服務(wù)器的不足計(jì)算資源。 基于此框架，文獻(xiàn)采用斯塔克爾伯格博弈方法設(shè)計(jì)了一種最佳的多級卸載方案，該方案可以最大程度地利用車輛和計(jì)算服務(wù)器的效用。

(2)以降低能耗為優(yōu)化目標(biāo)

文獻(xiàn)[6]將卸載決策公式化為凸優(yōu)化問題，用于在邊緣云計(jì)算能力無限和有限的兩種情況以及在計(jì)算等待時間的約束下最小化加權(quán)和移動能量消耗。 文獻(xiàn)[7]對該方案做出了改進(jìn)，相比前者降低了90%的能耗。

(3)以權(quán)衡能耗和時延為目標(biāo)

文獻(xiàn)[8]分析了單用戶MEC 系統(tǒng)的能耗延遲權(quán)衡問題，提出了一種基于Lyapunov 優(yōu)化的云卸載計(jì)劃方案以及云執(zhí)行輸出的下載調(diào)度方案。 在文獻(xiàn)[9]中擴(kuò)展到了多用戶系統(tǒng)。

文獻(xiàn)[10]研究了在多信道無線干擾環(huán)境下移動邊緣云計(jì)算的多用戶計(jì)算卸載問題。采用博弈論方法以分布式方式實(shí)現(xiàn)有效的計(jì)算卸載。

1 MEC

本文討論一個由一個訪問接入點(diǎn)(Access Point，AP)和多個移動設(shè)備組成的MEC(Mobile Edge Computing)系統(tǒng)。無線AP 可以是小型蜂窩基站，也可以是Wi-Fi AP。除了用作核心網(wǎng)絡(luò)的常規(guī)AP 之外，它還安裝了其他計(jì)算服務(wù)器作為MEC 服務(wù)器。 由于移動設(shè)備可能沒有足夠的計(jì)算能力或電池容量來完成計(jì)算密集型或?qū)ρ舆t敏感的任務(wù)，將部分工作分擔(dān)給AP 可以有效提高服務(wù)質(zhì)量，降低移動設(shè)備能耗。

MEC 系統(tǒng)包括2 個模型：任務(wù)模型、計(jì)算模型。

1.1 任務(wù)模型

本文假設(shè)計(jì)算任務(wù)按照泊松過程到達(dá)用戶設(shè)備(User Equipment，UE)，其速率為λa。 將時間劃分為單位時隙t0，獲得一個參數(shù)為pa=λat0的伯努利過程[14]。由此，UE 的任務(wù)到達(dá)時間是獨(dú)立的隨機(jī)變量， 服從帶參數(shù)pa的幾何分布。

到達(dá)的任務(wù)用二元組(La，μa)描述，其中La表示每個任務(wù)卸載到AP 所需上傳數(shù)據(jù) (例如輸入數(shù)據(jù)和程序代碼)的平均大小，μa表示完成一項(xiàng)工作所需的平均CPU周期。 任務(wù)到達(dá)后UE 根據(jù)本地狀態(tài)、MEC 服務(wù)器狀態(tài)和信道狀態(tài)進(jìn)行卸載決策(即選擇以x 的概率卸載其任務(wù))。 決策結(jié)果表示為Ak∈{0，1}，其中Ak=0 表示第k 個UE 選擇本地執(zhí)行任務(wù)，Ak=1 表示第k 個UE 選擇卸載任務(wù)到AP 執(zhí)行。

本文主要關(guān)注的是多用戶共享的MEC 服務(wù)器的計(jì)算卸載決策問題，簡化了無線通信部分，考慮了用戶在正交信道上工作的情況[15]。 因此用戶彼此之間不會受到多用戶干擾，這是目前LTE(Long Term Evolution)等通信系統(tǒng)中常見的情況。

由于傳輸任務(wù)數(shù)據(jù)的信道狀態(tài)會隨時間變化，當(dāng)任務(wù)到達(dá)并且信道太差而無法進(jìn)行數(shù)據(jù)傳輸時，UE 應(yīng)選擇本地計(jì)算，而不是等待有利的信道條件。

設(shè)hk為第k 個UE 到AP 的小尺度信道增益，k=1，2，…，N，式(1)通過香農(nóng)定理(Shannon theorem)[16]計(jì)算得出信道的可靠傳輸速率Rk：

1.2 計(jì)算模型

根據(jù)卸載策略，已卸載到AP 的任務(wù)將被推送到AP緩沖區(qū)中等待計(jì)算。 否則，任務(wù)將被推送到本地緩沖區(qū)中等待本地計(jì)算。接下來將討論本地計(jì)算模型與卸載計(jì)算模型。

1.2.1 本地計(jì)算模型

任務(wù)在本地計(jì)算時，UE 使用自己的計(jì)算能力來執(zhí)行作業(yè)。到達(dá)且為執(zhí)行的任務(wù)將排列在本地計(jì)算緩沖區(qū)中。本地計(jì)算單元的工作狀態(tài)通過本地計(jì)算緩沖區(qū)中待執(zhí)行的任務(wù)還需要幾個時隙才能完成來描述，表示為：

fm(cycles/s)表示UE 的計(jì)算能力，UE 本地的計(jì)算服務(wù)速 率為μm=fm/μa(jobs/s)。 由此，對 于每個任務(wù)，系統(tǒng)所花費(fèi)的時間(包括計(jì)算執(zhí)行時間和在任務(wù)隊(duì)列中的等待時間)可以由式(4)得出：

(2)卸載到達(dá)AP 的任務(wù)需要一些時間才能在執(zhí)行后離開AP。 這些任務(wù)將被推送到AP 緩沖區(qū)中等待計(jì)算。AP 計(jì)算單元的工作狀態(tài)通過待執(zhí)行的任務(wù)完成所需時隙來描述，表示為：

與許多現(xiàn)有的研究(如文獻(xiàn)[8]、[12]、[13])類似，本文忽略了邊緣計(jì)算的能耗，因?yàn)锳P 通常不存在能量不足的問題。

(3)任務(wù)在AP 完成計(jì)算，AP 將計(jì)算結(jié)果返回UE。類似于文獻(xiàn)[11]-[14]等許多其他相關(guān)工作，本文忽略了MEC 服務(wù)器將計(jì)算結(jié)果發(fā)送回UE 的時間開銷，假設(shè)在下行鏈路方向上保證了計(jì)算結(jié)果的順利傳輸。 因?yàn)閷τ谠S多應(yīng)用程序（例如人臉識別）而言，計(jì)算結(jié)果的大小一般遠(yuǎn)小于計(jì)算輸入數(shù)據(jù)的大小。 則組合式(8)、式(9)、式(11)，可以通過式(12)來計(jì)算任務(wù)卸載的總加權(quán)成本：

2 ODRL 算法

本文通過計(jì)算分析MEC 系統(tǒng)的延遲及功耗計(jì)算系統(tǒng)總成本，將MEC 系統(tǒng)的卸載決策看作一個以降低MEC 系統(tǒng)加權(quán)總成本為優(yōu)化目標(biāo)的隨機(jī)優(yōu)化問題，并采用強(qiáng)化學(xué)習(xí)方法求解最優(yōu)卸載策略。

強(qiáng)化學(xué)習(xí)中有狀態(tài)(state)、動作(action)、獎賞(reward)這3 個要素。 智能體(Agent，指MEC 系統(tǒng))會根據(jù)當(dāng)前狀態(tài)來采取動作，并記錄被反饋的獎賞，以便下次再到相同狀態(tài)時能采取更優(yōu)的動作。 接下來將具體到上文提出的系統(tǒng)模型中介紹。

狀態(tài)：系統(tǒng)狀態(tài)由一個二元組τ[t]=(Cl[t]，Co[t])描述。 其中，Cl[t]為本地計(jì)算單元的工作狀態(tài)，Co[t]為AP計(jì)算單元的工作狀態(tài)。

動作：根據(jù)上述決策方案，UE 將選擇以x 的概率卸載其任務(wù)，設(shè)動作集為A={xi，i=1，2，…，N}，分別為UE的n 種不同的卸載決策。

本文采用基于貪婪策略的Q-learning 方法求解優(yōu)化問題。Q-learning 是一個基于值的強(qiáng)化學(xué)習(xí)算法，其核心為Q 表(Q-table)。 Q-table 的行和列分別為狀態(tài)集S 的各個狀態(tài)和動作集A 的各個動作。 Q-table 的值Q(s，a)記錄每個狀態(tài)所對應(yīng)的各個動作的效用值，即在某一時刻的s(s∈S)狀態(tài)下，采取動作a(a∈A)能夠獲得獎賞的期望。

訓(xùn)練過程中環(huán)境會根據(jù)智能體的動作反饋相應(yīng)的獎賞，所以算法的主要思想就是將狀態(tài)集與動作集構(gòu)建成一張Q 表來存儲Q 值，然后根據(jù)Q 值來選取能夠獲得最大的獎賞的動作。

強(qiáng)化學(xué)習(xí)的訓(xùn)練目標(biāo)是最大化其(未來)總獎賞。 在算法訓(xùn)練的過程中，使用式(13)去更新Q-table：

其中，st表示當(dāng)前狀態(tài)，at表示當(dāng)前動作，st+1表示下一狀態(tài)；rt表示即時獎賞；α 表示學(xué)習(xí)速率，且0<α<1，其取值大小影響價值函數(shù)的收斂速度；γ 表示折扣因子，且0<γ<1。

為避免算法陷入局部最優(yōu)，本文采用ε-greedy 策略權(quán)衡強(qiáng)化學(xué)習(xí)的開發(fā)與探索。即智能體在已知的(s，a)二元組分布之外，以概率ε 選擇探索其他未知的動作。

3 仿真結(jié)果

3.1 實(shí)驗(yàn)環(huán)境

本文采用Python 編程實(shí)現(xiàn)仿真實(shí)驗(yàn)，表1 給出了程序?qū)崿F(xiàn)的具體環(huán)境。

表1 實(shí)驗(yàn)環(huán)境

ODRL 中的訓(xùn)練參數(shù)包括外循環(huán)次數(shù)e、折扣因子γ、學(xué)習(xí)速率α、貪婪策略ε。

一次外循環(huán)(episode)指智能體在環(huán)境里面根據(jù)某個策略執(zhí)行一系列動作到結(jié)束的這一過程，算法通過多次外循環(huán)不斷更新Q 表得到一個最優(yōu)的計(jì)算卸載策略。外循環(huán)次數(shù)e 一般要足夠大，但是如果過大，則會導(dǎo)致鄰域搜索時間過長,從而影響算法的性能。 經(jīng)過實(shí)驗(yàn)(如圖1 所示)發(fā)現(xiàn)，100 次外循環(huán)后Q 函數(shù)收斂速度放慢，獎賞提升趨勢不大，因此可以設(shè)置e≥100。

由于學(xué)習(xí)速率α(0<α<1)影響Q 函數(shù)的收斂速度，本文使用指數(shù)減緩(exponential decay)方法調(diào)整學(xué)習(xí)率，即學(xué)習(xí)率按訓(xùn)練輪數(shù)增長指數(shù)差值遞減，如式(14)所示：

其中，α′表示下一輪外循環(huán)的學(xué)習(xí)速率，α 表示當(dāng)前外循環(huán)的學(xué)習(xí)速率，e 為當(dāng)前外循環(huán)次數(shù)。

圖1 獎賞隨外循環(huán)次數(shù)增加的變化

圖2 3 種決策方法在100 次仿真實(shí)驗(yàn)中的系統(tǒng)總成本

折扣因子γ 的取值范圍為0 ≤γ<1，γ=0 表示重視即時獎賞，γ 趨于1 表示重視將來獎賞。γ 決定時間的遠(yuǎn)近對獎賞的影響程度，即犧牲當(dāng)前收益來換取長遠(yuǎn)收益的程度。 本文在實(shí)驗(yàn)中設(shè)置γ=0.5。

貪婪策略ε 表示每個狀態(tài)探索新動作的概率，ε 較大時學(xué)習(xí)過程可以快速收斂，但容易陷入局部最優(yōu)，通常取值為0.1。

本文考慮由一個AP 和多個移動設(shè)備組成的MEC系統(tǒng)。200 個UE 均勻地隨機(jī)分布在一個以AP 為中心且半徑為0≤dk≤75(單位：m)的環(huán)上。參考相關(guān)工作，本文設(shè)置了各項(xiàng)環(huán)境參數(shù)，如表2 所示[17-18]。其中，W 是取決于設(shè)備芯片架構(gòu)的能耗系數(shù)，Pt表示完成一項(xiàng)工作所需的平均CPU 周期，σ2表示每個任務(wù)卸載到AP 所需上傳數(shù)據(jù)(例如輸入數(shù)據(jù)和程序代碼)的平均大小，α 表示任務(wù)按照泊松過程到達(dá)用戶設(shè)備速率，fB表示本地計(jì)算所花費(fèi)時間的權(quán)重，fm表示本地計(jì)算能耗的權(quán)重。

表2 環(huán)境參數(shù)

3.2 對比試驗(yàn)

為了驗(yàn)證本文所提出的ODRL 在求解MEC 計(jì)算卸載的卸載決策問題的有效性，將所提出算法與兩種基線策略進(jìn)行了對比實(shí)驗(yàn)。

圖2 中給出了100 次仿真實(shí)驗(yàn)中3 種決策方法的系統(tǒng)總成本，Local execution 表示任務(wù)到達(dá)時所有UE 都選擇在本地執(zhí)行任務(wù)，Edge execution 表示所有UE 都選擇將到達(dá)的任務(wù)卸載到MEC 節(jié)點(diǎn)執(zhí)行。可以看出ODRL的平均表現(xiàn)優(yōu)于兩種對比策略，使得系統(tǒng)總成本大幅度降低。

在圖3 中，將ODRL 與兩種基線策略在MEC 服務(wù)器性能不斷提升的條件下各進(jìn)行100 次仿真實(shí)驗(yàn)，得出不同MEC 服務(wù)器性能下系統(tǒng)總成本的平均值。 從實(shí)驗(yàn)結(jié)果中可看出，ODRL 的系統(tǒng)總能耗最低，可以達(dá)到最好的效果。 隨著MEC 服務(wù)器性能的提升，被卸載任務(wù)的執(zhí)行時間縮短，ODRL 與全卸載策略產(chǎn)生的平均系統(tǒng)總成本降低。 當(dāng)本地執(zhí)行策略的總成本曲線并沒有隨著MEC 服務(wù)器性能提升而變化。 fB>5 GHz/s 時系統(tǒng)總成本下降較慢，且ODRL 與全卸載策略產(chǎn)生的平均系統(tǒng)總成本趨近。 則當(dāng)MEC 服務(wù)器性能過強(qiáng)時，系統(tǒng)總成本主要受傳輸信道條件制約。

圖3 系統(tǒng)總耗能隨著MEC 服務(wù)器性能的變化

4 結(jié)論

本文通過分析移動設(shè)備的時延和功耗，提出了一種基于強(qiáng)化學(xué)習(xí)的計(jì)算卸載決策算法ODRL。 與兩種基準(zhǔn)策略相比，ODRL 在仿真實(shí)驗(yàn)中達(dá)到了最小系統(tǒng)總成本，可以有效地提高服務(wù)質(zhì)量。在未來研究中，會進(jìn)一步考慮將算法拓展到多接入邊緣計(jì)算的場景中。