基于強(qiáng)化學(xué)習(xí)的分層協(xié)作邊緣緩存架構(gòu)

賈宗璞,鄭 帥,任建吉,原永亮

(1. 河南理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,河南 焦作 454003;2. 河南理工大學(xué)機(jī)械與動(dòng)力工程學(xué)院,河南 焦作 454003)

1 引言

隨著5G技術(shù)的發(fā)展和普及,移動(dòng)設(shè)備和應(yīng)用程序的數(shù)量迅速增加,產(chǎn)生的海量數(shù)據(jù)給網(wǎng)絡(luò)帶來(lái)了巨大的流量壓力[1]。傳統(tǒng)的內(nèi)容獲取方式是通過(guò)回程鏈路從骨干網(wǎng)下載,這種重復(fù)的訪問(wèn)方式會(huì)帶來(lái)大量冗余數(shù)據(jù)流量[2]。邊緣緩存的思想是將內(nèi)容下沉至邊緣節(jié)點(diǎn),實(shí)現(xiàn)就近內(nèi)容服務(wù),來(lái)顯著提高網(wǎng)絡(luò)傳輸效率。它被認(rèn)為是緩解回程鏈路和蜂窩網(wǎng)絡(luò)流量壓力的一種有效的方式[3]。通過(guò)在網(wǎng)絡(luò)邊緣緩存適當(dāng)?shù)膬?nèi)容,可以在本地滿足用戶對(duì)相同內(nèi)容的需求,而不是通過(guò)回程網(wǎng)絡(luò)重復(fù)傳輸[4,5]。

在實(shí)際的應(yīng)用場(chǎng)景中,由于緩存系統(tǒng)所處環(huán)境是不斷變化的,所以緩存內(nèi)容不能按照固定的策略來(lái)進(jìn)行。基于強(qiáng)化學(xué)習(xí)的緩存方法可以更好地適應(yīng)不斷變化的環(huán)境,并及時(shí)進(jìn)行緩存策略的更新。Chen等人在文獻(xiàn)[6]中使用Wolpertinger架構(gòu)的強(qiáng)化學(xué)習(xí)框架研究無(wú)線網(wǎng)絡(luò)邊緣的內(nèi)容緩存,研究?jī)?nèi)容沒(méi)有關(guān)注內(nèi)容流行度分布。Sadeghi等人在文獻(xiàn)[7]中提出基于Q-Learning的強(qiáng)化學(xué)習(xí)方案,沒(méi)有考慮到服務(wù)區(qū)域擴(kuò)大的問(wèn)題。Hu等人在文獻(xiàn)[8]中使用遷移學(xué)習(xí)來(lái)解決新增節(jié)點(diǎn)的冷啟動(dòng)問(wèn)題,沒(méi)有考慮到新增節(jié)點(diǎn)最近鄰的選取問(wèn)題。

本文考慮到新增節(jié)點(diǎn)最近鄰的選取、分層緩存等問(wèn)題,提出了一種基于A3C強(qiáng)化學(xué)習(xí)算法的的分層協(xié)作邊緣緩存架構(gòu)。使用KNN算法尋找新增節(jié)點(diǎn)的最近鄰節(jié)點(diǎn),進(jìn)而通過(guò)遷移學(xué)習(xí),解決新增節(jié)點(diǎn)的冷啟動(dòng)問(wèn)題。此外設(shè)計(jì)雙層網(wǎng)絡(luò)模型架構(gòu),以減少回程鏈路負(fù)載,進(jìn)一步降低訪問(wèn)延遲。仿真結(jié)果表明,本文提出的HECA架構(gòu)在提高緩存命中率和解決冷啟動(dòng)問(wèn)題的有效性。

2 系統(tǒng)模型與問(wèn)題表述

如圖1所示,該架構(gòu)包括四層:數(shù)據(jù)中心層、一級(jí)緩存層、二級(jí)緩存層和用戶層。

圖1 邊緣緩存系統(tǒng)架構(gòu)圖

數(shù)據(jù)中心層(DC):包含該系統(tǒng)的所有數(shù)據(jù),下層緩存層無(wú)法滿足的內(nèi)容請(qǐng)求將最終發(fā)送到這一層,再將用戶請(qǐng)求的內(nèi)容逐級(jí)下發(fā)直到最終發(fā)回給用戶。

一級(jí)緩存層(BBS):一級(jí)緩存層(BBS)和二級(jí)緩存層(SBS)功能類似,都是起到緩存數(shù)據(jù)的作用,這種分層的緩存模式可以將下層用戶的需求控制在一定區(qū)域內(nèi)解決,從而減小數(shù)據(jù)中心層以及主干網(wǎng)的壓力。

二級(jí)緩存層(SBS):節(jié)點(diǎn)部署在靠近用戶的邊緣側(cè)。在邊緣端部署的每個(gè)節(jié)點(diǎn),響應(yīng)其覆蓋區(qū)域內(nèi)所有用戶。當(dāng)用戶區(qū)域擴(kuò)大時(shí),則需要新增節(jié)點(diǎn)來(lái)提供服務(wù)?？紤]到相鄰區(qū)域內(nèi)的用戶有著相似的本地內(nèi)容流行特征。當(dāng)出現(xiàn)新增節(jié)點(diǎn)時(shí),通過(guò)KNN算法找到新增節(jié)點(diǎn)的最近節(jié)點(diǎn),然后通過(guò)遷移學(xué)習(xí)將找到的最近鄰節(jié)點(diǎn)的神經(jīng)網(wǎng)絡(luò)參數(shù)傳遞給新增節(jié)點(diǎn),從而降低新增節(jié)點(diǎn)的訓(xùn)練時(shí)間,使其快速收斂到最優(yōu)策略。

用戶層:內(nèi)容的請(qǐng)求方,用戶向SBS層提交他們的內(nèi)容請(qǐng)求。每個(gè)對(duì)應(yīng)的SBS在其存儲(chǔ)單元中搜索內(nèi)容。如果內(nèi)容存在,則SBS直接將內(nèi)容提供給用戶。否則SBS將用戶的請(qǐng)求發(fā)送到一級(jí)緩存層BBS。每個(gè)對(duì)應(yīng)的BBS在其緩存中搜索請(qǐng)求的內(nèi)容。如果存在,則BBS將其提供給下級(jí)SBS。否則,BBS將請(qǐng)求發(fā)送到數(shù)據(jù)中心層。在數(shù)據(jù)中心層,存儲(chǔ)了用戶請(qǐng)求所需的全部?jī)?nèi)容。數(shù)據(jù)中心在收到請(qǐng)求后將通過(guò)回程鏈路將內(nèi)容發(fā)送到BBS,進(jìn)而發(fā)送到SBS,直至傳送給請(qǐng)求相應(yīng)內(nèi)容的用戶。

緩存系統(tǒng)中的每個(gè)SBS、BBS都是基站,容量大小不同。每個(gè)單獨(dú)的基站都有一個(gè)緩存控制單元(CCU),目的在控制緩存過(guò)程并獲取最佳緩存策略[9]。本文定義每個(gè)SBS存儲(chǔ)E個(gè)內(nèi)容,每個(gè)BBS存儲(chǔ)M個(gè)內(nèi)容,數(shù)據(jù)中心共F個(gè)內(nèi)容?？紤]到一級(jí)緩存和二級(jí)緩存的功能類似。在接下來(lái)的描述中,本文主要對(duì)二級(jí)緩存進(jìn)行詳細(xì)描述。對(duì)于每個(gè)SBS以及數(shù)據(jù)中心的F個(gè)內(nèi)容,定義F×1的動(dòng)作矩陣。動(dòng)作矩陣可以表示為a(t)∈A,其中A是所有可行動(dòng)作的集合,定義為

A={a|a∈{0,1}F,aF1=E}

(1)

在每個(gè)時(shí)刻的t開(kāi)始,SBS中的CCU會(huì)根據(jù)當(dāng)前環(huán)境狀態(tài)和緩存策略執(zhí)行相應(yīng)緩存操作。本地和全局內(nèi)容流行度分別定義為pl(t)、pg(t)。因?yàn)樵O(shè)計(jì)的緩存架構(gòu)總計(jì)有四層,所以定義緩存收益由一個(gè)成本和三個(gè)部分的獎(jiǎng)勵(lì)組成。產(chǎn)生的成本是內(nèi)容替換產(chǎn)生的,定義為

r1,t(a(t),a(t-1))=λ1aT(t)(1-a(t-1))

(2)

第一種獎(jiǎng)勵(lì)是緩存操作和二級(jí)緩存層流行度配置文件之間的匹配,即當(dāng)用戶請(qǐng)求時(shí)內(nèi)容存儲(chǔ)在SBS中的獎(jiǎng)勵(lì),表示為

r2,t(s(t))=λ2aT(t)pl(t)

(3)

第二種獎(jiǎng)勵(lì)是緩存操作和一級(jí)緩存層流行度配置文件之間的匹配,表示為

r3,t(s(t))=λ3aT(t)pm(t)

(4)

第三種獎(jiǎng)勵(lì)是緩存操作和全局流行度配置文件之間的匹配,表示為

r4,t(s(t))=λ4aT(t)pg(t)

(5)

因?yàn)閞1表示為緩存操作產(chǎn)生的成本,即負(fù)向收益,r2、r3和r4表示為緩存操作的正向收益。所以t時(shí)刻緩存操作a(t)的整體收益可進(jìn)一步推導(dǎo)為

B(t)=-r1,t(a(t),a(t-1))+r2,t(s(t))+r3,t(s(t))+r4,t(s(t))

=-λ1aT(t)(1-a(t-1))+λ2aT(t)pl(t)+λ3aT(t)pm(t)

+λ4aT(t)pg(t)

(6)

面對(duì)當(dāng)前狀態(tài)s(t),本文通過(guò)緩存策略獲得將要執(zhí)行的緩存操作,緩存操作來(lái)指導(dǎo)具體緩存哪些內(nèi)容。緩存策略的性能由狀態(tài)值函數(shù)判斷,狀態(tài)值函數(shù)定義為

(7)

由于緩存策略和s(t)、a(t)和s(t+1)相關(guān)聯(lián),并且當(dāng)前的緩存操作對(duì)未來(lái)是有一定影響的。所以這個(gè)狀態(tài)值函數(shù)顯示了從當(dāng)前時(shí)間τ到無(wú)限時(shí)間的總回報(bào),呈現(xiàn)累加的形式,又考慮到當(dāng)前操作對(duì)后續(xù)的影響逐漸減小,所以引入因折扣因子γ∈(0,1)來(lái)進(jìn)行計(jì)算?；谏鲜鐾普?最優(yōu)緩存策略π*可以定義為

(8)

通過(guò)動(dòng)作a從當(dāng)前狀態(tài)s到下一個(gè)狀態(tài)s′的轉(zhuǎn)移概率被定義為[Pa]ss′。通過(guò)貝爾曼方程,狀態(tài)值函數(shù)可以進(jìn)一步推導(dǎo)為

(9)

最佳狀態(tài)值函數(shù)可以表示為

(10)

3 邊緣緩存算法設(shè)計(jì)

通過(guò)強(qiáng)化學(xué)習(xí)算法可以得到最佳緩存策略以及最佳狀態(tài)值函數(shù)。如圖2所示,A3C算法是一種異步多線程強(qiáng)化學(xué)習(xí)算法,它包含一個(gè)全局網(wǎng)絡(luò)和多個(gè)actor-critic網(wǎng)絡(luò),actor網(wǎng)絡(luò)產(chǎn)生緩存策略,critic網(wǎng)絡(luò)提供一種評(píng)估機(jī)制來(lái)評(píng)估獲得的緩存策略[10]。每個(gè)worker定期將新更新的參數(shù)上傳到全局網(wǎng)絡(luò),全局網(wǎng)絡(luò)經(jīng)過(guò)經(jīng)驗(yàn)整合及時(shí)將更新后的參數(shù)分發(fā)給所有worker。

圖2 A3C架構(gòu)圖

在全局網(wǎng)絡(luò)中,actor參數(shù)表示為θ,critic參數(shù)表示為θv。在每個(gè)worker中,actor參數(shù)表示為θ′,critic參數(shù)表示為θ′v。緩存策略表示為π(a|s;θ′)。如算法中所示,提出的基于A3C的邊緣緩存算法是N步返回算法,即單個(gè)worker步數(shù)達(dá)到MAX＿STEP時(shí)又從初始狀態(tài)開(kāi)始。所以本文定義動(dòng)作狀態(tài)值函數(shù)R為

R=Bi+γBi+1+γ2Bi+2+…+γt-iR

(11)

其中i∈{t-1,t-2,…,t-N},N個(gè)連續(xù)狀態(tài)中的動(dòng)作狀態(tài)值是相關(guān)的。

基于A3C的邊緣緩存算法:

輸入:初始化值Tmax、tmax,折扣因子γ

輸出:緩存策略

初始化參數(shù)時(shí)刻t=1,總迭代次數(shù)T=0

repeat

重置梯度dθ=0,dθv=0

更新worker異步線程參數(shù)θ′=θ,θ′v=θv

軌跡中的時(shí)間序列tstart=t

獲取當(dāng)前時(shí)刻狀態(tài)St

repeat

根據(jù)緩存策略和當(dāng)前狀態(tài)選擇動(dòng)作

at=π(at|st;θ′)

根據(jù)動(dòng)作at跳轉(zhuǎn)到狀態(tài)st+1并獲得

即時(shí)獎(jiǎng)勵(lì)rt

t=t+1,T=T+1

until st==terminal或者t-tstart==tmax

fori∈{t-1,…,tstart}do

R=ri+γR

累計(jì)計(jì)算梯度θ′

dθ=dθ+?θ′logπ(ai|si;θ′)(R-V(si;θ′v))

累計(jì)計(jì)算梯度θ′v

dθv=dθv+?(R-V(si;θ′v))2/?θ′v

end for

將當(dāng)前worker計(jì)算獲得的累計(jì)梯度異

步更新到全局網(wǎng)絡(luò)

until T>Tmax

4 實(shí)驗(yàn)研究

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

為了驗(yàn)證所提架構(gòu)的性能,進(jìn)行了模擬仿真。測(cè)試的實(shí)驗(yàn)平臺(tái)操作系統(tǒng)為Windows10,CPU為2.9GHz,運(yùn)行內(nèi)存為16GB。本文對(duì)緩存系統(tǒng)中的各部分設(shè)置了初始化參數(shù),其中內(nèi)容總數(shù)F=1500、一級(jí)緩存容量M=700、二級(jí)緩存容量E=300。緩存操作成本及獎(jiǎng)勵(lì)部分公式的參數(shù)設(shè)置為:λ1=10,λ2=60,λ3=600,λ4=1000。各層Zipf模型的參數(shù)分別為ηl=1.2、ηm=1.5、ηg=1.7。

4.2 仿真結(jié)果分析

圖3顯示了緩存命中率和邊緣節(jié)點(diǎn)緩存容量的關(guān)系,在內(nèi)容總數(shù)不變的情況下,邊緣節(jié)點(diǎn)緩存容量較低時(shí),緩存命中率也比較低。當(dāng)邊緣節(jié)點(diǎn)的緩存容量增加時(shí),對(duì)于不同的緩存策略,緩存命中率都有不同程度的提高。相比于其它緩存策略,提出的HCEA緩存架構(gòu)表現(xiàn)出了相對(duì)較好的緩存命中率,比較適應(yīng)于現(xiàn)實(shí)中的緩存場(chǎng)景。

圖3 緩存命中率與邊緣緩存容量

如圖4所示,在邊緣節(jié)點(diǎn)緩存容量和流行度分布等參數(shù)不變的情況下。隨著迭代次數(shù)的增加,緩存命中率剛開(kāi)始是逐漸增大的,后期隨著緩存系統(tǒng)逐漸適應(yīng)環(huán)境,緩存命中率逐漸趨于穩(wěn)定。提出的HCEA緩存架構(gòu)幾乎滿足了用戶65%的內(nèi)容請(qǐng)求,其命中率比Q-Learning、LRU、LFU和FIFO分別高出約4%、10%、13%和17%。

圖4 緩存命中率與迭代次數(shù)

對(duì)于遷移學(xué)習(xí)解決新增節(jié)點(diǎn)的冷啟動(dòng)問(wèn)題,本文同樣做了實(shí)驗(yàn)驗(yàn)證,并對(duì)比了不使用傳遞來(lái)的神經(jīng)網(wǎng)絡(luò)參數(shù)和使用傳遞來(lái)的神經(jīng)網(wǎng)絡(luò)參數(shù)這兩種訓(xùn)練。從圖5中的訓(xùn)練結(jié)果可以看出,在使用遷移學(xué)習(xí)的情況下,新增節(jié)點(diǎn)將更快地達(dá)到收斂狀態(tài),從而更快找到最佳緩存策略。

圖5 遷移學(xué)習(xí)的A3C性能比較

5 結(jié)論

在本文中,為了解決用戶在進(jìn)行內(nèi)容訪問(wèn)時(shí)的延遲問(wèn)題,提出了一種基于強(qiáng)化學(xué)習(xí)的分層協(xié)作邊緣緩存架構(gòu)HCEA。為了評(píng)價(jià)架構(gòu)的性能進(jìn)行了仿真,將其與Q-Learning、LRU、LFU和FIFO算法進(jìn)行了比較。仿真結(jié)果表明,所提出的架構(gòu)在緩存命中率及解決冷啟動(dòng)問(wèn)題方面是有效的。本次工作仍有一些不足之處需要在以后的工作中完善。本研究只考慮了內(nèi)容的流行性,沒(méi)有內(nèi)容的特征。內(nèi)容之間是有相似性的,接下來(lái)的研究中將在緩存架構(gòu)中考慮到這一點(diǎn)。