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

(四川師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院，四川 成都 610101)

0 引 言

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

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

1 相關(guān)研究

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

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

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

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

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

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

2.2 系統(tǒng)模型

圖2 系統(tǒng)模型

2.3 計(jì)算模型

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

(1)本地計(jì)算模型

(1)

(2)

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

(2)卸載計(jì)算模型

(3)

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

(4)

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

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

(5)

(6)

(7)

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

(8)

(9)

(10)

s.t.

(11)

(12)

(13)

(14)

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

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

3 算法設(shè)計(jì)

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

3.1 離散二進(jìn)制粒子群算法

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

BPSO的速度更新公式為

(15)

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

(16)

位置變化的概率可表示為

(17)

3.2 模擬退火算法

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

3.3 改進(jìn)的混合離散二進(jìn)制粒子群算法

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

圖3 算法流程

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

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

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

(18)

(19)

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

(20)

(21)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

6 結(jié)束語

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