无人机基站辅助的内容缓存多目标优化策略

纪洪运,沈 航,白光伟

(南京工业大学 计算机科学与技术学院,南京 211816)

1 引 言

在新一代无线通信网络中,各种新兴无线多媒体通信业务日趋普及.字节跳动旗下APP“抖音”最新发布的《2020抖音数据报告》显示,截止2020年12月,抖音日均视频搜索量突破4亿,日活跃用户突破6亿.以短视频平台为代表的新兴移动终端应用将以往web通信中对信息流的请求变为推送,即用户安装运行相关的APP后,应用服务提供商会推荐大量如视频、新闻等内容供用户浏览.随着用户体量的增长,短视频类平台对于网络负载的影响已经不容忽视.

在上述的短视频类应用中,视频文件以内容为中心存在明显的聚类特征,应用服务提供商会推荐大量的视频内容,而用户主动搜索的内容也存在明显的重复性,如在2020年COVID-19病毒肆虐期间,话题为“共同抗疫”的有关视频播放量达423亿次.除了具有内容为中心的时效性外,相关的国内及国际主流手机应用上看到人们关心的视频内容具有地理上的区域特征,如社交软件内部的同城板块、个人博客中带有地理位置信息的标注戳等,都强化了社交网络中的地理位置类标签与信息本身的耦合性.

当无线数据的业务量及数据流量大幅增长,现有的无线频谱资源会面临不足以支持大量的无线多媒体通信需求的问题,网络运营商需要采取有效手段以减少重复的多媒体数据传输和下载.

一方面,利用移动边缘计算(Mobile Edge Computing,MEC)技术可以将计算、存储、处理功能放置在网络边缘的边缘服务器处,从而大大缓解骨干网的负担.在存储方面具体来说,通过放置靠近用户终端的缓存设备以减少重复的文件传输.缓存设备存储热门文件,并在用户请求时直接发送给用户,避免访问骨干网而产生不必要的流量负载.

另一方面,近年来,由于体积小,价格低和灵活性高,无人机(Unmanned Aerial Vehicle,UAV)已广泛用于许多行业,以上优势有利于解决传统通信中如基站部署成本高和对特殊环境的适应性较差等问题.通过将UAV部署为空中基站(Drone Base Station,DBS)辅助无线通信网络,可以减轻某些热点地区高峰时段的流量压力[1].

本文针对短视频类应用使用场景,构建一个无线网络通信区域模型,并采用无人机基站作为移动边缘计算中的边缘服务器.通过对无人机基站中高速缓存和无人机基站移动路径的优化,缓解大量无线多媒体通信场景下通信资源不足的问题.

为了对系统缓存部署的优良程度进行评估,本文引入文献[2]中的系统平均缓存命中率(The average cache hit ratio of the system),作为评价本系统对于文件请求响应和节约高速缓存的重要指标.在技术使用的选择上,深度强化学习(Deep Reinforcement Learning,DRL)将深度学习(Deep Learning,DL)的感知能力和强化学习(Reinforcement Learning,RL)的决策能力相结合,可以直接根据输入的信息进行预测和控制,是一种更接近人类思维方式的人工智能方法[3].本文提出一种基于深度强化学习的无人机基站缓存联合解决策略(Drone Base Station Caching with Deep Reinforcement Learning,DC-DRL),其核心思想是,根据视频文件内容的流行度预测设计边缘服务器的内容缓存策略,并与无人机基站的部署调度相结合,进行多因素、多目标的联合优化,以提升边缘节点高速缓存的系统平均缓存命中率.

2 相关工作

无线数据业务量急剧增长业务增长模式的驱动力已经由以连接为中心的通信(例如语音和短消息)向以内容为中心的通信(例如视频流和音乐)转移[4].为提升网络容量以满足需求,各大运营商部署了密集的小基站,但这对回传链路造成了极大的负担[4].而从移动用户的角度来看,由于MEC服务器位于网络的边缘,非常接近移动设备的位置,因此可以结合用户移动性和内容访问日志来优化使用体验[5].

一些现有文献涉及基站内容缓存以及无人机基站调度的研究成果,如在边缘缓存文件放置方面,文献[3]中研究了具有移动边缘计算功能的5G网络中小型基站的内容缓存策略,并给出了相对优化的MyCaching算法;文献[6]中研究了无感知环境下移动边缘计算网络中的缓存放置优化问题;文献[7]中研究了车联网环境下缓存文件预测机制;文献[2,8,9]研究了D2D条件下边缘协同缓存问题;文献[10]提出了一种基于高速缓存的无人机优化物联网系统中的多媒体数据吞吐量最大化的方法.在无人机基站联合部署方面,文献[11]综述了5G无线网络下多层无人机基站架构的挑战、趋势和前景;文献[12-14]研究了多无人机基站系统的能耗优化问题;文献[15]研究了多无人机调度中的3D轨迹计划优化问题;文献[16]提出了一种基于多智能体深度强化学习的分布式干扰协调策略.

但以上研究大多针对无线网络或无人机部署方面单一目标进行优化,然而在实际应用中,区域内无线网络面临的问题大多是多因素、多目标联合优化问题,与所处时间以及空间有着难以忽略的关联性.例如,在以上考虑系统缓存放置及分发的研究中,都忽略了区域内文件流行度与二维平面上请求内容的关系;在以上考虑无人机移动性问题的研究中,很少有将无人机基站自身属性(如所携带的缓存内容)考虑在内的情况.文献[4]虽然同时考虑到了移动基站与缓存预测的结合,然而其使用的是基于文件相似性和用户相似性的单个用户内容偏好预测算法及无人机部署方面的聚类算法,通过暴力求解的方式给出最终答案,大大增加了网络内的计算负担.近年来,使用机器学习的方法解决过去难以解决的问题成为新风潮,机器学习所拥有的的从经验中得出结论的方法可以有效解决传统方法中计算量过大而难以求解的问题,其中,人们多用循环神经网络(Recurrent Neural Network,RNN)处理序列变化的数据.

本文采用的长短期记忆(Long short term memory,LSTM)神经网络来处理时变的文件参数序列,相比普通的循环神经网络,LSTM能够在更长的序列中有更好的表现.在强化学习中,Actor-Critic算法合并了Value-based和Policy-based两类强化学习算法,可以为DBS在空间移动选择上提供强有力的帮助.本文将长短期记忆神经网络输出的文件流行度的预测结果与MyCaching方法[3]的文件放置与更新的策略有机结合,将输出的带有时序特征的网络文件流行度预测结果作为指导无人机基站移动的强化学习网络的关键输入动作,以最大化系统平均缓存命中率.

3 系统模型

3.1 问题描述

本文拟解决缓存放置和无人机部署的联合优化问题.这是一个NP难问题,难以求解.这个优化问题中的变量都是离散的,如果在算法中使用暴力求解的方式,该算法的复杂度将远超相关设备的计算能力,并且难以实现.为了有效地解决这个问题,本文将其分解为两个子问题,并提出了相应的算法,即具有缓存功能的无人机基站的内容缓存策略,以及宏基站控制下的集中式无人机部署方案.

3.2 模型描述

如图1所示,在由一个具有宏基站及若干个无人机基站和移动设备组成的区域性无线网络中,若干个空中无人机基站为地面用户提供服务,无人机自身携带高速缓存,同时可以通过宏基站向核心网请求内容.该示例图中可以明显看出无人机基站(DBS)与地面宏基站及地面用户的从属关系.从上面的讨论中可以看出,缓存文件流行度及DBS的移动性对DBS缓存内容有着显著的影响.基于此,本文将定义一个基于请求文件流行度与DBS移动性的DBS缓存模型.

分别用m和n表示DBS和移动蜂窝网络中文件请求设备的数量.设N={n1,n2,n3,n4…}为蜂窝移动网络中文件请求设备的集合.无人机基站可以连接到宏基站和地面用户,并且每个用户都可以独立地请求所需内容.

图1 支持高速缓存的无人机辅助的蜂窝网络Fig.1 Cache-enabling UAV-assisted cellular networks

短视频类APP中,应用服务提供商会向用户推送短视频内容,用户也可根据自身爱好搜索浏览一些带有“话题标签”的短视频内容.因此,由有限数量的不同内容文件组成的文件库包含应用服务提供商推送的和用户额外请求的短视频类文件.设F={f1,f2,f3,f4…}为文件库内文件的集合.本文使用每个用户对每个文件的请求频率来表示这个文件的受欢迎程度.首先进行无人机基站缓存的初始化,随着无人机基站上的高速缓存被文件库中文件填满,每个无人机的缓存文件进行替换更新.假设每个用户设备基于APP自有推送需要和用户在APP内的搜索指令对无人机基站发出请求,并且单位时间内每次请求一个内容.用p(i)表示第i个文件f被请求的概率,作为第i个文件的流行度.本文中选取流行度存最高的若干个文件替换之前的文件存储于高速缓存,直至高速缓存中的空间再次被填满.同时,每个无人机基站可以借由宏基站从核心网请求内容.假定待请求文件数为F,单个无人机的缓存大小为C,系统时间为T={t1,t2,t3,…,tz},单个文件f大小为ω.在本文中的无人机基站组成的网络中,无人机基站m根据预测的每一个内容文件在该DBS的文件流行度和无人机基站缓存状态替换该DBS的缓存内容.在本文中,第i个待缓存文件fi在本地的流行度被定义为为pi(m,[tz,tz+1)),它由[tz,tz+1)内,待缓存文件fi将被请求的次数决定.则无人机基站m上高速缓存对于文件F的缓存状态向量为[s1(m,[tz,tz+1)),…,sF(m,[tz,tz+1))]T,其中si(m,[tz,tz+1))=

(1)

本文考虑在被划分数量为K个小区域的2D目标区域中实现多无人机通信覆盖的场景,在图1中,M={m1,m2,m3,m4…}为一组无人机,作为固定高度的移动基站为地面用户提供互联网服务.每个DBS都有通信距离R作为连通性约束,当它们与它们连接的设备的距离大于R时,二者将失去连接.由于无人机飞行在一定的高度,所以覆盖范围R0≤R始终成立.一般情况下,一个小区域中心的兴趣点(Point of Interests,PoI)被认为是该小区的服务点.为避免DBS之间的信道干扰,DBS之间的距离R1>R.在假定场景中,无人机从随机位置起飞,学习以方向θ∈[0,2π)和距离l∈[0,lmax)移动,或者简单地悬停在当前位置.

为了实现无人机辅助蜂窝移动网络对地面用户的有效覆盖,本文引入文献[13]中所采用的系统平均覆盖分数作为一个“时空”的度量,用以衡量某个特定的PoI在过去的t个时段中是如何被DBS通信覆盖的,因此,可以得到式(2):

(2)

其中ωt(b)表示在时段t时,一个PoIb被覆盖的指数,则ct(b)∈[0,1].在完成T个时段的作业后,可以计算该点在时间段的平均覆盖率,如式(3)所示:

(3)

则该次作业的最终平均覆盖率分数是Ct=Ct|t=T.

3.3 优化目标

边缘服务器提供服务时,对于内容缓存的效率可以由多个维度表征,其中,请求文件的缓存命中率是对于缓存效率的一个行之有效的量化方法.

本文的优化目标是最大化系统整体的平均缓存命中率,具体地,通过对无人机基站m和时间间隔[tz,tz+1)进行拆分,得到缓存状态向量s(m,[tz,tz+1)).则系统平均缓存命中率可以表示为式(4):

(4)

式(4)中:Is(m,[tz,tz+1))(i(k))为指示函数,由0和1表征,分别代表待请求文件fi在被用户请求时未在和已在无人机基站m的高速缓存上.由此,将时间段z与无人机基站数m综合起来,可以得到式(5)中的最大化系统平均缓存命中率:

(5)

式(5)中:s(m,[tz,tz+1))是待优化变量,ω=[ω1,…,ωF]T表示整个内容文件库F中各个内容文件的大小,z为各个时间段,m为各个无人机基站.

在实际的网络内容文件缓存和分发问题中,往往内容文件的大小都是长短不一的,为了使问题拆分方便解决,本文将每一个长短不一的内容文件拆分为不同数量、同等大小的小文件块,因此,在缓存阶段,本文要解决的是同等大小的小文件块的选择排序问题,具体地,本文将对每个无人机m上的文件块根据pi(m,[tz,tz+1))进行排序,直到填满缓存空间Cm,而对于这种背包问题的相关处理前人已有许多研究[17].那么在引入文件流行度后问题式(5)可以写成式(6)中的形式:

(6)

式(6)中的si(m,[tz,tz+1))是本文中的待优化变量.根据章节3.1中所述,此NP难问题直接求解会变得非常复杂,因为它涉及到多维部署和多维文件概率求解.因此,在这一部分,本文将联合优化问题划分为两个复杂度较低的次优解.从时间间隔[tz,tz+1)和无人机基站m入手可以解耦合为许多背包容量为Cm、品数为F的0-1背包问题.

在缓存文件的分发阶段,无人机基站接到文件请求后首先在本地搜寻相应缓存,若没有找到则向干路网请求响应文件,因此,提高本文提出的系统内平均缓存命中率可以减少系统通过宏基站向干路网请求的流量,减少干路网流量负载.

4 DC-DRL策略设计

根据以上讨论,本文考虑了应用内容文件的自带参数,将无人机基站(DBS)中的缓存文件流行度与无人机移动轨迹进行联合优化,即设计一种同时考虑时、空因素的缓存策略.本策略通过将由LSTM预测所生成的文件流行度序列进行比较排序作为Actor-Critic网络的输入序列,得出本文所需要的无人机基站缓存文件更新以及无人机的移动路径,即在内层使用神经网络进行缓存内容放置与更新的基础上,在外层的无人机位置调度方面,使用深度强化学习的Actor-Critic算法来辅助对无人机的位置调度.由于实际的深度强化学习过程是集中在宏基站的中央控制器(Central controller)上进行,只需把生成结果发送至DBS,因此可以有效节约DBS的计算负担和数据传输流量.

4.1 基于LSTM的文件流行度预测

在缓存文件流行度的预测方面,利用长短期记忆神经网络进行下一时段文件流行度的预测,相较于传统方法,更加强调时间序列对于缓存文件的重要作用,通过引入缓存矩阵,可以将文件存储的二元性有效表示并方便进行动作处理运算.本文中的缓存策略取决于内容流行度预测,在时间段t中预测到的t+1时间段内的流行度与实际t+1时间段的流行度越接近,用户就越有可能在时间段t+1中的请求缓存正确的内容,因此需要提高预测的准确性.考虑到内容文件流行度和用户轨迹都是与时间有关的序列,长短期记忆(LSTM)深度学习模型由一个记忆单元和几个门组成.如图2所示,本文中的LSTM单元的结构由记忆元组(memory cell)和非线性的门单元(nonlinear gating unit)组成,使用记忆元组可以保持系统的状态,使用非线性的门单元可以在每一个时间点调节记忆元组的输入、输出信息.每个递归的神经网络都可以分解成无数个基本重复单元,本文使用了4个神经网络层并且以图2关系进行交互.

图2 DC-DRL中的LSTM网络模型Fig.2 Long Short-Term memory model in DC-DRL

由于现有深度学习框架大多应用于图像处理领域,其中所处理的图像文件以矩阵形式存储和处理,本文因此受到启发,将缓存文件提取特征后的状态以矩阵形式表示,则用户请求文件的离散流行度分布为式(7):

(7)

其中pij表示第i个用户请求第j个文件的概率.矩阵是行随机的,因为第i行表示第i个用户的离散概率分布,因此,第i行中所有元素的总和等于1.随着文件数量的增长,该矩阵可能变得稀疏.

在Python官方网站给出的模型框架下,本文考虑到所需要的流行度结果,对文件进行处理和特征提取,在算法1中给出了本文的预测流程.

算法1.基于LSTM的文件流行度预测算法

输入:宏基站接收到的需求序列

输出:文件流行度预测序列

1. 导入相关包

2. 定义预测步长、回溯时间和训练次数

3. forf=1,…,Fdo

4. 读入基站接收需求序列

5. 定义分割数据函数

6. 生成随机种子

7. 定义训练集大小

8. 数据集切分

9. 定义前瞻步长

10. 分割训练集和测试集

11. 重新设置数据格式

12. 构建 LSTM 网络

13. 带入训练集进行训练学习

14. 定义预测步长

15. 预测

16. 累加记录预测结果

17. 更新预测结果

18. end for

19. 预测结果正则化

20. 计算真实值与预测值的误差

4.2 基于Actor-Critic的无人机基站调度

本文使用的强化学习包含演员(actor)、环境(environment)、奖励函数(reward function)3个部分.在算法中需要为DBS制定相应的行动方案(policy),使得本文中奖励函数得到的奖励值最大化.考虑到本文的最终目标是最大化无人机基站组网整体的系统平均缓存命中率,Actor-Critic算法结合了以策略为基础的和以值为基础的两类强化学习算法,非常适用于无人机系统的调度决策.

本文将决策算法当作Actor,用来实现概率选择行为,又将以值为基础的强化学习算法当作Critic,用来评判Actor的行为得分,Actor又会根据Critic的评分修改行为的概率.在算法内既可以在范围内处理连续动作的选取事件,又可以进行单步更新[16].

在奖励函数的设计中,本文着重强调了缓存命中率,同时本文创建一个Critic网络来计算Q函数值,就可以得出应用于无人机调度的Actor-Critic网络.Actor参数的梯度变为式(8):

(8)

此时的Critic根据估计的Q值和实际Q值的平方误差进行更新,对Critic来说,其loss为式(9):

(9)

算法2.深度强化学习-联合缓存和轨迹设计

1. 将重放缓冲区容量初始化为B

2. for UAVi=1,…,Ndo

3. 用权重θQi和θμi随机初始化评价网络Qi和演员网络μi,

4.用权重θQ′i=θQi和θμ′i=θμi初始化目标网络,

5. end for

6. for episode=1,…,Mdo

7. 初始化环境并接收初始状态st+1,

8. for t=1,…,Tdo

9. For each UAVi,select

(10)

11. for UAVi=1,…,Ndo

12. if UAViflies beyond the border or disconnected then

(11)

14. 取消 UAVi的移动

16. end if

17. end for

18. store(st,at,rt,st+1)inB,st←st+1

19. for UAVi:= 1,…,Ndo

20. 获取随机样本(sj,aj,rj,sj+1)∈B

22. 用最小的lossL(θQi)更新评价网络权重θQi.

23.用▽θμiJ(θμi)更新演员网络权重θμi

24.更新两个目标网络权重θQ′i,θμ′i

25. end for

26. end for

27.end for

5 仿真实验与性能分析

本节通过一系列的仿真实验,对本文提出的解决方案(DC-DRL)进行性能分析与评价.本章节首先介绍实验场景的设置,然后分析结果.

5.1 实验设置

本文中的实验使用TensorFlow 1.0和Python 3.7进行.在仿真实验中,首先设定目标区域大小为80m×80m的一片区域,并切割为16块热点区域.本文将 DC-DRL与一些常用的缓存文件置换方法进行了比较,例如在内容替代策略上,本文通过将DC-DRL策略与先入先出(First Input First Output,FIFO)策略、最近最少使用(least recently used,LRU)策略、最不经常使用(Least Frequently Used,LFU)策略等常用策略相比较,得出本文使用LSTM进行预测的优势,在无人机调度方面,本文设置了动态无人机与悬停无人机的对比实验.在具体细节上,对于轨迹设计,本文选择了两个基准线进行比较:

1.悬停:为避免碰撞,无人机悬停在用户的集群中心.

2.圆形飞行轨迹:无人机以100m的半径和恒定的速度周期性地围绕簇中心运动.

本文通过大量实验在神经网络中找到合适的超参数.在实验中设置学习率为0.001,批大小Bs=32,更新迭代数Bup=200,缓存空间大小C=2000,折扣因子γd=0.9.本文使用一个两层全连接神经网络作为目标和评估网络,隐藏层的神经单元数为120.

5.2 实验数据与分析

在无人机基站(DBS)缓存模拟步骤中,本文考虑了两个实验因素:缓存大小和缓存替换策略.缓存大小决定了一次可以在高速缓存中保存的内容量.当开辟的存储空间填满时,系统需要遵从缓存替换策略确定从缓存中删除哪些对象.本文提出的DC-DRL策略在缓存替代策略上使用基于文件流行度的替换方法.在对比实验上,本文考虑了5种缓存替换策略:最优缓存策略、本文提出策略(DC-DRL)、按照对象到达的顺序删除对象(FIFO)、根据最近使用情况删除对象(LRU)、删除不受欢迎的对象(LFU).后3种策略不再赘述,其中,最优缓存策略表示提前预知下一时段的所需文件从而进行内容预取的缓存策略,是一种理想状态,实际情况不可达到.

仿真实验中,在一个热点区域上,本文中使用在校园网络场景中抓取的一小时的带有时间戳的短视频文件序列作为输入提供给边缘缓存中央控制器,并以章节3.3中方法切割文件为尺寸小于512Kb的小文件,模拟器生成实验的缓存命中率作为输出.实验使用缓存命中率作为缓存性能的主要性能指标,着眼于优化目标对所使用的缓存空间和替换策略的敏感性.

本文在DBS静止状态下对DC-DRL和其它传统缓存替代策略得到的平均缓存命中率进行了比较.缓存文件数在文件库中文件数总数的占比在本文中被定义为缓存率,如图3所示,当缓存率处于20%以下时,本文提出的基于长短期神经网络的缓存策略性能明显优于传统的缓存策略.例如:当缓存率为10%时,本文提出算法比LRU算法的系统平均缓存命中率高出接近4%,当需要80%的平均缓存命中率时,LRU策略与本文提出的基于长短期神经网络的替换策略相比还需要约一半的缓存率,LFU算法比本文提出算法所需缓存率高出一倍,传统缓存算法在利用缓存文件历史流行度信息上与机器学习的方法比较更为机械化,在处理更长的历史信息的能力上不如长短期记忆神经网络.LRU忽略了缓存内容的大小和访问延迟.LFU在使用时也需要有无效机制的支持.

图3 系统平均缓存命中率性能比较Fig.3 Systemaverage cache hit rate comparison

学习率(Learning rate)是监督学习以及深度学习中重要的超参数,其决定对输出误差的利用程度.合理设置学习率能够使目标函数在合适的时间内收敛到局部最小值.如图4所示,学习率不能太大也不能太小,因为过大的学习率会引起收敛过程的波动,而过小的学习率容易导致训练速度变慢.本文将深度强化学习的学习率设置在0.001～0.01,并最终选择0.001、0.002和0.005这3个有区别和代表性的学习率下的实际结果.从图中可以看出,0.001是这个场景中的最佳选择,因为系统平均缓存命中率会随着训练过程平滑地增加到收敛.

图5比较了不同数量无人机基站下的平均缓存命中率.无人机采用圆形包装算法单独部署,以最大限度地扩大覆盖范围,根据平均覆盖分数阈值选择链路方案.用户数、无人机可服务的最大用户数、文件总数和缓存大小分别为15、10、10和5.很明显,命中率随着无人机基站的数量增加而增加.使用随机替代算法的结果保持不变,因为它没有利用文件内容的特性.随着无人机数量逐渐增长,在服务区域内服务区的重叠面积越来越多,链接越来越稳定.在本文的仿真设置背景下,4个无人机协作已经可以取得逼近最优的结果.

图4 具有不同学习率的AC算法与训练集数的收敛性Fig.4 Convergence of AC algorithm with different learning rates versus the number of training episodes

图5 系统平均缓存命中率与无人机数量关系Fig.5 Average cache hit rate versus the number of UAVs

6 结束语

本文对边缘计算的无人机基站内容缓存问题进行了研究,设计了一种基于深度强化学习的无人机基站缓存策略,该策略可以对系统模型进行多因素、多目标的联合优化,根据多份缓存文件基于时间所得出的流行度,进行差异化缓存放置,并将预测结果作为指导无人机调度的因素,使缓存在无人机基站的MEC服务器中的内容更容易被该区域中的用户请求,使缓存内容的总命中率最大化.仿真结果表明,使用本文所提策略所达到的系统平均缓存命中率明显优于传统流行度预测方法以及固定基站的方法.本文策略有效地提高了缓存文件的总请求命中率,然而在实际应用中,流媒体文件是多种多样的,如何针对不同种类文件设计应算法提高系统效用.下一步研究工作的重点是,在其他具体应用场景下,针对不同的文件设计有效的策略,以进一步提高研究的实用性.