[0077] 为了使本发明的目的、技术方案及优点更加清楚明白,以下结合附图对本发明进行进一步详细说明。
[0078] 如图1所示,本发明包括以下步骤:
[0079] S1.建立系统模型:EH‑D2D网络由一个无线充电桩和n个移动设备MD={MD1,...,MDi,...,MDn}组成。每个移动设备MDi可以用多元组来表示,其中 和 分别表示低性能CPU和高性能CPU内核的数量; 和 分别表示
低性能CPU和高性能CPU的最大计算能力。 分别表示移动设备MDi的执行功
率,发送功率和接收功率; 表示移动设备MDi的电池容量。n个移动设备均可以通过无线充电站充电。
[0080] 每个移动设备MDi会产生相互独立的任务,每个任务可以用一个二元组t=(W,D)表示,其中W(GHz·s)表示任务工作负载,D表示单位工作负载的数据量(以MB为单位)。每个移动设备MDi包含一个等待执行队列Qi,该队列主要用于存储从其他移动设备卸载而来的任务以及由移动设备MDi自身产生并留在本地执行的任务。
[0081] 在EH‑D2D网络中,本发明采用离散时间模型,将一个时间段逻辑上划分为若干等长的时间片。每个时间片的长度为Tslot=1s。本发明用 来表示时间片索引的集合。在每个时间片τ中,无线充电站可以给每个移动设备充电。当移动设备的可用电量不足以执行其上到达的任务时,可以将部分或全部任务卸载到其他移动设备上协作执行。
在每个时间片τ的开始,每个移动设备根据自身可用电量和任务负载情况做出协作决策,该决策包括卸载给每个移动设备的任务数、留在本地执行的任务数和最多能够接收的任务数。
[0082] S2.建立任务排队模型:假设n个移动设备上任务的到达过程服从参数为λ=(λ1,...,λi,...,λn)的泊松分布。在每个时间片τ的开始,计算任务A(τ)=(a1(τ),...,ai(τ),...,an(τ))到达n个移动设备。令μij(τ)表示在时间片τ从移动设备MDi卸载到移动设备MDj的任务数;ηij(τ)表示在时间片τ移动设备MDi可以从移动设备MDj接收的最大任务数。因此,执行队列Qi的状态演化可以根据公式(1)计算。
[0083] Qi(τ+1)=max[Qi(τ)+ai(τ)W‑bi(τ)W‑∑i≠jμij(τ)W,0]+∑j≠iμji(τ)W[0084] (1)
[0085] μji(τ)≤ηij(τ) (2)
[0086] ∑j∈nμij(τ)=ai(τ) (3)
[0087] ∑j∈nμij(τ)≤ai(τ) (4)
[0088] ∑j≠i,j∈nμij(τ)+bi(τ)≤Qi(τ)+ai(τ) (5)
[0089] 其中bi(τ)表示MDi在时间片τ中执行的任务数,μji(τ)表示在时间片τ中从MDj卸载到MDi上的任务数目。公式(2)表示在时间片τ中MDj卸载给MDi的任务数不能超过MDi可以从MDj上接收的最大任务数。公式(3)表示在时间片τ中MDi上到达任务数是卸载到其他移动设备任务数与留在本地执行任务数之和。公式(4)表示在时间片τ中MDi卸载到其他移动设备的任务总数∑j≠i,j∈nμij(τ)小于等于其上到达的任务数ai(τ)。公式(5)表示在时间片τ中MDi卸载到其他移动设备上的任务总数与本地执行的任务数之和小于等于Qi中的任务数与其上到达任务数之和。
[0090] S3.建立电量模型:在时间片τ中,移动设备MDi的充电电量可以表示为其中μ∈[0,1]表示无线充电系数;P表示无线充电站的发射功率;hi(τ)表示在时间片τ中无线充电站与移动设备MDi之间的信道增益。在每个时间片τ的开始,MDi的可用电量可以用来表示,其演化方式可以根据公式(6)计算:
[0091]
[0092]
[0093]
[0094]
[0095] 其中 和 分别表示在时间片τ中MDi执行任务,传输任务和接收任务所消耗的电池电量。公式(7)表示在时间片τ中,MDi接收任务,执行任务和卸载任务所消耗的电池电量总和不能超过移动设备当前的可用电量。公式(8)表示在时间片τ中,MDi当前的可用电量与充电电量之和不能超过MDi的电池容量。
[0096] S4.建立网络模型:在EH‑D2D网络中,由于设备的移动性,无线信道的传输速率会动态变化。令 和 分别表示在时间片τ中MDi与MDj之间的上行传输速率和下行传输速率,可以通过公式(10)和(11)计算:
[0097]
[0098]
[0099] 其中, 和 分别是MDi上行链路和下行链路的信道带宽; 表示MDi的传2
输功率;σ是高斯噪声功率; 和 分别表示移动设备MDi到MDj之间的上行信道增益和下行信道增益。由于MDi与MDj之间上下行的通信距离相同,所以通道增益 和 可以通过 计算,其中α是路径损耗参数;θ是路径损耗指数;d0为参
照距离;dij是MDi与MDj之间的距离。
[0100] S5.多智能体强化学习的协作任务卸载策略:需要定义协作问题的状态空间和动作空间,并设计协作任务卸载问题的奖励函数。最后将多用户协作任务卸载建模为部分可观测马尔可夫决策过程(POMDP)的问题表述。具体包含以下子步骤:
[0101] S51.定义状态空间:每个移动设备MDi被看作一个智能体。在时间片τ的开始,每个智能体当前的状态Oi(τ)可以被观测,并将其用公式(12)表示。
[0102]
[0103] 其中Qi(τ)表示在时间片τ中MDi执行队列中剩余任务的数量,Gi(τ)=[Gi1(τ),...,Gi(i‑1)(τ),Gi(i+1)(τ),...,Gin(τ)]表示在时间片τ中MDi与除了它本身之外的其他移动设备之间的信道增益; 表示在时间片τ中MDi的可用电量; 表示在时间片τ中MDi的充电电量;ai(τ)表示在时间片τ中到达MDi的任务数。
[0104] S52.定义动作空间:每个智能体根据它当前的状态Oi(τ)选择一个动作Ai(τ)。动作Ai(τ)是由本地执行任务数,卸载任务数和最大接收任务数组成,并将其用公式(13)表示:
[0105] Ai(τ)=[bi(τ),μi(τ),ηi(τ)] (13)
[0106] μi(τ)=[μi1(τ),...,μi(i‑1)(τ),μi(i+1)(τ),...,μin(τ)] (14)[0107] ηi(τ)=[ηi1(τ),...,ηi(i‑1)(τ),ηi(i+1)(τ),...,ηin(τ)] (15)[0108] 其中bi(τ)表示在时间片τ中MDi上执行的任务数,μi(τ)表示从MDi卸载到其他(n‑1)个移动设备的任务数向量,ηi(τ)表示MDi从其他(n‑1)个移动设备上可以接收的最大任务数向量。在时间片τ中移动设备MDi执行任务,卸载任务和接收任务所消耗的总电量不能超过MDi的可用电量。
[0109] (1)执行任务所消耗的电量:移动设备采用动态调频(DVFS)技术来动态调节CPU频率。在时间片τ中MDi的计算能力 和计算功率 分别根据公式(16)和公式(17)计算:
[0110]
[0111]
[0112] 其中ai是与芯片架构有关的常数; 和 分别表示低性能CPU和高性能CPU内核的实际计算频率。当移动设备MDi决定在时间片τ中本地执行bi(τ)任务时,本发明使用公式(22)计算本地执行任务需要消耗的电量
[0113]
[0114] (2)卸载任务所消耗的电量:在时间片τ中,移动设备MDi实际卸载到移动设备MDj的任务数μ′ij可以用公式(19)表示。实际卸载任务所消耗的电量 可以用公式(20)来计算:
[0115]
[0116]
[0117] 执行任务,卸载任务和接收任务所消耗的电量之和不能超过移动设备的可用电量该约束条件可以用公式(21)表示。必须满足以下约束:
[0118]
[0119] S53.定义奖励函数:在多智能体协作任务卸载中,每个智能体根据其当前的状态值Oi(τ)和选择的动作Ai(τ)计算奖励Ri。奖励函数Ri是任务的平均处理时间Qi(τ),任务丢弃Di(τ)以及电量惩罚Pi(τ)的加权和,可以用公式(22)表示:
[0120]
[0121] 其中ω1,ω2和ω3分别是Qi(τ),Di(τ)和Pi(τ)的加权系数。任务丢弃Di(τ)可以根据公式(23)计算。
[0122]
[0123] 其中|Qi|表示执行队列Qi的长度。公式(|Qi|+bi(τ)‑Qi(τ))表示执行队列Qi的可用空间。为了避免由于移动设备的电量耗尽而导致移动应用程序中断,本发明将电量损失阈值设置为hi。当移动设备的可用电量 与最大电池容量 的比率小于hi时,电量惩罚Pi(τ)可以用公式(24)计算:
[0124]
[0125] S54.问题形式化:多用户协作任务卸载问题可以建模为POMDP。它的主要目标是最大化整个系统的奖励。
[0126] Maximize:‑R (25)
[0127] S6.策略实现:本发明设计了一种基于多智能体深度确定性策略梯度(MADDPG)算法来求解多用户协作任务卸载问题。MADDPG算法的详细求解过程为:
[0128] (1)在学习阶段,首先初始化每个智能体的环境参数和网络参数。环境参数主要包括执行队列长度,移动设备之间的信道增益,可用电量以及无线充电站和移动设备之间的信道增益。网络参数主要包括学习动作网络、学习评价网络、目标动作网络、目标评价网络和中继缓存容量。然后,观测每个智能体的当前状态Oi(τ),并根据当前状态选择每个智能体的动作Ai(τ)。其次,根据每个智能体当前的状态Oi(τ)和采取的动作Ai(τ),计算出即时奖励Ri(τ)和下一个时间片(τ+1)时的状态O‑i(τ+1)。最后,每个智能体将其状态转移四元组(Oi(τ),Ai(τ),Ri(τ),O‑i(τ+1))存储到其中继缓存Ωi中。
[0129] (2)在训练阶段,每个智能体i首先会从其中继缓存Ωi中随机抽取mini_batch个状态转移四元组。然后,每个智能体i分别根据目标动作网络和目标评价网络计算状态O‑i(τ+1)的目标动作值和目标 值。在目标评价网络中更新状态Oi(τ)的目标 值,并根据该值更新估计 网络。
[0130] 实施例
[0131] 本实施例步骤与具体实施方式相同,在此不再进行赘述。下面就对比方法的实施和实施结果进行展示:
[0132] 本发明实现了基于梯度策略进行强化学习协作任务卸载策略的CACTE算法,将该算法与Local算法,Random算法,ECLB算法以及CCLB算法进行对比,并且分别就任务到达率ULλ,移动设备电池电量 工作负载W,任务数据大小D,带宽BW (τ),移动设备数量n对总奖励的影响进行评估。
[0133] 为了研究任务到达率λ对总奖励的影响,以[1,1,1,1]为增量,分别将λ设置为[1,0,5,8],[2,0,6,9],[3,1,7,10],[4,2,8,11]和[5,3,9,12]。图2显示了CACTE方案获得的总奖励优于Local算法,Random算法,ECLB算法和CCLB算法获得的总奖励。当任务到达率增加时,CACTE方案和四钟算法的总奖励都将逐渐降低。
[0134] 为了研究移动设备电池电量 对总奖励的影响,设置移动设备的电池电量以5为增量从40电量单位增加至60电量单位。图3显示了当电池电量小于55时,随着电池电量的增加,CACTE方案和四种算法的总回报都将增加。但是,当移动设备的电池电量等于或大于55时,所有算法的曲线都是平坦的。
[0135] 为了研究工作负载W对总奖励的影响,设置W在0.6到1.4的范围内变化,图4显示了CACTE方案比其他四种算法获得了更高的总奖励。并且当任务工作量W增加时,CACTE方案获得的总奖励在逐渐减少。
[0136] 为了研究任务数据大小D对总奖励的影响,设置D在0.6到1.4的范围内变化,图5显示了CACTE方案的总奖励高于四种算法的总奖励,并且CACTE计划获得的总奖励随着任务数据大小的增加而逐渐减少。
[0137] 为了研究带宽BWUL(τ)对总奖励的影响,将移动设备上行链路的带宽设置为与其下UL行链路相等的值。设置带宽BW (τ)从5MHz增加至15MHz,增量为0.25。图6显示了CACTE方案的总奖励高于四种算法的总奖励,并且当带宽增加时,CACTE计划的总奖励会增加并稳定。
[0138] 为了研究移动设备数量n对总奖励的影响,将n的值分别设置为3,4,5,6。表1显示了CACTE方案相较于其他四种算法可获得更高的总奖励。
[0139] 表1
[0140]
[0141] 并且,在由任务配置为Type1,Type2,Type3,Type4的四个移动设备组成的协作任务卸载场景中,CACYE方案也胜过其他四种算法。