移動Ad Hoc云中基于能量收集的分布式卸載方案研究

鮮永菊 郭陳榕 夏士超 李 云*

①(重慶郵電大學通信與信息工程學院 重慶 400065)

②(重慶郵電大學軟件工程學院 重慶 400065)

1 引言

在快速發(fā)展的物聯(lián)網(wǎng)技術驅動下，終端設備的數(shù)量和數(shù)據(jù)流量呈爆炸式增長，計算密集型和時延敏感型應用不斷興起，這對網(wǎng)絡的實時算力資源提出了更高的要求。另一方面?zhèn)鹘y(tǒng)終端設備的能量、帶寬和計算資源有限，難以滿足以大數(shù)據(jù)和智能化為特征的新興應用的實時計算需求及持久的續(xù)航能力。移動云計算和移動邊緣計算通過將計算任務卸載到云端處理的方式緩解了終端設備計算資源受限的問題，但邊緣算力不足以及分布不均衡的問題依然無法有效解決[1]。在一些網(wǎng)絡場景中沒有可用云服務器或本地微云，或因網(wǎng)絡擁塞造成計算任務不能被及時處理，難以有效地滿足用戶的業(yè)務體驗。

移動Ad Hoc云計算利用一組鄰近終端設備的空閑或過剩資源來協(xié)同處理網(wǎng)絡任務[2]。受體積和硬件成本的限制，傳統(tǒng)終端設備的電池容量難以滿足其長期續(xù)航的需求，尤其當設備分布在偏遠或有毒有害環(huán)境中時，難以通過可充電電池或傳統(tǒng)電網(wǎng)進行供電。能量收集(Energy Harvesting, EH)技術支持設備從環(huán)境中獲取可再生能源支撐其通信和任務處理，已成為實現(xiàn)綠色移動通信的重要技術[3,4]。因此，移動Ad Hoc云計算與EH技術融合對提高網(wǎng)絡計算性能具有重要意義。

近年來，移動Ad Hoc云計算的任務卸載問題得到了廣泛研究[5,6]。文獻[7]研究了移動Ad Hoc云環(huán)境中基于激勵機制的效用最大化問題，提出一種實時分布式算法鼓勵移動設備共享其空閑資源，使個體最優(yōu)與系統(tǒng)整體最優(yōu)相一致。為了激勵移動用戶參與異構移動云環(huán)境中的卸載服務，文獻[8]提出一種基于逆向拍賣的激勵機制促進移動云卸載市場積極和公平的競爭，對未完成卸載任務的移動用戶設立了故障恢復和懲罰機制。移動邊緣計算(Mobile Edge Computing, MEC)和EH技術相結合的綠色通信對EH技術和Ad Hoc移動云的融合帶來了極大啟發(fā)。針對帶有EH小基站的MEC異構環(huán)境，文獻[9]考慮平均時延和平均能量需求，提出一種基于分布式可預測隨機博弈的動態(tài)卸載算法，基站利用不完全狀態(tài)信息做出最優(yōu)卸載決策。文獻[10]針對能量收集物聯(lián)網(wǎng)霧系統(tǒng)中的可預測分布式卸載問題提出一種基于學習的分布式卸載算法，滿足時延約束下使物聯(lián)網(wǎng)設備根據(jù)預測的系統(tǒng)狀態(tài)做出近似最優(yōu)的決策。文獻[11]研究具有能量收集能力的MEC系統(tǒng)在隊列積壓和電池電量約束下的任務卸載問題，通過基于Lyapunov的動態(tài)卸載算法最小化移動設備的能量消耗和執(zhí)行時延的平均加權和。文獻[12]提出了能量收集MEC系統(tǒng)中基于強化學習的動態(tài)任務卸載策略，以最小化系統(tǒng)長期成本，所提算法使學習速率和運行性能顯著提高。

帶有EH功能的不同終端設備具有不同的數(shù)據(jù)特征和應用需求，這對任務的卸載效率提出了嚴峻挑戰(zhàn)，現(xiàn)有的任務卸載方案大多只考慮移動終端帶有EH功能，未考慮基站或MEC服務器帶有EH功能的場景。本文考慮所有終端設備都帶有EH功能的移動Ad Hoc云網(wǎng)絡，提出一種分布式動態(tài)卸載方案來聯(lián)合優(yōu)化能量收集和計算任務卸載策略；將終端設備間的任務卸載問題建模為一個買賣博弈問題，設計了一種基于動態(tài)報價的激勵機制；最后證明系統(tǒng)達到Stackelberg均衡，仿真分析驗證了本文方案的有效性。

2 系統(tǒng)模型

2.1 計算任務模型

2.2 任務卸載模型

為簡單起見，本地計算中只考慮處理計算任務產(chǎn)生的能耗

2.3 能量收集模型

2.4 問題分析

其中，式(14)表示Ci任務卸載量不超過其任務隊列積壓量，式(15)表示隊列穩(wěn)定性約束[15]。

3 基于博弈論的動態(tài)分布式卸載方案

在具有能量收集功能的移動Ad Hoc云中，終端設備受任務隊列積壓、算力資源以及電池能量等因素的影響，很難收集所有移動設備的狀態(tài)信息，此外，任務到達和能量收集的間歇性和不連續(xù)性導致移動終端很難預測系統(tǒng)狀態(tài)，使卸載決策變得更加復雜，傳統(tǒng)的集中式方案對此問題的求解比較困難。本節(jié)將代理終端作為賣方，通過動態(tài)資源報價為客戶終端提供不同的計算和存儲資源；客戶終端作為買方，根據(jù)自身的計算任務需求向代理終端購買資源。因此，本節(jié)將收益優(yōu)化問題建模成為具有買賣雙方的非合作博弈，通過Lyapunov優(yōu)化理論和博弈論對終端設備的卸載決策與價格策略建模，并對博弈模型進行分析。

3.1 買賣博弈模型分析

由于電池能量是與時間相關的，終端設備在不同時隙的卸載決策是耦合的。擾動加權方法是有效解決以上問題的方法[16]。為了消除耦合效應，首先定義終端設備的擾動參數(shù)和虛擬能量隊列。

3.1.2 賣方博弈模型分析

3.2 買賣博弈策略分析

3.2.1 買方策略分析

3.3 Stackelberg均衡性分析

4 仿真結果及分析

在本節(jié)對資源動態(tài)報價、電池能量、隊列積壓以及系統(tǒng)收益等進行仿真分析。本文方案通過與本地執(zhí)行方案、集中式方案[18]和貪婪算法[19]進行仿真對比，驗證本文所提方案的有效性。

4.1 仿真場景設置

4.2 性能分析

圖2描述了移動終端CPU計算頻率和動態(tài)價格的博弈過程。假設系統(tǒng)有1個客戶終端和4個代理終端，單位通信成本和能耗成本分別為ρ1= 0.06,η1= 1×10-7,Vj1=100;ρ2= 0.12,η2= 2×10-7,Vj2=150;ρ3= 0.18,η3= 4×10-7,Vj3=200;ρ4=0.24,η4= 8×10-7,Vj4=250。

由圖2(a)可知，代理報價隨著迭代次數(shù)的增加而增加，直到收斂于最優(yōu)報價。由圖2(b)可知，最初代理的成本價格較低，客戶終端購買的CPU頻率隨著迭代次數(shù)的增加先增加。隨著代理報價增加，客戶購買CPU頻率的意愿降低，購買的CPU頻率隨著迭代次數(shù)的增加而減少，最終當代理報價趨于穩(wěn)定時，購買的CPU頻率也趨于穩(wěn)定。此外，代理終端的單位通信成本和單位計算成本越高，動態(tài)資源報價越高，客戶終端購買的CPU頻率就會越少。

圖2 資源動態(tài)報價過程

圖3描述了不同客戶終端的電池能量和任務隊列積壓隨時間的變化過程。假設系統(tǒng)中有3個客戶終端和4個代理終端。其中，客戶終端的任務到達速 率 分 別 為λ1= 5 Mbit/s ,λ2= 8 Mbit/s ,λ3=12 Mbit/s ；任務處理密度為L1= 1500 cycle/Mbit,L2= 1200 cycle/Mbit,L3= 1000 cycle/Mbit；控制參數(shù)為V1= 100,V2= 300,V3= 500。

由圖3可知，客戶終端的電池能量和任務隊列積壓會隨著時間的增加先增加后趨于穩(wěn)定。由于不同客戶終端任務到達速率，控制參數(shù)以及任務處理速率不同，電池能量和任務隊列積壓達到穩(wěn)定的時間也不同。對于任務到達率高的客戶終端，可以通過調整控制參數(shù)加快任務隊列積壓和電池能量的收斂速度。

圖3 任務隊列積壓及電池能量

圖4描述了本文方案與不同卸載方案任務隊列積壓、電池能量和系統(tǒng)總收益的性能對比。由圖4可知，本地執(zhí)行方案只使用本地的計算資源導致任務處理效率較低，會造成最大的任務隊列積壓和最低的系統(tǒng)收益。文獻[18]中集中式方案在隊列積壓與收益之間進行平衡，獲得稍高于本地處理的系統(tǒng)收益。文獻[19]中貪婪算法盡可能地將任務卸載到代理處理，因此會有較小的任務隊列積壓，但是系統(tǒng)總收益也會降低。本文方案在代理終端增加能量收集功能，通過差異化的資源動態(tài)報價和買賣博弈論，可以有效提高系統(tǒng)收益，減少任務隊列積壓并增加電池能量。

圖4 不同方案對比

5 結束語

本文研究了一種基于能量收集的移動Ad Hoc云任務卸載問題，為了激勵終端設備間的協(xié)作，利用Lyapunov優(yōu)化理論和博弈論方法提出一種分布式卸載方案，聯(lián)合優(yōu)化了能量收集以及任務卸載策略，提高了系統(tǒng)收益。仿真結果驗證了所提算法的有效性。移動Ad Hoc云中終端設備的移動性也是影響任務卸載的重要因素，在未來工作將進一步研究基于終端設備可移動性的任務卸載方案研究。