基于模擬退火的多核多用戶任務卸載調度

魯 偉，宋榮方

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

0 引 言

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

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

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

1.1 任務調度與傳輸速率的定義

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

(1)

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

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

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

圖1 混合流水車間調度模型

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

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

(2)

(3)

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

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

(4)

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

(5)

2 問題建模

基于以上分析，該文以最小化時延和能耗的加權和為目標，即：

(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

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

3 模擬退火算法

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

(7)

算法流程：

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

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

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

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

4 仿真結果與分析

下面對多用戶多核服務器的MEC系統(tǒng)分別用基于混合流水車間模型的模擬退火算法(HFSP-SAA)與隨機任務卸載(random task offload strategy，RTOS)的任務數(shù)與時延的關系任務卸載調度進行仿真并分析。仿真中計算任務的數(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用戶時延與卸載任務數(shù)的關系。

圖2 時延與卸載任務之間關系(M=2)

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

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

圖3 P=0.5 mW任務卸載甘特圖

圖4 P=16 mW任務卸載甘特圖

圖5 P=32 mW任務卸載甘特圖

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

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

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

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

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

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

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

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

5 結束語

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