馬新新，管昕潔，白光偉，糜元根

(南京工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇 南京 211816)

0 引 言

現(xiàn)在交通場景中，智能輔助駕駛應(yīng)用程序不斷涌現(xiàn)，此類應(yīng)用通常對服務(wù)時(shí)延要求極為苛刻，由于路況瞬息萬變，過高服務(wù)延遲將會對用戶造成很大影響。究其高服務(wù)時(shí)延的原因主要是通信時(shí)延，此外在服務(wù)器端的處理時(shí)延[1]，以及如今各式各樣的終端設(shè)備通過核心網(wǎng)絡(luò)傳輸海量數(shù)據(jù)，信道的擁堵、服務(wù)器的任務(wù)等待造成的服務(wù)等待時(shí)延，種種方面的原因都提高了通信的時(shí)延。

而傳統(tǒng)云計(jì)算架構(gòu)將很難滿足低延遲應(yīng)用程序的需求，為縮減網(wǎng)絡(luò)延遲，移動邊緣計(jì)算(MEC)作為一種新的網(wǎng)絡(luò)架構(gòu)用來解決時(shí)延問題。對MEC的研究一直是熱點(diǎn)，尤其是邊緣服務(wù)器的選擇一直是研究的焦點(diǎn)問題，但現(xiàn)有研究多從節(jié)能[2]、高效負(fù)載[3]、服務(wù)器放置[4]著手，僅少量研究考慮了時(shí)延敏感應(yīng)用程序的使用場景，特別是在快速服務(wù)尤為重要的交通應(yīng)用程序中。

考慮到上述的問題，本文聚焦于城市范圍內(nèi)的智能公共交通場景下的智能應(yīng)用部署，如自動報(bào)站系統(tǒng)、車載安全監(jiān)控系統(tǒng)等。本文設(shè)計(jì)了一種最小化應(yīng)用服務(wù)時(shí)延的模型與部署策略，并提出一種基于深度強(qiáng)化學(xué)習(xí)(DQN)的方法求解最優(yōu)部署方案，能有效滿足交通場景下應(yīng)用對低時(shí)延嚴(yán)苛的要求。

1 相關(guān)介紹

本文為能最大化減小應(yīng)用的服務(wù)時(shí)延，采用了Docker容器和微服務(wù)框架相組合的新架構(gòu)，此外，從應(yīng)用部署的實(shí)例化過程著手，盡可能減少來自底層部署的時(shí)延。在方案求解使用了近年來火熱的深度強(qiáng)化學(xué)習(xí)方法，相對于一般啟發(fā)式算法有著更快的求解速度。下文對相關(guān)知識做出介紹。

1.1 應(yīng)用程序?qū)嵗^程

用戶使用程序服務(wù)會通過用戶終端將服務(wù)請求提交至邊緣服務(wù)器，服務(wù)器收到請求后作出若干部署決策，后對應(yīng)用程序進(jìn)行部署?？紤]到節(jié)能、降低成本等實(shí)際情況，運(yùn)營商將部分服務(wù)器設(shè)置為低功耗睡眠狀態(tài)。當(dāng)應(yīng)用程序部署所在服務(wù)器處于睡眠狀態(tài)，部署操作將其喚醒并進(jìn)入正常待機(jī)狀態(tài)，隨后相關(guān)服務(wù)器為新虛擬機(jī)搭建相關(guān)運(yùn)行環(huán)境。搭建過程包括諸如下載、提取(extracting)系統(tǒng)文件、庫文件，在容器中此類文件稱為鏡像。運(yùn)行環(huán)境搭建完成后應(yīng)用程序即可正常運(yùn)行，期間服務(wù)端可能會與終端進(jìn)行數(shù)據(jù)傳遞。過程如圖1所示。

圖1 應(yīng)用程序?qū)嵗^程

1.2 實(shí)例化中的鏡像重復(fù)下載

系統(tǒng)周期進(jìn)行鏡像快照(snapshot)操作會占用高額存儲空間，為節(jié)省空間，在服務(wù)結(jié)束后系統(tǒng)將移除服務(wù)鏡像。而在一個(gè)服務(wù)器上反復(fù)運(yùn)行同一個(gè)程序或同類型程序時(shí)，所需的基礎(chǔ)鏡像幾乎相同，每次運(yùn)行時(shí)的重新下載變?yōu)轭~外的下載代價(jià)。如多個(gè)應(yīng)用程序均在ubuntu上運(yùn)行，一個(gè)ubuntu 15.10的鏡像文件大約有51 MB，下載、提取此文件需要數(shù)秒時(shí)間，期間用戶不能進(jìn)行任何操作。而利用鏡像文件重用的方式，僅首個(gè)應(yīng)用程序會有一定下載時(shí)延，之后的應(yīng)用程序則可直接使用已有鏡像文件，再下載剩余所需文件即可補(bǔ)足運(yùn)行環(huán)境，此方式避免了重復(fù)下載。

1.3 微服務(wù)架構(gòu)的優(yōu)勢

微服務(wù)架構(gòu)提倡將單一應(yīng)用程序作為多種服務(wù)的組合，不同服務(wù)功能可以通過不同語言編寫、使用不用數(shù)據(jù)存儲技術(shù),并能獨(dú)立部署。微服務(wù)架構(gòu)的優(yōu)勢眾多，一方面微服務(wù)組件化的結(jié)構(gòu)可以分散、靈活地部署在不同物理機(jī)上，每一個(gè)模塊都可以獨(dú)立運(yùn)行；另一方面，整體應(yīng)用程序由于其高耦合性，程序全部功能整合于一體，只有將各功能所需環(huán)境全部部署完畢才能運(yùn)行程序。此外某一個(gè)功能如果需要更新，則要將整個(gè)程序代碼重新部署。而在微服務(wù)框架下，每個(gè)組件僅需下載自身所需的運(yùn)行環(huán)境，相對于整體部署則大大降低了部署代價(jià)。例如：一個(gè)應(yīng)用程序此時(shí)需要遷移3次，整體程序需要將完整代碼和環(huán)境部署3次。而在微服務(wù)框架下，只遷移當(dāng)前所需的服務(wù)模塊而并不處理其余模塊，所部署的代碼和環(huán)境文件數(shù)量遠(yuǎn)低于3次整體程序的總數(shù)量。

1.4 微服務(wù)應(yīng)用程序的構(gòu)成

本文中應(yīng)用程序由多個(gè)服務(wù)子任務(wù)組成，將其視為一條串行虛擬服務(wù)鏈。如：在圖像渲染服務(wù)[9]中，將整個(gè)工作流程分為頂點(diǎn)處理(vertex process)、裁剪和原始組裝(clipping and primitively assembling)、光柵化(rasteri-zing)、片段處理(fragment processing)，各部分服務(wù)依次進(jìn)行，每一階段服務(wù)的處理結(jié)果都將作為輸入送入下階段服務(wù)中。將程序分解為不同功能服務(wù)模塊后，各功能模塊可運(yùn)行在不同服務(wù)器上，增強(qiáng)了程序部署和維護(hù)的靈活性。需要注意的是，服務(wù)模塊并不全都在服務(wù)器上運(yùn)行，如人臉識別服務(wù)中，第一步的拍攝功能在終端設(shè)備上完成，捕獲圖像后才將數(shù)據(jù)傳入服務(wù)器進(jìn)行處理。為支持智能公交系統(tǒng)，本文假設(shè)將部署多套應(yīng)用程序，同時(shí)為了提高資源使用效率，所有的應(yīng)用程序都使用微服務(wù)架構(gòu)。

1.5 代價(jià)的定義

為將實(shí)際中時(shí)延和能耗統(tǒng)一簡化計(jì)算，本文將其抽象為一系列代價(jià)。MEC提倡將應(yīng)用程序托管至離用戶較近的小型云服務(wù)器中，從地理上縮短應(yīng)用程序終端和服務(wù)端之間的通信距離，由此降低所用服務(wù)器與終端之間的通信代價(jià)(communication cost)，并減輕核心網(wǎng)絡(luò)中的擁塞情況。通信時(shí)延在本文內(nèi)被抽象為通信代價(jià)，降低通信代價(jià)可視作減小通信時(shí)延。另外值得注意的是，隨著用戶的不斷移動，用戶與托管應(yīng)用程序的服務(wù)器距離可能會不斷變化，由此產(chǎn)生的通信代價(jià)變化可能導(dǎo)致服務(wù)器切換等情況，此情況下會產(chǎn)生高額的遷移代價(jià)[10](migration cost)，另外應(yīng)用程序遷移至新服務(wù)器上可能產(chǎn)生額外的部署代價(jià)(deployment cost)。同時(shí)在服務(wù)器運(yùn)行時(shí)也包括多種代價(jià)：從選中指定服務(wù)器開始，包括正常運(yùn)行時(shí)的基線能耗(運(yùn)行代價(jià))，也包括諸如：喚醒休眠服務(wù)器、下載鏡像文件等部署代價(jià)。

1.6 深度強(qiáng)化學(xué)習(xí)(DQN)

實(shí)際環(huán)境中并不能獲得完整的狀態(tài)轉(zhuǎn)移矩陣，根據(jù)bellman方程(公式)將值函數(shù)(回報(bào))分解為兩個(gè)部分：

(1)立即可得的回報(bào)；

(2)之前回報(bào)的折扣值。

可以將此等式看作狀態(tài)值函數(shù)和行為值函數(shù)自身以及相互之間的遞推關(guān)系

V(s)=maxα(R(s,a)+γV(s′))

(1)

Bellman方程是強(qiáng)化學(xué)習(xí)的理論基礎(chǔ)，狀態(tài)值函數(shù)和行為值函數(shù)的遞推關(guān)系也正是獲得未來信息的一種方式。然而在實(shí)際應(yīng)用中，狀態(tài)以及動作的維度往往很大，僅僅用傳統(tǒng)的數(shù)據(jù)結(jié)構(gòu)難以存儲如此巨大的信息，而深度神經(jīng)網(wǎng)絡(luò)的出現(xiàn)也讓強(qiáng)化學(xué)習(xí)的方法再次受到關(guān)注。在強(qiáng)化學(xué)習(xí)的基礎(chǔ)上，深度神經(jīng)網(wǎng)絡(luò)的增加使得此學(xué)習(xí)方法獲得以下優(yōu)勢：

(1)神經(jīng)網(wǎng)絡(luò)在高度結(jié)構(gòu)化的特征提取方面表現(xiàn)優(yōu)異，使得強(qiáng)化學(xué)習(xí)可以直接從高維原始數(shù)據(jù)學(xué)習(xí)控制；

(2)傳統(tǒng)強(qiáng)化學(xué)習(xí)的Q-table有著規(guī)模限制，很多問題在現(xiàn)實(shí)世界里無法遍歷全部狀態(tài)，而神經(jīng)網(wǎng)絡(luò)可以根據(jù)先前經(jīng)驗(yàn)直接生成所需價(jià)值函數(shù)。

綜合以上問題、方法，本文提出了一種綜合考慮了部署代價(jià)、通信代價(jià)以及遷移代價(jià)的新型應(yīng)用布局策略MIN-COST。布局模型基于微服務(wù)架構(gòu)和容器技術(shù)，將應(yīng)用程序以靈活的模塊化方式部署在邊緣服務(wù)器中，同時(shí)利用容器技術(shù)的輕量化部署方式滿足低時(shí)延需求的交通應(yīng)用程序，而達(dá)到降低總代價(jià)、減少用戶等待時(shí)延目的。在使用基于DQN的方法后可以快速獲得全局最優(yōu)布局方案，減少了使用一般算法的計(jì)算用時(shí)并且不受限于問題規(guī)模的擴(kuò)張。

2 最優(yōu)應(yīng)用部署策略(MIN-COST)

為最大化降低邊緣計(jì)算場景下的智能交通應(yīng)用從部署到服務(wù)的整體時(shí)延，我們提出了一種基于微服務(wù)框架的應(yīng)用程序并應(yīng)用于Docker容器的最優(yōu)應(yīng)用部署策略(MIN-COST)，下文將對此策略做詳細(xì)介紹。

2.1 建模目標(biāo)

本文將智能公交應(yīng)用程序布局問題建模為最小化總代價(jià)的優(yōu)化問題。優(yōu)化目標(biāo)是最小化由部署代價(jià)、通信代價(jià)、遷移代價(jià)組合成的總布局代價(jià)，具體體現(xiàn)在：①盡可能減少活動物理機(jī)器的數(shù)量；②提高鏡像文件重用；③縮短應(yīng)用程序副本與用戶之間的通信距離；以及，④減少由用戶移動引起的服務(wù)遷移次數(shù)。

2.2 相關(guān)參數(shù)

假設(shè)一個(gè)由n個(gè)MEC計(jì)算集群覆蓋的城市，這些集群為城市的公交系統(tǒng)提供計(jì)算服務(wù)，其中每個(gè)集群中有若干物理機(jī)，用一個(gè)Ni表示某一個(gè)具體的物理機(jī)。簡單起見，認(rèn)為全部物理機(jī)有相同的計(jì)算能力，但每個(gè)物理機(jī)擁有計(jì)算資源各不相同，即每臺物理機(jī)處理任務(wù)速度相同但支持運(yùn)行任務(wù)數(shù)量不盡相同。所設(shè)公交系統(tǒng)中，有k個(gè)不同的應(yīng)用程序(task)，進(jìn)一步假設(shè)每個(gè)應(yīng)用程序Ak∈task可以被視作一條虛擬微服務(wù)鏈Sk，虛擬微服務(wù)鏈Sk={α1,α2,α3…} 由多個(gè)功能模塊組成，每個(gè)微服務(wù)模塊αd∈Sk,d∈N可以具有多個(gè)副本，這些副本在不同的物理機(jī)上通過容器部署并以并行的方式執(zhí)行不相交的子任務(wù)(不同的功能模塊任務(wù))。這里每個(gè)微服務(wù)被表示為元組 (τα，Lα,l，Rm,α)， 其中，τα指定微服務(wù)α的最大允許服務(wù)時(shí)延。Lα,l表示用于部署微服務(wù)α所需支持鏡像集。Rm,α表示微服務(wù)α總計(jì)算量。本文涉及其它參數(shù)由表1列出。

表1 相關(guān)參數(shù)

2.3 相關(guān)變量

模型中有以下3種變量：x(i,t) 用來判斷物理機(jī)i在t時(shí)刻狀態(tài)，如果物理機(jī)i在此刻為工作狀態(tài)則x(i,t)=1， 否則為0；y(i,t,m,α) 用來判斷在t時(shí)刻，用戶m應(yīng)用程序中的微服務(wù)α是否映射到物理機(jī)i上，如果已被映射則y(i,t,m,α)=1， 否則為0；L(i,t,l) 判斷t時(shí)刻物理機(jī)i上是否有鏡像l，如果存在則L(i,t,l)=1， 否則為0。通過此3個(gè)變量，可以獲得在某一個(gè)時(shí)刻的全部物理機(jī)工作狀態(tài)，即一臺正常運(yùn)行的物理機(jī)上已下載的支持鏡像文件和正在運(yùn)行的應(yīng)用程序模塊。

2.4 模型分析

將整體優(yōu)化模型表述為式(2)

COST=Cop+Ccom+Cmig

(2)

總代價(jià)由3個(gè)部分構(gòu)成，分別為部署代價(jià)、通信代價(jià)和遷移代價(jià)。

部署代價(jià)(Cop)：

部署代價(jià)被描述為一個(gè)新建容器在物理機(jī)上所造成的一系列能耗，其中包括了以下各種能耗代價(jià)：

(1)下載所需環(huán)境的能耗，此過程包括下載、提取鏡像文件所用時(shí)間，以及產(chǎn)生的額外能耗，此代價(jià)用εl表示；

(2)喚醒已睡眠物理機(jī)的能耗，此過程包括休眠物理機(jī)啟動用時(shí)，以及休眠轉(zhuǎn)化為正常運(yùn)行的能耗，此代價(jià)用Ca表示；

(3)物理機(jī)的基線能耗，即物理機(jī)正常運(yùn)行時(shí)所必要的能耗，此代價(jià)用Cb表示；

(4)物理機(jī)運(yùn)算時(shí)的額外能耗，由于處理用戶應(yīng)用程序服務(wù)，物理機(jī)需要提供額外的計(jì)算資源，也需提供額外的計(jì)算能耗，此代價(jià)用Rm,α*Δ表示。

部署代價(jià)由式(3)表示出

(3)

式(3)可分為4部分代價(jià)的累加：第一部分為服務(wù)器正常運(yùn)行時(shí)的基線代價(jià)；第二部分為服務(wù)器處理用戶應(yīng)用程序服務(wù)的計(jì)算產(chǎn)生的額外代價(jià)；第三部分為下載所需鏡像的下載代價(jià)；第四部分為處于休眠服務(wù)器被喚醒的啟動代價(jià)。

通信代價(jià)(Ccom)：遷移能耗被描述為應(yīng)用程序不同微服務(wù)間的必要信息傳輸，體現(xiàn)在串行服務(wù)間上一層的輸出傳到下一層并作為輸入再次進(jìn)行計(jì)算的過程。同時(shí)還考慮到虛擬微服務(wù)鏈中首尾服務(wù)和用戶的通信。通信代價(jià)由式(4)表示出

(4)

式(4)中由3部分累加所得，第一部分為同一應(yīng)用程序在兩個(gè)服務(wù)器之間的數(shù)據(jù)遷移的通信代價(jià)；第二部分為用戶終端上傳應(yīng)用程序數(shù)據(jù)的通信代價(jià)；第三部分為用戶終端接受應(yīng)用程序數(shù)據(jù)的通信代價(jià)。

其中u(i,m(t)) 是控制用戶應(yīng)用程序放置位置的關(guān)鍵參數(shù)，將每一時(shí)刻用戶于全部物理機(jī)的通信距離都記錄，實(shí)驗(yàn)時(shí)此記錄作為輸入數(shù)據(jù)進(jìn)入模型計(jì)算。

遷移代價(jià)(Cmig)：遷移能耗被描述為容器信息在當(dāng)前物理機(jī)中復(fù)制到其它物理機(jī)上所用的能耗，這部分代價(jià)主要與物理機(jī)之間通信距離有關(guān)，在同一集群的物理機(jī)之間遷移會比跨集群的物理機(jī)之間遷移代價(jià)要小很多[11]。遷移代價(jià)由式(5)表示出

(5)

式(5)中只有兩個(gè)變量x(i,(t-1),m,α) 和y(j,t,m,α) 均賦值為1時(shí)才有遷移代價(jià)，即在(t-1)時(shí)刻用戶m的微服務(wù)α運(yùn)行在物理機(jī)i上，在下一個(gè)時(shí)刻t此微服務(wù)α運(yùn)行在物理機(jī)j上，則說明微服務(wù)進(jìn)行了遷移。

優(yōu)化目標(biāo)和約束條件：將系統(tǒng)模型結(jié)果最小化獲得最終優(yōu)化目標(biāo)。優(yōu)化目標(biāo)由式(6)表示

min{Cop+Ccom+Cmig}

(6)

此外，優(yōu)化模型包括若干約束條件(s.t.)，具體如下：

約束1：保證已放置微服務(wù)模塊的物理機(jī)是開啟的，即在時(shí)刻t時(shí)，當(dāng)物理機(jī)i已經(jīng)成功運(yùn)行微服務(wù)α?xí)r，物理機(jī)i必定是處于工作狀態(tài)。

s.t. 1

x(i,t)≥y(i,t,m,α),?i,t,m,α

約束2：保證鏡像文件的正確表示，變量L(i,t,l) 需始終大于等于右邊公式，即在t時(shí)刻，當(dāng)物理機(jī)已經(jīng)成功運(yùn)行微服務(wù)α?xí)r，必有鏡像文件l存在。

s.t. 2

L(i,t,l)≥y(i,t,m,α)×Lα,l,?i,t,m,α

約束3：保證每一個(gè)物理機(jī)上全部微服務(wù)模塊所需資源量不會超過此物理機(jī)的最大資源量。本文中物理機(jī)資源設(shè)置為內(nèi)存、CPU。

s.t. 3

約束4：保證每個(gè)微服務(wù)模塊的唯一性，即一個(gè)時(shí)刻內(nèi)某一個(gè)微服務(wù)模塊只能存在于一個(gè)物理機(jī)上。為簡易化模型，本文中我們假定每個(gè)微服務(wù)模塊為最小運(yùn)行單位。

s.t. 4

約束5～約束7：全部變量均為0-1變量，即賦值為1時(shí)，依次表示為微服務(wù)存在，處于工作狀態(tài)、鏡像文件存在，反之不存在

s.t. 5

y(i,t,m,α)∈{0,1}

s.t. 6

x(i,t)∈{0,1}

s.t. 7

L(i,t,l)∈{0,1}

約束8：用戶應(yīng)用程序的全部服務(wù)模塊運(yùn)行時(shí)延不能高于閾值，需要嚴(yán)格遵守QoS(quality of service)內(nèi)時(shí)延要求。

s.t. 8

本文根據(jù)以上優(yōu)化公式和約束條件，將其作為優(yōu)化模型，并設(shè)計(jì)算法實(shí)現(xiàn)MIN-COST策略的目標(biāo)。

3 基于深度強(qiáng)化學(xué)習(xí)的求解方法

服務(wù)器遷移問題是典型的組合優(yōu)化問題，而此類問題往往都是NP-hard問題，使用傳統(tǒng)求解器如CPLEX只能求解一定規(guī)模的問題，而隨著問題規(guī)模指數(shù)增長，求解器的功能則變得乏力。啟發(fā)式算法用于求解NP-hard問題最為廣泛，但由于缺乏理論支撐，算法設(shè)計(jì)需要大量的專業(yè)知識和試錯(cuò)。本文使用了一種基于深度強(qiáng)化學(xué)習(xí)(DQN)的方法來求解組合優(yōu)化問題，一方面強(qiáng)化學(xué)習(xí)算法不受限于問題規(guī)模，另一方面避免了啟發(fā)式算法繁瑣的算法設(shè)計(jì)，讓計(jì)算機(jī)自主學(xué)習(xí)問題的信息并解答。

3.1 學(xué)習(xí)模型設(shè)置

此節(jié)我們定義了學(xué)習(xí)模型的必要參數(shù)。在2.2小節(jié)中已經(jīng)定義了有n個(gè)邊緣計(jì)算集群，每個(gè)計(jì)算集群中的物理機(jī)記為Ni，以及一段時(shí)間t={0,1,…,T},T∈N。m(t) 定義為用戶位置。小節(jié)2.3中，y(i,t,m,α) 定義為用戶應(yīng)用部署在物理機(jī)Ni上。

強(qiáng)化學(xué)習(xí)模型中的元素定義如下：

Agent：集群中的控制器作為強(qiáng)化學(xué)習(xí)中的agent，由于控制器具備和全部物理機(jī)通信的功能，并且掌握各物理機(jī)的狀態(tài)和部署情況，本文中由控制服務(wù)器做出任務(wù)的部署和遷移決策。

States：在不同時(shí)刻t∈T的狀態(tài)表示為St，由于路徑可以根據(jù)歷史數(shù)據(jù)獲得，本文將用戶當(dāng)前坐標(biāo)作為輸入狀態(tài)，用戶位置的移動會導(dǎo)致與各服務(wù)器的相關(guān)代價(jià)改變。states定義為St=m(t)。

Actions：在本文中，控制器的決策域的大小與全部邊緣服務(wù)器數(shù)量成正比，當(dāng)前應(yīng)用所在服務(wù)器需要與全部服務(wù)器一一對應(yīng)，具體表示為：At∈Act={Ai,j},i,j∈PM, 其中i、j分別表示為當(dāng)前服務(wù)器和下一個(gè)遷移服務(wù)器，如果不遷移則有j=i。值得注意的是，本文依據(jù)POMDP的思想縮小了決策域，對于用戶距離過大的服務(wù)器從決策中排除，簡化了實(shí)驗(yàn)過程。

Reward：控制器根據(jù)動作和狀態(tài)獲得當(dāng)前時(shí)刻t的獎(jiǎng)勵(lì)。文中我們設(shè)置一個(gè)初始獎(jiǎng)勵(lì)R，需要注意的是，由于每臺物理機(jī)的當(dāng)前狀況并不相同，需要根據(jù)式(3)先行扣除部分獎(jiǎng)勵(lì)。上文所提出的通信式(4)、遷移代價(jià)式(5)在獎(jiǎng)勵(lì)中均為懲罰，也就是所用代價(jià)越大，獲得的獎(jiǎng)勵(lì)越小，所以最終獎(jiǎng)勵(lì)設(shè)置為

Rt(St,At)=R-Cop-Ccom-Cmig

(7)

上式根據(jù)action的情況寫成如下公式

(8)

在表2中列出了強(qiáng)化學(xué)習(xí)中的全部參數(shù)。

表2 相關(guān)參數(shù)

3.2 基于DQN的應(yīng)用部署算法

控制器在t的全部時(shí)刻選擇合適的策略來最大化總的獎(jiǎng)勵(lì)值?？刂破麝P(guān)于時(shí)間t序列的決策定義如下

π=Фt(St) ?t={0,1,…,T},T∈N

(9)

(10)

折扣率γ一定程度上保留了歷史經(jīng)驗(yàn)中的狀態(tài)效用的最大值，當(dāng)γ越大控制器越會重視以往經(jīng)驗(yàn)(far-sighted)，越小則就只重視眼前的獎(jiǎng)勵(lì)(myopic)，有γ∈(0,1)。 DQN算法使用bellman等式遞歸并更新自身參數(shù)

(11)

Q函數(shù)的最優(yōu)值Qt*(St,At) 即為選擇的最優(yōu)策略，在一般強(qiáng)化學(xué)習(xí)中Q函數(shù)值由列表保存，一般稱為Q-table，最優(yōu)值Q*代表在狀態(tài)St下可以獲得最多回報(bào)的action。Q函數(shù)表示為

(12)

在DQN中，獲得的近似Q函數(shù)用Qt(St,At;θ) 表示，θ是權(quán)重參數(shù)。由于DQN中Q值直接由神經(jīng)網(wǎng)絡(luò)生成，替代了傳統(tǒng)Q-table的保存方法，神經(jīng)網(wǎng)絡(luò)中每個(gè)神經(jīng)元的weight和bias參數(shù)都影響著Q值的變化。同傳統(tǒng)強(qiáng)化學(xué)習(xí)一樣，最優(yōu)策略表示為

(13)

在DQN算法中目標(biāo)值(Q值)為

(14)

為使網(wǎng)絡(luò)能最終收斂，需要計(jì)算兩個(gè)網(wǎng)絡(luò)的差距(MSE)來找到參數(shù)更新的方向

Li=Qtarget-Qeval

(15)

更為詳細(xì)的損失函數(shù)表示如下

Li(θi)=ESt,At,Rt,St+1[(Qtarget-Qt(St,At;θi))2]

(16)

微分上式獲得損失函數(shù)的梯度

(17)

(18)

α為學(xué)習(xí)效率，且有α∈(0,1)。

此外DQN中使用了experience replay的方法，即保存之前的學(xué)習(xí)經(jīng)歷在更新算法時(shí)隨機(jī)抽取再次學(xué)習(xí)，這種方法打亂了學(xué)習(xí)經(jīng)驗(yàn)的相關(guān)性，克服了經(jīng)驗(yàn)數(shù)據(jù)非平穩(wěn)分布的問題。

不同于Q-learning算法，DQN增加的fixed Q-targets方法打破數(shù)據(jù)關(guān)聯(lián)性，穩(wěn)定了學(xué)習(xí)過程。DQN使用兩個(gè)結(jié)構(gòu)相同的神經(jīng)網(wǎng)絡(luò)，分別為target和evaluation。evaluation網(wǎng)絡(luò)隨訓(xùn)練步數(shù)實(shí)時(shí)更新而target網(wǎng)絡(luò)則是隔步用evaluation網(wǎng)絡(luò)直接替換。式(15)、式(16)正是計(jì)算兩個(gè)網(wǎng)絡(luò)之差，稱之為TD-error。

算法1表示了本文所提出的基于DQN的應(yīng)用程序優(yōu)化部署算法。算法流程如下：

算法1： 基于DQN的最優(yōu)服務(wù)器選擇

輸入： 折扣率γ， 學(xué)習(xí)率α， 探索與利用的權(quán)衡參數(shù)ε， Replay的存儲容量D， 更新步數(shù)c。

輸出： 最優(yōu)服務(wù)器位置

(1)使用存儲容量D初始化Replay memory的容量。

(2)使用參數(shù)θ初始化評估網(wǎng)絡(luò)。

(3)使用參數(shù)θ-=θ初始化目標(biāo)網(wǎng)絡(luò)。

(4) 初始化全部服務(wù)器信息(資源量、 坐標(biāo)、 庫文件數(shù)量等)。

(5)t←1，m(1)←random value，i←random PM

(6)設(shè)置S1=m(1)

(7) 將全部服務(wù)器以到用戶距離為優(yōu)先級排序， 選擇前10個(gè)服務(wù)器作為備選服務(wù)器。

(8)whilet≤T：

(9) 生成隨機(jī)數(shù)值η∈[0,1]

(10)ifη<ε：

(11) 隨機(jī)選擇一個(gè)動作At;

(12)else：

(14) 判斷x(i,(t-1),m,α),y(j,t,m,α) 是否同值:

(15) 分別根據(jù)式(8)計(jì)算Rt(St,At)

(16)i←j,St+←m(t+1)

(17) 將此次經(jīng)驗(yàn)(St,At,Rt,St+1)存儲在Replay memory中

(18) 運(yùn)行算法2更新估值網(wǎng)絡(luò)

(19)ift%c=0：

(20) 設(shè)置θ-=θ

(21)t←t+1

(22)endwhile

算法2：更新估值網(wǎng)絡(luò)

(1) 采用minibatch的方式從Replay memory中隨機(jī)讀取先前經(jīng)驗(yàn)(St,At,Rt,St+1)，k∈T

(2)ift+1 是最后一個(gè)循環(huán)：

(4)else

(6)endif

(7) 使用MSE式 (16)、 式 (17)計(jì)算下降梯度， 根據(jù)式 (18) 更新估值網(wǎng)絡(luò)權(quán)重θ

至此一個(gè)完整的DQN構(gòu)建完成，通過輸入數(shù)據(jù)集可以訓(xùn)練出能自動選擇最優(yōu)部署位置的決策模型，具體實(shí)驗(yàn)在下節(jié)給出。

4 實(shí)驗(yàn)仿真

為測試所提的MIN-COST策略的有效性，本文與SABFD(space aware best fit decreasing)[12]、ITEM(ITe-rative expansion move)[13]和DF(distance first)3種策略進(jìn)行對比實(shí)驗(yàn)，SABFD策略主要關(guān)注了服務(wù)節(jié)能問題，強(qiáng)調(diào)盡可能將服務(wù)放置在資源充足的服務(wù)器上。ITEM將多個(gè)優(yōu)化部分組合成一個(gè)模型并求解最小代價(jià)。DF強(qiáng)調(diào)將應(yīng)用程序服務(wù)放置在最靠近用戶的邊緣服務(wù)器上，是一種被廣泛使用的部署策略。實(shí)驗(yàn)先按照已有研究[13]的實(shí)驗(yàn)數(shù)據(jù)范圍生成一個(gè)小型的仿真場景，考察小型場景與實(shí)際場景的相似度。并針對不同實(shí)驗(yàn)場景：不斷增加資源量、不斷增加用戶人數(shù)、不斷增加服務(wù)時(shí)間分別測試上述幾種部署策略，將MIN-COST策略中鏡像重用特征與其它策略進(jìn)行對比，最后給出了使用DQN在不同超參數(shù)的收斂速度。

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

實(shí)驗(yàn)參照文獻(xiàn)[14]將場景設(shè)置在4*4的格子中，在此區(qū)域中有若干邊緣服務(wù)器，用戶在區(qū)域中隨機(jī)行走(保留其路徑)。實(shí)驗(yàn)中假定共有10種不同的基礎(chǔ)鏡像文件，不同的微服務(wù)模塊需要種類不同、數(shù)量不一的鏡像文件，此需求數(shù)值均為隨機(jī)生成。物理機(jī)待機(jī)/工作能耗代價(jià)、通訊相關(guān)固定參數(shù)、時(shí)延閾值等均沿用文獻(xiàn)[15]中實(shí)驗(yàn)參數(shù)設(shè)置。其它參數(shù)和用戶、物理機(jī)狀態(tài)參數(shù)均使用隨機(jī)數(shù)據(jù)，數(shù)據(jù)控制在文獻(xiàn)[15]實(shí)驗(yàn)數(shù)據(jù)大致相同的范圍內(nèi)。

剩余參數(shù)設(shè)置[16,17]如下：reward中最大回報(bào)R=90，學(xué)習(xí)率α=0.01，折扣率γ=0.9，探索與利用的權(quán)衡參數(shù)ε=0.1，Replaymemory=500，批大小batch_size=32，總時(shí)間t=300。實(shí)驗(yàn)使用了兩層、每層30個(gè)神經(jīng)元的神經(jīng)網(wǎng)絡(luò)[18]，每層的weight使用范圍為[0,0.3]的隨機(jī)數(shù)值，bias初始值為0.1。

為證實(shí)所提的MIN-COST策略有效性，將本策略與SABFD、ITEM和DF這3種策略在相同實(shí)驗(yàn)環(huán)境和參數(shù)下進(jìn)行對比實(shí)驗(yàn)。實(shí)驗(yàn)將3種參數(shù)變化對策略的影響進(jìn)行測試，實(shí)驗(yàn)安排如下：

(1)為測試不斷增加計(jì)算資源量情況下MIN-COST策略自適應(yīng)調(diào)整狀態(tài)的效果，實(shí)驗(yàn)設(shè)置如下：控制時(shí)間段、用戶數(shù)量改變物理機(jī)數(shù)量，物理機(jī)數(shù)量控制在[80,240]內(nèi)；

(2)實(shí)際中可能有不斷增多的相同應(yīng)用程序請求的情況，比如使用相同應(yīng)用程序的用戶增多，為測試MIN-COST策略在此情況下的自適應(yīng)調(diào)整效果，實(shí)驗(yàn)設(shè)置如下：控制時(shí)間段、物理機(jī)數(shù)量改變用戶數(shù)量，用戶數(shù)量控制在[1，50]內(nèi)；

(3)為測試用戶請求更長服務(wù)時(shí)間MIN-COST策略的調(diào)整情況，實(shí)驗(yàn)中將用戶使用服務(wù)時(shí)間不斷延長，記錄該策略部署的變化。實(shí)驗(yàn)設(shè)置如下：控制物理機(jī)數(shù)量、用戶數(shù)量改變總時(shí)間，時(shí)間長度控制在[180，480]內(nèi)。

實(shí)驗(yàn)結(jié)果均使用相同數(shù)據(jù)在不同的策略下進(jìn)行計(jì)算獲得。隨后對比了不同策略鏡像文件的下載次數(shù)，以及相關(guān)超參數(shù)對算法收斂的影響。

4.2 結(jié)果分析與討論

4.2.1 計(jì)算資源量對策略的影響

改變物理機(jī)數(shù)量的實(shí)驗(yàn)結(jié)果如圖2所示，所提出的MIN-COST策略相比其它3種有較低的代價(jià)。由于不斷增加新的物理機(jī)，出現(xiàn)資源量充足或初始擁有多種鏡像文件的物理機(jī)概率會提高，所以有可能隨著物理機(jī)的增多而使得代價(jià)降低，實(shí)驗(yàn)結(jié)果也證實(shí)了此猜測。而DF策略只考慮距離用戶最近的物理機(jī)，若新增物理機(jī)距離都不及已有物理機(jī)的距離，該策略將忽視新增物理機(jī)，則無論新物理機(jī)的資源量和其它條件更優(yōu)也都不會對代價(jià)產(chǎn)生有利的影響。反而若新增物理機(jī)距離近但資源不足或鏡像文件不足，將會產(chǎn)生遷移和下載代價(jià)，總的代價(jià)反而會因此上升。SABFD策略同理，該策略只考慮尋找資源最充足的物理機(jī)，忽視關(guān)鍵的用戶與物理機(jī)間的通信代價(jià)，也很有可能會造成總代價(jià)的大幅上升。ITEM策略相比于上兩種策略有較好的提升，但缺少鏡像重用的考慮，代價(jià)仍高于MIN-COST策略。

圖2 計(jì)算資源量對策略的影響

4.2.2 應(yīng)用程序請求數(shù)量對策略的影響

隨著用戶的增多，物理機(jī)的資源量可能無法滿足新用戶的請求，用戶服務(wù)便會被分配至次優(yōu)的服務(wù)器上運(yùn)行，所以在圖3中，實(shí)驗(yàn)的4種策略的總代價(jià)都隨著用戶的增加而增加。MIN-COST策略中由于鏡像的重用，總代價(jià)仍低于其它策略。實(shí)驗(yàn)假設(shè)共有10種鏡像文件，不同的微服務(wù)模塊需要不同的鏡像文件。由于用戶放置完微服務(wù)模塊后的鏡像文件是保留在物理機(jī)上的，當(dāng)下一個(gè)或多個(gè)用戶將微服務(wù)模塊放置此物理機(jī)上時(shí)，有很大的概率會重用之前的鏡像文件，隨著用戶的增多，某一個(gè)資源量很足的物理機(jī)上甚至可能存在全部10種鏡像文件，新來的用戶微服務(wù)模塊可以直接運(yùn)行，避免了鏡像文件重復(fù)下載的過程。其它的策略并沒有考慮到此問題，所以相比MIN-COST策略有更高的代價(jià)。由于50個(gè)用戶的服務(wù)總代價(jià)遠(yuǎn)大于單個(gè)用戶的總代價(jià)，導(dǎo)致圖中4種策略看似在相同的起點(diǎn)，實(shí)際上在單用戶時(shí)4種策略有明顯的代價(jià)差異。

圖3 用戶數(shù)量對策略的影響

4.2.3 服務(wù)時(shí)間對策略的影響

隨著用戶使用微服務(wù)模塊時(shí)間增加，全部的策略代價(jià)都有所增加，如圖4所示，MIN-COST策略代價(jià)總代價(jià)仍小于其余3種策略。值得注意的是，DF策略在360至420的區(qū)間有下降趨勢，由于用戶的移動軌跡是隨機(jī)生成的，當(dāng)用戶的位置很靠近某個(gè)物理機(jī)，且此物理機(jī)恰好資源足夠，有較多的鏡像文件時(shí)，DF策略的代價(jià)可能會有所減?。划?dāng)用戶的位置很靠近一個(gè)資源量最充足的物理機(jī)時(shí)，SABFD策略由于降低了用戶與此物理機(jī)的通信距離，也會產(chǎn)生較小的代價(jià)。然而這兩種策略的性能具有很強(qiáng)的偶然性，不適合直接作為應(yīng)用程序部署的優(yōu)化策略。

圖4 服務(wù)時(shí)間對策略的影響

4.2.4 鏡像文件下載次數(shù)對比

為測試所提的MIN-COST策略在3組實(shí)驗(yàn)情況下的表現(xiàn)，我們記錄了每組實(shí)驗(yàn)中的鏡像下載數(shù)量，介于篇幅限制只展示其中一組實(shí)驗(yàn)結(jié)果,圖中L1、L2…L10為假設(shè)的庫文件。在實(shí)驗(yàn)中(pm=80，user=10，time=300)統(tǒng)計(jì)了全部10個(gè)鏡像文件生成的次數(shù)，實(shí)驗(yàn)結(jié)果如圖5所示?？梢奙IN-COST策略對鏡像文件的重用起到了很好效果，相對于SABFD、ITEM、DF策略的下載次數(shù)分別最多可以降低76.7%、73.7%、80.4%，其它策略在這一方面表現(xiàn)的并不突出，特別是在DF策略下，大部分時(shí)間微服務(wù)模塊所需要的鏡像都要重新下載。

圖5 鏡像文件下載次數(shù)

4.2.5 超參數(shù)與收斂速度

圖6實(shí)驗(yàn)測試了探索與利用的權(quán)衡參數(shù)e的改變對算法收斂的影響，由圖可以看出，當(dāng)探索與利用處于平衡狀態(tài)e=0.5時(shí)處于較高的代價(jià)，且很長時(shí)間都難以收斂。而在利用大于探索的設(shè)置里則能較好地實(shí)現(xiàn)收斂。

圖6 不同權(quán)衡參數(shù)e的影響

圖7測試了不同學(xué)習(xí)率的影響，學(xué)習(xí)率在0.1時(shí)收斂速度略低于剩下兩種，由于本實(shí)驗(yàn)規(guī)模并不大，所以此項(xiàng)參數(shù)的改變效果并不顯著。

圖7 不同學(xué)習(xí)率α的影響

5 結(jié)束語

本文對移動邊緣計(jì)算場景下的智能交通應(yīng)用優(yōu)化部署進(jìn)行了詳細(xì)的說明，采用了輕量的應(yīng)用架構(gòu)并制定了最優(yōu)策略，且通過有效的方法將其實(shí)現(xiàn)。使用最小化代價(jià)的模型表述了該優(yōu)化問題，并詳盡地分析了該模型，使用了深度強(qiáng)化學(xué)習(xí)的方法求解了該問題，與SABFD、ITEM、DF這3種部署策略在不同參數(shù)環(huán)境下對比實(shí)驗(yàn)后，驗(yàn)證了該模型的有效性。在未來的研究中，將以此優(yōu)化策略為基礎(chǔ)，將對不確定的用戶路徑進(jìn)行研究而不僅限于路徑固定的公交場景，同時(shí)還將考慮在不同時(shí)刻下交通流量對部署情況的影響。