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

鲜永菊 郭陈榕 夏士超 李 云*

①(重庆邮电大学通信与信息工程学院 重庆 400065)

②(重庆邮电大学软件工程学院 重庆 400065)

1 引言

在快速发展的物联网技术驱动下，终端设备的数量和数据流量呈爆炸式增长，计算密集型和时延敏感型应用不断兴起，这对网络的实时算力资源提出了更高的要求。另一方面传统终端设备的能量、带宽和计算资源有限，难以满足以大数据和智能化为特征的新兴应用的实时计算需求及持久的续航能力。移动云计算和移动边缘计算通过将计算任务卸载到云端处理的方式缓解了终端设备计算资源受限的问题，但边缘算力不足以及分布不均衡的问题依然无法有效解决[1]。在一些网络场景中没有可用云服务器或本地微云，或因网络拥塞造成计算任务不能被及时处理，难以有效地满足用户的业务体验。

移动Ad Hoc云计算利用一组邻近终端设备的空闲或过剩资源来协同处理网络任务[2]。受体积和硬件成本的限制，传统终端设备的电池容量难以满足其长期续航的需求，尤其当设备分布在偏远或有毒有害环境中时，难以通过可充电电池或传统电网进行供电。能量收集(Energy Harvesting, EH)技术支持设备从环境中获取可再生能源支撑其通信和任务处理，已成为实现绿色移动通信的重要技术[3,4]。因此，移动Ad Hoc云计算与EH技术融合对提高网络计算性能具有重要意义。

近年来，移动Ad Hoc云计算的任务卸载问题得到了广泛研究[5,6]。文献[7]研究了移动Ad Hoc云环境中基于激励机制的效用最大化问题，提出一种实时分布式算法鼓励移动设备共享其空闲资源，使个体最优与系统整体最优相一致。为了激励移动用户参与异构移动云环境中的卸载服务，文献[8]提出一种基于逆向拍卖的激励机制促进移动云卸载市场积极和公平的竞争，对未完成卸载任务的移动用户设立了故障恢复和惩罚机制。移动边缘计算(Mobile Edge Computing, MEC)和EH技术相结合的绿色通信对EH技术和Ad Hoc移动云的融合带来了极大启发。针对带有EH小基站的MEC异构环境，文献[9]考虑平均时延和平均能量需求，提出一种基于分布式可预测随机博弈的动态卸载算法，基站利用不完全状态信息做出最优卸载决策。文献[10]针对能量收集物联网雾系统中的可预测分布式卸载问题提出一种基于学习的分布式卸载算法，满足时延约束下使物联网设备根据预测的系统状态做出近似最优的决策。文献[11]研究具有能量收集能力的MEC系统在队列积压和电池电量约束下的任务卸载问题，通过基于Lyapunov的动态卸载算法最小化移动设备的能量消耗和执行时延的平均加权和。文献[12]提出了能量收集MEC系统中基于强化学习的动态任务卸载策略，以最小化系统长期成本，所提算法使学习速率和运行性能显著提高。

带有EH功能的不同终端设备具有不同的数据特征和应用需求，这对任务的卸载效率提出了严峻挑战，现有的任务卸载方案大多只考虑移动终端带有EH功能，未考虑基站或MEC服务器带有EH功能的场景。本文考虑所有终端设备都带有EH功能的移动Ad Hoc云网络，提出一种分布式动态卸载方案来联合优化能量收集和计算任务卸载策略；将终端设备间的任务卸载问题建模为一个买卖博弈问题，设计了一种基于动态报价的激励机制；最后证明系统达到Stackelberg均衡，仿真分析验证了本文方案的有效性。

2 系统模型

2.1 计算任务模型

2.2 任务卸载模型

为简单起见，本地计算中只考虑处理计算任务产生的能耗

2.3 能量收集模型

2.4 问题分析

其中，式(14)表示Ci任务卸载量不超过其任务队列积压量，式(15)表示队列稳定性约束[15]。

3 基于博弈论的动态分布式卸载方案

在具有能量收集功能的移动Ad Hoc云中，终端设备受任务队列积压、算力资源以及电池能量等因素的影响，很难收集所有移动设备的状态信息，此外，任务到达和能量收集的间歇性和不连续性导致移动终端很难预测系统状态，使卸载决策变得更加复杂，传统的集中式方案对此问题的求解比较困难。本节将代理终端作为卖方，通过动态资源报价为客户终端提供不同的计算和存储资源；客户终端作为买方，根据自身的计算任务需求向代理终端购买资源。因此，本节将收益优化问题建模成为具有买卖双方的非合作博弈，通过Lyapunov优化理论和博弈论对终端设备的卸载决策与价格策略建模，并对博弈模型进行分析。

3.1 买卖博弈模型分析

由于电池能量是与时间相关的，终端设备在不同时隙的卸载决策是耦合的。扰动加权方法是有效解决以上问题的方法[16]。为了消除耦合效应，首先定义终端设备的扰动参数和虚拟能量队列。

3.1.2 卖方博弈模型分析

3.2 买卖博弈策略分析

3.2.1 买方策略分析

3.3 Stackelberg均衡性分析

4 仿真结果及分析

在本节对资源动态报价、电池能量、队列积压以及系统收益等进行仿真分析。本文方案通过与本地执行方案、集中式方案[18]和贪婪算法[19]进行仿真对比，验证本文所提方案的有效性。

4.1 仿真场景设置

4.2 性能分析

图2描述了移动终端CPU计算频率和动态价格的博弈过程。假设系统有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)可知，代理报价随着迭代次数的增加而增加，直到收敛于最优报价。由图2(b)可知，最初代理的成本价格较低，客户终端购买的CPU频率随着迭代次数的增加先增加。随着代理报价增加，客户购买CPU频率的意愿降低，购买的CPU频率随着迭代次数的增加而减少，最终当代理报价趋于稳定时，购买的CPU频率也趋于稳定。此外，代理终端的单位通信成本和单位计算成本越高，动态资源报价越高，客户终端购买的CPU频率就会越少。

图2 资源动态报价过程

图3描述了不同客户终端的电池能量和任务队列积压随时间的变化过程。假设系统中有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；控制参数为V1= 100,V2= 300,V3= 500。

由图3可知，客户终端的电池能量和任务队列积压会随着时间的增加先增加后趋于稳定。由于不同客户终端任务到达速率，控制参数以及任务处理速率不同，电池能量和任务队列积压达到稳定的时间也不同。对于任务到达率高的客户终端，可以通过调整控制参数加快任务队列积压和电池能量的收敛速度。

图3 任务队列积压及电池能量

图4描述了本文方案与不同卸载方案任务队列积压、电池能量和系统总收益的性能对比。由图4可知，本地执行方案只使用本地的计算资源导致任务处理效率较低，会造成最大的任务队列积压和最低的系统收益。文献[18]中集中式方案在队列积压与收益之间进行平衡，获得稍高于本地处理的系统收益。文献[19]中贪婪算法尽可能地将任务卸载到代理处理，因此会有较小的任务队列积压，但是系统总收益也会降低。本文方案在代理终端增加能量收集功能，通过差异化的资源动态报价和买卖博弈论，可以有效提高系统收益，减少任务队列积压并增加电池能量。

图4 不同方案对比

5 结束语

本文研究了一种基于能量收集的移动Ad Hoc云任务卸载问题，为了激励终端设备间的协作，利用Lyapunov优化理论和博弈论方法提出一种分布式卸载方案，联合优化了能量收集以及任务卸载策略，提高了系统收益。仿真结果验证了所提算法的有效性。移动Ad Hoc云中终端设备的移动性也是影响任务卸载的重要因素，在未来工作将进一步研究基于终端设备可移动性的任务卸载方案研究。