楊錦霞，郭榮佐，陳芳瑩

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

0 引 言

移動(dòng)邊緣計(jì)算(mobile edge computing，MEC)作為5G通信的主要應(yīng)用之一，在更靠近數(shù)據(jù)源的網(wǎng)絡(luò)邊緣為物聯(lián)網(wǎng)設(shè)備提供低延遲計(jì)算和通信服務(wù)，能夠有效緩解物聯(lián)網(wǎng)終端設(shè)備自身能力不足的問(wèn)題[1,2]。在5G環(huán)境下，MEC的任務(wù)處理時(shí)延占整個(gè)卸載時(shí)延的最大比例[3]。合理分配有限的計(jì)算資源對(duì)卸載性能有著至關(guān)重要的影響。因此，研究MEC構(gòu)成的物聯(lián)網(wǎng)的資源分配與計(jì)算卸載的系統(tǒng)效益問(wèn)題，對(duì)提高物聯(lián)網(wǎng)邊緣計(jì)算的服務(wù)質(zhì)量(quality of service，QoS)是十分必要的。

針對(duì)計(jì)算資源分配問(wèn)題Zhang等[4]提出了一個(gè)高效的移動(dòng)邊緣云計(jì)算網(wǎng)絡(luò)框架，通過(guò)最優(yōu)定價(jià)和云計(jì)算資源管理實(shí)現(xiàn)MEC和云的利潤(rùn)最大化。該文聯(lián)合移動(dòng)云計(jì)算有效緩解計(jì)算資源不足的問(wèn)題，但是沒(méi)有考慮用戶卸載效益。Ning等[5]分別研究了單用戶和多用戶場(chǎng)景下的計(jì)算資源分配問(wèn)題，設(shè)計(jì)了一種迭代啟發(fā)式MEC資源分配算法，以動(dòng)態(tài)地做出卸載決策。針對(duì)計(jì)算卸載與資源分配聯(lián)合優(yōu)化問(wèn)題Wang等[6]提出了一個(gè)多層數(shù)據(jù)流處理系統(tǒng)，將任務(wù)分配到多個(gè)層次處理。Kiran等[7]構(gòu)建了一種新的MEC軟件定義邊緣云框架，提出了基于強(qiáng)化學(xué)習(xí)算法的方案來(lái)解決計(jì)算卸載與資源分配問(wèn)題。

綜上所述，這些研究都是非常有意義的，為進(jìn)一步研究物聯(lián)網(wǎng)邊緣計(jì)算的計(jì)算卸載決策與計(jì)算資源分配的聯(lián)合優(yōu)化奠定了堅(jiān)實(shí)基礎(chǔ)。首先構(gòu)建了系統(tǒng)卸載效益模型，提出了保證效益為正的最小計(jì)算資源分配閾值，將問(wèn)題轉(zhuǎn)化為帶約束的系統(tǒng)卸載效益最大化問(wèn)題，并利用罰函數(shù)解決約束問(wèn)題。其次引入了遺傳算法優(yōu)化(genetic algorithm optimization，GAO)，為了適應(yīng)問(wèn)題設(shè)計(jì)了一種兩段式染色體結(jié)構(gòu)和遺傳算子。最后進(jìn)行仿真實(shí)驗(yàn)，對(duì)比分析了隨機(jī)卸載決策和平均計(jì)算資源分配、全部卸載決策和隨機(jī)計(jì)算資源分配等4種策略，GAO無(wú)論是在時(shí)延還是能耗均優(yōu)于其它方案。同時(shí)還分析得出算法在傳輸功率、設(shè)備數(shù)量等重要參數(shù)下均具有較好的靈敏性。

1 系統(tǒng)模型

1.1 系統(tǒng)概述

如圖1所示，考慮一個(gè)資源受限的小型移動(dòng)邊緣計(jì)算卸載系統(tǒng)，該系統(tǒng)有多個(gè)移動(dòng)智能設(shè)備(smart mobile device，SMD)和一個(gè)MEC服務(wù)器(mobile edge computing server，MECS)。MECS部署在微蜂窩基站上，基站與MECS通過(guò)高帶寬有線直接相連，為用戶提供計(jì)算服務(wù)[8]。設(shè)備通過(guò)無(wú)線的方式與基站進(jìn)行交互，只有在可以建立無(wú)線連接的情況下，移動(dòng)設(shè)備才能訪問(wèn)服務(wù)器。假設(shè)在任意時(shí)隙，SMD都有一個(gè)計(jì)算密集型任務(wù)待處理，且任務(wù)都具備可分割性，可以部分在本地處理，部分在MECS上處理。MEC服務(wù)器可以動(dòng)態(tài)地分配其計(jì)算資源來(lái)執(zhí)行從不同的SMD卸載的任務(wù)。同時(shí)考慮一個(gè)準(zhǔn)靜態(tài)信道模型，即信道的狀態(tài)在各個(gè)卸載階段保持不變，且一旦開(kāi)始卸載，用戶將無(wú)法停止直到整個(gè)卸載完成[9]。

為了方便分析，設(shè)系統(tǒng)有K個(gè)移動(dòng)智能設(shè)備，K=[1,2,…,k]， 每個(gè)用戶的SMD用一個(gè)二元組Dk={fk,Pk} 來(lái)描述。其中fk， cycles/s表示SMDk的計(jì)算能力，Pk表示卸載任務(wù)時(shí)的傳輸功率；類似的，每個(gè)任務(wù)用一個(gè)三元組τk={dk,ck,ok} 來(lái)刻畫(huà)。其中dk， bits表示SMDk的任務(wù)數(shù)據(jù)總量，ck表示計(jì)算任務(wù)1 bit數(shù)據(jù)需要花費(fèi)的CPU周期個(gè)數(shù)，ok∈[0,1] 表任務(wù)卸載比例。任務(wù)執(zhí)行的時(shí)延由本地計(jì)算時(shí)延、傳輸時(shí)延以及MECS端計(jì)算時(shí)延3部分組成。由于MECS有持續(xù)不斷的供電電源，因此不考慮服務(wù)器端的能耗，則能耗僅包含本地執(zhí)行能耗和數(shù)據(jù)卸載的傳輸能耗兩部分。

圖1 多用戶MEC系統(tǒng)

1.2 通信模型

計(jì)算卸載過(guò)程可以簡(jiǎn)單描述為：SMD將輸入數(shù)據(jù)由上行鏈路傳輸?shù)組ECS，MECS執(zhí)行計(jì)算，計(jì)算完成后再將計(jì)算結(jié)果由下行鏈路傳回到SMD上。計(jì)算卸載過(guò)程產(chǎn)生額外的傳輸時(shí)延和能耗是影響用戶QoS的重要因素，而傳輸時(shí)延和傳輸能耗受數(shù)據(jù)傳輸速率的影響。

設(shè)移動(dòng)運(yùn)營(yíng)商提供的總帶寬為B， MHz，系統(tǒng)的上行鏈路采用正交頻分多址(orthogonal frequency division multiple access，OFDMA)技術(shù)，總通信頻帶均分為K個(gè)帶寬為B/K， MHz的正交子頻帶。為減少傳輸?shù)男诺栏蓴_，每個(gè)用戶在卸載周期內(nèi)分別占用不同的子頻帶。根據(jù)香農(nóng)公式可得出任務(wù)卸載到服務(wù)器的傳輸速率為

(1)

其中，Bk=B/K，Pk為傳輸功率，Gk為SMDk與基站之間上行鏈路的信道增益，σ2為背景噪聲功率。傳輸時(shí)延=傳輸?shù)臄?shù)據(jù)總量/傳輸速度，根據(jù)式(1)可得上行鏈路的傳輸時(shí)延為

(2)

傳輸過(guò)程中設(shè)備能量消耗=傳輸時(shí)間*傳輸功率，因此根據(jù)式(2)的傳輸時(shí)間可得上行鏈路任務(wù)的傳輸能耗為

(3)

其中，Ln是尾部能量，在數(shù)據(jù)傳輸完成之后會(huì)繼續(xù)保持信道狀態(tài)一段時(shí)間，這種尾能量現(xiàn)象在移動(dòng)蜂窩網(wǎng)絡(luò)中普遍存在[10]。

1.3 本地計(jì)算模型

任務(wù)在本地執(zhí)行產(chǎn)生的時(shí)延可以表示為

(4)

CPU每周期能量消耗模型E=?f2， ?是與CPU芯片結(jié)構(gòu)相關(guān)的能量消耗系數(shù)，f， cycles/s是CPU計(jì)算頻率[11]。則任務(wù)在本地執(zhí)行消耗的能量可以表示為

(5)

1.4 MECS計(jì)算模型

(6)

由于每個(gè)用戶計(jì)算的數(shù)據(jù)量以及其它參數(shù)之間的差異，MECS應(yīng)該給每個(gè)任務(wù)分配不同數(shù)量的計(jì)算資源。一般來(lái)說(shuō)，計(jì)算結(jié)果的大小遠(yuǎn)小于輸入數(shù)據(jù)，下行鏈路的數(shù)據(jù)傳輸速率也遠(yuǎn)遠(yuǎn)大于上行鏈路。因此，不考慮計(jì)算結(jié)果回傳的時(shí)延[14,15]。

MEC服務(wù)器由某個(gè)運(yùn)營(yíng)商操作和維護(hù)，將從提供計(jì)算卸載服務(wù)中收取一定的費(fèi)用[16]。設(shè)用戶租用MEC服務(wù)器計(jì)算資源的代價(jià)為線性函數(shù)cost=αx+β， 其中α≥0，β為代價(jià)函數(shù)系數(shù)，為了便于分析，令β=0。 則SMDk租用計(jì)算資源的代價(jià)costk為

costk=αfk

(7)

1.5 卸載實(shí)體

卸載產(chǎn)生的總時(shí)延Tk為本地執(zhí)行時(shí)延、傳輸時(shí)延和MEC服務(wù)器計(jì)算時(shí)延之和

(8)

由式(2)、式(4)、式(6)可得SMDk的整體時(shí)延開(kāi)銷為

(9)

SMDk的總能耗為本地執(zhí)行能耗和傳輸能耗之和

(10)

由式(3)、式(5)可得SMDk的整體能耗為

(11)

計(jì)算卸載的目的是增強(qiáng)設(shè)備的計(jì)算能力從而滿足用戶的時(shí)延、能耗需求，此外卸載的費(fèi)用也影響著用戶的QoS。因此將卸載問(wèn)題轉(zhuǎn)化為聯(lián)合卸載時(shí)延效益、能耗效益以及費(fèi)用的卸載效益最大化問(wèn)題。設(shè)SMDk的時(shí)延效益TRk為

(12)

類似的，能耗效益ERk為

(13)

Uk=ωtTRk+ωeERk+ωccostk

(14)

考慮到效益建模的靈活性，式中ωt、ωe、ωc分別表示時(shí)延效益、能耗效益及費(fèi)用的權(quán)重。通過(guò)設(shè)置權(quán)重可分別捕捉用戶在這3方面的偏好，以滿足用戶不同的需求。

1.6 問(wèn)題制定

(15)

(16)

C2表示每個(gè)用戶總卸載時(shí)延應(yīng)該小于完全本地計(jì)算的時(shí)延，以保證用戶卸載的有效性，避免計(jì)算資源的浪費(fèi)。由C2可進(jìn)行如下推導(dǎo)

2 基于改進(jìn)遺傳算法的問(wèn)題求解

問(wèn)題P1是一個(gè)混合整數(shù)非線性(mixed integer nonli-near programming，MINLP)問(wèn)題，難以用低復(fù)雜度算法求得全局最優(yōu)解。因此，為了便于實(shí)驗(yàn)實(shí)現(xiàn)，本文引入改進(jìn)的低復(fù)雜度遺傳算法對(duì)問(wèn)題求解。遺傳算法是一種模仿生物進(jìn)化論的啟發(fā)式算法，能很好的在有效性和復(fù)雜度之間取得平衡，為NP難問(wèn)題求得近似最優(yōu)解。每條染色體對(duì)應(yīng)問(wèn)題的一個(gè)可能解，為了簡(jiǎn)化編碼和解碼過(guò)程，采用實(shí)數(shù)編碼的方法初始化每條染色體。如圖2所示，設(shè)計(jì)一個(gè)兩段式的染色體，即每條染色體由兩組長(zhǎng)度均為K的基因序列OD和RA構(gòu)成，分別對(duì)應(yīng)K個(gè)設(shè)備的卸載決策和計(jì)算資源分配結(jié)果。

圖2 染色體結(jié)構(gòu)

遺傳算法的一般過(guò)程為初始化、個(gè)體適應(yīng)度評(píng)估、選擇、交叉、變異。下面將描述利用改進(jìn)的遺傳算法求解卸載效益最大化問(wèn)題的主要過(guò)程。

(1)初始化

(2)個(gè)體評(píng)估

初始化種群后，通過(guò)P1對(duì)每個(gè)個(gè)體進(jìn)行評(píng)估。由于該問(wèn)題含約束條件，可能存在違反約束條件的個(gè)體，稱這些個(gè)體為不可行解。為了解決約束限制，采用了罰函數(shù)求解約束優(yōu)化問(wèn)題的思想：可行解優(yōu)于不可行解，對(duì)不可行解進(jìn)行懲罰，為可行域提供搜索方向。定義如下罰函數(shù)

CV=CV1+CV2

(17)

(18)

(19)

CV1和CV2分別解決不等式約束C2、C3。適應(yīng)度值越大，個(gè)體越優(yōu)秀，則對(duì)于任意個(gè)體cn適應(yīng)度函數(shù)為

fit(cn)=U(cn)-λCV

(20)

λ為懲罰因子。

(3)選擇

采用輪盤(pán)賭選擇方法，該方法根據(jù)適應(yīng)度值大小對(duì)個(gè)體進(jìn)行選擇，適應(yīng)度值較大的優(yōu)秀個(gè)體，被選擇的概率也更大，從而保證優(yōu)秀個(gè)體能保留下來(lái)。首先根據(jù)式(20)計(jì)算出每個(gè)個(gè)體的適應(yīng)度值，再根據(jù)適應(yīng)度值計(jì)算每個(gè)個(gè)體的累積概率pn，pn對(duì)應(yīng)輪盤(pán)跨度，跨度越大，個(gè)體被選中的概率越大。pn的計(jì)算公式為

(21)

產(chǎn)生一個(gè)[0,1]之間的隨機(jī)數(shù)r，保留pn>r的第一個(gè)個(gè)體n。

(4)交叉

(22)

其中，β滿足以下的概率密度函數(shù)

(23)

式中：隨機(jī)數(shù)μ∈[0,1]，ηc為交叉分布指數(shù)。

圖3 交叉操作

(5)變異

這一步采用多項(xiàng)式變異算子來(lái)產(chǎn)生子代。首先產(chǎn)生一個(gè)[0,1]之間的隨機(jī)數(shù)pm， 若pm

(24)

式中：隨機(jī)數(shù)v∈[0,1]，ηm為變異分布指數(shù)，對(duì)于基因序列OD來(lái)說(shuō)xmax，xmin分別為卸載決策的最大值和最小值，對(duì)于基因序列RA來(lái)說(shuō)xmax，xmin則分別為資源分配的最大值和最小值。

圖4 變異操作

算法求解的具體過(guò)程見(jiàn)表1。

表1 基于改進(jìn)的GA算法的問(wèn)題求解

3 實(shí)驗(yàn)仿真與結(jié)果分析

3.1 實(shí)驗(yàn)設(shè)置

本節(jié)將通過(guò)Matlab R2017a仿真，參照已有文獻(xiàn)的參數(shù)設(shè)置模擬MEC系統(tǒng)，分析所提算法的性能。設(shè)定服務(wù)器的計(jì)算能力F=50 GHz，總帶寬B=20 MHz，移動(dòng)設(shè)備的個(gè)數(shù)N=20，設(shè)備輸入數(shù)據(jù)量dk為 [500,1000] kbi的隨機(jī)值，每bit數(shù)據(jù)的計(jì)算強(qiáng)度ck取值范圍為[500,100] cycles/bit。設(shè)備的計(jì)算能力fk為[0.5,2.0] GHz的隨機(jī)值，傳輸功率P=100 mW。設(shè)備與基站之間的信道增益Gk服從范圍[-50,30] dBm的隨機(jī)分布，噪聲功率譜密度-174 dBm/Hz。

3.2 權(quán)重設(shè)置分析

系統(tǒng)效益由時(shí)延效益、能耗效益和費(fèi)用3部分構(gòu)成，這3部分的量級(jí)各不相同，為了更好了解模型的各個(gè)組成部分對(duì)系統(tǒng)效益做出的貢獻(xiàn)，分析不同權(quán)重設(shè)置下的系統(tǒng)總效益。設(shè)置4種不同的權(quán)重：

編號(hào)1：ωt=1，ωe=1，ωc=1；

編號(hào)2：ωt=10，ωe=1，ωc=1；

編號(hào)3：ωt=1，ωe=10，ωc=1；

編號(hào)4：ωt=1，ωe=1，ωc=10。

編號(hào)1為基準(zhǔn)，編號(hào)2、編號(hào)3、編號(hào)4分別測(cè)試時(shí)延效益、能耗效益以及費(fèi)用對(duì)效益的貢獻(xiàn)，由圖5可知，能耗的貢獻(xiàn)最大，時(shí)延次之，費(fèi)用的變化最小。因此在分析不同參數(shù)對(duì)系統(tǒng)效益的影響時(shí)，需要選擇合適的權(quán)重設(shè)置。

圖5 不同權(quán)重設(shè)置下的系統(tǒng)總效益

3.3 算法收斂性能分析

圖6顯示出了種群規(guī)模大小對(duì)算法收斂速度的影響。隨著迭代次數(shù)的增加，不同的種群規(guī)模幾乎都能收斂到同一最優(yōu)值。此外，種群規(guī)模越大，收斂所需的迭代次數(shù)越少。當(dāng)個(gè)體為50時(shí)需要100次左右迭代才收斂，而個(gè)體數(shù)為100時(shí)收斂所需的迭代次數(shù)減少到75左右。當(dāng)個(gè)體數(shù)量為150和200時(shí)，收斂只需要50左右的迭代次數(shù)。因此，個(gè)體數(shù)設(shè)為100。

圖6 系統(tǒng)效益隨迭代次數(shù)的變化

3.4 計(jì)算資源分配策略對(duì)效益的影響

計(jì)算資源分配主要影響卸載時(shí)延，在該分析中設(shè)定時(shí)延效益為主要因素，選擇編號(hào)2的權(quán)重設(shè)置，令ωt=10。如圖7可知，計(jì)算資源分配對(duì)系統(tǒng)效益的影響十分明顯，GAO、隨機(jī)分配和均分3種資源分配策略均能收斂，但是GAO策略下的系統(tǒng)效益明顯高于其它兩種方案。這是由于各個(gè)設(shè)備的性能以及任務(wù)的復(fù)雜程度等各有差異，GAO能根據(jù)這些差異每次進(jìn)化都保留優(yōu)秀的個(gè)體，從而得到最佳的計(jì)算資源分配結(jié)果。

圖7 計(jì)算資源分配策略對(duì)效益的影響

3.5 設(shè)備數(shù)量對(duì)系統(tǒng)效益的影響

圖8顯示了不同策略下設(shè)備數(shù)量對(duì)系統(tǒng)平均效益的影響?？梢?jiàn)隨著設(shè)備數(shù)量的增多，系統(tǒng)平均效益減少，原因是邊緣服務(wù)器的計(jì)算資源是有限的，設(shè)備數(shù)量增多導(dǎo)致分配到的計(jì)算資源減少，MEC服務(wù)器端的處理時(shí)延增大，在本地執(zhí)行的數(shù)據(jù)量增多從而時(shí)延效益減少。GAO較其它4種方案減少的較為緩慢且效益值最高，能根據(jù)當(dāng)前的設(shè)備和服務(wù)器的計(jì)算資源進(jìn)行決策調(diào)整，做出最佳的策略。

圖8 設(shè)備數(shù)量對(duì)效益的影響

3.6 MECS計(jì)算資源總量對(duì)效益的影響

由于計(jì)算資源是影響時(shí)延效益的主要因素，為了便于分析，選擇編號(hào)2的權(quán)重設(shè)置，令ωt=10。從圖9可以看出，在5種不同方案下，系統(tǒng)效益均隨著計(jì)算資源的增加而增加。當(dāng)F較小時(shí)系統(tǒng)的平均效益很低，這是因?yàn)橛邢薜挠?jì)算資源無(wú)法支持大量設(shè)備的計(jì)算密集型任務(wù)，而當(dāng)F達(dá)到35左右后，效益迅速增加，這是因?yàn)檫@個(gè)值滿足了當(dāng)前設(shè)備數(shù)量下最低計(jì)算卸載資源量。對(duì)比其它4種策略，GAO方案下的系統(tǒng)效益值明顯高于其它方案。

圖9 MECS計(jì)算資源量對(duì)效益的影響

3.7 傳輸功率對(duì)效益的影響

傳輸功率影響能耗和上傳時(shí)延，而任務(wù)的上傳時(shí)延遠(yuǎn)小于任務(wù)在MEC服務(wù)器執(zhí)行的時(shí)延，因此設(shè)定能耗效益為主要因素，選擇編號(hào)3的權(quán)重設(shè)置，令ωt=10。分析圖10可以得知，傳輸功率越大系統(tǒng)效益越低，原因是傳輸功率增大，傳輸能耗增大，能耗效益減少。隨著功率均勻增加，總效益變化放緩，與其它參數(shù)相比，傳輸功率對(duì)系統(tǒng)總效益的影響較小。

圖10 傳輸功率對(duì)效益的影響

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

針對(duì)物聯(lián)網(wǎng)邊緣計(jì)算的計(jì)算卸載決策與計(jì)算資源分配的聯(lián)合優(yōu)化卸載效益并保證卸載的有益性，本文提出了以時(shí)延效益、能耗效益以及卸載費(fèi)用加權(quán)和的系統(tǒng)卸載效益這一概念，并將問(wèn)題轉(zhuǎn)化為系統(tǒng)效益最大化問(wèn)題。引入了針對(duì)該問(wèn)題改進(jìn)的遺傳算法，該算法不僅能在不同參數(shù)上有著很好的靈敏性，而且相對(duì)于其它卸載決策和資源分配方案能明顯提高系統(tǒng)的平均卸載效益。本文考慮的是單個(gè)MEC服務(wù)器的情況，未來(lái)可以考慮多個(gè)MEC服務(wù)器以及聯(lián)合計(jì)算資源更加豐富的云計(jì)算服務(wù)器。