物聯(lián)網(wǎng)邊緣計(jì)算中基于能量感知的動(dòng)態(tài)卸載算法

羅馨玥 李學(xué)華* 姚媛媛 岳新偉 云 翔

1(北京信息科技大學(xué)信息與通信工程學(xué)院 北京 100101) 2(北京佰才邦技術(shù)有限公司 北京 100085)

0 引 言

ZK Research的IoT設(shè)備發(fā)展預(yù)測(cè)數(shù)據(jù)顯示，到2025年，物聯(lián)網(wǎng)(Internet of Things,IoT)終端設(shè)備的連接將超過(guò)800億[1]。數(shù)以億計(jì)的物聯(lián)網(wǎng)移動(dòng)設(shè)備(Internet of Things Mobile Devices,IMDs)的管理和維護(hù)會(huì)給設(shè)備生產(chǎn)商、運(yùn)營(yíng)商帶來(lái)巨大的成本壓力[2]。傳統(tǒng)的IoT架構(gòu)如圖1所示，主要分為三層，分別是感知層、傳輸層和應(yīng)用層。其中，感知層由傳感器和感應(yīng)器件構(gòu)成整體感知網(wǎng)絡(luò)，結(jié)合云計(jì)算將海量的數(shù)據(jù)存儲(chǔ)到云節(jié)點(diǎn)，實(shí)現(xiàn)對(duì)環(huán)境的智能感知及記錄。傳輸層主要負(fù)責(zé)處理感知層獲取的海量信息并上傳至應(yīng)用層。應(yīng)用層將傳輸層的信息進(jìn)行分析并應(yīng)用于各個(gè)領(lǐng)域[3]。傳統(tǒng)的IoT架構(gòu)中感知層獲取的海量數(shù)據(jù)信息，其中一部分是高速率且時(shí)延敏感的，由于IoT能夠支持和提供的網(wǎng)絡(luò)帶寬、傳輸時(shí)延有限，IMDs的電池容量、節(jié)點(diǎn)處理能力受限，因此在基于云計(jì)算的IoT架構(gòu)中引入移動(dòng)邊緣計(jì)算(MEC)，將更多的數(shù)據(jù)計(jì)算和存儲(chǔ)從“核心”下沉到“邊緣”，部署MEC服務(wù)器于接近數(shù)據(jù)源的地方，大大降低傳輸時(shí)延和開(kāi)銷[4]。

圖1 傳統(tǒng)IoT架構(gòu)

計(jì)算卸載是MEC中關(guān)鍵技術(shù)之一，由終端設(shè)備將部分或全部計(jì)算任務(wù)交給邊緣節(jié)點(diǎn)處理。計(jì)算卸載技術(shù)主要包括卸載決策、資源分配和移動(dòng)性管理三個(gè)方面[5]。在多用戶的場(chǎng)景中，文獻(xiàn)[6]提出了一種計(jì)算卸載策略，該策略僅考慮計(jì)算資源分配，未涉及無(wú)線資源和計(jì)算資源聯(lián)合分配。文獻(xiàn)[7]通過(guò)控制發(fā)射功率和平衡負(fù)載，來(lái)優(yōu)化計(jì)算資源的分配。文獻(xiàn)[8]通過(guò)優(yōu)化帶寬分配，在多個(gè)設(shè)備的MEC系統(tǒng)中獲得最優(yōu)的無(wú)線資源分配方案。文獻(xiàn)[9]采用最優(yōu)化算法，通過(guò)最佳卸載決策與無(wú)線資源分配的共同執(zhí)行，聯(lián)合優(yōu)化系統(tǒng)的時(shí)延和能耗。文獻(xiàn)[10]采用啟發(fā)式算法，針對(duì)具有多個(gè)獨(dú)立任務(wù)的MEC系統(tǒng)共同優(yōu)化了任務(wù)卸載調(diào)度和傳輸功率分配，提高了能量效率。文獻(xiàn)[11]提出了一種感知用戶移動(dòng)性管理算法，降低了系統(tǒng)的時(shí)延?，F(xiàn)有物聯(lián)網(wǎng)邊緣計(jì)算中的計(jì)算卸載算法主要有最優(yōu)化算法及啟發(fā)式算法，以上文獻(xiàn)研究的性能指標(biāo)主要有時(shí)延、能耗、吞吐量、發(fā)射功率等，而已有研究較少涉及物聯(lián)網(wǎng)邊緣計(jì)算中系統(tǒng)能量效率和時(shí)延的聯(lián)合優(yōu)化。

雖然IMDs卸載高速率計(jì)算任務(wù)至MEC服務(wù)器可以減少處理時(shí)延，然而IMDs電池容量有限，可能出現(xiàn)由于電池耗盡中斷IMDs數(shù)據(jù)傳輸?shù)那闆r。為了解決上述問(wèn)題，相關(guān)學(xué)者將能量收集(Energy Harvest，EH)技術(shù)引入到通信系統(tǒng)中，IMDs配備EH裝置將收集的可再生能源轉(zhuǎn)換為直流供電，用于實(shí)現(xiàn)數(shù)據(jù)高效傳輸以及任務(wù)卸載，并提出了基于EH技術(shù)的計(jì)算卸載方法。文獻(xiàn)[12]捕獲環(huán)境可循環(huán)利用的能量，如太陽(yáng)能等，考慮單個(gè)移動(dòng)設(shè)備在MEC系統(tǒng)中的計(jì)算卸載問(wèn)題。文獻(xiàn)[13]從基站輻射的射頻信號(hào)中收集能量以用于單個(gè)移動(dòng)設(shè)備的任務(wù)處理。文獻(xiàn)[14]考慮具有EH的D2D輔助MEC系統(tǒng)，提出了一種協(xié)同卸載算法，該算法顯著提高了平均任務(wù)執(zhí)行成本。文獻(xiàn)[15]考慮收集太陽(yáng)能的單用戶MEC系統(tǒng)中計(jì)算資源分配問(wèn)題。文獻(xiàn)[16]考慮單個(gè)EH設(shè)備的MEC系統(tǒng)中平均任務(wù)處理時(shí)延的優(yōu)化。

但以上文獻(xiàn)考慮的都是單節(jié)點(diǎn)應(yīng)用EH技術(shù)的場(chǎng)景，暫未考慮基于EH的多IMDs與MEC系統(tǒng)下平均能效和時(shí)延兩項(xiàng)性能指標(biāo)的聯(lián)合優(yōu)化?，F(xiàn)有算法在多個(gè)移動(dòng)設(shè)備的MEC系統(tǒng)中，尚未考慮將移動(dòng)性管理、卸載決策和資源分配進(jìn)行聯(lián)合優(yōu)化的問(wèn)題，同時(shí)在節(jié)點(diǎn)能量資源受限的情況下，未能將系統(tǒng)的能效有效提升。因此本文考慮更切合實(shí)際場(chǎng)景的多IMDs隨機(jī)優(yōu)化問(wèn)題。該場(chǎng)景面向高速率IoT業(yè)務(wù)，多個(gè)IMDs配備EH裝置捕獲環(huán)境中的可再生能源轉(zhuǎn)換為直流供電。與傳統(tǒng)電池供電的設(shè)備相比，卸載決策更加復(fù)雜，不僅需要考慮時(shí)隙間用戶的移動(dòng)性管理、信道狀態(tài)信息和電量狀態(tài)信息，而且考慮在保證系統(tǒng)時(shí)延的前提下，提高系統(tǒng)的能量效率。

針對(duì)上述問(wèn)題，本文提出了最大化平均能效算法(MAEE)。該算法首先通過(guò)Lyapunov優(yōu)化將隨機(jī)優(yōu)化問(wèn)題轉(zhuǎn)化為每個(gè)時(shí)隙內(nèi)確定性問(wèn)題。然后為盡可能兼顧系統(tǒng)的時(shí)延和能量效率，提出基于貪心的卸載決策算法，在每個(gè)時(shí)隙內(nèi)根據(jù)設(shè)備電池電量和信道狀態(tài)等因素，分步求解單時(shí)隙內(nèi)最優(yōu)的卸載決策，當(dāng)電量充足時(shí)引入貪心策略，兼顧系統(tǒng)的時(shí)延與能量效率。實(shí)驗(yàn)結(jié)果表明，與傳統(tǒng)算法相比，本文提出的MAEE算法在保證時(shí)效性的同時(shí)，更大程度地提升了系統(tǒng)能量效率。

1 系統(tǒng)模型

1.1 任務(wù)模型

系統(tǒng)模型如圖2所示，該系統(tǒng)由多個(gè)配備EH裝置的IMDs和一個(gè)邊緣節(jié)點(diǎn)組成，其中邊緣節(jié)點(diǎn)部署于相應(yīng)的基站上，IMDs可通過(guò)連接的基站卸載計(jì)算任務(wù)至邊緣節(jié)點(diǎn)。

圖2 系統(tǒng)模型

(1)

1.2 計(jì)算模型

1.2.1卸載計(jì)算模型

(2)

根據(jù)香農(nóng)公式，單個(gè)IMDs執(zhí)行計(jì)算卸載的上行信息速率為：

(3)

(4)

t時(shí)隙所有執(zhí)行計(jì)算卸載的IMDs總時(shí)延為：

(5)

t時(shí)隙單個(gè)IMDs的卸載能耗為：

(6)

因此，t時(shí)隙所有執(zhí)行計(jì)算卸載的IMDs總能耗為：

(7)

1.2.2本地計(jì)算模型

(8)

t時(shí)隙所有執(zhí)行本地計(jì)算的IMDs總時(shí)延為：

(9)

t時(shí)隙單個(gè)IMDs的本地計(jì)算能耗為:

(10)

因此，t時(shí)隙所有執(zhí)行本地計(jì)算的IMDs總能耗為:

(11)

1.3 能量收集(EH)模型

(12)

(13)

式中：?(i，t)為t時(shí)隙消耗的電量。

(14)

1.4 系統(tǒng)平均能效

在時(shí)隙t內(nèi)，總的計(jì)算量為：

(15)

系統(tǒng)總能耗定義為t時(shí)隙內(nèi)所有IMDs執(zhí)行任務(wù)的能耗之和：

(16)

系統(tǒng)總時(shí)延定義為t時(shí)隙內(nèi)所有IMDs執(zhí)行任務(wù)的時(shí)延之和：

(17)

將能量效率定義為系統(tǒng)總計(jì)算量與總能耗的比值，則系統(tǒng)總能效為：

(18)

在最優(yōu)能量收集的情況下，最大化系統(tǒng)平均能效，故將總的優(yōu)化問(wèn)題描述為:

s.t. 式(1),式(3),式(12),式(13)

(19)

(20)

(21)

(22)

任務(wù)只能由執(zhí)行本地計(jì)算或者卸載計(jì)算，用于本地處理的CPU周期頻率小于IMDs的最大周期頻率，t時(shí)隙收集到的能量用于t+1時(shí)隙。式(19)是對(duì)每個(gè)時(shí)隙任務(wù)處理消耗的電量?(i，t)的約束；式(20)是對(duì)邊緣節(jié)點(diǎn)的無(wú)線資源約束，分配給每個(gè)任務(wù)的無(wú)線資源及分配給所有任務(wù)的無(wú)線帶寬資源不能超過(guò)無(wú)線上行鏈路的總帶寬；式(21)是對(duì)IMDs的無(wú)線資源約束，本地計(jì)算的CPU周期頻率不能超過(guò)最大CPU周期頻率；式(22)是對(duì)邊緣節(jié)點(diǎn)的計(jì)算資源約束，選擇卸載執(zhí)行的IMDs發(fā)射功率不能超過(guò)最大發(fā)射功率，因此聯(lián)合優(yōu)化無(wú)線資源和計(jì)算資源的優(yōu)化問(wèn)題為混合整數(shù)非線性規(guī)劃問(wèn)題。

2 MAEE算法

圖3 MAEE算法流程

2.1 Lyapunov優(yōu)化

考慮IMDs初始電量充足的情況，假定CPU周期頻率和發(fā)射功率僅取決于當(dāng)前時(shí)隙的狀態(tài)，t時(shí)隙內(nèi)的決定與歷史操作無(wú)關(guān)。Lyapunov優(yōu)化理論要求目標(biāo)方程的所有約束都為獨(dú)立同分布的，由于式(13)和式(14)，t時(shí)隙收集的電量用于t+1時(shí)隙，導(dǎo)致隨機(jī)優(yōu)化問(wèn)題在不同時(shí)隙卸載決策耦合，本文的EH模型不能滿足此要求條件，因此Lyapunov優(yōu)化理論不能直接應(yīng)用。為了解決該問(wèn)題，首先在IMDs中引入了擾動(dòng)參數(shù)和虛擬EH隊(duì)列。

(23)

生成Lyapunov函數(shù)：

(24)

Lyapunov漂移-懲罰函數(shù)：

ΔV(bt)=Δ(bt)-V·E[θ(t)|bt]t∈T

(25)

s.t. 式(1),式(3),式(12),式(13),式(19)-式(22)

s.t. 式(1),式(3),式(12),式(13),式(19)-式(22)

2.2 基于貪心的卸載決策算法

本文提出基于貪心的啟發(fā)式算法，在每個(gè)時(shí)隙內(nèi)根據(jù)設(shè)備電池電量和信道狀態(tài)等因素，分步求解單時(shí)隙內(nèi)最優(yōu)的卸載決策。當(dāng)電量不足時(shí)，最大化系統(tǒng)能量效率，當(dāng)電量充足時(shí)引入貪心策略，兼顧系統(tǒng)的時(shí)延與能量效率。

s.t. 式(1),式(3),式(12),(13),式(19)-式(22)

(26)

(27)

(28)

(29)

(30)

根據(jù)以上分析，本文提出的最大化平均能效算法詳細(xì)求解流程如算法1所示。

算法1最大化平均能效算法

2.接受任務(wù)請(qǐng)求，提取請(qǐng)求中任務(wù)信息；

3.for eachi∈{1,2,…,N} do；

6.引入貪婪策略，求最優(yōu)的卸載決策

7.Ifet-?(i,t)∈[Emin,Emax]

8.Ifρ≥ε

10.Else

12.Else

14.End for；

16.t=t+1；

17.End while

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

3.1 實(shí)驗(yàn)配置

利用MATLAB 2017進(jìn)行實(shí)驗(yàn)驗(yàn)證，實(shí)驗(yàn)平臺(tái)為AMD Ryzen 5 2600CPU 3.4 GHz,8 GB RAM，實(shí)驗(yàn)基本參數(shù)如表1所示。

表1 實(shí)驗(yàn)基本參數(shù)

3.2 結(jié)果分析

將本文算法與以下四種算法進(jìn)行能效比較:

(1) 全部本地處理：該算法僅本地處理所有任務(wù)，不進(jìn)行計(jì)算卸載。

(2) 全部卸載處理：該算法僅卸載至MEC服務(wù)器處理所有任務(wù)，不進(jìn)行本地處理。

(3) 基于貪心的動(dòng)態(tài)卸載處理：概率為ε時(shí)，以最大發(fā)射功率pmax卸載處理，概率為1-ε選擇時(shí)延低的處理模式。

(4) 優(yōu)化卸載算法(LODCO)[11]：電量充足時(shí)，發(fā)射功率pt為定值,選擇低成本能效處理模式，電量不足時(shí)，丟棄任務(wù)。

圖4為每個(gè)IMDs電量水平隨時(shí)隙變化的情況。每個(gè)IMDs的電量在初始階段不斷積累，最終維持在接近滿電量的水平上。在當(dāng)前參數(shù)下，每個(gè)IMDs的電池電量在第150個(gè)時(shí)隙后趨于穩(wěn)定。因?yàn)镸AEE算法在電池電量不充足時(shí)，會(huì)選擇能效最佳的執(zhí)行策略，減少每個(gè)時(shí)隙電池的消耗，從而使電量不斷累積增加。當(dāng)電量穩(wěn)定趨于滿電量時(shí)，MAEE算法會(huì)兼顧系統(tǒng)時(shí)延，會(huì)使電量在一定范圍內(nèi)上下波動(dòng)。

圖4 多個(gè)IMDs電量隨著時(shí)隙變化的曲線圖

3.2.1時(shí)延性能比較

圖5展現(xiàn)的是系統(tǒng)平均時(shí)延隨著貪心系數(shù)ε的變化趨勢(shì)。在電量充足時(shí)，不同的貪心系數(shù)會(huì)對(duì)算法的決策造成影響，從而影響系統(tǒng)的時(shí)延。在貪心系數(shù)較小接近于0時(shí)，系統(tǒng)選擇時(shí)延最佳模式的概率低，導(dǎo)致系統(tǒng)時(shí)延較高；隨著貪心系數(shù)的增大，系統(tǒng)以更大的比例選擇時(shí)延最佳的執(zhí)行模式,且可以看出貪心系數(shù)為0.7之后，時(shí)延的減少逐漸放緩，趨于穩(wěn)定。

圖5 貪心系數(shù)ε對(duì)時(shí)延的影響

時(shí)延隨時(shí)隙變化關(guān)系如圖6所示。由于本地處理的計(jì)算資源匱乏，與邊緣節(jié)點(diǎn)的計(jì)算資源有較大差距，因此全部本地處理的時(shí)延較大。全部卸載處理雖然可以利用MEC服務(wù)器計(jì)算資源快速處理任務(wù)，但是由于IMDs會(huì)在一定區(qū)域內(nèi)移動(dòng)，使卸載任務(wù)至邊緣節(jié)點(diǎn)的時(shí)間產(chǎn)生變化，導(dǎo)致時(shí)延在一定范圍內(nèi)上下波動(dòng)?；谪澬牡膭?dòng)態(tài)處理算法未能很好地優(yōu)化時(shí)延因素。LODCO算法主要考慮對(duì)時(shí)延的優(yōu)化，因此其在時(shí)延的表現(xiàn)上較好。MAEE算法在初始階段任務(wù)處理時(shí)延略大，隨著時(shí)間的推移，時(shí)延逐漸下降。這是因?yàn)镸AEE算法在初期電量不足時(shí)主要選擇能效最大化的執(zhí)行策略，未考慮對(duì)時(shí)延的優(yōu)化，而隨著時(shí)間推移，當(dāng)電量充足時(shí)MAEE算法開(kāi)始兼顧時(shí)延，使后段的時(shí)延逐漸下降。

圖6 時(shí)隙數(shù)對(duì)時(shí)延的影響

3.2.2能效性能比較

系統(tǒng)能量效率隨時(shí)隙變化關(guān)系如圖7所示，數(shù)據(jù)量設(shè)置為500 bit。全部本地處理時(shí)需要過(guò)多的本地CPU資源計(jì)算，導(dǎo)致能量效率較低。全部卸載處理時(shí)，僅需考慮任務(wù)卸載能耗，從而大大提升了能量效率，但考慮到任務(wù)卸載距離的變化，其能效表現(xiàn)會(huì)有一定的浮動(dòng)。LODCO和貪心算法會(huì)在卸載率和時(shí)延等因素上有所取舍，因此能效表現(xiàn)略差。MAEE算法在初期電量不足時(shí)會(huì)選擇能效最大化的策略，使其電量得到充分的利用，且隨著電量的不斷增加，其可處理的任務(wù)數(shù)量也會(huì)增加，從而提升了能量效率。當(dāng)電量積累到一定程度后，MAEE算法會(huì)在能效和時(shí)延之間進(jìn)行權(quán)衡，導(dǎo)致能效有一定程度的降低。

圖7 時(shí)隙數(shù)對(duì)平均能量效率的影響

圖8展現(xiàn)的是系統(tǒng)能量效率隨著計(jì)算數(shù)據(jù)量變化的關(guān)系。全部本地處理算法在任務(wù)數(shù)據(jù)量低的時(shí)候能量效率較高，實(shí)驗(yàn)結(jié)果表明對(duì)于小數(shù)據(jù)量任務(wù)，本地處理比卸載處理消耗的能量少，而隨著數(shù)據(jù)量的增加，本地處理的能耗呈指數(shù)型增加，因此其能效逐漸降低。全部卸載處理算法能耗僅在任務(wù)傳輸上，在小數(shù)據(jù)量時(shí)優(yōu)勢(shì)不明顯，但隨著數(shù)據(jù)量的增長(zhǎng)，其仍可使用較少的能量卸載任務(wù)，從而使能量效率不斷提升?；谪澬牡膭?dòng)態(tài)卸載算法和LODCO算法在卸載率和時(shí)延等因素上各有取舍，但在能效的優(yōu)化上不佳。本文提出的MAEE算法根據(jù)圖4可分為兩個(gè)階段，在前150個(gè)時(shí)隙內(nèi)，由于電量不足MAEE算法將選擇能效最大的方案，因此其能效表現(xiàn)最好，而當(dāng)電量充足時(shí)會(huì)在能效和時(shí)延之間進(jìn)行權(quán)衡，因此能效略有降低，但仍然保持在較高的水平上。

圖8 計(jì)算數(shù)據(jù)量對(duì)平均能量效率的影響

4 結(jié) 語(yǔ)

本文研究了MEC中多個(gè)IMDs之間的移動(dòng)性管理、能量收集、卸載決策和資源分配的聯(lián)合優(yōu)化問(wèn)題，提出一種最大化平均能效算法，即MAEE算法。該算法聯(lián)合統(tǒng)籌無(wú)線資源和計(jì)算資源分配，針對(duì)不同環(huán)境自適應(yīng)地進(jìn)行卸載決策，在降低系統(tǒng)時(shí)延的同時(shí)，最大化系統(tǒng)能量效率。實(shí)驗(yàn)結(jié)果表明，在多IMDs和大數(shù)據(jù)量任務(wù)的復(fù)雜環(huán)境中該算法能夠顯著提升能效，并降低任務(wù)處理時(shí)延。