李 斌,徐天成

(1.南京信息工程大学 计算机学院,南京210044;2.南京信息工程大学 江苏省大气环境与装备技术协同创新中心,南京 210044)

0 引 言

随着5G、物联网和人工智能的融合与快速发展,以及日益增长的用户资源需求,利用移动边缘计算(Mobile Edge Computing,MEC)在网络边缘卸载任务,已成为解决此类问题的一个出色的方案[1-2]。其优势在于能够为网络边缘用户提供近距离通信,并且有效降低了计算密集型应用的通信开销和计算时延,同时有利于缓解网络和数据中心的计算压力[3]。物联网应用程序中的计算任务之间普遍存在一定的相关性[4],如果当前任务的前驱任务没有被优先执行,那么调度该任务会产生额外的等待时间甚至死锁,这将对系统的实时性和稳定性产生较大影响。通常,移动终端应用软件可以被建模为有向无环图(Directed Acyclic Graph,DAG),以实现计算密集型应用的调度问题。

为了解决用户资源和计算能力有限的问题,研究者提出引入终端直通(Device-to-Device,D2D)技术的卸载模式作为MEC的有效补充[5],旨在将丰富的计算和存储资源协同控制和管理起来,以完成密集的计算任务[6-8]。同时,未来物联网、边缘计算网络等新网络场景的快速发展,智能设备数量和用户需求也随之激增,如何将有限的计算、带宽和存储等网络资源充分利用起来,并在大量的终端数据上实现智能管控,以获得更高效的网络性能和服务质量,是实现这些5G应用需要解决的热点研究问题之一。

关于D2D和MEC一体化的工作已有相关研究[9-13],但主要考虑了任务的时延与能耗,鲜少考虑服务器有限资源下任务具有相关性的卸载情况。同时,因其没有考虑用户移动性与任务多样性,难以适应动态变化的物联网场景。

用户的移动性使得卸载决策高度动态,因此,如何通过考虑用户移动性驱动的网络状态不确定性来设计高效的任务调度和资源分配策略,以增强分布式系统中移动用户的任务卸载体验,成为了一个重要的研究方向[14]。目前,越来越多的学者试图用深度强化学习(Deep Reinforcement Learning,DRL)的方法来解决这一问题[15],通过构建自学习能力更强的神经网络来近似表示Q值。作为智能体的每个卸载节点学会基于与环境的交互做出计算卸载的决策。通过从经验中优化计算卸载策略,从长远来看,系统时延被最小化。

与现有文献不同,本文提出了一种结合移动边缘计算与无线传能的物联网架构,建立D2D辅助移动用户卸载数据模型。这种架构联合优化任务调度和卸载策略问题,最大程度地降低了系统执行时延。本文的贡献主要体现在三个方面:一是对具有多用户的MEC系统的任务调度和卸载问题进行了建模,研究了任务调度和任务卸载策略的联合问题,目标为最小化系统执行时延;二是提出了一种基于Dueling Double DQN(D3QN)的计算卸载算法,以实现动态任务卸载与资源智能管控;三是提出了基于改进的深度优先搜索(Depth First Search,DFS)算法解决了任务卸载调度问题。仿真结果证实了本文所提算法的可靠性和有效性。

1 基于相关性的任务调度算法

1.1 任务的相关性建模

任务的相关性通常用一个有向无环图表示,如图1所示。G=〈V,E〉为一个二元组,其中,V是任务节点的集合,vi表示第i个任务,E⊂V×V表示有向边集合。两个任务节点之间存在有向边表示这两个任务具有相关性,且发出有向边的任务为有向边指向任务的前驱任务,后继任务只有在其前驱任务全部完成后才可执行。在t时刻,移动终端将任务信息和用户坐标发送给基站,基站根据用户的数据和位置信息使用基于任务相关性的D3QN算法训练移动终端的卸载策略,训练完成后智能体将卸载决策发送给移动终端,移动终端根据卸载策略来判断任务的执行模式。

图1 任务执行架构

1.2 任务的优先级

(1)

pi数值越大,任务的优先级越高,具体过程如基于改进的DFS任务调度算法(算法1)所示。首先访问图中某一未访问的顶点v1,然后由v1出发,访问与v1邻接且未被访问的任一顶点v2,再访问与v2邻接且未被访问的任一顶点v3,重复上述过程。当不能再继续向下访问时,依次退回到最近被访问的顶点,若它还有邻接顶点未被访问过,则从该点开始继续上述搜索过程,直到图中所有顶点均被访问过为止。

算法1具体描述如下:

输入:DAG图

输出:拓扑排序之后的顶点

有向图中具有多个入度为0的顶点时,选择优先级高的顶点v1进栈;

依次从v1的各个未被访问的邻接点进行深度优先搜索遍历图;

如果s栈为空,则失败退出,否则继续;

从栈顶取出顶点到数组中,然后将该节点所有连接的节点的入度都减1;

如果当前顶点的出度为0或已访问,则回退一步并转向3;

继续根据DFS算法遍历后面的节点;

2 系统模型

本文考虑一个支持无线能量获取D2D通信的协同MEC网络,其中空闲和资源充裕的设备(如笔记本、平板电脑、手机等可以作为边缘节点)通过和资源有限的用户设备(User Device,UD)建立直接的D2D链路,以促进计算卸载。该系统模型由k个用户、多天线的基站和M个D2D设备组成,移动用户的任务沿着用户的轨迹被卸载到D2D设备或基站上,如图2所示。

图2 系统模型

本文假设UDk以一定的速度和角度步行,同时,UDk有I个相互依赖的计算密集型任务要执行,用集合I={1,2,…,i}表示。在UDk行走的道路上,分布着笔记本、平板电脑、手机等M个D2D设备,用集合M={1,2,…,m}表示。考虑一种网络辅助架构,其中基站拥有全局网络信息,包括关于用户移动性和任务的细节。对于任务卸载,UDk可以在基站的帮助下通过建立直接的D2D链路连接到附近的D2D设备。基站可检测出UDk的位置,以便将其任务调度到D2D设备,使计算卸载总时延最小化。为了简化计算模型,UDk和D2D设备均只考虑装配一根天线。为了避免用户数据卸载之间的干扰,假设所考虑的网络以时分多址方式工作。时间块T被划分为I个阶段,其中,ατ为无线能量传输,(1-α)τ为分配给UDk计算卸载的时间。

2.1 能量捕获模型

在能量捕获阶段,基站以功率Pk,n来广播能量射频信号,同时,k个移动终端从射频信号中捕获能量。在时间间隔为ατ的无线能量传输中,UDk收获的能量为

Ek,i=ηPk,ihk,iατ,∀i∈N。

(2)

式中:常数η∈(0,1)表示能量转换效率因子;Pk,n表示基站在第i个任务给用户k发射的信号功率;hk,n表示UDk和基站之间在第i个任务的无线信道增益。由于信道互易性,假设上行链路和下行链路的信道增益相同。依据文献[16-17],本文采用了式(2)所示的线性能量捕获模型。

2.2 用户移动模型

假设UDk的轨迹在[0,T]内可获得,小区空间划分为二维空间,λk(t)={x(t),y(t)},T={1,2,…,t}表示用户k在t时隙所在的位置。由于其有限的处理能力,UDk可以选择将任务卸载到附近的D2D进行计算。λm={xm,ym},M={1,2,…,m}表示第m个D2D的位置。

2.3 任务卸载模型

在持续时间T内,每个用户以一个确定概率随机生成I个任务,k个用户同时进行执行任务。本文用Υk,n来表示是否有任务请求,Υk,n=1表示用户k在第n时隙有一个任务请求,Υk,n=0表示用户k在第n时隙没有任务请求。UDk的计算任务可由TKk,i(ci,ai,di,pi)表示,其中,ci表示任务卸载时本地设备需向外传输的数据量,ai表示处理该任务所需的机器语言指令数。对于计算密集型任务,每个任务必须在di内完成,所以每个任务执行时间应该小于时隙长度τ。

(3)

(4)

UD在本地计算模式下的能耗定义为

(5)

(6)

UDk在D2D卸载模式下的上传任务能耗定义为

(7)

因此,UDk在D2D卸载模式下的处理时延定义为

(8)

UDk在D2D卸载模式下的计算能耗定义为

(9)

根据式(4)～(7),UDk在D2D卸载模式下的执行时延和能耗分别表示为

(10)

(11)

(12)

UDk在D2D辅助边缘计算模式下的上传任务能耗定义为

(13)

根据式(10)～(13),UDk在D2D辅助边缘计算模式下的执行时延和能耗分别表示为

(14)

(15)

3 问题描述

在这项工作中,本文的研究目标是最小化时延约束下任务执行的总时延,包括本地执行时间、D2D卸载时间和卸载到基站时间,可表示为

(16)

为了减少卸载时延,利用UDk移动过程中不同时隙的位置信息进行任务卸载决策,故本文的研究问题形式化描述如下:

(17)

式(17)给出了以任务卸载决策为优化变量的目标函数;约束C1表明用户最多只能选择一种模式来完成它的任务;约束C2表明采集的能量需要大于任务计算所需的能量;约束C3表明任务只能全部卸载;约束C4表明分配给移动用户的计算资源不能超过MEC服务器拥有的资源;约束C5表明如果用户选择3种模式中的一种来完成它的任务,其时延不能超过最大时延;约束C6表明移动用户最多同时连接一个D2D设备;约束C7中表示UDk和D2D的传输功率以及MEC服务器的计算资源分别是非负的。可见,优化问题(17)含有多个离散的决策变量,是一个混合整数非线性规划问题,很难快速求得最优解。本文提出基于深度强化学习的D3QN算法来解决此问题。

4 基于深度强化学习的算法设计

本文采用基于D3QN的计算卸载算法求解建立的D2D通信的协同MEC网络中优化任务卸载策略问题,求解目标是通过优化卸载决策变量,最小化系统执行时延。为解决具有高维状态空间的环境问题,深度强化学习将深度神经网络与强化学习的决策能力相结合,通过使用卷积神经网络对Q-table做函数拟合。由于本文研究的问题是移动场景下任务卸载的决策,随着用户的不断移动,环境也开始发生动态变化。传统的方案使用Q-learning算法来探索未知环境,由于它是通过计算每个动作的Q值进行决策,所以会在某些条件下高估动作值。因此,本文提出使用D3QN方案是一种有效的改进,通过在DQN和DDQN的基础上引入竞争网络结构,神经网络不再直接输出Q值而是输出状态价值函数和优势函数。解决Q值过估计问题的同时,拟合获得更准确的Q值。

4.1 基于D3QN的计算卸载

为了使用D3QN算法,首先将计算卸载问题转化为一个优化问题。通过优化任务卸载,实现了系统时延的最小化。由于优化问题是马尔科夫问题,首先将其建模为MDP问题。

状态空间:S={G,x,y},G代表已调度完成的任务序列,UDk在第t个时隙内的状态为其自身的位置(xk,t为UDk的横坐标,yk,t为UDk的纵坐标)。

(18)

D3QN中使用状态价值和动作优势来聚合Q值得网络设计,可以降低不同状态下动作的估计误差,即

(19)

式中:A(s,a)为动作优势函数;|A|为动作维度,V(s)为状态价值函数。

对于D3QN,不是在目标网络里面直接搜索最大Q值的动作,而是先在预测网络中找出最大Q值对应的动作,即

(20)

然后利用选取出来的动作在目标网络里面去计算目标Q值,即

(21)

式中:λ为折扣因子。综合定义为

(22)

L(θ)=

(23)

4.2 基于D3QN的时间最小化算法

本文所提D3QN算法的框架如图3所示,具体实现过程如下:首先,初始化预测网络、目标网络和回放空间(算法2中的第1行);其次,输入UD初始位置;接下来,利用ε-greedy选择并执行动作at(算法2中的第5行);在执行动作at后,获得即时奖励rt和新状态st+1(算法2中的第6～7行),并将记忆(st,at,rt,st+1)存储到D(算法2中的第8行);然后,从回放空间中随机抽取K个样本,通过计算损失函数更新目标网络的参数(算法2中的第10～13行)。

图3 D3QN算法流程

基于D3QN的时延最小化算法(算法2)具体描述如下:

输入:UD初始位置,已调度完成的任务序列

输出:移动过程中使得系统时延最小化的卸载决策

2.for episode =1:N

3. 获取初始状态s;

4. for episode =0:T-1;

5. 将st输入到预测网络中,采用ε-greedy获得动作at;

6. 执行动作at,利用式(18)计算即时奖励rt;

7. 然后获得即时奖励rt和新状态st+1;

8. 存储记忆(st,at,rt,st+1)到D;

9. 从D随机抽取K个样本;

10. 根据式(18)计算目标Q值;

11. 根据式(23)计算损失函数,反向传播更新θ;

12. 更新目标网络参数;

13. end for

14.end for

5 仿真结果与分析

5.1 参数设置

5.2 数值分析

为了充分验证本文所提算法的有效性,与贪心算法、Q-learning和DQN 3种算法进行了性能对比。

图4给出了在取不同折扣因子时D3QN算法随时间周期变化的收敛图。折扣因子是对未来奖励的衰减值,代表了当前奖励与未来奖励的重要性。λ越大则智能体越重视历史经验,历史经验对未来奖励的影响越大。当λ=0.5和λ=0.99时,奖励值差别较大,原因在于过大或过低的折扣因子不利于智能体的探索。D3QN算法曲线随着迭代次数的增加逐渐递减,在经过大约50个时间周期后趋近于收敛。算法训练200个周期,获得了训练回报。

图4 所提算法收敛性

图5给出了任务执行时延和用户数量之间的变化曲线。通过模拟2～10个用户数量(以2递增),比较4种算法的任务执行时延。如图5所示,系统时延随着用户个数的增加而增大。这是由于用户数的增加,导致系统需要更大的时延开销,从而使得任务执行时延增加。可以观察到,贪心算法、Q-learning和DQN三种算法系统时延较高,本文所提出的D3QN算法的实验结果更优。

图5 任务执行时延随用户数量的变化

图6反映了不同移动速度对系统时延的影响情况。观察图6可知,随着用户移动速度的增大,传输时延增加,从而系统时延不断增加。分别模拟了1～5 m的移动速度(以1递增),比较4种算法的执行时延。当用户移动速度大于3 m/s时,本文提出的D3QN算法达到的时延效果比贪心算法、Q-learning和DQN算法要好。

图6 不同移动速度下的算法性能对比图

为了进一步验证本文提出的D2D协同计算的性能,图7给出了D2D数量对不同方案的任务执行时延的影响情况。可以看出,随着D2D数量的增加,任务执行时延在不断减少。这是因为D2D数量的增加丰富了用户卸载的选择,可以有效减少传输时延。

图7 任务执行时延与D2D数量的关系

6 结束语

本文提出了一种融合D2D的两层边缘计算架构,并引入D2D协作中继技术用于辅助用户接入远端边缘服务器。考虑到用户移动性、任务相关性和任务卸载时延约束的特性,将任务卸载问题表述为时延最小化的混合整数非线性规划问题,并进一步提出了基于深度强化学习的D3QN算法来实时优化任务卸载决策变量。仿真结果表明,所提出的D2D协同计算方案在计算资源紧张的情况下,能有效降低移动用户的任务执行时延且优化决策的收敛性较好。在未来的工作中,将研究在对任务调度的同时考虑对任务节点的调度。