物聯網邊緣計算中基于能量感知的動態卸載算法

羅馨玥 李學華* 姚媛媛 岳新偉 云 翔

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

0 引 言

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

圖1 傳統IoT架構

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

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

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

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

1 系統模型

1.1 任務模型

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

圖2 系統模型

(1)

1.2 計算模型

1.2.1卸載計算模型

(2)

根據香農公式，單個IMDs執行計算卸載的上行信息速率為：

(3)

(4)

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

(5)

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

(6)

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

(7)

1.2.2本地計算模型

(8)

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

(9)

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

(10)

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

(11)

1.3 能量收集(EH)模型

(12)

(13)

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

(14)

1.4 系統平均能效

在時隙t內，總的計算量為：

(15)

系統總能耗定義為t時隙內所有IMDs執行任務的能耗之和：

(16)

系統總時延定義為t時隙內所有IMDs執行任務的時延之和：

(17)

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

(18)

在最優能量收集的情況下，最大化系統平均能效，故將總的優化問題描述為:

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

(19)

(20)

(21)

(22)

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

2 MAEE算法

圖3 MAEE算法流程

2.1 Lyapunov優化

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

(23)

生成Lyapunov函數：

(24)

Lyapunov漂移-懲罰函數：

Δ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 基于貪心的卸載決策算法

本文提出基于貪心的啟發式算法，在每個時隙內根據設備電池電量和信道狀態等因素，分步求解單時隙內最優的卸載決策。當電量不足時，最大化系統能量效率，當電量充足時引入貪心策略，兼顧系統的時延與能量效率。

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

(26)

(27)

(28)

(29)

(30)

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

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

2.接受任務請求，提取請求中任務信息；

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

6.引入貪婪策略，求最優的卸載決策

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

8.Ifρ≥ε

10.Else

12.Else

14.End for；

16.t=t+1；

17.End while

3 實驗結果與分析

3.1 實驗配置

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

表1 實驗基本參數

3.2 結果分析

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

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

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

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

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

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

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

3.2.1時延性能比較

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

圖5 貪心系數ε對時延的影響

時延隨時隙變化關系如圖6所示。由于本地處理的計算資源匱乏，與邊緣節點的計算資源有較大差距，因此全部本地處理的時延較大。全部卸載處理雖然可以利用MEC服務器計算資源快速處理任務，但是由于IMDs會在一定區域內移動，使卸載任務至邊緣節點的時間產生變化，導致時延在一定范圍內上下波動?；谪澬牡膭討B處理算法未能很好地優化時延因素。LODCO算法主要考慮對時延的優化，因此其在時延的表現上較好。MAEE算法在初始階段任務處理時延略大，隨著時間的推移，時延逐漸下降。這是因為MAEE算法在初期電量不足時主要選擇能效最大化的執行策略，未考慮對時延的優化，而隨著時間推移，當電量充足時MAEE算法開始兼顧時延，使后段的時延逐漸下降。

圖6 時隙數對時延的影響

3.2.2能效性能比較

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

圖7 時隙數對平均能量效率的影響

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

圖8 計算數據量對平均能量效率的影響

4 結 語

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