基于深度強(qiáng)化學(xué)習(xí)的數(shù)據(jù)動(dòng)態(tài)傳輸策略

尹將伯, 劉梓田, 梁子寒, 鄧艷紅, 王昌文, 程建東

(1.北京中電普華信息技術(shù)有限公司, 北京 100192;2.華北電力大學(xué), 控制與計(jì)算機(jī)工程學(xué)院, 北京 102206)

0 引言

數(shù)據(jù)中心作為云計(jì)算的核心基礎(chǔ)設(shè)施,具有數(shù)據(jù)匯聚、實(shí)時(shí)監(jiān)測(cè)、分析等能力,這對(duì)數(shù)據(jù)傳輸?shù)姆?wù)質(zhì)量(如吞吐量、傳輸時(shí)延等)提出了很高的要求,先進(jìn)的數(shù)據(jù)傳輸策略模型應(yīng)當(dāng)能夠提高數(shù)據(jù)吞吐量、降低傳輸延遲以提供較好的服務(wù)質(zhì)量。數(shù)據(jù)中心的數(shù)據(jù)傳輸目前主要面臨以下挑戰(zhàn)。

(1) 數(shù)據(jù)種類繁多,大小不一,易出現(xiàn)負(fù)載不均衡等問題,提高了數(shù)據(jù)傳輸?shù)难舆t,降低了傳輸效率。

(2) 數(shù)據(jù)傳輸?shù)沫h(huán)境較為復(fù)雜,傳統(tǒng)算法不能及時(shí)地適應(yīng)復(fù)雜且動(dòng)態(tài)的環(huán)境。

(3) 用戶對(duì)數(shù)據(jù)的需求時(shí)刻變化。數(shù)據(jù)的調(diào)度策略必須根據(jù)實(shí)際情況不斷做出變化。

除此之外,數(shù)據(jù)優(yōu)先級(jí)也影響著對(duì)用戶的服務(wù)質(zhì)量,符合生產(chǎn)需求的優(yōu)先級(jí)分類規(guī)則可以使重要的數(shù)據(jù)盡快傳輸,縮短用戶等待時(shí)間。因此不僅要考慮延遲對(duì)系統(tǒng)的影響,還要考慮數(shù)據(jù)的優(yōu)先級(jí)如何分配。

針對(duì)以上問題,本文設(shè)計(jì)一種基于深度強(qiáng)化學(xué)習(xí)(DRL)的數(shù)據(jù)動(dòng)態(tài)傳輸策略,包括數(shù)據(jù)分類模塊和動(dòng)態(tài)調(diào)度模塊。數(shù)據(jù)分類模塊通過抽取傳輸數(shù)據(jù)中不同維度的實(shí)時(shí)特征,將數(shù)據(jù)分為5個(gè)優(yōu)先級(jí)。動(dòng)態(tài)調(diào)度模塊利用DRL技術(shù),通過最小化數(shù)據(jù)流的平均等待時(shí)間,實(shí)現(xiàn)數(shù)據(jù)的動(dòng)態(tài)調(diào)度,提高數(shù)據(jù)傳輸?shù)男省?/p>

1 理論基礎(chǔ)

強(qiáng)化學(xué)習(xí)是機(jī)器學(xué)習(xí)的一個(gè)熱門研究領(lǐng)域[1]。基本思想是模擬人類在學(xué)習(xí)中“探索”的機(jī)制,通過智能體與環(huán)境的交互過程中獲得的獎(jiǎng)勵(lì)來學(xué)習(xí)最佳決策行為[2]。近幾年,隨著深度學(xué)習(xí)的發(fā)展,DRL將強(qiáng)化學(xué)習(xí)和深度學(xué)習(xí)深度結(jié)合,充分利用了強(qiáng)化學(xué)習(xí)的決策優(yōu)勢(shì)和深度學(xué)習(xí)的感知優(yōu)勢(shì),為復(fù)雜的感知決策問題提供了新方法[3],在很多復(fù)雜的決策問題中都取得了很好的成果。DeepRM[4]是最早將DRL技術(shù)應(yīng)用到資源調(diào)度管理中的模型,通過監(jiān)測(cè)數(shù)據(jù)中心當(dāng)前的CPU、內(nèi)存和待調(diào)度作業(yè)的狀態(tài),分析并做出相應(yīng)的決策。基于裝箱問題框架的作業(yè)調(diào)度算法DeepJS[5],可以自動(dòng)從經(jīng)驗(yàn)中計(jì)算適應(yīng)度,以最小化一組作業(yè)的完成時(shí)間,這種方法不限制輸入維度,可擴(kuò)展性較高。

DRL與強(qiáng)化學(xué)習(xí)類似,主要由智能體、狀態(tài)、動(dòng)作、環(huán)境、策略以及獎(jiǎng)勵(lì)組成。智能體是強(qiáng)化學(xué)習(xí)的本體,其在特定環(huán)境下的某個(gè)初始狀態(tài)st下根據(jù)策略π(s,a)執(zhí)行某一動(dòng)作at,此時(shí)將會(huì)轉(zhuǎn)換到新的狀態(tài)st+1。對(duì)于該狀態(tài),環(huán)境會(huì)反饋一個(gè)獎(jiǎng)勵(lì)值[6]。智能體根據(jù)新的狀態(tài)和反饋的獎(jiǎng)勵(lì)按照策略選取新的動(dòng)作at+1。該交互過程不斷重復(fù),根據(jù)累積的獎(jiǎng)勵(lì)值可以知道自己在當(dāng)前狀態(tài)下應(yīng)執(zhí)行的一系列動(dòng)作。

由于強(qiáng)化學(xué)習(xí)使用二維表來表示策略,當(dāng)狀態(tài)、動(dòng)作空間較大時(shí),表格就會(huì)變得非常龐大,DRL為了解決這一問題,使用神經(jīng)網(wǎng)絡(luò)參數(shù)化的方法基于策略πθ(s,a)來估計(jì)要采取的動(dòng)作及狀態(tài),從而達(dá)到降低維度的目的[7]。

DRL的交互過程如圖1所示。

圖1 深度強(qiáng)化學(xué)習(xí)基本架構(gòu)

圖2 策略模型示意圖

2 策略模型設(shè)計(jì)

本文設(shè)計(jì)的數(shù)據(jù)動(dòng)態(tài)傳輸策略模型共分為數(shù)據(jù)分類和動(dòng)態(tài)調(diào)度2個(gè)模塊。

2.1 數(shù)據(jù)分類模塊

不同類型數(shù)據(jù)的重要程度不同,應(yīng)當(dāng)分配不同的優(yōu)先級(jí)。優(yōu)先級(jí)的級(jí)數(shù)過少或分類粗糙,會(huì)增加等待隊(duì)列的長(zhǎng)度,導(dǎo)致較為重要的數(shù)據(jù)不能及時(shí)傳輸,降低此類數(shù)據(jù)的傳輸效率。級(jí)數(shù)過多會(huì)增加策略模型的決策時(shí)間,降低數(shù)據(jù)傳輸?shù)膶?shí)時(shí)性。

通過分析數(shù)據(jù)的主要特征,根據(jù)每類數(shù)據(jù)的重要程度、緊急程度及用戶需求,策略模型共分為5個(gè)優(yōu)先級(jí)。預(yù)警、報(bào)錯(cuò)等直接影響系統(tǒng)運(yùn)行的監(jiān)測(cè)數(shù)據(jù)最為重要,將其設(shè)置為第一優(yōu)先級(jí),并采用搶占式的調(diào)度策略,以保證傳輸此類數(shù)據(jù)的實(shí)時(shí)效率;為了提供更高的通信服務(wù)質(zhì)量以及用戶個(gè)性化需求,將用戶當(dāng)前申請(qǐng)?jiān)L問的數(shù)據(jù)設(shè)置為第二級(jí);其余數(shù)據(jù)為一般類型數(shù)據(jù),將按照效用函數(shù)設(shè)置3個(gè)優(yōu)先級(jí),以抵消動(dòng)態(tài)調(diào)度模塊可能對(duì)優(yōu)先級(jí)隊(duì)列產(chǎn)生的影響。

針對(duì)數(shù)據(jù)的特點(diǎn)并參考其他研究人員的成果[8],最終選取數(shù)據(jù)訪問頻率、最近訪問時(shí)間及緊急度等維度對(duì)數(shù)據(jù)進(jìn)行評(píng)價(jià),并使用效用函數(shù)來計(jì)算每類數(shù)據(jù)的優(yōu)先等級(jí)。

(1) 訪問頻率

訪問頻繁的數(shù)據(jù),代表其重要程度較高。通過式(1)來計(jì)算訪問頻率的效用函數(shù):

(1)

(2) 最近訪問時(shí)間

根據(jù)數(shù)據(jù)的歷史訪問記錄來進(jìn)行數(shù)據(jù)的分級(jí),核心思想是“如果數(shù)據(jù)最近被訪問過,那么將來被訪問的概率會(huì)更高,也意味著更為重要”。設(shè)定其效用函數(shù)為

U2(i)=Tn/(Tn-Tl(i))

(2)

其中,Tn表示當(dāng)前時(shí)間,Tl(i)表示最近一次的訪問時(shí)間。

(3) 緊急度

不同類型的數(shù)據(jù)對(duì)用戶的緊急程度也是不一樣的。如預(yù)警信息關(guān)系著整個(gè)系統(tǒng)能否正常運(yùn)行,所以將此類數(shù)據(jù)的緊急度設(shè)置為1,將用戶當(dāng)前需要訪問的數(shù)據(jù)設(shè)置為2,其他數(shù)據(jù)設(shè)置為3。

Pi={1,2,3}

(3)

根據(jù)以上3個(gè)效用函數(shù),計(jì)算總效用值來確定每類數(shù)據(jù)的優(yōu)先級(jí):

(4)

2.2 動(dòng)態(tài)調(diào)度模塊

當(dāng)前普遍認(rèn)為,數(shù)據(jù)流的傳輸效率極大影響著數(shù)據(jù)中心的傳輸質(zhì)量。數(shù)據(jù)中心中大部分都是傳輸實(shí)時(shí)性要求較高的數(shù)據(jù),所以如何對(duì)這類數(shù)據(jù)進(jìn)行動(dòng)態(tài)調(diào)度,同時(shí)滿足時(shí)刻變化的用戶需求,是改善數(shù)據(jù)傳輸延遲的關(guān)鍵。

此模塊采用了深度確定性策略梯度算法(DDPG)對(duì)數(shù)據(jù)流進(jìn)行調(diào)度。DDPG算法是DRL中經(jīng)典的無模型、參數(shù)化Actor-Critic算法,結(jié)合確定性策略梯度算法和Deep Q Network算法進(jìn)行學(xué)習(xí)。DDPG算法分為Actor和Critic兩部分。Actor通過與環(huán)境進(jìn)行交互得到四元組(st(i)、at(i)、rt、st+1(i)),并放入經(jīng)驗(yàn)池中。通過經(jīng)驗(yàn)回放[9],使Critic能夠非均勻地抽取輸入的數(shù)據(jù)流狀態(tài)st(i)及當(dāng)前采取的動(dòng)作at(i),即數(shù)據(jù)流的傳輸順序。計(jì)算出在當(dāng)前狀態(tài)下采取該動(dòng)作的價(jià)值函數(shù)Q(s,a|θμ)后,Actor對(duì)Q(s,a|θμ)利用策略梯度定理,從而輸出數(shù)據(jù)流在當(dāng)前狀態(tài)下最優(yōu)的傳輸順序。

J=E(s～ρβ)[μθ(s)Q(s,a)|(a=μθ(s)]

(5)

同時(shí),Critic根據(jù)最優(yōu)傳輸順序進(jìn)行策略的更新:

(6)

其中,N為數(shù)據(jù)流的數(shù)目。此模塊的流程如圖3所示。

圖3 動(dòng)態(tài)調(diào)度模塊流程圖

此模塊的狀態(tài)空間、動(dòng)作空間及獎(jiǎng)勵(lì)設(shè)計(jì)如下。

狀態(tài)空間:將可變長(zhǎng)度的數(shù)據(jù)集St(i)作為狀態(tài)空間。每類數(shù)據(jù)都由其3個(gè)維度以及優(yōu)先級(jí)進(jìn)行標(biāo)識(shí)。

動(dòng)作空間:從數(shù)據(jù)到傳輸順序的映射。對(duì)于每類數(shù)據(jù)i在時(shí)間步t時(shí)其動(dòng)作為at(i)∈[1,N]。其中,N為數(shù)據(jù)個(gè)數(shù)。

獎(jiǎng)勵(lì):數(shù)據(jù)越及時(shí)進(jìn)行傳輸,即等待時(shí)間越短,用戶的滿意度越高。對(duì)于數(shù)據(jù)傳輸來說,等待時(shí)間指數(shù)據(jù)在傳輸隊(duì)列中排隊(duì)等待的時(shí)間,其公式為

(7)

其中,ti為此數(shù)據(jù)流中第i條數(shù)據(jù)的完成時(shí)間,ta,i是第i條數(shù)據(jù)的提交時(shí)間。因此將獎(jiǎng)勵(lì)設(shè)定為

(8)

3 實(shí)驗(yàn)仿真策略性能比較

采用與傳統(tǒng)調(diào)度算法的對(duì)比實(shí)驗(yàn)來評(píng)估本策略模型的性能。

3.1 數(shù)據(jù)集及實(shí)驗(yàn)環(huán)境

為了驗(yàn)證本策略模型在實(shí)際生產(chǎn)環(huán)境中的有效性,實(shí)驗(yàn)使用4000條在數(shù)據(jù)中心截取的真實(shí)數(shù)據(jù),并分為20組數(shù)據(jù)集。其中,10組數(shù)據(jù)集用于模型的訓(xùn)練,10組用于測(cè)試。

實(shí)驗(yàn)假設(shè)數(shù)據(jù)傳輸?shù)奈锢礞溌分挥?條,即數(shù)據(jù)不能同時(shí)被傳輸。為了檢驗(yàn)算法是否能夠有效降低數(shù)據(jù)傳輸?shù)臅r(shí)延,利用2.2小節(jié)中的式(7)和平均完成時(shí)間作為實(shí)驗(yàn)的評(píng)價(jià)指標(biāo)。平均完成時(shí)間是指完成傳輸1條數(shù)據(jù)流所需要的時(shí)間。

3.2 與相近算法的比較

以下實(shí)驗(yàn)將基于DRL的數(shù)據(jù)動(dòng)態(tài)傳輸策略模型與SJF算法、MFQ算法進(jìn)行了比較。SJF算法按照數(shù)據(jù)量大小分配相應(yīng)的優(yōu)先級(jí)。MFQ算法以時(shí)間片輪轉(zhuǎn)的方式進(jìn)行調(diào)度,是目前公認(rèn)的較好的一種基于優(yōu)先級(jí)的進(jìn)程調(diào)度算法。

(1) 算法性能比較

從圖4可以看出:在平均等待時(shí)間及平均完成時(shí)間指標(biāo)下,基于DRL的動(dòng)態(tài)調(diào)整策略模型較MFQ算法的性能提升了約10.83%,這是因?yàn)榛贒RL的策略模型克服了MFQ算法的時(shí)間片可能會(huì)分割數(shù)據(jù)流的問題;基于DRL的策略模型的性能略低于SJF算法,這是因?yàn)镾JF算法優(yōu)先傳輸數(shù)據(jù)量較小的數(shù)據(jù)流,而這種數(shù)據(jù)流在數(shù)據(jù)集中占大多數(shù)。

圖4 不同算法的性能表現(xiàn)

(2) 不同優(yōu)先級(jí)的表現(xiàn)

3種算法針對(duì)不同優(yōu)先級(jí)數(shù)據(jù)的性能表現(xiàn)如圖5所示。由于SJF算法未對(duì)數(shù)據(jù)優(yōu)先級(jí)進(jìn)行特殊優(yōu)化,最重要的第一優(yōu)先級(jí)沒有得到及時(shí)傳輸,但是不同優(yōu)先級(jí)的數(shù)據(jù)平均等待時(shí)間差距較小;MFQ算法雖然考慮了數(shù)據(jù)具有不同優(yōu)先級(jí)的特點(diǎn),但第四、第五優(yōu)先級(jí)數(shù)據(jù)的平均等待時(shí)間都比較高;本文基于DRL的策略模型針對(duì)優(yōu)先級(jí)進(jìn)行了優(yōu)化,5個(gè)優(yōu)先級(jí)數(shù)據(jù)的平均等待時(shí)間較MFQ算法分別提升了7.78%,13.61%、4.52%、24.92%、5.08%,說明基于DRL的調(diào)度策略的性能較高。鑒于合理的優(yōu)先級(jí)分類規(guī)則,第二、第四優(yōu)先級(jí)的指標(biāo)有較大的提升。因?yàn)椴呗阅Ｐ蜎]有平衡每個(gè)優(yōu)先級(jí)之間的指標(biāo)差距,只優(yōu)先傳輸高優(yōu)先級(jí)的數(shù)據(jù),導(dǎo)致第五優(yōu)先級(jí)等待傳輸?shù)臅r(shí)間較長(zhǎng),因此需要進(jìn)一步優(yōu)化。

圖5 不同算法基于優(yōu)先級(jí)的性能表現(xiàn)

4 總結(jié)

本文設(shè)計(jì)了一種基于深度強(qiáng)化學(xué)習(xí)的數(shù)據(jù)動(dòng)態(tài)傳輸策略模型,針對(duì)數(shù)據(jù)不同維度的特征進(jìn)行分析并分配優(yōu)先級(jí),以最小化平均等待時(shí)間為優(yōu)化目標(biāo)對(duì)數(shù)據(jù)進(jìn)行調(diào)度。對(duì)比實(shí)驗(yàn)結(jié)果表明,該策略模型在數(shù)據(jù)傳輸?shù)难舆t優(yōu)化問題上有著較好的性能,有效降低了數(shù)據(jù)中心在數(shù)據(jù)傳輸過程中的延遲,提升了數(shù)據(jù)傳輸?shù)男省?/p>