面向優先級任務的移動邊緣計算資源分配方法

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

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

0 概述

移動互聯網的發展使得移動終端(如手機、平板電腦等)逐漸取代臺式設備,成為人們日常處理信息的主要工具。目前,移動終端的通信計算量呈爆炸式增長的趨勢,但由于硬件設備條件約束,其在處理大量計算業務時會導致較高的計算時延,并且加速電池的能量消耗,降低用戶的體驗質量(Quality of Experience,QoE)。傳統方法將移動端需要進行計算的任務部署至云服務器,解決了移動設備計算資源有限導致計算時延過高的問題,但是將任務全部傳輸至距移動端較遠的云服務器進行計算,會面臨網絡負荷和通信鏈路傳輸時延增加,以及通信鏈路帶寬有限的問題。對此,研究者提出了移動邊緣計算的概念[1]。移動邊緣計算整合了距用戶移動端較近的邊緣網絡中的計算資源,能夠降低網絡負荷和通信鏈路的傳輸時延,提高任務分發能力同時優化終端用戶的使用體驗。但移動邊緣網絡中的計算資源有限,因此需要設計合理的計算資源分配策略,以降低計算時延和能量消耗。

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

1 相關研究

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

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

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

2 場景分析與系統建模

2.1 場景分析

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

圖1 資源分配場景

2.2 系統建模

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

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

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

3)對任務在邊緣服務器端的計算時間進行建模。通過對優先級不同的任務進行加權處理,分配相應的計算資源,服務器同時處理所需計算的任務,完成后即將計算結果發送回對應的移動端,取邊緣服務器進行任務計算所需的最長計算時間作為計算時間。

由移動端及邊緣服務器構成的系統任務處理流程如圖2所示。

圖2 任務處理流程

2.2.1 任務優先級加權設定

2.2.2 數據傳輸時間設定

Vmax=Blb(1+S/N0)

(1)

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

(2)

2.2.3 邊緣服務器端計算時間建模

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

3 邊緣服務器計算資源分配策略

3.1 基于優先級的資源分配方式

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

圖3 資源分配過程

(3)

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

(4)

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

(5)

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

min{TC}

(6)

3.2 加權算法描述

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

面向優先級任務的加權分配算法執行步驟如下:1)初始化時輸入任務的優先級和任務數據數據量等參數;2)根據相關參數及歸一化系數設定加權值;3)利用加權值將計算資源分配給各個任務進行計算。算法描述如下:

輸入Tn,SC,SW

輸出計算結果,計算時延,系統能耗

1)任務傳輸至邊緣服務器端后,將其置于調度隊列中,以任務優先級為關鍵字對任務進行排序。

2)根據任務優先級及任務的期望完成時間,以及邊緣服務器的計算能力,按式(4)計算加權值。

3)檢測邊緣服務器的工作狀態SW,若SW=1,則將任務置于調度隊列中等待;若SW=0,則按加權數值進行進行資源分配并開始計算,計算完成后將計算結果回傳至各任務所對應的移動端。

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

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

t=ttrans+TC

(7)

設定各個移動終端的發射功率及計算功率相同,則由移動端與邊緣服務器組成的系統完成計算所消耗的總能量Etotal可記為:

Etotal=Mpn×ttrans+SP×TC

(8)

4 仿真實驗

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

表1 仿真參數設定Fig.1 Simulation parameter setting

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

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

Fig.4 Calculation time of mobile terminal and edge server

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

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

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

圖6 4種方法的能耗對比

Fig.6 Comparison of energy consumption of four methods

5 結束語

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