边缘云资源感知下的无人机飞行规划

UAV Flight Planning under Edge Cloud Resource Awareness

摘要: 在近距离为无人机(Unmanned Aerial Vehicles, UAVs)提供适当的地面控制和互补的计算与存储服务基础上，将使无人机能够支持广泛的应用。为实现此目标，部署在基站或其附近的边缘云平台至关重要。我们对现阶段提出的对于边缘云平台的资源约束的两种方法，即基于整数线性规划的多访问边缘计算(Multi-Access Edge Computing, MEC)感知无人机路径规划(MEC-Aware UAV Path Planning, MAUP)和加速MAUP (Accelerated MAUP, AMAUP)方法提出改进，并对其相关模拟环境提出限制条件，使得更加接近于真实环境。实验利用计算机仿真对原方案和改进方案进行评估，结果证明提出接近真实环境的必要性以及改进方案的有效性。

Abstract: Based on providing appropriate ground control and complementary computing and storage services for Unmanned Aerial Vehicles (UAVs) at close range, UAVs will be able to support a wide range of applications. To achieve this goal, edge cloud platforms deployed at or near base stations are crucial. We have proposed two methods for resource constraints on edge cloud platforms at this stage, namely Multi-Access Edge Computing (MEC)-Aware UAV Path planning based on integer linear programming, MAUP) and accelerated MAUP (Accelerated MAUP, AMAUP) methods propose improvements and put forward restrictions on their related simulation environments, making them closer to the real environment. The experiment uses computer simulation to evaluate the original plan and the improved plan. The results prove the necessity of proposing a solution that is close to the real environment and the effectiveness of the improved plan.

1. 引言

智能手机、智能手环等移动设备的普及，带来了数据的爆炸式增长，从而催生了交互式游戏、人脸识别和增强现实等计算密集型和延迟密集型移动应用 [1] 。多访问边缘计算(Multi-Access Edge Computing, MEC)被认为是一种很有前途的技术，因为它能够以令人满意的性能支持那些需要资源的应用程序 [2] 。相应地，用户可以将其计算任务卸载到资源丰富的基础设施，例如搭载多访问边缘计算(服务器共址的宏基站基站(Base Stations, BS)与MEC服务器或无人机(Unmanned Aerial Vehicles, UAV) [3] 。

由于其灵活性、低成本、到达某些偏远地区的便利性和快速交付，无人机正在获得动力，增加了其市场足迹，超出了最初的监视和侦察军事应用。无人机可用于广泛的公共和民用应用，如医疗保健、农业、安全、运输管理和货物交付。为了在物联网设备上实现及时的态势感知，如何在随机计算任务到达设备的情况下实现多个UAV的实时路径规划和节能计算卸载是一个主要挑战。

为了更好地发挥无人驾驶飞行器的灵活性，提出了不规则轨迹模式的路径规划来控制无人驾驶飞行器的飞行方向。有学者采用一系列离散位置来逼近无人驾驶飞行器的飞行轨迹，以对抗无限的飞行选择，并采用凸优化技术进行求解 [4] 。其他学者则有采用深度强化学习方法，实现多个UAV的自适应路径控制 [5] 。除了UAV辅助数据采集外，UAV的机载计算资源还可以作为飞行计算平台，辅助物联网设备的任务处理 [6] 。

然而，与集中式云数据中心不同，MEC节点的资源是有限的，因此鼓励智能利用，这主要通过优化资源配置和服务布局来实现 [7] 。资源配置的目标是找到在边缘节点上分配的最佳计算量和存储资源，而服务放置的目标是在一组边缘节点上找到给定服务的最佳分布，从而使该服务可以为最大数量的用户可用。

为了管理管理无人机应用中所需的MEC潜在资源和服务分配，有学者提出两种解决方案以保证飞行中的无人机能够连接到允许使用具有足够资源的MEC节点的基站，同时使总行进距离最小化 [8] 。一种方案是，采用整数线性规划方法寻找满足无人机连通性和计算资源要求的最优飞行路径(MEC-Aware UAV Path Planning, MAUP)，另一种方案则是，考虑到其复杂性，当飞行距离较长和/或网络规模较大时，特别是当密度较大时，MAUP可能需要较长时间才能找到最优飞行路径，于是提出加速MAUP (Accelerated MAUP, AMAUP)方案，使用考虑有向图的最短加权路径算法，即确定所需的路径。但是在方案中，默认无人机有足够的能耗飞到终点，且节点与节点之间的来回飞行的等效的，还可以考虑实际环境更接近于真是模拟环境，于是本文对两种方案提出改进。

对于整体系统模拟环境来讲，增加了考虑无人机在节点之间的单程最大飞行距离和无人机整体的最大飞行距离，并且添加风险较高的禁飞区域。在这个过程中，同时为MEC节点添加风险值，确保因为飞行高度等因素导致的两个节点的耗能不同导致的MEC节点之间的有向权值不同，有效增加环境的真实性。对于MAUP来说，增加了新的约束条件和改动原有不变的约束策略。而对于AMAUP来讲，考虑了新的权值函数的更新方法以及整体流程。

2. 系统模型

Figure 1. Network model

图1. 网络模型

在场景中，无人机将需要从起始点出发，并在具有一定资源的EMC基站点获取资源，最终到达目标点。在这个过程中，保证无人机在每个基站点获取相应的需求资源点，并且选择一条最优路径，保证无人机能够在有限的飞行距离内保持有效地利用资源并达到目标点。

在本文中，对原有算法下的场景和算法进行改进，包括限定无人机的节点间的最大飞行距离和无人机整体飞行路径的最长距离以及添加禁飞区域，并且模拟两个节点之间由于高度差等因素造成的节点之间往返的消耗不同，并观察新的算法下的运动轨迹，以及算法执行时间和飞行路径长度。

2.1. 网络模型

如图1，我们考虑一个固定的MEC节点的蜂窝网络，记为N。让U表示无人机的集合， $U_S$ 表示无人机的起始点， $U_D$ 表示无人机的目的地MEC节点。每个MEC节点被标记为 $R_i$ ，每架无人机的资源需求点被表示为 $r_u$ 。

给定一个加权图 $G=\left(V,E,W\right)$ 代表整个场景，起始节点 $S\in V$ 和目标节点 $D\in V$ ，V代表了图中所有MEC的节点，即 $V=N$ 。E表示这些节点之间的邻接关系，W则表示边权值， $w_{i,j}$ 则表示节点和节点的边权值。P是从S到D的可能路径集合，路径 $p\in P=\langle v_0,v_1,\cdots ,v_k\rangle$ ，则p路径所对应的整体的权值之和为 [8] ：

$w\left(p\right)={{{\displaystyle \sum }}^{\text{}}}_{i=1}^k{w}_{i-1,i}$

定义 $W\left(P\right)=\left\{w\left(p\right),\forall p\in P\right\}$ 代表P中路径权值的集合，则选择的路径p为集合中的最小值。

2.2. 问题公式化

在本文中，我们对现有的两种无人机路径规划策略做出改进，并确保沿轨迹路径的计算卸载和控制MEC资源的可用性，并在无人机的最长可飞行范围内，最小化行进距离。我们假设无人机从具有足够资源点的MEC节点开始飞行，并在选择节点后，对MEC节点资源进行减少，且无人机拥有的资源随着飞行释放，即无人机需要每个节点上都要能保证其资源储存多于或等于其需求资源点。

本文使用的符号摘要表如下表1：

Table 1. Symbol summary table

表1. 符号摘要表

2.3. NEW MAUP

原有的MAUP算法将路径规划建模为一个整数线性规划，旨在根据MEC资源可用性和最大UAV数量的行进距离长度提供最优路径，这有助于提供高效的路径选择，能够更好地利用MEC节点的计算、存储和通信资源，提高整体系统的性能和效率，本文根据设置的实验场景对相关约束进行更改和添加新的约束。

我们定义了以下变量 [8] ：

$\forall u\in U,\forall i\in N,\forall j\in \eta \left(i\right)$ :

$X_{i,j}^u=\{\begin{array}{l}1\text{If}UAVu\in U\text{passesfromnode}i\text{tonode}\hfill \\ 0\text{Otherwise}\hfill \end{array}$

MAUP的线性规划模型如下：

$\min \underset{u\in U}{{\displaystyle \sum }}\underset{i\in N}{{\displaystyle \sum }}\underset{j\in \eta \left(i\right)}{{\displaystyle \sum }}{X}_{i,j}^u\times w_{i,j}\times \left(1+K_i\right)$

$\forall u\in U$ :

$\underset{j\in \eta \left(D\left(u\right)\right)}{{\displaystyle \sum }}{X}_{j,D\left(u\right)}^u=1$ (1)

$\forall u\in U$ :

$\underset{j\in \eta \left(D\left(u\right)\right)}{{\displaystyle \sum }}{X}_{D\left(u\right),j}^u=0$ (2)

$\forall u\in U$ :

$\underset{j\in \eta \left(S\left(u\right)\right)}{{\displaystyle \sum }}{X}_{S\left(u\right),j}^u=1$ (3)

$\forall u\in U$ , $\forall i\in N$ :

$\underset{j\in \eta \left(i\right)}{{\displaystyle \sum }}{X}_{i,j}^u\le 1$ (4)

$\forall i\in N$ :

$\underset{\forall u\in U}{{\displaystyle \sum }}\underset{j\in \eta \left(i\right)}{{\displaystyle \sum }}{X}_{j,i}^u\times r_u\le R_i-\underset{\forall u\in U\wedge S\left(u\right)=i}{{\displaystyle \sum }}{r}_u$ (5)

$\forall u\in U$ :

$X_{i,\eta \left(i\right)}^u\times w_{i,\eta \left(i\right)}\times \left(1+K_i\right)\le O{L}_u$ (6)

$\forall u\in U,\forall i\in N,\forall j\in \eta \left(i\right)$ :

$\min \underset{u\in U}{{\displaystyle \sum }}\underset{i\in N}{{\displaystyle \sum }}\underset{j\in \eta \left(i\right)}{{\displaystyle \sum }}{X}_{i,j}^u\times w_{i,j}\times \left(1+K_j\right)\le M{L}_u$ (7)

其中约束1保证确保每个无人机在网络中从其起始位置移动到一个且仅一个MEC节点，而约束2确保每个无人机V从一个且仅一个MEC节点到达其目的地。约束3确保无人机V在到达目的地时会停止不会转向其他MEC节点。约束4确保每个无人机V从一个MEC节点移动到另一个MEC节点，而约束5确保每个MEC节点满足无人机群的资源需求。约束6保证每个无人机在选择下一个MEC节点时超过自己的节点间的最大飞行距离，而约束7保证了每个无人机的整体飞行路径长度不超过无人机的最长飞行距离。

2.4. NEW AMAUP

原有的AMAUP为了解决当出现大量可选择路径和MEC节点时，能够有效减少计算时间，以便应对复杂的飞行情况下的方案，并利用迪杰斯特拉算法所提出的加速算法。在原有加权图 $G=\left(V,E,W\right)$ 中，转换为有向加权图，以两个节点的路径长度和资源值确定新的路径权值。并在移除后不足以满足当前无人机的MEC节点后，不断更新路径权值，找到符合条件的无人机的最短飞行轨迹。

在本文中，对算法进行改进，包括增加和修改禁飞区域的权值和风险值，并且由于两个MEC节点之间由于高度差等因素造成的节点之间往返的消耗不同以及禁飞区域的设置，从而给MEC节点添加不同的风险值k。并且考虑UAV在MEC节点之间最远飞行路径和UAV本身最远飞行距离，采用新的权值计算方法完成对有向加权图的权值更新，并用以迪杰斯特拉算法结合，找到最佳路径。

2.4.1. 迪杰斯特拉

迪杰斯特拉算法用于寻找从起始节点 $S\in V$ 到目标节点 $D\in V$ 在加权图 $G=\left(V,E,W\right)$ 中的最短路径。分为以下三个步骤 [8] ：

1) 算法首先为每个无人机u设置初始的暂定距离值，在初始点S时，该值设置为0，其余节点设置为无穷大。规定两个集合，一个是初始化为空值的访问顶点集合VST和初始化为V的UVST集合。

2) 算法会暂定一个权值最小值的未访问顶点为当前节点CN。然后将未访问的相邻节点j，即 $j\in \left\{\text{neighbors}\left(CN\right)\cap UVST\right\}$ ，把它的暂定距离更新为 $\min \left[\text{tentative}\left(j\right),\text{tentative}\left(CN\right)+w\left(cn,j\right)\right]$ 。完成之后将CN标记为访问顶点，并从UVST中移除。在这个过程中，如过两个节点之间的原始距离大于无人机u的节点间最远飞行距离 $O{L}_u$ ，则将更换当前节点CN为当前权值排序的下一个最小值所在的顶点。

3)重复步骤2)直到所有的目标节点D被标记为已访问。

2.4.2. 目标算法

为了更有效描述算法的过程，使用图2来详细阐述执行步骤。

算法首先根据无人机群的资源需求对集合进行排序，然后将加权图 $G=\left(V,E,W\right)$ 转换为有向加权图 $dG=\left(dV,dE,dW\right)$ ，其中新的权重计算函数通过使用加权函数 $\lambda \left(\left(i,j\right)\right)=w_{i,j}*\left(1+k_j\right)/R_j$ 。其中 $k_j$ 为MEC节点下的风险参数， $R_j$ 为该节点的资源数。加权函数 使得具有较高资源容量的MEC节点更受青睐，且成本较低。这确保了MEC节点之间的负载均衡和无人机的能量消耗，同时最小化了网络分区的概率。

首先将禁飞区域的风险参数改为较大值99，从而增大加权函数修改后的权值，确保无人机不会向着禁飞区域飞行，而对于排序后的每个无人机u来讲，将会经历以下步骤：

1) 移除所有不满足无人机u资源需求的顶点，在图2的例子中，第一次迭代截止到图2(d)，并没有移除任何顶点，因为所有的MEC节点都满足了c的资源需求，而在图2(f)和图2(j)中，移除了不满足u2和u3的顶点节点。

2) 根据迪杰斯特拉算法寻找到成本最低到达目的地的航线，如果超出无人机最大飞行限度，则选择路径P中下一个距离最小的路径。图2(c)、图2(g)和图2(k)分别描述了无人机u3、u1和u2的飞行路径选择。

3) 最后，该算法通过减少所选路径上的资源值，并重新更新所在路径上的所有节点的权重来更新 $dG$ 。在图2(d)、图2(h)和图2(l)中，路径上的MEC节点的资源值和相关权重全部更新。

3. 仿真和讨论

本节将会比较更改后的算法与原有的MAUP和AMAUP在执行时间和平均每个无人机走过的平均距离上所展现的差异以及模拟本身之间的差异性。前一个指标显示解决方案的时间差异，后一个指标显示能耗和飞行方面的成本，行进距离越长，消耗能量越多，图中的平均飞行距离比较以相同条件下模拟加权图表示，将不显示单位。

对于每种场景，反复运行50次重复，改变UAV的起始和目的地位置，UAV的资源需求和MEC节点的资源容量。在模拟结果中，每个绘制的点代表50次重复的平均值，绘制的图以95%的置信区间表示。

3.1. 运行时间复杂度

图3(a)和图3(b)分别展示四种算法在不同MEC数量和不同UAV数量下在的执行时间。从整体上看，改进的MAUP和AMAUP在执行时间上是略优于改进前的算，并证明出AMAUP算法在随着MEC数量和UAV数量增加导致运行时间复杂度的上升的时候，是远远优于MAUP算法。如图3(a)所示，在MEC数量逐渐增加时，执行时间上会逐渐明显拉开一些差距，证明修改后的目标算法是在性能上优于原算法的。从图3(b)，随着UAV数量的增加，在AMAUP上的性能改变，也仍有提升。

Figure 2. AMAUP Target improvement solution

图2. AMAUP目标改进方案

3.2. 平均路径长度

图4(a)和图4(b)分别展示四种算法在不同MEC数量和不同UAV数量下在的平均路径长度。从整体上看，AMAUP算法由于改变了MEC顶点之间的权值，从而在数量的激增时，无法保证在路径长度上绝对优于MAUP。

对于图4(a)来说，随着MEC数量的增加，目标算法整体占优。而对于图4(b)来讲，随着UAV数量

Figure 3. Run time complexity

图3. 无人机场景建设

Figure 4. The average of traveled distances

图4. 无人机场景建设

的增加，其整体平均路径长度与原算法保持均势，在不同的数量下有不同的性能差距。

4. 结论

本文针对现阶段对于无人机边缘云资源感知飞行规划的问题所提出的MAUP和AMAUP算法以及相应实验场景进行改进。在整体的实验模拟中，提出对于无人机的节点单程飞行距离和最远飞行距离做出限制，并对环境中的禁飞区域和MEC节点的风险值进行添加，使得实验环境更逼近真实飞行环境。在MAUP所使用的线性规划模型中，修改原有限制和增加新的约束。对于AMAUP算法，除了新增的条件限制外，并重新采用新的权值计算方法进行更改。仿真结果表明，验证了所提出限制对逼近真实环境的必要性，并且在所提出的新的算法上，虽然在环境条件上添加了新的限制，但是在整体上是仍然可以优于原有两个算法。