考虑无人机飞行时间的能耗与数据量联合优化

朱 江，肖 津

重庆邮电大学 通信与信息工程学院，重庆 400065

随着第五代移动通信技术（fifth generation，5G）的规模化应用，各种类型的新兴业务和应用深刻改变了人类社会的生产和生活方式[1-2]。为了满足更多样的应用场景，针对5G以及未来的第6代移动通信（sixth generation，6G）系统，业界和学术界展开了以实现“空天地海”一体化为目标的相关研究。在未来“空天地海”一体化的网络中，UAV作为空基网络层面的组成部分，在一体化网络中起着重要的作用[3]。

在UAV 的众多应用场景中，一项重要的研究分支就是在物联网场景下进行数据采集。物联网节点具有资源受限的特点，因此目前的相关研究是在能耗、时间、频谱等资源的受限条件下，对通信时延、数据量、能效等进行优化。具体而言，有一部分研究是在资源受限条件下实现系统数据量最大化，包括：文献[4]通过联合优化用户关联、UAV 轨迹和每个节点的上传功率解决了一个在UAV能耗约束和用户服务要求下的最大化系统数据量问题。文献[5]考虑单UAV在时间约束下从多个传感器节点收集数据的场景，通过联合设计UAV 三维轨道和传输调度来最大化所有节点最小数据收集率。文献[6]提出了一种通过启用非正交多址技术的UAV辅助数据收集（non-orthgonal multiple access enabled UAV assisted data collection protocol，NUDC）协议，通过联合UAV位置、传感器分组和功率控制进行优化，以最大化传感器网络的总速率；还有一部分研究是以降低节点或者UAV的能耗为目标：文献[7]考虑运用UAV进行数据采集，联合传感节点任务调度和UAV轨迹，以最小化传感器节点能耗进行优化。文献[8]解决了在数据采集和UAV 移动距离约束下，以最大化传感器在数据传输后的最小剩余能量为目标的优化问题。文献[9]为了克服UAV 续航问题，提出了一种利用用户端主动缓存来支持UAV 通信的方案，通过对文件缓存和文件检索成本进行权衡，联合文件缓存策略、UAV轨迹和通信调度进行优化，以最小化UAV能耗。文献[10]通过优化UAV位置与传感器上传功率，解决了在传感器节点能耗有限时最小化UAV 能耗的问题；此外，还有部分文献针对UAV与节点的能耗进行权衡：文献[11]考虑在传感器网络中存在能够收集其他节点数据的簇头，因此UAV 进行数据采集时要与簇头进行通信，为了求解该模型下系统能耗最小问题，文章提出了一种深度强化学习算法，通过仿真证明了方法的可靠性。文献[12]考虑多UAV场景，将UAV的推进能耗和运行成本定义为空中成本，将传感器网络传输能耗定义为地面成本，通过将问题分解为子问题来求解空中与地面成本的权衡问题，子问题采用凸逼近与交替优化求解。

上述研究资源虽然受限，但整体而言资源是能够保证数据采集任务完成的，研究的重点是提高资源使用效率问题。但在某些节点密集部署的场景下，不能保证所有任务能够完成，例如：在战场中，要在有限时间内收集尽可能多的敌方数据；在海量机器类型通信场景下，在有限时间内尽可能多地收集传感器节点的数据等。为了应对这些通信场景，相关研究需要进一步深入。

出于上述分析，本文考虑一个有时间约束的数据采集系统，网络中的每个节点有一定量的数据，UAV要在有限时间内进行数据采集。该问题复杂程度高且高度非凸，为求解此问题，提出了一种初始轨迹优化和二次轨迹优化的两阶段优化方法。在初始轨迹优化阶段提出基于贪心算法和禁忌搜索算法的优化方案，实现节点选择，确定采集顺序。在二次轨迹优化阶段，将初始化轨迹离散化，针对非凸问题采用逐次凸逼近算法，在每次迭代的过程中更新UAV轨迹与传输调度参数。通过迭代找到符合条件的次优解。

1 系统模型

考虑如图1所示的无线通信场景，一架旋翼UAV被派遣到一片区域进行数据采集，并在有限时间内完成数据采集任务。在这片区域内节点数量大，因此UAV 只能为部分节点提供数据采集服务。考虑在实际的应用中，UAV 采集的数据量与采集消耗的系统能耗是评估UAV 采集系统的重要指标。因此，本文方案的目标是在兼顾UAV 飞行能耗与节点传输能耗的前提下，通过轨迹规划和传输调度，尽力而为地提供数据采集服务。该区域有K个节点，节点集合用U={u1,u2,…,uK} 表示，设{k|k=1,2,…,K}，则第k个节点的二维坐标表示为wk∈R2。假设UAV在固定高度H飞行。假设模型规定任务完成时间为T。定义UAV在某一时刻投影在二维平面上的位置为{q(t)|q(t)∈R2,0 ≤t≤T}。定义UAV的最大速度为vmax。因此，在任意时刻t∈[0,T]，UAV与第k个节点之间的距离可以表示为

图1 UAV数据采集模型Fig.1 UAV data collection model

1.1 通信模型

关于UAV到节点的信道模型，根据文献[7]可知：在时刻t∈[0,T]，UAV 与节点k之间的信道系数为hk(t)=其中βk(t)与ρk(t)分别表示大尺度衰落与小尺度衰落系数。大尺度衰落受路径损耗与阴影效应影响会影响额定的传输速率。小尺度衰落通常由多径效应引起，会导致瞬时信道容量低于预定义的传输速率，导致系统中断。大尺度衰落主要考虑路径损耗，主要与通信距离相关，大尺度衰落模型可以表示为：

式中，β0表示参考的单位距离信道增益，此增益值在任务时间T内不变，||q(t)-wk||表示某时刻UAV与节点距离的二范数，下文中出现的||·||均指二范数。假设在任意时刻，UAV 的小尺度衰落为独立同分布的随机变量。那么，香农传输速率为：

B表示系统的带宽；表示节点传输功率，假设功率固定为σ2表示的是加性高斯白噪声功率；Γ＞1 表示系统实际接收信号与理论接收信号的信噪比差异。考虑到小尺度衰落可能会导致系统中断，通过中断概率pk(t)可以推导出累积分布函数F(·)。

假设UAV容忍的最大中断概率为ε。F-1(·)是F(·)的反函数。因此节点k的上行传输速率可以表示为：

因为UAV 飞行时信道系数hk(t)随时间变化，且要与多个节点通信，采用时分多址传输协议。设传输调度相关参数{αk(t)|αk(t)∈{0,1}}表示在t时刻节点k是否进行通信。当αk(t)=0 时表示在t时刻，UAV 不与节点k通信。另一种情况表示进行通信。根据条件在t时刻所有用户传输调度参数的和小于等于1：

在总时间约束T内，其总数据传输量应该满足：

其中，Dk表示采集节点的有效数据量，设在有限时间内采集的节点有效数据和为D；Sk表示需要从节点k采集的数据量，不失一般性，假设对于任意用户Sk=S。式（6）表明总数据传输量大于等于其数据量。对应的任一节点传输能耗可表示为：

1.2 UAV飞行模型

在UAV 通信系统中，除了数据传输产生的能耗还有UAV 飞行产生的能耗。相比于固定翼UAV，旋翼UAV 具有高精度以及可悬停的特性，使用旋翼UAV 进行数据采集可以应对更为复杂的场景。旋翼UAV的功率随速度变化的相关公式由文献[13]给出。出于问题复杂度的考虑，只考虑速度对功率的影响。UAV 飞行功率可以表示为：

公式中的三项分别为：旋翼型阻功率，旋翼诱导功率以及机体阻力功率。式中常数P0与Pi为悬停状态下叶型功率和诱导功率；Utip为桨叶叶尖速度；v0为UAV悬停时转子诱导速度；d0为机身阻力比；s为转子坚固性；ρ为空气密度；A为转子盘面面积。

定义UAV 飞行总能耗为Efly，可以将UAV 飞行能耗表示为：

其中，v(t)=q′(t)为UAV的瞬时速度。

2 联合优化问题描述

基于上述相关通信模型的构建，UAV 数据采集系统中多目标联合优化问题可以表示为：

为了权衡不同量纲的参数，让目标各项落在同一数量级，设置W1、W2、W3为各项对目标函数的加权，具体的数值设置在结果分析中介绍；参数qinitial与qfinal属于R2，表示UAV 投影初始点与终止点。约束C1 描述节点数据传输量满足数据量要求；约束C2描述UAV是否采集某个节点的数据，即Dk=0 表示UAV 不采集k节点数据，Dk=S表示采集；C3 与C4 为传输调度参数的约束；C5为飞行速度约束；C6为飞行轨迹约束。

表1 参数及其定义Table 1 Notation and definition

3 问题求解

为了求解非凸问题P1，将其分解为两个步骤来优化。第一步为UAV 初始轨迹优化，为降低飞行轨迹优化的复杂度，考虑一种飞行悬停方案，基于贪心算法和禁忌搜索算法，找到一条可行初始轨迹，并且确定从哪些节点处采集数据。第二步为二次轨迹优化，在第一步的基础上，进一步对目标函数进行优化。具体而言，通过将轨迹离散将初始问题转化为离散变量问题，针对该非凸问题采用逐次凸逼近技术优化UAV轨迹和传输调度参数，求出优化问题的次优解。

3.1 UAV飞行模型

在UAV 数据采集的轨迹优化方案中，一种较为简单的方法是将模型简化成一个在节点间飞行，在节点投影点上悬停传输的模型[4]。具体到本文的应用场景就是：UAV从一个投影坐标点通过直线飞行，飞到另一个节点投影点悬停，在悬停时UAV 才会采集对应节点的数据，采集完后飞到下一个节点投影点继续采集，在时间耗尽前，综合考虑飞行、传输能耗以及有效数据量来采集数据。在这种模式下，悬停与传输对应，即悬停可以代表UAV进行数据采集，飞行代表不采集数据，那么传输调度参数就可以被忽略。通过初始轨迹优化可以确定UAV 数据采集的节点选择，同时优化得到的解也可作为二次轨迹优化的初始解。

通过上述分析可得，问题P1 的初始解通过求解P2获得。

约束C1 为数据量约束；约束C2 为速度约束；约束C3 为轨迹约束；约束C4 为时间约束。在该阶段W1、W2、W3的设置对轨迹有一定影响，W1设置较大、W2设置较小或W3设置较小时，目标函数中数据量权重增加，即收益增加，飞行能耗和传输能耗权重减小，即成本减少，UAV 会倾向采集更多节点数据。相反条件下，UAV采集节点数更少。求解问题P2可以得到一条从初始点到终点，在节点间飞行，在节点投影点悬停传输的最优轨迹。本质上来看，这个问题被转换成了一个特殊旅行商问题[14]。在常见旅行商问题中遍历的节点数目是固定的，而此问题要格外考虑访问节点数。求解该问题的一个简单的算法是穷举法，穷举能服务的节点数、服务的节点、节点的排序方法，最终找出一个收益最高的访问轨迹。穷举法能得到最优解，但其时间复杂度非常高，约为O(K!)，在K较大时难以求解。因此，初始轨迹优化考虑一种改进贪心算法来求解P2的有效次优解，具体算法如下所示。

算法1初始轨迹优化算法

算法1 采用的启发式算法是禁忌搜索算法[15]，具体过程如下所示。由于不同的启发式算法在时间复杂度上不会有数量级上的差异，所以这里使用其他的启发式算法也可行。考虑时间复杂度，执行次数较多的步骤5包含三层循环，时间复杂度为O(K3)。另一个执行次数较多的是步骤11 使用的启发式算法，复杂度为O(K3Max_GEN)[16]。式中Max_GEN为最大迭代次数。显然，所提算法的时间复杂度远远小于穷举法。

禁忌搜索算法更新轨迹：

3.2 二次轨迹优化

初始轨迹优化考虑的是一个飞行，悬停传输模型。严格来说，这个模型本身就并非最优。考虑将问题分解为两步来解决，能够降低算法复杂度，得到可行的次优解。二次轨迹优化考虑将初始轨迹优化得到的解做进一步的优化。

对连续问题进行求解的有效方法是将连续问题离散化。考虑将时间离散，设δ为时隙长度，设M为时隙的数量，有T=Mδ。假设在每个时隙内信道保持不变，不同时隙间可变。为了简化符号表达，定义{q[m]|q[m]=q(mδ),m=0,1,…,M}表示UAV 在mδ时刻的位置。同理，定义v[m]表示UAV 在m时隙内的平均飞行速度，且满足：

对于传输参数，定义{αp[m]|αp[m]=αp(mδ),m=1,2,…,M}表示在第m个时隙UAV 是否采集p节点数据。在参数离散化之后，目标函数可以写成以下形式：

与问题P1 类似，问题P3 中：约束C1 表示每个通信的节点的数据传输量要满足要求，约束C2描述UAV是否采集某个节点的数据，约束C3 与C4 为传输率的约束，C5 为速度约束，C6 为轨迹约束。在问题P3 中采集数据的节点确定，P1 优化目标中有效数据传输量D为定值可以忽略。约束C1为等式约束，为了求解，对其进行放缩，令

定理1对问题P3 中约束C1 左侧进行放缩不会影响新问题P4与原问题P3的等价性质。

证毕。

为了求解P3，利用松弛函数法和凸逼近（successive convex approximation，SCA）迭代求出其次优解，即通过迭代，在每次迭代的过程中优化松弛函数法放缩得到的凸优化问题，在多次迭代后条件收敛，得到非凸问题P3 的解。对于整数变量传输调度参数，将该变量松弛，即0 ≤αp[m]≤1。约束C1 是一个非凸约束，其中Rp[m]为非凸项，对其用一阶泰勒展开，则其在第l次迭代时满足式（15）。

在飞行能耗相关的函数中第二项诱导功率也是非凸的，引入松弛变量，设：

与约束C1类似，通过放缩松弛变量，让收敛时能保证松弛变量与原参数严格相等。

上式左侧为凸，对右侧进行一阶泰勒展开，有：

将上述所示的公式变化带入问题P3，可以得到如下问题P4：

可以证明如果问题P4 的约束满足要求，那么问题P3的约束也能够满足，即P4的可行域是P3可行域的子集。通过SCA算法迭代，更新局部点，可以获得P3的有效次优解。但P4 的约束C1 左侧依然存在变量耦合问题，为了解耦不妨考虑下式。

在第l次迭代时，通过一阶泰勒展开，可以得到其下界。

那么可以得到以下不等式：

将上式放缩代入P4，可以得到第l次迭代时的优化问题P5：

通过上述推导可知，问题P5是一个凸问题，可以使用现有的凸优化方法工具箱（如CVX）进行优化。使用初始轨迹优化得到的初始轨迹，可以通过SCA迭代，在每次迭代的过程中优化问题P5，在多次迭代后条件收敛，得到非凸问题P3 的解。采用SCA 技术进行迭代，多次迭代后收敛的解即为目标的解。具体算法总结如下：

算法2基于SCA求解P3的算法

4 结果分析

考虑一个节点数K=18的系统，随机分布在2 000 m×2 000 m 的区域。设置初始点与终点分别为：qinitial=[-1 000 m,0 m]T、qfinal=[1 000 m,0 m]T。设UAV 飞行高度H=100 m，通信带宽B=1 MHz，最大飞行速度vmax=50 m/s。设置节点传输功率Pcom=0.1 W，时隙长度δ=0.5 s 。单位距离参考的信道概率增益β0=-60 dB，加性高斯白噪声功率σ2=-110 dBm，系统实际调制方案高斯噪声与理论值的信噪比差Γ=7 dB，UAV容忍的最大中断概率ε=10-2，信道莱斯衰落因子Kc=10，其累计分布函数，其中Qmarcum-Q为Marcum Q 函数，以上参数设置主要参考文献[7]。设置参数W1、W2、W3的目的是让不同量纲的表达式归一化，让它们处于同一数量级，让不同项对目标函数影响相当。具体而言，设置W1=1、W2=103、W3=107，参数设置参考文献[12]。

图2 展示了对于四种不同数据量，即S=1 Mbit、S=5 Mbit、S=10 Mbit 和S=20 Mbit 时，初始轨迹优化得到的直线飞行悬停传输轨迹和二次优化通过逐次凸逼近得到的轨迹对比图。文章设置数据量范围最大为20 Mbit，是因为此范围足够描述规律。通过对比可以发现，在初始轨迹优化的轨迹中，UAV要在节点的投影点、节点的正上方悬停进行通信。二次轨迹优化的轨迹中，UAV不会悬停进行通信，而是在节点投影点附近进行通信。这种现象展示了二次优化对飞行能耗和传输能耗的权衡。具体来说，当UAV 在投影点传输时，UAV 的传输能耗最小，但此刻飞行的路径是最长的。通过优化飞行轨迹可以减少UAV 飞行能耗，提高一定传输能耗，达到能耗之间的平衡。对比不同数据量下的轨迹可知，随着数据量需求的提高，二次优化的轨迹越加接近初始轨迹优化的轨迹且采集的节点数减少。二次优化轨迹趋近于节点是因为随着数据量需求的提高，能耗的权衡更倾向于传输能耗。采集的节点数减少是因为：数据量需求的提高导致采集每个节点消耗的时间增加。且由于时间约束，导致在相同时间约束下，UAV能够采集的节点数减少。

图2 初始轨迹优化与二次轨迹优化对比Fig.2 Comparison of initial trajectory optimization and secondary trajectory optimization

固定每个节点数据量S=10 Mbit。图3 展示了初始轨迹优化和二次轨迹优化UAV飞行速度随时间变化的曲线图。图4 展示了UAV 飞行功率随时间变化曲线。对比图2 轨迹可知：在二次轨迹优化的轨迹中，UAV 不会悬停进行通信，而是在节点投影点附近减速飞行进行通信。初始轨迹优化悬停通信由于UAV与节点更近，需要消耗的数据采集时间更少。在二次轨迹优化中，UAV 不会悬停，不需要飞到节点正上方通信，而倾向于在靠近节点附近时进行通信，因此通信时间更久，但飞行的距离减少，产生的飞行能耗下降。对比图3和图4 可以发现，在初始轨迹优化，UAV 以最大速度进行飞行时要消耗的能量非常大，而在二次轨迹优化中UAV在两节点间飞行时消耗的能量远远小于最大速度飞行时的能耗。即，通过二次轨迹优化可以提高飞行速度的自由度，可以更好地解决直线飞行，悬停传输方案中由高速飞行带来的较大的能量消耗。

图3 UAV飞行速度随时间变化曲线Fig.3 UAV flight speed curve with time

图4 UAV飞行功率随时间变化曲线Fig.4 UAV flight power curve with time

图5展示了UAV在不同数据量下UAV与各节点间传输调度参数α随时间变化的对比图，不同颜色的函数对应不同节点。从图中可以看出随着数据量的提高，UAV 采集一个节点的时间变长，同时UAV 采集的节点数减少。对比图2中不同数据量之间的轨迹可知：在数据量较大时，UAV 与节点之间通信的时间更长，因此，在总时间给定的前提下，UAV 在节点之间飞行的时间更少，能够采集的节点数也更少。

为了对比初始轨迹优化中采用的改进贪心算法的效率，考虑一种较为简单的求解节点数的方法——改进随机算法。具体来说，假设初始轨迹只包含初始点和终点，从服务一个节点开始，在所有节点中随机选择k个节点，然后通过启发式算法计算得到选择这k个节点时，目标函数值最大的情况。将这个步骤重复多次，从中选择服务k个节点时目标函数值最大的情况。为了对比分析，该方案的参数设置和改进贪心算法的方案相同。

固定每个节点数据量S=10 Mbit。如图6所示，对比初始轨迹优化中改进贪心算法对比改进随机算法在不同服务节点数下对应时间范围（时间范围是指UAV采集k个节点时不同算法消耗的最短时间）。图7为在相同时间约束下改进贪心算法与改进随机算法服务总数据量对比。如图2所示，区域内的节点总数为18。观察图6 可知，采集的节点在4 到13 之间时，改进贪心算法消耗的时间更少，即在相同时间下改进贪心算法能够服务的节点数更多，采集的有效数据量更大。这点也可以从图7中得到证明。从排列组合的角度分析，因为选择k个节点时，可能的情况为组合数为当选择节点数k为K的一半时组合数非常大，即改进随机算法选到总消耗时间最小节点组合的可能性更低。而改进贪心算法每次选择的节点都是当前看来最好的情况，即收敛到总消耗时间最小节点组合的可能性更高。

图6 不同算法数据采集消耗时间Fig.6 Time consumption of data collection by different algorithms

图7 不同算法采集数据量Fig.7 Amount of data collected by different algorithms

图8 为初始轨迹优化、二次轨迹优化、直线飞行与悬停通信方案飞行能耗对比。悬停通信方案是指：在初始轨迹优化相同的条件下，UAV 悬停在节点的几何中心进行通信，飞行时间与联合优化方案相同。直线飞行方案是指：在初始轨迹优化相同的条件下，UAV从初始点到终点匀速飞行，飞行时间与联合优化方案相同。从图8中可以观察到，悬停通信与直线飞行的能耗在不同数据量下接近但不完全相同。这种现象是因为，在初始轨迹优化时，由于只给定了时间约束，整个UAV采集的实际时间会略小于约束时间。为了进行对照，图中同一组数据量不同方案时间相同，不同数据量时间可能略有差异。直线飞行能耗最小是因为其飞行速度接近飞行功率最小的速度。初始轨迹优化能耗最大是因为其飞到每个节点上方采集数据，飞行路径非常大，且在飞行过程中飞行速度一直保持最大速度，综合来看飞行能耗非常高。初始轨迹优化与二次轨迹优化飞行能耗随数据量要求提高而减小是因为数据量提高，UAV 能够采集的节点数减少，飞行的路径也在一定程度上减少，因此飞行能耗也会有一定程度的减少。对比初始轨迹优化与二次轨迹优化的结果可知，通过二次轨迹优化，UAV的飞行能耗较明显地降低。

图8 不同方案飞行能耗Fig.8 Flight energy consumption of different schemes

图9 为四种方案传输能耗对比。从图9 中可以看出，初始轨迹优化、二次轨迹优化的结果相比于对比方案能耗小很多，且二次轨迹优化中消耗的传输能耗相较于初始轨迹变化不明显。传输能耗较小是由于上二次轨迹优化轨迹进行通信时都是在节点附近，而对比方案中UAV与节点距离较大。二次轨迹优化相较初始轨迹传输能耗只有小幅度增加是因为UAV是在高度H=100 m飞行，在二次轨迹优化中通信距离的变化相较飞行高度较小。综合来看，（1）悬停通信和直线飞行方案属于极端情况，因此能耗平衡较差；（2）相比于其他方案，二次轨迹优化的能耗平衡最好，即二次轨迹优化算法能够以小幅度增加传输能耗为代价换取较大的飞行能耗的优化。

图9 不同方案传输能耗Fig.9 Transmission energy consumption of different schemes

为了对比下层优化中UAV飞行能耗和传输能耗不同权值下的仿真结果，以上文中的W2、W3为基准，将目标函数权值改为：λW2、(1-λ)W3，设每个节点数据量S=10 Mbit，仿真结果如图10所示。从图10中可以看出当λ=0 时，优化方程只考虑传输能耗，此时，UAV 轨迹倾向于初始轨迹，因为，在初始轨迹下，UAV在节点正上方进行数据采集，传输能耗最小。随着λ的增加，目标函数中飞行能耗的权重增加，那么通过优化，UAV的轨迹会更倾向飞行能耗更少的轨迹，即直线飞行的轨迹。

图10 不同权值比例下传输能耗与飞行能耗对比Fig.10 Comparison of transmission energy consumption and flight energy consumption under different weight ratios

5 结语

针对时间约束下的UAV 数据采集模型，提出系统数据量、节点上行传输总能耗和UAV 飞行能耗的联合优化方案，通过该方案找到了这个多目标优化问题的次优解。由于所求优化问题非凸，该算法考虑将问题分解为两个步骤来优化。第一步为UAV 初始轨迹优化，为了降低问题复杂度，考虑一种飞行悬停方案，并基于贪心算法和禁忌搜索算法，找到一条可行初始轨迹。第二步为二次轨迹优化，目标是进一步对轨迹进行优化，因此先将轨迹离散化，将连续问题转换为离散问题，然后采用逐次凸逼近技术求解非凸问题并得到次优解。数值结果表明，所提出方法能够更好地做到UAV 飞行能耗、节点传输能耗、通信数据量的权衡。后期，将考虑采用多UAV完成数据采集任务。