考虑韧性的无人机集群自组织区域覆盖方法

刘 涛, 王沙沙, 张 驰, 白光晗, 陶俊勇

(国防科技大学智能科学学院, 湖南 长沙 410073)

0 引 言

无人机具有体积小、重量轻、隐蔽性强、造价低廉、起降条件简单等特点,其环境适应性强、生存能力较强,更适合较危险或重复性的工作。而随着无人机自主化和网络化通信技术的发展,无人机的运用模式也在不断发展,单架无人机由于受到探测能力、武器载荷等因素限制,难以完成复杂的任务。无人机集群,类似于蜂群和蚁群,由具备一定自主能力的无人机组成,集群通过无人机之间的实时数据共享、多机组网、协同配合,从而实现整体任务的达成。其中,通信网络覆盖是无人机集群的一个典型应用场景,例如灾后利用无人机集群建立应急通信网络[1],战场提供区域战地通信[2]等。因此,在任务过程中能否保证良好的通信覆盖率,对任务的成败起关键作用,无人机集群的通信覆盖问题也成为一个研究热点[3-5]。

针对固定翼无人机,其覆盖主要是指规划无人机的飞行路径,实现扫描式覆盖[6]。而旋翼式无人机能够保持位置不变进行持续覆盖,因此本文关注旋翼无人机集群的覆盖问题,该问题也被称为无人机编队的部署问题[7]。文献[1]针对灾后通信基站失去功能的情况,利用遗传算法对无人机集群进行部署设计,利用无人机充当临时通信基站,以满足灾区的通信覆盖要求。该算法属于集中控制,即在获取全局信息后集中计算所有无人机的位置。随着集群规模的增加,集中控制面临着全局信息获取难、计算复杂等问题。分布式解决方案成为一个研究热点,其中基于虚拟力的节点分布式覆盖算法吸引了诸多研究者。文献[8]提出了一种虚拟力算法来提高传感器初始随机放置后的覆盖率。但该文章在力的权重系数上没有给出明确设计,仅假设排斥力权重系数应远远大于吸引力权重系数,这使得在不同实验条件下需多次尝试以找到合适的权重系数。文献[9]引入了Sink与Target之间的“引力线”概念,提出了一种基于虚拟力的移动节点精确部署算法,更加关注目标与目标直接的通信中继,而非区域覆盖,并且没有给出虚拟力增益系数的确定方法。文献[10]在文献[8]的基础上假设边界排斥力和传感器间的排斥力的权重系数相同,对虚拟力权重系数进行了具体设计,该算法虽然没有考虑传感器之间的通信范围,但仍然可看作是各节点的分布式计算。文献[11]在半聚集算法[12]的基础上,提出了一种基于虚拟力场,并且按需部署的无人机自组网算法,该算法同样未明确给出各虚拟力权重系数的确定方法。除了基于虚拟力的分布式算法,文献[13]考虑了无人机的感知范围,提出一种基于相对距离的无人机集群部署算法,但在该研究中,无人机个体除了需要感知范围内其他无人机的位置信息,还需要实时获取未被覆盖区域的位置信息。针对目标区域内有重点关注目标的情况,文献[14]对布谷鸟算法进行了改进,提出了一种在节点数量较少情况下对监测价值较高区域的重点覆盖优化的无人机网络覆盖优化算法,该算法本身虽然借鉴了分布式理念,但其计算仍需要掌握全局信息。

无人机集群在执行覆盖任务时,部分无人机可能会出现自身故障、环境扰动、蓄意毁伤等失效情况,导致覆盖范围下降,影响任务完成。文献[10]针对无线传感器节点故障情况提出了自组织补位算法,该算法要在毁伤故障点附近寻找合适节点集进行“补位”,但该选择过程被证明是非确定性多项式(non-deterministic polynomial, NP)难问题,且需要集中决策。此外,文献[10]未考虑恢复过程对覆盖任务的影响。韧性(也译为弹性)最早在生物学领域提出[15],随后在诸如经济[16-17]、社会[18-19]、工业[20]、军事[21-22]等多个领域应用。韧性是可靠性的拓展和延伸,是衡量系统对抗扰动并从中恢复的能力,能够反映系统毁伤及恢复的全过程,对系统设计、优化、崩溃或状态跃迁预测等都有重要的指导意义[23-26]。目前,对无人机集群的韧性研究逐渐受到关注[27-28],但集群覆盖问题的研究鲜有涉及无人机发生失效并开展恢复的情况。因此,有必要将韧性因素纳入无人机集群通信覆盖问题的研究。

在诸多覆盖算法中,文献[1]为需要全局信息的集中控制算法,文献[8-10,11,13-14]均可视作分布式控制算法,其中除文献[14]以外均是基于虚拟力的方法。但上述方法鲜有综合考虑以下几个问题:① 仅依赖于局部信息的完全分布式方法;② 明确给出虚拟力权重的确定方法;③ 考虑任务中无人机个体失效的情况。因此,在现有研究的基础上,本文旨在充分发挥无人机集群自组织、自恢复的能力,进一步考虑个体失效的情况,提出一种分布式自组织覆盖方法。本方法引入边界排斥力、重点区域吸引力、无人机排斥力3种虚拟力并给出其权重因子的确定方法,使无人机在感知周围信息的情况下自组织地完成区域覆盖,并适用于包含重点覆盖区域的情况。此外,通过引入基于韧性的覆盖关键阈值调节机制,使无人机集群在个体失效后能够快速完成重构和补位。

1 无人机集群自组织覆盖算法

1.1 基本假设

为对无人机集群覆盖问题进行简化,本文基于以下假设:

(1) 所有无人机均可看作具有恒定飞行高度的节点,其覆盖范围为Rc(见图1)。

(2) 所有无人机节点可通过定位系统获取本身位置信息。

(3) 每个无人机节点具有半径为Rs感知能力,可以获取感知范围内友军的位置(见图1)。

(4) 待覆盖目标区域为二维平面。

(5) 所有无人机节点提前获知覆盖区域边界及重点区域位置信息。

图1 无人机覆盖示意图Fig.1 Schematic diagram of unmanned aerial vehicle coverage

1.2 监视覆盖区域划分

如图1所示,在实际的覆盖任务中,往往存在着需要重点关注的覆盖区域,针对这样的区域,对其覆盖更应保持连续性,并尽量减少覆盖盲区。因此当用传统的覆盖率表征无人机任务能力时,需进一步考虑重点区域与普通区域的差别。

假设需覆盖的区域面积为ST,无人机已实现覆盖的重点区域面积为Sa,已覆盖的普通区域为Sb,则无人机集群的覆盖率C计算如下:

(1)

式中:μ为重点区域的权重系数;φ为重点区域在全部需覆盖区域(普通加重点)内所占比例。因此,覆盖率C可以表征无人机集群在考虑重点区域下所达到的覆盖范围。

1.3 虚拟力设计

虚拟力的概念源于势场和圆盘堆积理论的结合,前人的研究多将虚拟力设为3种,即节点之间的吸引和排斥力,以及区域边界对节点的排斥力[8-9]。本文重点考虑目标区域存在重点覆盖区域的情况,因此将无人机集群中的个体在运动过程中受到的虚拟力分为3种:无人机之间的排斥力;无人机与边界之间的排斥力;无人机与重点覆盖范围中心的吸引力。

1.3.1 无人机之间的排斥力

假设无人机UAVi在t时刻的坐标为(xi(t),yi(t)),感知范围为Rs,在其感知范围内存在友军无人机Γ={s1,s2,…,sκ},其中κ为感知范围内无人机的数量。任意友军j∈Γ,t时刻的坐标为(xj(t),yj(t)),可获取两无人机之间的距离为

(2)

假设存在一个覆盖关键阈值dth=γ·2Rc,其中0≤γ≤1为关键阈值权重,若dij≥dth,则UAVj和UAVi之间没有作用力发生。若dij

(3)

式中:θji为力的方向,计算如下所示:

(4)

ωu为无人机之间排斥力系数。综上所述,UAVi所受的合力为

(5)

图2 无人机节点间的排斥力Fig.2 Repulsive force among unmanned aerial vehicles

1.3.2 无人机与边界之间的排斥力

(6)

式中:ωb为无人机所受边界产生排斥力系数。UAVi所受的边界合力如下所示:

(7)

图3 无人机受外力分析Fig.3 Analysis of external force on unmanned aerial vehicles

1.3.3 无人机与重点覆盖区域中心的作用力

当目标区域中存在重点区域时,引入了另一虚拟力,即重点区域中心对无人机集群的吸引力。在执行任务过程中,无人机集群在目标区域内应主动向重点覆盖区域靠近,特别是现有集群数量不能完全覆盖全部区域时。如图3所示,假设重点覆盖区域的中心坐标为(xD,yD),则该区域对无人机的吸引力为

(8)

(9)

式中:ωd为重点区域吸引力因子;θid为无人机指向中心坐标为(xD,yD)向量与x轴的夹角。

1.3.4 虚拟力因子的确定

无人机所受虚拟力的各权重系数,ωu,ωb和ωd决定了无人机最终所受合力的大小以及方向。因为边界产生的排斥力是对称存在的,且对于所有无人机个体来说均是朝向监控区域中心的,故边界的排斥力并未对无人机之间的相对距离产生影响。因此,无人机集群的覆盖范围主要受无人机之间的作用力以及重点区域中心吸引力的影响。在前人的研究中,假设节点的排斥力远大于吸引力[8],即ωu≫ωd。但实际实验中发现,仅凭上述条件难以对权重系数进行确定。文献[10]明确了相关系数,一方面其计算是基于全局所有节点信息,不适用于本文所涉及的分布式算法,另一方面其权重确定过程并未考虑边界排斥力产生的影响。因此,本文根据覆盖任务要求与无人机配置,提出虚拟力因子的量化确定方法。

图4 无人机位置极端情况1Fig.4 Extreme situation 1 of unmanned aerial vehicle location

UAVi与重点区域中心(xD,yD)之间的吸引力大小为

此外,UAVi所受边界排斥力为

(10)

当把无人机集群看作一个整体时,无人机之间的排斥力是集群的内力,无人机集群整体位置则由无人机所受外力决定,即边界产生的排斥力和关键区域的吸引力。边界产生的斥力使无人机集群朝覆盖范围中心(xU+xL)/2,(yU+yL)/2运动,同时关键区域的吸引力使集群朝(xD,yD)运动。考虑如图5所示的极端情况,UAVi与重点区域中心(xD,yD)均处于整个覆盖范围的边缘,无人机所受两个力方向相反。

图5 无人机位置极端情况2Fig.5 Extreme situation 2 of unmanned aerial vehicle location

(11)

将式(11)代入式(10),有:

(12)

(13)

将式(13)代入式(12),并且Dd≫Δ,可得

(14)

因此可设:

(15)

ωb=(Dc+0.5Dd)3

(16)

将式(16)代入式(11)可得

(17)

故可得各虚拟力的权重系数设计如表1所示。

表1 各虚拟力的权重系数设计Table 1 Weight coefficient of each virtual force

1.3.5 虚无人机位置更新

(18)

假设UAVi当前t时刻的位置坐标为(xi(t),yi(t)),无人机的飞行速度为vi,则可更新下一个时刻(t+1)时无人机的位置:

(19)

式中:合力方向与x轴的夹角为θi。

1.4 覆盖算法

基于所提出的虚拟力,无人机个体在群体中的运动则由感知范围内其他个体、覆盖区域边界以及重点区域中心所共同决定。每个无人机个体依据这些信息不断调整位置以最终达到覆盖效果。值得注意的是,本自组织算法是分布式,即无人机只需进行有限的通讯和获取少量的信息以完成自身的协同运动,针对每个无人机个体,具体算法流程如图6所示。

步骤 1初始化任务基本参数,包括覆盖区域坐标(xU,xL,yU,yL)、重点区域中心坐标(xD,yD)、感知半径Rs、覆盖半径Rc及飞行速度为vi。

步骤 2判断无人机是否进入覆盖区域,若已进入跳至步骤3,若未进入令ωb=0并跳至步骤3。

步骤 3根据式(5)、式(7)和式(8)计算无人机所受合力Fi。若合力Fi>0,则进行步骤4,否则跳至步骤6。

步骤 4根据式(19)计算无人机下一时刻位置坐标,若该坐标在覆盖区域边界内,则按此坐标更新无人机坐标,并跳至步骤6,否则进入步骤5。

步骤 5以(xD,yD)为运动目标确定运动方向θi,根据式(14)更新无人机下一时刻位置坐标,进入步骤6。

步骤 6判断当前是否停止覆盖任务,若任务继续进行则跳至步骤3再次对无人机的位置进行更新。

图6 无人机个体自组织算法流程图Fig.6 Flow chart of unmanned aerial vehicle self- organization algorithm

2 基于韧性的无人机集群覆盖

2.1 集群韧性指标

无人机集群在执行覆盖任务时,其韧性可以定义为集群遭到扰动(例如个体故障、外界毁伤等)时,能够快速恢复任务区域的覆盖率,保障覆盖任务顺利执行的能力。韧性作为集群系统一种能力的表征,需要对其进行度量。现有韧性度量方法已有很多研究[25,29-31],而无人机集群覆盖具有明显的任务特性,例如,任务要求在规定时间内保障区域覆盖率达到一定程度。因此本文利用文献[25]中面向任务的系统韧性指标对无人机集群覆盖能力的韧性进行评估。其计算指标如下所示:

R(T)=βR0(T)+(1-β)R1(T)

(20)

式中:R(T)为T时刻系统的综合韧性,参数0≤β≤1,为韧性侧重因子。R0(T)为系统任务时间韧性,R1(T)为系统任务性能韧性,其计算公式如下:

(21)

2.2 集群的自组织恢复行为

集群的自组织行为机制使得个体能够根据所感知的周边情况对自身行为做出相应改变,而正是这样的机制使得无人机具有自重构、自恢复能力。以所提自组织覆盖算法为例,当个体感知周边无人机距离小于覆盖关键阈值dth时,排斥力的作用会使得个体相互原理以保障合适的覆盖重叠。当个体感知周边无人机距离大于dth时,虽然个体之间并没有作用力产生,但重点区域的吸引力会使个体朝重点区域靠近,在此过程中,个体之间的距离会随之减小并接近dth。

当无人机集群由随机分布状态到自组织完成区域覆盖后,无人机个体仍然基于此自组织算法实时根据感知范围内局部信息进行调整。如图7所示,在任务初始阶段,无人机在吸引力、排斥力的作用下,自发地朝覆盖区域各处运动,并最终保持相对稳定的覆盖效果。当无人机个体遭遇自身故障或外界扰动导致失去功能时,其覆盖范围内会出现“空洞”,此时集群的覆盖率会降低。随后无人机个体基于自组织行为规则,逐步将“空洞”补位填充,特别是将重点区域内的空缺进行填补,因此整个集群的覆盖率得到提高,从而体现了无人机集群在自组织覆盖算法下的韧性。

图7 集群自组织恢复过程Fig.7 Self-organizing recovery process of swarm

2.3 考虑失效的集群覆盖算法

由第2.2节可知,无人机集群通过本文提出的覆盖算法可实现毁伤下的自组织恢复,但反映韧性高低的一个重要方面是系统恢复的快慢程度。能否快速对毁伤无人机造成的空缺,特别是重点区域内的空缺进行填补,将直接影响集群韧性的高低。

图8 覆盖关键阈值调节过程图Fig.8 Coverage critical threshold adjustment process

将上述覆盖关键阈值调节机制与所提自组织覆盖算法相结合即可得到基于韧性的无人机集群覆盖算法,其流程如图9所示。在个体无人机每次执行自组织覆盖算法位置更新之前,无人机个体判断集群是否遭遇毁伤,若发生毁伤,则通过覆盖关键阈值调节机制对dth的大小进行调整,以进一步改变自组织覆盖算法位置更新结果。最终使无人机在遭到毁伤时,尽快完成重点区域内的空洞补缺,随后再避免无人机过度紧凑,扩大外围覆盖范围。

图9 韧性自组织覆盖算法流程Fig.9 Flow chart of resilient self-organizing coverage algorithm

3 仿真实验分析

在完成无人机集群自组织覆盖算法及韧性策略之后,为验证算法有效性,分别开展了重点区域覆盖、集群数量与关键阈值灵敏度以及集群韧性3个方面的仿真实验,所有实验采用多智能体仿真技术,并基于Anylogic平台开展。

3.1 重点区域覆盖

第1类实验是验证算法是否能正确引导无人机集群进行重点区域覆盖。将重点覆盖区域中心设置在整个目标区域的不同位置,整体目标区域范围为1 200 m×1 200 m,无人机个数为25个,覆盖半径Rc=80 m,感知半径Rs=400 m,结果如图10所示。由图10可以看出,无论重点覆盖区域的中心位于整个目标区域的哪个位置,本文所提出的算法都可以较好地引导无人机集群在数量较少无法对整体目标区域覆盖的情况下完成对重点区域的覆盖。

图10 不同重点区域中心无人机集群覆盖情况Fig.10 Coverage of unmanned aerial vehicle swarm in different key areas

3.2 集群数量与关键阈值灵敏度

图11 n=20时集群覆盖情况Fig.11 Swarm coverage with n=20

图12 n=30时集群覆盖情况Fig.12 Swarm coverage with n=30

图13 n=40时集群覆盖情况Fig.13 Swarm coverage with n=40

图14 n=50时集群覆盖情况Fig.14 Swarm coverage with n=50

图15 无人机数量和不同关键阈值覆盖率大小Fig.15 Number of unmanned aerial vehicles and different critical threshold coverage sizes

3.3 考虑个体失效的集群韧性评估对比

当集群数量分别为20,30,40,50时,各进行20次实验,并在任务结束时,根据第2.1节中的韧性指标计算集群韧性,其中将各时刻下覆盖率作为系统的性能指标Q(t),实验参数如表2所示。实验结果如图16所示,无论集群规模如何,所提算法的平均韧性均要高于方式N,并且方式P的稳定性更强,即多次实验下,集群的韧性偏差不明显,而方式N的恢复效果具有较强的随机性。当无人机数量较少时,本身覆盖率已经不高,而且由于个数数量较少,个体之间的虚拟力相对也较少,所以遭到毁伤后,两种方式的恢复差距不大。与之相对应的,当无人机数量增多时,无人机之间的作用力也随之增加,此时所提算法能帮助集群更加快速、稳定的恢复。

表2 实验参数表Table 2 Parameters in experiments

图16 不同集群规模下两种模式的韧性Fig.16 Resilience of two modes in different swarm scales

当无人机集群数量为40,两种模式下单次实验覆盖率随时间变化的过程如图17所示。当毁伤发生后,两种模式均开始恢复,并最终能恢复到相类似的覆盖率。但在恢复过程中,韧性策略模式能够更快速补充重点区域产生的空缺,使覆盖率能够快速回升。而过度收缩同样会减小覆盖率。因此,在聚集一段时间后再次恢复覆盖关键阈值(时刻130),使集群以更合适的间距进行覆盖。因此变阈值模式下集群的韧性达到0.881,而常规模式下系统韧性只有0.71。

图17 n=40时两种模式下单次实验覆盖率随时间变化过程Fig.17 Variation process of single test coverage over time in two modes with n=40

3.4 毁伤规模与无人机集群韧性

参考第3.3节集群覆盖仿真实验参数,以无人机集群数量n=40为例,考虑无人机集群遭遇毁伤时,失效无人机规模不同对集群执行覆盖任务得影响。由无人机失效规模为2架为起始,逐渐增加失效个数,直至最大失效个数为10架。每种失效规模各开展20次仿真实验,记录其韧性的均值。

实验结果如图18所示,随着失效规模的增加,两种恢复策略下的韧性值均会下降,但本文所提算法(方式P)的韧性均优于方式N。此外,在方式P下,毁伤规模达到7时韧性会显著下降,而在方式N下,毁伤规模达到6即发生显著韧性下降。韧性的显著下降代表着实验中,存在多次集群恢复后未达到任务要求覆盖率。当毁伤规模大于等于9架时,两恢复模式均处于低位,且基本不变。这是由于剩余无人机的数量无论怎样分布,均已无法达到任务要求。

图18 n=40时无人机韧性随毁伤程度变化Fig.18 Resilience of unmanned aerial vehicles varies with degree of damage with n=40

4 结束语

本文针对空域目标区域覆盖中存在重点区域的场景,提出了一种基于虚拟力的无人机集群自组织空域覆盖算法。无人机个体通过感知周围个体的位置,调节自身的运动以达到目标区域覆盖,特别是重点区域的偏向覆盖效果。通过分析集群的自组织行为,设计了一种覆盖关键阈值调节机制,以提高集群在执行覆盖任务过程中遭遇毁伤后的恢复能力。仿真实验以面向任务的韧性指标度量无人机集群的恢复能力,实验结论表明所提出的算法相比一般自组织覆盖算法具有更强的韧性。后续将进一步考虑关键阈值变更大小、恢复时间以及集群毁伤比例之间的关系,研究其最优化参数确定方法。