基于移动边缘计算的无人机资源分配及轨迹优化∗

崔维庆

（中国石油大学（华东）计算机科学与技术学院 青岛 266580）

1 引言

近年来，传感器网络被广泛应用到农作物环境检测、森林火灾检测、健康监护、交通控制以及家庭自动化等领域，可以有效地检测温度、湿度、压力、声音及运动状态等信息。然而，传感器网络中的传感器设备电池容量有限且计算能力有限，并且位置偏远或恶劣环境中的传感器不方便进行信息采集处理［1］。这对传感器设备带来了许多挑战。

将无人机应用到传感器网络中利用了移动边缘计算（MEC）的思想［2～3］，无人机作为移动边缘云更加靠近传感器，能够减少路径损耗［4～6］，进而提高传感器设备的上传速率，为MEC 系统带来更大的收益。另一方面，MEC 系统中的无人机给传感器设备带来便利的同时也造成了也给自身带来了相当多的能耗［7］，并且优化无人机在整个MEC系统中的资源分配可以合理利用无人机作为边缘云和移动基站的计算资源和通信资源［8～9］，设计无人机的飞行轨迹可以减少无人机的飞行能耗并且给传感器设备带来更加有力的通信条件［10～11］。Zeng 等设计一种新型的基于时分多址的工作流模型，并联合优化无人机和物联网设备之间的通信关联、计算资源、无人机悬停时间和物联网设备的服务序列来最小化无人机的总能耗［12］。Mei 等将无人机作为边缘云为每一个地面终端配备了移动克隆，通过网络功能虚拟化实现的移动克隆来执行地面终端卸载的任务，最终使用块坐标下降法得到最优的资源分配和无人机轨迹［13］。

本文将无人机作为移动基站收集传感器设备的信息，并作为边缘云与中央云共同分析处理收集到的数据。首先根据数据流动方向设计无人机端的任务缓存模型，动态表示系统中的数据流向。然后使用基于天牛群算法的块坐标下降法来优化无人机的通信资源、计算资源和飞行轨迹来最大化无人机的能耗效率，并且引入Cubic混沌映射和Lvy飞行对天牛群算法进行改进。

2 问题描述

2.1 通信模型

传感器网络中无人机支持下的移动边缘计算系统模型如图1 所示，其中中央云与基站有线连接。无人机作为移动基站配备有信号收发器可以为传感器提供通信服务，并且作为边缘云配备有轻量级服务器可以提供计算服务。本文采用部分卸载策略，无人机接收传感器上传的数据并在本地处理一部分数据，然后将剩余数据卸载到中央云，无人机可以同时进行数据收集、数据处理和任务卸载。

图1 无人机支持下的移动边缘计算系统模型图

为了结合现实，无人机支持下的移动边缘计算系统使用了一个三维的欧几里得坐标。M个异构传感器不均匀地分布在二维平面内，在平面内的位置表示为qm=[xm,ym]，m∈M，M=｛1，2，…，M｝，并且这些传感器设备的坐标对无人机来说是已知的。在整个任务处理期间，无人机在一个固定的高度H 飞行，并且本文将无人机轨迹分解为N条轨迹段，用N+1 个轨迹点来表示，n∈N，N=｛1，2，…，N｝。表示无人机在第n条轨迹段飞行的时间。传感器设备中的任务数据可分，即可以在两个或多个服务器中处理该数据并将反馈的结果统一分析。将每个传感器设备中待处理的任务定义为｛Rm,Fm｝，m∈M。Rm表示第m个设备待处理任务的数据规模，Fm表示处理任务所需的CPU周期数。

本文使用正交频分多址来消除传感器与无人机之间的通信干扰［14］，无人机和传感器m之间的信道增益表示为

其中β0是距离为1m 时的信道增益；dm,n表示无人机在第n条轨迹段与传感器m之间的距离；‖∙‖表示欧几里得范数。则传感器m在无人机第n条轨迹段的上传速率表示为

其中αm[n]B1表示分配给传感器m的带宽；Pm是传感器m的上传功率；σ2表示传感器m上的噪声功率。值得注意的是，当无人机在第n条轨迹段和传感器m没有通信连接时，Vm[n] 的值为0。

当无人机接收到传感器上传的数据后，其中一部分数据在本地进行处理，另一部分卸载到中央云，卸载速率表示为

2.2 任务缓存模型

对于本地计算方法，本文假设无人机数据的一部分βDn（β∈［0，1］）在无人机本地处理，则剩余的(1 -β)Dn卸载到中央云上处理，本文定义fn≤Fu为无人机的计算能力（每秒的CPU 周期数），Fu表示无人机服务器的最大计算能力。

对于中央云服务器计算方法，中央云边收集无人机上传的数据边进行分析处理。中央云有充足的计算能力能够确保数据在有限时间内处理完成。让Hn表示无人机在每一轨迹段终点的队列长度，表示为Hn+1=Hn-Dn+An。An表示无人机在第n条轨迹段接收到的数据，表示为

Dn表示无人机在第n条轨迹段在本地处理的数据以及卸载数据的总和，表示为

其中∅=0.025 表示处理单位比特数据所需的CPU周期数，并且本文假设无人机从第2 条轨迹段开始处理和卸载数据。则在时间T内处理的总数据量表示为

2.3 能耗效率模型

本文的目标是最大化无人机的能耗效率，首先建立无人机的能耗模型，无人机的能耗由三部分组成：本地计算的能耗、卸载数据的能耗以及飞行能耗。无人机服务器在本地处理数据的能耗表示为

其中k=10-26表示能量转化能力。无人机在整个任务处理时间T内卸载数据的能耗表示为

本文所使用的无人机为固定翼无人机，其能耗模型表示为

其中c1和c2是两个与无人机重量、飞行翼范围及密度有关的常数；v[n]表示无人机在第n条轨迹段的飞行速度，表示为

其中‖qu[n] -qu[n-1]‖表示无人机在第n条轨迹段的飞行距离。

2.4 问题描述

本文的优化问题是最大化无人机在传感器网络中的能耗效率。让F=｛fn,∀n∊N｝，P=｛Pn,∀n∊N｝，T=｛tn,∀n∊N｝，Q=｛qn,∀n∊N｝，则问题P可以表示为

其中C1 是有关无人机飞行时间的限制条件；C2 确保无人机的上传功率在可控制的范围内；C3 确保无人机的计算能力不超过其最大限制；C4 确无人机的飞行速度在可控制范围内；C5 确保在每条轨迹段内无人机和传感器设备之间的距离基本不变。

3 基于天牛群算法的块坐标下降法

问题P 的目标函数和限制条件有非凸性，因此本文使用块坐标下降法来分布迭代求解问题P，得到最优的资源分配和无人机轨迹。

3.1 资源分配

本文首先将问题P 转化为两个有关计算资源F和通信资源P的子问题P1和P2，问题P1表示为

问题P2表示为

本文对问题P1和问题P2分别使用KKT 条件和拉格朗日乘子法求解［15］，得到最优的计算资源F*和通信资源P*。

3.2 轨迹优化

根据得到的最优的计算资源和通信资源，本文将问题P 转化为两个有关无人机飞行时间T和无人机轨迹Q的子问题P3和P4，问题P3表示为

不难看出问题P3是一个线性规划问题，本文使用Matlab里的linprog函数对问题P3求解得到最优的无人机飞行时间T*。

有关无人机飞行轨迹的子问题P4表示为

本文使用改进的天牛群算法来求解此问题［14］，天牛群算法结合了天牛须算法和粒子群算法［15～16］，解决了传统天牛须算法面对多维问题收敛性差的问题。并且本文引入了Cubic混沌映射生成多样性的初始种群［17］，引入Lvy 飞行策略扰动最优个体位置避免求得局部最优解［18］。基于Cubic混沌映射与Lvy 飞行的天牛群算法介绍如下：

首先，使用Cubic 混沌映射生成多样性的初始种群：

其中i∊I表示第i个天牛，I=｛1，2，…，I｝，ρ为控制参数。

天牛须长与最优的种群位置和个体最优位置相关，因此每架无人机的左右须长表示为

其中β表示缩放因子。

然后每架无人机的左右须坐标分别表示为

每架无人机的速度更行方式为

其中ω表示惯性权重；C1和C2是两个常数代表学习因子；A*B 表示具有相同形状的矩阵A 和B 对应元素逐个相乘。本文设置惯性权重和缩放因子随时间递减来增强前期的全局搜索能力和后期的局部搜索能力。

另外本文定义增量函数ξ的更新方式为

其中λ=0.6。

然而，启发式算法容易出现早熟收敛状态，此时无人机最优位置为一局部最优解，无人机通常向无人机群最优解位置靠近，从而导致无人机聚集在局部最优解附近。为了使无人机跳出局部最优解，本文对最优的无人机位置使用Lvy 飞行对进行扰动，使其跳出局部最优解，Lvy 飞行扰动表示如下：

3.3 算法实现

基于天牛群算法的块坐标下降法流程如图2所示。

4 实验分析

本文将基于天牛群算法的块坐标下降法应用于传感器网络中无人机的资源分配和轨迹优化，使用Matlab软件进行算法仿真实验，本文提出的算法和对比算法均部署在Windows 10，64bit；Matlab 2018b，处理器为AMD Ryzen 5600H；主频为3.3GHz；内存为16.0GB。

本文假设传感器设备不均匀地分布在100×100 m2的地面上，且基站的坐标为［0，0］，具体的参数如表1所示。

表1 模拟实验所用的参数

使用基于天牛群算法的块坐标下降法得到的无人机轨迹如图3所示。

图3 无人机轨迹图

为了验证本论文提出的算法（OP）的有效性，将其与另外三种方法进行比较，方法1 采用了二元卸载策略（BOM），方法2 使用了网络功能虚拟化技术（NFV）［12］，方法3使用了工作流调度（WS）［13］。如图4 所示，以收集数据规模为横坐标，以无人机能耗效率为纵坐标画出本论文算法与其他方法的对比图，能够直观看出采用本文基于天牛群算法的块坐标下降法的能耗效率要大于其他三种方法。这说明本文提出的算法性能更好，并使得无人机的能耗效率更高，进而降低无人机能耗给传感器网络中的无人机带来更大的收益。

图4 无人机能耗效率对比图

5 结语

基于传感器网络中传感器设备计算能力不足和不方便收集处理其存储数据的问题，本论文提出一种传感器网络中无人机支持下的移动边缘计算系统模型。首先设计一种无人机端的任务缓存模型动态表示数据流动方向，然后提出一种基于天牛群算法的块坐标下降法来优化无人机的通信资源、计算资源和飞行轨迹，其中天牛群算法中引入了Cubic 混沌映射和Lvy 飞行策略能够得到最优的无人机轨迹，最终得到了最大的无人机能耗效率。实验结果表明，该算法能够显著提高无人机的能耗效率，从而保证无人机给传感器设备带来计算服务的同时能够有效控制自身功耗。