物聯(lián)網(wǎng)邊緣計算卸載和資源分配關(guān)聯(lián)算法

衛(wèi)金菊，郭榮佐

(四川師范大學 計算機科學學院，四川 成都 610101)

0 引 言

隨著物聯(lián)網(wǎng)(internent of things，IoT)、無線通信技術(shù)等的發(fā)展，涌現(xiàn)出了大量新興智能IoT應用設(shè)備，使得物聯(lián)網(wǎng)終端設(shè)備需運行并處理大量的計算密集型數(shù)據(jù)，例如自動駕駛、人臉識別和自然語言處理等[1，2]對時延和能耗敏感要求較高的任務。基于物聯(lián)網(wǎng)終端設(shè)備的缺陷，其計算能力和電池續(xù)航能力等均有一定限度，難以有效處理這些要求低時延、低能耗的應用。同時，傳統(tǒng)云計算也難以處理爆炸式增長的邊緣數(shù)據(jù)[3]，因此學者提出了移動邊緣計算。移動邊緣計算的概念及相關(guān)定理由文獻[4]給出，將物聯(lián)網(wǎng)終端設(shè)備的待處理任務通過無線接入點(radio access network，RAN)或基站(base station，BS)遷移到移動網(wǎng)絡(luò)邊緣并進行處理的過程。其中RAN具有較強的存儲能力和計算能力，可為就近的移動物聯(lián)網(wǎng)終端設(shè)備提供服務及計算能力，從而能夠滿足5G網(wǎng)絡(luò)所需的低時延、低能耗、高可靠性及連續(xù)廣域覆蓋等需求[4]。

針對物聯(lián)網(wǎng)邊緣計算的能耗及時延的研究，主要通過卸載決策和資源分配等方式建立數(shù)學模型，對目標函數(shù)優(yōu)化模型進行求解。但對這類屬于NP-hard問題求解難度大。對此，本文提出了改進混合離散二進制粒子群算法(improve-BPSO)，該算法通過將離散二進制粒子群(binary particle swarm optimization algorithm，BPSO)與模擬退火算法(simulated annealing，SA)相結(jié)合，同時改進模擬退火算法中產(chǎn)生新算子的方法，提高了得到最優(yōu)卸載決策和資源分配的概率。

1 相關(guān)研究

針對卸載決策和資源分配的研究，已存在大量處理能耗和時延的方法。國內(nèi)外已有學者從多個角度提出了關(guān)于MEC的卸載決策和資源分配的解決方案[5-11]。在文獻[5]中，學者提出基于深度強化學習和深度確定性策略梯度的動態(tài)調(diào)度策略解決多移動終端設(shè)備MEC系統(tǒng)中的動態(tài)緩存、計算卸載和資源分配問題，從而能夠得到最小化成本函數(shù)的長期平均值。文獻[6]提出了一種基于深度強化學習算法的在線解決方案，處理非正交多址訪問的MEC網(wǎng)絡(luò)中計算卸載和資源分配的聯(lián)合優(yōu)化問題。文獻[7]中設(shè)計了一個有界改進分支有界算法來尋找全局最優(yōu)解同時提出了一種求解次優(yōu)解的組合算法，從而優(yōu)化計算卸載和資源分配。文獻[8]是在多智能體深度確定性策略梯度深度強化學習框架的動態(tài)通信環(huán)境下，提出了智能高效的資源分配和任務卸載決策算法及方案。文獻[9]研究多個移動服務需求在不同的工作流調(diào)度問題，提出了基于遺傳算法求解計算卸載方案。文獻[10]針對基于時分多路無源光網(wǎng)絡(luò)的移動邊緣計算，提出了一種最小化延遲和網(wǎng)絡(luò)部署聯(lián)合成本的最大線性規(guī)劃模型。文獻[11]提出以最大限度地提高全網(wǎng)頻譜效率和系統(tǒng)容量為目標的移動邊緣計算資源分配的最優(yōu)策略。但在單邊緣服務器多物聯(lián)網(wǎng)終端設(shè)備環(huán)境中基于邊緣服務器計算資源有限的研究，如何實現(xiàn)計算卸載和資源分配的聯(lián)合優(yōu)化使系統(tǒng)總成本最小，即實現(xiàn)時延的減少和能耗的降低是值得研究的問題。

綜上，針對物聯(lián)網(wǎng)邊緣計算卸載和資源分配求解時延和能耗的相關(guān)問題，在一個邊緣服務器多物聯(lián)網(wǎng)終端設(shè)備情景中、邊緣服務器計算資源有限的情況下，將該系統(tǒng)模型轉(zhuǎn)化為數(shù)學模型，提出聯(lián)合卸載決策和資源分配的策略，同時設(shè)計系統(tǒng)總成本(時延和能耗的加權(quán)和)最小的函數(shù)模型，在此基礎(chǔ)上采用改進混合離散二進制粒子群算法進行卸載決策研究，在該卸載決策下將原問題轉(zhuǎn)化為計算資源分配問題，然后根據(jù)拉格朗日乘子法及其理論求出計算資源的最優(yōu)解，最后，通過迭代可以求解出最優(yōu)的卸載決策和資源分配的結(jié)果，從而能夠降低系統(tǒng)總開銷，有效提升物聯(lián)網(wǎng)終端設(shè)備性能和服務質(zhì)量。

2 物聯(lián)網(wǎng)邊緣計算模型架構(gòu)、系統(tǒng)模型及問題描述

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

由于傳感器和移動智能設(shè)備等的顯著增加，將物聯(lián)網(wǎng)與邊緣計算結(jié)合，把集中式數(shù)據(jù)資源轉(zhuǎn)移到更靠近生成數(shù)據(jù)源的設(shè)備上，從而減少云計算的處理能力，以減少系統(tǒng)的延遲，提高物聯(lián)網(wǎng)終端設(shè)備的性能。物聯(lián)網(wǎng)邊緣計算架構(gòu)圖如圖1所示，該架構(gòu)圖主要由3部分組成：邊緣設(shè)備層、中間服務層及數(shù)據(jù)中心層。其中邊緣設(shè)備層是由兩部分組成：物聯(lián)網(wǎng)應用設(shè)備和感知設(shè)備，物聯(lián)網(wǎng)應用設(shè)備包括智能家居、綠色農(nóng)業(yè)、智慧醫(yī)療等，感知設(shè)備主要是通過傳感器等感知物聯(lián)網(wǎng)應用設(shè)備產(chǎn)生的數(shù)據(jù)，同時對數(shù)據(jù)進行收集和傳輸；中間服務層由無數(shù)個物聯(lián)網(wǎng)網(wǎng)關(guān)和其它服務器組成，這些服務器可以促進通信，減輕處理數(shù)據(jù)功能并推進邊緣服務器的操作同時還能對手機到的數(shù)據(jù)進行預處理，并將結(jié)果發(fā)送到數(shù)據(jù)中心。而預處理的作用主要是減輕帶寬的限制，并優(yōu)化轉(zhuǎn)發(fā)數(shù)據(jù)，最小化傳輸數(shù)據(jù)量和節(jié)省大量傳輸成本。數(shù)據(jù)中心主要由邊緣服務器等組成，邊緣服務器能處理物聯(lián)網(wǎng)終端設(shè)備終端的數(shù)據(jù)。

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

2.2 系統(tǒng)模型

圖2 系統(tǒng)模型

2.3 計算模型

設(shè)每個物聯(lián)網(wǎng)終端設(shè)備n有一個需要完成的且不可分割的計算密集型任務Un={Cn,Dn}，n∈[1,N]。 其中，Un表示第n個物聯(lián)網(wǎng)終端設(shè)備待處理任務信息的集合，Cn表示第n個物聯(lián)網(wǎng)終端設(shè)備請求的計算資源的數(shù)量，即完成任務Un的CPU周期總數(shù)，Dn表示第n個物聯(lián)網(wǎng)終端設(shè)備的處理任務的數(shù)據(jù)量大小。

(1)本地計算模型

(1)

(2)

其中，k表示能量因子，大小取決于CPU芯片工藝，本文將該值取值為k=10-27。 本文不考慮到fl隨著本地執(zhí)行時任務消耗的能耗的變化而變化，即fl設(shè)置為一個不變值。

(2)卸載計算模型

(3)

其中，Dn為計算Cn所需輸入數(shù)據(jù)的大小，rn為系統(tǒng)模型中無線信道中，物聯(lián)網(wǎng)終端設(shè)備n的上行鏈路速率。

(4)

其中，fcn是邊緣邊緣服務器分配給物聯(lián)網(wǎng)終端設(shè)備的計算資源。

設(shè)邊緣服務器最大計算資源為Fc， 由于邊緣服務器的計算資源有限，則約束條件應設(shè)為邊緣服務器的允許的最大計算資源Fc應大于等于邊緣服務器分配給卸載物聯(lián)網(wǎng)終端設(shè)備的計算資源的總和，可用表達式表示為

(5)

(6)

(7)

本文的目的是通過使用智能算法找到使出整個系統(tǒng)中所有物聯(lián)網(wǎng)終端設(shè)備的總成本(時延和能耗加權(quán)和)最小的卸載決策和資源分配的最優(yōu)解，則本文的最終優(yōu)化問題轉(zhuǎn)化為S=， 卸載決策XN={X1,X2,…,Xn}， 計算資源fc={fc1,fc2,…,fcn} 優(yōu)化目標函數(shù)G可以表述如下

(8)

(9)

(10)

s.t.

(11)

(12)

(13)

(14)

其中，C1表示用戶設(shè)備的卸載決策；C2表示邊緣服務器分配給卸載用戶設(shè)備的計算資源為正數(shù)；C3表示邊緣服務器分配給每個卸載用戶設(shè)備的計算資源的總和小于等于邊緣服務器的最大計算資源；C4中α、β是權(quán)重系數(shù)，表示對時延和能耗的權(quán)衡，若對時延敏感性應用，則取α的值大于β的值；若對設(shè)備能耗不足時，則取β的值大于α的值，本文研究時延和能耗同等重要，則取α與β均等于0.5。

基于上式(8)～式(14)的優(yōu)化函數(shù)及約束條件，其同時存在著整數(shù)約束和連續(xù)變量型，則該優(yōu)化問題屬于NP-hard問題。針對這一問題，本文將優(yōu)化目標問題分解為卸載決策和資源分配兩個問題，并通過智能算法進行求解。

3 算法設(shè)計

在本文所提模型中，卸載決策問題的本質(zhì)是0-1規(guī)劃為問題，故用離散二進制粒子群算法(BPSO)對卸載決策求解，但由于BPSO易陷入局部最優(yōu)，存在早熟早收斂等缺陷，為解決這一問題，引入了模擬退火算法(SA)，同時對SA中產(chǎn)生算子的方法改進，在SA中，設(shè)置一個較高的溫度作為初始值，該溫度按照一定的下降參數(shù)不斷下降，當算法中的某個解趨于穩(wěn)定時，可利用模擬退火算法具有以某個概率能跳出局部最優(yōu)的特點，可有效避免算法陷入局部最優(yōu)解，同時提高算法精度，從而找到卸載決策和資源分配的聯(lián)合最優(yōu)解。在應用improve-BPSO算法優(yōu)化系統(tǒng)總成本的問題時，主要思路是：①利用改進混合離散二進制粒子群算法 (improve-BPSO)制定卸載決策；②在更新卸載決策情況下，利用拉格朗日乘子法及其理論進行資源分配，計算適應度函數(shù)得出全局最優(yōu)和個體最優(yōu)；③隨機選擇個體最優(yōu)作為模擬退火的初始值，執(zhí)行模擬退火操作，其在降溫過程中，可概率性地接受不優(yōu)于當前解的新解，依次迭代，得到最優(yōu)解。

3.1 離散二進制粒子群算法

粒子群算法(particle swarm optimization，PSO)是一種基于全局搜索的智能算法[14]，其主要優(yōu)化目標是基于連續(xù)性計算的問題。BPSO于1997年由 James Kennedy和Russell C.Eberhart首次提出[15]，其主要優(yōu)化目標是基于離散空間約束的問題，BPSO是PSO的擴展和應用。下面給出BPSO的基本步驟：

BPSO的速度更新公式為

(15)

位置更新公式：利用sigmoid函數(shù)，計算粒子的速度映射到區(qū)間[0,1]的概率，并將該概率作為粒子下一步取值為1的概率

(16)

位置變化的概率可表示為

(17)

3.2 模擬退火算法

模擬退火算法(SA)由Metropolis在1953年首次提出[16]，同時在1983年首次提出SA可解決組合優(yōu)化的問題。本文所采用的模擬退火的基本思路是對當前解重復產(chǎn)生新解，計算適應度函數(shù)的差，判斷是否能接受的迭代過程與BPSO結(jié)合，從而找到最優(yōu)解，該算法具有概率性地跳出局部極值等優(yōu)點。

3.3 改進的混合離散二進制粒子群算法

在改進的混合離散二進制粒子群算法中，初始化粒子的速度和位置，確定全局最優(yōu)、個體最優(yōu)，同時更新速度和位置，計算適應度函數(shù)，更新粒子的個體最優(yōu)，然后隨機取出一個個體最優(yōu)，運用模擬退火算法，產(chǎn)生新的算子，進而得到更小的適應度函數(shù)，依次迭代，直至找到最優(yōu)解。圖3是該算法的流程。

圖3 算法流程

Improve-BPSO算法的流程圖。如圖3所示。

4 卸載用戶設(shè)備計算資源分配

通過上述改進混合離散二進制粒子群算法制定用戶的卸載決策后可得到用戶的卸載決策Xn， 由前文可知Xc表示卸載的任務的集合，則原目標問題可以簡化為

(18)

(19)

則資源分配minf由g(f) 決定，可以觀察到g(f) 的定義域為凸集，利用凸優(yōu)化判別式的二階條件，可證明目標函數(shù)g(f) 的Hessian矩陣是半正定的，可得到g(f) 為凸函數(shù)。在定義式(18)中不等式約束條件C1、C2下的拉格朗日函數(shù)表達式為

(20)

(21)

5 仿真實驗

通過MATLAB對本文所提算法進行仿真實驗，然后對其進行性能分析。在該仿真實驗中，設(shè)每個任務的數(shù)據(jù)量大小為Dn(單位:Kbits)服從 (300,500) 的均勻分布，且所需要的CPU周期數(shù)為Cn(單位:MHz)服從 (800,1200) 的均勻分布。邊緣服務器的計算能力Fc為15 GHz。設(shè)N個用戶設(shè)備的計算能力是相同的，其任務在本地處理的頻率fl均為0.8 GHz，任務卸載到邊緣服務器的上傳信道速率rn為2 Mbit/s，傳輸功率Pt為500 mw。為便于仿真實驗的對比和分析，設(shè)置如下對比方案，將改進混合離散二進制粒子群算法(improve-BPSO)與文獻[17]中模擬退火粒子群算法(PSOSA)、離散二進制粒子群算法(BPSO)、模擬退火算法(SA)、全部卸載(OFFLOAD)、全部本地(LOCAL)進行對比分析。

5.1 迭代次數(shù)對算法的影響

設(shè)終端用戶設(shè)備為20個，設(shè)種群數(shù)目為60，迭代次數(shù)從1遞增到100。由圖4可知，全部本地執(zhí)行(LOCAL)和全部卸載到邊緣服務器執(zhí)行(OFFLOAD)不會隨著迭代次數(shù)的增加而變化，但始終處于較高的數(shù)值處。由圖5知，其它幾種算法隨迭代次數(shù)的增加，其總成本數(shù)值逐漸遞減直至收斂，但總的來說，improve-BPSO算法的收斂速度最快且收斂效果最好。

圖4 迭代次數(shù)對系統(tǒng)總成本的影響

圖5 迭代次數(shù)對總成本影響的詳情

5.2 任務數(shù)量對算法的影響

本節(jié)任務數(shù)量從10到55以間距為5不斷增加，擬定迭代次數(shù)為100，比較6種算法在系統(tǒng)總成本上的差別。如表1所示，在這6種算法中，系統(tǒng)的總成本均隨著任務數(shù)量的增加而不斷增加，這是由于任務數(shù)據(jù)量的增加，導致系統(tǒng)需要更多的時延和能耗開銷，故系統(tǒng)的總成本會隨著任務數(shù)據(jù)的增加而增加。在同一任務數(shù)量下，但improve-BPSO與其它幾種算法相比，其總成本較低，則本文提出的improve-BPSO算法具有一定的優(yōu)勢。

5.3 任務周期數(shù)對算法的影響

假設(shè)任務數(shù)量為20，迭代次數(shù)為100次，比較任務周期數(shù)從800 MHz到1200 MHz以間距為100 MHz增加，對比分析在其它條件相同時，僅在不同任務周期數(shù)的情況下，各算法的系統(tǒng)總成本的大小，以及在同周期下不同算法中系統(tǒng)總成本的大小。如圖6所示，隨著周期數(shù)的增加，導致處理任務時的計算時延增加，從而使系統(tǒng)的總成本增加；在相同周期情況下，improve-BPSO算法系統(tǒng)總成本與其它幾種算法進行比較分析，可得出improve-BPSO算法的總成本低于其它幾種算法。

表1 不同任務數(shù)量對系統(tǒng)總成本的影響數(shù)據(jù)

圖6 周期數(shù)與總成本的關(guān)系

5.4 傳輸數(shù)據(jù)量對算法的影響

假設(shè)任務數(shù)量為20，迭代次數(shù)為100次，傳輸數(shù)據(jù)量從300 Kbits增加到500 Kbits以50 Kbits的間距增加，improve-BPSO算法與其余幾種算法進行對比。如圖7所示，隨著傳輸數(shù)據(jù)量的增加，系統(tǒng)總成本不斷增加，這是由于傳輸數(shù)據(jù)量增加時其任務的計算時延和能耗不斷增加，從而導致總成本在不斷增加。由圖7可知，在相同的傳輸數(shù)據(jù)量的情況下，improve-BPSO算法與其余幾種算法進行比較，可得出該算法的總成本略低。

圖7 傳輸數(shù)據(jù)量與總成本的關(guān)系

6 結(jié)束語

本文對物聯(lián)網(wǎng)邊緣計算卸載和資源分配的關(guān)聯(lián)算法研究，在單邊緣服務器多物聯(lián)網(wǎng)終端設(shè)備的場景中，邊緣服務器的計算資源有限的情況下，將邊緣計算卸載和資源分配策略關(guān)聯(lián)，提出以最小化系統(tǒng)總成本(時延和能耗的加權(quán)和)為優(yōu)化目標的函數(shù)模型。然后采用improve-BPSO算法制定卸載決策，并在該卸載決策下，將原問題轉(zhuǎn)化為計算資源分配的子問題，然后根據(jù)凸優(yōu)化及其理論，再利用拉格朗日乘子法求出計算資源分配的最優(yōu)解。實驗結(jié)果表明，該方案在迭代次數(shù)、任務數(shù)量、任務周期數(shù)及傳輸數(shù)據(jù)量方面均優(yōu)于BPSO、PSOSA、SA、LOCAL、ODDLOAD這5種算法。