魯 偉，宋榮方

(南京郵電大學(xué) 通信與信息工程學(xué)院，江蘇 南京 210003)

0 引 言

隨著物聯(lián)網(wǎng)、移動(dòng)互聯(lián)網(wǎng)、大數(shù)據(jù)技術(shù)的快速發(fā)展，人類進(jìn)入了一個(gè)萬物互聯(lián)的智能時(shí)代，移動(dòng)智能終端隨時(shí)隨地在線，服務(wù)于移動(dòng)終端上的交互式游戲、智慧城市等計(jì)算密集型的業(yè)務(wù)也正在興起[1]，這些業(yè)務(wù)需要大量的計(jì)算資源才能滿足自身對(duì)低時(shí)延的要求[2]。由于移動(dòng)智能設(shè)備處理能力、存儲(chǔ)容量有限，因此大量的計(jì)算需要在云端進(jìn)行[3]，而云端存在較大的傳輸時(shí)延，當(dāng)云端資源不足時(shí)，甚至存在較大的排隊(duì)等待時(shí)延，這些時(shí)延嚴(yán)重影響了眾多業(yè)務(wù)的服務(wù)質(zhì)量。為了使用戶能獲得良好的體驗(yàn)，減輕云端服務(wù)器的負(fù)擔(dān)，移動(dòng)邊緣計(jì)算(mobile edge computing，MEC)概念孕育而生[4-5]。與傳統(tǒng)的集中式網(wǎng)絡(luò)架構(gòu)不同，MEC將邊緣服務(wù)器部署在靠近用戶的一端，縮短了用戶與服務(wù)器之間的距離，從而大大降低了用戶設(shè)備的傳輸時(shí)延。在移動(dòng)邊緣計(jì)算系統(tǒng)中，任務(wù)卸載調(diào)度策略的好壞也會(huì)直接影響到系統(tǒng)時(shí)延和用戶體驗(yàn)。終端將業(yè)務(wù)卸載至邊緣計(jì)算服務(wù)器時(shí)，服務(wù)器通過優(yōu)化業(yè)務(wù)調(diào)度順序可以進(jìn)一步降低時(shí)延和系統(tǒng)能耗。目前已有許多文獻(xiàn)對(duì)MEC任務(wù)卸載調(diào)度進(jìn)行了研究，MEC卸載常見的衡量指標(biāo)有時(shí)延、能耗以及時(shí)延和能耗綜合權(quán)衡問題[6]。文獻(xiàn)[7]研究了單用戶單核服務(wù)器任務(wù)卸載情景，提出了一種基于李雅普諾夫優(yōu)化的動(dòng)態(tài)計(jì)算遷移算法，旨在優(yōu)化應(yīng)用的執(zhí)行時(shí)延。文獻(xiàn)[8]研究了單用戶單核服務(wù)器任務(wù)卸載情景，提出了二進(jìn)制粒子群優(yōu)化算法，旨在優(yōu)化系統(tǒng)的能耗。文獻(xiàn)[9]利用流水車間調(diào)度模型對(duì)任務(wù)卸載調(diào)度進(jìn)行建模，以交替最小化優(yōu)化方法研究系統(tǒng)時(shí)延與能耗關(guān)系。文獻(xiàn)[10]研究單用戶多核任務(wù)卸載情景，利用遺傳算法對(duì)單用戶的能耗與時(shí)延關(guān)系進(jìn)行了優(yōu)化分析。受以上文獻(xiàn)的啟發(fā)，且目前多核多用戶任務(wù)卸載研究較少，該文研究多核多用戶任務(wù)卸載情景，采用混合流水車間模型進(jìn)行建模，以最小化系統(tǒng)時(shí)延和能耗加權(quán)和為優(yōu)化目標(biāo)，采用模擬退火算法進(jìn)行求解，通過仿真獲得了多用戶最優(yōu)的任務(wù)卸載策略，最后對(duì)系統(tǒng)時(shí)延和能耗關(guān)系進(jìn)行了分析。

1 系統(tǒng)模型與問題建模

該文研究多用戶多核任務(wù)卸載情景。該邊緣任務(wù)卸載系統(tǒng)包含了多個(gè)用戶和一個(gè)多核的MEC服務(wù)器。每個(gè)用戶之間卸載相互獨(dú)立互不影響，每個(gè)用戶的多個(gè)可卸載任務(wù)也相互獨(dú)立互不影響。用戶可以通過無線信道將任務(wù)上傳至邊緣服務(wù)器進(jìn)行任務(wù)卸載。由于每個(gè)任務(wù)上傳所需的時(shí)間和在核服務(wù)器上卸載的時(shí)間的不同，不合理的任務(wù)卸載順序必將導(dǎo)致系統(tǒng)的總體時(shí)延較大，因此確定合理的任務(wù)卸載順序至關(guān)重要。

1.1 任務(wù)調(diào)度與傳輸速率的定義

移動(dòng)終端將各自的N項(xiàng)獨(dú)立的計(jì)算任務(wù)卸載到MEC[11]。記各自的任務(wù)集合為R={T1,T2,…,TN}，每個(gè)任務(wù)T用一對(duì)參數(shù)〈Di,Ci〉來表示，其中Di(bits)表示任務(wù)的數(shù)據(jù)量，Ci(cycles/bit)表示每比特的數(shù)據(jù)所需的計(jì)算資源。每個(gè)用戶N個(gè)任務(wù)的卸載調(diào)度順序定義為σ={σ1,σ2,…,σN}，其中TNσi表示該任務(wù)N于第i次卸載到MEC服務(wù)器上。該文研究移動(dòng)端配置單天線情景，一次只能發(fā)一個(gè)任務(wù)，任務(wù)TNσi的傳輸速率定義為:

(1)

其中，Pi是任務(wù)TNσi的傳輸功率，g0是路徑損耗常數(shù)，θ是路徑損耗指數(shù)，取值范圍一般為2～4，L0是參考距離，L是終端與MEC服務(wù)器之間的距離，w是系統(tǒng)帶寬，N0是MEC服務(wù)器接收端的噪聲功率譜密度。

1.2 系統(tǒng)時(shí)延和能耗模型

混合流水車間調(diào)度(hybrid flow-shop scheduling problem，HFSP)是一種車間作業(yè)排序問題[12]。如圖1所示，設(shè)有n個(gè)獨(dú)立的工件按照相同加工方向在m道工序上加工，m道工序中至少有一道工序包含多臺(tái)并行處理器[13]。

圖1 混合流水車間調(diào)度模型

模型一般滿足以下條件：(1)同一階段中所有機(jī)器都相同；(2)每個(gè)工件可以在某階段的任意一臺(tái)機(jī)器上進(jìn)行加工；(3)任意時(shí)刻每個(gè)工件至多在一臺(tái)機(jī)器上加工；(4)每臺(tái)機(jī)器某時(shí)刻只能加工一個(gè)工件；(5)工件的加工過程不允許中斷；(6)每臺(tái)機(jī)器都有一個(gè)無限的存儲(chǔ)空間。

在多用戶多核服務(wù)器MEC系統(tǒng)中，可將卸載的任務(wù)看成是待加工的工件，每個(gè)計(jì)算任務(wù)都需要經(jīng)過本地傳輸和服務(wù)器執(zhí)行兩道工序。在第一道工序中，移動(dòng)設(shè)備負(fù)責(zé)任務(wù)的上傳，在第二道工序中，MEC服務(wù)器具有M個(gè)計(jì)算能力相同的處理器，因此可以利用混合流水車間模型對(duì)多用戶多核服務(wù)器MEC系統(tǒng)的任務(wù)卸載調(diào)度進(jìn)行建模。當(dāng)任務(wù)TNσi卸載到MEC服務(wù)器上執(zhí)行時(shí)，系統(tǒng)時(shí)延由三部分組成，即任務(wù)上傳到服務(wù)器的時(shí)間t(1,σj)、任務(wù)在服務(wù)器執(zhí)行的時(shí)間t(2,σj)和任務(wù)結(jié)果反饋到移動(dòng)設(shè)備的時(shí)間，通常由于下行速率遠(yuǎn)遠(yuǎn)高于上行速率，因此可忽略結(jié)果的反饋時(shí)間。

(2)

(3)

σj∈(1,2,…,N)

在多用戶多核MEC系統(tǒng)中，每個(gè)用戶完工時(shí)間定義為該用戶最后一個(gè)任務(wù)在某個(gè)核上的完工時(shí)間[14],系統(tǒng)時(shí)延定義為每個(gè)用戶最后一個(gè)任務(wù)在某個(gè)核上的完工時(shí)間的累加和，即：

(4)

系統(tǒng)能耗定義為每個(gè)用戶每個(gè)任務(wù)上傳所消耗能耗的累加和，即：

(5)

2 問題建模

基于以上分析，該文以最小化時(shí)延和能耗的加權(quán)和為目標(biāo)，即：

(6)

s.t. 0≤pi≤pmax,i=1,2,…,N

σ={σ1,σ2,…,σN}，其中σi∈{1,2,…,N},i≠j,σi≠σj,?i,j,i,j=1,2,…,N

其中，η為權(quán)重因子，用于調(diào)節(jié)系統(tǒng)時(shí)延和能耗之間的數(shù)量級(jí)，當(dāng)其較大時(shí)，表示對(duì)系統(tǒng)能耗的優(yōu)化更加看重。該求解問題是一個(gè)優(yōu)化問題，可以使用窮舉算法遍歷所有情況，但復(fù)雜度太高?？紤]到模擬退火算法是一種借鑒于固體的退火原理的優(yōu)化算法，計(jì)算過程簡(jiǎn)單，通用，魯棒性強(qiáng)，適用于并行處理，可用于求解復(fù)雜的優(yōu)化問題，所以用模擬退火算法對(duì)問題p進(jìn)行求解。

3 模擬退火算法

模擬退火算法(simulated annealing algorithm，SAA)是一種基于蒙特卡洛迭代的隨機(jī)尋優(yōu)算法，其出發(fā)點(diǎn)是模仿物理中固定物質(zhì)的退火過程與一般組合優(yōu)化問題之間的相似性[15]。模擬退火算法在某一初溫下，隨著溫度參數(shù)的不斷下降，以一定的概率突跳，在解空間中隨機(jī)尋找目標(biāo)函數(shù)的全局最優(yōu)解。為方便表示，將適應(yīng)度函數(shù)fitness表示為目標(biāo)函數(shù)值E，目標(biāo)函數(shù)值E越低，表示可行解越接近最優(yōu)解。

(7)

算法流程：

(1)設(shè)定當(dāng)前解：T=T0，即開始退火的初始溫度，隨機(jī)生成一個(gè)初始解Xbest=X0，并計(jì)算相應(yīng)的目標(biāo)函數(shù)值E(x0)，令T等于冷卻進(jìn)度表中的下一個(gè)溫度值Ti。

(2)產(chǎn)生新解與當(dāng)前解的差值：對(duì)當(dāng)前解Xi進(jìn)行擾動(dòng)，產(chǎn)生一個(gè)新解Xnew，并計(jì)算相應(yīng)的目標(biāo)數(shù)值E(Xnew)進(jìn)而得到ΔE=E(Xnew)-E(Xi)。

(4)更新溫度，Tk+1=update(Tk)，在溫度Tk+1下，再經(jīng)過k次擾動(dòng)和接受，即執(zhí)行步驟2和步驟3。

(5)找到可行解：判斷T是否達(dá)到了終止溫度，是，終止算法；否，則轉(zhuǎn)到步驟2繼續(xù)執(zhí)行。

4 仿真結(jié)果與分析

下面對(duì)多用戶多核服務(wù)器的MEC系統(tǒng)分別用基于混合流水車間模型的模擬退火算法(HFSP-SAA)與隨機(jī)任務(wù)卸載(random task offload strategy，RTOS)的任務(wù)數(shù)與時(shí)延的關(guān)系任務(wù)卸載調(diào)度進(jìn)行仿真并分析。仿真中計(jì)算任務(wù)的數(shù)據(jù)量Di和所需的計(jì)算資源Ci都服從均勻分布，即Di～U(2 davg，20 davg)，Ci～U(5 cavg，27.975 cavg)，其中davg=1 kbit，cavg=797.5 cycles/bit。表1列出了仿真所需要的參數(shù)及取值。

表1 仿真參數(shù)與取值

圖2展示了η=0時(shí)基于混合流水車間模型模擬退火算法在不同傳輸功率下2核2用戶時(shí)延與卸載任務(wù)數(shù)的關(guān)系。

圖2 時(shí)延與卸載任務(wù)之間關(guān)系(M=2)

從圖中可以看出，隨著卸載任務(wù)數(shù)量的增大，時(shí)延呈現(xiàn)上升趨勢(shì)。傳輸功率從0.5 mW增大至16 mW，時(shí)延顯著降低，但傳輸功率從16 mW增大至32 mW，時(shí)延降低并不明顯。

圖3～圖5分別展示了在不同的傳輸功率下2核2用戶的卸載任務(wù)調(diào)度的甘特圖。用戶的任務(wù)數(shù)字表示正在上傳的任務(wù)序號(hào)，而核服務(wù)器上的數(shù)字表示該任務(wù)的歸屬，例如核2上數(shù)字的2|5，表示核2正在處理用戶2的第5個(gè)任務(wù)。

圖3 P=0.5 mW任務(wù)卸載甘特圖

圖4 P=16 mW任務(wù)卸載甘特圖

圖5 P=32 mW任務(wù)卸載甘特圖

從甘特圖中可以看出，當(dāng)傳輸功率P=0.5 mW時(shí)，核服務(wù)器一開始等待時(shí)間較長(zhǎng)，任務(wù)上傳時(shí)間過長(zhǎng)，從而導(dǎo)致MEC服務(wù)器資源無法充分得到利用，且在處理任務(wù)過程中，因?yàn)閭鬏敼β实投鴮?dǎo)致核服務(wù)器有空閑等待的時(shí)刻，從而導(dǎo)致時(shí)延較高，且當(dāng)卸載任務(wù)數(shù)量顯著增大時(shí)，這種空閑等待情況更加明顯，因此時(shí)延會(huì)顯著增大。而當(dāng)傳輸功率P=16 mW時(shí)，任務(wù)上傳時(shí)間減少，核服務(wù)器等待時(shí)間減少，且核服務(wù)器無空閑等待時(shí)刻，因此時(shí)延降低。當(dāng)P=32 mW時(shí)，盡管任務(wù)上傳時(shí)間減短，但核服務(wù)器因?yàn)橘Y源有限，上傳的任務(wù)進(jìn)入了緩存等待區(qū)域，因此傳輸功率的再次增大并沒有換取時(shí)延的顯著降低。

圖6展現(xiàn)了基于混合流水車間模型的模擬退火算法(HFSP-SAA)與隨機(jī)任務(wù)卸載(random task offload strategy，RTOS)的任務(wù)數(shù)與時(shí)延的關(guān)系。

圖6 系統(tǒng)時(shí)延與卸載任務(wù)數(shù)量關(guān)系(P=16 mW)

從圖中可以看出，隨著任務(wù)數(shù)的增大，基于HFSP-SAA卸載策略比RTOS卸載策略的系統(tǒng)時(shí)延要少，這是因?yàn)镠FSP-SAA卸載策略綜合考慮了兩道工序的加工時(shí)間，確定了合理的任務(wù)卸載順序，從而使得系統(tǒng)時(shí)延得以減少，且隨著任務(wù)數(shù)量的增大，HFSP-SAA卸載策略的優(yōu)勢(shì)更加明顯，因此提出的卸載策略可以有效降低時(shí)延，提高用戶體驗(yàn)。

圖7展示了在2用戶不同核數(shù)情況下，系統(tǒng)時(shí)延與卸載任務(wù)數(shù)量的關(guān)系。從圖中可以看出，當(dāng)核數(shù)小于用戶數(shù)時(shí)，系統(tǒng)時(shí)延優(yōu)化瓶頸在核服務(wù)器等待和空閑時(shí)延上，此時(shí)核數(shù)的增加可以顯著減少時(shí)延，而當(dāng)核數(shù)大于或等于用戶數(shù)時(shí),核數(shù)的增加不會(huì)顯著減少時(shí)延，系統(tǒng)時(shí)延優(yōu)化瓶頸在第一道工序的任務(wù)上傳上。由此可得出參與計(jì)算卸載最佳的核數(shù)應(yīng)該等于或近似于參與任務(wù)卸載的用戶數(shù)，由此可以實(shí)現(xiàn)服務(wù)器端能耗的節(jié)約，當(dāng)參與調(diào)度的用戶數(shù)改變時(shí)，動(dòng)態(tài)調(diào)節(jié)核數(shù)，保證核數(shù)等于或近似于用戶數(shù)時(shí)，從而可以有效降低用戶任務(wù)卸載時(shí)延。

圖7 不同核數(shù)下時(shí)延與卸載任務(wù)數(shù)量關(guān)系

圖8展示了2用戶情景下，不同核數(shù)不同的權(quán)重下，能耗與時(shí)延的優(yōu)化關(guān)系。從圖中可以看出，當(dāng)用戶數(shù)大于核數(shù)時(shí)，增加核數(shù)可以顯著減少時(shí)延。系統(tǒng)時(shí)延隨著η增大而增大，系統(tǒng)能耗隨著η增大而減小，但能耗呈現(xiàn)先陡峭后平緩減少的走勢(shì);陡峭部分的能耗說明當(dāng)能耗增大到某一程度后，能耗的增加不會(huì)降低時(shí)延，當(dāng)能耗小到某一程度，能耗與時(shí)延成反比關(guān)系，能耗降低會(huì)引起時(shí)延的增大。當(dāng)M=1時(shí)，用戶數(shù)大于核服務(wù)器數(shù)量時(shí)，此時(shí)能耗的增加并不會(huì)引起時(shí)延降低，可取η=10 000，作為優(yōu)化權(quán)重，從而實(shí)現(xiàn)節(jié)約能耗，對(duì)于用戶數(shù)小于核數(shù)的M=4和M=2的情況，可取η=10作為優(yōu)化權(quán)重，此時(shí)能耗較低，時(shí)延較低，由此實(shí)現(xiàn)節(jié)約能耗的目的。

圖8 系統(tǒng)時(shí)延與能耗關(guān)系

5 結(jié)束語

該文研究了多用戶多核情景下多個(gè)獨(dú)立任務(wù)調(diào)度和功率分配問題。基于混合流水車間調(diào)度模型和模擬退火算法，對(duì)系統(tǒng)時(shí)延和能耗進(jìn)行加權(quán)和優(yōu)化，獲得了最佳的任務(wù)卸載調(diào)度甘特圖。與隨機(jī)任務(wù)卸載調(diào)度相比，提出的卸載調(diào)度策略時(shí)延較小。找到了一種基于混合車間模型的核服務(wù)器數(shù)量與參與調(diào)度的用戶數(shù)的關(guān)系，從而確定最佳的核服務(wù)器數(shù)量，解決了當(dāng)用戶數(shù)大于核數(shù)時(shí)，系統(tǒng)時(shí)延的優(yōu)化瓶頸。最后揭示時(shí)延與能耗之間的關(guān)系，根據(jù)核數(shù)與用戶數(shù)關(guān)系，找到了不同情況下最佳的優(yōu)化權(quán)重，從而達(dá)到了節(jié)約能耗的目的。