一种面向航空集群的无人机中继网络部署策略

刘 创,吕 娜,陈柯帆,张步硕,曹芳波

(空军工程大学 信息与导航学院,西安 710077)

0 概述

随着数字化战场研究的不断深入,通过少量作战平台完成单一作战任务的作战方式已不能满足复杂多变的战场环境,为使航空作战平台协同、高效地完成作战任务,实现多平台、多任务的综合化、体系化作战,研究人员将生物集群的理念应用到航空作战领域,提出航空集群的概念[1-3]。航空集群中通常存在多种类型的作战平台,如预警机、战斗机、侦察机、无人机等,并且规模较大,一般达到几十甚至上百架,且平台机动性强、分布范围广。航空集群作战针对侦察发现-定位跟踪-决策-打击(OODA)各阶段的不同作战任务,不同类型的平台依据任务需求动态组合,按需协同、连续、闭环地实现OODA的完整作战过程。

在航空集群作战环境中,平台的位置和组合随任务需求而变,使航空集群平台的分布呈现随机性、离散性和广域性特点。平台分布、作战目标与作战任务匹配,但可能与通信拓扑不匹配,即某些平台可能成为通信的孤立节点,从而造成信息无法相互传输,集群协同任务无法完成。因此,如何实现航空集群中大量机动、分散作战单元间的有效连通是需要研究的问题。近年来无人机在飞行高度、续航时间和通信能力等方面有了很大提高,利用无人机中继可以有效解决上述问题。无人机中继平台具有覆盖范围广、部署便捷、使用灵活的特点,并能实现超视距通信[4]。

在航空集群作战中,通过合理部署多架无人机组成中继网络,可以有效连通网络覆盖范围内相互孤立的节点或者编队子网,使广域分布的作战资源相互联结,实现多种平台间的密切交互。为此,本文提出利用无人机构建中继网络的设想,在给定中继无人机数量和通信半径的约束条件下,综合考虑作战单元覆盖、网络连通和抗毁性,设计虚拟力局部调整的粒子群优化(Virtual Force locally Adjusted Particle Swarm Optimization,VFA-PSO)算法,以解决无人机中继网络的部署问题。

1 中继网络部署相关研究

中继节点的部署位置直接影响网络的覆盖质量、连通性和抗毁性,从而影响整个网络的拓扑结构和网络可靠性等性能[5]。目前,关于无人机中继网络的相关研究主要分为2类:

1)无人机动态维持问题的研究。此类研究即在中继无人机数量较少的情况下,研究中继无人机的最优飞行路径和网络性能优化等问题[6-7]。文献[7]提出了一种支持地面移动自组网通信的无人机中继网络,其中中继无人机需要周期性收集地面移动节点的位置信息,实时地调整自身的飞行轨迹,不适合在航空集群作战背景下对空中高速移动的节点或者编队子网进行中继。

2)相对静态网络场景下网络部署问题的研究。此类研究分为确定性部署[8]和随机部署[9]2种部署方式。确定性部署是指事先根据业务需求和节点性能设计节点放置的位置,将节点定点部署。这种部署方式存在边界区域资源冗余、灵活性差、不适用于非规则区域的缺点。随机部署则是根据已知的条件构造最优化问题并利用遗传、虚拟力和粒子群等智能算法获得部署的位置点,具有很强的灵活性,更具实用性。例如:文献[10]将网络部署建模成几何连通圆盘问题,并利用遗传算法对部署开销和用户覆盖同时优化,但是遗传算法通常针对静态设备进行部署;文献[11]提出一种不依赖网络连通性的虚拟力算法,但这种方法容易导致节点总是聚集在区域中心部分,无法有效实现区域边缘附近的覆盖。这两类研究均以民用中继为背景,主要考虑对于用户的覆盖问题,而未考虑网络的抗毁性,不适合作战应用。

针对上述问题,本文首先建立中继无人机的连通覆盖模型,并结合中继网络的特点,提出节点聚集度的概念;然后针对已有算法无法有效结合覆盖、连通和抗毁性进行部署的问题,设计VFA-PSO算法;最后结合实际的部署问题将该算法与其他算法进行对比,研究其有效性和稳定性。

2 场景及模型

2.1 场景描述

本文研究如图1所示的集群作战应用场景,场景中大量分散着多种类型的作战飞机,有单个孤立的飞机节点和编队子网,它们根据不同的作战任务动态组织。这些航空集群平台的分布呈现随机性、离散性和广域性特点,因此,本文把对分散机动单元的有效连通问题转化为对任务区域的覆盖问题。其中,任务区域的划分是根据具体作战任务和预定航线事先划定的,可以是规则的任务区域,也可以是非规则的,并通过合理部署多架中继无人机实现对任务区域的稳定覆盖,为整个作战过程提供通信支持。

图1 集群作战场景

2.2 中继无人机的几何模型

在一般情况下,中继无人机的覆盖区域范围由飞行高度、覆盖区域高度和中继信号最大传播距离决定,而中继信号最大传播距离与中继链路信道状况有关[12]。本文主要针对空中作战平台进行中继。假设中继信号的最大传播距离为R,中继无人机的部署高度为H,对于高度为h的空中区域,若不考虑发射功率和天线波束限制因素,中继信号的最大覆盖半径为:

在航空集群作战中,不同的空中平台相互之间高度差通常在几十米到几千米之间,而中继信号的最大传播距离可达到数百千米以上,虽然中继平台与作战平台不处于同一飞行高度范围,但是平台之间的高度差与平台的通信距离相比几乎可以忽略。从中继网络的拓扑结构来看,平台之间的高度差对中继信号的覆盖范围和网络拓扑结构的影响可以忽略。因此,为便于建模分析,本文把三维空间中的无人机中继网络部署问题降维到二维平面上进行研究,同时假设中继无人机具有以下特征:

1)对任务区域的覆盖半径和中继无人机之间的连通半径相等,都设为R。

2)中继无人机可以获取自身的位置信息,并和邻居节点交换位置信息。

3)中继无人机能够准确移动到优化后的位置,并能够盘旋在这个位置附近,而又不至于远离这个位置,并认定盘旋状态下的无人机为静止状态。

3 相关定义

3.1 区域覆盖率

为有效地评估网络覆盖性能,本文采用网格化方法将任务区域划分成网格形式(其中相邻网格间的距离由待求解问题的精度决定),并将每个网格简化为点,称为像素点,分析各节点对该像素点的覆盖情况。设任务区域内有m×n个像素点。节点集S的区域覆盖率Rarea(S)为节点集S覆盖像素点数的总和与任务区域总像素点的比值,计算公式如下:

(1)

3.2 中继节点的聚集度

对于一个网络,网络的抗毁性是衡量节点在遭受打击失效的情况下网络拓扑结构保持连通的能力[13]。目前的抗毁性优化设计模型集中于拓扑结构的优化,主要讨论了2个方面的问题:在满足网络连通性的要求下使总费用最少,以及在给定费用的前提下使网络的连通性最大。在本文研究的无人机中继网络部署问题中,由于中继无人机数量和通信半径受限,因此如何在此条件下构造一个既要满足覆盖和连通的要求,同时又最大化网络抗毁性的部署模式是本文考虑的主要问题。

为解决上述问题,本文引入凝聚度的概念。凝聚度的衡量标准是节点之间的平均最短路径和网络中的节点数目[14]。这种对节点重要性的评估只关注网络拓扑结构,并未考虑节点自身的功能和在网络中承担的作用。图2表示7个节点形成的中继网络在节点位置变化情况下网络拓扑和覆盖范围的变化。从中可以看出,节点1、节点3、节点5和节点6位置的变化并未引起网络拓扑结构的变化,因此,每个节点的凝聚度并没有发生变化。但图2显示中继网络的覆盖范围却发生了明显变化,每个节点在中继网络中承担的作用也发生了明显变化。

图2 中继网络变化示意图

在中继网络中,每个中继节点不仅要对自身覆盖范围内的用户进行中继,同样要考虑为邻居节点转发信息。因此,本文针对无人机中继网络部署的问题,结合凝聚度和中继节点自身的功能,定义节点聚集网络资源的评估参数,即中继节点i的聚集度βi:

(2)

3.3 部署评估函数

在中继节点数量和通信半径一定的情况下,同时考虑网络覆盖、连通和抗毁性3个条件构建中继网络,应在保证网络连通的基础上最大化网络对任务区域的覆盖,同时为增强网络的抗毁性,各中继节点的聚集度方差应尽可能小。这3个条件相互约束,无法单独拿出其中一个条件对网络性能进行评估。综合考虑后可得到无人机中继网络的部署评估函数为:

Earning=l1×Rarea(S)-l2×var(βi)

(3)

其中,l1、l2为权重系数。

4 VFA-PSO算法设计

目前利用遗传、虚拟力和粒子群等智能算法对连通和覆盖问题的研究存在以下2种特点:1)网络中存在固定节点和移动节点,以覆盖率为目标利用智能算法对移动节点位置进行优化;2)节点的连通半径远大于节点的覆盖半径,并且节点数量较多,初始分布较密。上述特点使得对网络部署问题的研究通常在默认网络是连通的基础上进行优化。而在本文场景中不存在固定节点,并且任务区域较大,中继无人机数量和通信半径受限,粒子搜索结果容易出现网络节点之间不连通导致无法评判解的质量的情况,这在一定程度上限制了PSO算法的使用。

4.1 PSO算法原理

PSO算法是一种基于群体智能的新型进化计算技术,被广泛应用于各种优化领域。PSO算法中每个粒子代表了一种潜在的最优解,每个粒子根据自身的当前信息、自身历史信息和种群的信息局部扰动其飞行轨迹,从而在搜索空间寻找最优解。设由m个粒子组成的群体对Q维(即每个粒子的维数)空间进行搜索。粒子i的位置表示为:Xi=(xi1,xi2,…,xiQ),粒子i的速度表示为Vi=(vi1,vi2,…,viQ)。基本PSO算法的速度更新公式如下:

viQ(k+1)=w×viQ(k)+c1×γ1×[p(k)-xiQ(k)]+

c2×γ2×[g(k)-xiQ(k)]

(4)

粒子在搜索过程中位置更新公式为:

xiQ(k+1)=xiQ(k)+viQ(k+1)

(5)

在式(4)和式(5)中,k表示第k次迭代,w为惯性权重因子,c1和c2为学习因子,γ1和γ2为相互独立的(0,1)区间内的随机数,v(k)∈[-Vmin,Vmax],为粒子的速度范围,x(k)∈[Lmin,Lmax],为搜索空间,p(k)为粒子自身历史最优值,g(k)为整个种群的历史最优值。

粒子的速度和位置更新方式能够直接决定解的质量和求解效率。粒子位置更新过快虽然在一定程度上会使粒子遍历搜索,跳出局部最优解,但由于中继节点之间连通性的限制,无目的位置更新会导致中继节点之间不连通。鉴于此,为兼顾网络覆盖和连通,避免每次迭代后由于节点之间不连通导致无法计算适应度值的情况出现,本文在每次迭代后加入虚拟力有目的性地对节点的位置进行局部调整。

4.2 基于虚拟力的收缩和分散

假设在粒子位置更新过程中加入引力和斥力来对粒子位置进行有目的性的调整。每个粒子在完成一次迭代后根据粒子位置信息计算相应的邻接矩阵,并根据邻接矩阵进行网络连通性检测。若检测到网络不连通,则把网络中的节点分为连通节点和不连通节点,并计算网络不连通节点受到的来自连通节点的引力,对中继节点进行有目的性的收缩;若检测到网络连通,则计算节点受到邻居节点和边界的斥力,通过虚拟力影响,在保证网络连通的基础上使节点分散,增强每次搜索的效果。

不连通的节点sk受到网络中连通节点sl的引力可表示为:

(6)

节点si受到邻居节点的斥力表示为:

(7)

节点si受到边界的斥力表示为:

(8)

在式(6)～式(8)中,wa和wr分别表示节点之间的引力系数和斥力系数,用于调节粒子位置更新后中继节点的疏密程度,αkl表示为节点sk到节点sl的方位角,D(sk,sl)为两节点之间的距离。

网络中节点sk所受合力Fk为所有作用到该节点力的叠加。粒子i的位置向量中第Q维元素受到虚拟力的移动距离fiQ为:

(9)

其中,各元素的上角标表示元素序号,下角标则对应粒子序号的虚拟力在相应坐标轴的分量,maxstep为最大位移距离。

虚拟力调整的位置更新公式为:

xiQ(k,i)=xiQ(k)+w×γ3×c3×fiQ

(10)

其中,γ3为(0,1)之间的随机数,c3为调节因子,w为惯性权重因子。

从式(4)、式(5)和式(10)中可以看出,w不仅影响粒子的飞行速度和飞行位置,决定整个算法的搜索效率,同时影响粒子位置局部调整的精度。在粒子早期搜索阶段,粒子位置更新较快,节点之间容易出现不连通现象,此时希望w较大来加强粒子的早期搜索能力同时强化虚拟力的影响。在后期搜索阶段,希望w较小来弱化虚拟力的影响,强化全局最优解和粒子历史最优解的影响。因此,本文设置w为:

w=wmax(wmax/wmin)1/(1+10×iter/itermax)

(11)

其中,iter表示当前迭代次数,itermax表示最大迭代次数,wmax和wmin为w的限制范围。

4.3 搜索策略

在一个二维平面内,假设利用PSO算法对N个中继节点进行部署,则算法的搜索空间维数Q=2N。在粒子运动过程中,解的质量取决于适应度函数。本文将部署评估函数Earning的倒数取为PSO算法的适应度函数Fitness。根据上述规则设计VFD-PSO部署算法,伪代码如下:

1. 输入无人机数量N,通信半径R,任务区域范围;

2. 初始化粒子速度V0,位置X0;

3. Do{

4. 式(4)→更新粒子的速度;

5. 式(5)→更新粒子位置;

6. 根据粒子位置XiQ计算对应的邻接矩阵A;

8. for i=1∶N

9. BN(i,i)≠0→连通节点集;

10. BN(i,i)=0→非连通节点集;

11. end for

12. if∃i,使得 BN(i,i)=0

13. Do{

14. 式(6)→计算节点受到的引力;

15. 式(10)→非连通节点收缩;

16. }while∀i,j,BN(i,j)≠0

17. end if

18. 式(7)和式(8)→计算节点之间的斥力;

19. 式(10)→调整粒子位置XiQ;

20. if Fitness(Xi)

21. 更新p(k);

22. 找出种群中每个粒子自身历史最优值p(k);

23. 种群的历史最优值g(k)为g(k)=min{p(X1),p(X2),…,p(Xi)}

24. }while iter达到最大

在上述算法中,第6行～第11行是对网络连通性的检测和对节点分类,第12行～第17行是对不连通的节点进行收缩。

5 仿真分析

在一台主频为3 GHz、内存为4 GB的PC上,基于MATLAB环境下对所提出的算法进行仿真。设置任务区域的大小为500 km×400 km,中继无人机的通信半径R为120 km。学习因子c1和c2都为2,wmax=0.9,wmin=0.4,虚拟力参数|Fth|=5,虚拟力的调节因子c3=0.5,wα=5,wr=0.2,最大位移距离maxstep=30 km。

在仿真实验中同时采用基本PSO算法和2种改进的PSO算法作为对比:1)基于速度更新因子改进的带有引力和斥力的PSO(Combined Attraction and Repulsion PSO,CAR-PSO)算法[15];2)基于粒子搜索能力改进的粒子搜索能力增强型PSO(Explorative Capability Enhancement PSO,ECE-PSO)算法[16]。种群大小都设为10,最大迭代次数itermax为100。

首先,为了验证节点聚集度对网络抗毁性评估的有效性,在任务区域内部署12个节点,选取2种算法的部署情况进行分析。图3为VFA-PSO算法部署结果,覆盖率为98.7%。图4为CAR-PSO算法部署结果,覆盖率为97.3%。图5为2种部署结果的节点聚集度变化曲线。

图3 VFA-PSO算法部署结果

图4 CAR-PSO算法部署结果

图5 2种部署情况的节点聚集度变化曲线

可以看出,2种部署方式对任务区域的覆盖率相差不大,但是从图5中可以看出,VFA-PSO算法部署的网络节点聚集度的方差明显小于CAR-PSO算法。从网络的抗毁性角度分析2种部署结果,例如,节点7对应图4中坐标为(290,97)的节点聚集度最大,移去该节点,虽然中继节点对任务区域的覆盖没有变化,但网络将不连通。而在图4的部署结果中,节点分布更“分散”。结合图3和图4可以明显看出,图4部署网络中每个节点承担的“作用”差距较大,导致节点分布并不均匀,网络抗毁性较差,这验证了节点聚集度定义的准确性,可以有效评估中继网络中各个节点的作用。

表1为50次独立实验的平均性能比较。从中可以看出,在中继节点数量较多的情况下,各算法覆盖率差距不大,但是VFA-PSO算法的聚集度方差要明显优于另外3种算法。这说明只更改优化目标而不对算法的机制作适应性改变,并不能有效改善解的质量。

表1 50次独立实验的平均性能比较

为进一步分析VFA-PSO算法的稳定性和有效性,并验证VFA-PSO算法在节点数量减少的情况下的部署效果,采用上述4种算法对8个中继节点的部署效果进行了仿真验证,图6为适应度函数值随迭代次数的变化曲线。可以看出,VFA-PSO算法具有比其他3种算法更好的寻优能力,具体反映在2个方面:1)每次迭代后适应度值更小;2)种群最优解停滞不变的次数最小。这说明VFA-PSO能有效增强每次迭代所产生解的质量,避免粒子搜索过程中由于节点之间不连通导致无法计算适应度函数的情况出现。同时可以看出,ECE-PSO算法虽然能够有效提高粒子搜索能力,避免种群长时间陷入局部最优解,但是在节点数量较少的情况下,节点的位置受到网络连通性的限制比较大,单一地提高粒子搜索能力并不能有效改善解的质量。

图6 适应度函数值随迭代次数的变化曲线

图7显示了50次独立实验区域覆盖率的变化,从中可以看出,VFA-PSO算法每次实验的覆盖率要高于另外3种算法,并且覆盖率的波动较小。其中,VFA-PSO算法的方差为9.26E-5,PSO算法为2.84E-4,ECE-PSO算法为2.24E-4,CAR-PSO算法为2.26E-4,可见VFA-PSO算法方差最小。因此,VFA-PSO算法的稳定性要优于其他算法。

图7 相同实验条件下覆盖率的变化曲线

结合图6和图7可以看出,在节点数量较少的情况下,VFA-PSO算法解的质量要明显优于其他3种算法,并且覆盖率能保持较高水平,具有更高的稳定性。

6 结束语

网络部署是网络运行的前提和基础。为解决航空集群作战中大量机动、分散作战单元有效连通的问题,本文提出利用多架无人机构建中继网络的设想,并对该网络的部署问题进行研究。考虑到高对抗的战场环境,在部署过程中以优化网络覆盖率、提高网络抗毁性为目的,设计了一种基于虚拟力局部调整的PSO算法,通过在粒子每次迭代后加入虚拟力有目的性地对节点的位置进行局部调整,增强粒子群算法的搜索能力。仿真结果表明,该算法在保证网络连通的前提下,能有效提高网络覆盖率和网络的抗毁性,具有较好的部署效果。后续将进一步研究链路中断、任务区域动态变化以及网络信号相互干扰等环境下的无人机中继网络部署方案。

[1] 霍大军.网络化集群作战[M].北京:军事科学出版社,2009.

[2] 段海滨,邵 山,苏丙未,等.基于仿生智能的无人作战飞机控制技术发展新思路[J].中国科学:技术科学,2010,40(8):853-860.

[3] 吕 娜,陈柯帆.面向航空集群云网络的航空数据链MAC协议[J].系统工程与电子技术,2016,38(5):1164-1175.

[4] 刘红军.美军无人机通信中继发展现状与趋势[J].飞航导弹,2017,2(2):35-40.

[5] 李 旭.面向应急通信的中继网络部署问题研究[D].合肥:中国科学技术大学,2015.

[6] 符小卫,程思敏,高晓光.无人机协同中继过程中的路径规划与通信优化[J].系统工程与电子技术,2014,36(5):890-894.

[7] 徐赞新,袁 坚,王 钺,等.一种支持移动自组网通信的无人机中继网络[J].清华大学学报(自然科学版),2011,51(2):150-155.

[8] WANG H,WANG W,HUANG J,et al.Modeling multiple unmanned aerial vehicles placement problem in ad hoc network quadratic unconstrained binary optimization[C]//Proceedings of International Conference on Unmanned Aircraft Systems.Washington D.C.,USA:IEEE Press,2013:926-932.

[9] PERUMAL S,BARAS J S,GRAFF C J,et al.Aerial platform placement algorithms to satisfy connectivity,capacity and survivability constraints in wireless ad-hoc networks[C]//Proceedings of GLOBECOM’08.Washington D.C.,USA:IEEE Press,2008:518-522.

[10] 李 越,刘乃安.无线Mesh网络部署几何连通覆盖问题求解方法[J].计算机科学,2016,44(6):75-79.

[11] LIU H,CHU X,LEUNG Y W,et al.Simple movement control algorithm for bi-connectivity in robotic sensor networks[J].IEEE Journal on Selected Areas in Communications,2010,28(7):994-1005.

[12] 朱秋明,周生奎,霍帅珂,等.无人机中继平台覆盖区域统计模型[J].航空学报,2014,35(1):223-229.

[13] 史春辉.复杂网络拓扑结构抗毁性研究[D].成都:电子科技大学,2012.

[14] 杜雨弦.复杂网络中节点重要度评估算法的研究[D].重庆:西南大学,2015.

[15] LU S,YU S.An improved particle swarm optimizer with attraction and repulsion[C]//Proceedings of Inter-national Conference on Computing and Convergence Technology.Washington D.C.,USA:IEEE Press,2013:735-740.

[16] 杨永建,樊晓光,甘 轶,等.基于改进PSO算法的传感器网络覆盖优化[J].系统工程与电子技术,2017,39(2):310-315.