曹騰飛,劉延亮,王曉英
(青海大學(xué) 計算機技術(shù)與應(yīng)用系,西寧 810016)
隨著互聯(lián)網(wǎng)與無線通信技術(shù)的發(fā)展,現(xiàn)代信息社會逐漸邁入了萬物互聯(lián)的物聯(lián)網(wǎng)時代[1]。以超高清視頻、虛擬現(xiàn)實(Virtual Reality,VR)、自動駕駛等為代表的各類新興移動互聯(lián)網(wǎng)業(yè)務(wù)大量涌現(xiàn)。根據(jù)中國互聯(lián)網(wǎng)信息中心(China Internet Network Information Center,CNNIC)發(fā)布的《第48 次中國互聯(lián)網(wǎng)發(fā)展狀況統(tǒng)計報告》,截至2021 年6 月,我國網(wǎng)民規(guī)模達10.11 億,較2020 年12 月增長2 175 萬,互聯(lián)網(wǎng)普及率達71.6%,較2020 年12 月提升1.2 個百分點[2]。隨著用戶數(shù)大幅增長,人們對于網(wǎng)絡(luò)多媒體資源的需求也迅速增長:我國網(wǎng)絡(luò)視頻用戶規(guī)模達9.44 億,較2020 年12 月增長1 707萬。這些數(shù)字表明人們對于計算型多媒體資源的需求增多,由于云端服務(wù)器通常遠離用戶側(cè),用戶從中獲取計算后的數(shù)據(jù)往往會導(dǎo)致較高的時延,僅依靠云服務(wù)的計算方式無法有效響應(yīng)如此龐大的資源需求。因此,也誕生了一種新的計算模型——邊緣計算(Edge Computing,EC)[3]。通過將服務(wù)資源從云端遷移到邊緣節(jié)點上,EC 可以有效降低時延,這使EC 成為提升計算型服務(wù)質(zhì)量(Quality of Service,QoS)的一種重要方法。
然而,由于當(dāng)前邊緣節(jié)點資源有限,通常不能在同一時隙內(nèi)向區(qū)域內(nèi)的所有用戶提供服務(wù),進而不能同時滿足用戶對于低時延的要求。因此,將云與邊緣節(jié)點結(jié)合進行計算成了當(dāng)前主要的研究方向。然而,由于邊緣節(jié)點的資源有限,位于云端的計算型服務(wù)不能全部轉(zhuǎn)移到邊緣節(jié)點上,邊緣節(jié)點需要自行決定應(yīng)該從云端卸載哪些服務(wù),而如何提高卸載服務(wù)效率來滿足低時延的要求成了當(dāng)前面臨的問題。相關(guān)研究者針對此類問題進行了分析[4-9],但這些工作只考慮了邊緣節(jié)點有限的計算資源,卻未考慮到邊緣節(jié)點中存儲容量有限的問題,因為資源和服務(wù)需要占據(jù)實際空間,許多計算型服務(wù)需要緩存所需服務(wù)資源至邊緣節(jié)點以滿足用戶的需求。例如,自適應(yīng)視頻流(Dynamic Adaptive Streaming over HTTP,DASH)[10]中,視頻文件以多個視頻塊的形式存儲在云端或邊緣節(jié)點中,每個塊以不同的碼率編碼,DASH 作為計算型多媒體服務(wù),需要設(shè)計算法提升用戶的體驗質(zhì)量(Quality of Experience,QoE)。在DASH 中使用由客戶端實現(xiàn)的碼率自適應(yīng)技術(shù)(Adaptive Bitrate Streaming,ABR)算法[11],將網(wǎng)絡(luò)吞吐量等信息作為輸入,輸出下一視頻塊碼率級別,視頻服務(wù)應(yīng)根據(jù)用戶所處的網(wǎng)絡(luò)環(huán)境從邊緣節(jié)點緩存中獲取合適碼率的視頻塊提供給用戶。另外,由于邊緣節(jié)點存儲資源有限,當(dāng)大量用戶從邊緣節(jié)點請求流媒體服務(wù)時,將導(dǎo)致邊緣節(jié)點的計算與存儲資源負載過大等問題,因此需要同時考慮以上兩者的約束條件,提升EC 的服務(wù)卸載效率。
近幾年,深度強化學(xué)習(xí)(Deep Reinforcement Learning,DRL)[12]算法被廣泛使用。DRL 算法具有諸多優(yōu)勢,它能從訓(xùn)練的經(jīng)驗中學(xué)習(xí)并預(yù)測最佳行為,而且能適應(yīng)不同的網(wǎng)絡(luò)環(huán)境。最具代表性的深度強化學(xué)習(xí)算法為深度Q 學(xué)習(xí)[13]。盡管已經(jīng)有將深度Q 學(xué)習(xí)應(yīng)用到EC 的相關(guān)工作[14-15],但仍無法解決因動作空間過大以及存在非法動作導(dǎo)致的模型總體收益降低等問題。本文將計算型服務(wù)卸載問題建模為馬爾可夫決策過程(Markov Decision Process,MDP),在實現(xiàn)深度Q 網(wǎng)絡(luò)(Deep Q-Network,DQN)[16]算法的基礎(chǔ)上降低算法的動作空間大小,并提出了基于改進深度強化學(xué)習(xí)的邊緣計算服務(wù)卸載(Edge Computing and Service Offloading,ECSO)算法。本文主要工作如下:
1)將邊緣計算服務(wù)卸載問題建模為存儲空間以及計算資源限制的MDP,同時將算法在邊緣計算服務(wù)卸載中節(jié)省的時間消耗視為獎勵。但由于本問題中的概率轉(zhuǎn)移矩陣在實際情況下難以實現(xiàn),需要進一步在MDP 基礎(chǔ)上實現(xiàn)深度強化學(xué)習(xí)算法。
2)提出了基于改進深度強化學(xué)習(xí)的ECSO 算法。相較于原DQN 算法,本文提出了一種新的動作行為,規(guī)避了非法動作,優(yōu)化了動作空間的大小,進而提升了算法的訓(xùn)練效率;同時,本文運用動態(tài)規(guī)劃的思想提出了動作篩選算法,針對單一服務(wù)的動作進行篩選與組合,以便得到理論收益最大的最優(yōu)動作集;并通過本文提出的動作篩選算法得到最優(yōu)動作集,進而通過比例的方式梯度下降更新網(wǎng)絡(luò)參數(shù),優(yōu)化算法決策。
3)將ECSO 算法分別與DQN、鄰近策略優(yōu)化(Proximal Policy Optimization,PPO)[17]以及最流行(Most Popular,MP)[18]算法進行仿真實驗對比。結(jié)果表明本文ECSO 算法能顯著降低邊緣計算處理時延,相較于DQN、PPO 以及MP 算法,ECSO 的算法獎勵值分別提升了7.0%、12.7%和65.6%,邊緣計算傳輸時延分別降低了13.0%、18.8%和66.4%。
邊緣計算服務(wù)卸載作為邊緣計算的一個重要領(lǐng)域,近年來被人們廣泛關(guān)注。部分研究者將這類問題視為MDP,利用最優(yōu)化方法進行求解。文獻[4]中提出了一個由用戶和網(wǎng)絡(luò)運營商聯(lián)合通信計算(Joint Communication Computing,JCC)資源分配機制組成的綜合框架,在提供優(yōu)質(zhì)通信的同時最小化資源占用;文獻[5]中提出了一種用于分配資源的框架,該框架結(jié)合了通信以及計算要素來解決移動邊緣云計算服務(wù)的按需供應(yīng)問題;文獻[6]中提出了一種基于強化學(xué)習(xí)的狀態(tài)/動作/獎勵/狀態(tài)/動作(State-Action-Reward-State-Action,SARSA)算法,以解決邊緣服務(wù)器中的資源管理問題,降低系統(tǒng)成本,并作出最佳的卸載決策;文獻[7]中探究了DQN 及PPO 算法在基于多輸入多輸出(Multiple-Input Multiple-Output,MIMO)的移動 邊緣計 算(Mobile Edge Computing,MEC)系統(tǒng)中的計算型服務(wù)卸載問題,目標是在隨機系統(tǒng)環(huán)境下最大限度地降低移動設(shè)備的功耗及卸載延遲;文獻[8]中提出了一種深度強化學(xué)習(xí)方法將任務(wù)分配到不同的邊緣服務(wù)器進行處理,以便將包括計算服務(wù)延遲和服務(wù)故障損失在內(nèi)的服務(wù)成本降至最低;文獻[9]中針對車聯(lián)網(wǎng)中車對外界的信息交換(Vehicle to Everything,V2X)網(wǎng)絡(luò)的資源分配問題進行研究,并使用Double DQN 來解決資源分配問題。然而,這些工作都基于一個未定的假設(shè)——邊緣節(jié)點能卸載并執(zhí)行所有類型的計算型任務(wù)。事實上,邊緣節(jié)點的存儲空間通常有限,并且各服務(wù)緩存策略并不一致,因而在實際中很難有效地應(yīng)用。
而對于這類服務(wù)卸載問題來說,云服務(wù)器與邊緣節(jié)點任務(wù)的分配效率以及多媒體的QoS 是需要考慮的,例如,文獻[19]中提出了一種名為BitLat 的ABR 算法以提高用戶在線視頻的QoS。而基于資源受限的MDP 建模的服務(wù)卸載問題在很多情況下屬于NP-hard 問題[20],常規(guī)的搜索方法已經(jīng)不適用于解決此類問題,因而近年來不斷有學(xué)者針對邊緣節(jié)點的服務(wù)卸載問題提出優(yōu)化理論,并取得了不錯的效果。文獻[21]針對移動邊緣計算上的在線計算與服務(wù)卸載問題,使用適應(yīng)性遺傳算法(Adaptive Genetic Algorithm,AGA)優(yōu)化深度強化學(xué)習(xí)的探索過程,相較于對比算法,它所提出的DRGO 算法能更快地收斂并得到更好的卸載策略。文獻[22]針對5G 邊緣網(wǎng)絡(luò)中的計算服務(wù)卸載問題,提出了一種高效可靠的多媒體服務(wù)優(yōu)化機制,并利用博弈理論對問題進行求解,有效提升了網(wǎng)絡(luò)傳輸性能。文獻[23]中通過擴寬服務(wù)緩存的作用,實現(xiàn)了一種基于緩存服務(wù)和計算卸載的聯(lián)合優(yōu)化算法;但該算法假定計算型服務(wù)是可分割的,而本文假定每個計算型服務(wù)為最小單元,并通過增加服務(wù)數(shù)量來表示它是可分割的,改進文獻[23]的算法以解決本文的問題。
因此,不同于以上工作,本文提出了一種基于改進深度強化學(xué)習(xí)的DRL 算法——ECSO 算法。通過對邊緣節(jié)點可用存儲資源及計算資源加以限制,并基于MDP 模型實現(xiàn)DRL算法,以解決狀態(tài)概率轉(zhuǎn)移難以預(yù)測的問題;同時,基于本文給出的動作篩選算法得到最優(yōu)動作集,降低算法動作空間的大小,進一步優(yōu)化算法決策過程,進而滿足邊緣計算服務(wù)卸載過程中對低時延的要求。
本章將分別介紹系統(tǒng)模型、MDP 以及邊緣服務(wù)卸載的定義和描述。
在本文的模型中,邊緣節(jié)點有著計算資源F以及存儲空間C,計算資源F用于服務(wù)計算,存儲空間C用于緩存服務(wù)數(shù)據(jù)。本文定義計算型服務(wù)集合為κ={1,2,…,K},時隙集合為Γ={1,2,…,T}。每個服務(wù)都有兩個屬性(ck,fk),分別表示此服務(wù)所需空間以及此服務(wù)所需計算資源,假定每個單獨的服務(wù)都是不可分割的。本文設(shè)定單一k服務(wù)帶來的下載時延為邊緣節(jié)點使單一k服務(wù)減少的傳輸時延為用戶發(fā)送請求到邊緣節(jié)點的傳輸時延定義為,由于邊緣節(jié)點算力有限,因而會帶來額外的執(zhí)行時延設(shè)定t時隙服務(wù)k的請求數(shù)量為為用戶對單一服務(wù)k的請求提供數(shù)量,表明當(dāng)邊緣節(jié)點提供單一服務(wù)k時,多個用戶請求服務(wù)k這一類服務(wù)。本文定義的環(huán)境存在實際應(yīng)用,例如,當(dāng)社會熱點新聞出現(xiàn)時,會引發(fā)大量用戶關(guān)注,此時多個用戶將請求相同的數(shù)據(jù)內(nèi)容,當(dāng)邊緣節(jié)點緩存這類數(shù)據(jù)內(nèi)容時,就可以直接向這些用戶提供服務(wù)[18]。邊緣節(jié)點不會緩存不在本地提供的服務(wù),每一時隙邊緣節(jié)點采取不同的策略來進行服務(wù)卸載,且單一時隙內(nèi)總能完成回傳數(shù)據(jù)的任務(wù)。
系統(tǒng)模型如圖1 所示,本文的目標是解決單個邊緣節(jié)點的邊緣計算服務(wù)卸載問題。
圖1 邊緣計算服務(wù)卸載模型Fig.1 Edge computing service offloading model
在該模型中,邊緣節(jié)點擁有相應(yīng)的計算資源以及存儲資源,并且邊緣節(jié)點可以記錄所有服務(wù)。系統(tǒng)模型中存在兩類過程:服務(wù)卸載過程以及邊緣計算過程。在服務(wù)卸載過程中,當(dāng)邊緣節(jié)點未緩存k服務(wù)時,從云端下載相關(guān)數(shù)據(jù)需要的下載時延為若邊緣節(jié)點滿足服務(wù)k的需求且可以提供服務(wù)時,用戶無須再上傳數(shù)據(jù)至云端計算,而只需向靠近用戶側(cè)的邊緣節(jié)點發(fā)送指定服務(wù)的卸載請求數(shù)據(jù),這個過程的時延為整個過程消耗存儲空間ck,完成服務(wù)卸載過程。而在邊緣計算過程中,當(dāng)邊緣節(jié)點向用戶提供已完成卸載的服務(wù)時,消耗計算資源fk,并消耗執(zhí)行時延完成計算。由于邊緣節(jié)點靠近用戶側(cè),當(dāng)邊緣節(jié)點卸載計算型服務(wù)時,邊緣節(jié)點可降低的傳輸時延為完成邊緣計算過程。此時如果針對單一服務(wù)k有多個服務(wù)請求時,則需要分別向多個用戶提供計算型服務(wù)k,因此資源消耗也會增加,同時累計降低的傳輸時延也會增加。
在此系統(tǒng)模型中,本文將邊緣計算服務(wù)卸載問題建模為MDP,下面將分別介紹狀態(tài)空間、動作空間以及獎勵方法。
2.2.1 狀態(tài)空間
狀態(tài)是對當(dāng)前系統(tǒng)環(huán)境的描述,而狀態(tài)空間是所有可能狀態(tài)的集合。在本文定義的問題中,狀態(tài)是時隙開始時的系統(tǒng)狀態(tài),系統(tǒng)狀態(tài)由緩存狀態(tài)和請求狀態(tài)組成。
設(shè)定邊緣節(jié)點t時隙下的服務(wù)緩存狀態(tài)為矩陣Mt,如果邊緣節(jié)點在時隙t內(nèi)緩存提供服務(wù)k,其緩存狀態(tài)=1,否則=0。同樣的,邊緣節(jié)點的請求狀態(tài)矩陣設(shè)為Dt=[],其中代表用戶對于服務(wù)k在t時隙內(nèi)的請求數(shù)量。邊緣節(jié)點需要緩存數(shù)據(jù)和服務(wù)計算,但存儲空間及計算資源有限。因此,存儲空間和計算資源需要分別滿足式(1)和式(2):
本文考慮到用戶的請求可能針對同一個服務(wù)的不同類型,當(dāng)邊緣節(jié)點對服務(wù)k進行服務(wù)卸載時,不同類型的服務(wù)請求需要緩存并計算多份數(shù)據(jù),因而存儲以及計算資源約束需要考慮請求數(shù)量矩陣Dt,具體到每一服務(wù)即為由于緩存狀態(tài)在t時隙開始時仍為t-1 時的狀態(tài),因此t時隙的狀態(tài)空間為St=(Mt-1,Dt)。
2.2.2 動作空間
動作空間就是一系列邊緣節(jié)點可能采取的動作的集合。本文定義動作矩陣At=其中∈{-1,0,1}。對于每個邊緣節(jié)點=1 表示邊緣節(jié)點在時隙t-1 不提供服務(wù)k,而在時隙t內(nèi)提供服務(wù)k。在這一動作中,用戶會向邊緣節(jié)點發(fā)送服務(wù)k的卸載請求,這個過程耗時邊緣服務(wù)器將會從云端下載服務(wù)所需服務(wù)數(shù)據(jù),經(jīng)過下載所需時延之后提供服務(wù)k;=-1 表示邊緣節(jié)點在時隙t-1 時在本地提供服務(wù)k,而在時隙t內(nèi)不在本地提供服務(wù)k。在這一動作中,由于邊緣節(jié)點只需刪除相關(guān)服務(wù)數(shù)據(jù),因此不會產(chǎn)生額外的時延;而=0 表示邊緣節(jié)點不采取任何改變狀態(tài)的行為,在時隙t的服務(wù)提供狀態(tài)與在時隙t-1 相同。
設(shè) |κ|為總服務(wù)數(shù)量,由于動作空間為一系列邊緣節(jié)點可能采取的動作的集合,因此動作空間的總大小為3|κ|,然而動作空間中也有許多無意義的動作,例如當(dāng)=0 且-1 時,表明邊緣節(jié)點并未緩存提供服務(wù)k所需的數(shù)據(jù),但邊緣節(jié)點仍要刪除這些數(shù)據(jù)。這些動作即“非法動作”。設(shè)π為滿足存儲空間及計算資源限制的所有策略的集合,那么這些動作可以表示為
狀態(tài)轉(zhuǎn)移概率是策略制定后當(dāng)前狀態(tài)轉(zhuǎn)移到新狀態(tài)的概率。對于(Mt-1,At)來說,轉(zhuǎn)移概率是確定的;但由于狀態(tài)空間還包括請求狀態(tài)Dt,它會隨著時間的推移而隨機變化,狀態(tài)轉(zhuǎn)移概率難以精確估測。這是邊緣計算服務(wù)卸載問題不能直接用MDP 來解決的根本原因。
2.2.3 獎勵方法
獎勵方法R(s,a)就是邊緣節(jié)點從狀態(tài)s執(zhí)行動作a之后得到的激勵值,正向激勵有利于提高邊緣節(jié)點在此狀態(tài)下執(zhí)行動作a的概率;負向激勵則降低邊緣節(jié)點在此狀態(tài)下執(zhí)行動作a的概率。
由2.2 節(jié)的獎勵方法可知,獎勵代表著邊緣節(jié)點在系統(tǒng)模型中總共降低的邊緣計算處理時延??偺幚頃r延越低,意味著邊緣節(jié)點越能滿足用戶對于低時延的要求,因此目標是最大化邊緣節(jié)點所獲取的長期獎勵,由式(4)給出:
s.t. 式(1),(2)
其中:γt是衰減因子,隨著時間的變化不斷減?。籖t=表示t時隙內(nèi)所有服務(wù)的獎勵之和。
本章將介紹ECSO 算法的具體實現(xiàn)以及優(yōu)化過程。傳統(tǒng)DRL(如DQN)可以作為此類問題的解決方法,但相較于DQN,ECSO 算法能更有效地降低邊緣計算處理時延,因而更適合解決此類問題。
上述MDP 不能直接應(yīng)用的原因是狀態(tài)轉(zhuǎn)移概率難以預(yù)測,且傳統(tǒng)MDP 的建模方案在一定程度上受到狀態(tài)空間和動作空間大小的限制。而DRL 算法可以很有效地解決這類問題,因為DRL 算法可以不用預(yù)先輸入任何數(shù)據(jù),主要依靠不斷的環(huán)境探索和經(jīng)驗回放來得到對應(yīng)環(huán)境下執(zhí)行動作的獎勵,并依據(jù)這些獎勵優(yōu)化模型參數(shù)。本文以DQN 為例實現(xiàn)DRL 算法。
DQN 的目標就是得到執(zhí)行動作后的預(yù)計獎勵,即Q 值。DQN 將邊緣節(jié)點的狀態(tài)作為其深度神經(jīng)網(wǎng)絡(luò)的輸入進行訓(xùn)練,得到所有動作的Q 值,以此改進依賴于表格的傳統(tǒng)強化學(xué)習(xí)算法。由此,它省略了以表格記錄Q 值的過程,直接通過深度神經(jīng)網(wǎng)絡(luò)生成Q 值,解決了無限狀態(tài)空間的問題。它的探索策略E為ε貪心策略,設(shè)定隨機概率為p,如式(5)所示:
使用ε貪心策略進行探索可以避免算法陷入局部最優(yōu)狀態(tài)。本文算法采用遞減ε貪心策略,它的參數(shù)會隨著訓(xùn)練迭代數(shù)的增加而遞減,這種策略在訓(xùn)練前期能夠探索更多的動作可能性,而后期也可以使算法減少采取隨機動作的可能性,這有助于算法的穩(wěn)定。
DQN 使用兩個神經(jīng)網(wǎng)絡(luò)進行訓(xùn)練:一個是需要訓(xùn)練的主網(wǎng)絡(luò),一個是用于生成Q 值的目標網(wǎng)絡(luò)。DQN 通過損失函數(shù)來訓(xùn)練模型參數(shù)。損失函數(shù)為目標網(wǎng)絡(luò)的估計值Qr(s,a)和主網(wǎng)絡(luò)的輸出Q(s,a)的平方差,如式(6)所示:
γ是應(yīng)用于下一步獎勵的衰減系數(shù);Q'(s',a')是目標網(wǎng)絡(luò)中對狀態(tài)s'執(zhí)行動作a'所得到的單步獎勵估計值,而則是下一步狀態(tài)s'中擁有最高Q 值估計的動作a'。
目前未經(jīng)修改過的動作空間大小為3|κ|,這個數(shù)值會隨著總服務(wù)數(shù)量的增大而呈指數(shù)型增長,當(dāng)服務(wù)數(shù)量過多時,模型訓(xùn)練將會非常困難。其次,定義的動作空間仍包括非法動作,非法動作的Q 值無意義,算法執(zhí)行和學(xué)習(xí)無意義的非法動作反而會影響它的穩(wěn)定性,因此需要采取措施優(yōu)化動作空間,以提高訓(xùn)練效率。
算法1 動作篩選算法。
對于算法1,i與j從1 開始逐漸迭代到最大值,這是為了尋找并優(yōu)先組合能夠帶來收益、且所要求的資源最小的動作,并在后續(xù)迭代中從動作集中去除對于資源要求較大的動作。如果ck大于邊緣節(jié)點所剩余的空間i,或是fk大于邊緣節(jié)點剩余的計算資源j,那么服務(wù)k就不能在邊緣節(jié)點本地提供,因而篩選后的動作集保持不變。當(dāng)邊緣節(jié)點剩余的存儲空間和可用的計算資源滿足服務(wù)k的需求時,邊緣節(jié)點可以作出兩種選擇:提供服務(wù)k,并令Rmax+=rk;或者不提供服務(wù)k,令Rmax保持不變。
算法1 的目標是盡可能在提供更多服務(wù)的情況下最大化各服務(wù)動作帶來的獎勵,而算法1 本質(zhì)上可視為動態(tài)規(guī)劃問題進行求解,求解后得到的動作集合即為能帶來最大獎勵值的動作集合。
得到最優(yōu)動作集后,由于主網(wǎng)絡(luò)和目標網(wǎng)絡(luò)輸出的是單一動作xk的Q 值,而不是整體Xt的Q 值,因此不能使用整個Xt的Q 值代替xk更新。由于Xt由篩選后的xk組成,因此,針對每個動作行為xk更新?lián)p失值的損失函數(shù)也需作出改變。對于t時刻候選動作列表Xt,根據(jù)式(6)所示的形式,定義式(8):
對于Q(St,Xt),分別計算其中每個xk動作產(chǎn)生的Q 值,Q(St,Xt)為其中所有動作行為Q 值之和,如式(10)所示:
為了得到動作列表Xt中每個xk的損失值,本文使用占比的方式計算每個xk的損失值,如式(11)所示:
本質(zhì)上,邊緣節(jié)點執(zhí)行的是各服務(wù)k的動作xk。依據(jù)算法1,每一次篩選得到的最優(yōu)動作集取決于各動作xk預(yù)期的獎勵,對應(yīng)的是主網(wǎng)絡(luò)預(yù)測的Q 值。這一時隙得到的最優(yōu)動作集與上一時隙中得到的最優(yōu)動作集會因為主網(wǎng)絡(luò)參數(shù)的更新而發(fā)生更改,各xk之間也相互獨立,因而無須考慮各服務(wù)動作xk的組合情況,也不會導(dǎo)致算法性能下降。
按照以上方法求解每個xk的損失值,就可以在更改動作空間之后使用動作行為的損失值梯度下降更新主網(wǎng)絡(luò)。
ECSO 算法流程如圖2 所示,主網(wǎng)絡(luò)與目標網(wǎng)絡(luò)有著相同的網(wǎng)絡(luò)結(jié)構(gòu),由于定義了新的動作行為xk,主網(wǎng)絡(luò)與目標網(wǎng)絡(luò)的輸出值均為xk的Q 值而不是原有動作空間的Q 值。首先,算法會根據(jù)探索策略隨機選擇執(zhí)行動作或是Q 值最高的行為執(zhí)行動作,根據(jù)算法1 篩選動作行為xk放入動作列表Xt中,并將元組(St,Xt,Rt,St+1)作為經(jīng)驗存入回放經(jīng)驗池中。之后算法隨機取出一批經(jīng)驗來訓(xùn)練主網(wǎng)絡(luò)。目標網(wǎng)絡(luò)則輸出動作列表的Q 值Q'(St+1,X')。接著算法根據(jù)主網(wǎng)絡(luò)輸出的每個Q(St,xk)以及目標網(wǎng)絡(luò)輸出的Q'(St+1,X')依次計算每個xk的損失值。并依次梯度下更新?lián)p失值,以此訓(xùn)練主網(wǎng)絡(luò),且每隔一定頻率更新目標網(wǎng)絡(luò)的網(wǎng)絡(luò)參數(shù)。算法2給出了ECSO 算法實現(xiàn)的偽代碼。
圖2 ECSO算法流程Fig.2 Flow of ECSO algorithm
算法2 ECSO 算法。
依據(jù)本文提出的ECSO 算法,通過定期更新網(wǎng)絡(luò)參數(shù),優(yōu)化目標網(wǎng)絡(luò)對于邊緣節(jié)點服務(wù)采取的動作集合Xt,從而達到優(yōu)化邊緣節(jié)點服務(wù)卸載決策的目的。
本章將介紹ECSO 算法的實驗環(huán)境以及參數(shù)設(shè)定,然后與其他DRL 算法以及傳統(tǒng)算法進行對比,根據(jù)結(jié)果驗證本文ECSO 算法更適合解決邊緣計算服務(wù)卸載的問題。值得說明的是,本文在實驗中對所有算法均設(shè)置了存儲和計算資源的條件限制。
本實驗使用TensorFlow[24]運行算法。本次實驗?zāi)M考慮50 個服務(wù),計算所需資源fk在[0.5,2.5] GHz 內(nèi)隨機取值,儲存所需資源ck在[0.2,2] GB 內(nèi)隨機取值,邊緣節(jié)點減少的傳輸時延在[2,5] s 內(nèi)隨機取值,假定服務(wù)所需的計算資源充足且充分利用,則它的執(zhí)行時延用戶發(fā)送請求到邊緣節(jié)點的傳輸時延取值取決于請求數(shù)量的多少。下載時延即為下載該服務(wù)數(shù)據(jù)需花費的時間,而帶寬決定了下載速率的理論上限,考慮到單位的換算,服務(wù)對應(yīng)的下載時延=8ck/Bandwidth,取帶寬為8 Gb/s。本文假設(shè)服務(wù)的請求頻率遵循齊夫分布[25],則平均請求數(shù)量如式(12)所示:
其中:r(k)是服務(wù)k的請求頻率的排名;N是用戶數(shù)量,在實驗中取值為150;在齊夫分布中通常取V=0.1;λ為數(shù)據(jù)分布的指數(shù)特征,在實驗中取λ=1;設(shè)定邊緣節(jié)點總計算資源為10 GHz,邊緣節(jié)點總存儲資源為10 GB。
4.2.1 云端計算與邊緣計算性能對比
為了驗證實驗環(huán)境下邊緣計算與直接由云端響應(yīng)的服務(wù)性能差異,本文將兩者進行了對比分析。
ECSO-EC(ECSO-Edge Computing):依照本文提出的算法以及模型進行運算,緩存的服務(wù)由邊緣節(jié)點提供給用戶,其他服務(wù)由云端進行響應(yīng)。
ECSO-CC(ECSO-Cloud Computing):訓(xùn)練過程不變,只是邊緣節(jié)點不再向用戶提供緩存服務(wù),轉(zhuǎn)而由云端直接進行響應(yīng)和運算,因而不考慮緩存服務(wù)帶來的下載時延以及計算時延,因此不會降低傳輸時延。
從圖3 可以看出,在訓(xùn)練的開始階段,由云端直接響應(yīng)的性能優(yōu)于由邊緣節(jié)點緩存并提供服務(wù)的性能,這是由于邊緣節(jié)點的決策還尚未被完全優(yōu)化,邊緣節(jié)點提供的服務(wù)并不能降低更多的時延。隨著訓(xùn)練回合的增加,算法能夠更好地決策,邊緣節(jié)點也能優(yōu)先向用戶提供占用資源少、請求數(shù)量多的服務(wù),因而ECSO-EC 算法能夠積累到較多正向的獎勵值。ECSO-CC 算法積累的獎勵值代表邊緣節(jié)點提供計算型服務(wù)時帶來的額外時延,同樣隨著回合數(shù)的增加而趨于較低的值。此時由邊緣節(jié)點提供計算型服務(wù)相比直接由云端響應(yīng)所降低的總處理時延更高。這也表明了由邊緣節(jié)點緩存并提供服務(wù)所帶來的性能提升。
圖3 云端響應(yīng)和邊緣計算的性能對比Fig.3 Performance comparison between cloud computing and edge conputing
4.2.2 邊緣計算中不同算法之間性能對比
本節(jié)將對比不同回合中算法的獎勵值以及單一回合中不同時隙下降低的傳輸時延。本文的ECSO、DQN 和PPO 這三種DRL 算法以及傳統(tǒng)MP 算法介紹如下:
ECSO:算法每時隙輸出自身對各個動作的預(yù)測價值,并將它們作為動作篩選算法的輸入,從而得到最優(yōu)動作集。邊緣節(jié)點每時隙按照最優(yōu)動作集提供或卸載服務(wù)。
DQN[16]:算法根據(jù)式(5)的ε 貪心算法探索得到動作并更新網(wǎng)絡(luò)參數(shù)。邊緣節(jié)點依據(jù)神經(jīng)網(wǎng)絡(luò)預(yù)測值提供以及卸載服務(wù)。
PPO[17]:算法在開始階段探索并積累動作軌跡,并且每一時隙更新動作軌跡的優(yōu)勢以及回報,一旦積累一定數(shù)量時,開始更新網(wǎng)絡(luò)策略。邊緣節(jié)點根據(jù)其中執(zhí)行者網(wǎng)絡(luò)的預(yù)測值提供或卸載服務(wù)。
MP[18]:邊緣節(jié)點根據(jù)用戶每個時隙中服務(wù)請求數(shù)量的積累計算每個服務(wù)的流行度,每一時隙中提供流行度最高的服務(wù)。由于MP 算法不具備學(xué)習(xí)能力,進行多個回合的實驗不會對MP 算法的表現(xiàn)帶來提升。因而對于傳統(tǒng)算法,本文只對比單個回合內(nèi)200 次時隙所能降低的傳輸時延。最終用于對比的獎勵值定義為算法最終降低的傳輸時延與緩存計算服務(wù)帶來的各類時延之差。
本文的目標為最大化迭代后的獎勵值。圖4 為三種DRL算法在100 次迭代中的獎勵值對比,獎勵值定義如式(3)所示,是驗證算法性能的重要指標之一。從圖4 中可以看出,本文實現(xiàn)的算法最終穩(wěn)定的獎勵值整體要高于DQN 算法,而PPO 算法前期由于需要積累動作軌跡以便積累完成后學(xué)習(xí),因此在前30 次迭代中探索得到的獎勵很低;ECSO 算法相較于DQN 算法收斂更快,這是因為ECSO 算法會預(yù)先篩選動作,排除非法的動作并執(zhí)行最優(yōu)動作。PPO 算法探索環(huán)境得到的獎勵并不穩(wěn)定,這是因為在它積累完動作軌跡之后需要從回放經(jīng)驗池中隨機取出一批樣本進行學(xué)習(xí),由于存在針對非法動作的獎勵懲罰,這就使PPO難以短時間平穩(wěn)所獲得的獎勵。而DQN 以及ECSO 算法因為使用ε貪心策略進行探索,它們探索得到的獎勵能較為平緩地增長。由于優(yōu)化了算法的動作空間,一定程度上規(guī)避了非法動作帶來的負獎勵,ECSO 算法在100次迭代內(nèi)的整體收益高于DQN 算法。PPO 算法由于收斂緩慢,雖有上升趨勢,但整體收益仍不及前兩者。
圖4 訓(xùn)練回合獎勵對比Fig.4 Comparison of rewards in different training epochs
圖5 為單一迭代中200 個時隙下幾種算法累計減少的傳輸時延。DQN 算法以及ECSO 算法能夠較快地收斂,而PPO算法卻收斂緩慢,最終固定在一個較低的值。這是因為前兩者通過ε貪心策略的探索能夠快速達到局部最優(yōu)解,從而迅速適應(yīng)環(huán)境;而PPO 算法則需要預(yù)先積累,在軌跡積累達到一定數(shù)量后開始訓(xùn)練算法中的執(zhí)行者以及評論者網(wǎng)絡(luò),而前期完成的動作軌跡中勢必存在非法行為帶來的負獎勵,因此PPO 算法在一次迭代中所減少的傳輸時延存在較大波動且數(shù)值相對較低。而對于MP 算法,累計降低的傳輸時延逐漸增加,但它的速率提升十分緩慢且低于三種DRL 算法的積累值,因而最終效果不及ECSO 的算法。而從算法200 個時隙的迭代來看,ECSO 算法相較于其他三種算法能顯著減少數(shù)據(jù)傳輸時延。
圖5 累計減少的傳輸時延對比Fig.5 Comparison of transmission latency reduction
表1 為本文實驗的四種算法訓(xùn)練至穩(wěn)定后最終的性能表現(xiàn)??梢园l(fā)現(xiàn),相較于DQN 算法,ECSO 算法的總獎勵值提升了7.0%,邊緣計算傳輸時延降低了13.0%,驗證了算法優(yōu)化的有效性;所提算法相較于PPO 算法,總獎勵值提升了12.7%,邊緣計算傳輸時延降低了18.8%,說明ECSO 算法相較于PPO 算法更適合解決本文的邊緣計算服務(wù)卸載問題。而本文所提算法相較于傳統(tǒng)算法中的MP 算法總獎勵值提升了65.6%,邊緣計算傳輸時延降低了66.4%,驗證了DRL 算法的有效性。
表1 四種算法訓(xùn)練至穩(wěn)定后最終的性能對比Tab.1 Final performance comparison of four algorithms after training to stability
低時延是邊緣計算服務(wù)卸載的基本應(yīng)用要求。為探究不同實驗參數(shù)對本文算法降低傳輸時延的影響,本節(jié)以算法獎勵值作為本文三種DRL 算法的性能指標,以MP 算法最終降低的傳輸時延與緩存計算服務(wù)帶來的各類時延之差為傳統(tǒng)算法的性能指標,在同一實驗環(huán)境中對于單一參數(shù)采取不同的值進行模擬實驗,并分析所得結(jié)果。為了減小隨機生成的數(shù)據(jù)可能導(dǎo)致的結(jié)果偏差,每個設(shè)定的參數(shù)分別運行10 次算法,并對算法趨于穩(wěn)定后得到的結(jié)果取均值作為最終數(shù)據(jù)。
4.3.1 資源限制對于算法性能的影響
圖6(a)、(b)分別為算法在不同儲存空間以及計算資源限制下所能夠降低的總處理時延。
圖6 不同儲存空間和計算資源下降低的時延對比Fig.6 Latency reduction comparison under different storage space and computing resource
從圖6 中可以看出,無論是存儲空間還是計算資源的仿真實驗,隨著資源的增多,三種DRL 算法所降低的時延均呈現(xiàn)上升趨勢,但增長速率越來越低。這是因為當(dāng)存儲空間或是計算資源增加時,能夠緩存更多所需的服務(wù)數(shù)據(jù)或是提供更多的計算型服務(wù)。以存儲空間為例,存儲空間的提升使邊緣節(jié)點能夠緩存更多的用戶所需服務(wù)的數(shù)據(jù),因而可以更加充分地利用邊緣節(jié)點剩余的計算資源。但在存儲空間提升到一定量之后,存儲空間不再是限制邊緣節(jié)點提供邊緣計算服務(wù)的因素,計算資源的不足使緩存服務(wù)無法在邊緣節(jié)點處完成計算,因而導(dǎo)致所降低的計算時延逐漸減少直至趨于穩(wěn)定。此時再提升邊緣節(jié)點的存儲空間也不會進一步降低其邊緣計算處理時延。而對于MP 算法來說,隨著資源的增多,其降低的時延沒有明顯的變化,這也說明了DRL 算法相較于傳統(tǒng)MP 算法更能適應(yīng)實驗環(huán)境的變化。
4.3.2 平均請求數(shù)量對于算法性能的影響
由式(3)可知,服務(wù)的請求數(shù)量會影響算法的獎勵值,進而也會對算法性能產(chǎn)生影響,如式(12)所示,有兩個因素影響著各服務(wù)的平均請求數(shù)量:用戶的數(shù)量以及齊夫分布參數(shù)λ的取值。
圖7 為各類算法在不同用戶數(shù)的情況下能夠降低的邊緣計算處理時延。由圖7 可知,各類算法對于用戶數(shù)呈現(xiàn)較強的線性關(guān)系,說明隨著服務(wù)平均請求數(shù)量的增加,邊緣計算處理時延降低得也越多。
圖7 不同用戶數(shù)量下降低的時延Fig.7 Latency reduction under different number of users
圖8 為ECSO 算法在不同λ取值下降低的邊緣計算處理時延(Total)以及對于每個服務(wù)所能平均降低的時延(Average)。由圖8 可知,隨著λ的增大,算法所能降低的處理時延越來越少。這是由于隨著λ的增大,每個服務(wù)的平均請求數(shù)量也隨之降低,進而導(dǎo)致算法所能降低的時延更少。但總共降低的時延越多并不意味著對于每個服務(wù)的請求所平均降低的時延越多,因此本文將算法總共能降低的時延與服務(wù)請求數(shù)量相除,得到算法對于每個服務(wù)請求所能平均降低的時延。由圖8 可以看到,隨著λ的增大,每個服務(wù)平均降低的時延反而越多。這是因為λ的增大會導(dǎo)致用戶對各類服務(wù)的請求更集中,下載服務(wù)數(shù)據(jù)所導(dǎo)致的下載時延也就越低,因而對于每一請求,平均降低的時延也越多。
圖8 不同λ參數(shù)下降低的時延Fig.8 Latency reduction under different λ parameters
本文研究了存儲空間以及計算資源限制情況下的邊緣計算服務(wù)卸載問題。首先將問題建模為馬爾可夫決策過程,旨在最大化長期獎勵,也就是邊緣節(jié)點長期所降低的處理時延;其次提出了ECSO 算法,在DQN 算法的基礎(chǔ)上提出了一種新的動作行為,將動作空間大小從3|κ|減少到了 ||κ,避免非法動作影響的同時對動作進行篩選,得到最優(yōu)動作集合,提升模型的訓(xùn)練收益;最后通過仿真實驗?zāi)M,對比不同算法在同一實驗環(huán)境下所能降低的邊緣計算處理時延。結(jié)果表明,本文ECSO 算法相較于DQN、PPO 以及MP 三種算法能更有效地降低計算服務(wù)卸載帶來的時延消耗。由于在實際應(yīng)用中單一考慮邊緣節(jié)點進行服務(wù)卸載的效率還有待進一步提升,因此未來還將考慮多邊緣節(jié)點下的協(xié)同服務(wù)卸載與計算問題。