面向ET-DQN的卫星网络任务部署算法研究

刘治国,董效奇,汪 林,夏清雨,潘成胜,3

1(大连大学 通信与网络重点实验室,辽宁 大连 116622)

2(大连大学 环境与化学工程学院,辽宁 大连 116622)

3(南京信息工程大学 电子与信息工程学院,南京 211800)

0 引 言

随着大量物联网(Internet of Things,IoT)设备、虚拟现实(Virtual Reality,VR)、高清视频传输以及自动无人驾驶新兴应用的出现[1],第五代移动通信标准(5G)地面网络可能无法对森林、农村、山地和海洋等地区实现覆盖,然而在这些地区,物联网设备却广泛部署用于摄像信息处理以及信息收集,并产生大量的处理延迟.除此之外,地面网络的抗干扰和抗灾害能力较弱,不能够应对突发事件[2].由此第六代移动通信标准(6G)将地面网络与卫星通信集成,真正的做到了网络的全覆盖,同时又不受外部环境的影响[3].星地协同网络可以应用于许多有前途的领域,如智能交通系统、远程区域监控、灾难救援和大规模高速移动互联网接入,还能实现真正意义上的全球广域覆盖,真正的解决了地面网络的诸多问题[4].

而随着新兴应用的出现,部分应用需要大量的计算资源.例如,虚拟现实和高清视频流需要大量计算资源用于渲染和视频的编码和解码,自动驾驶车辆依赖大量计算进行自动控制[5].这些计算密集型应用对资源受限的终端设备的电池和计算能力带来了巨大挑战,由此云计算被提出.在云计算中,计算密集型应用被部署到具有集中和丰富计算资源的云服务器上.虽然云计算能降低用户的计算延迟和能耗,但它无法满足延迟敏感应用的需求,例如增强现实,因为终端用户和云服务器之间的传输距离很长,从而导致较大的传输延迟[6].为了解决这个问题,世界各学者对移动边缘计算(Mobile Edge Computing,MEC)进行了广泛的研究,利用网络边缘的计算资源来提供高效灵活的计算服务.将边缘计算技术引入星地协同网络,即将云计算平台扩展到网络边缘,为用户提供异构计算资源,同时使得用户可以在世界任何地方获取计算服务,从而改善用户服务体验,减少冗余网络流量[7].

然而,由于卫星MEC服务器计算能力和能耗都是十分有限的,只能同时部署一部分的服务请求,分配给每个服务的计算资源也十分有限.终端用户希望将尽可能多的任务转移到卫星边缘计算节点,从而减少任务处理延迟,改善用户体验.如果卫星边缘计算节点资源不足,用户设备的计算任务将发送至远程云进行处理,这无疑会增加服务请求的处理成本.

因此在地面网络稀疏环境下,面对卫星网络的资源和能量的有限性,制定高效的任务部署算法,降低处理时延和卫星系统能耗是当今卫星网络边缘计算研究的一大挑战.本文提出了SDN的卫星-地面联合部署网络架构SSGIN,并对融合边缘计算的SDN控制器进行设计,为远程终端提供强大的边缘-云计算服务.在该框架下,将任务部署问题表述为马尔可夫决策过程(Markov Decision Process,MDP),提出了改进的深度强化学习算法:经验竞选的DQN算法(Experience Tournament-DQN,ET-DQN),动态学习最优部署策略,以最小化任务处理时延和能耗.因此本文的贡献归纳为3点:

1)提出了SSGIN网络架构,并对融合边缘计算的SDN控制器进行设计.

2)提出了改进DQN算法:经验竞选的ET-DQN,在SSGIN网络架构下,对批量任务的处理时延和能耗作为优化目标,显著降低了优化问题的复杂性,并与基准算法相比,在时延和能耗方面获得了更好的性能.

3)在仿真结果中,将ET-DQN与传统的DQN算法、Prioritized-DQN的收敛性以及平均奖励以及方差进行了对比,在收敛性表现优秀,与Prioritized-DQN平均奖励提高近百分之16%.

1 相关研究

1.1 SDN卫星网络相关研究

SDN作为一种新兴的网络管理模式,能够有效提高卫星网络的资源管理水平,提高卫星网络的整体性能.Li等[8]人将SDN思想引入卫星网络以提高网络的管理和配置效率,设计了一种基于SDN的空地一体的多层网络结构,包括多层网络结构和虚拟化服务的部署.Toufik Ahmed等[9]结合SDN和NVF技术,针对于网络切片不同的阶段设计了相应的资源管理策略,实现了切片综合效益最大化.Qiu C等[10]人以资源角度出发,提出了基于SDN的天地一体化网络架构,并将整个网络的网络资源、缓存资源、计算资源一起,用于动态管理和联合编排.然而融合边缘计算的SDN空地一体的网络结构的研究却很少.

1.2 融合边缘计算的卫星网络相关研究

近些年来,国内外对边缘计算都进行了广泛的研究,在国际上,行业标准化权威组织 IEC 发布了垂直边缘智能(Vertical Edge Intelligence,VEI)白皮书,介绍了边缘计算对制造业和其他垂直行业的重要价值[11].信息和通信技术(Information and Communications Technology,ICT)领域的权威标准组织 ISO/IEC JTC1成立了边缘计算研究小组,推动边缘计算标准化工作[12].除了边缘计算各种标准相关标准、布局的研究外,任务卸载是边缘计算中解决边缘设备计算、存储和性能资源限制的主要方法.大量文献致力于针对不同场景和不同优化目标下的最优部署策略,文献[13-17]通过聚类和凸优化方法解决卫星网络中的资源分配和计算卸载,其中zhu等[15]人通过基于模拟退火的粒子群优化算法(SAPSO)获得满足延迟约束的最优分配方案.该类方法都是通过多项式时间复杂度来解决该类问题的,然而面对实时变化的卫星网络,上述方法一般需要重新进行搜索求解.文献[18-20]通过强化学习的相关算法解决任务部署问题,Zhang等[18]以时延和能耗为优化目标,通过地轨卫星实现对资源的整合和分配,提出一种协同计算卸载的方案.Cheng等[19]建立了一种空天地边缘-云网络,并在此基础上,提出了联合资源分配和任务调度方案,以有效地进行资源分配并调度卸载的任务.然而强化学习算法仍然存在经验池利用率低和网络训练的效率低下的问题.Xiong等[20]在DQN的基础上,对神经网络训练进行改进,由于DQN算法存在难以收敛以及过学习的问题,该文献对DQN网络进行了改进,采用多个重放存储器分别存储相互影响较小的经验,进一步改进了Q 网络的训练过程,然而设计多个重放存储器,经验选择策略仍然采用随机选择,没有根本上解决样本利用率低下的问题.除此以外,相关任务部署的研究对于针对任务部署的SDN控制器的具体设计,以及在卫星星座任务部署具体流程却很少提及.

综上所述,本文提出了SDN的卫星-地面联合部署网络架构,并对融合边缘计算的SDN控制器、以及卫星星座卸载流程进行设计.与此同时,为了解决DQN经验利用率和网络训练的效率低下的问题,提出改进的ET-DQN算法以解决任务部署问题.

2 系统模型和问题表述

基于SDN的卫星-地面联合部署网络架构(SDN-Space-Ground Integrated Network,SSGIN)如图1所示,其主要有地面网络和卫星网络两个部分组成,两者互为彼此的补充,实现全球无缝覆盖.

图1 基于SDN的卫星-地面联合部署网络架构示意图Fig.1 Schematic diagram of SDN based satellite ground joint deployment network architecture

卫星网络由LEO低轨卫星网络、GEO同步卫星网络以及相应的地面基础设施组成(信关站和卫星地面控制中心).LEO低轨卫星构成空间接入网络,每个LEO卫星可部署边缘计算节点为地面稀疏终端设备直接提供服务.GEO同步卫星得益于其覆盖范围广的特性,可作为SDN卫星网络的控制层,用以维护网络拓扑和状态信息,并以OpenFlow协议进行路由控制.

地面网络主要由地面通信系统组成,包括移动网络、转发网络、自组织移动网络、无线局域网和地面云计算中心.地面网络在人口密集区域可以为用户提供超高速的服务,而在农村和偏远地区、人口稀疏的区域,网络覆盖范围有限.

GEO卫星作为SSGIN网络架构的控制层,为了实现边缘计算任务部署的相关功能,需针对任务部署的SDN控制器进行设计.SDN控制器中有4个主要模块:网络拓扑管理模块、路由管理模块、边缘计算管理模块和任务部署模块.网络拓扑管理模块和路由管理模块与传统的SDN控制器相同,主要负责拓扑相关和路由相关的服务.为了实现边缘计算任务部署的相关功能,在SDN控制器中增加了边缘计算管理模块,主负责边缘计算节点的监控和管理.任务部署模块的作用是任务到达时,任务部署模块需从网络拓扑管理模块获取全局拓扑,从边缘计算节点管理模块获取节点信息,最后,将本文提出的算法用于求解任务的部署位置.

卫星网络的部署任务过程如下:

步骤1.地面多个用户向对应覆盖的卫星发起任务部署请求.

步骤2.对应的接收卫星统一向GEO卫星发送任务信息,GEO上有全局的SDN控制器,SDN控制器只的各个模块相互配合协调,最终由任务部署模块求解最佳部署位置.

步骤3.GEO控制器将对应的控制信息下发至LEO卫星上.

步骤4.低轨卫星通过流表控制将任务转发至指定部署位置.

步骤5.边缘计算节点经过任务处理将结果返给至任务发起卫星.

步骤6.将任务结果返回至地面用户.

3 成本模型

3.1 任务部署时延

3.1.1 任务处理时延

(1)

3.1.2 任务等待时延

由于本文卫星边缘计算服务器是以多核多线程并行的情况下提供服务的,需对节点sk上资源调度建立模型.在卫星sk上的wait_queuek,run_queuek分别表示等待任务集合和执行任务集合.本文采用非抢占式的先来先服务的思想来分配卫星边缘计算服务器的计算资源,该方式优点简单易实现.即对到来的任务如果不满足其需要获取的计算资源,那么需要进入wait_queuek等待资源分配满足后,再使其进入run_queuek队列执行,任务等待时延可分为以下两种情况:

(2)

3.1.3 任务传输时延

(3)

(4)

3.2 任务能耗

(5)

3.3 总成本模型

为了解决部署位置和计算资源分配不合理而导致任务处理时延过长、卫星能耗过大的问题,本文以任务部署时延和卫星能耗为优化目标,求解该批服务请求各自的最佳部署位置,以及分配的计算资源,使得其该批请求的任务处理时延和卫星能耗最小.

根据公式(4)、公式(5),最终得优化方程为:

(6a)

(6b)

elemi,k∈{0,1}i∈N,k∈M

(6c)

(6d)

(6e)

4 算法设计

4.1 ET-DQN算法

4.1.1 状态空间

状态空间state第1部分为当前边缘计算节点的状态矩阵,即将计算节点集合S={s1,s2,…,sp,scloud}组成矩阵s_sat:

(7)

第2部分为当前服务请求矩阵s_app:

(8)

4.1.2 动作空间

定义动作空间action:

(9)

4.1.3 奖励函数

(10)

(11)

其中θ和θ-分别代表估计网络与目标网络的参数值.

立即回报reward值高的经验对Agent的学习同样有很大的影响.因此本文以TD-error和立即回报reward作为各样本优先级的衡量标准.TD-error和reward立即回报越大,其优先级越高.样本的TD-error的优先级y1和reward的优先级分别y2为:

y1=reward+ρ

(12)

y2=|δ|+ρ

(13)

其中ρ为一正常数,以确保样本y1与y2不为0.那么最终优先级Y可表示为:

(14)

目前已知的经验回放方法都是以高优先级样本为主,而过度的使用优先级高的样本,低优先级的样本很有可能长时间不能被回放,从而造成Q网络过拟合的发生.由此本文提出经验竞选的DQN算法(Experience Tournament-DQN,ET-DQN).采用经验抽样策略,该抽样选择和遗传算法的选择策略十分类似,Schaul等[23]提出了Prioritized replay的采样策略,其采样方式采用轮盘赌策略,而竞选策略比轮盘赌无论是在通用性还是性能上都表现更佳.本文采用竞选策略来抽取批量的经验行经验回放.竞选策略流程图如图2所示.

图2 竞选策略流程图Fig.2 Campaign strategy flow chart

在竞选策略流程中,初始化神经网络的batchsize,并从经验池中随机获取n个经验,并计算每条经验的Y值,选出Y值经验最大的放入到批量训练集中,直到取满batchsize为止,并放入神经网络进行训练.

ET-DQN算法如算法1所示.

算法1.ET-DQN算法

1.初始化估计网络与目标网络的参数值θ,θ-,经验池容量为Z,批量经验数batchsize,遍历次数X,目标网络的更新步幅D,折扣因子γ,ε-greedy,策略π,学习率ρ,随机经验数n;

2.Start

3.Forepisode=1,Xdo

4.初始化环境,通过SDN控制器获取当前网络状态state={s_sat,s_app};

5.Fort=1,Hdo

6. 以ε的概率随机选择一个动作action,或者根据模型选择当前最优的action=maxactionQ*(state,action;θ);

7. 执行动作action,进入新状态state′和回报reward;

8. 通过κ=(state,action,state′,reward)经验样本计算该经验的优先级Y,并放入经验池;

9. 根据图2流程选取经验放入批量训练集中,并计算该批经验的y值:

10. 根据公式在(y-Q(state,action;θ))2上执行梯度下降,更新估计网络θ参数;

11. 如果t可被更新步幅D除尽,则将估计网络参数θ赋给目标网络θ-;

12.EndFor

13.EndFor

5 仿真实验

为了验证ET-DQN的算法性能,本次仿真实验使用STK仿真软件模拟信息传输网络,并使用python和pytorch搭建神经网络,进行训练.在仿真实验中,本文采用LEO卫星星座采用66颗卫星的Walker星座,即将轨道倾角90度的walker星座划分为6个轨道面,11颗低轨卫星分布在每个轨道平面上.通过3颗GEO卫星覆盖整个walker星座和地面,将SDN控制器部署至GEO卫星上,对walker星座的各个卫星进行监控,以做到全局的优化.

系统模拟仿真参数如表1所示.

表1 系统模拟参数Table 1 System simulation parameters

为验证ET-DQN的收敛性,仿真实验中,分别对传统DQN,Prioritized-DQN以及ET-DQN的loss函数进行测试,得出的结论如图3所示.

图3 loss对比图Fig.3 Loss comparison chart

由loss可知,传统的DQN算法在经过80000次迭代后依然难以收敛,仍然有较大的振幅,而Prioritized-DQN收敛速度很快,但是随着迭代次数增加,loss不降反升,说明此时的Prioritized-DQN经验池因为记忆缓存中的记忆单元不再独立.经过多次迭代,高优先级的存储经验被多次存入经验池,低优先级的经验逐渐消失,经验池有效的训练集变小,导致训练模型下降陷入局部最优.而ET-DQN算法,初期的收敛速度不及Prioritized-DQN,由于其由于抽样的随机性,并不会造成经验池利用不充分的问题,loss处于平稳下降状态,并在50000次后基本趋于稳定,在收敛性方面,ET-DQN算法是优于其他两种算法的.

在强化学习中,奖励reward是深度强化学习的最重要的指标参数,奖励reward对比图如图4所示.

图4 reward变化图Fig.4 Reward variation diagram

由图4可知,随着迭代次数的增加,3种算法在每个回合获得到的reward值都逐渐提高.表2中列举了在训练过程中,3种算法的均值与方差.由表2可得,ET-DQN算法在仿真实验中平均每个回合获得的回报最大,比Prioritized-DQN提高了近16%.二者的方差相近的情况下,在迭代40000次后,虽然每轮的奖励值略有波动,但获得的总体奖励值保持稳定.Prioritized-DQN收敛快,但在训练后期,仍然出现性能下降的情况,而DQN的reward均值最低,方差大,出现了较大的震荡.综上所述,ET-DQN算法在是优于其他两个算法的.

表2 实验效果对比Table 2 Comparison of experimental results

在经过算法的性能对比后,对ET-DQN训练完成的神经网络进行性能测试,除了DQN和Prioritized-DQN以外,需要加入基准算法进行对比:随机任务部署法:将应用随机部署至各个边缘计算节点处;卫星节点部署法:将所有任务部署至合适的卫星节点.

图5和图6中分别为时延与能耗性能对比.由图可知,ET-DQN、DQN和Prioritized-DQN对任务处理时延都有一定程度的优化,在任务规模小于15时,ET-DQN、DQN和Prioritized-DQN的对时延的优化效果很接近,甚至在图6中,任务规模为15时,Prioritized-DQN的性能优于ET-DQN,因为Prioritized-DQN训练时总是尽可能选择优先级高的经验进行训练,收敛快,任务量小时能展现出较好的性能.随着任务数量的增大,Prioritized-DQN则出现过拟合现象,导致其性能变差.而ET-DQN在任务量小时也展现了很好的性能,随着任务的增大,泛化能力更强,优化最为明显且稳定,由此可得ET-DQN训练出的模型在性能优化方面更为出色.

图5 不同任务放置策略时延性能对比Fig.5 Comparison of delay performance of different task placement strategies

图6 不同任务放置策略能耗对比Fig.6 Comparison of energy consumption of different task placement strategies

6 总结和展望

为了解决在卫星边缘计算中,部署位置和计算资源分配不合理而导致任务处理时延过长、卫星能耗过大的问题,本文提出了基于SDN的卫星-地面联合部署网络架构SSGIN,同时对卫星网络的成本模型进行分析,并改进了经典DQN算法的经验池利用率低、过估计和难收敛的问题:提出ET-DQN以优化任务部署的时延与能耗.在仿真实验中,对ET-DQN算法的收敛性、泛化性以及优化性能进行测试.仿真结果表明,所提出的任务部署算法能够有效地减少了任务计算的处理延迟和系统能耗,并且算法能够稳定地进行训练和收敛.与典型的强化学习算法相比,学习效率明显提高,能够有效解决经典DQN算法经验池利用率低,过估计以及难收敛的问题.ET-DQN虽能提提高传统DQN的收敛速度,然而相较于Prioritized-DQN仍然收敛速度稍慢,而如何提高深度强化学习算法的收敛速度仍然需要后续的研究.