多无人机辅助边缘计算下的路径规划研究

Research on Path Planning in Multi-UAV Assisted Edge Computing

摘要: 无人机(Unmanned Aerial Vehicles, UAVs)越来越多地被用作移动边缘计算(Mobile Edge Computing, MEC)中的移动服务器，并被广泛地集成到现代物联网应用中。本文在现有研究的无人机路径规划中，引入考虑无人机的能量消耗和无人机之间的合作，并用于改善提供给终端用户的服务质量(Quality of Service, QoS)。通过加深考虑无人机在飞行过程中以及处理终端用户的能量消耗以及多无人机的协作能力，提出相应的模型改进，通过观察无人机的飞行路径，验证所提算法的有效性和低耗性，并证明无人机之间团队合作的有效性。实验结果表明，所提模型在合作时更能降低总体能耗，并增强模拟环境的真实性。

Abstract: Unmanned Aerial Vehicles (UAVs) are increasingly being utilized as mobile servers in Mobile Edge Computing (MEC) and widely integrated into modern Internet of Things (IoT) applications. In this paper, we introduce a novel approach to UAV path planning that considers both the energy con-sumption of UAVs and their collaboration, aiming to improve the Quality of Service (QoS) provided to end users. By incorporating the energy consumption during UAV flight and the collaborative capabilities of multiple UAVs, we propose model enhancements. The effectiveness and efficiency of the proposed algorithms are validated through the observation of UAV flight paths, demonstrating the effectiveness of team collaboration among UAVs. Experimental results show that the proposed model significantly reduces overall energy consumption when UAVs cooperate, while enhancing the realism of the simulated environment.

1. 引言

随着5G技术的发展，运行在用户设备(User Equipment, UE)上的计算密集型应用，如在线游戏、VR/AR和远程医疗，将变得更加繁荣和流行。这些移动应用程序通常需要大量的计算资源，并产生高能耗。然而，当前的用户设备通常具有有限的计算资源和有限的电池容量。移动云计算(MCC)的出现是为了增强终端的计算和存储能力 [1] ，并通过移动网络将计算卸载到云端，从而降低终端的能耗。

然而，云服务器往往在空间上与终端相距较远，这可能会产生较高的传输延迟 [2] ，并对用户体验产生不利影响。为了减少回程链路延迟，移动计算最近转向了一种新的计算范式，即移动边缘计算(Mobile Edge Computing, MEC) [3] 。可以将云计算资源和服务迁移到离终端更近的地方，从而有效降低通信延迟和能耗 [4] 。

近年来，无人机因其高机动性和灵活部署而受到研究人员的特别关注 [5] 。他们研究了无人机辅助MEC系统中的资源分配或路径规划 [6] - [11] 。为了减少无人机辅助MEC系统中UE之间的处理延迟，有学者开发了一种基于惩罚对偶分解优化框架的算法，对无人机轨迹、计算卸载和用户调度进行联合优化 [5] 。

在考虑无人机的能量消耗中，学者采用了基于Lyapunov的方法 [12] ，将加权能量消耗最小化问题分解为涉及设备和无人机的三个子问题，这些问题交替进行优化。有的文章提出了一个场景，其中多个物联网设备将计算任务卸载到无人机或周围的地面基站，通过联合优化计算卸载、带宽分配、比特分配和人机自由路径，同时满足任务延迟约束，最小化网络设备和无人机的加权能量消耗 [13] 。

然而，目前将无人机视为边缘服务器与实际飞行环境之间尚存在差距。实际的无人机操作场景要复杂得多。现有的模拟和仿真环境往往无法完全复制真实飞行条件，导致一系列问题，如性能预测不准确、通信不稳定和感知与决策能力不足。因此，考虑到无人机飞行环境的复杂性和变化性，增强其在复杂环境中的感知和决策能力至关重要。进一步研究和改进飞行环境模拟技术对于实现无人机作为边缘服务器部署，并使其与真实飞行条件更加接近至关重要。

因此，本文考虑其它一系列综合因素来完成无人机的路径规划过程，以保证更加接近无人机的真实飞行环境，加强对现实环境的接近性。这些因素包括终端用户需求的动态变化、环境中静态和移动障碍物的风险，以及为终端用户提供服务和无人机飞行所涉及的能量消耗，将所有这些因素都整合到一个成本矩阵中。

此外，这三个因素与传统无人机在边缘计算路径规划中的成本矩阵考虑有所不同，并且它们也会相互影响。由于障碍物的随机移动，无人机的飞行环境不断变化。同时，终端用户的需求也在不断变化，导致每一刻终端需求的奖励和避免障碍物的惩罚发生变化，从而影响无人机的飞行能量消耗。此外，由于终端用户的需求自处理，这将影响无人机需要处理的终端需求引起的计算和下载能量消耗，从而影响无人机的整体飞行轨迹。在这个过程中，这三个因素相互作用，影响无人机的飞行选择，符合真实环境中的多因素交互效应，使模拟更加真实。

除此之外，使用多架无人机相互协作，共同满足系统的整体终端需求。无人机将在它们之间共享终端信息和障碍物数据，当单个终端的需求超过一定阈值时，它们可以协同工作为其服务。

2. 系统模型

在无人机作为终端用户的边缘服务器的场景中，无人机配备了高性能的计算和存储设备，以及必要的通信和传感器技术。它们利用传感器收集环境数据、图像或视频，实现对实时任务如数据分析、图像处理和物体识别的即时计算和数据处理。无人机可以提供各种服务，以满足终端用户的需求，包括实时视频传输、数据分析结果和位置信息。在为终端用户提供服务的过程中，无人机通过将计算和存储能力靠近终端用户，减少数据传输延迟和网络负载，实现更快速和实时的响应。

如图1所示，无人机作为边缘服务器，从起始位置飞行到最终位置。在整个过程中，无人机为终端用户服务，同时降低了与躲避障碍物相关的风险。在无人机的飞行过程中，其余出现在地图上的无人机将作为移动障碍物，持续移动。同时，无人机共享终端信息和障碍物信息。此外，终端用户的需求将在无人机到达其服务范围之前开始自我处理。在此过程中，将最终用户的需求作为无人机的奖励因素，将障碍物、飞行能耗和终端处理能耗作为成本因素。

Figure 1. UAV scenario construction

图1. 无人机场景建设

在无人机之间的合作方面，它们将相互共享终端信息和障碍物信息。如果一架无人机目前正在处理一个终端，它将在自己的处理完成后通知其他无人机对该终端的剩余需求，通常表明需求已得到充分解决。然而，当一架无人机在处理需求过多的终端时，它会在最大处理时间内将该终端的剩余需求告知其他无人机，并等待其他无人机协助处理。在此过程中，多架无人机可以协作处理相同的需求。对于障碍物，在无人机感知范围内检测到的任何新障碍物将与其他无人机共享，作为风险评估的参考。

本文将每个无人机充当代理者，不断从环境中学习。在每一步中，无人机根据周围环境选择规划策略，以实现最佳奖励。因此，在最大化期望奖励时，代理者必须考虑到障碍物的不断移动引起的风险因素、地图上每个点的几何距离、终端需求的动态因素以及无人机在每一步终端飞行中的能量消耗。这些元素以奖励矩阵的形式反馈给移动的无人机。

2.1. 障碍物模型

为更准确地描述真实环境，本研究中的地图场景包括执行飞行任务的移动无人机和不同类型的障碍物，如不可移动的山脉或建筑物。在假设中，假设所有障碍物都符合指数分布。

这样做的好处在于，指数分布具有无记忆性的特点，这意味着在任何时刻，下一个障碍物出现的时间与上一个障碍物已经存在的时间没有关联。这种性质对于路径规划和飞行避障具有一定的优势。指数分布具有数学上的便利性，其概率密度函数和累积分布函数具有简单的表达形式，这有利于在算法中高效地计算和处理障碍物的出现概率，并且使得路径规划算法更具灵活性，能够更好地适应障碍物出现的不确定性和随机性，从而考验了无人机飞行的适应性和安全性。

本文将 $\left(x,y\right)$ 表示地图上的坐标，将场景分为 $N\ast N$ 的网格，坐标点代表的是网格中的每一个交叉点的坐标。对于地图中的独立障碍物，给出第i个障碍物的位置 $O_i=\left(X_i,Y_i\right)$ ，风险 $r_i\left(x,y\right)$ [14] 表示在点 $O_i$ 处来自 $\left(x,y\right)$ 的风险，并可以定义为：

$r_i\left(x,y\right)=\lambda {\text{e}}^{-\lambda O_i},i\in \left\{1,2,\cdots ,n\right\}$ (1)

地图上从一个点到另一个点的风险暴露风险 $R\left(x,y\right)$ 由两点之间线性路径上任意点的积分风险表示。

${{{\displaystyle \int }}^{\text{}}}_{\left(x,y\right)\in S}\left(1-{{{\displaystyle \prod }}^{\text{}}}_{i=1}^n\left[1-r_i\left(x,y\right)\right]\right)$ (2)

由于移动障碍物可能出现在不可预测的位置，因此每次无人机模拟都会遇到不同的移动情况，这可以更好地检测无人机在遇到新障碍物时的应急处理能力。这可以用于验证和评估目标算法模型的鲁棒性和无人机控制算法的有效性。

2.2. 终端用户模型

在移动边缘计算(MEC)的应用场景中，终端需求之间通常存在一定的时间关系和相关性。使用马尔可夫随机矩阵可以对这些终端需求进行建模，并利用其概率转移矩阵推断下一时刻的需求。这不仅减少了冗余计算，还提高了算法的效率和准确性。此外，作为移动的边缘计算节点，无人机具有有限的资源，并且容易受到环境影响。虽然基于马尔可夫随机矩阵建模的自处理方法需要一些计算资源，但与云平台相比，它消耗更少的资源，并且更加灵活便捷。无人机可以根据环境变化调整其处理方法并做出更优化的决策。因此，基于马尔可夫随机矩阵的自处理方法为无人机的应用提供了一种有效的验证和评估方法。

对于每一个需要服务的终端用户来说，本文假设第j个终端用户具有初始需求 $d_j^0$ ，等待无人机进行处理。由第k个无人机 $UA{V}_k$ 服务的需求 $d_j$ 可以随时间 $t_k$ 变化表示为 [14] ：

$d_j^{l+1}=d_j^1-\tau t_k$ (3)

其中， $\tau$ 表示每个时间槽可以处理的需求数量。终端用户的剩余需求越大，无人机所需的服务时间就越长。

为了计算服务质量并便于进行更好的实验比较，定义了具体的参数。服务质量被定义为 [14] ：

$QoS=1-\frac{{\displaystyle {\sum }_{j=1}^m{d}_j}}{{\displaystyle {\sum }_{j=1}^m{d}_j^0}}$ (4)

在无人机到达之前，无人机自身的处理过程可以表示为马尔可夫随机矩阵的迭代过程，并采用迭代矩阵作为表达方式。这个模型的主要目标是通过使用马尔可夫随机矩阵的迭代计算，模拟无人机在不同状态下的行为和决策，以优化其对终端用户需求的响应和处理效率。通过这种方式，我们致力于改善整个系统的性能和用户满意度。同时，考虑到不同终端用户的需求，还将进行合理的分配和调度，以提高整个系统的性能和稳定性，从而更好地优化无人机对终端用户需求的响应和处理效率。定义迭代矩阵A和初始成本矩阵B：

$A=\left[\begin{array}{cc}a& 1-b\\ 1-a& b\end{array}\right],B=\left[\begin{array}{c}{d}_j^0\\ 0\end{array}\right]$ (5)

在每次无人机移动后，终端用户首次处理的未完成需求被表示为 $ans\left[0\right]$ ( $ans=A\ast B$ )，而后续迭代的乘积为 $A\ast ans$ 。矩阵A中的每一列代表不同的需求进出比例。其中，a代表终端用户当前独立处理的需求比例，而 $1-a$ 代表剩余的比例。b代表能够完全独立处理其需求的终端用户比例，而 $1-b$ 代表由于意外情况而未满足的需求比例。因此，总未完成需求可以表示为

$d_j=\{\begin{array}{l}A\ast B,step=t\\ A\ast ans,step=\rho t\end{array}$ (6)

引入两个关键变量来描述无人机移动的时间和终端处理的频率，即step和t。其中，t代表完成一次固定移动所需的时间，而 $\rho$ 代表t的倍数。因此，step代表终端处理的频率。

2.3. 无人机能耗模型

对于无人机来说，能源通常是一个重要的限制因素。了解无人机的能源消耗情况可以有效控制能源消耗，确保无人机的正常运行并高效利用能源。这还可以更好地理解如何在设计和配置无人机系统中采用最佳实践，以减少总体能源消耗，找到优化的空间和方向。从而使得无人机可以找到更合适的路径，优化飞行轨迹，进一步提高能源利用效率和飞行性能。

无人机系统的能源消耗由计算能量消耗、下载能量消耗和飞行能量消耗组成。飞行能量消耗通过几何距离在奖励矩阵中表示为因子点。

2.3.1. 计算能耗

当无人机进入需求检测范围时，需要在最大时间限制内完成任务，表示为T。如果超过时间限制T，无人机将放弃当前任务并移动到目标点。无人机在为终端用户提供服务的时间T内消耗的能量计算如下 [15] [16] ：

$E_j^c=\tau C^3\gamma d_j^2$ (7)

其中， $\gamma$ 表示未使用的有效电容开关，表C示每个待处理的输入数据比特的CPU周期数。

2.3.2. 下载能耗

下载能耗被表示为 [17] ：

$E_j^d=\frac{N_{0}B{d}_j}{g_i\left(p_i\right)}\left(2^{\frac{\tau }{B}}-1\right)$ (8)

其中，N₀表示频谱密度，B表示上行和下行带宽， $g_j\left(p_i\right)$ 表示第i个无人机与第j个终端用户之间的信道增益 [18] 。

$g_j\left(p_i\right)=\frac{g_0}{{\left(x_i-x_j\right)}^2+{\left(y_i-y_j\right)}^2}$ (9)

变量g₀表示在传输功率为1瓦特时，距离为1米处接收到的功率。被终端用户使用的无人机的能量消耗定义如下：

$E_j=E_j^c+E_j^d$ (10)

2.4. 奖励矩阵

地图上点 $p_i$ 和 $p_r$ 之间的奖励矩阵定义如下：

$A_{p_i,p_r}=d_{p_i,p_r}+E_j+K{\displaystyle {\int }_{C}R\left(x,y\right)\text{d}s}+\frac{M}{1+{\displaystyle {\sum }_{j\in s\left(p_i,ϵ\right)}U\left(d_j\right)}}$ (11)

K和M分别代表了服务的风险参数和需求参数，当K设置为较高值时，无人机在避免障碍物时会更加谨慎，即使可能导致路径长度更长。这表明无人机优先考虑避免潜在风险，并致力于最小化与障碍物的碰撞。这种设置适用于对安全性要求较高的任务，如医疗紧急物资的运输或需要避开人口密集区域的飞行任务。另一方面，当M设置为较低值时，无人机倾向于优先考虑在飞行过程中最小化总体成本，这可能导致某些服务被省略。这意味着无人机更注重路径的经济效益，并可能选择跳过某些服务点或减少路径长度。这种设置适用于对效率和经济性要求较高的任务，如大规模货物配送或需要尽快完成的任务。因此，K和M的设定可以根据具体任务的要求来平衡风险和效率，从而使无人机的飞行策略更加灵活和适应不同的应用场景。

根据任务的具体需求和优先级，调整参数K和M的值可以在风险和效率之间寻求平衡。这有助于根据实际情况制定最优的路径规划策略。通过考虑这些因素，本文的路径规划算法可以确定无人机的最优路径，以在满足动态需求的同时最小化成本和风险。

2.5. 成本矩阵

路径规划中使用成本矩阵确定初始最优路径到目标点。生成成本矩阵需要多次迭代，最终达到收敛状态 [19] 。对于地图中的一组u个无人机，第 架无人机的初始位置表示为 $p_o^j$ 。利用每架无人机的初始点来调整成本矩阵为每个无人机计算成本矩阵 的过程如下：

1) 初始化成本矩阵 $G^0$ 。将目标点赋值为0，将非目标点的元素赋值为无穷大。

2) 更新成本矩阵的过程如下：选择地图中的一个点，并根据其他点的赋值更新成本值(其中k为迭代次数)。

3) 重复步骤2)，直到矩阵收敛到稳定状态。

$G_{p_i}^{k+1}=\min \left\{G_{p_i}^k,\frac{{\displaystyle {\sum }_{j=1}^u{A}_{p_i,p_o^j}}}{u}+A_{p_i,p_r}+G_{p_r}^k\right\},i,r\in \left\{1,2,\cdots ,N^2\right\},j\in \left\{1,2,\cdots ,u\right\}$ (12)

通过更新成本矩阵，直到其收敛到最终稳定状态，生成了一个有序的点序列作为无人机的初始路径。为了生成这个成本矩阵G，利用每架无人机的初始点位，并通过计算每个无人机共同的成本之和来调整成本值。

2.6. 路径规划

具体而言，每个无人机会根据成本矩阵G生成自己的点序列，作为其初始路径。在成本矩阵G中，选取成本最低的点，并将其连续地添加和更新至路径中。这个过程的描述如下 [14] 。

1) 将初始化为空。

2) 将G中的最小值 $p_i$ 添加到Path中，并将 $p_i$ 设置为无穷大。

3) 重复步骤2)直到达到目标点。

在这个过程中，每个无人机将被视为一个智能式正体，都具有自己的记忆和成本矩阵。记忆负责存储环境地图信息的是中央智能体，成本矩阵负责生成学习结果并选择无人机的下一步动作。

在无人机移动过程中，障碍物会发生随机位移，并且终端用户会进行需求自处理。无人机在半径为R的区域内扫描障碍物，并更新位置和与其他无人机共享信息以协同规划。环境变化时更新权重和成本矩阵，无变化时沿现有路径继续飞行并获取新位置，在这个过程中无人机在检测范围内处理终端用户请求。

在整个路径规划过程中，无人机将持续共享观测到的障碍物信息，并根据终端需求的变化和其他无人机在飞行过程中的运动情况，不会遵循特定的路径。这使得驾驶路径更加复杂，更能够模拟无人机所处理的环境的真实情况。

3. 仿真和讨论

本节首先讨论了无人机在复杂环境中的运动，并将其与在标准固定环境中的飞行进行了比较。此外，还比较了在相同复杂环境中，所提出的路径规划算法与经典的A*算法之间的适应能力差异。

本节首先讨论了无人机在合作与不合作时所产生的在接近现实环境下的运动比较，其次在不同环境中，比较了提出的目标算法和A*算法之间的差异性。

在模拟中，环境地图被定义为一个50*50的网格，在地图中，存在三架无人机和二十一个终端用户。每个无人机的路径将会以不同颜色划分出来，以区别整体路线。

3.1. 多无人机的路径规划

在地图上，底部的三个黑色圆圈表示三个无人机，红色圆圈则代表终端用户，蓝色点状代表需求可服务半径，所示等高线代表障碍物位置及其风险区域。并且，随着无人机飞行，终端用户需求的处理不断变化。在地图上，这通过终端用户的红色圆圈消失来表示。此外，障碍物的位置以及与之相关的风险等高线也在不断变化。此外，无人机的路径会不断修改，直到它们到达目标点。

对于图2(b)，观察到蓝色和绿色无人机，由它们各自的颜色表示，协同处理位于地图中心的相同终端需求。这表明终端的需求过大，导致单个无人机在最长时间段T内的处理能力有限。因此，联合处理需要其他无人机的协助。这一发现验证了无人机之间的合作性质。

通过观察图2(c)和图2(d)，可以推断，当多个无人机相互合作时，与独立运行的单个无人机相比，它们在路径覆盖方面表现出优越的性能。根据图3所示的结果，可以观察到，与不合作相比，合作在平均路径长度和平均风险方面产生了优越的性能。

这意味着多无人机合作，可以协调它们的飞行路径，避免冲突和重叠，从而提高空域的资源利用效率，并且加快任务完成速度，提高整体效率。在资源方面来说，可以避免不必要的飞行距离，从而减少能源消耗。协同规划路径还可以减少不必要的加速和减速，进一步节约能源，可以共同调整路径或协同完成任务，提高整个系统的鲁棒性和抗干扰能力。

(a) step = 5 (b) step = 60 (c) step = 195, with collaboration (d) step = 195, without collaboration

Figure 2. Differences of UAV-MEC path planning platform in complex scenarios between collaboration and non-collaboration

图2. 合作与非合作情况下，在复杂场景中，无人机移动边缘计算路径规划平台的差异

3.2. 目标算法与A*算法的比较

A*算法是一种启发式搜索算法，用于在图形或图像中找到最短路径，它是一种基于图形搜索的算法，通常用于解决路径规划问题，如在地图上找到最短路径或最佳路径。

利用目标算法和现有A*算法进行比较，从而基于A*算法，在路径规划的每一步中，无人机可以在固定数量的等距离方向中选择一个方向，向前移动一步。在实验中，为无人机设置了八个方向，因此在每一步中，无人机有八个候选节点 $p_i$ 可供选择。考虑路径长度和风险作为成本，终端用户需求作为奖励，在A*算法中将每个节点 $p_i$ 的权重函数 $F_i$ 定义为：

(13)

对于图3来说，在接近真实和复杂的场景中，A*算法无法找到可行的路径，导致无人机无法飞到目标点，陷入死解从而无法找到路径。

21个终端用户

Figure 3. Simulation of UAV-MEC based on path planning platform with A* algorithm trajectory in complex situation

图3. 在复杂情况下，基于A*算法轨迹的无人机移动边缘计算路径规划平台的仿真

Table 1. Comparison of key factors between target algorithm and A* algorithm in complex environment (M = 0.5, twenty-one terminal users)

表1. 在复杂环境中(需求参数M = 0.5，21个终端用户)，对目标算法和A*算法的关键因素进行比较

Table 2. Comparison of key factors between target algorithm and A* algorithm in complex environment (K = 2, twenty-one terminal users)

表2. 在复杂环境中(风险参数K = 2，21个终端用户)，对目标算法和A*算法的关键因素进行比较

表1和表2比较了目标算法和A*算法在相同的复杂环境下的路径规划所计算出的性能。从表1和表2可以看出，A*算法在风险参数过高时会陷入死解，这表明，A*算法无法适应高风险的地图。A*算法在为保持能量消耗、平均风险和平均路径长度时，会放弃服务质量，使得服务质量降低，导致未满足部分终端用户的需求。并且，在一些情况下，平均路径长度反而会高于目标算法。

通过比较，可以看出目标算法在保证服务质量保持较好的同时，在对比A*算法的避开高风险从而放弃服务的平均路径长度和能量消耗上，还可以保持较低的消耗水平。

4. 结论

本文在现有无人机路径规划中，加入考虑能量消耗和多无人机合作执行，使之在奖励矩阵中考虑动态障碍物和终端需求以及无人机在飞行过程中和为终端用户提供服务时的能量消耗。这些因素加强了现实无人机所考虑的多方位需求和复杂情况，使得更接近于真实环境。实验结果表明，目标算法在复杂场景中，可以表现出很好的可靠性、低耗性以及合作性，并优于其余基准算法。在未来的研究当中，无人机领域还需要考虑更多现实因素，比如无人机的耗电或者满足于服务质量对于无人机速度的改变之间的关系等，这些因素仍然有待深入学习和整合，以使相关理论具有更强的说服力。

NOTES

^*通讯作者。