1 引言
无人机因其成本可控、机动性强、控制灵活、环境适应性好及人员伤亡风险低等优点，在民用和军事领域均得到了广泛的应用，尤其是执行高危环境下的污染监测、紧急搜救、灾后通信恢复及数据采集等任务时，与传统手段相比表现出更显著的优势[1]。
在时延容忍网络(delay tolerant networks,DTN)中，节点之间的数据传递具有一定的时间容忍度，在截止时间内实现数据的最终交付对于用户来说即是可接受的。当电磁环境复杂、基础通信设施受损或通信条件较差时，基于多跳的数据转发会出现高误码率及高丢包率等问题，影响数据转发的可靠性和有效性[2]。此时，采用无人机充当渡轮(ferry)实现节点间的数据摆渡能够确保数据的可靠交付。与传统的数据传输不同，数据摆渡可以采取装载-携带-交付(load-carry-and-deliver,LCAD)的方式[3-4]，即无人机从源地面节点装载数据，在飞向目的地时携带数据，最后将数据交付给目的节点，这一方式在源和目的节点没有直接通信链路的情况下得到了广泛的应用。此外，当多架无人机同时执行多个具有不同截止时间约束(时延容忍区间)的数据摆渡任务时，受限于单无人机自身的任务执行能力，采用“一一对应”的任务分配方式很可能导致部分任务无法得到有效完成，即无法在任务截止时间内将源节点的数据传递至目的节点，从而直接影响任务的完成质量。在这种情况下，采用“交叉执行”的协同任务分配方式通常具有更好地适用性。
目前，已有许多文献围绕多无人机协同任务分配问题展开了研究。文献[5-8]研究了无人机任务分配中的成本最小化问题。文献[9-10]研究了无人机任务分配中的公平性问题。文献[11-13]研究了无人机任务分配中的效用最大化问题。然而，上述研究很少考虑不同任务的差异化时间约束,仅从无人机能耗或系统收益的角度出发对任务进行分配仍可能导致部分任务完成效果不佳。
在考虑时间约束的情况下，可以将多任务分配问题建模为带有时间窗约束的组合优化问题，该问题已被证明是NP-hard问题[14]，通常可以通过状态压缩动态规划(状压DP)、(混合)整数规划[15]、启发式算法[16]、博弈论[17]以及强化学习[18]等方法进行求解。
本文考虑了DTN中基于多无人机摆渡的数据转发场景，研究了差异化时间约束下的多任务分配问题，采用任务拆解与重组的思想，将其建模为具有右时间窗的车辆路径问题，并以无人机总能耗最小化为目标对其进行优化。通过引入大规模邻域搜索(large-scale neighborhood search，LNS)[19]中的“破坏和修复”思想，有效提高了遗传算法的全局寻优能力，能够在满足多任务时间约束的前提下，降低多无人机系统的总能耗。
2 系统模型及问题形式化
2.1 系统模型
如图1所示，本文考虑了DTN中基于多无人机的数据摆渡场景，包括一个信息中心，n个目标点和m架可用摆渡无人机。信息中心接收到多个用户的数据获取需求后，为无人机分配数据摆渡任务；无人机根据分配到的数据摆渡任务，飞往任务目标点处，采用悬停的方式采集任务目标点的信息，而后将其携带回信息中心；信息中心接收到无人机获取的信息后，根据用户的需求向用户分发信息。假设用户与信息中心之间通信条件良好，且不考虑两者之间的通信时延问题，信息中心获取到无人机所采集信息的时间即为用户获取到所需信息的时间。
初始数据摆渡任务是根据用户的不同信息获取需求来区分的，记K={task1,task2,…,taskK}表示K个任务的集合，其中，taskk=<poik, tdk>表示第k个任务，poik是完成任务k需要访问的目标点集合，tdk是任务k的截止时间。
如图1(a)所示，采用“一一对应”的任务分配方式时，由于不同用户的信息获取需求不同，可能导致不同无人机访问目标点的数量存在较大差异(如UAV2和UAV3)，这一方面影响了无人机之间的能耗公平性，另一方面也造成无人机资源的浪费；同时，由于单个无人机飞行能力有限，当其需要访问的目标点数量过多时，任务完成时间通常会比较长，会导致对应的数据摆渡任务无法有效完成。
图1 系统模型示意图
Fig.1 System model
为此，主要考虑如图1(b)所示的“交叉执行”任务分配方式，即一架无人机可以执行多个数据摆渡任务，每个数据摆渡任务可以由多架无人机执行。具体过程如下：首先将初始数据摆渡任务进行分解，把每个目标点看作一个任务碎片，并根据其所属的初始摆渡任务poik，使用tdk作为时间戳对其进行标记；而后对任务碎片进行重组，并将重组后的数据摆渡任务分配给不同的无人机。碎片重组的有效性会直接影响任务的完成质量，为此，需要对碎片重组策略进行优化。这种基于碎片重组的任务分配问题可以归属于组合优化问题，下面对具体的约束和优化目标进行详细描述。
2.2 能耗约束
在考虑能耗约束的情况下，无人机任务分配与路径规划之间具有高度耦合性，因为无人机的能耗很大程度上取决于其在任务执行过程中的飞行路径。为此，通常会将任务分配与路径规划一同进行考虑：在确定了任务分配策略之后，无人机的飞行路径可以建模为完全无向图G(V,D)，其中，V是节点集合，表示无人机需要访问的所有目标点的集合；D是节点之间边的集合，当2个节点之间有边时表示这两个节点由同一架无人机进行访问，即属于同一架无人机的任务目标点集合。此外，无人机在整个数据摆渡任务中的能耗包含采集目标点信息时的悬停能耗和飞行消耗两部分[20-21]，将无人机的悬停能耗和飞行能耗分别表示为节点和边的权重：对于节点vq∈V，点权重记为p(vq)，对于边m(vq,vq+1)∈D，边权重记为w(vq,vq+1)。下面对无人机的飞行能耗和悬停能耗进行详细描述。
2.2.1 飞行能耗
无人机i的飞行能耗Efi主要取决于i的飞行路径长度。本文只考虑二维平面的无人机，记无人机i的飞行速度为γi，则Efi可以表述为
Efi=φ·Si
(1)
其中，φ为单位距离的能量消耗率，li是i飞行路径，由其执行任务过程中所访问的目标点进行表示，记为
是路径li的长度，表示为
(2)
2.2.2 悬停能耗
无人机i在目标点j的悬停能耗
主要与其在目标点的悬停时间
有关。假设每个目标点的数据量Dtj恒定，i收集数据时的信息传输速率为Bi，则i在j的悬停能耗可以表示为
(3)
其中， β表示单位时间内的悬停能耗。
基于上述分析，如式(4)所示，i的总能耗Eui可以表示为
(4)
记i的最大可用能量为
则能耗约束可以表示为
(5)
2.3 时间约束
时间约束满足与否主要通过任务碎片的时间戳来检验，即无人机将信息摆渡至信息中心的时间Tui应小于各任务碎片的时间戳，该条件等价于Tui小于i所访问的目标点的最小时间戳
记目标点vn的时间戳为tdk(vn)，则
Tui主要与i的飞行时间Tfi和悬停时间Thi有关，可表示为
(6)
其中，
综上所述，时间约束可以表示为
(7)
2.4 目标函数
以无人机总能耗最小化为目标对多无人机协同任务分配问题进行优化，优化目标表示为
(8)
其中: R表示任务分配策略集，ai表示策略集R中的一个可行解。由于目标函数的非凸性，问题P是一个非凸优化问题，很难通过直接求解得到问题的最优解。为此，我们提出了一种基于大规模邻域搜索算法改进的遗传算法对该问题进行求解。
3 算法描述
3.1 遗传算法概述
遗传算法是借鉴生物进化过程而提出的一种启发式搜索算法，通过选择、交叉和变异等操作产生下一代的解，并逐步淘汰掉适应度函数值低的解，增加适应度函数值高的解，从而通过进化演变，逐步逼近问题的最优解。该算法具有简单通用，鲁棒性强，适于并行处理等优势。但是，遗传算法的局部搜索能力较差，且对初始种群的选择具有一定依赖性。
3.2 基于改进遗传算法的协同任务分配算法
本算法以遗传算法为基础，在进化算子中引入了大规模邻域搜索中的“破坏和修复”思想，有效弥补了遗传算法容易陷入局部最优解的缺陷，提高了解的质量，算法的具体描述如下。
3.2.1 染色体结构
如图2所示，采用整数编码的形式将一个染色体描述为(1,2,3,…,n,n+1,n+2,…,n+m-1)，其中，数字1～n表示对应序号的目标点，数字(n+1)～(n+m-1)表示1～m号无人机。如果无人机序号第一次出现在数字1-n之间时，则表明第一条路径生成，以此类推。
图2 染色体结构示意图
Fig.2 Chromosome structure
3.2.2 适应度函数
考虑可能出现违反任务时间窗约束的情况，设计了如式(9)所示的惩罚函数P(ai)，表示为
P(ai)=δ·w(ai)
(9)
其中， δ表示单位惩罚成本，本实验中δ设置为10；w(ai)表示在采用任务分配策略ai时，违反任务时间窗约束的目标点信息的累积超时时间，表示为
(10)
其中，tdk(vj)表示目标点vj的时间戳，若标点vj的信息到达信息中心的时间尚未超过其时间戳，则wj(ai)为0；否则，将wj(ai)记为该信息的超时时间。
记c(ai)为所有无人机的总能耗，则适应度函数表示为
f(s)=1/(c(s)+P(s))
(11)
3.2.3 种群初始化
采用启发式方法构造初始种群，其中，单个初始解的构造方法如算法1所示。
算法1：基于贪婪思想的初始解生成算法
输入:无人机数目m，n个目标点的坐标，截止时间集合{tdk}
输出:初始可行解
1.路径序号：path_num←1；
2.从n个目标点中随机选择一个点j；
3.以j为初始点，生成一个目标点遍历序列：seq←[j, j+1,…,n,1,…, j-1]；
4.按seq依次遍历目标点，如果将vj添加到当前路径中，不会导致路径中的节点(含vj)出现违背能耗约束的情况，则vj添加到路径中，并将vj从seq剔除；否则更新路path_num=path_num+1；
5.重复步骤4，直至seq为空，根据生成路径的数量path_num。
6.如果path_num小于m，则选择1～path_num号无人机作为任务无人机，将n+1,n+2,…,n+path_num依次插入到各个路径的起始点，并将各路径合并得到初始解；否则，当前解为不可行解，从步骤1开始重新构造初始解。
3.2.4 进化算子
选择算子：采用轮盘赌算法作为选择算子，基于个体的适应度选择若干个个体参与后续的交叉、变异以及局部搜索操作。
交叉算子：采用顺序交叉的方式实现，如图3所示，系统随机生成2个交叉位置，用以选择父代交叉的片段，如图3中标黄部分为例。随后将父代2的交叉片段移动到父代1的前面，将父代1的交叉片段移动到父代2的前面。接着从前到后把第2个重复的基因位删除，形成2个子代个体。
变异算子：采用了2种变异算子，一是基于two-element swap[22]算子实现染色体变异，即随机生成2个位置，将父代染色体相应位置上的基因进行交换，形成子代染色体。二是引入LNS中的局部搜索算法，通过破坏算子和修复算子实现染色体变异，具体步骤如算法2所示。
图3 交叉算子示意图
Fig.3 Instance of crossover operator
算法2：LNS算法
输入:当前的解solution
输出:进化后的解solution*
1.初始化需要移出的目标点数量为num=N/5；
2.从原有目标点集合中随机选出一个目标点z；
3.根据相关性计算公式R(i, j)=1/(Cij+Vij)，由高到低依次移出solution中的num个目标点，放入集合S；
4.分别找出S中的目标点c在solution中的可行插入点集合，并记录此时的最小的能耗增量Δ；
5.按照Δ从大到小的顺序，将S中的目标点在不违反约束的情况下依次插入当前解solution中，并计算此时的最小能耗；
6.重复该操作直至S中的num个目标点都被重新插回解集合solution*。
基于上述分析，得到基于改进遗传算法的协同任务分配算法，具体步骤入算法3所示。
算法3：基于改进遗传算法的协同任务分配算法
输入:无人机数目m，n个目标点的坐标，截止时间集合{tdk}
输出:最优解
1.初始化种群，种群规模popsize=100，最大迭代次数max gen=100；
2.根据算法1构造初始解，输出随机初始解的路线，即产生路径点集合li，并计算初始解中的UAV使用数目，UAV飞行总能耗以及违反约束目标点数目；
3.计算w(vq,vq+1),和p(vq)，和E矩阵；
4.根据路径li和能耗矩阵E，计算出
5.当gen≤max gen时，执行步骤6，否则，执行步骤10；
6.计算适应度函数Fitness=f(s)；
7.进行选择，交叉和变异操作；
8.利用破坏和修复算子，根据算法2对染色体进行局部搜索操作；
9.gen=gen+1；
10.输出当前最优解。
4 仿真结果及分析
为了评价算法的性能，除了本文提出的协同任务分配算法(cooperation task redistribution algorithm,CTRA)之外，同时对“一一对应”任务分配方式下的性能和传统的遗传算法性能进行了仿真。仿真结果均为在Matlab 2019a环境下进行了10次实验后，求取的平均值。
4.1 仿真参数设置
仿真过程中，目标点分布于大小为3 000 m*3 000 m的二维平面，信息中心位置固定，且为(0，0)，可用无人机数量为25，目标点的默认数量为100。图4显示了目标点的分布情况和任务需求。此外，任务截止时间如表4所示，其他主要仿真参数如表5所示。
图4 目标点分布及任务需求示意图
Fig.4 Distribution of targets VS task requirements
表4 任务截止时间
Table 4 Deadline of tasks
序号截止时间/s序号截止时间/s11 10061 26028007500390084004600966051 000
表5 参数设置
Table 5 Parameter setting
描述符号数值无人机速度γi20 m/s飞行能耗参数φ13.19 J/m信息传输速率B2 Mbps悬停能耗参数β237 J/s目标点的数据量Dtj20 Mb无人机可用能量Emaxi5×105 J
4.2 仿真结果
4.2.1 算法收敛性
图5显示了CTRA的收敛性。从仿真结果可以看出，该算法经过约86次迭代后，已经基本收敛。
图5 算法CTRA的收敛性曲线
Fig.5 Convergence of algorithm CTRA
4.2.2 算法性能比较分析
1) 能耗效率。如图6所示，采用“一一对应”的任务分配方式时，由于任务8和任务9的信息需求量差异较大，导致无人机8和无人机9消耗的能量差异也较大。而经过“交叉执行”的任务碎片化重组之后，如图7所示，需要的无人机总数量减少为7架，且无人机的能耗效率和公平性均得到明显改善。
图6 “一一对应”任务分配方式的分能耗直方图
Fig.6 Energy consumption of “one to one” task allocation
图7 “交叉执行”任务分配方式的分能耗直方图
Fig.7 Energy consumption of “ cross execution ” task allocation
2) 任务完成时间。图8显示了“一一对应”任务分配方式下的任务完成时间，对于信息需求较大的任务8而言，任务完成时间超过了其截止时间，导致对应的数据摆渡任务8无法有效完成，任务2，4，7亦是如此。而在“交叉执行”任务分配方式下，如图9所示，所有任务均可在任务截止时间前完成，有效改善了任务完成质量。
图8 “一一对应”任务分配方式的分时间直方图
Fig.8 Time of “one to one” task allocation
图9 “交叉执行”任务分配方式的分时间直方图
Fig.9 Time of “ cross execution ” task allocation
4.2.3 算法适应性
1) 截止时间分布对算法性能的影响。默认的截止时间分布是随机分布，因此图10研究了截止时间服从泊松分布时λ变化对目标函数的影响。当λ值较小时，由于违法约束的目标点数目较多，惩罚函数值较大，因此得到的最优解随之增大。随着λ的不断增大，截止时间均得到满足，最优解趋于稳定。
图10 最优值随截止时间分布变化直方图
Fig.10 The optimal value changes with the deadline distribution
2) 目标区域大小对算法性能的影响。图11和图12的仿真结果比较了目标区域大小对算法性能的影响。仿真中将侦察区域设置为正方形，图中的横坐标代表侦察区域的边长。随着侦察区域的增大，无人机的飞行距离变大，从而增加了无人机的飞行能耗和飞行时间，因此，需要的无人机数量随侦察区域范围的扩大产生了变化。另外，如图12所示，与“一一对应”任务分配方式相比，“交叉执行”任务分配方式在满足所有任务截止时间的情况下，系统总能耗可以降低约17.7%～41.9%。
图11 无人机数量随目标区域大小变化直方图(CTRA)
Fig.11 Variation of UAV number(CTRA)
图12 总能耗随目标区域大小变化曲线
Fig.12 Total energy consumption
3) 目标点数量对算法性能的影响。图13和图14对比了CTRA和遗传算法GA的性能。其中，图13展示了无人机数量随着目标点数量的变化情况，从仿真结果可以看出，随着目标点数量的增加，为满足任务的截止时间，使用的无人机数目均随之增加，但是基于CTRA的任务分配算法能够在一定程度上获得更优的解，即可以采用更少数量的无人机来满足任务需求。此外，如图14所示，和遗传算法GA相比，CTRA平均降低了约12%的系统能耗。
图13 无人机数量随目标点数量变化直方图
Fig.13 Variation of UAV number (CTRA VS GA)
图14 总能耗随目标点数量变化曲线
Fig.14 Total energy consumption (CTRA VS GA)
5 结论
针对多无人机执行数据摆渡任务时的多任务协同分配问题，提出了一种基于任务碎片的“交叉执行”任务分配方法，将其建模为多约束的组合优化问题。通过引入破坏算子和修复算子提出了一种改进遗传算法对该模型进行求解，该方法避免了传统遗传算法易陷入局部最优和过早收敛。
仿真结果证明了提出的算法CTRA能够满足任务截止时间，有效节省无人机使用的数量并降低总能耗。
[1] Zeng Y,Zhang R.Wireless communications with unmanned aerial vehicles:Opportunities and challenges[J].IEEE Communications,2016,54(05):36-42.
[2] Xiong F,Xia L,Xie J,et al.Is Hop-by-Hop Always Better Than Store-Carry-Forward for UAV Network?[J].IEEE Access,2019(07):154209-154223.
[3] Cheng C,Hsiao P,Kung H,et al.Maximizing Throughput of UAV-Relaying Networks with the Load-Carry-and-Deliver Paradigm[C]//IEEE Wireless Communications and Networking Conference,2007.
[4] Taniya Shafifique,Hina Tabassum,and Ekram Hossain.End-to-End Energy-Effificiency and Reliability of UAV-Assisted Wireless Data Ferrying[J].IEEE Transactions on Communications,2019,68(03):1822-1837.
[5] Haitao Zhao,Haijun Wang,Weiyu Wu,et al.Deployment Algorithms for UAV Airborne Networks Toward On-Demand Coverage[J].IEEE Journal on Selected Areas in Communications,2018,36(09):2015-2031.
[6] Haibo Mei,Kezhi Wang,Dongdai Zhou,et al.Joint Trajectory-Task-Cache Optimization in UAV-Enabled Mobile Edge Networks for Cyber-Physical System[J].IEEE access,2019,7:156476-156488.
[7] Jiawen Hu,Miao Jiang,Qi Zhang,et al.Joint Optimization of UAV Position,Time Slot Allocation,and Computation Task Partition in Multiuser Aerial Mobile-Edge Computing Systems[J].IEEE Transactions on Vehicular Technology,2019,68(07):7231-7235.
[8] Zhaohua Lv,Jianjun Hao,and Yijun Guo.Energy Minimization for MEC-enabled Cellular-Connected UAV:Trajectory Optimization and Resource Scheduling[C]//IEEE International Conference on Computer Communications,2020.
[9] Qin Z,Li A,Dong C,et al.Fair-Energy Trajectory Plan for Reconnaissance Mission Based on UAVs Cooperation[C]//International Conference on Wireless Communications and Signal Processing,IEEE,2018.
[10] Diao X,Wang M,Zheng J,et al.Fairness-Aware Offloading and Trajectory Optimization for Multi-UAV Enabled Multi-Access Edge Computing[J].IEEE Access,2020(05):124359-124370.
[11] Sujit P B,Sinha A,Ghose D.Multi-UAV Task Allocation using Team Theory[C]//IEEE Conference on Decision and Control and the European Control Conference,Seville,2005.
[12] Zhuo Sun,Zhiqiang Wei,Nan Yang,et al.Two-Tier Communication for UAV-Enabled Massive IoT Systems:Performance Analysis and Joint Design of Trajectory and Resource Allocation[J].IEEE Journal on Selected Areas in Communications,2020,39(04):1132-1146.
[13] Fen Cheng,Shun Zhang,Zan Li,et al.UAV Trajectory Optimization for Data Offloading at the Edge of Multiple Cells[J].IEEE Transactions on Vehicular Technology,2018,67(07):6732-6736.
[14] Solomon,M.M.Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints[J].Operations Research,1987,35(02):254-265.
[15] Cheng Zhan,Han Hu,Zhi Liu,et al.Multi-UAV-Enabled Mobile Edge Computing for Time-Constrained IoT Applications[J].IEEE Internet of Things Journal (Early Access),2021.
[16] Li X,Tian P,Leung S.Vehicle Routing Problems with Time Windows and Stochastic Travel and Service Times:Models and Algorithm[J].International Journal of Production Economics,2010,125(01):137-145.
[17] Yi C,Cai J,Su Z.A Multi-User Mobile Computation Offloading and Transmission Scheduling Mechanism for Delay-Sensitive Applications[J].IEEE Trans.Mobile Comput.2020,19(01):29-43.
[18] Xiong X,Zheng K,Lei L,et al.Resource Allocation Based on Deep Reinforcement Learning In IoT Edge Computing[J].IEEE Journal on Selected Areas in Communications,2020,38(06):1133-1146.
[19] Shaw P.Using Constraint Programming and Local Search Methods to Solve Vehicle Routing Problems[M].Principles and Practice of Constraint Programming,1998.
[20] Thammawichai M,Baliyarasimhuni S P,Kerrigan E C,et al.Optimizing Communication and Computation for Multi-UAV Information Gathering Applications[J].IEEE Transactions on Aerospace and Electronic Systems,2018,54(02):601-615.
[21] Tang C,Mckinley P K.Energy Optimization Under Informed Mobility[J].IEEE Transactions on Parallel and Distributed Systems,2006,17(09):947-962.
[22] Pavai G,Geetha T V.A Survey on Crossover Operators[J].ACM Computing Surveys,2016,49(04):1-43.