綠色能源驅動的移動邊緣計算動態任務卸載

馬惠榮 陳 旭 周 知 于 帥

(中山大學數據科學與計算機學院 廣州 510006)mahr3@mail2.sysu.edu.cn)

隨著移動通信技術的空前發展(如5 G)，移動設備的數量呈爆炸式增長，預計數十億物聯網(Internet of things, IoT)設備[1](如移動設備、可穿戴設備、傳感器等計算節點)將通過蜂窩網、低功耗廣域網等方式連接到互聯網.在這一背景下，各種各樣的IoT應用[2]應運而生，如車聯網、智能監控、增強現實[3]、智慧城市等，物聯網系統發展迅速[4].隨著IoT應用類型的不斷豐富、功能的日益強大，IoT設備將產生大量的中間數據，并且需要龐大的算力和能源以支撐相應的IoT服務.但在實際生活中，出于便攜的考慮，較小的移動設備受物理尺寸的限制難以提供足夠的資源以實現令人滿意的IoT服務.

為解決上述問題，任務卸載被廣泛認為是一種有效的任務處理方式.任務卸載是將數據處理任務從計算資源缺乏的、能量匱乏的IoT設備卸載到有充足計算資源和能量的計算結點，從而為IoT設備任務的執行提供更多可用的資源和能量.圍繞任務卸載學者們做了許多研究[5-6].傳統的移動云計算[7](mobile cloud computing, MCC)是將任務上傳到強大的云端服務器(例如Google公有云計算引擎)進行處理.大量實踐證明，移動云計算對具有中等時延容忍度的移動應用程序(例如個人云存儲服務)是非常有效的計算卸載方式[7].但對于新興的IoT應用來說，傳統的云計算模型是不適用的.一方面，如果將本地的IoT應用卸載至遠端的云服務器，海量中間數據的傳輸將對骨干網絡造成極大的負擔.此外，長距離的通信將導致網絡時延不穩定，難以達到時延敏感任務的要求(通常為幾十毫秒)，移動設備服務質量將會下降.

作為移動云計算模式的延伸，移動邊緣計算[8-10](mobile edge computing, MEC)被業界認為是一種很有前景的解決方案.在移動邊緣計算模式中，網絡邊緣設備(如基站、接入點和路由器)被賦予了計算和存儲能力，以代替云服務器提供服務.這種將遠端云的網絡資源下沉至網絡邊緣的方式，使得用戶可以近距離地使用邊緣節點的網絡資源.相比于移動云計算，移動邊緣計算不僅能夠極大地降低傳輸時延，還能夠避免因上傳大量數據而引起的骨干網絡擁塞.因此，近年來移動邊緣計算吸引了工業界[11]和學術界[12-13]的廣泛關注.

盡管MEC能夠有效降低IoT設備的能耗及網絡傳輸時延，邊緣服務器端的能效(power usage efficiency, PUE)卻是實現MEC可持續計算的瓶頸.具體而言，云服務器通常位于氣候和地理環境優越的農村地區，因而其PUE較高且容易獲得豐富的可再生能源，例如太陽能和風能.而邊緣服務器通常位于難以吸納可再生能源的城市與人群中心，因此使用電網電力.相比于云服務器，邊緣服務器的PUE更低，因此面臨著綠色可持續問題.

為了解決上述問題，本文利用信息和通信技術(information and communication technology, ICT)行業的2項技術.第1種是綠色能源收集(energy harvesting, EH)技術[14-15]，該技術使得設備能夠捕獲環境中可回收的能量，包括太陽能、風能以及人體運動能量[16]等綠色能源，從而促進電池的自我可持續性和不間斷運行.第2種是IoT設備間通信(device-to-device communication, D2D)[17-18]技術，該技術允許2個移動設備不經過基站就直接在設備之間進行高效通信.直觀上來說，將EH技術和D2D技術引入到MEC系統中，可以促進MEC系統可持續發展，并實現綠色計算(green computing)[19-21].特別是當執行任務的設備中綠色能源供應不足時，可以通過D2D技術將能耗較大的任務卸載到綠色能源供應充足的設備上執行.

因此，為了促進MEC系統的可持續發展并實現綠色計算，本文設計了一種基于能量收集(EH)技術和設備間通信(D2D)技術的綠色任務卸載框架，具體結構如圖1所示.此外本文還提出了一種高效的動態任務卸載策略，優化系統內任務執行所造成的邊緣服務器端電網電力能源成本及云服務器端云資源租用成本.圖1中，一個邊緣服務器服務范圍內有多個配備EH模塊的IoT設備，每個IoT設備可以與基站建立蜂窩鏈接，也可以與臨近其他IoT設備建立D2D鏈接，還可以通過基站與云服務器建立鏈接.本文中運營商可以針對不同IoT應用的類型和對時延的需求調整相應的任務執行策略以優化系統的服務性能：如為減少系統內總的任務執行成本，選擇本地端執行、卸載到其他設備端執行、卸載到邊緣服務器端執行，以及卸載到云服務器端執行.

Fig. 1 An illustration of the proposed architecture圖1 本文提出的架構的說明

在本文所提出框架中，每個IoT設備均能收集綠色能源儲存在設備的電池中，并將收集到的綠色能源作為IoT設備電池唯一的能量來源，這不僅可以為任務執行提供可持續的能源，還能延長電池的使用壽命.因而，本文假設任務在本地端執行和將任務卸載到其他IoT設備執行時在設備端所消耗的能源不計入系統內總的任務執行成本.系統總的任務執行成本主要由2部分構成：一部分是IoT設備將任務卸載到邊緣服務器端執行時，邊緣服務器為執行該任務所消耗的電網電力能源成本；另一部分是將IoT設備上時延不敏感的任務卸載到云端服務器執行時，云端服務器為執行該任務所產生的云資源租用成本.因此，本文以最小化系統內總的執行成本為優化目標.

本文的主要貢獻包括3個方面：

1) 本文框架中，引入D2D技術使得IoT設備之間可以動態、有益地共享計算和通信資源，這有助于在節約成本的同時提高能效.考慮到IoT設備的資源可能被其他設備過度使用(即某些設備向臨近設備大量卸載任務但極少接收臨近設備卸載過來的計算任務)，本文引入激勵約束，該約束確保一個IoT設備只有向其他設備提供足夠多的資源時才能使用其他IoT設備的計算資源.該約束不僅能夠有效防止設備資源被其他設備過度使用，還能夠有效促進設備間的協作.

2) 針對本文提出的優化問題，考慮到不同時間片各個設備EH模塊的緩存與設備所消耗的綠色能源之間的動態耦合性，以及設備任務特性和綠色能源到達等系統參數的隨機性和突發性，要想離線求解本文提出問題的最優解是極其困難的.因此，本文利用李雅普諾夫優化技術[22]提出了一種在線任務卸載算法.作為該算法的核心模塊，本文針對每個時間片設備任務的卸載執行情況設計了基于圖變換的任務卸載分配策略，該算法僅依賴系統的當前狀態信息，通過調用愛德蒙帶花樹算法[23]即可求得近似最優解.

3) 本文對所提出算法的性能進行了嚴格的理論分析，論證了系統最小化長期成本和隊列長度之間存在[O(1V),O(V)]的折中.實驗中通過與現有文獻中常見的4種任務卸載機制相比較，驗證了所提出算法的優越性能.通過調控參數V的值，本文評估了其對系統內總的任務執行成本和隊列積壓的影響，并驗證了本文所提出的在線任務卸載算法所得的系統執行成本可以接近離線最優的結果.通過對引入激勵約束參數的設置，有效驗證了本文提出激勵約束對系統任務執行成本節省率的有效性.

1 相關工作

在過去的幾年里，許多研究MEC的科研人員致力于解決計算效率的最大化和IoT設備能耗的最小化問題[24-29].文獻[24]主要研究聯合任務卸載和計算資源分配的MEC系統的能量效率最大化問題，提出一種計算效率指標，通過迭代和梯度下降方法解決了這一問題.文獻[25]提出了一種基于非正交多路訪問MEC環境的節能任務卸載算法，該算法確定了網絡鏈路的上行功率控制解決方案，解決了任務卸載劃分和時間分配問題.針對MEC服務器可以為IoT設備充電的任務卸載問題，文獻[26]提出了有時延約束的卸載算法，該算法能夠將能耗降至最低.文獻[27]以最小化IoT設備任務在基于正交頻分多址協議的上行網絡鏈路傳輸的能耗為目標，綜合使用計算分流、子載波分配和計算資源分配等3種優化策略來降低IoT設備能耗.文獻[28]提出了一種在無線電力傳輸環境中的IoT設備卸載調度算法，在此算法中，IoT設備會決定是在本地計算任務還是將任務卸載到MEC服務器進行計算.文獻[29]主要研究MEC和云服務器協同計算卸載，并針對MEC和云服務器環境提出了一種協同部分計算卸載算法.該文使用分支限界方法解決了單個MEC服務器的計算卸載問題，然后將其擴展到多個MEC服務器和云服務器場景中.針對多種場景，該文提出了一種迭代的啟發式MEC資源分配算法.上述研究[24-29]專注于IoT設備的能效，卻并未考慮利用能量收集技術為設備提供能源.

隨著綠色計算的提出和能量收集技術的進步，具有能量收集功能的MEC系統的研究受到了研究人員的極大關注[30-31].文獻[30]研究了能量收集MEC系統的聯合卸載和自動擴容問題.該文指出能量收集MEC可靠、高效運行的關鍵在于其前瞻性和適應性.為了在系統參數未知的情況下快速學習，該文利用問題的特殊結構，提出了一種基于PDS的強化學習算法來學習最優卸載和自動擴容策略.文獻[31]將可再生能源集成到MEC系統，提出了一種考慮MEC電池和服務體驗質量(QoE)的卸載調度算法.該文所提算法包括卸載請求的準入控制和MEC服務器頻率的計算.但是上述算法均不適用于本文提出的為每個IoT設備配備EH模塊，并對設備任務進行綠色任務卸載調度的情況.

當然，具有能量收集功能的IoT系統的研究也受到了很多研究人員的關注[32-34].文獻[32]提出了一種能量收集IoT設備根據電池電量確定卸載速率的基于強化學習的卸載算法.文獻[33]提出了一種著重于MEC服務器計算能力的動態計算卸載算法.該算法僅僅提及能量收集對延長網絡壽命的作用，并沒有將能量收集作為系統任務卸載調度的主要考慮方面.文獻[34]假設IoT設備具有能量收集模塊，并利用李雅普諾夫優化技術提出了一種IoT設備根據能量收集狀態決定其計算頻率的算法.然而，該文僅僅考慮了單個IoT設備任務的卸載調度情況，本文考慮了多個能夠利用綠色能源的IoT設備任務卸載調度情況.

在這些研究的基礎上，本文重點研究在邊緣系統中利用綠色能源的多個IoT設備任務的計算卸載調度問題.考慮為每個IoT設備配備EH模塊，同時利用D2D技術促進設備間的協作，充分利用各個設備的綠色能源，從而實現最小化任務執行所造成的邊緣服務器端電網電力能源成本和云服務器端云資源租用成本的優化目標.

2 系統模型與問題形式化

本文研究的框架模型如圖1所示，考慮一個邊緣服務器基站服務范圍內的一組IoT設備{Dev1,Dev2,…,DevN}，每個IoT設備Devi,i∈{1,2,…,N}既可以與基站建立蜂窩鏈路，也可以與臨近的IoT設備建立D2D鏈路，還可以通過基站與云服務器建立鏈接.本文考慮以時間片為單位運行，單位時間片t∈{t1,t2,…,tT}，且每一個任務都可以在單一時間片內完成.由于基站一般具有完整的網絡信息和較高的計算能力，本文考慮基站在每個時間片為IoT設備制定任務卸載策略的網絡輔助架構.

本文所提出框架中，每個IoT設備均配備EH模塊，該模塊能夠收集綠色能源并儲存在設備的電池中，這不僅可以為任務執行提供可持續的能源，還能延長電池的使用壽命.由于本文將收集到的綠色能源作為IoT設備電池唯一的能量來源，因而，本文假設設備任務在本地端執行和卸載到其他IoT設備執行所消耗的IoT設備的能源不計入系統的任務執行成本.因而，本文以最小化系統內的任務執行成本為優化目標，動態優化各個設備任務的執行模式.表1中列出了本文中主要符號及其意義.

Table 1 Main Notations and Their Meanings表1 主要符號及其意義

Continued (Table 1)

2.1 設備資源模型

1) 計算能力.一般來說，有許多種方法控制現代移動設備處理器的處理能力，例如隨需應變調控器(即通過DVFSD實時調整CPU的頻率)或性能調控器(即鎖定設備CPU的最大頻率).本文中，對每個IoT設備Devi,i∈{1,2,…,N}，定義Fi(t)為其CPU工作頻率，從而該設備總的計算能力即為Fi(t)(即單位時間內CPU周期的數目).此外，定義Yi(t)為設備當前的負載(即處理能力的占比).考慮到設備可能運行一些從后臺加載或者不能卸載的任務，設備閑置的計算能力可表示為ci(t)=(1-Yi(t))Fi(t).

需要強調的是，與蜂窩鏈路類似，上述與D2D鏈路相關的參數均是隨時間變化的，因而這些參數并不是本文的控制變量.此外，根據本文框架中設定的時間長度，基站可以在一個時間片內為每一個設備建立和維護一個或多個D2D鏈接.然而，考慮到系統內時間和資源的限制，本文參考FlashlinQ[35]，引入一個實用的相關性約束，即每個時間片內執行任務卸載期間每一個IoT設備允許最多建立和維護一個D2D鏈路.

2.2 云資源模型

為了進一步簡化任務執行的模式，本文假定運營商在網絡中部署一個云服務器.該云服務器由一組虛擬機{VM1,VM2,…,VMM}構成，其中每一個虛擬機VMi,i∈{1,2,…,M}都可以運行一個從IoT設備到來的任務.具體來說，時間片t內，IoT設備Devi,i∈{1,2,…,N}的任務將被分配給一個專用的虛擬機進行處理.本文定義ai(t)來表示相應的虛擬機是否激活，當ai(t)=1時虛擬機激活，反之虛擬機處于休眠狀態.

2.3 移動任務模型

為了描述IoT設備Devi,i∈{1,2,…,N}的任務特性，本文采用了一個參數元組Ii(t),Oi(t),Ci(t)，其中Ii(t)表示設備Devi上計算任務輸入數據的大小，Oi(t)表示計算任務輸出數據的大小，Ci(t)表示計算該任務所需要的計算資源(即CPU周期的數目).值得一提的是，通過在元組中引入其他的參數，任務的資源模型可以很容易地擴展到其他類型的資源(例如存儲資源).此外，為了描述一個任務是否是時延敏感的、能否卸載到云端服務器進行處理，本文定義0-1變量σi(t)來表示.當σi(t)=1時，表示設備Devi的任務可以卸載到云服務器端執行，反之，則表示該任務是時延敏感的任務，僅能卸載到設備本地端、其他設備端或者是邊緣服務器端執行，不能卸載到云服務器端執行.

2.4 任務執行模型

接下來，將介紹任務執行模型.正如引言所介紹的，為減少系統內總的任務執行成本，IoT設備Devi,i∈{1,2,…,N}可以選擇本地端執行、卸載到其他設備端執行、卸載到邊緣服務器端執行，以及卸載到云服務器端執行(設備任務對時延不敏感時).

2.5 任務分配決策

關于IoT設備的任務卸載問題，有以下一些約束.首先，定義0-1變量hi(t).其中hi(t)=1表示IoT設備Devi,i∈{1,2,…,N}在時間片t內有任務需要執行;反之，則表示設備Devi在時間片t內沒有要執行的任務.此外，本文對每一個設備Devi定義一個0-1向量xi(t)=(xi1(t),…,xi i(t),…,xiN(t),xie(t),xic(t))表示時間片t內所有任務的卸載決策.其中，xi j(t)=1表示設備Devi的任務卸載到設備Devj,j∈{1,2,…,N}上執行(當j=i時，任務即在本地移動端執行)，相應地，xi e(t)=1及xi c(t)=1分別表示將任務卸載到邊緣服務器端和云服務器端執行.此外，每一個時間片設備的任務都會被分配到一個且僅一個執行節點.為了描述不同時間設備之間鏈接的變化情況，本文引入一個隨時間變化的卸載圖G(t)=(Vex(t),E(t))，其中Vex(t)代表節點集合，E(t)代表圖中邊的集合.任務分配約束條件為

(1)

(2)

(3)

(4)

約束條件式(2)表示所有IoT設備的任務只能調度一次；約束條件式(3)表示由于IoT設備資源有限，在一輪任務卸載過程中，一個IoT設備最多只執行一個任務(可以是設備自己的任務，也可以是其他設備的任務)；約束條件式(4)表示：1)如果2個IoT設備都有任務要計算，并且它們之間建立了一個D2D鏈路來交換各自要執行的任務，則xi j(t)=xji(t)=1.這是很容易理解的，即在任務卸載過程中如果一對設備已經建立了D2D鏈接，它們就不能與其他IoT設備建立任何其他D2D鏈接.2)如果2個IoT設備都有任務要執行，但是它們不想在彼此之間建立D2D鏈接來交換執行任務，則設備Devi(設備Devj，類似地)可以在本地端執行任務，也可以將任務卸載到另一個IoT設備Devs執行，也可以將任務卸載到邊緣服務器端執行，對于時延不敏感的任務，還可以將任務卸載到云服務器端執行，即xi j(t)=xji(t)=0.換句話說，當hi(t)=1時，可以得到xji(t)=hj(t)xi j(t).

因而當每個IoT設備選擇不同的執行方式時，根據對設備端所消耗的綠色能源以及在邊緣服務器端產生的電力能源成本和云服務器端云資源租用成本建立的模型，任意IoT設備Devi,i∈{1,2,…,N}通過D2D鏈路將任務卸載至其他設備以及通過蜂窩鏈路將任務卸載至邊緣服務器或云服務器端執行所消耗的綠色能源可以表示為

和

相應地，IoT設備Devi在本地端執行任務所消耗的綠色能源和通過D2D鏈路幫助其他設備Devj,j∈{1,2,…,N}執行任務所消耗的綠色能源可以匯總為

那么，有任務需要執行的IoT設備Devi(也就是hi(t)=1的設備)在時間片t內消耗的綠色能源總和為

沒有任務執行的IoT設備Devi(也就是hi(t)=0)在時間片t內消耗的綠色能源為

綜上，IoT設備Devi在時間片t內消耗的綠色能源的總和為

為處理IoT設備Devi的任務，時間片t內邊緣服務器端產生的電網電力能源成本為

為處理IoT設備Devi的任務，時間片t內云服務器端產生的云資源租用成本為

2.6 綠色能量收集模型

本文假設每個IoT設備都配有一個EH模塊，該模塊由太陽能電池板、風力渦輪機、動能瓦片或它們的組合構成.由于自然界中綠色能源的可獲得量是隨機的和突發的，本文假設在給IoT設備供電前，EH模塊所收集的能量均被緩存在一個能量存儲電池中，以確保為設備提供持續的能源供應.此外，每一個EH模塊的充電和放電過程都是可以同時進行的.

Qi(t+1)=max[Qi(t)-Ei(t)+ri(t),0],

(5)

其中，ri(t)可以視作能量隊列Qi(t)中的“到達率”，而Ei(t)則可以視作能量隊列Qi(t)的“服務率”.

在式(5)中，IoT設備Devi中EH模塊收集到的儲存在電池中的綠色能源ri(t)受可用性約束

ri(t)∈[0,Ri(t)],

(6)

此外，還有

(7)

設備所消耗的綠色能源受電池能量約束

Ei(t)≤Qi(t).

(8)

由于電池容量有限，緩存的能量Qi(t)也應該滿足最大電池容量約束

(9)

需要強調的是，配備EH模塊的IoT設備的任務執行卸載調度策略比由電池驅動的移動邊緣計算系統的卸載調度策略要復雜得多.為了解決本文提出的綠色任務卸載調度問題，最直接的想法是通過對每個單獨的時間片進行漸進優化，進而實現最小化系統內總的任務執行成本的優化目標.然而，這種針對每個時間片的局部最優決策可能會影響到全局最優的決策.因為各個EH模塊的緩存與不同時間片各個設備所消耗的綠色能源是動態耦合的.因此，任何時間段的任務卸載調度和能量收集對未來邊緣服務器端所產生的電網電力能源成本和云服務器端云資源的租用成本的影響都是不可忽視的.此外，由于設備任務特性和綠色能源到達等系統參數具有隨機性和突發性，離線計算該調度問題的最優解是不切實際的.值得慶幸的是，本文在第4節提出了一種在線任務卸載算法.該算法僅依賴于系統的當前狀態信息，在每個時間片，通過求解一個圖匹配問題就能得到近似最優解.

3 問題建立

在上述框架的基礎上，本文提出了一種具有一系列必要約束條件的多個EH IoT設備任務執行的卸載調度問題.

3.1 激勵約束

由于IoT設備間進行協作時，存在某些設備向臨近設備大量卸載任務卻極少接收臨近設備卸載過來的計算任務的情況，這可能導致一些設備的資源被過度使用.為了防止IoT設備的資源被其他設備過度使用，并促進IoT設備間的協作，本文引入一個激勵約束.該約束確保一個IoT設備只有向其他設備提供足夠多的資源時才能使用其他IoT設備的計算資源.此外，系統還可以考慮將資源貢獻量作為設備的信用值，由系統中的基站來維護，并以每個IoT設備的信用值作為任務調度決策的重要參考因素，以此來促進設備間協作，防止資源的過度使用.

考慮到約束式(4)，進一步得到

(10)

(11)

此處，對每一個IoT設備Devi,i∈{1,2,…,N}，αi∈[0,1].

3.2 系統任務執行成本問題最小化

本節進一步描述多個配備EH模塊的IoT設備執行任務的卸載問題.本文所提綠色任務卸載框架的優化目標不再是最小化網絡中的能耗，而是最小化任務執行所造成的邊緣服務器端電網電力能源成本和云服務器端云資源租用成本，表示為

(12)

s.t.式(1)～(8)，式(10)，(11)成立.

其中，

4 在線算法設計

求解問題式(12)面臨的主要挑戰是需要知道系統未來不可預測的信息，例如可獲得的綠色能源、設備資源以及D2D鏈接的情況等.考慮到不同時間片內各個設備EH模塊的緩存與設備所消耗能源之間的動態耦合性，以及設備任務特性和綠色能源到達等系統參數的隨機性和突發性，離線求解最優解是不切實際的.因此，通過利用李雅普諾夫drift-plus-penalty方法[22]，本文設計了一個在線任務卸載算法.作為該算法的核心模塊，本文針對每個時間片設備任務卸載執行設計了基于圖變換的任務卸載分配策略，該算法僅依賴系統的當前狀態信息.

4.1 問題轉化

針對優化問題式(12)，本文制定了以下關鍵概念.

(13)

此外，本文還引入以下虛擬隊列來捕獲時間平均的激勵約束的變化：

特別地，本文先定義一個二次李雅普諾夫函數

(14)

此處Θ(t)表示本文系統中所有虛擬隊列和真實隊列積壓的向量.在李雅普諾夫函數[22]中，本文針對約束式(5)和式(13)引入廣泛用于保證隊列穩定性的L1，對激勵約束式(10)和式(11)引入廣泛用于保證隊列穩定性的L2.應該強調的是，虛擬隊列的負積壓沒有違反系統定義的時間平均約束，所以不需要考慮.

接著，定義one-slot李雅普諾夫drift-plus-penalty表達式：

其中，V是系統目標最優性和隊列穩定性之間的非負權衡參數(即本文所提框架對于最小化邊緣服務器端電網電力能源成本及云服務器端資源租用成本的重視程度).本文中第5節將會通過仿真來研究V值與系統性能之間的關系.就李雅普諾夫drift-plus-penalty表達式而言，式(12)可以被轉換為以下問題：

(15)

s.t.式(1)～(8)，式(13)成立.值得注意的是，此時平均時間約束式(10)和式(11)已包含在ΔΘ(t)中.

由于目標函數中包含的二次項很難處理，因此本文最小化目標函數的一個上界，該上界將在引理1中給出.

引理1.時間片t內，給定任務卸載決策x*(t)，以下不等式成立：

(16)

其中，

此處，F*在任何時間片都是一個常數，而f(t)不涉及任何系統內的調度因子.因而，在任務分配算法的設計中，本文不予考慮.由于頁面限制，具體的表述和詳細證明留至本文的在線技術報告中[38].

根據轉化后的問題和引理1，本文提出了滿足約束條件式(1)～(8),(13)情況下，使drift-plus-penalty上界(式(16)右側后4項)最小化的在線任務調度算法，并證明通過求解問題式(12)能夠獲得問題的近似最優解，且具有很好的性能.因此，本文提出的在線任務卸載算法的核心是解決下面的優化問題，使drift-plus-penalty上界最小化，即

(17)

s.t. 式(1)～(8)，式(13)成立.

算法1.在線任務卸載算法.

① for each time slott∈{t1,t2,…,tT}

② 調用最優任務卸載算法求每一個時刻的解x*(t)=arg min (Equ(17))；

③ 基于當前的卸載策略更新系統中的策略；

④ end for

算法1詳細描述了本文的在線卸載算法實現的過程.對每一個IoT設備，通過算法1第2步的求解，可以得到系統時間片t內所有任務調度決策的近似最優解，接著更新電池隊列以及2個虛擬隊列的積壓，以便下一時間片的任務卸載調度計算.該算法僅利用了當前時間片的系統信息和隊列積壓.不幸的是，由于其耦合性，該實時優化問題通常是NP難的.然而根據本文建模及約束條件，對每個有任務執行的IoT設備而言，其任務只能被分配到一個任務執行點(即本地移動執行、D2D卸載執行、邊緣服務器端卸載執行或云服務器端卸載執行).受任務卸載模式的啟發，本文設計了一個基于多個EH IoT設備的任務卸載問題的圖匹配方法，該方法能夠在滿足電池能量隊列長度的情況下，最大限度地降低系統內總的任務執行成本.

4.2 在線任務卸載算法

本文將求解每個時間片內算法1中的在線任務卸載算法的關鍵部分(即問題式(17))的近似最優解.針對式(17)中的任務卸載問題，本文提出一種圖匹配算法，該算法的關鍵在于圖結構的正確定義.具體而言，在D2D鏈接圖的基礎上構建系統最初的基本圖結構，然后通過以下步驟對基本圖進行修改：

1) 修剪節點.對于當前時間片中沒有任務要執行的IoT設備Devi，如果它的所有相鄰設備也都沒有任務需要執行，則刪除該設備節點Devi(例如，刪除圖2步驟1中的節點6)，因為設備Devi不會被分配任何任務.

2) 生成節點.對于一個有任務需要執行的IoT設備Devi(即hi(t)=1)，首先生成可以執行設備Devi的任務的設備節點(如節點2～4有任務需要執行，因此在圖2步驟2中生成5個白色節點1,2′,3′,4′和5).第2步生成虛擬邊緣節點，也就是用來表示設備Devi的任務可以在邊緣服務器端執行的節點(例如，節點2～4有任務需要執行，因此在圖2步驟2中生成了3個正方形的節點).第3步生成虛擬云節點，用來表示設備Devi的任務可以在云服務器端執行(例如，節點2～4有任務需要執行，其中節點3的任務是時延敏感的，不能卸載到云服務器端執行，即σ3(t)=0，因此，圖2步驟2中生成2個橢圓形的節點).

Fig. 2 Illustration of modelling the task offloading problem as weighted graph matching圖2 將任務卸載問題建模為加權圖匹配

3) 圖匹配.首先，需要得到表示設備任務卸載策略的圖UG(t)=(U(t)∪W，E(t)).具體而言，在圖2中，設備集合S={Dev2,Dev3,Dev4}是頂點集合，集合W表示所有可以執行任務的節點的集合，包括設備節點集合(即白色節點{node1,node2′,node3′,node4′,node5})、邊緣服務器端節點集合(即正方形節點{node2,node3,node4})、云服務器端節點集合(即橢圓形節點{node2,node4})，而E(t)={(Devi,nodej):ei j(t)=1,Devi∈S,nodej∈W,t∈{t1,t2,…,tT}}.這樣做，就得到了基本的連接圖(即圖2步驟3).其次，為了滿足約束式(3)，檢查集合U(t)中任意2個設備Devi和Devj之間是否存在邊ei j∈E(t)和eji∈E(t)，如果存在，就從圖UG(t)中刪除這條邊，并在集合U(t)中增加一條邊，該邊的權值為兩條邊的權重之和(如圖2步驟4所示).根據修改后的圖UG(t)，很容易證明問題式(17)的求解就是得到一個適應集合U(t)的最小權值匹配(即集合U(t)中所有設備在匹配中都有邊連接，如圖2步驟5所示).通過調用愛德蒙帶花樹算法[23]，即可求得每個時間片的圖匹配問題的解.基于上述圖匹配問題的解決方案，可以有效解決問題式(17)的求解.算法2總結了該求解過程.在4.3節中將證明本文所提出的在線任務卸載算法(算法1)長遠看是可以獲得卓越性能的，且該性能與離線優化的性能差距非常小.

算法2.最優任務卸載算法.

輸出：匹配x*(t).

① 對每一條邊ei j∈E(t) do

② 更新E(t)中邊ei j(t)的權重為-wi j(t)+ζ;

③ ifDevi∈U(t) &&Devj∈U(t) then

④ ifeji(t)∈E(t) then

⑤ 從集合E(t)中刪除ei j(t)和eji(t)兩條邊,并在集合U(t)中增加一條設備Devi到設備Devj的邊，權重為兩邊權重之和;

⑥ end if

⑦ else

⑧ 根據約束式(3)，將ei j從E(t)中刪除;

⑨ end if

⑩ 調用帶花樹算法求解UG(t).

4.3 性能分析

定理1.在線任務卸載算法中系統所有設備任務執行的平均時間成本、平均時間的真實隊列及虛擬隊列的積壓滿足

從定理1可以得知，通過調控參數V的值，本文提出的在線任務卸載算法求得的系統成本接近離線求解問題的結果.此外，時間平均的電池隊列積壓和虛擬隊列積壓也由參數V決定.簡而言之，本文提出的在線算法在最小化系統成本和限制隊列長度之間存在[O(1V),O(V)]的折中.

5 實驗結果

本節中將通過數值研究來評估本文所提出的在線任務卸載算法在降低系統任務執行成本方面的性能.表2給出了實驗中典型參數的詳細值.本文將所提出算法與4種機制相比較：

1) Naive edge and cloud execution strategy.即將所有設備的任務卸載到邊緣服務器端或者云服務器端進行處理.

2) Greedy execution strategy.即為每個設備的任務貪心地選擇本地端、D2D端、邊緣服務器端或者云服務器端進行處理.

3) Random execution strategy.即為每個設備的任務隨機選擇本地端、D2D端、邊緣服務器端或者云服務器端進行處理.

4) No energy harvesting strategy(No EH).每個設備的電池充電成本是計入系統總成本的，設備端有足夠電量時任務在本地端執行，否則卸載至邊緣服務器端或者云服務器端進行處理.

Table 2 Simulation Parameter Description and Setup表2 仿真參數描述及對應值設置

前3種機制中設備電池的配置與本文相同，均使用綠色能源為設備電池提供能源.實驗中以naive edge and cloud execution strategy作為系統任務執行成本節省率的基準.

1) 電池最大容量Qmax對系統性能的影響.從圖3中可以明顯看出隨著電池容量的增加，系統任務執行成本減少率動態增加，這驗證了在系統任務執行成本降低方面較大的電池容量可以為任務卸載的優化提供更多潛力的事實.

Fig. 3 Reduction ratio of costs vs control parameter V under different Qmax圖3 不同Qmax下的成本降低率與控制參數V

Fig. 4 Reduction ratio of costs vs control parameter V圖4 成本降低率與控制參數V

2)V值對系統性能的影響.圖4展示了不同的V值對于系統性能的影響.在李雅普諾夫優化理論[35]中，V是權衡目標函數最優性和隊列穩定性之間的參數.在本文提出的算法中，V用來權衡系統內總的任務執行成本和隊列的穩定性.V值越大，代表更多的關注系統任務執行成本的降低，而較少關注隊列的積壓狀況.通過設置不同的V值，本文評估了其對系統內總的任務執行成本和隊列積壓的影響.本文中，實驗結果與理論分析相符.分析實驗結果可以看出，隨著V值的增大，系統任務執行成本進一步降低，系統任務執行成本減少率增加，當V值增加到一定的值時，系統任務執行成本降低率會趨于平緩，這是因為此時系統任務執行成本降低率已經接近理論最優值.

從圖4可以看出，Greedy的選擇執行任務的模式所得到的系統任務執行成本降低率相比Random的選擇任務執行模式要高10%以上.這是因為Greedy策略是基于貪心選擇方法來選擇任務執行模式，會優先選擇系統任務執行成本最低的卸載策略，而Random策略不考慮這些，是隨機選擇各個任務的卸載方式，所以產生的系統內總的任務執行成本會高一些.與這些均能收集綠色能源的基準策略相比，本文提出的算法在系統總成本降低率方面確實有明顯的改進.具體而言，當控制參數V=5時，本文提出算法的性能提高了78.6%，明顯優于其他2種策略.

圖5將本文所提出利用綠色能量實現綠色任務卸載框架與沒有使用能量收集技術(即系統成本中包含每一時刻電池的充電成本)的卸載框架進行對比.從實驗結果來看，本文所提出算法遠遠優于不使用能量收集技術的方法.這是因為當設備的電池不能收集綠色能源時，電池的充電成本會計入系統總成本中，如果一直不對電池充電，則該種方法需要的成本和naive edge and cloud execution strategy大致一致，而當對電池進行充電時，所產生的系統總成本可能高于naive edge and cloud execution strategy的成本，也可能低于naive edge and cloud execution strategy的成本，這取決于仿真實驗對于設備充電成本的系數設置.本文實驗中，所提出算法是遠遠優于no energy harvesting strategy算法的.

Fig. 5 Reduction ratio of costs vs control parameter V圖5 不同控制參數V下本文算法的成本降低率的比較

實驗中，隨著V值的增加，系統隊列的變化情況如圖6所示.可以看出，V增加時，電池容量隊列和虛擬隊列均以近似線性的方式增加，這與定理1相符.因而，結合圖3可以得出，系統內總的任務執行成本性能和隊列變化服從[O(1V),O(V)]的權衡，這與理論分析相符.

Fig. 6 Sum of queue vs control parameter V圖6 隊列之和與控制參數V

從圖7可以看出，無論V值的大小，隊列的變化曲線都會隨著時間逐漸趨于穩定，這說明當電池最大容量一定時，本文提出的算法能夠為系統任務執行提供可持續的能源.

Fig. 7 Sum of all queue backlogs vs time slot圖7 所有隊列之和隨時間變化情況與控制參數V

3) 激勵約束參數對系統性能的影響.圖8描述了V=10時不同α值下系統任務執行成本節省率的變化.可以看到系統任務執行成本節省率隨著α的減少而增加.這是因為，根據本文提出激勵約束的定義，一個較小的α意味著設備在與其他設備協作時更加無私，更愿意在幫助其他設備的過程中犧牲更多的資源，其結果是，系統性能得到了改善.而當α的值較大時，意味著設備不愿意貢獻太多自己的資源，會限制其他設備使用自己的資源.本文其他實驗中，α的值均設置為0.5.

Fig. 8 Reduction ratio of costs vs control parameter V under different values of α圖8 不同激勵參數α下成本節省率與控制參數V

4) 設備數對系統性能的影響.設備數量對系統任務執行成本節省率的影響如圖9所示.可以看到隨著系統中設備數量的增多，本文提出算法的性能穩定優于其他2種算法(相比Greedy和Random策略，分別有超過10%和25%的系統任務執行成本節省率的提升).這些實現現象均表明本文提出的算法具有很好的擴展性，能夠很好地適應系統設備數量的變化.

Fig. 9 Reduction ratio of costs vs user amount under various online algorithms圖9 多種在線算法下的成本節省率與設備數量

6 總 結

為了提高MEC系統的PUE并實現綠色計算，本文提出了一種綠色任務卸載框架.該框架考慮多個配備EH模塊的IoT設備任務的卸載調度問題，旨在最小化任務執行所造成的邊緣服務器端電網電力能源成本和云服務器端云資源租用成本.在系統中，IoT設備通過關聯到最合適的基站，可以將任務卸載到本地端、其他設備端、邊緣服務器端以及云服務器端執行.為有效促進設備間的協作，并防止設備資源被其他設備過度使用，本文引入激勵約束，該約束確保一個IoT設備只有向其他設備提供足夠多的資源時才能使用其他IoT設備的計算資源.考慮到系統未來信息的不確定性，例如綠色能源的可獲得性，本文利用李雅普諾夫優化技術提出了一種在線任務卸載算法.作為該算法的核心模塊，本文針對每個時間片設備任務卸載執行情況設計了基于圖變換的任務卸載分配策略，該算法僅依賴系統的當前狀態信息，通過調用愛德蒙帶花樹算法即可求得近似最優解.嚴格的理論分析和充分的實驗均驗證了本文所提出框架的優越性能.