缓存需求驱动的无人机轨迹优化

张小沛，赵梓晓，杜清河

（西安交通大学，西安 710049）

1 引 言

传统意义上的无线通信主要是利用地面上的固定基站等设施，但为了满足日益增长的多样化的通信需求，可利用无人机作为空中通信平台，从空中为地面终端提供无线通信服务。因为空中视野开阔，遮蔽物少，所以无人机可以提供视距链路，从而提供良好的服务质量。目前，有大量的研究工作致力于优化无人机在二维或三维空间的布局[1-4]。同时，随着信息技术领域的日益普及，无人机已经可以为无线用户提供无缝的互联网连接服务。无人机的自由移动特性可以让无人机能根据服务的地面终端位置及其通信要求动态调整空中位置。因此，无人机能够在缺乏地面基础设施的地区或过载条件下，为地面用户提供地面—空中通信服务。例如，在文献[5]中，优化无人机的部署位置可以改善无线网络的连接质量。在文献[6]中，用无人机作为通信中继，帮助无人水下航行器与地面设备进行通信连接。在文献[7]中，研究了无人系统在多障碍环境中的路径规划。

当前，网络中数据流优化的解决方案包括带宽管理、编码压缩、路由选择等，但这些解决方案不能很好地适应数据的爆炸式增长。影响网络吞吐量和传输时延的关键因素之一是内容提供商与终端用户之间的距离。因此，通过在靠近用户的边缘服务器上缓存流行内容可有效减少内容与终端用户的距离。在这种情况下，缓存是提高网络传输效率的一种有效技术。在机器学习的基础上，大量文献提出了各种基于机器学习的缓存策略。文献[8]将缓存替换问题建模成一种经典的多臂老虎机问题，利用强化学习来解决缓存问题。文献[9]提出了一种基于迁移学习的缓存策略。该策略所用的机器学习模式与传统的机器学习模式不同，传统的机器学习模式训练完毕后，如果再添加新的训练数据，机器学习将重新从零开始训练。

在移动边缘计算网络中，无人机搭载缓存服务器可视为移动的边缘节点，其可以按照一定顺序接近每个地面终端。在这种场景中，无人机不仅需要尽可能地缩短与每个地面终端的视距距离，以获得更高效的传输速率和通信质量，而且还需要使无人机尽可能快速地满足所有地面终端的通信需求。然而，先前的工作主要集中在无人机导航应用上，以确保其在已预先确定的初始位置和最终位置之间能安全飞行，如研究如何避免与其他无人机或地形障碍物发生碰撞[10]。对于无人机搭载缓存服务器的场景，无人机的轨迹决定了系统性能。近年来，已有部分文献研究了如何通过设计无人机的飞行轨迹来优化系统通信性能。例如，文献[11]研究了无人机在物联网中的应用，即利用无人机进行数据采集和机器通信时，无人机通过依次靠近每个地面终端的方式来缩短通信与移动调度距离，以实现更高效的数据采集。文献[12]研究了无人机作为移动中继的场景，当其为不同用户传输数据时，需在数据量和下载延迟之间进行权衡，为此可通过遗传算法优化无人机轨迹。在文献[13]中，提出了一种使无人机通信的能效最大化的轨迹优化方案。在文献[14]中，针对无人机移动中继系统，为了最大化吞吐量，提出了一个功率/速率分配和无人机轨迹（包括飞行方向和速度）的联合优化方案。针对优化无人机的飞行时间和飞行总长，文献[15]为了最大限度地提高了无人机的能量效率，利用线性规划和凸优化来优化无人机的飞行轨迹。但该算法仅考虑了无人机和地面终端的吞吐量，未考虑无人机与地面终端的实时通信质量。文献[16]研究了一种基于无人机多播系统的飞行轨迹设计问题，其优化目标是在确保每个地面终端能成功接收到内容的基础上保证无人机完成任务的时间最小。该方案将复杂的轨迹约束条件简化为每个地面终端的最小连接时间约束，利用凸优化方法，提出了一种有效路径点的设计方案。该文献中的无人机轨迹仅由直线段，其中包含了大量的急转弯。在实际应用中，由于惯性等物理因素，无人机较难实现这种轨迹。文献[17]针对多任务场景中的多子群任务分配和路径规划问题，将任务分配和路径规划联合优化，提出了改进的蚁群优化算法。

在本文中，我们利用半监督学习的思想，提出了一种缓存需求驱动的无人机轨迹优化方案。该方案解决了单无人机和多个地面终端通信时的飞行轨迹设计问题，优化了无人机飞行轨迹总长和飞行时间。无人机从部署服务器的位置出发，依次经过各地面终端并完成通信任务，然后返回至初始位置。其中，当无人机起飞时，根据已确定的与地面各结点的通信顺序，依次朝各地面终端位置飞去；当无人机进入地面终端的通信范围时，无人机初始化地面终端的信息，同时地面终端向无人机发送需求信息，无人机接收到需求信息后则开始向地面终端传输需求内容，其中，同一时间无人机只能与一个地面终端进行通信。无人机在与地面终端的通信过程中，利用迭代采取启发式随机法及半监督模型法优化局部飞行轨迹，当无人机与当前地面终端完成通信任务后，无人机飞向下一个地面终端或返回初始位置。仿真表明，该方案可以明显降低无人机的飞行距离及飞行时间，降低周期循环时间，有效地为地面终端提供边缘计算服务。

2 系统模型

在一些特殊场景，地面终端与基站间的通信质量较差，无法满足通信需求。如图1所示，我们考虑一个基站服务多个地面终端的场景。基站处可派遣搭载缓存服务器的无人机飞向地面终端，并向地面终端提供内容下载缓存、数据采集缓存、双向信息传输、扩展网络覆盖等通信服务。无人机与基站可通过无线或有线的方式进行数据传输，在无人机的缓存服务器中存储内容后，无人机成为一个移动边缘节点。随后无人机将从基站位置出发，向所有地面终端提供内容后返回基站位置，我们将整个流程定义为一个周期。在本文中，我们专注于单无人机和多个地面终端通信的场景。

图1 系统模型图Fig.1 System model

我们用K= {1,… ,k,…K}表示的K个地面终端组成的无线通信系统，地面终端k的位置表示为wk∈R2×1,k∈K。在实践中，地面终端的位置可以在系统数据库中(例如用无线传感器网络)获得，或者由标准定位技术(例如GPS 定位)确定。无人机的飞行高度固定为H。在实践中，为确保无人机安全飞行，H可以对应于最合适的飞行高度（例如躲避障碍而不频繁地使飞机上升或下降）。

因此， 无人机轨迹可用[x(t),y(t),H],0≤t≤TP表示，其中，x(t)和y(t)表示在水平面上投影的x和y的坐标，H表示无人机与地面终端的高度差。那么，无人机的投影位置可以用q(t) =[x(t),y(t)]表示，其中0≤t≤TP。为了便于问题的公式化，我们引入时隙δ(t)，将周期时间离散为M个时隙δ(t)，我们假设无人机的轨迹满足以下约束：

式(1)表明无人机的起始位置和终止位置。说明在一个周期内，无人机从基站位置出发最终返回至基站位置。式(2)中，L表示无人机在一个时隙的飞行距离，即在一个时隙中，无人机的飞行距离不超过L。

在任何一个时隙内，无人机与地面终端k之间的距离d k(n) 为：

式中，wk为地面终端的位置坐标。

假设每个UAV-GT 信道遵循LoS 链路且其他地面终端不会对无人机和当前通信任务的地面终端k之间的通信信道造成任何干扰。实际的UAV-GT 信道可以很好地近似于LoS 模型，同时假设由于无人机的移动性引起的多普勒频移可以完全预补偿掉[13]，从地面终端k到无人机的信道功率增益符合自由空间损耗模型，其表示为

式中，β0为距离d0=1 m 处的接收功率。

每个时隙中的每个地面终端的传输功率P是恒定的，则时隙n时地面终端k的接收信噪比SNR 为

式中，σ2为加性高斯白噪声功率。为d0= 1m 时接收机的信噪比（SNR）。

根据式(5)，为满足服务质量，即γk(n)的值应大于某个阈值，这个条件等价于无人机与地面终端k之间的水平距离不应大于某个阈值D。

我们定义了一个二进制变量αk(n)，代表地面终端的通信调度因子，表示无人机在时隙n是否与地面终端k发生数据交互。αk(n)具体表示无人机在时隙n时是否与地面终端发生数据交互，即αk(n) = 1，则表明无人机在时隙n时与地面终端发生了数据交互通信；αk(n) = 0，则表明无人机在时隙n时没有与地面终端发生数据交互通信，所以αk(n)应满足

假设无人机的通信带宽为B，无人机和地面终端k之间的瞬时信道容量可以被写为

在整个周期，地面终端k的吞吐量为

具体的，设无人机搭载的边缘计算服务器需要处理来自地面终端的各种数据请求，与地面终端请求的所有内容可以用一组数据集表示：C={1,2, …,Cmax}，C中的元素代表数据对象，这些数据对象的类型多种多样。同样在实际系统中，数据集C中元素可能有无限多个，但由于无人机搭载的缓存设备容量有限，无人机会对其缓存服务器中的缓存内容进行处理，使其在每个周期内其缓存的内容都是该周期内流行度最高（需求量最高）的内容，以保证无人机的传输效率和缓存效率最大化。即使无人机在当前周期无法向地面终端提供所需内容，当无人机返回起始地面服务器时，在下个周期的准备时间里无人机会更新缓存内容，以保证无人机在下个周期为地面终端提供上周期未能提供的内容。总的来说，无人机向地面终端提供内容这一需求可以表述为

式中：为本周期内地面终端k所需内容的总和。

综上所述，我们最终的目标是要优化无人机的飞行轨迹q(n) ，使其所飞行的时长最短，进而飞行路径最短。建立的全局轨迹优化问题如式(10)所示。

式中：M为周期时间内离散间隙δ(t) 数量。

寻找式(10)最优解等价于寻找有序路径点Q的最优集合，其中包含表示每路径段的起点和终点的位置。但该优化问题是NP-hard，难以直接求解。

对于终端通信半径D=0 时的极端情况，即无人机需要按某种顺序访问所有地面终端，并在每个地面终端的顶部保持静止Tmin。在这种情况下，寻找到式(10)的最优路径点集简化为确定所有地面终端的访问顺序，这样就可以最小化总的无人机飞行距离，这基本上等同于TSP。

但在实际中，终端通信半径D＞0 ，所以我们寻找次优解。为此，我们首先假设无人机与各地面终端的通信顺序已知，即通信调度表已确定（或利蚁群算法确构建通信调度表），然后将全局优化问题转变为局部优化问题。

如图2所示，当前周期开始时，无人机从基站处将数据存入自身缓存服务器。接着无人机从基站位置出发，根据已知的通信顺序飞向目标地面终端。当进入目标地面终端的通信范围后，无人机在与地面终端通信的同时根据算法决定每一时刻的飞行轨迹。当完成与该地面终端的通信任务后，无人机根据通信调度表确定下一个地面终端的位置。如果无人机已经完成所有任务，则无人机返回基站更新缓存服务器的内容，为下周期通信任务做准备。

图2 无人机缓存通信流程图Fig.2 Flow diagram of UAV trajectory

3 基于半监督学习的局部轨迹优化

3.1 局部轨迹优化算法

根据通信调度表，无人机首先飞往的地面终端及其位置我们用w1表示，以此类推，通信调度表中顺序为第k个地面终端的位置为wk。也就是说，无人机从起始位置出发，依次飞向{w1,w2,…,wK}并在完成所有通信任务后返回起始位置。根据通信调度表中的顺序，当无人机需要与wk进行通信时，即在进行第k个通信任务时，算法进入地面终端k的局部轨迹优化环节，并当完成当前局部优化后，将局部优化轨迹并入全局优化轨迹中。

在第k个通信任务中，当前需求通信的地面终端k为wk，下一个需要通信的地面终端为wk+1（未完成所有通信任务的情况下）。为了不失一般性和方便表述，将当前需求通信的地面终端k定义为wT，其有效通信半径为D。wS为无人机在局部轨迹中的初始位置，wE为下一个要前往的地面终端。无人机从wS出发，经过wT的通信范围，并完成通信任务后前往下个目的地wE。

我们的局部优化问题就是要使得无人机在完成wT通信任务的同时，使得无人机的飞行距离和飞行时间最少。因此，式(10)的优化问题转化为式(11)。

该问题仍属于NP-hard。本文所述算法利用半监督学习的思想，通过训练参考轨迹，逼近最优解。当无人机进入局部轨迹优化区域时，无人机的计算系统先判断系统中有无存储的参考轨迹。若无人机计算系统中无参考轨迹，则通过仿真启发式的生成参考轨迹，并判断该轨迹是否满足任务需求。若满足任务需求，则记录该轨迹和其特征向量。

式中：qk(n)为无人机在第k个通信任务中的位置。

若无人机计算系统中存在参考轨迹时，则通过对参考轨迹的特征向量的训练，形成新模型来生成新的飞行轨迹。若该轨迹可提升性能，则记录该轨迹和其特征向量，并利用该轨迹以及其特征向量优化参考轨迹生成模型。

算法通过循环迭代不断优化轨迹生成模型，使得无人机在进入局部优化区域时可以快速地生成一条符合性能标准的轨迹曲线。循环迭代同时也可以使得生成的轨迹曲线进行再次优化，直到性能逼近理论上界或迭代计数到达上界。

3.2 预处理特征参数

在局部轨迹优化场景中，根据式(7)对于无人机传输速率的描述，无人机在距离目标地面终端越近时，其传输速率越大。那么无人机在wT处有最大传输速率

人机处于边界上有最小传输速率

关于无人机飞行的方向选择有两种可能。第一种可能：为了获得更高的传输速率，无人机可能会朝着目标地面终端wT的方向飞行。第二种可能：为了缩短无人机飞行距离，无人机可能朝着下一目标地面终端wE的方向飞行。总之无论无人机如何选择飞行方向，无人机在飞行时每一时隙所在的位置必然比上一时隙所在的位置更接近目标地面终端wT或下一个地面终端wE。无人机的飞行区域存在非优解区域和优解区域。

无人机与目标地面终端wT的距离为

无人机与下一目标地面终端wE的距离为

无人机在n+1 时刻与地面终端wT和wE的加权距离必然比n时刻与地面终端wT和wE的加权距离短，如式(16)所示。

式中：ζ为距离重要程度因子，0≤ζ≤1 ，ζ值越大，距离对方向的选择越重要。ζ由式(17)表示

式中：Rk为已传输的数据总量。

满足式(2)的条件下，为了保证飞行时间最短，我们假设无人机只有两个状态：静止或以最大速度飞行。则无人机在第i+1 个时隙的位置坐标可以表示为

在满足式(16)的条件下，可解出θi的上界θiH及下界θiL，θi表示无人机在第i～i+1 个时隙之间的飞行方向。

根据无人机的计算系统中有没有存储最佳飞行轨迹或者贪心指数的大小，可将算法细分为两大类，分别为启发式优化飞行轨迹和半监督模型化优化飞行轨迹。

3.3 启发式优化飞行轨迹

如果无人机的计算系统中没有存储参考轨迹，或满足贪心指数，那么本次局部轨迹优化采用启发式的贪心策略，根据θi的概率密度P(θi)随机选取θi值，得qk(i+1)=[x k(i+1),y k(i+1)]的坐标，其θi的概率密度如式(19)。随着时隙的不断增加，最终获得本次局部优化的轨迹，并得到方向参数数据集。

对于本次局部优化的轨迹qk，其路径长度为

3.4 半监督模型化优化飞行轨迹

如果无人机的计算系统中存储最佳飞行轨迹，最优空间中的参数为Θ=[θ1B,θ2B,…,θNB]，那么本时隙无人机的飞行方向采用机器学习的方式，根据θi的概率密度P(θi)随机选取θi值，得qk(i+1)=[x k(i+1),y k(i+1)]的坐标；其θi的概率密度如式(21)。随着时隙的不断增加，最终获得本次局部优化的轨迹。

4 仿真评估

4.1 对比算法

在基于飞行轨迹优化的无人机缓存通信策略中，本文提出了一种基于半监督学习的轨迹优化方案。我们通过仿真结果来评估所提出方案的性能。为了突出比较，在仿真中设置了一种对比算法，即基于椭圆折线的轨迹优化算法。在我们的仿真中设置了两种对比算法，分别为基于TSP 的轨迹优化算法和基于椭圆折线的轨迹优化算法。

4.1.1 基于TSP 的轨迹优化算法

这种方案的假设是当地面终端的通信范围D= 0时，与地面终端的通信范围相当于一个点。如果无人机需要与各地面终端进行通信，那么无人机必须经过（贴近）地面终端，此时可以将该问题看作是一般的经典TSP，可利用蚁群算法加以解决。

4.1.2 基于椭圆折线的轨迹优化算法

在现实中，无人机的飞行轨迹是一条有向曲线，但如果把曲线离散化形成一个个坐标点，那么无人机飞行轨迹可由一系列坐标点组合而成。如果需要找到无人机在每个时隙的最优坐标点，那么算法难以设计。椭圆折线法的核心思想是只找最优飞行轨迹的关键坐标点，通过将关键坐标点相连，近似地逼近最优飞行轨迹。

基于椭圆折线的轨迹优化算法，根据已确定的通信顺序，在与地面终端进行通信的同时进行局部轨迹优化。可以说，基于椭圆折线的轨迹优化算法是一种局部轨迹优化算法。

具体来说，当无人机与wk进行通信时，即在进行第k个通信任务时，算法进入地面终端k的局部轨迹优化环节。同样，将当前需求通信的地面终端k定义为wT，其有效通信半径为D。wS为无人机在局部轨迹中的初始位置，wE为下一个要前往的地面终端。

我们需要将地面终端的有效通信半径D再度离散化，定义离散程度d将通信半径D分为nD=D/d段。在每一段通信区域内，无人机与地面终端的通信速率相等，即

式中，nP为无人机所在的离散通信区域序号，序号相同时，无人机与地面终端的通信速率相等。

即离散通信区域Pn的通信区域为

我们知道，无人机在飞行过程中要尽可能地缩短飞行距离。如果无人机能以直线飞行，那么其飞行距离一定是最短的。但是由于通信范围的限制，无人机几乎不可能以一条直线为轨迹，所以我们需要找出几个关键的拐点，以折线为飞行轨迹。

利用椭圆性质：椭圆上任意一点到两焦点的距离相等。

式中，(xp,yp)为无人机进入离散通信区域nP的外边界时的坐标。(xE,yE)为下一个要前往的地面终端wE的坐标。

通过调整C的大小，作一个椭圆与离散通信区域nP的内边界相切，该切点即所找的拐点。

4.2 仿真参数设置

本节中将所有仿真实验涉及的参数汇总，如表1所示。

表1 仿真参数表Table 1 Simulation parameters

4.3 仿真结果评估

在第一组实验中，我们首先仿真了在两个地面终端在需求数据量不同的情况下的无人机飞行轨迹，设置两地面终端所需求的数据量分别为110 Mbit 和60 Mbit，通信半径都为60 m。从图3可以看出，蓝色路线为基于半监督学习的飞行轨迹，其总长为459 m，比TSP 蚁群算法轨迹（红色路线）总长减少202 m，优化30.6%；两地面终端的轨迹不相似，左侧的地面终端需求数据量较小，无人机绕其边界飞行；右侧地面终端需求数据量较大，则需要略微深入地面终端的通信范围。说明本算法能很好地把握终端的通信需求。

图3 两地面终端无人机轨迹优化图Fig.3 Ground terminal UAV trajectory optimization

在第二组实验中，我们仿真了D= 60 m 时无人机的飞行轨迹图。基于椭圆折线法的无人机飞行轨迹，其总长为2251 m，比TSP 蚁群算法轨迹总长减少511 m，总长优化18.5%；如图4所示，蓝色路线为基于半监督学习的无人机飞行轨迹，其总长为2152 m，比TSP 蚁群算法轨迹总长减少610 m，优化22.1%。

图4 D=60 m 时基于半监督学习的无人机飞行轨迹图Fig.4 UAVs flight trajectory graph based on Semi-supervised Learning (D=60 m)

在第三组实验中，我们仿真了D=140 m 时无人机的飞行轨迹图。如图5所示，蓝色路线为基于半监督学习的无人机飞行轨迹，其总长为1836 m，比TSP 蚁群算法轨迹总长减少926 m，优化33.5%。基于椭圆折线法的无人机飞行轨迹，其总长为1910 m，比TSP 蚁群算法轨迹总长减少852 m，总长优化30.8%。

图5 D=140 m 时基于半监督学习的无人机飞行轨迹图Fig.5 UAVs flight trajectory graph based on Semi-supervised Learning (D=140 m)

两种方法相比TSP 蚁群算法，有明显的提升。基于半监督学习的无人机飞行轨迹总长比基于椭圆折线法的无人机飞行轨迹总长减少74 m，性能提升3.8%。从性能提升上看，半监督学习法比椭圆折线法只有略微的提升。但从飞行轨迹上看，椭圆折线法的飞行轨迹拐角较大，无人机因为自身性能和惯性的原因其转向较慢，无人机按照椭圆折线法的轨迹可能较难操作，达不到实际要求。半监督学习法拐角圆润，易于操作。

5 结 论

本文研究了在移动边缘计算系统中，搭载边缘计算服务器的无人机与地面终端的通信问题，并将该问题转化为无人机的飞行轨迹优化问题。并且提出了缓存需求驱动的无人机轨迹优化方案。具体为：在一个周期内，无人机从部署服务器的位置出发，依次经过各地面终端并完成通信任务，然后返回至初始位置。其中，当无人机起飞时，根据已知的通信顺序，依次飞行经过各地面终端并与各地面终端通信；当无人机进入地面终端的通信范围时，无人机初始化地面终端的信息，同时地面终端向无人机发送需求信息，无人机接收到需求信息后则开始向地面终端传输需求内容。其中，同一时间无人机只能与一个地面终端进行通信，无人机在与地面终端的通信过程中，利用迭代采取启发式随机法及半监督模型法优化局部飞行轨迹，无人机沿着优化轨迹飞行。仿真表明，该方案可以明显降低无人机的飞行距离及飞行时间，有效地为地面网络节点提供边缘计算服务。