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

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

0 引 言

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

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

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

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

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

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

1 系統(tǒng)模型

1.1 任務(wù)模型

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

圖2 系統(tǒng)模型

(1)

1.2 計算模型

1.2.1卸載計算模型

(2)

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

(3)

(4)

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

(5)

t時隙單個IMDs的卸載能耗為：

(6)

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

(7)

1.2.2本地計算模型

(8)

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

(9)

t時隙單個IMDs的本地計算能耗為:

(10)

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

(11)

1.3 能量收集(EH)模型

(12)

(13)

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

(14)

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

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

(15)

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

(16)

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

(17)

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

(18)

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

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

(19)

(20)

(21)

(22)

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

2 MAEE算法

圖3 MAEE算法流程

2.1 Lyapunov優(yōu)化

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

(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ā)式算法，在每個時隙內(nèi)根據(jù)設(shè)備電池電量和信道狀態(tài)等因素，分步求解單時隙內(nèi)最優(yōu)的卸載決策。當電量不足時，最大化系統(tǒng)能量效率，當電量充足時引入貪心策略，兼顧系統(tǒng)的時延與能量效率。

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

(26)

(27)

(28)

(29)

(30)

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

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

2.接受任務(wù)請求，提取請求中任務(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 實驗結(jié)果與分析

3.1 實驗配置

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

表1 實驗基本參數(shù)

3.2 結(jié)果分析

將本文算法與以下四種算法進行能效比較:

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

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

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

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

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

圖4 多個IMDs電量隨著時隙變化的曲線圖

3.2.1時延性能比較

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

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

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

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

3.2.2能效性能比較

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

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

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

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

4 結(jié) 語

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