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

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

0 概述

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

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

1 相關(guān)研究

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

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

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

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

2.1 場(chǎng)景分析

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

圖1 資源分配場(chǎng)景

2.2 系統(tǒng)建模

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

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

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

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

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

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

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

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

Vmax=Blb(1+S/N0)

(1)

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

(2)

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

邊緣服務(wù)器端的具體參數(shù)設(shè)定如下:邊緣網(wǎng)絡(luò)中有1臺(tái)服務(wù)器,用S1表示。對(duì)于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ù)器的計(jì)算能力,即單位時(shí)間內(nèi)邊緣服務(wù)器可提供的計(jì)算資源量(以bit/s為單位);SP表示邊緣服務(wù)器的計(jì)算功率。

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

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

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

圖3 資源分配過(guò)程

(3)

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

(4)

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

(5)

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

min{TC}

(6)

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

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

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

輸入Tn,SC,SW

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

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

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

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

4)取k個(gè)任務(wù)中計(jì)算時(shí)間最大值作為計(jì)算時(shí)延。

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

t=ttrans+TC

(7)

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

Etotal=Mpn×ttrans+SP×TC

(8)

4 仿真實(shí)驗(yàn)

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

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

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

圖4 移動(dòng)端與邊緣服務(wù)器的計(jì)算時(shí)間

Fig.4 Calculation time of mobile terminal and edge server

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

圖5 4種方法的計(jì)算時(shí)間對(duì)比

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

圖6 4種方法的能耗對(duì)比

Fig.6 Comparison of energy consumption of four methods

5 結(jié)束語(yǔ)

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