刘泽原，赵文栋，李艾静，刘存涛

(陆军工程大学通信工程学院，江苏南京210000)

1 引言

当前，由于无人机的高机动性、灵活控制性和经济性等优势，无人机侦察在抢险救灾、边境巡查敌情获取、战场态势感知等民用和军用领域均得到了广泛应用。其一般过程如下：用户基于自身对侦察目标的信息需求，向无人机基地发送侦察服务请求；基地响应用户的请求并派遣无人机前往侦察区域对相应目标实施侦察；无人机获取侦察信息后，将其直接或间接地回传至无人机基地；而后由无人机基地将获取的侦察信息分发给对应的用户[1，2]。目前，针对无人机侦察的研究大多数集中在多无人机服务于单用户的情况[3-7]，且无人机不直接参与侦察信息的分发任务。

在实际应用过程中，当无人机基地与用户之间的信道条件较差而无法实现高速数据传输时，采用DF(Data ferry)机制让无人机直接参与到信息分发任务中不失为一个好的选择。此时，如果无人机基地同时处理多个用户的侦察服务请求，且不同用户的信息需求存在重叠时，基于各用户请求单独进行任务分配必然存在服务于不同用户的无人机重复访问同一侦察点的情况。基于多用户的需求合集进行统一的任务分配，则会存在一架无人机获取到多个用户的需求信息的情况，从而在信息分发时造成多无人机对同一用户的重复访问。

本文提出了一种基于信息共享的多无人机协同侦察方法(Information Sharing based Cooperative Reconnaissance，ISCR)，采用集中式信息共享机制实现无人机信息获取和信息交付的有机衔接：在信息获取阶段，采用基于多用户需求聚合的任务分配策略实现对多个侦察任务的统一分配，避免多无人机对同一目标的重复侦察；在信息共享阶段，采用单用户需求驱动的信息共享策略实现各个无人机侦察信息的补全，以使得各个无人机获取其服务用户所需的完整的侦察信息；在信息交付阶段，实现无人机与用户之间一对一的信息分发，避免多无人机对同一用户的重复访问。将上述问题建模为带约束的无人机路径规划问题，并基于改进的遗传算法提出了一种低能耗的IETP(Information Exchange based Trajectory Planning)算法，对服务不同用户的无人机进行协同路径规划。

2 相关工作

通过任务规划节省无人机能耗方面，当前工作主要集中在单用户下的任务规划[3-7]，缺少对多用户任务规划的研究。文献[3]构建了一个多无人机协同侦察的场景，在同时考虑飞行能耗和悬停能耗的情况下对各无人机进行了任务分配和路径规划，但其只把基地当作唯一用户，而没有考虑基地为多个用户服务的情况。文献[4]考虑了无人机在目标区域内的停留时间对获取的侦察信息大小的影响，研究了无人机能耗与收益平衡的问题。文献[5]中利用地面传感器提前收集侦察信息，无人机则通过传感器获取相应信息，降低了其在目标区域获取信息的时间及对应的悬停能耗。同时学者还对无人机具有一定侦察范围[6]以及各无人机飞行速度和起飞时间不同[7]等情况下的任务规划问题进行了研究，但这些研究同样都只局限在满足单一用户的需求，多用户下的无人机任务规划仍有待研究。

在多目标任务规划方面，文献[8]研究了无人机的协同合作问题，综合考虑无人机任务类型的重叠互补关系，使无人机根据任务属性形成相应的群组执行任务。文献[9]在无人机提供信息传递的场景中考虑了不同用户的服务质量需求并对无人机进行任务分配。文献[10]考虑了多无人机协同侦察决策问题，在多目标约束下平衡多任务区间的侦察收益。文献[11]提出了一种事件驱动的无人机数据采集方法，使无人机能够处理多目标任务，最大化收集的总信息价值。然而在多用户信息侦察的场景中，都没有综合考虑信息获取和分发多用户信息的过程。

3 系统模型与问题建模

3.1 系统模型

如图1所示，假设基地附近存在多个用户，基地中停靠多架无人机为用户提供服务，同时在目标区域中的每个侦察点放置一个传感器为无人机提供侦察信息。无人机、传感器和用户分别表示为：U={u1，ui，…，um}，S={s1，sk，…，sr}和B={b1，bj，…，bn}。当前考虑无人机数量较少的情况，假设无人机数量小于用户数量。用Cj={sj(1)，sj(2)，…，sj(k)}表示当前联合规划中的用户bj需要集合内传感器的所有信息。首先，无人机从基地出发对被分配的目标进行侦察，随后前往信息共享位置共享信息。进行信息共享的无人机得到其服务用户需要的完整信息，最后各无人机前往所服务的用户附近分发信息。

图1 ISCR侦察过程示意图

3.2 ISCR过程

(1)

(2)

同时，当无人机共享信息时，只能向其它无人机传输其已经采集的信息，其约束条件表示为

(3)

(4)

(5)

3.3 问题建模

无人机路径规划的优化目标是在用户能够获得需求信息集合内的所有信息前提下，使无人机系统总能耗最小。无人机系统能耗主要由飞行能耗和悬停能耗组成，通信能耗相较飞行和悬停能耗过小，因而忽略。假设无人机以恒定速度v飞行，约束如式(6)所示

(6)

(7)

Li为ui的最终飞行长度，Pf(v)表示旋翼无人机推进功率，可以表示为[12]

(8)

其中P0和Pi分别表示悬停状态下的叶型功率和诱导功率，Utip为旋翼的叶边速度，v0为悬停状态下旋翼的诱导速度。d0为机身阻力比，s为转子稳定性。ρ和A分别表示空气密度和旋翼旋转的面积。同时，悬停功率表示为：

Ph=P0+Pi

(9)

无人机悬停能耗取决于无人机的悬停时间和悬停功率。在信息获取阶段，无人机悬停能耗来自于采集传感器信息的过程，假设传感器以恒定速率R传输信息，传感器sk的信息量大小为Nk，则无人机在传感器sk处的悬停能耗表示

(10)

无人机在信息共享阶段，无人机悬停能耗来自于信息共享过程，假设调整各无人机出发时间，以保证其在同一时间到达信息共享区域，则无人机在信息共享点的悬停时间由接收信息大小和发送信息大小决定，则其在信息共享点的悬停能耗表示为

(11)

(12)

无人机i的总能耗为

(13)

综上，本问题为采集信息共享机制情况下对多无人机进行路径规划，使得无人机系统总能耗最小，形式化描述为式(14)

(14)

4 IETP算法描述

多无人机的路径规划可以转化为每个无人机分配需要访问的侦察目标和所服务的用户，即规划函数f，χ和g，随后根据每架无人机需要访问的目标点并确定组合顺序。在该路径规划问题中，目标分配问题和组合顺序优化问题两者相互耦合，极大增加了求解的复杂度，其类似于同样作为NP-hard问题的旅行商问题[13]或车辆路由问题[14]，难以求出最优解或需要耗费大量时间进行求解。对于已确定所分配的目标点的情况下的组合优化问题，通常运用遗传算法[15]等启发式算法进行求解，其能够在规定的迭代次数内得出次优解。而整数拆分方法则是一种可以遍历对各无人机可能的目标分配方案的数学方法。本文提出启发式算法IETP，将遗传算法与整数拆分相结合，并更改遗传算法中适应度函数值的计算方式，在多次迭代后寻找最佳路径。下面简单介绍遗传算法和整数拆分，并对IETP算法细节进行详细介绍。

4.1 整数拆分

整数拆分方法将一个正整数用多个整数之和表示，IETP算法中，采集树的形式表示整数拆分结果。在拆分树中，层级0为虚拟层，仅代表根节点，且对于i，j(i>j)，层级i的值不小于层级j的值，层级中的一个整数值表示一架无人访问侦察点的数量，同时拆分过程不考虑拆分顺序以避免出现重复结果。假设3架无人机总共需要访问5个目标，则如图4所示，其共有5种拆分方案。根据整数拆分方案，按顺序将一条个体拆分为各无人机的子路径。例如，根据第4种拆分方案M4={1，1，3}，则无人机1需要访问一个目标点，无人机2访问一个目标点，无人机3访问三个目标点。

图2 整数拆分示意图

4.2 改进遗传算法

遗传算法是依靠染色体编码和变异原理衍生出的进化算法，得出其具体操作包括染色体编码、种群初始化、染色体选择、并使用遗传算子产生新的个体。多个遗传个体构成一个遗传种群，其中个体表示一条遍历所有侦察目标和用户的完整组合顺序，个体中的一个染色体代表一个侦察点或用户。利用整数拆分方法拆分遗传个体，每个拆分方案可以将遗传个体拆分为多个染色体片段，每个片段表示一架无人机被分配的访问点及对应的访问顺序。能够满足第3节中无人机侦察服务约束的拆分方案为正确的拆分方案，不能够满足侦察约束的拆分方案为错误的拆分方案。

图3 遗传个体拆分示意图

如图3所示，1-5号染色体为侦察目标，6-7号染色体为用户，按照拆分方案(1)对遗传个体(2，4，6，3，8，1，5，7)进行拆分并获得三个染色体片段，片段1代表无人机1依次访问染色体2，4，6代表的访问点，表示无人机侦察目标点2，4并为用户6传递信息。无人机2侦察目标3并为用户8提供信息，无人机3侦察1，5并为用户7提供信息。无人机根据访问侦察目标情况及其所服务用户需求情况确定无人机之间的信息共享关系，以补足所服务用户需求的所有信息。按照拆分方案(2)对遗传个体拆分获得染色体片段(2，4)，(6，4，8，1)以及(5，7)，按照此访问顺序无人机在访问用户6和8时无法为其提供需要的所有信息，则该拆分方案为错误拆分方案。

遗传算法通过遗传算子对种群中的遗传个体进行遗传操作，遗传个体完整保留的概率取决于该个体的适应度函数值。在IETP算法中遗传个体中使无人机系统总能耗最小的正确拆分方案作为该个体的最优拆分方案，最小能耗值为该遗传个体的适应度函数值。遗传算法是一个非常成熟的技术，这里不再对如何进行遗传操作详细介绍。

4.3 IETP算法步骤

IETP算法将整数拆分和遗传算法相结合，首先根据任务池内所有用户信息需求的并集得出需要访问的侦察点集合S，根据集合S随机生成多个初始遗传个体组成初始遗传种群，确定每个个体的适应度函数值，并通过不断进行遗传迭代，达到最大迭代次数后，跟遗传种群中的适应度函数值最小的遗传个体及其最优拆分方案确定各无人机被分配的侦察目标及访问顺序，联合其对应的信息共享点和服务用户确定无人机飞行路径。IETP算法具体步骤总结如下：

1)确定侦察点集合S，并根据集合中的侦察点中生成包含N个遗传个体的遗传种群，确定最大迭代次数iter。

2)对每个遗传个体进行整数拆分，根据每个拆分方案为各无人机分配侦察目标和用户以及相应的访问顺序，同时确定无人机之间的信息共享关系。

3)根据式(13)计算每个遗传个体的每个成功拆分方案所产生的无人机系统总能耗，并判断出各遗传个体的适应度函数值。

4)判断是否达到最大迭代次数，达到最大迭代次数进入步骤5)，否则对种群中的遗传个体进行遗传操作，生成新的种群，重复步骤2)。

5)选出该种群中的适应度函数值最小的个体，并将其最优拆分方案结果作为无人机路径规划结果。

5 仿真结果及分析

5.1 仿真设置

为验证ISCR方法及对应的IETP算法的有效性，采用MATLAB软件进行仿真，假设传感器随机分布在5km x 5km侦察区域内，默认传感器数量为25。默认基地需要同时处理3个用户的侦察请求，每个用户的需求信息集随机生成。由于用户之间可能存在相同的信息需求，用Ior表示用户信息重合率，代表重合的信息需求占用户总信息需求的比例，默认值为30%。无人机基地的坐标为(0，0，0)，能耗模型参数参考引用文献[3][12]进行设置，具体参数如表1所示。将针对用户请求单独进行任务规划的方法统一称为PSTP(Plan Separate Trajectory Plan)，将其作为ISCR的对比方法，并利用遗传算求解PSTP方法中的无人机路径。图4-图7为路径规划结果的能耗对比图。

表1 仿真参数

5.2 仿真分析

5.2.1 单架无人机能耗对比

图4表示了在默认参数设置下，PSTP方法和ISCR方法中的每架无人机能耗对比。可以看出，与PSTP相比，ISCR中每架无人机能耗更低，但是其较大的无人机在满足用户时效需求方面表现较差，因为其在承担自己用户侦察任务的同时，又过多的承担了其他用户的侦察任务，因而IETP算法不适用于对信息时效性要求较高的场景。

图4 无人机单独能耗对比

另一方面，在PSTP中，每架无人机访问的侦察点由所服务用户的信息需求决定，存在侦察点被重复侦察的问题，而在ISCR模型中，各用户的信息需求被合并成一个总的信息需求，并采集系统总能耗最小的方案将侦察点分配给各无人机，因而与PSTP相比，ISCR中每架无人机的能耗更小。

5.2.2 传感器数目的影响

在默认参数下，用户信息集内传感器数量以固定比例随侦察区域内传感器数量变化，则无人机系统能耗随侦察区域内传感器数量变化的趋势如图5所示，与PSTP相比，ISCR中的系统总能耗降低了24%-28%。

图5 无人机系统总能耗与传感器数量关系

这是由于无人机之间通过信息共享的方式建立了一种协作能力，将距离其大部分侦察点远的传感器交由其它无人机访问，进而减少无人机总的飞行路径。特别的，当用户信息集相交时，通过信息共享方式可以使被重复需要的侦察信息仅被采集。

5.2.3 用户数量的影响

无人机系统能耗随用户数量变化的趋势如图6所示。在给定用户数量变化的范围内，与PSTP相比，ISCR中系统总能耗降低了7%-36%，且随着用户数量增加，ISCR的优势更加明显。这是由于随着用户数量增加，PSTP中无人机系统需要访问的传感器总数增加，同时无人机往返于目标区域和用户之间的总距离增加，因而无人机系统总能耗增加。而ISCR中，由于信息共享方式存在，无人机系统需要访问的传感器总数不变，仅无人机往返于目标区域于用户之间总距离增加，因而总能耗增加缓慢。

图6 无人机系统总能耗与用户数量关系

5.2.5 信息需求重合率影响

无人机系统总能耗随Ior变化如图7所示，相比ISCR方法，PSTP中系统总能耗随着Ior增大而更快的增长。这是由于当Ior增大时，PSTP中无人机系统冗余访问的侦察点增多，系统的运动和悬停能耗增大，而在ISCR模型中，无人机系统避免了对侦察点的冗余访问，随着Ior增大，仅无人机在信息交付阶段的悬停和通信能耗增加，增加的能耗远小于PSTP中增加的运动和悬停能耗，因而 ISCR中系统总能耗增长较缓慢。

图7 无人机系统总能耗与关系

6 结束语

为了解决多用户无人机协同侦察中的多目标点重复侦察问题以及多用户重复访问问题，提出一种基于信息共享机制的协同侦察方法ISCR，随后以无人机系统总能耗最小为优化目标，提出一种启发式算法IETP对服务不同用户的无人机进行路径规划。相比于针对单用户需求驱动侦察方法，ISCR侦察方法能够有效减少无人机系统能耗，且随着用户数量和信息重合率增加，其能耗节省优势更加明显，但是不能采集ISCR为用户获取具有时间紧迫性的信息，同时该方法可能会使部分无人机承担较多任务，产生各无人机能耗分布不均匀的情况。下一步工作将寻找无人机存在多个信息共享点并进行多阶段信息共享的情况，同时对此方法进行改进，使其能够为用户侦察具有时间敏感性的信息。