地震灾区中继无人机群组角色指派研究

刘冬宁，曾思敏，陈凌丰，吴诗珏

(广东工业大学 计算机学院，广东 广州，510006)

在地震发生后，地面的基础设施被破坏，导致灾区的通信网络瘫痪。救援工作是紧急、突发、具有时效性的，通信中断会极大地影响救援工作，所以构建稳定的通信网络是灾区救援的重要任务。无人机(unmanned aerial vehicle,UAV)可以跨越地理环境障碍，在救援中完成巡逻、搜索、探测等多项任务，还可以搭载相关设备后作为网络中继，为灾区提供稳定的通信服务。因此利用无人机中继建立临时的通信网络的方式应运而生[1-4]。其中，Liu等[3]充分探讨了在发生灾难时，如何部署无人机基站的网络接入和通信资源分配的方案，证明在灾后利用无人机基站恢复通信的可行性。

然而，通信网络需要有多个中继点不规则地散布在灾区的各个角落。利用无人机建立网络时，因无人机在数量有限的情况下还需要完成多项任务，如巡航、侦察遇难者等，所以在保证通信质量的前提下，如何使用有限的无人机完成中继任务，实现任务的最优分配，是灾区重建通信网络面临的重大挑战。

为解决非饱和式救援期间的多无人机协同最优分配这一关键问题，王峰[5]、王巍等[6]研究如何利用启发式算法解决多无人机协同任务分配问题。除此之外，集中式和分布式的新型算法也被广泛应用于无人机指派中，其中Schwarzrock等[7]基于集中式提出3种基于启发式算法的变形，使其互相补充来解决多架无人机执行协同任务的分配问题。Geng等[8]针对搜索和救援应用领域，提出一种基于粒子群优化的改进集中式算法 (modified centralized algorithm based on particle swarm optimization，MCPSO) 来解决搜索和救援领域的任务分配问题。然而不管是启发式算法，还是分布式和集中式算法，都可以应用在任务分配这类研究中。

在任务分配的研究中，Zhu等[9]和Liu等[10]提出集中式建模分布式执行的群组角色指派 (group role assignment，GRA)，它是基于角色的协同 (role-based collaboration，RBC) 方法及其通用模型E-CARGO的子模型。RBC[11-14]、E-CARGO和GRA已经发展成为一种与任务分配相关的有效决策方法，在角色分配问题中有很强的适用性。GRA能根据Agent评价的结果，寻求一个最优的角色分配。学者们研究GRA在各种不同场景中的适用性，如刘冬宁等[15]研究了志愿偏好指派问题。另外，Liu等[14]研究GRA在协同无人机部署通信网络的场景中的应用情况，发现GRA在无人机协同上有很好的效果。

综上，本文使用最小生成树算法生成通信网络，利用群组角色指派进行建模。将中继点作为角色，分布在不同基地的无人机作为Agent。应用GRA模型求解最优分配问题的关键在于将作为Agent的无人机的飞行距离作为救援代价进行评估，建立代价矩阵。但是，受机械特性与电气特性限制，在恶劣复杂环境下，无人机的定位系统无法对自身进行精准定位，且随着飞行距离的增加，无人机定位的垂直与水平误差也会随之增加，导致定位偏离过大，使得规划的通信网络不能联通。因此，在无人机实际飞行中需要通过水平、垂直误差修正点进行精确定位。针对这一问题，本文设计了贪心回溯算法，以尽可能减少误差纠正次数为目标，快速、精确求解无人机飞行轨迹，并依此建立代价矩阵。最终使用GRA模型解决非饱和式救援下的最优分配问题，快速重建网络恢复通信。

1 场景预设

2017年8月8日，九寨沟发生7.0级地震。据中国地震台网中心 (CENC)称，地震发生在20 km深处。超过90辆紧急车辆和1 200名人员被派往灾区参与救援工作。为了快速恢复通信，救援中心决定采用视距通信[6]的方式，使用无人机中继与地面移动终端组建通信网络。为此，在灾区部分地区部署了一些通信车辆作为地面移动终端以及无人机基地。为解决同类问题，科学指导救灾，本文根据九寨沟灾区高程数据，随机仿真20个通信车辆的坐标作为地面移动终端，7个救援中心作为无人机基地。图1是灾区高程图，其中描绘了移动终端的分布情况，图1中的圆点表示地面移动终端，五角星表示无人机基地在灾区的分布情况。

图1 灾区高程线图Figure 1 Elevation line of a disaster area

由于受道路影响，这些车辆在灾区不便通行，移动范围和通信距离有限，无人机与地面移动终端的距离需要在一定范围内，才能保证通信的有效性。本文假设通信车辆与无人机之间的有效通信距离在5 km内。

为尽快恢复灾区的通信，救援队决定部署携带通信设备的太阳能蓄能固定翼无人机作为中继点部署通信网络[16]。这些无人机从多个救援中心出发，无人机与无人机之间组成Ad-Hoc网络[6]。假设每架无人机能在空中稳定盘旋。由于无人机受负载、电力等因素限制，通信覆盖范围有限，本文为便于描述与实验，假设每架无人机的通信覆盖范围在3 km的覆盖半径下能保证稳定的通信，即无人机与无人机之间的最大通信距离为6 km。

为了利用最少无人机建立通信网络，救援队决定使用最小生成树算法来确定中继点数量和位置。此外，由于在非饱和救援下无人机有多项任务需要执行，例如灾区巡逻和遇难者探测等，所以每个基地对指派中继任务的无人机数量都有上限。随机仿真数据如表1所示。

表1 各个基地指派中继任务的无人机数量上限Table 1 Maximum number of UAVs assigned to relay tasks by each base

由于灾区救援工作紧迫，需要尽快将来自不同基地的无人机按最优分配原则分配到各个信号中继点上，为此使用GRA作为任务分配的决策方法。在应用GRA时用于评估的代价矩阵定义为资格矩阵Q，可将无人机飞往中继点的航迹距离作为执行能力的评分，得到Q矩阵。

无人机在飞行过程中会实时定位，由于受机械与电气特性限制，无人机在飞行过程中会产生飞行误差，其中误差分为水平误差和垂直误差。结合实际情况，本文预设无人机每飞行1 m，垂直误差和水平误差各增加1 mm。为保证无人机飞行过程不产生较大的定位误差，偏离指定的任务中继点较远，导致无人机脱离通信范围，设定无人机到达指定位置时垂直误差和水平误差均应小于2 m。可在灾区寻找一些未损毁的标志性建筑或已勘测点等作为垂直和水平校正点，校正点分布如图2所示。在考虑无人机的机械参数、当时环境等因素下，确定当无人机在垂直矫正点时，垂直误差小于2 m，水平误差小于1 m时，可以矫正到垂直误差为0，水平误差保持不变；无人机在水平校正点时，垂直误差小于1.5 m，水平误差小于2 m时，可以矫正到水平误差为0，垂直误差保持不变。

图2 灾区内无人机校正点分布图Figure 2 Distribution of UAV calibration points in a disaster area

当无人机距离目标位置过远时，直线飞往目的点很有可能由于误差过大导致偏离中继点位置。所以在计算资格矩阵Q时需要为无人机规划合理的航迹，确保无人机的误差在允许的范围内。考虑到灾区救援的紧急性，在规划航迹时要尽可能减少校正次数，避免花费不必要的校正时间。航迹的长度尽量接近直线距离，使无人机能飞行更短的距离，更快到达中继点执行中继任务。

2 算法设计

2.1 最小生成树组网算法

在选择中继点之前已知所有地面移动终端的位置，并且无人机的数量足以完全覆盖所有地面移动终端时，最小生成树算法具有全局通信最小成本的特性。因此本文使用Prim算法联通所有的地面移动终端。图3是根据图1生成的最小生成树图。

图3 最小生成树Figure 3 Minimum spanning tree

得到最小生成树后需要确保通信网络能全部覆盖这个树，因此可根据移动终端与无人机的通信距离以及无人机之间的通信覆盖范围，在该树上得到全覆盖通信所需要的最少中继数N。

其中V是所有通信车辆位置的集合；DAB是从A到B的距离；d是通信车辆与无人机的通信距离减去无人机的通信覆盖半径，在此场景中d为2 km；Ddrone是无人机通信的覆盖直径。在最小生成树的枝干位置上根据信号半径确定这些中继点的位置。中继点的具体位置如图4所示。其中黄色五角星为无人机基地；红色圆点为地面移动终端，其外围红色圆为该终端的通信范围；蓝色圆点为中继点，其外围蓝色圆为该中继无人机的通信范围。

图4 中继点分布图Figure 4 Distribution of relay points

2.2 群组角色指派

问题建模采用的是群组角色指派模型 (GRA)，它是RBC及其通用模型E-CARGO的子模型。ECARGO 模型以9元组＜C,O,A,M,R,E,G,s0,H＞抽象描述了协作系统的组成部分。其中，C表示类；O表示对象；A(Agent) 表示协作个体单元集合；M表示消息；R(Role) 表示角色集合 (即任务与需求抽象)；E用于抽象协作环境；G(Group) 表示群组集合；s0是系统的初始状态；H是一组用户。

本文视无人机作为代理，通信网络的各个中继点作为任务角色。因此，在使用GRA之前需要先确定中继点个数和位置。以下根据RBC和E-CARGO对问题进行形式化建模。

定义1角色需求向量为L。

在本文的场景中，每个角色只能分配给一个代理，∀j.L[j]=1(0≤j＜n)，即L=[111···111]。

定义2能力极限向量为La，即每个代理能分配出去的最大资源数。

根据表1各个基地指派中继任务的无人机数量上限表，可得La=[17 19 18 22 15 12 21]。

定义3资格矩阵为Q，是一个m×n的矩阵。其中Q[i,j]∈[0,1]，代表Ai(0≤i＜m)担 当Rj(0≤j＜n)的执行力评分。

在本文的场景中，使用无人机从基站到中继点的航迹长度作为执行能力的评分Qintial如下。

中国高铁要走出国门，合作国目前的政治社会环境也是一个不可忽视的因素，复杂的地域政治因素同样会造成影响。例如我国在2015年印度高铁项目竞标中取得了胜利，然而同一年安倍出访印度，莫迪总统在12月13日选择了让日本修筑印度高铁，虽然日本提出的方案中贷款政策相较我国更加优惠，但其中也掺杂着政治因素。

对其进行[0,1]空间归一化处理。

定义4分配矩阵为T，是一个m×n矩阵。其中T[i,j] ∈{0,1}(0≤i＜m，0≤j＜n)，代表Ai是否被分配执行Rj。T[i,j]=1代表执行；T[i,j]=0代表不执行。

群组执行能力 σ的求解过程是将资格矩阵Q与分配矩阵T进行矩阵点乘。

定义8群组角色指派的线性求解，即寻找可行的分配矩阵T，其中目标函数为

其中条件 (5) 根据本文场景中∀j.L[j]=1(0≤j＜n)的条件，又可以转化成

约束条件 (4) 表示角色分配矩阵T的值只能取0或1；约束条件 (6) 与最初的GRA问题不同，这意味着代理只能分配给有限数量的角色；约束条件(7) 表示角色分配矩阵T每一列的1的个数总和分别等于向量L每个值。

例如，在本文中根据 ∀j.L[j]=1(0≤j＜n)和La=[17 19 18 22 15 12 21]，结合上述约束可以得到分配矩阵T。7个基地的无人机群组执行力 σ为12.09，这是通过GRA得到的最佳结果。分配矩阵T散点图如图5所示。

图5 分配矩阵散点图Figure 5 Scatter diagram of a distribution matrix

2.3 贪心回溯航迹规划算法

为了解决无人机航迹规划的问题，使得无人机在尽可能减少校正次数的情况下，到达中继点时误差在允许范围内，并且使得航迹距离尽量接近直线距离。本文设计贪心回溯算法为无人机进行航迹规划。

虽然贪心算法存在容易陷入局部最优解的问题，但是考虑到灾区救援的背景，首先需要一个能快速为所有无人机规划航迹的算法，在确保高速的前提下才考虑其他的目标。所以在设计算法时需要首先考虑算法的运行时间。

本文使用非负整数p代表校正点集合S的大小，其中 {k0,k1,···,kn}∈S，具体指每一个校正点。非负整数p代表航迹经过的校正点集合P的大小，其中{x0,x1,···,xn}∈P，具体指每一个需要经过的校正点。

当无人机的起点是A，终点是B，所需要经过的校正点x0时，x0与AB的垂线交于。如图6所示。

图6 无人机飞行轨迹示意图Figure 6 Example diagram of UAVs’ flight trajectories

由此可得

根据式(9)可以看出，当Dsum越小，Daverage越大时，经过的校正总数e的值越小。为此航迹中两点之间距离应能在误差允许的范围内尽量大，即图6中的尽量大。其中Daverage代表航迹中两点之间的平均长度。

综上所述，本文为每一个校正点引入一个权值w。

根据权值w将所有校正点进行排序，每次遍历，探索能到达的下一个校正点时，优先选择权值大的校正点。以此快速选出更满足规划目标的路径。该算法的流程图如图7所示。

图7 贪心回溯算法流程图Figure 7 Flow chart of the greedy backtracking algorithm

3 实验及结果分析

论文实验在Windows10 系统下使用Matlab R2016b完成。

为了使算法满足灾区救援的时间窗压力，本文通过实验得到贪心算法的回溯次数对时间和无解情况的影响，以找到一个能平衡时间和求解能力回溯次数限制。本文进行了大规模随机仿真实验，根据起点与终点的距离取值30～ 130 km，以步长10 km作为跳变，随机起点与终点的位置。另外设置连续回溯数取值1～ 10，步长为1。测试回溯次数对实验出现无解的影响。

针对不同步长距离和连续回溯数，随机100个起点与终点位置。总共进行10 000次实验。其中每组不同回溯次数的实验中，回溯限制导致无解的平均耗时，以及无解情况占总无解数的比例情况如表2所示。

表2 回溯限制导致无解的情况表Table 2 Situations of no solution caused by backtracking restrictions

将这些数据根据式 (2) 作归一化处理后得到图8。在图8中可以看到当回溯次数取7时，算法在很好地兼顾求解时间的同时也避免了无解的出现。因此，本文将最长连续回溯次数设置为7。

图8 回溯次数限制导致无解的情况Figure 8 Situations of no solution due to the limitation of backtracking times

在设置连续回溯次数为7之后，再分别对不同步长距离做100次随机实验，共做1 000次实验。进一步论证算法的时效性以及对无人机灾区中继救援的影响。实验结果如图9～ 11所示。

图9 距离与时间的关系Figure 9 Relationship between the distance and the time

图9表示实验距离与求解时间的关系，从中可以看出本文算法能在1 s内求出解，而且平均求解时间稳定在0.1 s内。在救灾工作中能极快地为无人机规划航迹。

图10表示偏离率与实验距离的关系，偏离率为算法求解的实际距离与直线距离的比值。其中显示航迹距离在直线距离的2倍以内，而平均值则稳定在1.3倍以内。这表明无人机航迹在尽可能地接近直线距离，保证算法规划的航迹不偏离直线飞行方向。

图10 距离与偏离率的关系Figure 10 Relationship between the distance and the deviation rate

图11表示实验距离与校正次数的关系。数据显示，实验距离每增加10 km，校正次数约增加2次，表明在本文的算法中飞行距离与校正次数为线性相关。这能保证在长距离飞行中，所需的校正次数不会突然剧增。

图11 距离与校正次数的关系Figure 11 Relationship between the distance and correction times

4 结论

针对灾区部署无人机通信网络问题，设计了统一可行的解决方案。通过群组角色指派 (GRA) 对部署无人机通信网络进行了形式化建模并且给出了有效的解决方案。数千次随机实验表明，本文的解决方案可以在1 s内为无人机规划出航迹，并且保证航迹长度与直线距离的比值稳定在1.3以内，以及每10 km校正2次左右的校正频率。因此解决了通信网络不会因为无人机定位误差而导致整个网络通信存在部分中断的问题，确保了通信网络的稳定性。采用本文的解决方案，可以及时、高效地为灾区部署稳定的通信网络。在下一步工作中，将研究不同性能的无人机在灾区救援中根据不同任务的指派。