物聯(lián)網(wǎng)邊緣計算卸載和資源分配李氏優(yōu)化

衛(wèi)金菊，郭榮佐，謝小川，黎 力

(1.四川師范大學(xué) 計算機科學(xué)學(xué)院，四川 成都 610101；2.四川師范大學(xué) 教師教育學(xué)院，四川 成都 610068；3.同濟大學(xué) 軟件學(xué)院，上海 201804)

0 引 言

物聯(lián)網(wǎng)是實現(xiàn)物物相連，萬物互聯(lián)的基礎(chǔ)，廣泛應(yīng)用于各個領(lǐng)域，如智慧城市、智能交通、VR/AR、智能可穿戴設(shè)備、語言識別等[1]計算密集型和時延敏感型的設(shè)備。同時，隨著物聯(lián)網(wǎng)技術(shù)的不斷發(fā)展，物聯(lián)網(wǎng)終端設(shè)備產(chǎn)生的計算密集型任務(wù)不斷增多，產(chǎn)生的數(shù)據(jù)呈指數(shù)式增長，但由于終端設(shè)備在電池壽命和計算能力等諸多方面存在缺陷，這使得物聯(lián)網(wǎng)終端設(shè)備難以支持上訴應(yīng)用，且面臨著延遲長、能耗高和通信量大等挑戰(zhàn)[2]。為有效解決這些挑戰(zhàn)，有專家、學(xué)者遂即提出邊緣計算(edge computing，EC)的概念，EC的引入可用于實時、快速地處理數(shù)據(jù)，縮短延遲時間，同時還能減少網(wǎng)絡(luò)流量。將邊緣計算與物聯(lián)網(wǎng)結(jié)合，建立物聯(lián)網(wǎng)邊緣計算層次模型，可用于減小物聯(lián)網(wǎng)系統(tǒng)中終端設(shè)備處理的時延、能耗等問題，同時還能減少網(wǎng)絡(luò)帶寬及增強數(shù)據(jù)安全和隱私等[3]。針對物聯(lián)網(wǎng)終端設(shè)備的資源管理問題，其任務(wù)卸載決策主要取決于是否卸載及如何卸載，計算資源分配主要取決于對計算能力、資源等的優(yōu)化分配，那么采用何種算法或策略，能夠減少系統(tǒng)的時延和能耗的同時，使物聯(lián)網(wǎng)終端設(shè)備的計算卸載和資源分配更加合理，已受到國內(nèi)外學(xué)者的廣泛關(guān)注[4]，也出現(xiàn)一系列的研究成果。

1 現(xiàn)有研究

現(xiàn)有研究者對邊緣計算時延和能耗進行了相應(yīng)的研究。文獻[5]中，提出了利用邊緣計算體系結(jié)構(gòu)來解決隨物聯(lián)網(wǎng)設(shè)備和數(shù)據(jù)的增加導(dǎo)致的云通訊低時延，造成網(wǎng)絡(luò)擁塞的問題。文獻[6]中，制定了一個計算資源分配的聯(lián)合優(yōu)化，在不同的邊緣服務(wù)器，智能終端卸載工作負(fù)載及其無線電資源分配NOMA傳輸，最小化系統(tǒng)成本的函數(shù)優(yōu)化模型。文獻[7]中，解決基于物聯(lián)網(wǎng)設(shè)備的資源有限的情況下，將物聯(lián)網(wǎng)設(shè)備的應(yīng)用任務(wù)轉(zhuǎn)移到遠(yuǎn)程云數(shù)據(jù)中心時會給網(wǎng)絡(luò)帶來很大的負(fù)擔(dān)這一問題，實現(xiàn)卸載成本與性能之間的折中，將計算卸載描述為一個優(yōu)化問題模型，以最小化卸載成本為目標(biāo)，提出了一種動態(tài)計算算法(DCOA)。文獻[8]中，將物聯(lián)網(wǎng)邊緣計算網(wǎng)絡(luò)中具有資源分配的多個用戶的計算卸載機制描述為一個隨機博弈，通過選擇自己的發(fā)射功率電頻、RAT和子信道，在本地計算或邊緣計算上學(xué)習(xí)最優(yōu)決策，以最小化長期系統(tǒng)開銷為目標(biāo)，提出了一種基于獨立學(xué)習(xí)者的多智能體Q-learning(IL-basedma-Q)算法，建立了一個多智能體強化學(xué)習(xí)框架來解決博弈問題。文獻[9]中，解決了如何有效且合理地平衡時延和能耗，以滿足各種物聯(lián)網(wǎng)應(yīng)用的用戶需求，將問題形式化為一個約束多目標(biāo)優(yōu)化問題，并采用改進的快速精英非支配排序遺傳算法(NSGA-II)求解，同時在改進的NSGA-II中提出了一種新的針對特定問題的編碼方案和遺傳算子。文獻[10]中，以卸載成本為優(yōu)化目標(biāo)，以隊列穩(wěn)定性為約束條件，建立了一種以卸載成本為優(yōu)化目標(biāo)的優(yōu)化模型，提出了一種基于Lyapunov優(yōu)化的漂移加成本計算卸載策略(DCCO)算法。

綜上所述，在目前的大量研究中，主要針對的是物聯(lián)網(wǎng)終端設(shè)備計算資源受限的任務(wù)卸載到邊緣服務(wù)器的時延和能耗問題，但很少考慮到卸載至邊緣服務(wù)器端時可能存在任務(wù)積壓的問題，以及未能考慮到任務(wù)可能會出現(xiàn)丟棄的情況。因此，本文將研究在單個邊緣服務(wù)器下，一定的時間限制內(nèi)，將任務(wù)卸載到邊緣服務(wù)器產(chǎn)生的隊列積壓問題，并提出了基于李氏優(yōu)化的動態(tài)計算算法，該算法的目的是使得在該算法模型中，求解產(chǎn)生的能耗最小。

2 基于物聯(lián)網(wǎng)邊緣計算層次架構(gòu)模型

本文中物聯(lián)網(wǎng)邊緣計算的架構(gòu)模型如圖1所示。大體分為兩個部分：物聯(lián)網(wǎng)感知設(shè)備層和物聯(lián)網(wǎng)網(wǎng)絡(luò)層[11]。其中，在物聯(lián)網(wǎng)感知設(shè)備層中分為3部分，分別表示為感知設(shè)備、感知傳遞、感知互動。感知設(shè)備的作用在于通過傳感器、RFID、攝像頭、充電柱等感知獲取物聯(lián)網(wǎng)終端設(shè)備產(chǎn)生的數(shù)據(jù)，并將獲取的數(shù)據(jù)通過感知傳遞發(fā)送給感知互動層，在感知互動層中包括基站等通訊設(shè)備、WiFi等通訊技術(shù)及智能網(wǎng)關(guān)。其中，通訊設(shè)備和通訊技術(shù)的作用在于傳遞數(shù)據(jù)，而智能網(wǎng)關(guān)[12]的主要作用在于實現(xiàn)系統(tǒng)的信息的采集、信息輸入、信息輸出、集中控制、遠(yuǎn)程控制、聯(lián)動控制等功能，并且向邊緣服務(wù)器傳輸數(shù)據(jù)。感知互動層的作用在于接收來自感知設(shè)備的數(shù)據(jù)后，將其傳遞給智能網(wǎng)關(guān)，最后智能網(wǎng)關(guān)處將收集到的數(shù)據(jù)傳遞給網(wǎng)絡(luò)層的邊緣服務(wù)器，并在此處對數(shù)據(jù)進行處理。

圖1 物聯(lián)網(wǎng)邊緣計算的架構(gòu)模型

3 物聯(lián)網(wǎng)邊緣計算系統(tǒng)模型及問題描述

3.1 系統(tǒng)模型

本文研究的系統(tǒng)模型如圖2所示，其中包含一個邊緣服務(wù)器，一個無線訪問節(jié)點(access point，AP)和物聯(lián)網(wǎng)終端設(shè)備，并將邊緣服務(wù)器部署在AP的附近，以便對物聯(lián)網(wǎng)終端設(shè)備卸載到服務(wù)器的數(shù)據(jù)進行處理，AP與感知設(shè)備通過無線鏈路的方式連接[13]。在終端處有多種終端設(shè)備，其中可包括智慧交通、人臉識別、智慧工廠、可穿戴設(shè)備等。本文針對一個物聯(lián)網(wǎng)終端設(shè)備與邊緣服務(wù)器間的時延和能耗問題進行研究，時隙用t表示，時隙長度和時間長度的索引值分別用τt和T={0,1,2,…} 表示。

圖2 物聯(lián)網(wǎng)邊緣計算系統(tǒng)模型簡

3.2 計算模型

(1)本地計算模型

(1)

(2)

(2)卸載計算模型

(3)

其中，D表示處理任務(wù)的數(shù)據(jù)量，Rt表示在時隙t時，在信道的傳輸速率。

在本文中，假設(shè)每個終端設(shè)備通過正交頻分多址的方法接入邊緣服務(wù)器中，同時不考慮每個終端設(shè)備相互干擾的情況，設(shè)時隙t的傳輸功率為Pt， 根據(jù)香農(nóng)公式可得計算此時的信道傳輸速率Rt

(4)

其中，B為設(shè)備終端分配的信道帶寬，gt為時隙t時終端設(shè)備產(chǎn)生的信道增益，σ是接收噪音的功率。

(5)

(3)問題建模

在該系統(tǒng)模型中，將時隙t時的總時延用Tt表示，包括處理任務(wù)A時，在物聯(lián)網(wǎng)終端設(shè)備端和邊緣服務(wù)器端產(chǎn)生的時延之和，其表達式為

(6)

該模型在t時隙處理任務(wù)的總能耗為Et， 系統(tǒng)的總能耗表示時隙t時，在處理待任務(wù)A時，在物聯(lián)網(wǎng)終端設(shè)備端和邊緣服務(wù)器端的能耗之和，則可用公式表示為

(7)

(8)

(9)

(10)

s.t.

Tt≤τ,t∈T

(11)

Et≤Emax,t∈T

(12)

(13)

(14)

(15)

0≤Pt≤Pmax

(16)

其中，式(11)表示在該系統(tǒng)模式下，物聯(lián)網(wǎng)邊緣計算卸載的時延應(yīng)小于所設(shè)置的最大時延；式(12)是表示每個時間段邊緣計算的產(chǎn)生能耗不能超過的最大能耗；式(13)、式(14)表示物聯(lián)網(wǎng)邊緣計算的卸載決策，且物聯(lián)網(wǎng)終端設(shè)備任務(wù)選擇是0-1約束，即每個時隙的任務(wù)只能處于一種狀態(tài)；式(15)是物聯(lián)網(wǎng)終端設(shè)備的計算頻率取值范圍；式(16)是指物聯(lián)網(wǎng)終端設(shè)備的傳輸功率不能超過最大功率。

3.3 排隊模型

根據(jù)李雅普諾夫優(yōu)化理論，引入一個排隊隊列對邊緣服務(wù)器設(shè)置隊列緩沖區(qū)，在時隙t時，待處理任務(wù)的隊列緩沖區(qū)設(shè)置為：Qt[18]， 該隊列表示在每一時隙，邊緣服務(wù)器處任務(wù)的積壓情況，該隊列的初始條件為0，即Q0=0。 設(shè)該隊列的更新過程為

Qt+1=max(Qt-Ta,0)+Tt,t∈T

(17)

4 基于李雅普諾夫優(yōu)化的動態(tài)計算方法

4.1 問題建模

本文擬采用基于李雅普諾夫優(yōu)化的動態(tài)計算方法求解上述所提出的優(yōu)化問題。利用該方法，可對物聯(lián)網(wǎng)終端設(shè)備的CPU頻率和任務(wù)卸載至邊緣服務(wù)器的計算功率進行動態(tài)劃分，從而得到最優(yōu)的卸載結(jié)果。建立在任務(wù)隊列穩(wěn)定的前提下，求解最小化系統(tǒng)總能耗的問題。根據(jù)李雅普諾夫優(yōu)化算法[19]可先定義該系統(tǒng)模式的二次李雅普諾夫隊列模型為

(18)

利用李雅普諾夫算法可求得在時隙t和時隙t+1之間的變化量。通過式(17)、式(18)，可得到兩個時隙間變化量的推導(dǎo)公式為

(19)

在此，為了能保證隊列的穩(wěn)定性，引入基于李雅普諾夫漂移函數(shù) (Δ(Q(t))) 的條件，其作用表示在從時隙t到時隙t+1時李雅普諾夫函數(shù)的增長量。可通過式(19)，得到其增長量的公式如下

Δ(Q(t))=E{L(Q(t+1))-L(Q(t))|Qt}

(20)

同時，還需定義一個基于李雅普諾夫漂移懲罰函數(shù)求解李雅普諾夫漂移函數(shù)和目標(biāo)函數(shù)的最小解。可通過定義如下的方程式求解其最小值

Δ(Q(t))+V·E(Et|Qt)

(21)

其中，V是懲罰參數(shù)，可理解為權(quán)衡用戶卸載時隊列積壓的非負(fù)懲罰參數(shù)，該參數(shù)的作用在于調(diào)節(jié)Δ(Q(t)) 與目標(biāo)函數(shù)的權(quán)重程度。

在式(20)的函數(shù)方程式中， Δ(Q(t)) 是由時隙t+1的漂移懲罰函數(shù)和時隙t的漂移懲罰函數(shù)的差值得到，若想要得到下一個時隙的基本信息，可根據(jù)李雅普諾夫漂移懲罰函數(shù)理論對上述部分函數(shù)進行變換和伸縮，同時綜合式(21)，然后經(jīng)放縮變形可得

Δ(Q(t))+V·E(Et|Qt)≤B+V·E(Et)+
E(Qt·Tt)-E(Qt·Ta)

(22)

4.2 優(yōu)化計算卸載和資源分配問題

本節(jié)主要闡述如何利用基于李雅普諾夫漂移懲罰因子理論近似求取最優(yōu)解問題。首先，將函數(shù)優(yōu)化模型式(10)進一步轉(zhuǎn)化為基于最小化李雅普諾夫偏移函數(shù)上界的問題，即最小化式(22)，可得到式(23)

(23)

s.t.

(11)～(16)

其次，在式(23)中，由于該式具有組合優(yōu)化的特點，則該優(yōu)化問題是個NP-hard問題，所以，在求解優(yōu)化問題時需要將原問題轉(zhuǎn)化為最優(yōu)卸載決策和資源分配兩個子問題，然后通過將物聯(lián)網(wǎng)終端中的待處理任務(wù)設(shè)置在終端設(shè)備本地執(zhí)行和將其卸載至邊緣服務(wù)端執(zhí)行的求解。

(1)在終端設(shè)備本地執(zhí)行時

(24)

s.t.

kW(ft)2≤Emax

(25)

(26)

(15)

(27)

(2)邊緣服務(wù)器端執(zhí)行

(28)

s.t.

(29)

(30)

(15),(16)

將約束條件式(30)中的Rt用香農(nóng)式(4)表示，則可得

(31)

同時約束條件式(29)可表示為

(32)

(33)

4.3 聯(lián)合求解計算卸載和資源分配

將物聯(lián)網(wǎng)終端設(shè)備在本地執(zhí)行、邊緣服務(wù)器執(zhí)行與丟棄任務(wù)的參數(shù)聯(lián)合成一個目標(biāo)函數(shù)，從而可得到最優(yōu)解S。 設(shè)V?是在終端設(shè)備中，時隙t時，選擇丟棄的成本，其中， ?為丟棄任務(wù)的成本參數(shù)。在本地計算、邊緣服務(wù)器、任務(wù)丟棄的3種計算模式下，對時延約束條件下的最小能耗進行評估，可得到最終的最優(yōu)的計算卸載和資源分配，可將上述問題建立成數(shù)學(xué)模型為

(34)

式中：利用李雅普諾夫優(yōu)化的動態(tài)計算卸載算法，其流程見表1，首先應(yīng)初始化邊緣服務(wù)器的排隊隊列，然后通過求每一個時隙的優(yōu)化問題，更新邊緣服務(wù)器的排隊隊列，進行下一時刻的計算，依次循環(huán)，進而求解得出在該系統(tǒng)模式下最優(yōu)的計算卸載及資源分配策略，即得到Xt,ft,Pt的值，綜上通過此方法，可得到在時延約束條件下，能耗最小的最優(yōu)計算卸載和資源分配問題。其中，基于李雅普諾夫算法的動態(tài)資源分配問題求解的算法如表1所示。

表1 基于李雅普諾夫優(yōu)化的動態(tài)計算方法求解流程

5 仿真實驗

5.1 選擇計算模式的變化情況

圖3比較所選計算模式隨時隙的平均變化情況。由圖3可知：大體可分為兩部分：第一部分時隙數(shù)在0到200，第二部分為時隙數(shù)在200到1000。在第一部分中，即在0到200的時刻時，處于算法迭代的初期，因全局視野有限，同時由于隊列未收斂至穩(wěn)定，其物聯(lián)網(wǎng)終端設(shè)備的待處理任務(wù)選擇的計算模式波動幅度較大。在此部分中，大概在0到10的時刻，處于隊列的初期，絕對部分待處理任務(wù)更傾向于做任務(wù)丟棄的操作，但從10到200時刻，隨著時刻數(shù)的增加，邊緣服務(wù)器端和本地執(zhí)行端均有任務(wù)處理，且邊緣服務(wù)器的計算任務(wù)比重逐漸增大；在第二部分，200到1000時刻，是0到200時刻后隊列在原來的基礎(chǔ)上逐漸趨于逐漸穩(wěn)定的狀態(tài)，任務(wù)丟棄的選擇比重較小，在此時，終端設(shè)備的待處理任務(wù)主要傾向于將任務(wù)卸載至邊緣服務(wù)器端執(zhí)行，從而能將該系統(tǒng)模式下的能耗降到最小。

圖3 時刻數(shù)與計算模式選擇

圖4表示的是時隙數(shù)從0到200逐步增加時，任務(wù)選擇計算模式變化的詳情。

圖4 時刻數(shù)與計算模式選擇詳

圖5 時刻數(shù)與隊列積壓程度

5.2 懲罰參數(shù)V對隊列積壓的影響

圖5表示懲罰參數(shù)V的值，對隊列積壓程度的影響。在同一個懲罰參數(shù)下，隨著時刻數(shù)的增加，其隊列積壓程度逐漸減少，意味著隊列越穩(wěn)定。在時隙0到200時，隊列的變化程度較大，這是由于剛開始，全局視野受限，隊列不穩(wěn)定，200之后逐步趨于平緩，是由于該算法下隊列逐步趨于穩(wěn)定，在圖中表現(xiàn)為隊列積壓程度趨于平緩。同時，若改變懲罰參數(shù)V的值，隨著V增加，隊列積壓程度也會增加。

5.3 懲罰參數(shù)V對能耗的影響

在圖6中，設(shè)置在其它條件不變，在改變懲罰參數(shù)V的情況下，能耗隨時刻數(shù)的變化情況。在0到200時刻，算法迭代初期時，隊列不夠穩(wěn)定，使得能耗變化地較快，在200時刻到400時刻之間，隨著時刻數(shù)的增加，隊列在趨于穩(wěn)定的過程中，其能耗增加且增加速率逐漸減小，在400時刻之后，由于隊列已達到相對穩(wěn)定狀態(tài)，則各部分能耗逐漸趨于穩(wěn)定。同時，比較在同一時刻，懲罰參數(shù)小時，能耗較小，隨著懲罰參數(shù)的增大，能耗也會逐漸增加，隨著隊列積壓程度逐漸趨于穩(wěn)定，該系統(tǒng)的能耗也逐漸趨于穩(wěn)定。綜上，懲罰參數(shù)V的增大會影響能耗的增加。

圖6 控制參數(shù)與能耗

5.4 本算法與其它算法相比較

將本文所提的基于李雅普諾夫優(yōu)化的動態(tài)計算方法與本地執(zhí)行、邊緣服務(wù)器執(zhí)行、資源隨機分配的算法相比較。由圖7可知，在其它條件均相同的前提下，0到200時刻時，各種算法執(zhí)行的能耗依次增加的速率較大，在200時刻到400時刻時，能耗增加的速率逐漸減少，但仍在不斷增加，在400時刻之后，能耗逐漸趨于平穩(wěn)。在此圖中，可以了解到不同的算法得到的最小能耗不同。其中，在同一時刻，本文所提算法產(chǎn)生的能耗最小。

圖7 本算法與其它算法比較

6 結(jié)束語

本文針對物聯(lián)網(wǎng)終端設(shè)備計算資源有限的情況下，為提高物聯(lián)網(wǎng)終端設(shè)備對待處理任務(wù)的處理效率，研究將其卸載至邊緣服務(wù)器時的時延和能耗問題?？紤]在單邊緣服務(wù)器單物聯(lián)網(wǎng)設(shè)備的情況下，任務(wù)卸載至邊緣服務(wù)器可能會在邊緣服務(wù)器端產(chǎn)生卸載任務(wù)的隊列積壓問題，從而可能影響任務(wù)處理時延賀系統(tǒng)能耗的問題，基于此，提出了基于李雅普諾夫優(yōu)化的動態(tài)計算方法，同時建立基于李雅普諾夫優(yōu)化的函數(shù)模型，然后將原問題分解為兩個子問題：①當(dāng)任務(wù)選擇在本地執(zhí)行時，在此處求解終端設(shè)備的最優(yōu)CPU頻率；②當(dāng)任務(wù)選擇在邊緣服務(wù)器執(zhí)行時，可得到最優(yōu)的傳輸功率。最后利用李雅普諾夫優(yōu)化的漂移加罰函數(shù)，建立聯(lián)合的計算卸載和資源分配算法，通過調(diào)整卸載決策、計算頻率和傳輸功率，求得最優(yōu)的卸載決策和資源分配方案。實驗結(jié)果顯示：在本文算法中，該算法在不同的參數(shù)設(shè)置上有不同的靈敏性；相比于其它算法，本文算法在計算卸載和資源分配上，能得到較小的能耗，從而驗證了本算法的有效性。