边缘计算中基于强化学习的无人机任务卸载方法及系统转让专利
申请号 : CN202010675018.7
文献号 : CN111787509B
文献日 : 2021-11-02
发明人 : 邓晓衡 , 李君 , 关培源 , 李博
申请人 : 中南大学
摘要 :
权利要求 :
1.一种边缘计算中基于强化学习的无人机任务卸载方法,其特征在于,包括:步骤1,根据无人机到边缘节点的距离、边缘节点处理能力、切换节点对任务完成时间和能耗的影响建立基于边缘计算的无人机目标追踪的系统模型;
步骤2,通过研究无人机目标追踪过程中的任务分配决策问题,将无人机目标追踪过程中的任务分配决策问题建模成马尔可夫决策过程;
步骤3,基于强化学习中的Q学习设计求解算法,对无人机目标追踪过程中的任务分配决策问题进行求解,得出最佳的边缘节点选择方案和发射功率调整方案;
所述步骤1具体包括:
无人机在目标追踪过程中,将拍摄的视频任务卸载到地面边缘节点进行处理,研究无人机在时间T内的工作情况,假设无人机的飞行高度为H(m),无人机的飞行轨迹投影到地面
2×1
上表示为q(t)∈R ,0≤t≤T,时间T被离散成M个时隙,即T=Mδt,其中,δt表示每个时隙的长度,无人机在一个时隙中位置认为是不变的,无人机的轨迹近似离散为一个集合Q={qm,
1≤m≤M},其中,qm表示时隙m中无人机的位置,无人机在M个时隙产生的M个任务表示S={s1,s2,…,sM},其中,sm表示第m个任务的数据量大小,单位为bits,1≤m≤M;
所述步骤1还包括:
假定在城市的一片区域里有k个边缘节点,用集合N={n1,n2,n3,…,nk}表示,ni表示第i
2×1
个边缘节点,i∈[1,k],边缘节点ni的位置表示为wi∈R ,考虑到每个边缘节点的计算能力不同和无人机实时移动,无人机到边缘节点的通信距离为变化的,无人机到每个边缘节点的通信距离不同,无人机卸载到每个边缘节点的任务完成时间和产生的能耗也不同,假设在时隙m,将边缘节点ni选择为计算节点,如下所示:其中,dm,i表示无人机与边缘节点ni之间的距离,qm表示时隙m中无人机的位置,wi表示
2×1
边缘节点ni的位置,wi∈R ,H表示无人机的飞行高度;
准静态块衰落信道遵循自由空间路径损耗模型,无人机和边缘节点之间的信道,如下所示:
其中, 表示无人机和边缘节点之间的信道,β0表示参考距离d0=1m处的信道功率增益,qm表示时隙m中无人机的位置,wi表示边缘节点ni的位置,H表示无人机的飞行高度;
所述步骤1还包括:
假设发射功率在一个有限的状态空间Pn中调整选择,系统的通信速率R与发射功率和选择边缘节点有关,给定发射功率pm,i和无人机到边缘节点的距离dm,i,选择不同的边缘节点,无人机到边缘节点的距离不同,系统的通信速率如下所示:其中,Rm,i(pm,i,dm,i)表示系统的通信速率,单位为bps,pm,i表示在时隙m中无人机分配2
给节点ni的发射功率,B表示信道带宽,σ表示高斯白噪声功率, 表示距离d0=1m时的信噪比, 表示无人机和边缘节点之间的信道,β0表示参考距离d0=1m处的信道功率增益,qm表示时隙m中无人机的位置,wi表示边缘节点ni的位置,H表示无人机的飞行高度;
所述步骤1还包括:
在无人机进行目标追踪的过程中,无人机将视频任务卸载到边缘节点进行协同处理,无人机进行目标追踪过程的时间开销包括传输时间和计算时间,任务传输时间表示为:其中,Rm,i(pm,i,dm,i)表示系统的通信速率,pm,i表示在时隙m中无人机分配给节点ni的发射功率,dm,i表示无人机与边缘节点ni之间的距离,sm表示第m个任务的数据量大小,单位为bits;将任务sm卸载到边缘节点ni的计算时间为: 其中,sm表示第m个任务的数据量大小,w表示处理单位视频任务量需要的CPU周期,单位为周期数/比特,fi表示边缘节点ni的CPU时钟频率,单位为周期数/秒;
假设结果反馈时延是一个固定的很小的值,可以忽略不计,将任务sm卸载到边缘节点ni处理的总执行时间为数据传输时间和数据计算时间之和,如下所示:其中, 表示将任务sm卸载到边缘节点ni处理的总执行时间, 表示数据传输时间,表示数据计算时间;
将执行计算任务的能耗开销,如下所示:其中,pm,i表示在时隙m中无人机分配给节点ni的发射功率,pidle表示空闲状态下的功率, 表示执行计算任务的能耗开销, 和 分别表示数据传输时间和数据计算时间;
所述步骤1还包括:
当无人机在时隙m连接的边缘节点ni与在上一个时隙m‑1连接的边缘节点nj不同时,会带来额外的切换开销,包括能耗开销和时间开销,假设切换过程中每个时隙的能耗开销,如下所示:
其中,1{Ω}表示指示函数,Ω=
假设切换过程中的每个时隙的时间开销,如下所示:其中, 表示切换过程中每个时隙的时间开销,表示一次节点切换带来的时间开销;
结合执行计算任务的能耗开销和切换过程中每个时隙的能耗开销,得出每个时隙m的总能耗开销 如下所示:
其中, 表示每个时隙m的总能耗开销, 表示执行计算任务的能耗开销, 表示切换过程中每个时隙的能耗开销;
得出每个时隙m的总时间开销 如下所示:其中, 表示每个时隙m的总时间开销, 表示执行计算任务的时间开销, 表示切换过程中每个时隙的时间开销;
将每个时隙m的任务执行开销 定义为能耗开销和时间开销的权重和,如下所示:其中, 表示每个时隙m的任务执行开销, 表示每个时隙m的总能耗开销,表示每个时隙m的总时间开销,α表示传输能量消耗的相对权重,α≥0,β表示总延迟的相对权重,β≥0;
假设在时隙m选择边缘节点ni作为服务节点,决策变量xmi=1,时隙m不选择边缘节点ni作为服务节点,决策变量xmi=0,为联合优化无人机的传输功率和边缘节点的选择机制,最小化无人机能耗开销与时间开销的权衡 优化问题如下所示:其中,xmi表示决策变量, 是每个时隙m的任务执行开销;
其中,xmi表示决策变量。
2.根据权利要求1所述的边缘计算中基于强化学习的无人机任务卸载方法,其特征在于,所述步骤2具体包括:
无人机追踪过程中不断产生的视频任务根据上一个任务所在执行节点、无人机位置和任务量大小被卸载到边缘节点执行,系统的状态由上一个任务所在执行节点、无人机位置m m‑1 m
和任务量大小构成,将无人机在每个时隙m的状态表示为x=(N ,A)∈X={1,2,…,k}×m
{qm,sm},其中,A={qm,sm},动作空间由选择的执行任务的节点和无人机发射功率的大小构m m
成,y=(N ,pm)∈Y={1,2,…,k}×{Pm},其中,Pm表示发射功率可能取值的集合,在每个时m
隙m开始时对状态x的观测,无人机遵从静态控制决策 从动作空间中选择一个动作,其中, 表示卸载节点选择机制, 表示发射功率调整策略,系统在一个状态选择相应的动作之后,其中,状态为上一个任务所在执行节点、无人机位置和任务量大小,相应的动作为计算节点和发射功率,按照动作转移的概率为1,系统的状态转移概率为1,给定一个决策m
则{x:m∈M}是一个有以下状态转移概率的可控的马尔科夫链,如下所示:
3.根据权利要求2所述的边缘计算中基于强化学习的无人机任务卸载方法,其特征在于,所述步骤2还包括:
一个决策规则描述了一个特定时隙的状态进行动作选择的过程,如下所示:1
其中, 表示在给定一个初始状态x 和策略 的情况下无人机的长期预期总开销,m m 1 C C
C(x ,y)表示每个时隙的总开销,x 表示初始状态, 表示策略;x=(N ,A),C表示特定时m m
隙,1≤C≤M,存在一个静态策略对所有策略来说是最优的,C(x ,y)为 在强化学习中的函数表示,Eφ表示数学期望;
设计一个最佳的控制策略 最佳的控制策略中建议采取的动作使得在当前阶段以及后续阶段产生的开销 最小,如下所示:其中, 表示最佳的控制策略,将 作为最佳的状态‑值函数,
4.根据权利要求3所述的边缘计算中基于强化学习的无人机任务卸载方法,其特征在于,所述步骤3具体包括:
使用强化学习解决无人机目标追踪过程中的任务分配决策问题,将回报函数与需要优化的目标函数联系起来,根据优化目标为最小化总开销和强化学习的目标为最大化回报,将回报函数与原始的目标函数设置为负相关,如下所示:R(x,y)=‑C(x,y) (16)其中,R(x,y)表示瞬时回报,x表示状态,y表示动作。
5.根据权利要求4所述的边缘计算中基于强化学习的无人机任务卸载方法,其特征在于,所述步骤3还包括:
为限制动作空间的大小,在学习过程之前对于每个边缘节点,根据无人机到边缘节点的距离判断无人机是否在该边缘节点的服务范围内,如果不满足条件,则在第一次选到这个边缘节点时,将与该边缘节点有关的动作的Q值设置为一个很小的值,采用Q‑learning强化学习方法,每个状态‑动作都有一个值Q(s,a),对于寻找最佳动作过程中的每一步,智能体将每个状态‑动作的值Q(s,a)进行计算并存储在Q表中,将每个状态‑动作的值Q(s,a)视为长期回报的期望,Q(s,a)的更新公式如下所示:Q(s,a)=r(s,a)+γ*max Q(s′,a′) (17)其中,s,a表示当前状态和动作,s′,a′表示下一个时隙的状态和动作,γ表示学习率,0≤γ≤1;当γ趋于0,agent考虑当前的瞬时回报,当γ趋于1,agent关注未来的回报,对于寻找最佳动作过程中的每一步,迭代每个状态‑动作的值Q(s,a),r(s,a)表示回报。
说明书 :
边缘计算中基于强化学习的无人机任务卸载方法及系统
技术领域
背景技术
要研究无人机在目标追踪场景中的应用,然而,和前面提到的无人机在其他领域的应用一
样,依赖实时视频流和图像处理的决策应用往往会超过低成本无人机的本地数据处理能
力,或者延长执行某个决策动作所需的时间。
带宽、低时延高可靠、低功耗大连接的网络环境,在边缘计算环境中,计算任务可以在接近
数据源的计算资源上运行,它具有实时性、隐私保护和降低能耗等特点。
有如下已有工作:1、使用基于cloudlet的基础设施来减少使用移动云计算时的功耗和网络
延迟;2、重点从物理层安全方面考虑,研究无人机移动边缘计算系统的节能计算卸载技术;
3.卸载无人机工作过程中繁重的计算任务,同时实现了能耗、时间延迟和计算成本之间的
最佳折衷。在任务卸载方法选择方面,有工作建立了马尔可夫决策过程框架下的延迟最优
计算任务卸载问题,并提出了有效的一维搜索算法来寻找最优解。
机目标追踪场景中最主要的特征:随着无人机的移动,无人机上产生的任务是移动的,无人
机在追踪的过程中会飞出边缘节点的服务范围,所以无人机不能一直和一个边缘节点保持
连接,而且无人机发射功率的调整,可以减少无人机数据传输过程中的能耗。
发明内容
时间开销的权衡最优的问题。
2×1
地面上表示为q(t)∈R ,0≤t≤T,时间T被离散成M个时隙,即T=Mδt,其中,δt表示每个时
隙的长度,无人机在一个时隙中位置认为是不变的,无人机的轨迹近似离散为一个集合Q=
{qm,1≤m≤M},其中,qm表示时隙m中无人机的位置,无人机在M个时隙产生的M个任务表示S
{s1,s2,…,sM},其中,sm表示第M个任务的数据量大小,单位为bits。
第i个边缘节点,边缘节点ni的位置表示为wi∈R ,考虑到每个边缘节点的计算能力不同
和无人机实时移动,无人机到边缘节点的通信距离为变化的,无人机到每个边缘节点的通
信距离不同,无人机卸载到每个边缘节点的任务完成时间和产生的能耗也不同,假设在时
隙m,将边缘节点ni选择为计算节点,如下所示:
表示边缘节点ni的位置,wi∈R ,H表示表示无人机的飞行高度;
行高度。
缘节点,无人机到边缘节点的距离不同,系统的通信速率如下所示:
分配给节点ni的发射功率,B表示信道带宽,σ表示高斯白噪声功率, 表示距离d0=1m
时的信噪比, 表示无人机和边缘节点之间的信道,β0表示参考距离d0=1m处的信道功
率增益,qm表示时隙m中无人机的位置,wi表示边缘节点ni的位置,H表示表示无人机的飞行
高度。
其中,Rm,i(pm,i,dm,i)表示系统的通信速率,pm,i表示在时隙m中无人机
分配给节点ni的发射功率,dm,i表示无人机与边缘节点ni之间的距离,sm表示第M个任务的数
据量大小,单位为bits;将任务sm卸载到边缘节点ni的计算时间为: 其中,sm
表示第M个任务的数据量大小,w表示处理单位视频任务量需要的CPU周期,单位为周期数/
比特,fi表示边缘节点ni的CPU时钟频率,单位为周期数/秒;
间。
<i};
相对权重,β≥0;
制,最小化无人机能量开销与时间开销的权衡 优化问题如下所示:
m m‑1 m
位置和任务量大小构成,将无人机在每个时隙m的状态表示为x=(N ,A)∈X={1,2,…,
k}×{qm,sm},其中, 动作空间由选择的执行任务的节点和无人机发射功率
m m m
的大小构成,y =(N ,p)∈Y={1,2,…,k}×{Pn},其中,Pn表示发射功率可能取值的集合,
m
在每个时隙m开始时对状态x的观测,无人机遵从静态控制决策 从动作空
间中选择一个动作,其中, 表示卸载节点选择机制, 表示发射功率调整策略,
系统在一个状态(上一个任务所在执行节
点、无人机位置和任务量大小)选择相应的动作(计算节点和发射功率)之后,按照动作转移
m
的概率为1,系统的状态转移概率为1,给定一个决策 则{x:m∈M}是一个有
以下状态转移概率的可控的马尔科夫链,如下所示:
开销,C(x ,y)表示每个时隙的总开销,x表示初始状态, 表示策略;x=(N,A),存在一个
静态策略对所有策略来说是最优的;
报,将回报函数与原始的目标函数设置为负相关,如下所示:
到这个边缘节点时,将与该边缘节点有关的动作的Q值设置为一个很小的值,采用Q‑
learning强化学习方法,每个状态‑动作都有一个值Q(s,a),对于寻找最佳动作过程中的每
一步,智能体将每个状态‑动作的值Q(s,a)进行计算并存储在Q表中,将每个状态‑动作的值
Q(s,a)视为长期回报的期望,Q(s,a)的更新公式如下所示:
对于寻找最佳动作过程中的每一步,迭代每个状态‑动作的值Q(s,a)。
和能耗的影响,建立了基于边缘计算的无人机目标追踪的系统模型,研究无人机目标追踪
过程中的任务分配决策问题,将无人机目标追踪过程中的任务分配决策问题建模成马尔可
夫决策过程,基于强化学习中的Q学习设计求解算法对无人机目标追踪过程中的任务分配
决策问题进行求解,得出最佳的边缘节点选择方案和发射功率调整方案,实现任务卸载过
程中能量开销和时间开销权衡的最小化,提高无人机目标追踪系统的性能。
附图说明
具体实施方式
任务卸载方法及系统。
换节点对任务完成时间和能耗的影响建立基于边缘计算的无人机目标追踪的系统模型;步
骤2,通过研究无人机目标追踪过程中的任务分配决策问题,将无人机目标追踪过程中的任
务分配决策问题建模成马尔可夫决策过程;步骤3,基于强化学习中的Q学习设计求解算法,
对无人机目标追踪过程中的任务分配决策问题进行求解,得出最佳的边缘节点选择方案和
发射功率调整方案。
面边缘节点进行处理,然后反馈处理结果引导无人机实现成功追踪,综合考虑无人机到边
缘节点的距离、边缘节点处理能力、切换节点对任务完成时间和能耗的影响等因素,建立基
于边缘计算的无人机目标追踪的系统模型,将无人机目标追踪的任务分配决策问题建模成
马尔可夫决策过程,并设计了基于Q学习的求解算法,得出最佳的边缘节点选择方案和发射
功率调整方案,实现任务卸载过程中能量开销和时间开销权衡的最小化。
2×1
(m),无人机的飞行轨迹投影到地面上表示为q(t)∈R ,0≤t≤T,时间T被离散成M个时隙,
即T=Mδt,其中,δt表示每个时隙的长度,无人机在一个时隙中位置认为是不变的,无人机的
轨迹近似离散为一个集合Q={qm,1≤m≤M},其中,qm表示时隙m中无人机的位置,无人机在M
个时隙产生的M个任务表示S{s1,s2,…,sM},其中,sm表示第M个任务的数据量大小,单位为
bits。
n2,n3,…,nk}表示,ni表示第i个边缘节点,边缘节点ni的位置表示为wi∈R ,考虑到每个边
缘节点的计算能力不同和无人机实时移动,无人机到边缘节点的通信距离为变化的,无人
机到每个边缘节点的通信距离不同,无人机卸载到每个边缘节点的任务完成时间和产生的
能耗也不同,假设在时隙m,将边缘节点ni选择为计算节点,如下所示:
表示边缘节点ni的位置,wi∈R ,H表示表示无人机的飞行高度;
行高度。
距离dm,i,选择不同的边缘节点,无人机到边缘节点的距离不同,系统的通信速率如下所示:
分配给节点ni的发射功率,B表示信道带宽,σ表示高斯白噪声功率, 表示距离d0=1m
时的信噪比, 表示无人机和边缘节点之间的信道,β0表示参考距离d0=1m处的信道功
率增益,qm表示时隙m中无人机的位置,wi表示边缘节点ni的位置,H表示表示无人机的飞行
高度。
间,任务传输时间表示为: 其中,Rm,i(pm,i,dm,i)表示系统的通信速率,
pm,i表示在时隙m中无人机分配给节点ni的发射功率,dm,i表示无人机与边缘节点ni之间的距
离,sm表示第M个任务的数据量大小,单位为bits;将任务sm卸载到边缘节点ni的计算时间
为: 其中,sm表示第M个任务的数据量大小,w表示处理单位视频任务量需要的
CPU周期,单位为周期数/比特,fi表示边缘节点ni的CPU时钟频率,单位为周期数/秒;
间。
的能耗开销,如下所示:
<i};
相对权重,β≥0;
制,最小化无人机能量开销与时间开销的权衡 优化问题如下所示:
m
任务所在执行节点、无人机位置和任务量大小构成,将无人机在每个时隙m的状态表示为x
m‑1 m
=(N ,A)∈X{1,2,…,k}×{qm,sm},其中, 动作空间由选择的执行任务
m m m
的节点和无人机发射功率的大小构成,y=(N ,p)∈Y{1,2,…,k}×{Pn},其中,Pn表示发射
m
功率可能取值的集合,在每个时隙m开始时对状态x 的观测,无人机遵从静态控制决策
从动作空间中选择一个动作,其中, 表示卸载节点选择机制, 表
示发射功率调整策略, 系统在一个状态
(上一个任务所在执行节点、无人机位置和任务量大小)选择相应的动作(计算节点和发射
功率)之后,按照动作转移的概率为1,系统的状态转移概率为1,给定一个决策
m
则{x:m∈M}是一个有以下状态转移概率的可控的马尔科夫链,如下所示:
开销,C(x ,y)表示每个时隙的总开销,x 表示初始状态,表示策略;x=(N,A),存在一个
静态策略对所有策略来说是最优的;
强化学习的目标为最大化回报,将回报函数与原始的目标函数设置为负相关,如下所示:
满足条件,则在第一次选到这个边缘节点时,将与该边缘节点有关的动作的Q值设置为一个
很小的值,采用Q‑learning强化学习方法,每个状态‑动作都有一个值Q(s,a),对于寻找最
佳动作过程中的每一步,智能体将每个状态‑动作的值Q(s,a)进行计算并存储在Q表中,将
每个状态‑动作的值Q(s,a)视为长期回报的期望,Q(s,a)的更新公式如下所示:
寻找最佳动作过程中的每一步,迭代每个状态‑动作的值Q(s,a)。
程中的每一步来说,agent在状态x下,执行一个可能的动作y后,都会得到一个回报R(x,y),
强化学习的目标就是获得最大的回报,一般来说,奖励函数应该与目标函数相关,使用强化
学习解决无人机目标追踪过程中的任务分配决策问题,就必须将回报函数与要优化的目标
函数联系起来,优化目标是最小化总开销,强化学习的目标是最大化回报,设置的回报函数
应该与原始的目标函数成负相关,定义瞬时回报为R(x,y)=‑C(x,y),表示加权总开销的相
反数,得到最大的回报等同于获得了最小的加权总开销。随着系统规模的增大,卸载决策与
无人机发射功率组成的动作的可能取值会急速增长,不利于算法的运行和收敛。为了限制
动作空间的大小,在学习过程之前提出了一个预处理步骤,对于每个边缘节点,先根据无人
机到边缘节点的距离判断无人机是否在该边缘节点的服务范围内,如果不满足条件,则在
第一次选到这个边缘节点时,将与该边缘节点有关的动作的Q值设置为一个很小的值,在下
次迭代过程中就不会再选择这个动作,提高了效率。
边缘节点的处理能力存在差异性,以及切换节点对任务完成时间和能耗的影响等问题,建
立了基于边缘计算的无人机目标追踪的系统模型,研究无人机目标追踪过程中的任务分配
决策问题,将无人机目标追踪过程中的任务分配决策问题建模成马尔可夫决策过程,并基
于强化学习中的Q学习设计求解算法,得出最佳的边缘节点选择方案和发射功率调整方案,
任务卸载过程中能量开销和时间开销权衡的最小化。
应视为本发明的保护范围。