无人机辅助的移动边缘计算中的任务分配策略

王岱巍，徐高潮，李 龙

（吉林大学计算机科学与技术学院，长春 130012）

0 引言

随着物联网（Internet of Things，IoT）的普及以及移动应用程序功能的日渐强大，用户设备（User Equipment，UE）的计算需求已达到前所未有的水平。移动边缘计算（Mobile Edge Computing，MEC）技术由于可以在较小的延迟下为资源受限的UE提供处理计算密集型任务的能力，受到学术界和业界的日益关注。标准化组织和行业协会如欧洲电信标准化协会（European Telecommunications Standards Institute，ETSI）和5G汽车联盟（5G Automotive Association，5GAA）已经确定了MEC 的几个应用场景，主要有智能视频加速、可感知应用程序的性能优化、万物互联、大规模机械化通信等［1-2］。MEC 的基本原理是通过在接入点（Access Point，AP）部署云服务器，使UE 的计算任务可以在无线网络的边缘完成，从而将UE 从繁重的计算工作任务中解放出来并延长其电池寿命［3-4］。

当前对于MEC 的应用中，提高系统能效或减少各种基于蜂窝网络的MEC 系统的等待时间的相关研究主要有文献［5-10］。文献［5］中研究了多输入多输出（Multiple Input Multiple Output，MIMO）的MEC 系统，通过联合优化通信功耗和计算资源将总能耗降至最低；文献［6］中研究了具有边缘云和中心云并存的两层异构网络，并且对计算卸载的目标选择进行了优化以最大限度地减少网络通信的能耗；文献［7-10］中考虑将无线电力传输（Wireless Powered Transmission，WPT）技术应用到MEC 系统中，这使UE 能够为其无线通信和本地计算提供可持续的能量供应，但增加了系统的复杂度。

此外，由于无人机（Unmanned Aerial Vehicle，UAV）在通信方面的诸多优势如按需部署、快速部署、视距通信等［11］，使用UAV协助的MEC服务有着巨大的前景。对此，有诸多侧重点不同的相关研究。在文献［12］中，对于UAV辅助的MEC系统，使用一种两阶段交替优化的方法，获得了使能量效率最大化的飞行轨迹与通信和计算资源的分配；在文献［13］中，研究了启用WPT 技术的支持UAV 的MEC 系统，其中UAV 可以提供能量发送和MEC 服务，以便为UE 供能以及计算卸载。通过交替算法，解决了在局部和二进制泛洪模式下的计算速率最大化问题。在另一项研究［14］中，UAV 作为UE 而不是MEC服务器，由多个蜂窝地面基站提供服务以计算UAV 产生的任务。通过连续凸逼近（Successive Convex Approximation，SCA）算法，优化了资源分配策略和UAV 轨迹，使UAV 的任务完成时间最小化。此外，在文献［15］中，考虑将多架UAV 以固定的飞行轨迹作为边缘服务器为一定范围内的UE提供服务，通过使用强化学习解决混合整数非线性规划的方法，使UE的能耗最小化。

尽管应用广泛，但限制UAV 在移动边缘计算中广泛应用的最主要原因在于，UAV 使用电池供能，其保持飞行状态的时间和机载计算设备的计算能力都是有限的。为此，文献［16-18］中的研究主要针对UAV 的能耗进行优化：文献［16］中研究了基于UAV 的MEC 系统，在此模型中UAV 可以提供计算能力，帮助UE 计算其任务，通过使用SCA 方法共同优化任务分配和UAV 的轨迹，将UAV 的总能量消耗降至最低；文献［17］中分别考虑了UAV 和UE 两者各自的能耗，并基于不同的帕累托最优权衡得出了不同的轨迹与通信功率；文献［18］中通过推导出旋翼UAV 的能耗计算公式，使用SCA 联合优化了飞行轨迹与通信策略，解决了旋翼无人机的能量最小化问题。

此外，如果UE分布比较分散，单次飞行很难对于全部UE实现访问覆盖，因此可能需要多次派遣UAV 来完成全部覆盖或者派遣多架UAV 共同工作，因此，减少派遣次数或派遣数量，将有效地降低收集全部数据所需的时间或成本。为此，考虑在派遣UAV完成任务之前，对终端和UAV进行预分配。通过多次飞行遍历多个聚类中的终端，UAV 可以完成大规模的访问与通信任务。为此，可以考虑使用聚类算法对地面UE进行划分，从而将大规模的任务分成多个子任务来执行。在文献［19］中，使用了自组织特征映射（Self-Organizing feature Map，SOM）网络对用户进行实时聚类，该聚类以信道增益作为判断类别的指标，得到了UAV 的最佳部署位置；在文献［20］中，提出了一种基于最小包围圆和改进K均值聚类算法（K-means clustering algorithm）的无人机基站优化部署方法，解决了无人机基站在无线通信中的位置部署和轨迹优化问题。当前基于欧氏距离的聚类方法主要有K-Means 算法及其衍生的改进算法、迭代自组织数据分析（Iterative Self-Organizing DATA analysis，ISODATA）方法等，对于K-Means 算法和类似的改进算法，聚类数目需要预先确定，而在本文场景下，不同的地面节点分布、不同的数据传输量，都会导致最佳的聚类数目不同，因此难以预先确定；对于自适应的ISODATA 算法，其诸多的初始参数在本文场景下也难以确定。

在此背景下，本文设计了一种适用于UE大范围分布的场景下使用UAV 对计算卸载数据进行收集的解决方案。首先，运用现有的对于旋翼UAV 的功率计算函数及无线通信的能耗函数推导出本文描述场景中的能量消耗函数，并将问题设定为在多个约束条件下该函数的最小化，该问题需要优化UAV 的飞行轨迹、飞行速率以及UAV 的通信策略，是一个非凸的问题；之后，通过使用连续凸逼近方法，可以将原非凸问题转化为迭代求解凸优化的问题，在每次迭代时同时更新UAV 轨迹和通信时间分配；最后，可以收敛到一个满足原问题KKT（Karush-Kuhn-Tucker）条件的解。

在获取了能耗最小化的策略后，进一步设计了一个自适应的聚类方法，通过多次迭代进行分裂与合并，获得合适的聚类策略，以保证每个聚类簇中所有的UE都可以在一次飞行中访问，且聚类的数量尽可能地少，从而减少UAV 的起飞次数以提高覆盖效率，或减少UAV 的派遣数量（对于多UAV 访问多个聚类的场景）以降低覆盖成本。

1 系统模型及问题描述

1.1 系统模型

如图1 所示，考虑一种UAV 辅助的移动边缘计算下的数据收集场景。

图1 无人机协助的移动边缘计算系统Fig.1 UAV-assisted MEC system

在此场景下，在地面上有N个UE，表示为集合N={1，2，…，N}，对于序号为n的UE（n∈N），其位置在三维坐标系中表示为wn={xn，yn，0}，并有Offn大小的计算卸载数据需要上传到边缘服务器上。UAV 在此场景下作为移动边缘服务器的数据收集器，对全部UE的计算卸载数据进行接收。将UAV 接收全部UE 数据的总时间表示为Tt，设UAV 的飞行高度恒定为H，其在t时刻的位置表示为loc(t)=(xt，yt，H)，0

其中β0表示距离为1 m 时的信道功率增益。根据香农公式，UAV与第n个UE之间的传输速率Rn(t)可以表示为：

其中：B为信道带宽；P为UE 的通信功率；σ2表示噪声功率，表示单位距离为1 m 时的信噪比；将第n个UE在t时刻的通信状态表示为Sn(t)，当等于1 时表示第n个UE在t时刻与UAV 通信，0表示不通信。由于在TDMA 接入方式下UAV 在某个时刻t只能与1 个UE 通信，因此可以得到以下约束：

因此，在总的飞行时间里，UAV 与第n个UE 之间的传输数据量DATAn可以表示为：

由于UAV 需要收集所有UE 的数据，对于DATAn有以下约束：

1.2 UAV能耗模型

由文献［18］中的研究可以得到，旋翼UAV 的飞行功率与速度之间的关系为：

其中各个参数的具体含义如表1所示。

表1 UAV相关参数Tab.1 UAV related parameters

当速度为0 时，悬停功率可以表示为P0+Pi，由式（6），UAV在其飞行总时间内的能耗可以表示为：

其中v(t)=。对于UAV 的通信能耗，设其在t时刻的通信功率为Pcomm(t)，因此，UAV 在飞行期间的通信能耗可以表示为：

考虑到UAV的最大通信功率为Pc，则有以下约束：

因此，UAV的总飞行能耗可以表示为：

1.3 聚类模型

由于UAV 板载电池的储存电能有限，在大传输量或大分布范围的场景下，单机单次飞行无法收集全部的计算卸载数据，需要派遣多架UAV同时执行任务或单架UAV多次起降执行任务。为此，将UAV 执行的任务分成c个独立的子任务，对于每个子任务taski(i∈[1，2，…，c])，将会在一次飞行中完成对于若干个UE进行计算卸载数据的收集。将地面上的UE作为样本，将UAV 需要执行的子任务数量c作为聚类数目，就可将问题转化为将地面的N个样本划分成c个聚类的问题。

首先，用Γi(i∈[1，2，…，c])表示第i个聚类，其中的样本数表示为ki，则需要满足约束：

此外，用Ei(i∈[1，2，…，c])表示UAV 收集聚类Γi中全部样本所消耗的最小能量，将UAV 板载电池储存的能量表示为Ecell，则需满足以下约束：

1.4 问题描述

基于以上讨论，减少聚类的数量，将会减少派遣UAV 的成本，为此就需要UAV 以尽可能节能的策略飞行，从而可以在一次飞行中尽可能遍历更多的UE，因此，问题被分为能耗最小化和聚类数量最小化两个问题。

对于能耗最小化问题，可以公式化表示为P1：

对于约束（18），由于UAV 使用场景的局限性，通常难以在任意位置起降，因此在本文模型中，考虑将起飞和降落点都设为同一个点loccenter。

对于聚类数量最小化问题，可以公式化表述为P2：

由于在P2 的约束（12）中，Ei的计算依赖于对P1 的求解，因此，接下来的工作首先解决P1，得到一个计算Ei通用的方法，再根据此方法解决P2。

2 能量最小化方法

由于问题P1是建立在连续时间变量上的，需要优化的变量也是无限多的，无法有效求解，因此需要将其转化为有限个变量的优化问题。首先将其飞行轨迹loc(t)转化成有限个，将其细分成M个线段。在此，M的取值要足够大，使每一个线段m的长度足够小，以使在每一个线段m∈[0，1，…，M-1]中，UAV 与各个UE 间的距离以及通信功率均可视为不变，从而可以将UAV 的轨迹近似视为M个固定的坐标点组成的集合。为此，需要M+1个点来将路径离散化，将这些点表示为集合{locm}，m∈[0，1，…，M]，其中，loc0=locM=loccenter，UAV 执行任务的时间Tt也可以离散化为M个时间片段{Tm}，m∈[0，1，…，M-1]，Tm表示在线段m上的飞行时间。由于UAV 有飞行速度上限Vmax，在任意一个线段m上的飞行速度都不可能大于Vmax，因此可以将P1的约束（14）改写为：

将路径离散化后，UAV 与第n个UE的距离不再是一个连续函数，而是M个表达式的集合。

将UAV 在线段m上飞行时与第n个UE 的通信时间表示为τmn，则需新增约束：

通信功率Pcomm(t)也可以离散化表示为Pm，m∈[0，1，…，M-1]，从而可以将约束（17）改写为：

对于P1中起飞和降落点的约束（18），同样可以改写为：

用Δm=‖locm+1-locm‖，m∈[0，1，…，M-1]来表示线段m的长度，则UAV 在线段m上的平均飞行速度vm可以转化成Δm/Tm。将上述生成的离散化变量集合带入P1 的目标函数中，可以将原目标函数改写为：

最终，可以将P1转化为有限变量的优化问题P3，表示为：

P3 仍然是一个非凸问题，因为目标函数E({locm}，{Tm}，{τmn}，{Pm})以及约束（22）都是非凸的，难以直接求解，因此需要对其进行转化。首先，对于目标函数的第一个非凸项，考虑到UAV 的主要能耗是保持飞行状态所需的机械能耗，其通信能耗相对而言很小。因此，虽然减小通信功率可以降低一部分通信能耗，但是也会导致接收速率变低，从而使UAV 收集同样大小数据的时间变长，为此UAV 需要额外的悬停或飞行时间来完成任务，由此导致的额外机械能耗远大于节省的通信能耗。因此，想要最小化UAV 的飞行能耗，就必须将网卡的通信功率保持为UAV 所能提供的最大通信功率Pc以保持最大的数据接收速度。因此，可将其转化为凸表达式，并将约束（23）省略。

此外，对于非凸约束（22），引入第二个松弛变量集合{ψmn}，将其表示为：

从而可以将式（22）改写为：

通过代换，可将松弛变量ψmn与原变量的关系表示为：

由定理1，问题P3可以转化为等价问题P4：

定理1P3和P4等价。

证明 P3 与P4 的差别在于P4 中将松弛变量与原变量的关系表达式（27）、（30）变成了不等式约束（32）、（31），若P4 有一个解使约束（32）满足严格不等条件，那么若不断减小松弛变量φm，直到使约束（32）满足严格相等条件，目标函数E也会随之逐渐减小，因此，此解一定不是P4 的最优解，对于约束（31）同理。因此P4 的最优解一定可以使约束（31）和（32）满足严格相等条件，此时的目标函数与约束都与P3 相同，因此P3与P4等价。证毕。

由于非凸约束（29），（31）和（32）的限制，P4 仍然非凸，然而，这3 个约束中的非凸表达式都可以通过替换获取其在某个局部解的全局下界，从而将非凸表达式转化为凸。对于约束（29），由于凸函数的一阶泰勒展开式可以视为凸函数的全局下界，可以将凸表达式在局部点处展开，获取其在的全局下界，表示为不等式：

对于约束（31）中不等式右侧的表达式，虽然因为非凸不能使用一阶泰勒公式的性质，但可以由定理2 获取其全局下界，定理2表示如下：

证明 见文献［21］中的定理2。

最终，将P4 中约束（29）、（31）和（32）中相关表达式替换为在局部点的全局下界表达式（33）、（35）和（34），可以将P4转化为P5：

P5 在转化后变成了一个凸问题，可以使用相关的工具包进行求解。在算法1 中，通过将P5 中的局部点逐步逼近到使目标函数值更小的点，可以使每一轮迭代产生的局部最优值逐渐趋近全局最优值。当两轮迭代求得最优值的比值大于给定阈值ε时，算法收敛，获得的解可以视为原问题P3的近似最优解。算法1如下。

算法1 基于SCA的迭代算法。

算法的收敛性由定理3可知。

定理3算法1 每轮迭代的最优值单调递减且计算出的最优解满足原问题P4的KKT条件。

证明 为方便起见，将P4 和P5 中的变量简单表示为x，将P4 中的约束表示为fi(x) ≥0，∀i∈[1，2，…，I]，将算法1 中第j轮迭代计算P5时的全部约束表示为gi，j(x) ≥0，∀j、∀i∈[1，2，…，I]。

首先，由于在算法1中，第j轮迭代求解P5时的全部约束，一部分是将P4中的约束改写成了在某个局部点的全局下界，另一部分为原约束，因此可以满足gi(x) ≤fi(x)。

由于满足以上3 个条件，根据文献［22］中的命题3 可知，算法1 最终迭代产生的解可以视为原问题P4 的近似最优解，且在此最优解下的各项最优值均满足原问题P4的KKT条件。证毕。

3 自适应聚类方法

通过第2 章提出的能量最小化算法，可以在给定地面UE分布和数据传输量要求时，获取使UAV 能耗最小的飞行轨迹、飞行速度以及与各个UE之间的通信时间。接下来据此对地面上的终端进行聚类，以减少飞行的次数或派遣UAV 的数量。为此，设计了一个以飞行能耗为聚类标准的自适应聚类算法来解决P2，其具体步骤如算法2所示。

算法2 基于分裂与合并的自适应聚类算法。

步骤1 将地面的N个UE表示为样本集{w1，w2，…，wN}，c为聚类的数量，Ui(i=1，2，…，c)为初始的聚类中心。在算法开始时，令c=1，随机选取一个点Um作为聚类中心。

步骤2 按照以下关系

若‖w-Ui‖≤‖w-Uj‖；i，j=1，2，…，c且i≠j，则w∈Γi

将样本分到各个聚类中去；

步骤3 按照以下关系

更新聚类中心Ui的位置，其中Ni是第i个聚类的样本数目，wk为聚类Γi中的第k个样本点。

步骤4 将Ui作为UAV 起飞和降落的地点loccenter，将聚类中的样本作为此次飞行需要完成数据收集的UE集合，通过算法1计算其总能耗Ei。

步骤5 对于每一个聚类Γi(i=1，2，…，c)，判断其总能耗Ei是否小于UAV机载能量Ecell，对于满足能耗限制的聚类，将此聚类的样本点及其总能耗Ei保存；对于超出机载能耗的聚类Γj，进入步骤6；当本步骤保存的全部聚类均满足能量约束时，进入步骤9。

步骤6 计算当前不满足能量约束的聚类Γj的标准差向量σj=[σjx，σjy]T，其中：

步骤12 计算以Unew为loccenter，以Γnew中的全部样本作为需要完成计算卸载任务的UE 集合产生的能耗Enew，若Enew≤Ecell，则删除生成Γnew的两个原聚类，并使Γnew生效，令c=c-1，回到步骤9；如果Enew>Ecell，说明不可合并，回到步骤10，从之前保存的位置向后继续搜索。

算法2的整体流程如图2所示。

图2 算法2的流程Fig.2 Flowchart of algorithm 2

进入步骤9 之前，算法通过不断的分裂，将样本分成多个满足能量约束的聚类。由于某些特殊情况如样本存在离群点，在步骤7 中通过标准差选择的新聚类中心不合适等，分裂出的某些聚类内样本非常少，因此在步骤9～12将会尝试对分裂完成后的聚类进行合并。在步骤10 中，以聚类之间的距离Dij作为合并的优先级，Dij越小，优先级越高。由于当两个聚类各自的能量消耗之和大于Ecell时，合并出的新聚类将需要更多的能耗来完成数据收集任务，因此只有当两个聚类能量消耗之和小于机载能量Ecell时，才会尝试进行合并。在步骤12 中，一旦完成了合并，之前使用的递增距离序列{Dij}将会失效，因此将返回步骤9 重新生成新的序列。若不能合并，则返回步骤10 继续向后搜索下一个有合并可能的两个聚类。当步骤10 遍历完{Dij}时，所有可能的合并操作已全部完成，算法结束。

4 仿真实验与分析

为验证所提出的能耗最小化算法和聚类算法的效果，设计了4个仿真实验，首先，在一个给定的UE 分布条件下，通过计算本文提出的能量最小化算法在不同卸载数据量下对应的飞行轨迹来获取结果，并分析其合理性。接着，设计了几种不同的飞行轨迹方案来验证本文设计的算法在能耗方面的优化。之后，为了呈现聚类算法的效果，在给定UE 的分布条件和各自的计算卸载数据量大小的情况下，将UAV 机载电池的能量作为变量，在固定的数据卸载量下获取相应的聚类结果。最后，在本文描述的应用场景下，使用一种递增聚类中心数目的K-Means 聚类算法与本文提出的聚类算法进行对比，来验证本文提出的聚类算法的高效性和普适性。

4.1 实验环境与初始参数

仿真实验运行在使用Intel Core i7 8750H 处理器，主频为3.9 GHz，内存为16 GB，操作系统为Ubuntu16.04 的计算机上，仿真程序代码使用Python2.7 编写。对于优化模块，使用解决非线性优化问题的方法包PyOpt［23］来求解，使用的优化器有SLSQP、ALGENCAN、NSGA2。

首先，对于UAV 相关参数，设UAV 重量W=20 N，空气密度ρ=1.225 kg/m3，螺旋桨半径R=0.4 m，螺旋桨梢速Utip=120 m/s，螺旋桨转盘面积A=0.503 m2，悬停时转子的感应速率v0==4.03，螺旋桨叶片功率P0=79.856 W，感应功率Pi=88.628 W，网卡最大通信功率Pc=5.0 W，螺旋桨在转盘中的面积占比s=5%，UAV 的最大飞行速度Vmax=30.0 m/s。

此外，对于能耗最小化模块，设置信道带宽B=1MHz，UAV 的飞行高度H固定为100 m，噪声功率σ2=-110 dBm，UE 的通信功率P为10 dBm，信道功率β0=-50 dB，由此可以计算出γ0=70 dB。

在算法1中，需要生成初始的轨迹集合、UAV 在每条线段m上的飞行时间集合以及在线段m上与第n个UE 的通信时间集合。在此，为了生成一个合理的初始值集合，使用动态规划（Dynamic Programming，DP）求解旅行商问题（Traveling Salesman Problem，TSP）的方式，计算出以聚类中心为起点和终点，连接所有样本点的最短路径。然后将这条最短路径离散化为M+1个点作为。之后计算出在此下可以满足P3 约束的最小时间Tˉ作为集合中的每一项，并令τmn=作为的每一项，生成的结果作为算法1的初始值。实验设置了10个UE的位置，并将M设为30，以平衡精确度和算法的运行时间。将全部N个UE 的计算卸载任务量Offn统一为同一个值，表示为Off，以方便算法的实现。

对于聚类模块，由于在特定场景下，某个聚类中可能只含有一个样本，而通过聚类算法计算的聚类中心位置，即起飞和降落点，也为此UE 的位置，因此，在实验中，设UAV 访问只有一个UE 的聚类时，飞行速度为0，在UE 的上方悬停，因此其产生的能耗仅与UE 的计算卸载任务量Offn有关。此外，设置聚类分裂时的分裂系数q=0.8。

4.2 结果与分析

首先，10 个UE 的位置如图3 中所示，分别将数据传输量Off设置为0.1 Mb、1 Mb、10 Mb、100 Mb，使用所提出的能量最小化方案，获得的轨迹如图3所示。

图3 四种数据传输量下的飞行轨迹对比Fig.3 Flight trajectories comparison under four data transmission amounts

由图3（a）可知，当吞吐量较小时，UAV 趋近于以一个半径较小的接近环形的轨迹飞行，而不会向UE 的方向显著偏移，这可以理解为当传输量小时，虽然UAV 以此轨迹飞行会导致自身与UE 的距离较远，传输速率较低，但是由于数据量很小，传输速率降低导致的通信时间增加所产生的额外能耗并不如飞行时向UE偏向而产生的机械能耗大；当数据量足够大时，从图3（d）中可以看出，UAV 趋近于在每一个UE 上方盘旋和悬停来与UE 通信，这也可以理解为由于数据量大，需要传输速率更快，这样减少了总通信时间也就减少了飞行和悬停的时间，而由此节省的能量要大于向UE偏向所产生的额外机械能耗。当吞吐量在一个适中的大小时，如图3（b）、（c）所示，UAV 的轨迹会向UE 的位置偏移但不会飞至UE 的上方，这是优化算法在飞行能耗和通信时间之间做出的权衡。

接下来，为了体现本文方案在能量上的优化效果，本文额外设计了两种使用固定轨迹的方案作为对比：第一种将UAV设置为在全体UE 的中心（质心）上方悬停，表示为CENTER；第二种使UAV 沿着TSP 算法生成的固定轨迹飞行，表示为TSP，这两种方案相对简单且易于实现；将本文所提出的能量最小化方案表示为ENERGY。在不同数据传输量Off下的能量消耗如表2所示。

从表2 可以看出，当数据量较小时，能量最小化方案对比TSP 方案具有显著的优势，这是因为其飞行距离较短，节省了许多飞行能耗，而由于其飞行轨迹接近于在起飞点附近盘旋，其结果也接近于悬停方案；当数据量逐渐变大，能量最小化方案的能耗逐渐接近于TSP方案，这是由于数据量变大，飞行轨迹逐渐接近于TSP 的轨迹造成的，而在此时使用悬停方案产生的能耗将会显著变大，这是由于较大的数据量和较低的信道速率导致的较长的悬停时间所导致。而本文所提出的能量最小化方案通过连续凸逼近的方法，平衡了通信速率和飞行距离，在不同的数据传输量下都有着更低的能耗。

表2 无人机在不同飞行方案下的能量消耗 单位：JTab.2 UAV energy consumption under different flight strategies unit：J

对于聚类方案的评估，仍然使用图3 中的UE 分布，在全部UE 的计算卸载的数据量Off固定为10 Mb 的条件下，在不同的机载能量Ecell下聚类的结果和UAV在各个聚类中的飞行轨迹如图4所示。

图4 两种机载能量条件下的聚类结果和飞行轨迹对比Fig.4 Comparison of clustering results and flight trajectories under two airborne energy conditions

在图4 中，在Ecell为10 kJ 时，分成了3 个聚类；在Ecell为15 kJ 时分成了2 个聚类。由此可以看出，UAV 的机载电池储存的能量越大，其在一次飞行中可以访问的UE 数量越多，每个聚类中的样本数量也就越大。若以每个UE 的数据卸载量Off为变量，在同样的机载能量Ecell下，得到的聚类结果也遵循此规律，在此不再赘述。

最后，在多种聚类策略中，基于欧氏距离进行划分的聚类算法适合本文中对UE进行分类的场景，而由于现有的基于划分的聚类算法需要在算法开始时预先确定k个初始中心点，而在不同的UE 分布场景下，合适的k值也是不同的，因此，为了使算法可以在不同的UE 分布场景中获得合适的初始中心点数目，设计了一种递增k的K-Means 聚类算法：从1 开始逐步递增k，在每次迭代中随机确定k个聚类中心的位置并使用K-Means算法获取聚类结果，对所得的k个聚类分别计算UAV访问此聚类的能量消耗，若有某个聚类的能量超出了Ecell，则k=k+1。直到当k到达某个值时，对于每个聚类，其全部UE的计算卸载数据都可以在一次飞行中收集，算法结束，记当前值k=k*。在此，分别使用K-Means 和K-Means++算法作为上述递增k的聚类算法获取聚类结果的方案，将这两组方案计算出的最终聚类数量与本文所提出的聚类算法计算出的聚类数量进行对比。实验样本使用网址http：//elib.zib.de/pub/mptestdata/tsp/tsplib/tsp/index.html 中的数据集att48.tsp，为了提高计算效率，取其中的前40条数据并分成4组，并将其中的每条数据的横纵坐标大小都除以10。在前两组的对比中，将数据卸载量Off设为25 Mb，机载能量Ecell设为20 kJ；在后两组的对比中，将数据卸载量Off设为50 Mb，机载能量Ecell设为25 kJ，最终得出的聚类数量如表3所示。

从表3 可以看出，本文提出的算法产生的聚类数量在几个不同的样例下都小于或等于K-Means 和K-Means++聚类的聚类数量。这是因为K-Means 算法的结果受初始聚类中心的影响较大，而由于在本文场景下，UE 的分布情况在不同的时间、地点时没有可循的规律，只能通过随机生成初始聚类中心的方法来初始化K-Means 算法，当初始聚类中心的位置不够理想时，最终计算出的聚类数量就会偏大，即使使用K-Means++优化了初始聚类中心点的离散程度，由于某些离群点的存在，其结果仍然不够理想。而本文提出的方法通过动态分裂与合并来调整聚类的数量，不依赖初始聚类中心的位置，可以广泛适应不同的UE 分布场景；也不需要逐步递增聚类数目，可以快速收敛。

表3 在不同数据集上三种聚类算法的最终聚类数量Tab.3 Final number of clusters of three algorithms on different datasets

5 结语

针对当前UAV 的应用场景及其局限性，本研究以能量约束作为聚类是否可行的标准、以最小化聚类的数量为目的设计了一个自适应的聚类算法。通过解决给定地面终端分布下的能量最小化问题，获得了一个可以有效判断聚类方案是否可行的依据，并通过多次分裂和合并，在可以快速收敛的前提下将聚类的数量有效地缩减。该方法可以应用在如智能工业、智慧城市等前沿领域，使用UAV 辅助进行大范围的信息采集，数据同步。本文将UAV 的起飞和降落点简单考虑为聚类中心，有一定的局限性。首先，聚类中心所在的位置在现实场景中并不一定支持UAV 起降；其次，UAV 并不一定需要在同一点起降，若考虑起飞和降落点的优化，对于某一聚类内UE 的数据收集所需的能量可能会更小；此外，多次飞行之间并无相互之间的联系，若在地面设置某些固定的可以为无人机充电的起降点，并将UAV 的起降位置设置为这些起降点，就可将完成各个聚类收集任务的轨迹连接到一起，这意味着全部任务的完成将全程自动，具有更强的实用性。而对于能量最小化模块，其目标函数将飞行高度设为定值，并未考虑用户设备的水平高度带来的影响。因此，下一步的研究将会在能量最小化中加入飞行高度变量，以及优化起降点的选择，使模型更加符合各种应用场景的需求。