面向優(yōu)先級任務(wù)的移動邊緣計算資源分配方法

董思岐,吳嘉慧,李海龍,屈毓錛,胡 磊

(1.火箭軍工程大學 作戰(zhàn)保障學院,西安 710025; 2.中國電子科技集團公司第二十八研究所,南京 210007)

0 概述

移動互聯(lián)網(wǎng)的發(fā)展使得移動終端(如手機、平板電腦等)逐漸取代臺式設(shè)備,成為人們?nèi)粘Ｌ幚硇畔⒌闹饕ぞ?。目?移動終端的通信計算量呈爆炸式增長的趨勢,但由于硬件設(shè)備條件約束,其在處理大量計算業(yè)務(wù)時會導(dǎo)致較高的計算時延,并且加速電池的能量消耗,降低用戶的體驗質(zhì)量(Quality of Experience,QoE)。傳統(tǒng)方法將移動端需要進行計算的任務(wù)部署至云服務(wù)器,解決了移動設(shè)備計算資源有限導(dǎo)致計算時延過高的問題,但是將任務(wù)全部傳輸至距移動端較遠的云服務(wù)器進行計算,會面臨網(wǎng)絡(luò)負荷和通信鏈路傳輸時延增加,以及通信鏈路帶寬有限的問題。對此,研究者提出了移動邊緣計算的概念[1]。移動邊緣計算整合了距用戶移動端較近的邊緣網(wǎng)絡(luò)中的計算資源,能夠降低網(wǎng)絡(luò)負荷和通信鏈路的傳輸時延,提高任務(wù)分發(fā)能力同時優(yōu)化終端用戶的使用體驗。但移動邊緣網(wǎng)絡(luò)中的計算資源有限,因此需要設(shè)計合理的計算資源分配策略,以降低計算時延和能量消耗。

目前關(guān)于計算資源分配的研究,多數(shù)按照任務(wù)請求計算卸載的時間順序為其分配計算資源,而在許多實際應(yīng)用中,任務(wù)計算處理的緊迫程度或重要性具有一定區(qū)分度,僅依靠任務(wù)請求計算卸載的時間順序?qū)ζ溥M行資源分配是不合理的,結(jié)合實際需要劃分任務(wù)的優(yōu)先級并據(jù)此進行計算資源分配,能夠更好地滿足任務(wù)的計算需求。因此,本文提出面向優(yōu)先級任務(wù)的邊緣計算資源分配方法,根據(jù)任務(wù)優(yōu)先級通過加權(quán)法分配相應(yīng)的計算資源,在保障高優(yōu)先級任務(wù)獲取計算資源的同時,減少系統(tǒng)任務(wù)的計算時間及能量消耗。

1 相關(guān)研究

將計算任務(wù)卸載至邊緣服務(wù)器進行計算,需要通過通信鏈路將數(shù)據(jù)傳輸至邊緣服務(wù)器端,邊緣服務(wù)器利用計算資源對任務(wù)進行計算,計算完成后再將計算結(jié)果傳輸至移動端。整個過程中涉及的資源主要為通信鏈路的通信資源及邊緣服務(wù)器的計算資源。文獻[2]提出了基于半定松弛和隨機化映射的啟發(fā)式算法,將最小化時延和能耗問題公式化為非凸約束二次規(guī)劃問題。實驗結(jié)果表明,該算法經(jīng)過少量隨機性迭代即可達到最優(yōu)性能。文獻[3]提出利用迭代算法查找上行鏈路發(fā)送的比特數(shù)量的最優(yōu)值,其對文獻[2]的卸載策略做了進一步的討論,論證了信道質(zhì)量好時執(zhí)行計算卸載的效率更高。文獻[4]通過設(shè)置存放計算業(yè)務(wù)的緩沖區(qū),在緩沖區(qū)穩(wěn)定性約束的基礎(chǔ)上構(gòu)建功耗最小化模型,并利用Lyapunov算法進行傳輸功率和帶寬分配優(yōu)化。文獻[5]提出整合上行鏈路的傳輸功率與邊緣計算服務(wù)器處的計算資源分配,利用凸優(yōu)化算法實現(xiàn)計算資源分配,設(shè)計一種啟發(fā)式算法解決任務(wù)卸載問題。文獻[6]提出了基于效益函數(shù)模型的資源優(yōu)化方法增加系統(tǒng)收益,并對多種研究場景進行了討論分析。文獻[7]通過對任務(wù)數(shù)據(jù)進行壓縮,構(gòu)建在通信資源充足而計算資源有限場景下的分段優(yōu)化模型,達到減少移動端計算時延的目的。文獻[8]在增強現(xiàn)實任務(wù)的場景下建立凸優(yōu)化資源求解數(shù)學模型,研究在不同時延約束條件下節(jié)約能耗的情況。文獻[9]通過對博弈算法和匈牙利算法的相互迭代解決資源分配的優(yōu)化問題,從而降低了計算能耗及時延。文獻[10]提出一種能耗感知的卸載方案,將電池剩余電量引入到能量消耗和時間延遲的加權(quán)因子中,通過迭代搜索算法優(yōu)化通信和計算資源的分配。文獻[11]構(gòu)建了移動端的待處理數(shù)據(jù)具有異構(gòu)性的能量消耗模型,根據(jù)任務(wù)的截止時間在調(diào)度階段設(shè)定卸載時間間隔。文獻[12]通過設(shè)計分布式計算卸載算法,對計算時延和能耗指標進行量化,達到了更低的計算時間開銷。文獻[13]通過二分法尋找需要進行計算卸載的移動設(shè)備的最優(yōu)發(fā)射功率和匹配計算資源,提高了用戶的任務(wù)卸載量,有效減少了系統(tǒng)開銷。

由上述研究可以看出,在資源分配方面,研究者主要通過優(yōu)化移動端的發(fā)射功率以及合理分配通信帶寬,或結(jié)合優(yōu)化邊緣服務(wù)器端的計算資源來降低時延及能耗。此外,在移動邊緣計算的研究場景中沒有區(qū)分任務(wù)之間的優(yōu)先級,默認任務(wù)之間為平等關(guān)系。文獻[14]考慮了任務(wù)間的優(yōu)先級關(guān)系,在云計算場景下構(gòu)建符合用戶優(yōu)先級的適應(yīng)度函數(shù),通過引入重優(yōu)化判斷準則優(yōu)化了粒子群算法,從而得到全局最優(yōu)解。

區(qū)別于云計算場景下基于任務(wù)優(yōu)先級的資源分配算法、對任務(wù)進行部分卸載計算及定義任務(wù)優(yōu)先級的方式,面向移動邊緣計算場景,本文提出針對邊緣服務(wù)器資源的加權(quán)分配策略,以任務(wù)平均價值量作為任務(wù)優(yōu)先級區(qū)分標準,將任務(wù)全部卸載到邊緣服務(wù)器進行計算。

2 場景分析與系統(tǒng)建模

2.1 場景分析

本文策略針對的移動端(任務(wù))與服務(wù)器多對一場景如圖1所示,其中有多個移動設(shè)備終端和一臺邊緣計算服務(wù)器,每個設(shè)備終端處包含一個需要進行計算處理的任務(wù)。各個移動終端上待處理的任務(wù)根據(jù)其平均計算價值量劃分優(yōu)先級高低。由于移動終端計算能力有限,若在移動終端進行處理,可能會導(dǎo)致計算時間過長超出任務(wù)的處理時間限制,或本地資源不足以支持完成計算。因此,需要將待處理任務(wù)卸載至邊緣計算服務(wù)器上進行計算。通過無線通信鏈路將任務(wù)傳輸至邊緣計算服務(wù)器,邊緣計算服務(wù)器利用自身計算資源完成計算任務(wù)后,再由無線通信鏈路將計算結(jié)果傳回至移動設(shè)備終端?？紤]到通信鏈路帶寬及通信資源有限,邊緣計算服務(wù)器的計算資源也是有限的,本文對邊緣服務(wù)器端的計算資源優(yōu)化分配方法進行分析,以期在存在資源和任務(wù)優(yōu)先級約束的條件下降低計算時延與能量消耗。

圖1 資源分配場景

2.2 系統(tǒng)建模

基于上述場景分析及任務(wù)計算流程,將系統(tǒng)建模分為以下3個部分:

1)任務(wù)平均優(yōu)先級建模。首先需要對任務(wù)根據(jù)其要處理的平均價值量進行任務(wù)的優(yōu)先級劃分。

2)對任務(wù)在通信鏈路上的傳輸時延進行建模。傳輸時延為任務(wù)數(shù)據(jù)由移動端發(fā)送至邊緣服務(wù)器過程中消耗的時間與邊緣服務(wù)器將計算結(jié)果回傳至移動端消耗的時間之和。由于邊緣服務(wù)器的發(fā)射功率較大,因此在計算時間延遲時可以忽略將數(shù)據(jù)由邊緣服務(wù)器回傳至移動端的時間消耗,只考慮將任務(wù)數(shù)據(jù)上傳至邊緣服務(wù)器的時間消耗。

3)對任務(wù)在邊緣服務(wù)器端的計算時間進行建模。通過對優(yōu)先級不同的任務(wù)進行加權(quán)處理,分配相應(yīng)的計算資源,服務(wù)器同時處理所需計算的任務(wù),完成后即將計算結(jié)果發(fā)送回對應(yīng)的移動端,取邊緣服務(wù)器進行任務(wù)計算所需的最長計算時間作為計算時間。

由移動端及邊緣服務(wù)器構(gòu)成的系統(tǒng)任務(wù)處理流程如圖2所示。

圖2 任務(wù)處理流程

2.2.1 任務(wù)優(yōu)先級加權(quán)設(shè)定

2.2.2 數(shù)據(jù)傳輸時間設(shè)定

Vmax=Blb(1+S/N0)

(1)

其中,S/N0為信噪比,S為信道內(nèi)信號傳輸功率,N0為信道內(nèi)噪聲功率。任務(wù)Tn在通信信道中由移動設(shè)備終端傳輸至邊緣計算服務(wù)器的傳輸速率可表示為:

(2)

2.2.3 邊緣服務(wù)器端計算時間建模

邊緣服務(wù)器端的具體參數(shù)設(shè)定如下:邊緣網(wǎng)絡(luò)中有1臺服務(wù)器,用S1表示。對于S1服務(wù)器的相關(guān)參數(shù),用集合S1={SW,SC}表示具體的參數(shù)配置及服務(wù)器狀態(tài),其中:SW表示邊緣服務(wù)器的工作狀態(tài),SW=1代表服務(wù)器正忙,SW=0代表服務(wù)器處于空閑狀態(tài);SC表示邊緣服務(wù)器的計算能力,即單位時間內(nèi)邊緣服務(wù)器可提供的計算資源量(以bit/s為單位);SP表示邊緣服務(wù)器的計算功率。

3 邊緣服務(wù)器計算資源分配策略

3.1 基于優(yōu)先級的資源分配方式

邊緣服務(wù)器的計算資源有限,需要根據(jù)任務(wù)的優(yōu)先級進行計算資源分配,分配過程如圖3所示。

圖3 資源分配過程

(3)

由式(3)可知,λ系數(shù)影響對應(yīng)優(yōu)先級任務(wù)所能獲取到的計算資源量,因此,λ需要體現(xiàn)任務(wù)的優(yōu)先級指標作為資源分配的加權(quán)系數(shù)。假定λ1,λ2,…,λk之間滿足以下關(guān)系:

(4)

TC=max{TC1,TC2,…,TCk}

(5)

在進行計算的整個過程中,每個任務(wù)間的計算是相互獨立的,可以將計算事件視為獨立離散事件,將最小化時延轉(zhuǎn)化為約束條件下的單目標組合優(yōu)化性質(zhì)的問題,因此時間延遲的數(shù)學模型可表示為:

min{TC}

(6)

3.2 加權(quán)算法描述

本文算法將最小化時延問題轉(zhuǎn)化為加權(quán)線性規(guī)劃問題,首先通過分治思想將時間延遲及能量消耗問題分解為各部分建模模塊消耗的時間及能耗的子問題進行求解,結(jié)合任務(wù)優(yōu)先級、服務(wù)器計算能力及計算資源量的約束,通過線性規(guī)劃方法為不同任務(wù)分配相應(yīng)加權(quán)值的計算資源,降低處理任務(wù)計算能耗的時間延遲。

面向優(yōu)先級任務(wù)的加權(quán)分配算法執(zhí)行步驟如下:1)初始化時輸入任務(wù)的優(yōu)先級和任務(wù)數(shù)據(jù)數(shù)據(jù)量等參數(shù);2)根據(jù)相關(guān)參數(shù)及歸一化系數(shù)設(shè)定加權(quán)值;3)利用加權(quán)值將計算資源分配給各個任務(wù)進行計算。算法描述如下:

輸入Tn,SC,SW

輸出計算結(jié)果,計算時延,系統(tǒng)能耗

1)任務(wù)傳輸至邊緣服務(wù)器端后,將其置于調(diào)度隊列中,以任務(wù)優(yōu)先級為關(guān)鍵字對任務(wù)進行排序。

2)根據(jù)任務(wù)優(yōu)先級及任務(wù)的期望完成時間,以及邊緣服務(wù)器的計算能力,按式(4)計算加權(quán)值。

3)檢測邊緣服務(wù)器的工作狀態(tài)SW,若SW=1,則將任務(wù)置于調(diào)度隊列中等待;若SW=0,則按加權(quán)數(shù)值進行進行資源分配并開始計算,計算完成后將計算結(jié)果回傳至各任務(wù)所對應(yīng)的移動端。

4)取k個任務(wù)中計算時間最大值作為計算時延。

忽略任務(wù)進行優(yōu)先級排序及資源分配所需時間,由移動端與邊緣服務(wù)器組成的系統(tǒng)完成計算所消耗的總時間t可記為:

t=ttrans+TC

(7)

設(shè)定各個移動終端的發(fā)射功率及計算功率相同,則由移動端與邊緣服務(wù)器組成的系統(tǒng)完成計算所消耗的總能量Etotal可記為:

Etotal=Mpn×ttrans+SP×TC

(8)

4 仿真實驗

利用Matlab仿真平臺對本文方法作實驗驗證,并與以下3種方法進行對比:將任務(wù)全部置于本地移動端進行計算的方法(本地計算方法),將任務(wù)卸載至邊緣服務(wù)器進行計算時平均分配計算資源的方法[18](平均分配方法),按照任務(wù)數(shù)據(jù)量大小分配計算資源的方法[19](按數(shù)據(jù)量分配方法)。對比的性能指標為計算時延和能耗:將任務(wù)置于本地移動設(shè)備端進行處理的時延為移動端的計算時延;將任務(wù)卸載至邊緣服務(wù)器進行處理的時延為邊緣服務(wù)器計算時延與將數(shù)據(jù)傳輸至服務(wù)器的上傳時延之和;將任務(wù)置于本地進行處理的能耗為移動端的計算功率與計算時延之積。將任務(wù)卸載至邊緣服務(wù)器進行處理時,由移動端及邊緣服務(wù)器構(gòu)成的整體系統(tǒng)的能耗為移動端的待機功率與時延之積、移動端的發(fā)射功率與數(shù)據(jù)傳輸時延之積、邊緣服務(wù)器的計算時間與計算功率之積三部分總和。具體數(shù)據(jù)范圍及參數(shù)設(shè)定如表1所示。

表1 仿真參數(shù)設(shè)定Fig.1 Simulation parameter setting

本文研究系統(tǒng)中移動端的任務(wù)數(shù)量范圍為10個～100個時,移動端及由移動端和邊緣服務(wù)器構(gòu)成的系統(tǒng)所用的時延及能耗的數(shù)值。通過本文方法與本地計算及資源平均分配算法的對比,論證本文算法的優(yōu)越性。根據(jù)經(jīng)驗值給出具體的仿真參數(shù)范圍[8-15],實驗中使用的數(shù)據(jù)值由Matlab在表1范圍內(nèi)生成隨機數(shù)作為具體參數(shù)。給定相同的數(shù)據(jù)時,移動端與邊緣服務(wù)器的計算時間如圖4所示。

圖4 移動端與邊緣服務(wù)器的計算時間

Fig.4 Calculation time of mobile terminal and edge server

由圖4可以看出,在相同的數(shù)據(jù)量下,將任務(wù)置于邊緣服務(wù)器進行計算所需要的時間遠低于在移動端本地進行計算消耗的時間,因此,有必要將任務(wù)卸載到邊緣服務(wù)器進行計算。為進一步降低計算時延,將邊緣服務(wù)器端的計算資源根據(jù)任務(wù)的優(yōu)先級進行合理分配。仿真結(jié)果表明:本文算法與平均分配方法相比降低了83.76%的時間消耗,與平均分配方法相比降低了15.05%的時間消耗,與本地計算方法相比降低了99.42%的時間消耗。為便于直觀觀察不同方法間的性能差異,采用對數(shù)縱坐標顯示消耗時間的值,4種方法所需時延如圖5(a)所示,為進一步顯示本文方法與按數(shù)據(jù)量分配方法的對比,將圖5(a)中的虛線框部分放大表示為圖5(b)。

圖5 4種方法的計算時間對比

在對比計算時延的基礎(chǔ)上,對未進行計算卸載時移動端的能量消耗情況與進行計算卸載時由移動端與邊緣服務(wù)器構(gòu)成的系統(tǒng)的能量消耗進行對比,如圖6所示。仿真實驗結(jié)果表明:與本地計算方法相比,本文方法能夠節(jié)約87.69%的計算能耗;與平均分配方法相比,本文方法能夠節(jié)約84.87%的能量消耗,與按任務(wù)數(shù)據(jù)量分配方法相比,本文方法能夠降低17.37%的能量消耗。

圖6 4種方法的能耗對比

Fig.6 Comparison of energy consumption of four methods

5 結(jié)束語

為解決移動端進行任務(wù)計算時時延及能耗高,以及目前研究中利用邊緣計算技術(shù)處理任務(wù)時較少考慮任務(wù)優(yōu)先級的問題,本文提出一種資源加權(quán)分配方法,將有限的計算資源在約束條件下合理分配給具有不同優(yōu)先級的任務(wù)。實驗結(jié)果表明,該方法可以有效降低計算時延與系統(tǒng)能耗。為便于計算,本文設(shè)定數(shù)據(jù)在同一時刻對邊緣服務(wù)器進行計算卸載請求,數(shù)據(jù)傳輸過程中速率恒定,未計算數(shù)據(jù)的回傳時間。下一步將結(jié)合實際情況設(shè)定任務(wù)在不同時刻動態(tài)向邊緣服務(wù)器進行計算卸載請求,同時在數(shù)據(jù)傳輸過程中加入干擾因子使傳輸速率更符合實際傳輸情景。