魯 偉，宋榮方

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

0 引 言

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

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

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

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

移動終端將各自的N項獨立的計算任務(wù)卸載到MEC[11]。記各自的任務(wù)集合為R={T1,T2,…,TN}，每個任務(wù)T用一對參數(shù)〈Di,Ci〉來表示，其中Di(bits)表示任務(wù)的數(shù)據(jù)量，Ci(cycles/bit)表示每比特的數(shù)據(jù)所需的計算資源。每個用戶N個任務(wù)的卸載調(diào)度順序定義為σ={σ1,σ2,…,σN}，其中TNσi表示該任務(wù)N于第i次卸載到MEC服務(wù)器上。該文研究移動端配置單天線情景，一次只能發(fā)一個任務(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)時延和能耗模型

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

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

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

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

(2)

(3)

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

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

(4)

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

(5)

2 問題建模

基于以上分析，該文以最小化時延和能耗的加權(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ù)量級，當(dāng)其較大時，表示對系統(tǒng)能耗的優(yōu)化更加看重。該求解問題是一個優(yōu)化問題，可以使用窮舉算法遍歷所有情況，但復(fù)雜度太高?？紤]到模擬退火算法是一種借鑒于固體的退火原理的優(yōu)化算法，計算過程簡單，通用，魯棒性強，適用于并行處理，可用于求解復(fù)雜的優(yōu)化問題，所以用模擬退火算法對問題p進行求解。

3 模擬退火算法

模擬退火算法(simulated annealing algorithm，SAA)是一種基于蒙特卡洛迭代的隨機尋優(yōu)算法，其出發(fā)點是模仿物理中固定物質(zhì)的退火過程與一般組合優(yōu)化問題之間的相似性[15]。模擬退火算法在某一初溫下，隨著溫度參數(shù)的不斷下降，以一定的概率突跳，在解空間中隨機尋找目標(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，即開始退火的初始溫度，隨機生成一個初始解Xbest=X0，并計算相應(yīng)的目標(biāo)函數(shù)值E(x0)，令T等于冷卻進度表中的下一個溫度值Ti。

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

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

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

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

下面對多用戶多核服務(wù)器的MEC系統(tǒng)分別用基于混合流水車間模型的模擬退火算法(HFSP-SAA)與隨機任務(wù)卸載(random task offload strategy，RTOS)的任務(wù)數(shù)與時延的關(guān)系任務(wù)卸載調(diào)度進行仿真并分析。仿真中計算任務(wù)的數(shù)據(jù)量Di和所需的計算資源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時基于混合流水車間模型模擬退火算法在不同傳輸功率下2核2用戶時延與卸載任務(wù)數(shù)的關(guān)系。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)束語

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