邊緣計(jì)算中多服務(wù)器協(xié)同任務(wù)緩存策略

馬世雄，葛海波，宋 興

西安郵電大學(xué) 電子工程學(xué)院，西安 710121

隨著超高清視頻、虛擬現(xiàn)實(shí)、自動(dòng)駕駛等新興互聯(lián)網(wǎng)業(yè)務(wù)的大量涌現(xiàn)，用戶(hù)對(duì)于計(jì)算型服務(wù)的需求不斷增多，僅靠云計(jì)算技術(shù)不能有效地響應(yīng)越來(lái)越多的用戶(hù)任務(wù)需求[1]。邊緣計(jì)算被視為克服上述問(wèn)題的有效方法之一[2]。其主要形式為將云服務(wù)器的計(jì)算和存儲(chǔ)能力下降到網(wǎng)絡(luò)邊緣的服務(wù)器（例如基站），使其能夠作為云服務(wù)器的替代品滿(mǎn)足終端用戶(hù)的大多數(shù)需求。

大多數(shù)邊緣計(jì)算的相關(guān)研究都隱含地假設(shè)邊緣服務(wù)器可以執(zhí)行從用戶(hù)卸載的所有類(lèi)型的計(jì)算任務(wù)，卻沒(méi)有考慮到相應(yīng)任務(wù)在邊緣服務(wù)器上的可用性，即對(duì)應(yīng)任務(wù)是否緩存在邊緣服務(wù)器上[3]。因此，任務(wù)緩存（也稱(chēng)服務(wù)緩存）是目前邊緣計(jì)算的研究的熱點(diǎn)之一，其主要內(nèi)容為：在邊緣服務(wù)器（edge server，ES）中緩存應(yīng)用服務(wù)程序及其相關(guān)的數(shù)據(jù)，從而使相應(yīng)的計(jì)算任務(wù)能夠被執(zhí)行[4]。由于邊緣服務(wù)器距離終端設(shè)備更近，其處理任務(wù)的時(shí)延相比云服務(wù)器會(huì)顯著降低，也減少了傳往云服務(wù)器的流量傳輸，減輕了傳輸網(wǎng)絡(luò)的傳輸壓力。但是由于邊緣服務(wù)器內(nèi)存容量和計(jì)算能力有限[5]，它不能緩存所有用戶(hù)的任務(wù)，將不合適的任務(wù)緩存到邊緣服務(wù)器上，會(huì)浪費(fèi)邊緣服務(wù)器的內(nèi)存資源和計(jì)算資源，并降低用戶(hù)體驗(yàn)。因此，確定一個(gè)合理的任務(wù)緩存策略對(duì)于邊緣服務(wù)器來(lái)說(shuō)極為重要。

任務(wù)緩存決策的制定面臨著一些挑戰(zhàn)。首先，之前的研究一般假設(shè)任務(wù)請(qǐng)求是已知的[6]，但這與現(xiàn)實(shí)情況有一些偏差。移動(dòng)設(shè)備的任務(wù)請(qǐng)求絕不是一成不變的，用戶(hù)的個(gè)性化的任務(wù)需求在空間和時(shí)間上都存在變化，邊緣服務(wù)器需要根據(jù)環(huán)境實(shí)時(shí)調(diào)整緩存策略以最大化用戶(hù)體驗(yàn)。其次，現(xiàn)有的研究大多忽略了動(dòng)態(tài)任務(wù)緩存策略對(duì)長(zhǎng)期服務(wù)成本和服務(wù)延遲的影響[7]。如何在沒(méi)有預(yù)見(jiàn)未來(lái)系統(tǒng)動(dòng)態(tài)的情況下做出緩存以最大化系統(tǒng)長(zhǎng)期性能是很大的挑戰(zhàn)。最后，由于邊緣計(jì)算服務(wù)器覆蓋范圍遠(yuǎn)遠(yuǎn)小于云計(jì)算，相鄰邊緣服務(wù)器的用戶(hù)更傾向于請(qǐng)求相似的任務(wù)[8]，如何將相鄰邊緣服務(wù)器協(xié)同起來(lái)優(yōu)化任務(wù)緩存策略是一個(gè)挑戰(zhàn)。

針對(duì)以上挑戰(zhàn)，本文考慮多個(gè)移動(dòng)設(shè)備，多個(gè)邊緣服務(wù)器和一個(gè)遠(yuǎn)程云服務(wù)器組成的網(wǎng)絡(luò)系統(tǒng)，在Soft Actor-Critic（SAC）算法的基礎(chǔ)上設(shè)計(jì)MSAC算法，通過(guò)經(jīng)驗(yàn)共享機(jī)制使多個(gè)服務(wù)器協(xié)作訓(xùn)練，實(shí)現(xiàn)在線(xiàn)任務(wù)緩存決策。

1 相關(guān)工作

近年來(lái)，學(xué)術(shù)界對(duì)于任務(wù)緩存技術(shù)的研究越來(lái)越多[9]。首先考慮一個(gè)邊緣服務(wù)器的情況。文獻(xiàn)[10]考慮了邊緣服務(wù)器計(jì)算和緩存能力的限制，通過(guò)設(shè)計(jì)一種交替迭代的方法來(lái)探索任務(wù)緩存和卸載的聯(lián)合優(yōu)化策略。文獻(xiàn)[11]通過(guò)考慮用戶(hù)的移動(dòng)性，利用子模塊優(yōu)化的方法來(lái)最大化緩存命中率。文獻(xiàn)[12]采用細(xì)粒度的任務(wù)模型，在邊緣云緩存能力有限的情況下，利用遺傳算法研究了邊緣云上的任務(wù)緩存和遷移策略。雖然以上研究都考慮了邊緣服務(wù)器緩存和計(jì)算能力的限制，但是都假設(shè)用戶(hù)對(duì)任務(wù)的請(qǐng)求是固定的。而在實(shí)際中，用戶(hù)的任務(wù)請(qǐng)求在空間上和時(shí)間上都是動(dòng)態(tài)變化的，也就是先驗(yàn)未知的。

為了解決用戶(hù)請(qǐng)求是先驗(yàn)未知的這一問(wèn)題，文獻(xiàn)[13]站在應(yīng)用服務(wù)提供商的角度，讓基站通過(guò)觀察用戶(hù)上下文信息來(lái)了解用戶(hù)的需求模式，從而選擇緩存內(nèi)容并進(jìn)行合理的基站租賃決策，但是此方法需要在基站內(nèi)部維護(hù)較大的上下文信息空間。文獻(xiàn)[14]中以未知的用戶(hù)請(qǐng)求為前提并考慮任務(wù)計(jì)算量和緩存需求的異構(gòu)性，提出一種基于強(qiáng)化學(xué)習(xí)的多臂強(qiáng)盜算法來(lái)實(shí)現(xiàn)智能的任務(wù)緩存策略，通過(guò)利用上置信約束來(lái)實(shí)現(xiàn)探索與開(kāi)發(fā)之間的平衡。文獻(xiàn)[15]提出了一個(gè)新的任務(wù)緩存框架，該框架通過(guò)使用馬爾可夫鏈和Q 學(xué)習(xí)算法尋找最優(yōu)的緩存策略。首先利用馬爾可夫決策過(guò)程對(duì)用戶(hù)請(qǐng)求建模，然后基于Q學(xué)習(xí)方法設(shè)計(jì)線(xiàn)性逼近函數(shù)，實(shí)現(xiàn)了在線(xiàn)任務(wù)緩存決策。文獻(xiàn)[16]將深度學(xué)習(xí)與強(qiáng)化學(xué)習(xí)相結(jié)合，通過(guò)利深度強(qiáng)化學(xué)習(xí)算法來(lái)綜合優(yōu)化任務(wù)緩存和卸載策略。然而這些研究都是在單個(gè)服務(wù)器上進(jìn)行的，沒(méi)有考慮相鄰服務(wù)器聯(lián)合決策的情況。

隨著研究的深入，多邊緣服務(wù)器的情況被越來(lái)越多地研究。文獻(xiàn)[17]利用李雅普諾夫優(yōu)化技術(shù)建立一個(gè)能量不足隊(duì)列（energy defificit queue）來(lái)指導(dǎo)任務(wù)緩存和卸載決策，通過(guò)吉布斯抽樣算法實(shí)現(xiàn)基站之間的分散協(xié)調(diào)。文獻(xiàn)[18]將多服務(wù)器任務(wù)緩存優(yōu)化問(wèn)題進(jìn)行分解以降低計(jì)算復(fù)雜度，然后利用廣義彎曲度分解（generalized benders decomposition）的方法得到系統(tǒng)決策。但是這些方法并沒(méi)有擺脫任務(wù)請(qǐng)求已知的假設(shè)，也僅僅是單個(gè)時(shí)隙的最優(yōu)決策，忽略了系統(tǒng)的長(zhǎng)期性能。

與以上的研究不同，本文將用戶(hù)請(qǐng)求未知的假設(shè)，系統(tǒng)長(zhǎng)期性能和多服務(wù)器協(xié)同任務(wù)緩存問(wèn)題聯(lián)合起來(lái)，通過(guò)設(shè)計(jì)深度強(qiáng)化學(xué)習(xí)（deep reinforcement learning，DRL）算法來(lái)最大限度減少系統(tǒng)平均任務(wù)執(zhí)行時(shí)延。本文的主要貢獻(xiàn)可以概括如下：

（1）建立多服務(wù)器協(xié)同任務(wù)緩存模型。邊緣服務(wù)器上可以緩存移動(dòng)設(shè)備請(qǐng)求的任務(wù)，當(dāng)任務(wù)不在邊緣設(shè)備上緩存時(shí)，移動(dòng)設(shè)備只能在云服務(wù)上執(zhí)行。邊緣服務(wù)器之間可以進(jìn)行通信來(lái)協(xié)同優(yōu)化任務(wù)緩存決策。

（2）將任務(wù)緩存問(wèn)題形式化。以最小化用戶(hù)總?cè)蝿?wù)平均執(zhí)行時(shí)延為目標(biāo)，綜合考慮邊緣服務(wù)器的計(jì)算能力和緩存空間大小。

（3）設(shè)計(jì)基于改進(jìn)Soft Actor-Critic 的任務(wù)緩存算法MSAC。該算法通過(guò)與環(huán)境的不斷交互，可以適應(yīng)用戶(hù)請(qǐng)求任務(wù)的改變并不斷更新任務(wù)緩存策略。通過(guò)引入最大熵鼓勵(lì)探索更多策略，設(shè)計(jì)經(jīng)驗(yàn)共享機(jī)制優(yōu)化任務(wù)緩存決策，從而降低用戶(hù)平均任務(wù)執(zhí)行時(shí)延。

2 系統(tǒng)模型

2.1 網(wǎng)絡(luò)建模

如圖1 所示，在一個(gè)區(qū)域中，多個(gè)邊緣服務(wù)器和一個(gè)云服務(wù)器組成邊緣計(jì)算系統(tǒng)。邊緣服務(wù)器通過(guò)無(wú)線(xiàn)鏈路與移動(dòng)設(shè)備進(jìn)行通信，云服務(wù)器通過(guò)核心網(wǎng)與邊緣服務(wù)器通信，邊緣服務(wù)器之間可以通過(guò)本地局域網(wǎng)進(jìn)行通信。云服務(wù)器和邊緣服務(wù)器均可以為移動(dòng)設(shè)備提供任務(wù)計(jì)算服務(wù)，前提是先緩存要計(jì)算的任務(wù)。假設(shè)云服務(wù)器具有充足的計(jì)算能力和緩存容量，可以緩存所有的任務(wù)。相比于云服務(wù)器，邊緣服務(wù)器的計(jì)算能力和緩存容量都是有限的，因此不能緩存所有的任務(wù)，只能緩存部分任務(wù)。每個(gè)移動(dòng)設(shè)備都有需要執(zhí)行的計(jì)算任務(wù)，例如移動(dòng)游戲或者視頻流。考慮到移動(dòng)設(shè)備的計(jì)算能力和電池容量有限，不適于一些計(jì)算需求大且耗能的任務(wù)，因此，與文獻(xiàn)[14]中的工作類(lèi)似，假設(shè)移動(dòng)設(shè)備本身不處理任務(wù)，只考慮邊緣服務(wù)器或遠(yuǎn)程云上的任務(wù)緩存和處理。

圖1 系統(tǒng)模型Fig.1 System model

令N={1,2,…,n}表示邊緣服務(wù)器的集合。邊緣服務(wù)器的最大計(jì)算能力為fES（以cpu周期數(shù)為單位），內(nèi)存容量為C。云服務(wù)器的最大計(jì)算能力為fCS，fCS＞fES。令K={1,2,…,k}表示k個(gè)任務(wù)的集合，其中1,2,…,k表示任務(wù)的編號(hào)。每個(gè)任務(wù)之間是獨(dú)立的，且具有四個(gè)固定參數(shù)：{wk,ck,pk,qk},wk指完成任務(wù)k所需的cpu周期總數(shù)，ck指緩存任務(wù)k所需的代碼和環(huán)境所占用的內(nèi)存空間大小，pk指任務(wù)計(jì)算所需的初始數(shù)據(jù)的大小，qk指任務(wù)計(jì)算完成后的數(shù)據(jù)結(jié)果大小。

為了簡(jiǎn)化計(jì)算和實(shí)現(xiàn)，假設(shè)該模型運(yùn)行在離散的時(shí)隙t=1,2,…,T，其中T表示有限的時(shí)間范圍。每個(gè)時(shí)隙內(nèi)任務(wù)均計(jì)算完成后轉(zhuǎn)移到下一時(shí)隙。邊緣服務(wù)器每個(gè)時(shí)隙中所關(guān)聯(lián)的移動(dòng)設(shè)備個(gè)數(shù)為Mt，且移動(dòng)設(shè)備在每個(gè)時(shí)隙內(nèi)位置固定，每個(gè)時(shí)隙結(jié)束后有一定的幾率移動(dòng)到相鄰的服務(wù)器。

2.2 任務(wù)請(qǐng)求模型

每個(gè)時(shí)隙t開(kāi)始時(shí)移動(dòng)設(shè)備會(huì)在K個(gè)任務(wù)中選擇一個(gè)請(qǐng)求至與其相關(guān)聯(lián)的邊緣服務(wù)器。由于每個(gè)用戶(hù)可能請(qǐng)求相同的任務(wù)，且邊緣服務(wù)器相關(guān)聯(lián)的用戶(hù)個(gè)數(shù)可能不同，如果將所有用戶(hù)請(qǐng)求的任務(wù)依次表示，則總?cè)蝿?wù)請(qǐng)求集合的元素個(gè)數(shù)將會(huì)不斷改變。為了保持系統(tǒng)狀態(tài)維度不變，便于模型求解，因此使用記錄任務(wù)k的請(qǐng)求次數(shù)，則時(shí)隙t中用戶(hù)總的任務(wù)請(qǐng)求表示為。例如，Bt={5,4,3,2,1}表示在任務(wù)種類(lèi)為5 的系統(tǒng)中，時(shí)隙t內(nèi)1 號(hào)任務(wù)請(qǐng)求個(gè)數(shù)為5，2號(hào)任務(wù)請(qǐng)求個(gè)數(shù)為4，以此類(lèi)推即可。

2.3 任務(wù)緩存模型

邊緣服務(wù)器在為移動(dòng)設(shè)備提供服務(wù)時(shí)首先要把對(duì)應(yīng)任務(wù)相關(guān)環(huán)境和數(shù)據(jù)緩存在內(nèi)存中，定義每個(gè)邊緣服務(wù)器上在時(shí)隙t的任務(wù)k的緩存決策：

則邊緣服務(wù)器在時(shí)隙t的總緩存決策為at={…}。例如，at={0,1,0,0,1}表示2號(hào)任務(wù)和5號(hào)任務(wù)需要緩存在邊緣服務(wù)器上。考慮到邊緣服務(wù)器內(nèi)存容量限制，每個(gè)邊緣服務(wù)器進(jìn)行任務(wù)緩存時(shí)需要滿(mǎn)足的約束條件為：

每個(gè)時(shí)隙邊緣服務(wù)器都會(huì)做出新的任務(wù)緩存決策at，由于at不會(huì)一直完全相同，因此需要對(duì)新的任務(wù)進(jìn)行緩存替換，即刪除不需要緩存的舊任務(wù)，給新任務(wù)分配其所需的內(nèi)存資源并從磁盤(pán)中緩存該任務(wù)。

2.4 任務(wù)執(zhí)行時(shí)延模型

該模型中任務(wù)執(zhí)行的時(shí)延可以分為三部分：通信時(shí)延，計(jì)算時(shí)延，緩存替換時(shí)延。

（1）通信時(shí)延

通信時(shí)延指移動(dòng)設(shè)備發(fā)送任務(wù)初始數(shù)據(jù)和接受計(jì)算結(jié)果過(guò)程中所產(chǎn)生的延遲。

當(dāng)任務(wù)在邊緣服務(wù)器上執(zhí)行，即1 時(shí)。由于模型中移動(dòng)設(shè)備和邊緣服務(wù)器之間采用正交頻分多址的方式進(jìn)行通信，即邊緣服務(wù)器為每個(gè)關(guān)聯(lián)的移動(dòng)設(shè)備分配一個(gè)正交信道用以傳輸數(shù)據(jù)，因此不用考慮傳輸信道之間可能產(chǎn)生的干擾問(wèn)題。移動(dòng)設(shè)備與邊緣服務(wù)器之間的上行傳輸速率可由香農(nóng)公式得出：

其中，Bk表示無(wú)線(xiàn)傳輸帶寬，Ps和Pn分別表示邊緣服務(wù)器的傳輸功率和噪聲功率。則移動(dòng)設(shè)備將任務(wù)k的初始數(shù)據(jù)通過(guò)無(wú)線(xiàn)鏈路發(fā)送到邊緣服務(wù)器的上行傳輸時(shí)延為：

由于從邊緣服務(wù)器到移動(dòng)設(shè)備的下行鏈路速率遠(yuǎn)大于上行鏈路速率，因此只考慮上行鏈路，忽略從邊緣服務(wù)器將任務(wù)結(jié)果傳回移動(dòng)設(shè)備的時(shí)延開(kāi)銷(xiāo)。則1時(shí)的通信時(shí)延為。

當(dāng)任務(wù)在云服務(wù)器上執(zhí)行，即0 時(shí)，輸入數(shù)據(jù)通過(guò)邊緣服務(wù)器轉(zhuǎn)發(fā)到云服務(wù)器，計(jì)算結(jié)果通過(guò)邊緣服務(wù)器轉(zhuǎn)發(fā)到移動(dòng)設(shè)備。由于與云服務(wù)器距離較遠(yuǎn)，假設(shè)核心網(wǎng)中的數(shù)據(jù)傳輸時(shí)間為tc，則可以得到任務(wù)k在0 時(shí)的通信時(shí)延：

則時(shí)隙t內(nèi)任務(wù)總通信時(shí)延為：

（2）計(jì)算時(shí)延

計(jì)算時(shí)延表示為任務(wù)在邊緣服務(wù)器或云服務(wù)器上計(jì)算所需的時(shí)間。邊緣服務(wù)器會(huì)計(jì)算所有已緩存任務(wù)的請(qǐng)求，為每個(gè)任務(wù)平均分配計(jì)算能力：

每個(gè)任務(wù)計(jì)算時(shí)延為：

則該時(shí)隙內(nèi)邊緣服務(wù)器上任務(wù)總計(jì)算時(shí)延為：

由于云服務(wù)器計(jì)算能力充足，每個(gè)任務(wù)分配到的計(jì)算能力均為fCS，其計(jì)算時(shí)延為：

云服務(wù)器上任務(wù)總計(jì)算時(shí)延為：

由于邊緣服務(wù)器的計(jì)算能力不如云服務(wù)器，若在邊緣服務(wù)器上執(zhí)行過(guò)多的任務(wù)，每個(gè)任務(wù)分配到的計(jì)算能力太少，其任務(wù)計(jì)算時(shí)延就會(huì)大大增加。因此，邊緣服務(wù)器和云服務(wù)器的協(xié)同計(jì)算是必要的。

（3）緩存替換時(shí)延

緩存替換時(shí)延指邊緣服務(wù)器做出緩存決策后，刪除不再緩存的任務(wù)并從磁盤(pán)中加載新任務(wù)所需的時(shí)延。因?yàn)閯h除任務(wù)所需的時(shí)間極短，因此忽略刪除任務(wù)的時(shí)延。任務(wù)k的緩存替換時(shí)延表示為：

其中，ck表示緩存任務(wù)k所需的內(nèi)存大小，v代表任務(wù)從磁盤(pán)加載到內(nèi)存的速度。由于緩存替換時(shí)任務(wù)不能執(zhí)行，所以任務(wù)的總等待時(shí)間為：

綜上所述，在一個(gè)邊緣服務(wù)器上，時(shí)隙t的平均任務(wù)執(zhí)行時(shí)延可以表示為：

2.5 問(wèn)題表述

本文的研究目標(biāo)是最小化多服務(wù)器任務(wù)緩存模型的平均任務(wù)執(zhí)行時(shí)延，考慮到邊緣服務(wù)器的計(jì)算能力和內(nèi)存空間限制，對(duì)于圖1 所示每個(gè)邊緣計(jì)算服務(wù)器，任務(wù)時(shí)延問(wèn)題表述為：

其中，目標(biāo)函數(shù)為計(jì)算每個(gè)時(shí)隙的任務(wù)平均執(zhí)行時(shí)延，第一個(gè)約束是任務(wù)總的緩存容量不能超過(guò)邊緣服務(wù)器的內(nèi)存空間限制，第二個(gè)約束表示任務(wù)k是否緩存在邊緣服務(wù)器上。

3 MSAC算法設(shè)計(jì)

深度強(qiáng)化學(xué)習(xí)是近年來(lái)研究的一個(gè)熱點(diǎn)，智能體通過(guò)與環(huán)境進(jìn)行交互（做出動(dòng)作決策并產(chǎn)生相應(yīng)的獎(jiǎng)勵(lì)）來(lái)不斷調(diào)整行為以最大化長(zhǎng)期系統(tǒng)收益。相比于傳統(tǒng)優(yōu)化算法，DRL方法可以針對(duì)不同邊緣計(jì)算環(huán)境中不同的任務(wù)請(qǐng)求做出對(duì)應(yīng)的緩存決策，能夠適應(yīng)環(huán)境且決策用時(shí)短，更適用于邊緣計(jì)算環(huán)境。目前已有許多DRL算法應(yīng)用于邊緣計(jì)算相關(guān)研究[19-22]。

在上文的模型中，由于任務(wù)替換時(shí)延需要考慮上一時(shí)隙的緩存決策，因此邊緣服務(wù)器的緩存決策不僅影響當(dāng)前時(shí)隙的任務(wù)平均執(zhí)行時(shí)延，也會(huì)對(duì)下一時(shí)隙產(chǎn)生影響。如果僅考慮令當(dāng)前時(shí)隙的任務(wù)平均時(shí)延最小，則可能會(huì)頻繁地進(jìn)行緩存替換，任務(wù)的執(zhí)行時(shí)延可能會(huì)大大增加。因此邊緣服務(wù)器做出緩存決策時(shí)不僅需要讓當(dāng)前時(shí)隙任務(wù)平均執(zhí)行時(shí)延盡可能小，也要為未來(lái)考慮，最大化系統(tǒng)長(zhǎng)期收益，這與強(qiáng)化學(xué)習(xí)的特點(diǎn)不謀而同。雖然進(jìn)化算法也能夠找到較優(yōu)的決策，但是其決策用時(shí)過(guò)長(zhǎng)，且僅能考慮當(dāng)前時(shí)隙，沒(méi)有“長(zhǎng)遠(yuǎn)眼光”。

因此，為了解決任務(wù)緩存模型中用戶(hù)請(qǐng)求未知和系統(tǒng)長(zhǎng)期性能的挑戰(zhàn)，本章基于Soft-Actor-Critic深度強(qiáng)化學(xué)習(xí)算法設(shè)計(jì)基于分布式?jīng)Q策的在線(xiàn)任務(wù)緩存算法，每個(gè)邊緣服務(wù)器均通過(guò)與環(huán)境交互進(jìn)行緩存決策以最小化移動(dòng)設(shè)備任務(wù)平均執(zhí)行時(shí)延，最大化系統(tǒng)長(zhǎng)期性能。同時(shí)，為了解決邊緣服務(wù)器協(xié)同的挑戰(zhàn)，本章在SAC算法的基礎(chǔ)上設(shè)計(jì)經(jīng)驗(yàn)共享機(jī)制，使相鄰邊緣服務(wù)器共享經(jīng)驗(yàn)以?xún)?yōu)化任務(wù)緩存決策。

3.1 構(gòu)建MDP

馬爾可夫決策過(guò)程（Markovian decision process，MDP）是強(qiáng)化學(xué)習(xí)中利用交互式學(xué)習(xí)來(lái)實(shí)現(xiàn)最大化系統(tǒng)收益的理論模型，其主要包含狀態(tài)、動(dòng)作、獎(jiǎng)勵(lì)這三個(gè)關(guān)鍵要素。在本模型中，對(duì)于每個(gè)邊緣服務(wù)器，其三要素的定義如下：

系統(tǒng)獎(jiǎng)勵(lì)：系統(tǒng)獎(jiǎng)勵(lì)指在狀態(tài)st下采取動(dòng)作at后系統(tǒng)的收益。本文優(yōu)化的目標(biāo)是邊緣服務(wù)器的平均任務(wù)執(zhí)行時(shí)延，目的是令任務(wù)時(shí)延盡可能地減小，而強(qiáng)化學(xué)習(xí)的目標(biāo)是最大化系統(tǒng)獎(jiǎng)勵(lì)。因此系統(tǒng)獎(jiǎng)勵(lì)應(yīng)與平均任務(wù)執(zhí)行時(shí)延呈負(fù)相關(guān)，將系統(tǒng)獎(jiǎng)勵(lì)設(shè)置為：

其中Qt的計(jì)算方式由式（14）給出。

3.2 動(dòng)作優(yōu)化

由于邊緣服務(wù)器緩存容量有限，其緩存決策受到式（2）的限制。若邊緣服務(wù)器做出非法動(dòng)作，即任務(wù)緩存決策at不滿(mǎn)足式（2）時(shí)，需要對(duì)該動(dòng)作進(jìn)行優(yōu)化以滿(mǎn)足式（2）。

本文通過(guò)任務(wù)優(yōu)先級(jí)優(yōu)化緩存動(dòng)作。定義每個(gè)任務(wù)的優(yōu)先級(jí)dk：

在等式右側(cè)，前者表示任務(wù)請(qǐng)求數(shù)量占總數(shù)量的比值，后者表示任務(wù)大小和邊緣服務(wù)器內(nèi)存大小的比值。優(yōu)先級(jí)越高，則表示該任務(wù)請(qǐng)求數(shù)量越多或所占緩存資源越少。當(dāng)服務(wù)器做出的緩存決策at不滿(mǎn)足式（2）時(shí)，服務(wù)器會(huì)根據(jù)at中要緩存任務(wù)的優(yōu)先級(jí)進(jìn)行排序，從優(yōu)先級(jí)最高的任務(wù)開(kāi)始緩存，直至服務(wù)器存儲(chǔ)資源用完，從而得到優(yōu)化后的動(dòng)作。這個(gè)優(yōu)化目標(biāo)是要求服務(wù)器盡可能多地執(zhí)行任務(wù)和緩存任務(wù)。同時(shí)，因?yàn)閍t是非法動(dòng)作，該動(dòng)作對(duì)應(yīng)的系統(tǒng)獎(jiǎng)勵(lì)應(yīng)為-r1。r1為懲罰因子，可以令服務(wù)器在更新策略時(shí)減少對(duì)該動(dòng)作的選取。因此系統(tǒng)獎(jiǎng)勵(lì)應(yīng)改為：

3.3 MSAC算法

標(biāo)準(zhǔn)強(qiáng)化學(xué)習(xí)的目標(biāo)是最大化智能體的回報(bào)，而SAC算法在傳統(tǒng)AC算法的基礎(chǔ)上增加了最大熵模型，通過(guò)最大化熵值來(lái)讓動(dòng)作的分布更加均勻，鼓勵(lì)智能體探索更多策略，從而避免反復(fù)選擇同一動(dòng)作而收斂于局部最優(yōu)，同時(shí)通過(guò)最大化獎(jiǎng)賞，放棄較低獎(jiǎng)賞的策略以尋找最優(yōu)策略。因此本文在SAC 算法的基礎(chǔ)上設(shè)計(jì)MSAC 算法。由于本文的任務(wù)緩存模型中智能體輸出的緩存決策為離散動(dòng)作，因此本文采用SAC 算法的離散形式。

MSAC算法的結(jié)構(gòu)如圖2所示。該算法遵循Actor-Critic 框架。Actor 部分為一個(gè)參數(shù)為?的策略網(wǎng)絡(luò)π?(at|st)，作用是通過(guò)與環(huán)境交互采集每個(gè)時(shí)隙的任務(wù)請(qǐng)求和上一時(shí)隙的緩存決策作為系統(tǒng)的輸入st，通過(guò)策略網(wǎng)絡(luò)輸出任務(wù)緩存決策at。應(yīng)用于離散情況時(shí)，策略網(wǎng)絡(luò)不輸出動(dòng)作分布的均值和協(xié)方差，而是直接輸出動(dòng)作分布。具體操作是參數(shù)化π將狀態(tài)映射到一個(gè)有2 |A|個(gè)元素的實(shí)數(shù)向量，其中 |A|是動(dòng)作空間的維度。在該網(wǎng)絡(luò)最后一層應(yīng)用softmax 函數(shù)，以確保其輸出的每個(gè)動(dòng)作的概率分布是有效的。Critic部分為參數(shù)為θ的Q值網(wǎng)絡(luò)Qθ(st,at)，它通過(guò)輸出每個(gè)動(dòng)作的Q值來(lái)評(píng)估當(dāng)前策略的好壞。

圖2 MSAC算法框架Fig.2 Framework of MSAC

SAC算法目標(biāo)是尋找最優(yōu)策略π*：

其中，E表示均值，T是時(shí)間步數(shù)，r(st,at)為智能體在狀態(tài)st下執(zhí)行動(dòng)作at獲得的獎(jiǎng)勵(lì)，γ∈[0,1]是折扣因子，st,at分別為智能體在t時(shí)刻的狀態(tài)和動(dòng)作。τπ為策略π下的(st,at)的軌跡分布。α決定了熵項(xiàng)相對(duì)于獎(jiǎng)勵(lì)的重要性，稱(chēng)為溫度系數(shù)。考慮到用戶(hù)任務(wù)請(qǐng)求的時(shí)變性，為了維持算法的探索性，α設(shè)為定值。

H(π(·|st)表示策略在狀態(tài)st處的熵，計(jì)算公式為：

Actor 部分通過(guò)觀察環(huán)境狀態(tài)st后輸出最優(yōu)動(dòng)作at，執(zhí)行動(dòng)作at后，收集獎(jiǎng)勵(lì)rt并觀察得到下一個(gè)狀態(tài)st+1。四元組(st,at,rt,st+1)將被收集并存入經(jīng)驗(yàn)回放池D中。

Critic 部分從經(jīng)驗(yàn)回放池中采樣，目標(biāo)是通過(guò)訓(xùn)練Q值網(wǎng)絡(luò)參數(shù)使貝爾曼誤差JQ(θ)最小：

其中，E表示期望，狀態(tài)值函數(shù)Vθ(st)表示為：

其中，π(st)表示離散化后的策略在st狀態(tài)下每個(gè)動(dòng)作的概率的集合，Q(st)表示st狀態(tài)下每個(gè)動(dòng)作Q 值的集合，因此可以直接計(jì)算得到Vθ(st)的值。通過(guò)隨機(jī)梯度優(yōu)化即可更新Q值網(wǎng)絡(luò)參數(shù)θ：

其中，β表示學(xué)習(xí)率。

Critic部分有兩個(gè)獨(dú)立的Q值網(wǎng)絡(luò)Qθ1、Qθ2，每個(gè)Q值網(wǎng)絡(luò)還對(duì)應(yīng)一個(gè)目標(biāo)Q 值網(wǎng)絡(luò)Qθˉ1、Qθˉ2，其作用是穩(wěn)定Q值網(wǎng)絡(luò)的學(xué)習(xí)效果。Q值網(wǎng)絡(luò)參數(shù)更新后，需要對(duì)目標(biāo)Q值網(wǎng)絡(luò)參數(shù)進(jìn)行軟更新：

其中，λ為調(diào)節(jié)目標(biāo)Q值網(wǎng)絡(luò)軟更新的超參數(shù)。為了避免對(duì)值函數(shù)的高估，使用兩個(gè)Q值網(wǎng)絡(luò)輸出的最小值作為Critic部分的Q值網(wǎng)絡(luò)輸出：

得到Critic 網(wǎng)絡(luò)輸出后，可以計(jì)算Actor 網(wǎng)絡(luò)的損失函數(shù)：

進(jìn)而更新Actor網(wǎng)絡(luò)參數(shù)以改進(jìn)緩存策略：

該算法在策略評(píng)估和策略改進(jìn)之間交替進(jìn)行，從而不斷優(yōu)化服務(wù)器的緩存策略。

3.4 經(jīng)驗(yàn)共享機(jī)制

通過(guò)在每個(gè)邊緣服務(wù)器上部署上文的MSAC算法，每個(gè)邊緣服務(wù)器均可以與本地環(huán)境進(jìn)行交互來(lái)學(xué)習(xí)緩存決策。但是深度強(qiáng)化學(xué)習(xí)算法需要足夠且多樣的經(jīng)驗(yàn)數(shù)據(jù)，以確保其學(xué)習(xí)性能。僅靠單個(gè)邊緣服務(wù)器與本地環(huán)境交互來(lái)獲取數(shù)據(jù)，會(huì)導(dǎo)致時(shí)間消耗和數(shù)據(jù)多樣性不足。此外，在真實(shí)邊緣計(jì)算環(huán)境中，DRL算法的學(xué)習(xí)時(shí)間與用戶(hù)體驗(yàn)相關(guān)聯(lián)，僅從單個(gè)環(huán)境中獲取經(jīng)驗(yàn)數(shù)據(jù)的學(xué)習(xí)成本太高[23]。

考慮到鄰近地區(qū)的用戶(hù)任務(wù)請(qǐng)求大多相似，相鄰的邊緣服務(wù)器所處環(huán)境較為相似，因此邊緣服務(wù)器在收集四元組(st,at,rt,st+1)時(shí)不僅可以放入自己的經(jīng)驗(yàn)回放池D 中，也可以發(fā)送給相鄰的邊緣服務(wù)器，自己也可以接受相鄰的服務(wù)器傳來(lái)的經(jīng)驗(yàn)四元組來(lái)訓(xùn)練本地SAC算法。此時(shí)經(jīng)驗(yàn)回放池D為：

其中，Dl為本地經(jīng)驗(yàn)回放池，Dn為相鄰服務(wù)器傳來(lái)的經(jīng)驗(yàn)四元組的集合。兩者均為相同長(zhǎng)度的雙端隊(duì)列，按照先進(jìn)先出的原則，始終維護(hù)較新的經(jīng)驗(yàn)回放池來(lái)訓(xùn)練SAC網(wǎng)絡(luò)，以保持緩存決策的及時(shí)更新。

相鄰服務(wù)器的定義為：兩服務(wù)器之間的距離小于服務(wù)器最大接受范圍的2 倍。不滿(mǎn)足該條件的邊緣服務(wù)器之間不共享經(jīng)驗(yàn)。

MSAC算法流程描述如下：

輸入：移動(dòng)設(shè)備集合I，計(jì)算任務(wù)集合K，邊緣服務(wù)器集合N，以及邊緣服務(wù)器緩存容量C和計(jì)算頻率fES，云服務(wù)器計(jì)算頻率fCS。

4 仿真實(shí)驗(yàn)與結(jié)果分析

4.1 實(shí)驗(yàn)設(shè)置

由于無(wú)法實(shí)現(xiàn)真實(shí)的邊緣計(jì)算環(huán)境，因此，為盡可能模擬真實(shí)環(huán)境，本文參考文獻(xiàn)[24]的環(huán)境設(shè)置，在其基礎(chǔ)上適當(dāng)修改進(jìn)行實(shí)驗(yàn)仿真。使用python3.7 和pytorch1.5.0 模擬了具有5 個(gè)邊緣服務(wù)器和一個(gè)云服務(wù)器組成的小區(qū)邊緣計(jì)算系統(tǒng)。邊緣服務(wù)器的位置如圖1所示擺放，每個(gè)時(shí)隙每個(gè)用戶(hù)可以在現(xiàn)有任務(wù)中選擇一個(gè)任務(wù)請(qǐng)求至邊緣服務(wù)器，任務(wù)的請(qǐng)求概率服從齊夫分布[25]。由于邊緣服務(wù)器所覆蓋范圍較小，因此假設(shè)每個(gè)用戶(hù)與邊緣服務(wù)器之間的數(shù)據(jù)傳輸帶寬相同，以簡(jiǎn)化系統(tǒng)模型。該系統(tǒng)的主要參數(shù)設(shè)置由表1給出。

表1 系統(tǒng)主要參數(shù)設(shè)置Table 1 Main parameters setting of system

邊緣計(jì)算系統(tǒng)采用分布式?jīng)Q策，在每個(gè)邊緣服務(wù)器上部署MSAC算法，Actor部分和Critic部分均使用全連接神經(jīng)網(wǎng)絡(luò)來(lái)訓(xùn)練模型，學(xué)習(xí)率分別為0.001和0.000 5，并使用adam 優(yōu)化器進(jìn)行優(yōu)化。Critic 部分中溫度系數(shù)為0.2，折扣因子為0.9，軟更新參數(shù)為0.001。設(shè)置經(jīng)驗(yàn)回放池的大小為5 000，每次采樣32組經(jīng)驗(yàn)進(jìn)行訓(xùn)練。

在實(shí)驗(yàn)中，默認(rèn)設(shè)置每個(gè)邊緣服務(wù)器計(jì)算能力為5 Gigacycle/s，內(nèi)存空間為1 000 Mbit，初始關(guān)聯(lián)用戶(hù)數(shù)量為10，任務(wù)數(shù)量為6。

4.2 收斂性分析

為了研究所提算法的收斂性和經(jīng)驗(yàn)共享機(jī)制的有效性，圖3 展示了默認(rèn)設(shè)置下圖1 中3 號(hào)邊緣服務(wù)器上MSAC算法的收斂性能，其中SAC算法為不采用經(jīng)驗(yàn)共享機(jī)制的獨(dú)立SAC算法。由于用戶(hù)請(qǐng)求的隨機(jī)性和RL的探索性，每個(gè)訓(xùn)練回合的任務(wù)平均時(shí)延不可能完全相同，因此，在任務(wù)平均執(zhí)行時(shí)延較低且在一個(gè)較小范圍內(nèi)波動(dòng)時(shí)，可視為算法達(dá)到收斂。從圖3 可以看出，隨著訓(xùn)練回合的增加，MSAC算法吸收更多的經(jīng)驗(yàn)進(jìn)行學(xué)習(xí)，能夠較快收斂，大約在75 回合訓(xùn)練后達(dá)到收斂，而SAC算法由于經(jīng)驗(yàn)多樣性不足，在大約100回合訓(xùn)練后才達(dá)到收斂。MSAC算法收斂更快且性能更好，任務(wù)平均執(zhí)行時(shí)延在225 ms左右，優(yōu)于SAC算法，驗(yàn)證了經(jīng)驗(yàn)共享機(jī)制的有效性。

圖3 MSAC與SAC算法收斂性能Fig.3 Convergence performance of MSAC and SAC

4.3 不同算法之間性能對(duì)比

為了驗(yàn)證所提算法的性能，將MSAC 算法和SAC算法訓(xùn)練200 回合時(shí)的性能分別與以下三種方案進(jìn)行比較，具體描述如下：

基于DQN 算法[26]的緩存方案（DQN）：每個(gè)邊緣服務(wù)器部署用DQN 算法進(jìn)行緩存決策，通過(guò)輸出狀態(tài)st下動(dòng)作at的Q值判斷該動(dòng)作的優(yōu)劣并改進(jìn)緩存決策。

基于遺傳算法[12]的緩存方案（GEN）：使用遺傳算法不斷迭代得到較優(yōu)緩存方案，取迭代100次的結(jié)果進(jìn)行對(duì)比。

基于流行度的緩存方案（POP）：邊緣服務(wù)器統(tǒng)計(jì)任務(wù)的請(qǐng)求個(gè)數(shù)，按照個(gè)數(shù)從高到低緩存任務(wù)。

圖4為5種算法在改變?nèi)蝿?wù)種類(lèi)個(gè)數(shù)時(shí)任務(wù)平均執(zhí)行時(shí)延的變化情況。隨著任務(wù)種類(lèi)的增加，系統(tǒng)任務(wù)平均執(zhí)行時(shí)延呈上升趨勢(shì)。由于邊緣服務(wù)器內(nèi)存空間的限制，邊緣服務(wù)器不能緩存更多的任務(wù)，導(dǎo)致更多用戶(hù)任務(wù)轉(zhuǎn)發(fā)到云端執(zhí)行，從而增加執(zhí)行時(shí)延。與SAC 算法、DQN 算法、GEN 算法和POP 算法相比，本文提出的MSAC 算法性能最好，任務(wù)平均執(zhí)行時(shí)延分別降低約3.8%、15.5%、8.4%、31.4%。

圖4 任務(wù)種類(lèi)個(gè)數(shù)與平均時(shí)延Fig.4 Number of task types and average latency

任務(wù)種類(lèi)改變時(shí)各個(gè)算法每個(gè)時(shí)隙做出緩存決策的用時(shí)由表2列出，由于POP算法根據(jù)邊緣服務(wù)器統(tǒng)計(jì)的各任務(wù)次數(shù)從高到低依次緩存，因此做出決策時(shí)間幾乎為0 ms。隨著任務(wù)種類(lèi)的增加，其余算法決策用時(shí)均增加。SAC 算法、MSAC 算法和DQN 算法的決策因由神經(jīng)網(wǎng)絡(luò)計(jì)算得出，所以用時(shí)極短，僅需1～2 ms。相比于神經(jīng)網(wǎng)絡(luò)，GEN 算法由于需要不斷迭代來(lái)尋找最優(yōu)決策，需要耗費(fèi)大量時(shí)間。在任務(wù)種類(lèi)為6，8，10時(shí)，GEN算法迭代100 次的用時(shí)大約為其他三種算法的203 倍，200倍，135倍。

表2 任務(wù)種類(lèi)與決策用時(shí)Table 2 Task type and decision-making

圖5展示了5種算法在邊緣服務(wù)器計(jì)算能力分別為5，6，7，8，9，10 Gigacycle/s 時(shí)的性能表現(xiàn)。隨著邊緣服務(wù)器計(jì)算能力的增加，系統(tǒng)平均任務(wù)執(zhí)行時(shí)延不斷降低。MSAC 算法在不同計(jì)算能力下均有著最好的性能表現(xiàn)，SAC 算法次之。由于DQN 算法容易過(guò)擬合且收斂速度慢，其性能不如GEN 算法。POP 算法由于不能動(dòng)態(tài)適應(yīng)用戶(hù)的請(qǐng)求，其性能最差。相比于SAC算法、DQN算法、GEN算法和POP算法，MSAC算法的任務(wù)平均執(zhí)行時(shí)延分別降低3.6%、16.5%、6.4%、26.3%。從曲線(xiàn)斜率來(lái)看，平均時(shí)延降低的速度逐漸變緩。這是由于邊緣服務(wù)器緩存容量有限，已緩存任務(wù)的計(jì)算時(shí)延逐漸變小，而未緩存的任務(wù)只能在云服務(wù)器上執(zhí)行，其時(shí)延與邊緣服務(wù)器的計(jì)算能力無(wú)關(guān)，限制了系統(tǒng)的性能。

圖5 邊緣服務(wù)器計(jì)算能力與平均時(shí)延Fig.5 Computing power of edge server and average latency

內(nèi)存空間大小的改變對(duì)算法性能的影響由圖6 給出，通過(guò)曲線(xiàn)可以看到內(nèi)存空間是影響系統(tǒng)性能的因素之一，除POP 算法外，其他四種算法的平均任務(wù)執(zhí)行時(shí)延隨著內(nèi)存容量的提高而降低。隨著內(nèi)存容量的增加，POP算法緩存了越來(lái)越多的任務(wù)，但由于邊緣服務(wù)器計(jì)算能力的限制，每個(gè)任務(wù)需要更長(zhǎng)的時(shí)間去計(jì)算，從而導(dǎo)致任務(wù)執(zhí)行時(shí)延的增加。而MSAC 算法，SAC 算法，DQN 算法和GEN 算法經(jīng)過(guò)不斷訓(xùn)練或迭代，能夠智能地做出緩存決策，而不是地緩存任務(wù)，從而降低任務(wù)執(zhí)行時(shí)延。與SAC 算法、DQN 算法、GEN 算法和POP 算法對(duì)比，MSAC 算法的性能最好，其任務(wù)平均執(zhí)行時(shí)延分別降低4.7%、17.2%、10.9%、37.8%。

圖6 邊緣服務(wù)器內(nèi)存空間與平均時(shí)延Fig.6 Memory space of edge server and average latency

圖7 為邊緣服務(wù)器初始關(guān)聯(lián)用戶(hù)數(shù)量的改變對(duì)任務(wù)平均執(zhí)行時(shí)延的影響。隨著用戶(hù)數(shù)量的增多，邊緣服務(wù)器分給每個(gè)已緩存任務(wù)的計(jì)算能力變少，導(dǎo)致任務(wù)計(jì)算時(shí)延不斷增加。從圖7可以看出，本文所提MSAC算法性能最好，相比于SAC 算法、DQN 算法、GEN 算法、POP算法，其任務(wù)平均執(zhí)行時(shí)延分別降低約2.3%、11.5%、9.4%、37.6%。

圖7 初始用戶(hù)數(shù)量與平均時(shí)延的關(guān)系Fig.7 Computing power and memory space of edge server

5 結(jié)束語(yǔ)

本文研究了邊緣計(jì)算中多用戶(hù)多服務(wù)器系統(tǒng)中的任務(wù)緩存策略。首先建立了任務(wù)緩存模型，把平均任務(wù)執(zhí)行延遲作為評(píng)價(jià)系統(tǒng)性能的指標(biāo)，并給出了一種等效的強(qiáng)化學(xué)習(xí)形式。提出了一種有效的在線(xiàn)任務(wù)緩存算法MSAC，該算法考慮了邊緣服務(wù)器緩存能力和計(jì)算能力的限制以及相鄰服務(wù)器用戶(hù)任務(wù)請(qǐng)求相似的特點(diǎn)，令相鄰邊緣服務(wù)器之間通過(guò)共享經(jīng)驗(yàn)優(yōu)化緩存決策，以適應(yīng)用戶(hù)任務(wù)請(qǐng)求的變化。多次仿真實(shí)驗(yàn)表明，通過(guò)在邊緣服務(wù)器上部署MSAC算法，可以顯著降低任務(wù)執(zhí)行時(shí)延，且MSAC 算法在不同條件下均有較好的性能表現(xiàn)。下一步工作將把任務(wù)緩存與任務(wù)卸載技術(shù)相結(jié)合，聯(lián)合考慮能耗與時(shí)延的約束，進(jìn)一步優(yōu)化邊緣計(jì)算系統(tǒng)性能。