邊緣計算場景下基于強化學(xué)習(xí)的應(yīng)用最優(yōu)部署

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

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

0 引 言

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

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

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

1 相關(guān)介紹

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

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

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

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

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

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

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

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

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

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

1.5 代價的定義

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

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

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

(1)立即可得的回報；

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

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

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

(1)

Bellman方程是強化學(xué)習(xí)的理論基礎(chǔ)，狀態(tài)值函數(shù)和行為值函數(shù)的遞推關(guān)系也正是獲得未來信息的一種方式。然而在實際應(yīng)用中，狀態(tài)以及動作的維度往往很大，僅僅用傳統(tǒng)的數(shù)據(jù)結(jié)構(gòu)難以存儲如此巨大的信息，而深度神經(jīng)網(wǎng)絡(luò)的出現(xiàn)也讓強化學(xué)習(xí)的方法再次受到關(guān)注。在強化學(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)異，使得強化學(xué)習(xí)可以直接從高維原始數(shù)據(jù)學(xué)習(xí)控制；

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

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

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

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

2.1 建模目標

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

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

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

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

2.3 相關(guān)變量

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

2.4 模型分析

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

COST=Cop+Ccom+Cmig

(2)

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

部署代價(Cop)：

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

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

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

(3)物理機的基線能耗，即物理機正常運行時所必要的能耗，此代價用Cb表示；

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

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

(3)

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

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

(4)

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

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

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

(5)

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

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

min{Cop+Ccom+Cmig}

(6)

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

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

s.t. 1

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

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

s.t. 2

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

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

s.t. 3

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

s.t. 4

約束5～約束7：全部變量均為0-1變量，即賦值為1時，依次表示為微服務(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ù)模塊運行時延不能高于閾值，需要嚴格遵守QoS(quality of service)內(nèi)時延要求。

s.t. 8

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

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

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

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

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

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

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

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

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

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

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

(7)

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

(8)

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

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

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

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

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

(9)

(10)

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

(11)

Q函數(shù)的最優(yōu)值Qt*(St,At) 即為選擇的最優(yōu)策略，在一般強化學(xué)習(xí)中Q函數(shù)值由列表保存，一般稱為Q-table，最優(yōu)值Q*代表在狀態(tài)St下可以獲得最多回報的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ò)中每個神經(jīng)元的weight和bias參數(shù)都影響著Q值的變化。同傳統(tǒng)強化學(xué)習(xí)一樣，最優(yōu)策略表示為

(13)

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

(14)

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

Li=Qtarget-Qeval

(15)

更為詳細的損失函數(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)歷在更新算法時隨機抽取再次學(xué)習(xí)，這種方法打亂了學(xué)習(xí)經(jīng)驗的相關(guān)性，克服了經(jīng)驗數(shù)據(jù)非平穩(wěn)分布的問題。

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

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

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

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

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

(8)whilet≤T：

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

(10)ifη<ε：

(11) 隨機選擇一個動作At;

(12)else：

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

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

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

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

(18) 運行算法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īng)驗(St,At,Rt,St+1)，k∈T

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

(4)else

(6)endif

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

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

4 實驗仿真

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

4.1 實驗設(shè)置

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

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

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

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

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

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

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

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

4.2.1 計算資源量對策略的影響

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

圖2 計算資源量對策略的影響

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)束語

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