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

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

1 引言

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

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

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

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

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

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

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

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

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

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

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

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

(1)

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

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

(2)

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

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

(3)

第二種獎勵是緩存操作和一級緩存層流行度配置文件之間的匹配,表示為

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

(4)

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

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

(5)

因為r1表示為緩存操作產(chǎn)生的成本,即負(fù)向收益,r2、r3和r4表示為緩存操作的正向收益。所以t時刻緩存操作a(t)的整體收益可進一步推導(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)

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

(7)

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

(8)

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

(9)

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

(10)

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

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

圖2 A3C架構(gòu)圖

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

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

(11)

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

基于A3C的邊緣緩存算法:

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

輸出:緩存策略

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

repeat

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

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

軌跡中的時間序列tstart=t

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

repeat

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

at=π(at|st;θ′)

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

即時獎勵rt

t=t+1,T=T+1

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

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

R=ri+γR

累計計算梯度θ′

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

累計計算梯度θ′v

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

end for

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

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

until T>Tmax

4 實驗研究

4.1 實驗設(shè)置

為了驗證所提架構(gòu)的性能,進行了模擬仿真。測試的實驗平臺操作系統(tǒng)為Windows10,CPU為2.9GHz,運行內(nèi)存為16GB。本文對緩存系統(tǒng)中的各部分設(shè)置了初始化參數(shù),其中內(nèi)容總數(shù)F=1500、一級緩存容量M=700、二級緩存容量E=300。緩存操作成本及獎勵部分公式的參數(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é)點緩存容量的關(guān)系,在內(nèi)容總數(shù)不變的情況下,邊緣節(jié)點緩存容量較低時,緩存命中率也比較低。當(dāng)邊緣節(jié)點的緩存容量增加時,對于不同的緩存策略,緩存命中率都有不同程度的提高。相比于其它緩存策略,提出的HCEA緩存架構(gòu)表現(xiàn)出了相對較好的緩存命中率,比較適應(yīng)于現(xiàn)實中的緩存場景。

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

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

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

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

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

5 結(jié)論

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