无线网络中具有MEC的多UAV飞行轨迹优化

2023-11-03贾哲松王高才

计算机工程与设计 2023年10期

贾哲松，王高才

(广西大学计算机与电子信息学院，广西南宁 530004)

0 引言

移动边缘计算(MEC)将具有计算能力的服务器下沉到距离终端设备较近的网络边缘，以达到降低时延、提升效率、节省功耗等目标，从而改善用户的服务体验，但同时也带来了新的挑战，那就是MEC设备的部署问题。作为对于地面移动边缘计算的一种补充，由搭载MEC服务器的无人机集群提供的无人机边缘计算网络[1]能够很好解决MEC设备的部署问题。它具有灵活性、智能性和多样性的优势，通过对资源的合理分配和UAV轨迹优化，还将有望进一步提高无人机边缘计算网络的计算性能[2]。

本文研究了一个以具有MEC功能的UAV为核心的无人机集群，其主要功能是调度多个UAVs前往指定地点收集数据，因此考虑了数据量约束条件下的多UAVs通信延迟问题。其中对飞行轨迹的优化和任务节点的分组排序是改善通信延迟的关键因素。为了能够最大限度地利用UAV资源，还探讨了UAV的最佳巡航速度，并验证了其存在的可能性。

本文主要贡献总结如下：

(1)研究了UAV的有效巡航轨迹，以确保UAV能够在规定的服务时间内完成每一个用户的通信任务。还探讨了在UAV巡航速度固定的前提下，通信延迟与多UAV巡航轨迹之间的关系，最终将通信延迟的优化问题简化为MTSP。

(2)提出一种元启发式算法K-WAOA，它通过聚类算法K-means来提供初始解集，并使用模因算法来探寻更加优秀的解决方案，其中鲸鱼优化算法(WOA)与模拟退火算法(SA)分别作为模因算法框架下的全局搜索策略和局部搜索策略被运用。数值结果表明，所提优化方法具有很好的收敛速度，且在飞行速度受限以及任务密集的工作环境中更能发挥价值，同时还为当UAV数量增加时UAV集群的通信延迟的性能分析提供了实验分析。

1 相关研究

作为一项很有前景的技术，UAV可以很好地配备MEC设备，以便在地面部署策略受限的场景中提供空中移动边缘服务，以提高用户的服务质量(QoS)。MEC服务器则为UAV群带来了强大的计算能力，成员们可以将复杂的计算任务传递给搭载MEC设备的UAV[3-8]，有效地降低整个无人机网络的延迟，也可以使用更加灵活的部署策略来提高UAV的长期工作效率[9，10]。特别的，文献[4]将UAV集群联合调整卸载比和传输信道的优化问题表述为卸载博弈，并设计了一种基于并发最佳响应的分布式卸载算法从而有效地减少任务延迟。为了优化UAV网络的相对延迟，文献[8]提出了一种基于最短有效作业优先的调度方法。基于调度和资源分配之间的耦合关系，然后联合优化计算卸载和信道接入问题。考虑到多UAVs需要依靠复杂的充电和重新配置方案才能来实现无缝的长期网络覆盖[10]。首先介绍了一种新的UAV能耗模型，其次提出了一种在无缝覆盖约束下优化的节能可充电无人机部署策略。最后采用一种两阶段联合优化算法实现了UAV的循环部署策略。

为了提高UAVs信息收集的效率，对其轨迹优化也成为设计的关键[11-15]。通过考虑无人机在固定高度飞行，文献[11]的研究中优化了一维(1D)无人机轨迹，以最大限度地提高无人机支持的WPT网络的能量传输性能。文献[12]引入了一种高效的聚类算法，以负载平衡的方式将区域划分为子区域，以最小化无人机的移动次数。对于单无人机和一维无线传感器网络的情况，文献[14]优化了随时间变化的无人机速度和传输间隔，以最小化无人机的飞行时间。在文献[15]中研究了最大化服务SN数量的时间敏感数据收集任务，其中通过逐次凸近似算法联合优化无人机的轨迹和无线电资源分配。

2 系统模型

图1为一个无人机联盟数据收集系统，该系统包括负责数据收集的N架无人机UAVs，索引由={1，2，…，N} 表示，M个传感器用户以及一天搭载有MEC服务器的领导型无人机。在t=0时刻起UAVs被调度从起始点O=(x0，y0) 出发，在航行过程中以及给定区域内的共计M个任务节点上方悬停时收集信息，并最终返回起始点，回收UAVs。为提高任务的成功率，UAVs以某种相对经济的巡航速度Vf行驶，飞行高度固定为H，然后UAVs的位置由 (xn，yn，H) 表示，任务节点的地理位置已由领导型无人机收集完成，由于UAVs飞行高度固定，所以主要研究对象为UAVs飞行轨迹在平面上的投影，如图2所示。记第m个用户位置为 (xm，ym)，悬停点位于用户节点的正上方，即 (xm，ym，H)，需要收集的数据量为Qm。

图1 多UAV通信系统模型

图2 多UAV通信系统水平投影

2.1 相关数学模型

2.1.1 信息传输模型

用Tn表示索引为n的UAV的工作周期，在某时刻t的位置为 (xn(t)，yn(t))，初始时n访问的任务节点的索引可由n={1，2，…Mn} 表示，因此无人机n的轨迹长度公式

(1)

其中，x′n(t)，y′n(t)，分别表示xn(t)，yn(t) 关于t的一阶导数，tn，m，tn，m-1分别表示n从自身巡航路线第m个以及从第m-1个节点出发的时刻。

在UAV和设备共享同一信道的一对多场景中，干扰模型始终是一个重要问题。在文献[16]中，UAV通过时分多址(TDMA)从其相关节点收集数据，其中每个传感器节点仅在计划进行数据传输时唤醒。在这种情况下，UAV顺序地与通信节点，并且节点之间不存在干扰。此外，文献[17]中研究了支持无人机的正交频分多址(OFDMA)网络，其中无人机作为移动基站(BS)进行调度，为一组地面用户提供服务。除去信号干扰外，一对多和多对多传输模式还会面临信道选择，任务调度等问题[18，19]，这不是讨论的范围。因为研究中采用一对一传输模式，即UAVs在同一时刻仅为一个任务节点提供服务，n对第m个任务节点的传输速率公式为

(2)

其中，B为带宽，σ2为高斯白噪声，β为单位距离下的信道增益，ρ为传输功率。

(3)

其中

(4)

2.1.2 采集数据的延迟模型

在t=0时刻n从起止点出发，按顺序为指定用户提供通信服务，最终在t=Tn时刻返回起止点。结合式(4)可知，n在t=tn，m-1时开始负责收集任务节点m的数据，那么m的数据通信延迟公式为

(5)

2.1.3 速度模型

系统中所用到的UAV类型为旋翼无人机(rotary-wing UAV)，这类UAV的工作状态由推进动力决定，主要为悬停状态和飞行状态，因此首先给出UAV的推进功率模型

(6)

其中，P0和Pi是两个常数，表示悬停状态下的叶片剖面功率和感应功率；Utip表示转子的尖端速度；v0为悬停状态下的平均旋翼诱导速度，d0和s分别为机身阻力比和旋翼固体度，p和A表示空气密度和旋翼盘面积[20]。

UAV存在两种基本类型的速度，即最大续航速度VME和最大航程速度VMR。VME确保在移动期间移动功率最小。VMR可以实现UAV的最长行驶距离，两者与UAV的最大速度Vmax的关系为：VME

(7)

(8)

接下来验证VMR可以通过式(8)得出。

Proof：不难看出，当式(8)第二项是凸的便能验证式(8)成立。因此可以对第二项做两次一阶泰勒展开。计算过程如下

(9)

可知展开之后f(V)″≥0，那么式子第二项为凸，且三项的非负、非零加权和也为凸。当V≥0，式(8)为凸，式(7)成立。为了提高UAV的能量利用效率，默认后续的研究内容UAV所使用的移动速度始终保持着Vf=VMR。

2.2 问题分解和重组

2.2.1 UAV巡航轨迹重构

以飞行轨迹Dn.m为例，为了更好量化它，在n的第m个悬停点和第m-1个悬停点之间上引入I个转折点，如图3所示。可知Dn.m被分割为I+1条转折线，且I的值越大量化值就越接近于路径的实际长度。第i个转折点坐标可表示为 (xn，m-1，i，yn，m-1，i)；i=1，2，…，I。

图3 使用转折点优化UAV飞行轨迹示例

这里补充定义n所经历的悬停点的坐标可表示为 (xn，m，yn，m)，在引入转折点之后为了方便归类，将悬停点改写为 (xn，m，0，yn，m，0)，那么n的悬停点集合、转折点集合分别为

Shov={(xn，1，0，yn，1，0)，(xn，2，0，yn，2，0)，…，(xn，Mn，0，yj，Mn，0)}
Stra={(xn，0，1，yn，0，1)，…，(xn，0，I，yn，0，I)，…，(xn，Mn，1，yn，Mn，1)，…，(xn，Mn，I，yn，Mn，I)}

所有UAVs起止点表述为 (xn，0，0，yn，0，0) 和 (xn，Mn+1，0，yn，Mn+1，0)，综上n的路径可表示为集合Φn=(Xn，Yn)，Xn=(xn，0，0，xn，0，1，…，xn，1，I，xn，2，0，…，xn，Mn，0，…，xn，Mn+1，0)T，Yn的定义与之同理。

定义Dn.m第i条转折线的长度公式为

(10)

那么n一个工作周期的计算公式

(11)

(12)

上文已经分析出了n的轨迹Φn，折线段长度Dn.m，i，以及随时间t变化的坐标，那么n自t=0时刻起飞，它的巡航轨迹公式为

(13)

可知n在工作周期对节点m的数据收集量公式可改写为

(14)

其中

2.2.2 通信延迟

最小化所有任务的通信延迟可表述为min{T1，…，TM}，假设它们对应的大小关系为：TM≥，…，≥T1事实上必定存在n′遵从如下的等式关系

(15)

可知在引入转折点来量化UAV的单轨迹之后，通信延迟的优化实际上涉及到了任务节点的分配、排序以及相邻节点之间转折点的求解，共计3个问题，因此接下来可以统一对其进行数学建模。

定义一个三维变量B={βn，b，e|n≤N，b，e≤M，n∈Ν+，b，e∈Ν} 用来区分不同UAV的弧。其中βn，b，e=1，表示悬停点b(或起止点)和悬停点e(或起止点)之间的弧是最优轨迹，否则βn，b，e=0。对于给定的节点分组和UAV数量N，优化问题可建立为

Qn，b，eβn，b，e≥Q′b，eβn，b，e；b=0，…，M；

e=1，…，M；b≠e；n=1，…，N

(16a)

b≠e；n=1，…，N

(16f)

2≤b≠e≤M

(16g)

βn，b，e={0，1}；

n≤N；b，e≤M；n∈Ν+；b，e∈Ν

(16i)

其中，Tmax表示UAVs中最大的工作周期。(16a)中Qn，b，e是前文Qn，m在P1的映射，注意b包含了起止点，而UAVs在返航过程中不再收集数据，所以e不包含起止点。Q′e则表示需要在任务节点e收集到的最小的数据量。(16b)，(16c)表示每个UAV只访问一次起止点，(16d)，(16e)，(16f)表示每个悬停点只允许一台UAV到达和离开一次，(16g)是MTZ(miller-tucker-zemlin)约束，用来消除子路径，(16h)表明优化目标是N个UAVs中用时最长的个体。

这是一个MTSP的变种，具有很强的NP-hard性，它表明系统满足每个任务节点的数据收集需求的同时，还需要最小化UAVs的最大工作周期。

3 基于模因算法框架的鲸鱼退火优化算法

多无人机轨迹规划问题面临着两个难点，一个是任务节点的分组，另一个就是无人机轨迹中的悬停点排序优化，同时还需选择合适的转折点来控制无人机的飞行轨迹，以此满足每一个节点的通信要求，接下来将围绕这些问题来探讨优化方法。

3.1 多无人机的任务分组及通信节点排序

模因算法，又称文化基因算法(memetic algorithm)是Pablo Moscato提出的建立在模拟文化进化基础上的优化算法，它实质上是一种基于种群的全局搜索和基于个体的局部搜索的结合体。模因算法是指全局搜索框架(鲸鱼算法，WOA)和局部搜索框架(模拟退火算法，SA)的组合。WOA充当解决方案生成器，利用算法收敛速度的优势快速得到所有可能的种群，生成有希望的解决方案来扩展搜索空间。而通过SA则可以有效避免陷入局部最优解的情况。综上所述，基于K-means的WOA与SA的混合算法(K-WAOA)将有望成为一种能够高速收敛且全局搜索能力优异的路径规划算法。K-WAOA的伪代码在算法Ⅰ中进行描述。

3.1.1 鲸鱼优化算法

(2)适应度函数step3 and step6：算法利用适应度值来评价种群，以及淘汰没有希望的种群。在这里的优化目标是一个种群中工作周期最长的任务分组，因此利用式(11)构建适应度函数，首先计算出种群内不同分组所需的飞行时间Tn，最后选取其中而最大值作为该种群的适应度值，则种群的适应度公式为

(17)

(3)包围猎物step5：该行为模仿的是多个鲸鱼群体在进行捕食时，处于最佳位置的鲸鱼群体会将自身成员的位置信息共享给其它种群，其它种群则根据得到的信息不断改变自身成员的位置，以确保能够达到缩小搜索范围的效果。其数学表达式如下

(18)

其中

(19)

C1=2γ2

(20)

A1=2αγ1-α

(21)

(4)发泡网攻击step5：在该阶段鲸鱼种群会有两种行为模式，一种是以螺旋的方式向当前最佳种群游走，另一种是在游走的过程中继续进行包围猎物阶段的动作。选择两种行为模式的概率各为50%，数学模型如下

(22)

其中，b为对数螺旋形状常数，-1到1之间的随机数。该阶段包含局部和全局两种搜索模式，但由于这两种方式是随机发生的，所以可能出现种群向当前周期最优种群收敛进度过快，从而陷入局部最优的情况，这也是WOA性能上最大的缺陷，对此可以采用SA算法，通过其特有的Metropolis准则来进一步提升WOA算法的全局搜索能力。

(5)搜索捕食step5：搜索捕食的思想是在进行最终的捕食行为之前，当前鲸鱼种群会随机选取一个目标，并向其靠拢。该过程虽然会导致最终结果与真正的最优值有所偏差，但可以有效地提高算法的全局搜索能力。这一阶段的数学模型与包围猎物阶段的数学模型相似，仅将当前最优种群Π*转变为随机种群Πrand，因此不再过多赘述。

3.1.2 SA(simulated annealing algorithm)

SA算法是一种通用的优化算法，其流程分为加温过程、等温过程和冷却过程，其在路径寻优的问题中已被较为成熟的运用。值得一提的是等温过程对应算法的Metro-polis抽样过程能够一定概率接受恶化解，从而可有效避免陷入局部极小，最终趋于全局最优。当然SA算法本身也有较大缺陷，那就是算法收敛的结果常常受迭代次数的影响，迭代数越多结果越优秀，相应的消耗的搜索周期也就越长。

3.2 UAV飞行轨迹优化

经由P1所得结果T′max需满足如下条件

(23)

其中

假设βn′，b′，e′=1根据式(14)和约束式(16a)，可将n′在索引为b′和e′之间的飞行轨迹优化问题可建立为

很明显这是一个非线性优化问题，主要目的为寻找最优的转折点及悬停时间，使得UAV既能满足数据收集的要求，又能使得UAV为目标节点提供服务的耗时最短。P2的求解难度相对简单，接下来利用式(14)来提前研究最优解的可能取值。

负责通信服务的UAV的最优工作方式，是以额定的速度在相邻悬停点之间沿直线行驶，并最终在悬停点上方完成对应任务节点剩余的通信任务。

Algorithm Ⅰ：K-Whale Annealing Optimization Algorithm(K-WAOA)

Input：初始亲代种群数量，S；UAV数量，N；悬停点坐标，(xn，yn)；n=1，2，…，N；最大迭代次数，τmax；

Output：悬停位置的最优分配和排序 {Φ1，…Φn，…ΦN}；

(2)在上述分组的基础上随机打乱组合生成S个初始亲代种群, {Π1,…,ΠS};

(3)结合式(11)和式(17)来评估每一个亲代种群的适应度, 并选择具有最大适应度值的种群作为Π*;

(4)whileτ=1;τ<τmax;do:

(5) 对 {Π1,…,ΠS} 执行包围猎物, 泡沫网攻击和搜索捕食以产生新的种群 {Π1′,…,ΠS′} 并进行优化; 该过程的详细描述在3.1.1节中(3)～(6)

(7)If种群的最大适应度发生改变:

(8) 重新确定Π*;

(9) {Π1′,…,ΠS′} 替代 {Π1,…,ΠS},τ++;

(10)endwhile

4 模拟和实验

4.1 模拟环境设置

在实验部分，考虑了一个5000m×5000m的矩形区域，其中N台UAVs从区域的中心出发，飞行高度分别为400 m，信道带宽B=1 MHz，传输功率ρ=0.5 w，高斯白噪声方差σ2=5×10-15，信道增益β=ηlos(4πf/c)2，ηlos=1，是LOS对应的衰减系数，f=2.4 GHz，c是光速。假设初始时UAV共收到了来自区域内随机的30个任务节点的通信请求，如图4所示，后续的实验中任务节点规模将逐步扩大(30到100，每10个间隔)。悬停位置被视为虚拟救援任务节点，UAV的初始巡航速度Vf=15 m/s。所选的点集经过K-means处理前后如图5所示，其中被调度的UAVs的数量，N=3。其它参数会在后续的模拟实验中给出。实验部分基于Windows10，i7-10875HCPU下的Python3.9实现。

图4 初始通信节点分布情况

图5 通信节点分组展示

4.2 悬停点排序及轨迹优化

图6展示了使用K-WAOA算法对多无人机路径优化的结果，此时使用转折点I=1时来模拟多UAV飞行轨迹。其中转折点是在连接两点直线附近的区域内随机产生，标记为方块的虚线是算法最后一次迭代时的优化目标，它的适应度最大，为786 s，该虚线自身轨迹没有发生重叠或交叉的现象，这符合路径优化的特征，因此验证了K-WAOA的可行性。图7展示了在路径规划的基础上，通过求解P2来进一步优化UAV的飞行轨迹的成果，此时标记为方块的虚线所代表的适应度为778 s。通过观察可知，优化过后的转折点基本上都位于对应悬停点之间的线段上，这也验证了3.2节最后的推断。因此在实际工作中，可以通过增加相邻悬停点之间转折点的数量I来控制UAVs的飞行轨迹，从而获得更好的工作效果。

图6 优化过后的访问通信节点排序

图7 求解P2后对巡航路径的进一步优化结果

4.3 速度和任务节点数量的影响

图8反映了当无人机数量取N=3，巡航速度Vf分别取15，12，9，6，3 (m/s)时，经求解P2优化飞行轨迹后UAVs工作周期的变化情况。其中索引为1，2，3的UAV所访问的任务节点数分别为12，10，8。可以看出随着速度的下降，每一台UAV工作周期的缩短幅度越来越大，由此可以得出结论：将UAVs在相邻两个节点之间的飞行轨迹优化为一条直线的方法能够有效降低其辅助的无线网络的通信延迟，并且在UAVs使用低巡航速度的通信模型中更能发挥效果。

图8 求解P2后所优化的巡航时间

事实上UAVs为保证任务的成功率，在工作周期内并不是一直维持着最大的推进功率，即最大的飞行速度Vmax会逐渐减小。而且上文已经验证了最大航程速度VMR的存在，其数值低于Vmax，所以在将VMR作为UAVs更加经济的巡航速度之后，经求解P2对UAVs飞行轨迹的进一步优化会更加具有现实意义。同时可以看出随着访问节点数的增加，优化过后节省掉的工作周期也更大，这可以理解为UAVs访问更多的任务节点就会产生更多冗余路径，因此优化前后的差距也就更明显。

4.4 多UAV轨迹规划算法性能对比

本节比较了基于K-means的WOA与SA的混合优化算法(K-WAOA)与其它两种元启发式算法，即鲸鱼算法(WOA)方案和模拟退火算法(SA)的性能。图9和10显示，所有UAVs轨迹中最长的飞行时间和运行周期随着网络规模的增加而增加。在3种轨迹优化方法中，由于没有采用有效的方法来对目标轨迹进一步优化，WOA方法中的Tmax增长速度极快。随着任务节点的增长，K-WAOA和SA仍然表现出优异的性能Tmax≤2000 s，但结合两张图片可以看出，SA达到相对最好的计算结果所消耗的运行周期逐渐增长到自身的最大周期数，但计算结果依旧逊色于K-WAOA，SA逐渐成为一个低效率的算法。