梁 楊,丁長(zhǎng)松,胡志剛

(1.湖南中醫(yī)藥大學(xué)信息科學(xué)與工程學(xué)院,湖南 長(zhǎng)沙 410208)(2.湖南省中醫(yī)藥大數(shù)據(jù)分析實(shí)驗(yàn)室,湖南 長(zhǎng)沙 410208)(3.中南大學(xué)計(jì)算機(jī)學(xué)院,湖南 長(zhǎng)沙 410083)

近年來(lái),智能手機(jī)、聯(lián)網(wǎng)汽車、AR/VR等智能設(shè)備快速普及,各類移動(dòng)終端產(chǎn)生的數(shù)據(jù)量呈爆炸式增長(zhǎng)[1]. 多接入邊緣計(jì)算(multi-access edge computing,MEC)作為一種鄰近計(jì)算范式,其本質(zhì)是云計(jì)算向邊緣網(wǎng)絡(luò)的延伸. MEC允許邊緣服務(wù)器分布在不同的地理位置,將計(jì)算和存儲(chǔ)資源部署在移動(dòng)用戶附近,因此可以提供比云計(jì)算服務(wù)更低延遲[2]. MEC框架在滿足訪問(wèn)時(shí)延的前提下,在節(jié)省網(wǎng)絡(luò)帶寬、提高服務(wù)質(zhì)量(quality of service,QoS)、緩解數(shù)據(jù)中心壓力等方面具有天然的優(yōu)勢(shì). 然而,在數(shù)據(jù)密集型應(yīng)用場(chǎng)景下因資源受限所帶來(lái)的一系列問(wèn)題正引起研究者們的廣泛關(guān)注[3]. 由于邊緣節(jié)點(diǎn)存儲(chǔ)資源有限,數(shù)據(jù)密集型應(yīng)用會(huì)頻繁地進(jìn)行遠(yuǎn)程數(shù)據(jù)訪問(wèn),從而導(dǎo)致較高的往返延遲,甚至完全抵消MEC的優(yōu)勢(shì)[4].

在MEC環(huán)境中,大量移動(dòng)邊緣設(shè)備將不斷產(chǎn)生和消費(fèi)各類數(shù)據(jù),不恰當(dāng)?shù)母北竟芾聿呗詷O易導(dǎo)致網(wǎng)絡(luò)資源浪費(fèi)和通信延遲過(guò)高[5]. 一方面,當(dāng)處理本地用戶任務(wù)的數(shù)據(jù)訪問(wèn)請(qǐng)求時(shí),由于邊緣節(jié)點(diǎn)存在嚴(yán)重自治,通常需要分別創(chuàng)建副本以減少遠(yuǎn)程數(shù)據(jù)訪問(wèn)的次數(shù),很容易出現(xiàn)副本的高冗余存儲(chǔ)和高頻次更新,導(dǎo)致“副本泛濫”、資源浪費(fèi)等問(wèn)題[6];另一方面,云邊網(wǎng)絡(luò)用戶對(duì)數(shù)據(jù)副本的多邊高并發(fā)請(qǐng)求具有隨機(jī)性和區(qū)域性,增加了“副本管理失控”的風(fēng)險(xiǎn)[7]. 因此對(duì)數(shù)據(jù)副本進(jìn)行全局部署時(shí),需要綜合權(quán)衡局部和全局的資源互補(bǔ)與沖突,進(jìn)而確定最佳副本布局.

一般,不合理的副本部署不僅會(huì)增加任務(wù)響應(yīng)延遲,還會(huì)增加網(wǎng)絡(luò)和存儲(chǔ)開(kāi)銷[8]. 為解決上述問(wèn)題,本文提出一種基于“推薦-學(xué)習(xí)”的兩階段數(shù)據(jù)布局策略(two-stage data placement strategy,TDPS),通過(guò)“推薦”階段和“學(xué)習(xí)”階段對(duì)副本放置規(guī)則進(jìn)行深度優(yōu)化. TDPS綜合考慮了副本流行度和用戶移動(dòng)性,旨在實(shí)現(xiàn)訪問(wèn)延遲和成本開(kāi)銷的權(quán)衡優(yōu)化. 綜上所述,本文的主要貢獻(xiàn)包括4個(gè)方面:

(1)提出了一種基于“推薦-學(xué)習(xí)”的兩階段副本管理框架,通過(guò)將MEC環(huán)境下副本決策過(guò)程分解為“邊緣推薦”和“整體學(xué)習(xí)”兩個(gè)階段,有效整合了邊緣端的局部信息和云端的全局信息,優(yōu)化了副本管理機(jī)制;

(2)對(duì)目標(biāo)問(wèn)題進(jìn)行形式化描述并構(gòu)建了數(shù)學(xué)模型,將MEC中的副本放置決策問(wèn)題描述為具有延遲和成本約束的雙目標(biāo)優(yōu)化問(wèn)題;

(3)在“推薦”階段,提出一個(gè)基于移動(dòng)預(yù)測(cè)和反饋優(yōu)化的副本推薦引擎,一定程度上解決了盲目創(chuàng)建副本的問(wèn)題;在“學(xué)習(xí)”階段,提出一個(gè)基于A3C強(qiáng)化學(xué)習(xí)的副本放置規(guī)則學(xué)習(xí)模型,從全局視角下進(jìn)一步保證了云邊系統(tǒng)的數(shù)據(jù)服務(wù)性能最優(yōu);

(4)實(shí)驗(yàn)結(jié)果表明,本文基于“推薦-學(xué)習(xí)”的兩階段數(shù)據(jù)布局策略可以有效降低數(shù)據(jù)管理成本并改善用戶QoS滿意度.

1 相關(guān)工作

隨著云計(jì)算和邊緣計(jì)算逐步融合,如何提高云邊系統(tǒng)的副本管理效率成為一個(gè)新興的研究熱點(diǎn),引起國(guó)內(nèi)外研究者的廣泛關(guān)注[9]. 一些研究學(xué)者提出了基于數(shù)據(jù)流行度的靜態(tài)副本策略[10],在指定的存儲(chǔ)節(jié)點(diǎn)上設(shè)置固定的副本數(shù)量;而另外一些研究人員則提出了動(dòng)態(tài)副本策略[11-12],允許根據(jù)用戶的行為特征動(dòng)態(tài)地調(diào)整副本數(shù)量和位置. Jin等[13]提出了一種邊端協(xié)作存儲(chǔ)框架,在邊緣計(jì)算環(huán)境中協(xié)作存儲(chǔ)必要的數(shù)據(jù),以提高邊緣層的性能,減少將任務(wù)轉(zhuǎn)移到云數(shù)據(jù)中心的可能性. Vales等[14]提出一個(gè)將移動(dòng)設(shè)備的存儲(chǔ)資源和霧節(jié)點(diǎn)集中起來(lái)的解決方案,有效解決了用戶訪問(wèn)遠(yuǎn)程云時(shí)面臨的訪問(wèn)延遲、帶寬受限、通信開(kāi)銷和位置盲目性等問(wèn)題. Chang等[15]通過(guò)分析邊緣服務(wù)器的數(shù)據(jù)副本收入、成本和利潤(rùn),提出了面向MEC的自適應(yīng)副本機(jī)制,有效地縮短了任務(wù)平均響應(yīng)時(shí)間,提高了數(shù)據(jù)分組的服務(wù)質(zhì)量.

由于邊緣端存儲(chǔ)資源和通信帶寬都存在一定限制,副本優(yōu)化機(jī)制需要充分考慮資源受限條件下的副本管理. Teranishi等[16]提出了一種面向邊緣環(huán)境下物聯(lián)網(wǎng)應(yīng)用的動(dòng)態(tài)數(shù)據(jù)流平臺(tái),不僅能夠使物聯(lián)網(wǎng)應(yīng)用實(shí)現(xiàn)較小的延遲,而且可以避免物聯(lián)網(wǎng)應(yīng)用對(duì)網(wǎng)絡(luò)和計(jì)算資源造成過(guò)載;研究者還提出了一個(gè)具有多因素最少使用算法的分布式多級(jí)存儲(chǔ)模型[17],為處理海量物聯(lián)網(wǎng)數(shù)據(jù)時(shí)可能面臨的存儲(chǔ)受限和網(wǎng)絡(luò)擁塞等問(wèn)題提供了有效的解決方案;Aral等[18]提出了一種智能分布式數(shù)據(jù)部署方案,解決了數(shù)據(jù)訪問(wèn)延遲和副本放置成本等問(wèn)題.

以上早期研究雖然考慮了邊緣端資源的有限性,但主要不足之處在于沒(méi)有充分利用云端已有的高性能資源. 對(duì)此,一些研究者針對(duì)云邊系統(tǒng)的副本管理優(yōu)化提出了若干新方法,其中最為突出的是基于機(jī)器學(xué)習(xí)的副本管理. Wang等[19]提出了一種基于強(qiáng)化學(xué)習(xí)的副本緩存框架,用于激勵(lì)邊緣設(shè)備為周邊用戶提供副本存儲(chǔ)服務(wù);為了能夠自適應(yīng)地利用網(wǎng)絡(luò)資源并降低任務(wù)響應(yīng)時(shí)間,研究者還提出了一種基于深度強(qiáng)化學(xué)習(xí)的智能資源分配方案[20]. 以上研究顯示,機(jī)器學(xué)習(xí)技術(shù)在實(shí)現(xiàn)“在線副本服務(wù)”方面具有較好的自適應(yīng)性和魯棒性.

綜上所述,優(yōu)化數(shù)據(jù)布局既需要考慮邊緣資源的受限性,還需要考慮網(wǎng)絡(luò)傳輸速度的差異性. 本文從以上兩個(gè)方面來(lái)分析現(xiàn)有系統(tǒng)數(shù)據(jù)服務(wù)的性能瓶頸,并提出基于“推薦-學(xué)習(xí)”的兩階段數(shù)據(jù)布局策略來(lái)動(dòng)態(tài)協(xié)調(diào)云端和邊緣端的存儲(chǔ)資源分配,以期充分利用云端的高性能來(lái)彌補(bǔ)邊緣端的資源短缺.

2 系統(tǒng)框架和數(shù)學(xué)模型

根據(jù)云邊環(huán)境下面向移動(dòng)用戶的典型應(yīng)用場(chǎng)景,本節(jié)提出了一個(gè)兩階段副本管理框架,并對(duì)目標(biāo)問(wèn)題進(jìn)行模型構(gòu)建.

2.1 基于“推薦-學(xué)習(xí)”的兩階段副本管理框架

在云邊協(xié)同系統(tǒng)中,一個(gè)有效的數(shù)據(jù)布局策略必須充分考慮云端和邊緣端資源性能的差異. 針對(duì)由此導(dǎo)致的一系列性能瓶頸問(wèn)題,本文提出了一種基于“推薦-學(xué)習(xí)”的兩階段副本管理機(jī)制TDPS,其整體架構(gòu)如圖1所示.

圖1 基于“推薦-學(xué)習(xí)”的兩階段副本管理架構(gòu)

在圖1中,TDPS架構(gòu)從邏輯上自下而上主要包含3層:用戶設(shè)備層、邊緣節(jié)點(diǎn)層和中心節(jié)點(diǎn)層.

(1)用戶設(shè)備層:主要包含各種具有移動(dòng)性的用戶設(shè)備,需要向邊緣云或中心云請(qǐng)求數(shù)據(jù)服務(wù).

(2)邊緣節(jié)點(diǎn)層:主要由分布式邊緣節(jié)點(diǎn)組成,各邊緣節(jié)點(diǎn)部署有副本推薦引擎、邊緣資源管理器和本地狀態(tài)信息表,負(fù)責(zé)向中心節(jié)點(diǎn)層推薦熱點(diǎn)副本.

(3)中心節(jié)點(diǎn)層:云數(shù)據(jù)中心是本層的重要組件,主要包括副本放置規(guī)則學(xué)習(xí)模型、全局資源管理器和全網(wǎng)資源狀態(tài)表,負(fù)責(zé)對(duì)全網(wǎng)數(shù)據(jù)布局進(jìn)行決策.

2.2 問(wèn)題描述與系統(tǒng)建模

假設(shè)E={e1,e2,…,en}表示所有邊緣節(jié)點(diǎn)的集合,n為邊緣節(jié)點(diǎn)的總數(shù);F={f1,f2,…,fm}表示所有可訪問(wèn)的文件全集,m為文件總數(shù);SZfi表示文件fi的大小.用戶所感知的訪問(wèn)延遲主要依賴于用戶和待訪問(wèn)文件之間的距離,則用戶和其對(duì)應(yīng)邊緣節(jié)點(diǎn)之間的平均等待延遲如式(1)所示.

(1)

式中,VE表示邊緣節(jié)點(diǎn)的數(shù)據(jù)傳輸速率;NRfi表示用戶請(qǐng)求訪問(wèn)文件fi的總次數(shù).Xfi,ej是一個(gè)二進(jìn)制變量,用以表示fi的副本是否位于ej上,如果fi的副本位于ej上,則Xfi,ej=1;否則Xfi,ej=0.

簡(jiǎn)化起見(jiàn),假設(shè)云數(shù)據(jù)中心存儲(chǔ)了所有文件的副本,如果用戶對(duì)fi的訪問(wèn)請(qǐng)求沒(méi)有在本地得到滿足,則必須向遠(yuǎn)程云請(qǐng)求fi,用戶與云數(shù)據(jù)中心之間的平均等待延遲可以表示為式(2).

(2)

此外,資源開(kāi)銷同樣制約著數(shù)據(jù)布局問(wèn)題的決策.本文主要考慮副本放置過(guò)程中網(wǎng)絡(luò)傳輸成本和邊緣存儲(chǔ)成本對(duì)總成本的影響.網(wǎng)絡(luò)傳輸成本是指文件從云數(shù)據(jù)中心傳輸?shù)竭吘壒?jié)點(diǎn)所產(chǎn)生的網(wǎng)絡(luò)傳輸開(kāi)銷,如式(3)所示.

(3)

式中,Tunit表示從云數(shù)據(jù)中心到邊緣節(jié)點(diǎn)的單位數(shù)據(jù)傳輸成本,Ctx表示總傳輸開(kāi)銷.

此外,因副本放置造成的存儲(chǔ)開(kāi)銷亦不容忽視,則邊緣節(jié)點(diǎn)的副本存儲(chǔ)成本可以表示為式(4)所示.

(4)

式中,Sunit表示邊緣節(jié)點(diǎn)上單位數(shù)據(jù)的存儲(chǔ)成本,Csto表示總存儲(chǔ)開(kāi)銷.

目標(biāo)問(wèn)題進(jìn)一步轉(zhuǎn)化為式(5)所示.

Ψ=μ(ALE+ALC)+η(Ctx+Csto),

(5)

式中,μ+η=1,0<μ,η<1.

基于上述分析,為表示延遲和成本敏感的數(shù)據(jù)布局問(wèn)題,構(gòu)建了如式(6)所示的雙目標(biāo)優(yōu)化函數(shù).

(6)

3 基于“推薦-學(xué)習(xí)”的兩階段副本管理機(jī)制

本節(jié)提出一種基于“推薦-學(xué)習(xí)”的兩階段副本管理機(jī)制,綜合權(quán)衡全網(wǎng)的QoS和資源開(kāi)銷,進(jìn)而確定當(dāng)前工作周期內(nèi)最優(yōu)的全局副本放置規(guī)則. 在副本推薦階段,通過(guò)在邊緣節(jié)點(diǎn)上構(gòu)建副本推薦引擎快速、準(zhǔn)確地量化邊緣層副本訪問(wèn)價(jià)值,縮小存在副本需求的局部文件規(guī)模,避免云端/邊緣端盲目創(chuàng)建副本,使服務(wù)提供商在保證QoS的同時(shí)減少不必要的資源開(kāi)銷;在副本放置階段,云數(shù)據(jù)中心基于強(qiáng)化學(xué)習(xí)構(gòu)建全局副本放置規(guī)則學(xué)習(xí)模型,優(yōu)化數(shù)據(jù)布局,以期指導(dǎo)副本管理中間件進(jìn)行副本放置和替換,在QoS和成本開(kāi)銷間達(dá)到最佳折中,從整體上改進(jìn)云邊環(huán)境下副本服務(wù)的各類性能指標(biāo).

3.1 基于移動(dòng)預(yù)測(cè)和反饋優(yōu)化的副本推薦引擎

為了快速、準(zhǔn)確地量化邊緣端副本價(jià)值,最大程度減小副本規(guī)模,本文首先在邊緣節(jié)點(diǎn)上構(gòu)建副本推薦引擎,從局部層面上避免副本的盲目創(chuàng)建.

一方面,推薦引擎必須充分考慮用戶移動(dòng)性和文件訪問(wèn)特性,從而準(zhǔn)確評(píng)估文件訪問(wèn)概率;另一方面,引入反饋機(jī)制及時(shí)修正誤差,提高推薦引擎自適應(yīng)性. 基于此,副本推薦引擎的框架如圖2所示.

圖2 基于移動(dòng)預(yù)測(cè)和反饋優(yōu)化的副本推薦引擎

由圖2可以看出,副本推薦引擎主要由輸入層、預(yù)測(cè)層、反饋層和推薦層組成. 其中,輸入層負(fù)責(zé)對(duì)數(shù)據(jù)進(jìn)行預(yù)處理以滿足模型輸入的要求;預(yù)測(cè)層根據(jù)文件歷史流行度和用戶移動(dòng)性來(lái)預(yù)測(cè)本地節(jié)點(diǎn)上不同副本的期望訪問(wèn)概率;反饋層負(fù)責(zé)將副本的預(yù)測(cè)誤差輸入到反饋優(yōu)化器,計(jì)算誤差期望并確定補(bǔ)償系數(shù),及時(shí)反饋給預(yù)測(cè)層優(yōu)化預(yù)測(cè)精度;推薦層負(fù)責(zé)篩選滿足條件的副本,從中選擇價(jià)值排名靠前的若干副本,構(gòu)成副本推薦序列.

(7)

(8)

由此可見(jiàn),副本推薦引擎同時(shí)考慮了邊緣節(jié)點(diǎn)上的文件歷史訪問(wèn)流行度和用戶移動(dòng)性的影響.

為改善價(jià)值評(píng)估模型性能,提高模型自適應(yīng)能力,本文在推薦引擎中引入反饋層,對(duì)預(yù)測(cè)層結(jié)果進(jìn)行誤差分析,通過(guò)補(bǔ)償系數(shù)進(jìn)一步對(duì)模型進(jìn)行修正,則式(8)進(jìn)一步改進(jìn)為式(9)所示.

(9)

式中,λtc表示在時(shí)段tc時(shí)的模型補(bǔ)償系數(shù),且λtc>0.

最后,推薦引擎將根據(jù)副本期望訪問(wèn)概率進(jìn)行推薦,具體推薦過(guò)程如算法1所示.

首先,將tc時(shí)段邊緣節(jié)點(diǎn)es上的所有文件的期望訪問(wèn)概率集作為推薦層的輸入;其次,根據(jù)價(jià)值閾值篩選出期望訪問(wèn)概率不低于該閾值的文件;最后,如果存在滿足閾值要求的文件,則返回期望訪問(wèn)概率中排名前K(K>0)的副本標(biāo)識(shí)符列表.

算法1 副本推薦算法

② fori=1 tomdo

⑤ else

⑥FPPNew[i]=0;

⑦ end if

⑧ end for

⑨ ifFPPNew!=NULL then

⑩FPPTopK[·]=TopK(FPPNew);

3.2 基于A3C強(qiáng)化學(xué)習(xí)的副本放置規(guī)則學(xué)習(xí)模型

邊緣端推薦的副本序列存在一定的局部性限制,為保證全局層面的QoS和系統(tǒng)性能最優(yōu),本文提出一種基于異步優(yōu)勢(shì)行動(dòng)者-評(píng)論家算法(asynchronous advantage actor-critic,A3C)的副本放置規(guī)則學(xué)習(xí)模型,采用基于多線程機(jī)制的異步訓(xùn)練框架,引入優(yōu)勢(shì)函數(shù)對(duì)策略網(wǎng)絡(luò)(Actor)和價(jià)值網(wǎng)絡(luò)(Critic)進(jìn)行更新,使模型在訓(xùn)練速度、收斂性能和預(yù)測(cè)精度等方面具有更好的表現(xiàn). 該模型由多個(gè)并行子線程和一個(gè)全局網(wǎng)絡(luò)組成,每個(gè)子線程由一個(gè)Actor和一個(gè)Critic組成,負(fù)責(zé)獨(dú)立運(yùn)行Actor-Critic算法和并行進(jìn)行參數(shù)探索,既獨(dú)立更新全局網(wǎng)絡(luò)參數(shù),又從全局網(wǎng)絡(luò)獲取參數(shù)指導(dǎo);全局網(wǎng)絡(luò)主要包括一個(gè)全局Actor和一個(gè)全局Critic,負(fù)責(zé)匯總子線程與環(huán)境交互的結(jié)果,異步更新全局網(wǎng)絡(luò)參數(shù).

(10)

式中,T表示矩陣轉(zhuǎn)置,πj表示ej上的副本放置模式,πj,i表示fi的副本放置在ej上的概率,πj,i∈[0,1].πj,i=0表示fi的副本不能放置在ej上;反之,πj,i=1.

為有效度量智能體所選動(dòng)作策略的優(yōu)劣,本文提出一個(gè)延遲-成本組合獎(jiǎng)勵(lì)函數(shù),如式(11)所示.

(11)

式中,Lt(St,At)和Ct(St,At)分別表示在狀態(tài)-動(dòng)作對(duì)(St,At)下的訪問(wèn)延遲和成本開(kāi)銷,LCt(St,At)表示組合獎(jiǎng)勵(lì).基于此,長(zhǎng)期累計(jì)獎(jiǎng)勵(lì)如式(12)所示.

(12)

式中,γ∈(0,1]為折扣因子,表示從環(huán)境狀態(tài)St開(kāi)始,未來(lái)環(huán)境獎(jiǎng)勵(lì)對(duì)累計(jì)獎(jiǎng)勵(lì)的影響權(quán)重.顯然,模型訓(xùn)練目標(biāo)可以表示為最大化長(zhǎng)期累計(jì)獎(jiǎng)勵(lì)的期望,如式(13)所示.

(13)

式中,環(huán)境狀態(tài)S服從先驗(yàn)分布F0,π表示在環(huán)境狀態(tài)St下選擇的副本放置策略,則此時(shí)狀態(tài)價(jià)值函數(shù)如式(14)所示.

Vπ(St)=Eπ[Rt|St=S],

(14)

類似地,智能體的動(dòng)作價(jià)值函數(shù)如式(15)所示.

Qπ(St,At)=LCt(St,At)+γVπ(St+1),

(15)

為尋找使長(zhǎng)期累計(jì)獎(jiǎng)勵(lì)期望最大化的副本放置策略π,需要不斷更新策略參數(shù)θ,對(duì)此,智能體采用優(yōu)勢(shì)函數(shù)來(lái)評(píng)價(jià)某一策略動(dòng)作所產(chǎn)生的增益大小,如式(16)所示.

Aπ(St,At)=Qπ(St,At)-Vπ(St),

(16)

式中,Vπ(S)的值由Critic網(wǎng)絡(luò)訓(xùn)練獲得,若Aπ(S,A)>0,則表示在狀態(tài)St下執(zhí)行的動(dòng)作有利于獎(jiǎng)勵(lì)的增加,策略參數(shù)可以朝梯度方向更新以改進(jìn)副本放置策略;反之,則不建議更新策略參數(shù).為加快長(zhǎng)期累計(jì)獎(jiǎng)勵(lì)期望收斂,通過(guò)梯度上升法更新Actor策略網(wǎng)絡(luò)參數(shù)θ,如式(17)所示.

θ=θ+μθlogπ(At|St;θ)Aπ(St,At),

(17)

式中,π(At|St;θ)∈[0,1]表示在St和θ條件下執(zhí)行At的概率,logπ(At|St;θ)∈[0,+∞)避免了梯度消失.μ為學(xué)習(xí)率,μ∈[10e-6,1].另外,為避免過(guò)早陷入局部收斂,在策略函數(shù)的損失函數(shù)中需增加π的交叉熵項(xiàng),則式(17)可改進(jìn)為式(18)所示.

θ=θ+μθlogπ(At|St;θ)Aπ(St,At)+ηθH[π(St;θ)],

(18)

式中,η為交叉熵權(quán)重因子,η∈[0,1].基于時(shí)間差分方法進(jìn)行Critic價(jià)值網(wǎng)絡(luò)參數(shù)更新,其價(jià)值函數(shù)的損失函數(shù)如式(19)所示.

LOSS=(Qπ(St,At)-Vπ(St))2,

(19)

為加快式(19)所示損失函數(shù)收斂,通過(guò)梯度下降法更新Critic策略網(wǎng)絡(luò)參數(shù)θv,如式(20)所示.

(20)

式中,ε為學(xué)習(xí)率,ε∈[10e-6,1].對(duì)此,副本放置規(guī)則的A3C子線程學(xué)習(xí)算法偽代碼如算法2所示.

算法2 A3C子線程學(xué)習(xí)算法

輸入:環(huán)境狀態(tài)集合S,智能體動(dòng)作集合A,A3C全局網(wǎng)絡(luò)的全局Actor參數(shù)θ和全局Critic參數(shù)θv,A3C子線程的Actor參數(shù)θ′和Critic參數(shù)θ′v,全局最大迭代次數(shù)Tmax和全局迭代計(jì)數(shù)器T,子線程單次迭代最大時(shí)間序列tmax和本地線程時(shí)間序列計(jì)數(shù)器t,折扣因子γ,學(xué)習(xí)率μ、ε,交叉熵權(quán)重因子η;

輸出:A3C全局神經(jīng)網(wǎng)絡(luò)參數(shù)θ、θv.

①T=0 andt=1

② repeat

③ dθ←0 and dθv←0;

④θ′←θandθ′v←θv;

⑤tstart=tandSt=getState(t);

⑥ repeat

⑦ 基于π(At|St;θ′)執(zhí)行動(dòng)作At;

⑧ 獲得LCt(St,At) andSt+1;

⑨t(yī)←t+1 andT←T+1;

⑩ untilt-tstart==tmaxorSt==ST

4 結(jié)果與討論

為評(píng)價(jià)和分析所提出算法的性能,本文引入副本命中率、平均訪問(wèn)延遲和成本節(jié)約率等[22]3項(xiàng)測(cè)試指標(biāo)作為評(píng)估標(biāo)準(zhǔn),將TDPS策略與其他基準(zhǔn)算法進(jìn)行比較,驗(yàn)證所提算法在副本決策方面的有效性.

4.1 實(shí)驗(yàn)環(huán)境設(shè)置

本文采用EdgecloudSim[23]平臺(tái)進(jìn)行仿真實(shí)驗(yàn),模擬云邊環(huán)境. 邊緣節(jié)點(diǎn)的位置分布由BRITE[24]拓?fù)渖善鹘o出,中心節(jié)點(diǎn)設(shè)置為距離各邊緣較遠(yuǎn)的數(shù)據(jù)中心. 為了便于比較和分析,假定所有待訪問(wèn)文件的大小相等,用戶提交的作業(yè)請(qǐng)求近似服從泊松分布,初始數(shù)據(jù)位置近似服從齊夫分布,用戶優(yōu)先向附近邊緣節(jié)點(diǎn)提出訪問(wèn)請(qǐng)求,實(shí)驗(yàn)參數(shù)的詳細(xì)設(shè)置如表1所示.

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

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

本實(shí)驗(yàn)將TDPS分別與D-ReP[18]、RPME[25]和HRS[26]3種基準(zhǔn)算法在副本命中率、平均訪問(wèn)延遲和成本節(jié)約率等方面進(jìn)行對(duì)比,每次對(duì)比實(shí)驗(yàn)采用同一性能指標(biāo),分別進(jìn)行10組獨(dú)立重復(fù)實(shí)驗(yàn),以評(píng)估TDPS策略的性能,具體實(shí)驗(yàn)結(jié)果與分析如下:

(1)副本命中率

副本命中率(replica hit rate,RHR)表示本地副本訪問(wèn)次數(shù)占本地用戶請(qǐng)求總數(shù)的比例,用以衡量該策略的本地化水平,如式(21)所示.

(21)

圖3 不同副本部署策略的副本命中率比較

圖3表明,當(dāng)并發(fā)請(qǐng)求規(guī)模較小時(shí),TDPS的副本命中率與其他算法差距不大,甚至略低于某些算法;隨著并發(fā)請(qǐng)求數(shù)的增加,副本命中率總體呈上升趨勢(shì),而TDPS的增長(zhǎng)幅度明顯高于其他算法,說(shuō)明其具有更好的副本放置決策能力. 主要原因是TDPS同時(shí)考慮了文件歷史流行度和用戶移動(dòng)性帶來(lái)的影響,通過(guò)預(yù)測(cè)用戶位置并提前放置數(shù)據(jù)副本,有效提高了副本命中率;當(dāng)并發(fā)請(qǐng)求規(guī)模較大時(shí),各算法副本命中率的變化幅度不明顯,原因在于邊緣節(jié)點(diǎn)存儲(chǔ)空間有限,當(dāng)副本數(shù)增加到一定程度后,僅進(jìn)行必要的副本替換,副本命中率趨于穩(wěn)定.

(2)平均訪問(wèn)延遲

平均訪問(wèn)延遲(average access latency,AAL)表示從作業(yè)提交數(shù)據(jù)訪問(wèn)請(qǐng)求到作業(yè)執(zhí)行完成的平均持續(xù)時(shí)間,如式(22)所示.

(22)

式中,ti(end)和ti(start)分別表示作業(yè)i的完成時(shí)間和開(kāi)始時(shí)間,Q表示用戶提交的作業(yè)總數(shù). 圖4對(duì)比了TDPS與基準(zhǔn)算法在平均訪問(wèn)延遲方面的表現(xiàn).

圖4 不同副本部署策略的平均訪問(wèn)延遲比較

由圖4可以看出,當(dāng)并發(fā)請(qǐng)求數(shù)較少時(shí),不同方法的平均訪問(wèn)延遲差別不大,TDPS的平均訪問(wèn)延遲甚至高于HRS,這是因?yàn)椴煌呗詣?chuàng)建的副本數(shù)量均處于較低水平,使得服務(wù)響應(yīng)時(shí)間較為接近;當(dāng)并發(fā)請(qǐng)求數(shù)達(dá)到500左右時(shí),TDPS的平均訪問(wèn)延遲比D-ReP減少約17.9%,比RPME減少約24.6%,原因在于TRMM具有更高的副本命中率;隨著并發(fā)請(qǐng)求的增加,TDPS平均訪問(wèn)延遲的增長(zhǎng)率明顯低于其他算法,進(jìn)一步說(shuō)明TDPS能夠有效增加用戶就近訪問(wèn)數(shù)據(jù)的機(jī)會(huì).

(3)成本節(jié)約率

成本節(jié)約率(cost saving rate,CSR)表示在所有作業(yè)請(qǐng)求中邊緣節(jié)點(diǎn)完成的作業(yè)總費(fèi)用與中心節(jié)點(diǎn)完成的作業(yè)總費(fèi)用之比,如式(23)所示.

(23)

圖5 不同副本部署策略的成本節(jié)約率比較

在圖5中,當(dāng)并發(fā)請(qǐng)求規(guī)模較小時(shí),TDPS與其他基準(zhǔn)算法的成本節(jié)約率差距不大,各策略的成本節(jié)約率隨著并發(fā)請(qǐng)求數(shù)的增加而增加;當(dāng)并發(fā)請(qǐng)求數(shù)達(dá)到500時(shí),與HRS、D-ReP和RPME 3個(gè)基準(zhǔn)算法相比,TDPS分別能夠節(jié)約2.68%、5.57%和8.43%的成本開(kāi)銷;之后,隨著并發(fā)請(qǐng)求規(guī)模繼續(xù)增大,不同算法的成本節(jié)約率雖時(shí)有波動(dòng),但變化幅度始終處于一個(gè)較小范圍,總體維持動(dòng)態(tài)平衡. 總體而言,TDPS能夠更顯著地提高成本節(jié)約率,原因在于:一方面,TDPS通過(guò)分布式副本推薦引擎為各邊緣節(jié)點(diǎn)推薦個(gè)性化副本序列,控制了局部副本規(guī)模;另一方面,TDPS基于副本放置規(guī)則學(xué)習(xí)模型優(yōu)化面向全網(wǎng)的副本放置決策,控制了全局副本規(guī)模. 因此,TDPS采用“推薦-學(xué)習(xí)”的兩級(jí)副本管理機(jī)制在成本控制方面的表現(xiàn)更優(yōu).

5 結(jié)論

本文提出一種基于“推薦-學(xué)習(xí)”的兩階段數(shù)據(jù)布局策略TDPS,解決云邊環(huán)境下面向數(shù)據(jù)密集型應(yīng)用如何改善用戶QoS滿意度并降低云邊協(xié)同集群的管理和維護(hù)成本等核心問(wèn)題. 采用基于移動(dòng)預(yù)測(cè)和反饋優(yōu)化的副本推薦引擎挖掘局部熱點(diǎn)副本,通過(guò)基于A3C強(qiáng)化學(xué)習(xí)的副本放置規(guī)則學(xué)習(xí)模型有機(jī)整合邊緣推薦信息,優(yōu)化全網(wǎng)數(shù)據(jù)布局. 將TDPS與其他基準(zhǔn)算法對(duì)比,實(shí)驗(yàn)結(jié)果表明,所提出策略在不同測(cè)試指標(biāo)下都明顯優(yōu)于其他算法,驗(yàn)證了所提出方法的有效性. 下一步工作將考慮如何根據(jù)大規(guī)模分布式節(jié)點(diǎn)異構(gòu)性調(diào)整數(shù)據(jù)布局策略,并在真實(shí)場(chǎng)景下對(duì)研究問(wèn)題進(jìn)行實(shí)驗(yàn)驗(yàn)證.