法律状态公告日
法律状态信息
法律状态
2022-07-01
公开
发明专利申请公布
技术领域
本发明属于移动通信技术领域，具体涉及一种移动Ad Hoc云中基于能量收集的多阶段随机规划任务卸载方法。
背景技术
随着物联网(Internet of Things,IoT)的发展，网络算力资源和算力需求都迎来了爆炸式增长，为节省云端的算力资源，许多任务卸载到云端前要经过预处理，这对移动终端的处理能力和电池的续航能力造成了严峻的挑战。移动终端的电池容量十分有限，传统的供电设备会造成较大的通信成本。随着万物互联时代的到来和面向‘云’终端的指数级增长，网络算力需求也迅速增长，边缘算力不足以及不均衡的问题依然无法有效解决。在一些网络场景中(如Ad Hoc网络，无人机网络，车辆云网络等)没有可用云服务器或本地微云，或因网络拥塞造成计算任务不能被及时处理，
移动Ad Hoc云计算作为一种新型的移动计算范式被提出并得到广泛研究。与传统云计算需要将本地任务卸载到网络中心云或边缘云服务器不同，移动Ad Hoc云是一组附近终端设备组成的自组织云，每个终端设备都可以将任务卸载到相邻的终端设备并使用其可用的计算资源。受体积和硬件成本的限制，电池容量有限的传统电池供电设备在电池能量不足时无法进行任务传输和任务处理，会影响计算性能。当设备分布在偏远或有毒有害环境中时，难以通过可充电电池或传统电网进行供电。能量收集(Energy Harvesting,EH)技术可以支持终端设备从环境中获取绿色能源(如太阳能、风能、机械能等)，减少对电网或电池能源供应的依赖，进一步提升系统的能量效率，实现绿色通信。因此，移动Ad Hoc云计算与EH技术融合对提高网络计算性能具有重要意义。Ad Hoc网络中的终端设备种类繁多，由于其随机移动性，节点间的无线连接往往会随之动态变化，使得其网络拓扑结构也极具不确定性。如果终端设备在执行卸载任务的过程中离开当前Ad Hoc网络，可能会导致子任务被重新分配，造成任务的处理时延过大、成本过高以及网络资源的严重浪费，甚至会导致任务卸载失败。因此，研究移动Ad Hoc云环境中的用户随机移动性问题是十分有必要的。
近年来，MEC和EH技术相结合的绿色通信也受到了广泛的关注，这对EH技术和AdHoc移动云的融合带来了极大启发。针对节点位置动态变化的特点，一些主要的成果有：(1)具有能量收集功能的物联网雾计算系统中的分布式计算卸载：DEC-POMDP方法(参考文献：TANG Q,XIE R,YU F A,et al.Decentralized computation offloading in IoT fogcomputing system with energy harvesting:A DEC-POMDP approach[J].IEEE Internetof Things Journal,2020,7(6):4898-4911.DOI:10.1109/JIOT.2020.2971323.)：该算法针对能量收集物联网雾系统中的可预测分布式卸载问题提出一种基于学习的分布式卸载算法，满足时延约束下使物联网设备根据预测的系统状态做出近似最优的决策。(2)一种用于不确定无线场景下的众感知分布式博弈方法(参考文献：Cao B,Xia S C,Han J W,etal.A distributed game methodology for crowdsensing in uncertain wirelessscenario[J].IEEE Transactions on Mobile Computing,2019,19(1):15-28.DOI:10.1109/TMC.2019.2892953)：由于移动设备是自私和理性的，感知任务的随机到达和离开，以及移动设备的随机移动导致随机连接，提出了一种基于多阶段随机规划的分布式博弈群体感知方法，以获得更好的群体感知响应。(3)物联网雾计算系统中的多阶段随机规划卸载策略(参考文献：Zhang L,Cao B,Li Y,et al.A multi-stage stochasticprogramming based offloading policy for fog enabled IoT-eHealth[J].IEEEJournal on Selected Areas in Communications,2020.DOI:10.1109/JSAC.2020.3020659)：为了评估随机情景下不确定性对卸载策略的影响，将任务卸载问题表述为多阶段随机规划问题(MSSP)，研究了卸载、资源分配和迁移的联合决策，以最小化卸载的总延迟。(4)移动Ad Hoc云环境中基于多阶段随机规划的任务分配方法(参考文献：Tham C K.,Cao B.Stochastic programming methods for workload assignment in anad hoc mobile cloud[J].IEEE Transactions on Mobile Computing,2017,17(7):1709-1722.DOI:10.1109/TMC.2017.2762313)：考虑移动Ad Hoc云环境中设备间连接时间的随机性，为最大化移动设备的效益，提出了一种分布式多阶段随机买卖博弈算法，有效地促进了移动设备间的协作，并实现了最优整体性能。
Ad Hoc云网络中用户的随机移动会导致移动设备间连接不稳定，终端设备协助附近终端处理计算任务时，很难准确预测是否会移出当前的网络，这会影响任务卸载决策和资源分配策略，从而影响系统的卸载收益。由于每个终端设备的资源有限，而且是自私和理性的，除非有合理的动机，否则没有终端设备愿意无偿地为其他终端设备提供服务。因此，如何以多阶段随机规划的方法开发具有能量收集水平的任务卸载策略具有重要研究价值。
发明内容
为了实现系统收益的提升，本发明提出一种移动Ad Hoc云中基于能量收集的多阶段随机规划任务卸载方法，具体包括以下步骤：
S1、构建带有EH功能的移动Ad Hoc云网络，用终端设备间Wi-Fi连接时间的不确定性来表示用户的随机移动，分别建立卸载收益模型、通信成本模型、计算成本模型和能量收集模型；
S2、将客户终端作为买方，根据自身的计算任务需求向代理终端购买资源，采用李雅普诺夫优化理论，建立买方的收益最大化问题；
S3、将代理终端作为卖方，通过动态资源报价为客户终端提供不同的计算和存储资源，建立卖方的收益最大化问题；
S4、建立随机买卖博弈模型，根据连接时间的不确定性，分别建立两阶段随机规划模型和多阶段随机规划模型；
S5、根据客户终端的任务积压、电池能量水平以及代理终端的报价，在各个子时隙内，利用拉格朗日乘子法和KKT条件计算出买方向所选择的代理终端卸载的最优任务卸载策略以及卖方的最优报价策略；
S6、若买方的最优任务卸载策略和卖方的最优报价策略满足斯坦克尔伯格均衡解，则客户终端按照最优任务卸载策略向代理终端进行任务卸载。
进一步的，建立买方的收益最大化问题包括：
约束条件：
其中，
进一步的，买方的两阶段随机规划模型包括：
其中，
进一步的，买方的多阶段的随机规划问题表示为：
其中，l表示将时隙t划分为l个子时隙；
进一步的，利用拉格朗日乘子法和KKT条件计算出买方向所选择的代理终端卸载的最优任务卸载策略，即最优任务卸载量表示为：
其中，
进一步的，建立卖方的收益最大化问题包括：
约束条件：
其中，
进一步的，卖方的两阶段随机规划模型包括：
其中，M为客户终端数量；
进一步的，卖方的多阶段的随机规划问题表示为：
其中，l表示将时隙t划分为l个子时隙；
进一步的，利用拉格朗日乘子法和KKT条件计算出卖方的最优报价策略，即第t
其中，ξ
首先，本发明为应对Wi-Fi区域内的随机连接时间所代表的附近移动终端的移动性，采用多阶段随机规划算法来解决任务卸载问题；考虑每个移动终端有不同的计算能力和电池能量，将会在移动终端间产生一个最佳的任务卸载决策；其次，为了激励移动终端间的合作，将问题建模成为一个买卖博弈问题，并确定买卖博弈的Stackelberg均衡策略，仿真分析验证了本发明方案可以有效提高系统收益。
附图说明
图1为本发明中移动Ad Hoc云中一种基于能量收集的多阶段随机规划卸载方法流程图；
图2为本发明中移动Ad Hoc云协作系统模型；
图3为本发明中通信成本与WiFi连接时间关系图。
具体实施方式
下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。
本发明提出一种移动Ad Hoc云中基于能量收集的多阶段随机规划任务卸载方法，具体包括以下步骤：
S1、构建带有EH功能的移动Ad Hoc云网络，用终端设备间Wi-Fi连接时间的不确定性来表示用户的随机移动，分别建立卸载收益模型、通信成本模型、计算成本模型和能量收集模型；
S2、将客户终端作为买方，根据自身的计算任务需求向代理终端购买资源，采用李雅普诺夫优化理论，建立买方的收益最大化问题；
S3、将代理终端作为卖方，通过动态资源报价为客户终端提供不同的计算和存储资源，建立卖方的收益最大化问题；
S4、建立随机买卖博弈模型，根据连接时间的不确定性，分别建立两阶段随机规划模型和多阶段随机规划模型；
S5、根据客户终端的任务积压、电池能量水平以及代理终端的报价，在各个子时隙内，利用拉格朗日乘子法和KKT条件计算出买方向所选择的代理终端卸载的最优任务卸载策略以及卖方的最优报价策略；
S6、若买方的最优任务卸载策略和卖方的最优报价策略满足斯坦克尔伯格均衡解，则客户终端按照最优任务卸载策略向代理终端进行任务卸载。
本实施例从系统模型、基于多阶段随机规划的问题分析以及基于多阶段随机规划的最优策略分析三个方面对本发明方案进行详细说明。
一、系统模型
考虑一个带有EH功能的移动Ad Hoc云网络，用终端设备间Wi-Fi连接时间的不确定性来表示用户的随机移动，其任务卸载模型图如图1所示，包括M个有不同计算任务的客户终端(Client，C
假设C
1.卸载收益模型
为了评估移动Ad Hoc云中C
其中，
2.通信成本模型
在移动Ad Hoc云中，任务的卸载过程主要包括客户终端的任务上传、代理终端协同计算卸载任务及计算结果返回。因此，通信成本是在客户终端的任务上传和计算结果返回两个过程中产生的。
首先，假设客户终端卸载到代理终端的任务必须在开始处理前被完全接收，并在全部处理完成后才将结果返回。假设时隙t开始时，所有代理终端都位于Wi-Fi覆盖区域内，蜂窝网络可始终用于网络通信，只有A
根据代理终端在Wi-Fi覆盖范围内的时间，可以确定客户终端通过Wi-Fi和蜂窝网络传输的数据量。当C
其中，
根据公式(2)和(3)，C
其中，
C
其中，λ
其中，
根据式(6)和(7)，A
类似于任务上传过程中的通信能耗，A
3.计算成本模型
A
其中，λ
4.能量收集模型
假设每个带有EH的终端设备都可以从环境中获取绿色能源用于电池供电，EH过程被建模为连续的能量包到达过程，g＝i时表示客户终端，g＝j时表示代理终端。用
用
A
为防止电池过度放电，应满足式(14)和(15)电池放电约束：
其中，Emax和Em
根据式(12)和(14)，C
根据式(13)和(15)，A
二、基于多阶段随机规划的问题分析
在移动Ad Hoc云中，终端设备卸载决策受能量队列稳定性以及任务卸载时间的约束，在同时考虑系统卸载收益、通信成本和计算成本的情况下，本发明提出一个系统收益的最大化问题，如式(20)所示。
max：
s.t.(14),(15),(16),(17)
式(21)表示卸载到代理终端的总任务量不能超过其任务队列积压。
在移动Ad Hoc云网络中，客户终端可以将计算任务卸载到邻近的代理终端，并决定卸载到每个代理终端的任务量，将代理终端作为卖方，通过动态资源报价为客户终端提供不同的计算和存储资源；客户终端作为买方，根据自身的计算任务需求向代理终端购买资源，这一过程可视为买卖博弈过程。
1.买卖博弈模型分析
由于电池能量是与时间相关的，终端设备在不同时隙的卸载决策是耦合的。扰动加权方法是有效解决以上问题的方法
EH设备的扰动参数θ
其中，
虚拟能量队列定义为
1)买方博弈模型分析
定义第t时隙C
s.t.(14),(15),(16),(17),(21)
为了权衡客户终端收益和能量队列积压之间的关系，引入Lyapunov函数对每个客户终端的队列积压进行建模，Lyapunov函数是当前时隙内C
其中，L[Θ
式(19)表示从第t时隙到第t+1时隙的队列积压增长。通过最小化Δ[Θ
Lyapunov漂移加惩罚表示为：
优化买方收益的目标是最小化Lyapunov漂移加惩罚函数，将其表示为P2问题：
P2：
s.t.(14),(16),(21)
2)卖方博弈模型分析
对于代理终端，在时隙t内为客户终端提供计算资源获得的收益为
类似地，代理终端的Lyapunov漂移加惩罚函数为：
将卖方的优化问题表示为P3问题：
P3:
s.t.(15),(17),(30)
2.随机买卖博弈模型分析
由于移动Ad Hoc云网络中的每个终端设备都具有随机移动性，会导致客户终端与代理终端之间的Wi-Fi连接时间不确定，从而导致任务卸载过程中的通信成本也不确定，在Wi-Fi覆盖区域内，可以根据历史上的观察值对客户终端与代理终端的连接时间进行预测，但简单的预测可能不准确。当客户终端与代理终端的实际连接时间小于预测值时，会导致决策任务量过大，造成较高的通信成本；当客户终端与代理终端的实际连接时间大于预测值时，会导致决策任务量过小，Wi-Fi连接不能被充分地用于数据传输，造成资源的浪费。为了处理连接时间的不确定性，采用多阶段随机规划方法能够采取后验追索行动来补偿预测的不准确性。
1)连接时间的不确定性
假设每个在客户终端所处的Wi-Fi覆盖区域内的代理终端和客户终端的Wi-Fi连接时间服从概率分布。用Ω
不确定参数被观测后的实际场景称为一个实现，当C
2)两阶段随机规划模型
C
s.t.(14),(16),(21)
类似地，卖方的两阶段的随机规划问题为
s.t.(15),(17),(30)
3)多阶段随机规划模型
使用两阶段随机买卖博弈模型，最优策略只有在每一时隙开始时决策一次，不能保证在一个决策时隙完全卸载任务，会造成预测的不准确，无法得到最优的卸载决策。为了更精确地捕捉客户终端与代理终端之间Wi-Fi连接时间的信息，将两阶段随机规划问题扩展为多阶段随机规划问题。在多阶段随机规划模型中，将时隙t划分为l个子时隙，定义t
买方的多阶段的随机规划问题为：
s.t.(14),(16),(21)(37)
卖方的多阶段的随机规划问题为：
s.t.(15),(17),(30)
三、基于多阶段随机规划的最优策略分析
在本实施例，首先分析所提出的多阶段随机规划方案的最优卸载策略和最优报价，并证明了客户终端最优卸载策略和代理终端最优报价的斯坦伯格均衡。不失一般性，本实施例分析了一个决策时隙、一个可能场景下的买卖双方最优策略。
1.买卖博弈策略分析
1)买方策略分析
买方的优化问题可以分为EH优化和任务卸载策略优化，由于两个变量是相互独立的，可以将P2问题转化为两个子问题Q1和Q2。
根据式(36)，求解能量收集的最优值：
Q1：min：
当
2)任务卸载优化策略
根据式(36)，将能量收集优化问题解耦合之后，任务卸载优化可表示为：
Q2：
s.t.(14),(16),(21)
客户终端为了最大化自身利益，根据控制参数V，队列积压Θ
其中，
2.卖方策略分析
代理终端的单位资源报价
1)根据式(26)，求解能量收集的最优值：
Q3：min：
当
2)资源报价优化策略
根据式(26)，将能量收集优化问题解耦合之后，资源报价优化可表示为：
Q4：
s.t.(15),(17),(30)
A
对
其中，
对
因此，
由于
3.Stackelberg均衡性分析
根据前面的分析可知，客户终端为最大化自身的收益，会根据代理的属性和信道资源做出卸载决策，选择合适的代理来协同计算卸载任务；而代理会根据客户终端的任务量和自身收益的关系，决策最优资源定价。接下来证明最优解
由于买方的效益函数二阶导数满足
尽管已经示出和描述了本发明的实施例，对于本领域的普通技术人员而言，可以理解在不脱离本发明的原理和精神的情况下可以对这些实施例进行多种变化、修改、替换和变型，本发明的范围由所附权利要求及其等同物限定。
