一种基于信息素图的无人机高效通信覆盖方法

任少睿,陆忠梅,2,*,石远明,李立欣,陈巍

1.清华大学 电子信息工程系,北京 100084

2.贵州电子信息职业技术学院,贵州 556000

3.上海科技大学 信息科学与技术学院,上海 201210

4.西北工业大学 电子信息学院,西安 710129

随着信息化的不断提升,无线数据通信被越来越广泛地应用在实时监控、调度监督等方面。在难以使用基站方式通信时,特别是遭遇洪水、地震等急需信息接收渠道的抢险救灾时刻,或是应用于保卫战争等特殊用途,借助无人机(UAV,Unmanned Aerial Vehicle)进行通信覆盖都是一种高效的方式。而这些实际运用,对于无人机自组织的飞行网络提出了灵活性、低时延及长续航、安全性等方面的要求。本文研究的主要问题,是在无人机数量相比于待覆盖面积较少,也即无人机平均密度较低情况下的无人机群通信覆盖方法。

目前无人机协同航迹规划中,集中式和分布式是主要采取的2种方式。对于集中式方法,需数据处理中心对所有无人机获取的信息进行分析并做出决策,这使得无人机无法自主进行航向选择而需作为数据处理中心的依附,进而使应用中增加了数据处理中心的限制及无人机群灵活性的约束。相比于集中式方法,分布式方法中无人机的运动不受数据处理中心的制约,更具灵活性。

目前的分布式方法中,基于深度强化学习的协调控制方法具有较强适应性,但这一方法的分布式建立于前期大量训练的基础之上。基于变量一致性的梯度下降算法(DGD),通过计算目标函数梯度,能较为高效地得到无人机规划结果。但目前此类分布式方法不能方便地处理异步问题,计算目标函数的梯度有时难以完成。同时受系统个体间通信时延的影响,其最终结果在收敛性上仍存在需继续研究的问题。基于分布式模型预测控制(DMPC)的方法在假设无人机间解耦的条件下能够完成分布式的要求,但该方法需假设无人机间的全连接,因此同样面临着无人机间可能出现的不同步而带来的问题。在无转角限制条件下,采取临近处信息素图(Pheromone Map)驱动能较快给出结果,是一种可行的方式。但从其续航性能而言,因机载能源的有限性限制了无人机的续航能力,为提高无人机的续航能力,在无人机机载能源不变的情况下需降低其平均能耗。而无人机在运动中单位时间能耗随着航迹转角增大而迅速上升,无人机行进相同距离的转角,也即无人机允许的转弯半径将受到限制。对于采取临近处信息素图驱动得出的最优航向中,因存在对于无人机进行快速转弯的需求,需对机载能源提出较高要求。

无人机通信覆盖方法中,将区域进行划分,借助信息素图,使无人机群能够自主规划行进路径,因与其他技术结合性好而成为常用方法。另一方面,目前无人机通信覆盖分布式方法大多未考量物理层中无人机实际航行的安全性需求。对此,若采取压制干扰方式,对无人机有源大功率辐射提出了要求,不利于无人机的续航能力；依靠航迹欺骗等手段在一定程度上优于压制干扰,但目前仍主要处于理论论证阶段；多无人机协同干扰能取得较好效果,但对单位覆盖面积的无人机数量需求将大幅上升。

为提高通信覆盖效率,考虑无人机灵活性、低时延及长续航、安全性的要求,提出一种基于信息素图的多无人机通信覆盖方法。首先分析实际应用场景以获得无人机运动的解耦条件,通过引入地面锚节点(Anchor-node)、限制无人机转弯半径、增加地理价值描述函数等方式满足前述要求。然后设计了无人机运动的收益函数及航向选择方法,最后以小范围内无人机收益最大作为目标进行仿真,优化待覆盖区域重访时间,提高通信覆盖效果。数值计算表明,所提出的方法优于无地理价值描述的覆盖方法,且具有较高的执行效率。

1 问题假设及流程

本文研究问题可表述如下：在给定区域内,给定无人机数量,其满足无人机密度较稀疏的条件,同时在保证无人机转弯半径存在下限的前提下,如何达到最优的无人机自组织覆盖,使得区域内各点接入时间间隔尽可能小且均匀。

1.1 问题说明

前述无人机密度较稀疏,一方面对应于部分实际任务中,待覆盖区域极短的接入时间间隔的收益,与付出的代价相比较低,如交通状况数据搜集等,其对于通信更新频率的要求不高,不必调用过多无人机；另外,在抢险救灾等特殊应用中,短时间调集大量无人机也存在实际困难。对于确需较高无人机密度的应用场景,请参考4.5节中的讨论。

实际中,无人机的爬升率对于其飞行性能同样有较大影响,飞行高度不同,其对地面的有效覆盖范围也不同。平原、丘陵地带的地面起伏在200 m 以下,有限大小的待覆盖区域内起伏约几十米,这与无人机数百米的飞行高度相比基本可作为一平面。以大疆Phantom 4 RTK 无人机的实际数据为例,当飞行高度为250 m 时,其可保持0.1 m 的悬停精度。此外,与水平运动相比,无人机爬升的能耗更高,因此在不必要的情况下减小爬升率有利于延长其飞行时间。假设各无人机在各不相同而差别很小的高度上做平面运动,保证了无人机之间不会发生碰撞,无人机的能耗只与其在水平面上的转弯半径相关,且其有效覆盖范围近似是一个常数。对此方面,进一步讨论请参考4.7节。

为保证安全性,无人机仅接收信号而不进行信号的发射,同时无人机仅需其与周围待覆盖区域内锚节点的相对位置而不需绝对坐标,是一种代价小,效果相对好的隐蔽方式。同时,2.2节中的地理位置,3.2 节中的覆盖收益、信息素值等,都是针对于地面锚节点而言的,也即对无人机而言,其覆盖的目标即为待覆盖区域中的锚节点。

根据上述分析,对模型做出如下假设：

1)平均而言,待覆盖区域内无人机密度稀疏。

2)各无人机在差别极小的不同高度上做平面运动,保证不会相撞的同时可以忽略此高度差。

3)无人机转弯半径存在下限,保证其续航能力。

4)存在地面锚节点,保证无人机运行安全性。

5)小范围内无人机航迹曲率近似不变。

1.2 流程架构

将本文讨论的方法称为相对位置的信息素图方法,方法中物理层地面锚节点完成信号的发送,同时根据相对位置及当前位置锚节点密度给出当前锚节点的地理价值(即2.2节向导信号中的函数)。对于航迹规划而言,无人机接收地面锚节点的向导信号,以预设的价值函数为依据,选择小范围内价值函数最大的航向行进。

其理论流程如图1所示,可抽象为：整个决策过程对时间进行离散化,在每个离散的时间内,各无人机依靠机载计算系统及预先设定的价值评价方式,通过对所需地点信息素的感知,计算并比较不同允许路径下,综合考量一段时间后的行进位置所获得的收益期望,选取收益最高的最优解行进。地面锚节点不断进行信号发送,当信息成功被无人机探知,则更新信息素记载,周期性运转,直至覆盖任务完成。

图1 算法模型流程图Fig.1 Flow chart of algorithm model

2 物理层及信号交互

2.1 物理层地面锚节点

本文所提出的相对位置的信息素图方法的物理模型示意如图2所示。

图2 物理层模型示意图Fig.2 Schematic diagram of the model

为满足无人机通信,待覆盖区域的各锚节点上均存在信号收发装置,而无人机上携带有信号接收装置以获取地面信息。为方便起见,将用于常规通信的信号称为通信信号,将用于为无人机行进选择提供判断依据的信号(即携带信息素信息的信号)称为向导信号,通常向导信号比通信信号更加简单,也更容易扩大向导信号的传播范围。

地面锚节点的信号收发装置一方面依靠无人机与外界通信,另一方面则判断是否成功依靠无人机完成通信,以不断更新向导信号。随着地面锚节点向导信号及通信信号的不断更新,与无人机的不断移动接收地面信号,整个无人机与地面锚节点系统将周期运行。

对地面锚节点及无人机间信号接收成功与否的判断方法而言,无人机可接收地面的向导信号并测定发射该向导信号的锚节点所在区域或位置,如应用与向导信号本身无关的基于图像识别技术的双目视觉技术及模糊测距技术,或采取适合于无人机所需探测方向的、有强定向性的侧射式天线阵,使用AOA(Angle of Arrival)技术,配合检测信号强度在信号传播过程中的自然衰减,即基于RSS(Received Signal Strength)技术,同时依据无人机飞行高度恒定,得到相应地点等。而对于地面锚节点而言,判断其发送的信号是否被无人机成功接收,同样可以采取上述双目视觉技术等。当无人机接收到地面锚节点信号,则可计算得出当前时刻应该选取的飞行方向,地面锚节点也根据当前无人机的位置更新该点的信息素值(若被覆盖则清零,未被任何一个无人机覆盖则继续增加)。时间单位的长度可根据无人机覆盖范围大小、地面锚节点密度以及无人机飞行速度选择,使得系统一方面保持较快的更新速度,另一方面不会做过多不必要的计算。

该方法采取分布式的信息处理与航向控制,同时信息素地图的存储亦不占用无人机内存,而储存在地面各锚节点的信号收发装置内。

2.2 向导信号P 函数的获取

为描述待覆盖区域内不同点的位置不同,同时避免使用锚节点之间的绝对位置以保证安全性,引入函数,称为地理价值描述量。对应于实际待覆盖区域内各点,函数的值有所不同。其计算表达式为

式中：为对应待覆盖区域的点集；为对应于以对应点为中心、半径等于向导信号的有效接收半径的点集(实际中信号自然传播可采取圆形)；取模运算为计算其内部点集的元素数量,即面积度量,以一无人机覆盖面积为单位。实际中,地面锚节点可根据接收半径(向导信号有效接收半径)内各锚节点所发向导信号的强度之和得到本地对应函数,如图3所示。

图3 向导信号P 函数有效接收半径示意图Fig.3 Schematic diagram of effective acceptance radius of P function of guide signal

特别地,在仿真中采取了方形的有效区域,是为在保证计算简便性的前提下检验函数的有效性。事实上,在物理层中这一计算远比仿真中所需要的简单。同时,为避免混淆待覆盖区域内不同点的函数值,仿真检验中以“矩阵”表示不同点的函数按照其位置排列而构成的矩阵。

无人机可采取基于RSS与AOA 结合的定位方法,受无人机转弯半径有下限的影响,本模型无人机所需要的信息素并非均匀分布在当前无人机位置的四周,而主要集中在当前运动方向前方,故而与基于天线辐射特性与接收天线方向特性的侧射式天线阵适应良好。

另一方面,地面锚节点的向导信号更新,亦可同样采取双目视觉等技术,对周围无人机距离进行测量,当存在无人机距当前锚节点小于通信信号接收半径时,可认为无人机已经将该锚节点的信息收集,向导信号可随之变化。

此外,函数可认为是一个动态变化的函数：当地面某一锚节点被摧毁,根据函数的获得方式,临近锚节点由于接收不到已被摧毁锚节点的向导信号,将会改变临近地点函数的具体数值。考虑到被摧毁的锚节点处虽然仍需覆盖,但由于缺少信号发射设备而丧失了覆盖的实际意义,故而这种动态变化有利于无人机有效覆盖效果的提升。

3 无人机航迹规划

3.1 无人机间运动解耦分析

多无人机系统需要考虑无人机之间的相互影响,但在该问题下若能对无人机之间运动解耦,则各无人机之间的影响作用可以只通过地面锚节点的信息素大小做间接的描述,而忽略其间的直接交互。即无人机之间并不是没有关联,其通过改变地面锚节点信息素来对其他无人机的运动产生影响；但因不需要再单独计算无人机之间的直接作用,所以可以简化推导,降低实际无人机航迹规划中的计算量。

接下来讨论无人机间运动解耦的限定性条件,这一条件也是本文达到分布式目标的充分条件。通过推导出各时间单位内,无人机之间发生直接相互影响的概率足够低,说明在无人机密度稀疏的假设下忽略无人机之间的直接相互影响是合理的,具体推导如下：

设每时刻无人机能覆盖的范围半径为,因本方法假设只考虑无人机在一恒定高度上运动,则两无人机之间发生直接相互影响需间距小于2。若无人机确实“均匀”地运行,即对于所有无人机而言,其在待覆盖区域上空的分布是均匀的,速度方向也是均匀的,设其大小为,那么对于一无人机而言,其他无人机的速度方向与此无人机的速度方向正交,无人机间的相对速度平均为

此时无人机均匀分布在整个待覆盖区域内,密度为

式中：为对应于待覆盖区域的点集；取模运算如前,为计算其内点集的元素数量,即对应的面积度量,以无人机覆盖面积为单位。因此平均而言,该无人机与其他无人机覆盖区域相互交叠的频率为

在一个时间单位内,该无人机的覆盖区域没有和任何一个其他无人机的覆盖区域发生交叠的概率满足：

考虑到实际中无人机并不是均匀分布在待覆盖区域中,无人机之间的速度方向也不是完全正交的,因此实际应该将相对运动速度修正为,频率修正为。因这一修正与无人机均匀性相关,则将与3.4节引入的参量相关。因此,无人机实际航行产生的值越接近于无人机均匀分布时所得到的值,则可以认为无人机越接近均匀分布,上述修正将越小,原公式与真实情况越相符,具体参量的引入在3.4节中进行。但即使需进行一定修正,由式(6)可知,与单位时间的长度、无人机密度的关系仍满足：当足够小时,趋于1。在时间单位长度确定时,无人机密度越小,将越接近于1。因此当无人机稀疏分布于待覆盖区域上空时,可近似认为到下一时刻之内,无人机间所允许的各路径均已解耦,无人机的运动不受其他无人机运动的直接影响,而仅需考虑接收到的地面信息。无人机运动解耦的假设,也是本文分布式计算的前提。事实上即使两无人机相距较近,两无人机也均会因受另一无人机已改变的地点的向导信号影响,而倾向于背离另一无人机行进。

经上述推导可知,时间单位长度不变时,随着无人机密度的提升,无人机的覆盖区域之间不发生交叠的概率将降低,不再满足解耦的条件,因此本模型难以直接应用到这种情况,对应讨论在4.7节中进行。

3.2 无人机航向及收益

参照图4,无人机决策依据系当前无人机从行进前方的小片区域内获知的向导信号。时间离散处理后,计算中无人机简化采取圆弧运动,而实际无人机运动为平滑的运动,这一点在离散时间的间隔趋零时得以过渡。每个时间单元内,无人机接收到前方所需区域(即图4中各预测轨迹末端连线内部,虚线所示)的向导信号,其携带有根据当前时刻距上一次该点被无人机覆盖的时间间隔,及该点周围锚节点密度,得到的覆盖该点的收益信息。因对于无人机的航行转角有限制,在每个时间单元内无人机航行距离与运动方向转角均较小,可将允许选择的航向转角离散处理。为保证离散得到的结果准确,可根据式(7)计算待选可行路径的数量,并据此得到各路径的曲率半径。实际计算中,无人机对比各可行路径的收益,选择最终的行进航向。

式中：为离散处理后待选择路径的总数,图4中为5；为一个时间单位内无人机可移动的距离,图4中为沿着无人机航向对比轨迹,从无人机当前位置到航向对比末端的距离；为无人机允许的最小转弯曲率半径；引入作为可调整的比例系数,同时用以调整量纲。

图4 无人机所需信息素对应区域及待比较路径示意图Fig.4 Corresponding area of pheromone and path to be compared for UAV

当≪时,根据几何关系,最小曲率的航向对比轨迹的末端与沿当前航向直行的轨迹末端距离近似为/,待选航向数应与此距离成正相关,以使得最终航行至轨迹末端时,不存在某点在各轨迹之间却不能被任何一轨迹覆盖的情况。简化地对二者取线性关系,对应的各个待选航迹的实际曲率半径使最终相邻两航迹末端距离相等,也可根据式(7)等价地计算出。

考虑允许的转弯有左右2个方向,以及直线航行,最终得到离散处理后待选择路径的总数满足式(7)。其中≪的条件,在单位时间长度不断减小时可满足。实际中系数(忽略单位)应至少大于1,以减小离散处理转弯半径对实际的影响,但为减小计算量也不宜过大,在本文最终的仿真检验中已取=2。

对于无人机不同路径的收益,采取如下分析：

首先,若将信息素均匀分布到无人机行走至信息素所在地的路径上,直到无人机行经该点,获得的信息素量相等,付出代价也相同(若将耗费时间等因素视为代价的话)。也即,单位行进(或者说单位代价)相应等效获得的收益,即

式中：为这一路径的收益；为对应行经地点的当前信息素价值(假设信息素随时间线性增长,为保证覆盖的均匀性,信息素价值与信息素本身的数值可以有所不同)；Δθ为当前转弯半径下,行经该点的速度方向与初始点速度方向的夹角绝对值；为小范围内行进轨迹的曲率半径,近似为一常数。

式(8)中的物理意义与信息素数值共同反映出来。信息素的数值对应了当前地点距离上一次被覆盖的时间长度,即接入时间间隔。为使无人机覆盖效果较好,应该使尽可能小,也即使无人机在相同时间内获得的尽可能大。因此信息素平均值反映了接入时间间隔的平均值,信息素极大值反映了接入时间间隔的最大值。而是时间长度与覆盖均匀度两方面综合考虑的描述参量,当对于某一地区进行无侧重点的通信覆盖时,一方面希望所有地点接入时间间隔的平均值最短,另一方面希望避免虽平均接入时间间隔较短,但存在某些地点长时间一直未被覆盖的情况。为避免第2种情况的出现而引入,因此与相关,但其数值可以有所不同。

同时在实际情况中,无人机移动的意义包括2方面：其一系收集行经地点的信息素,这一意义在上述参量中得以体现；另一方面,无人机从一点移动至另一点,其空间位置发生的改变,因周围环境存在差异(如周围锚节点密度不同),而对接下来无人机的行动收益产生潜在影响。根据该点的位置与周围环境,2.2节中已引入描述函数,来表现这种行进位置的意义。

表征了发射向导信号点位置的影响,也即地理价值描述量。这一参量的引入是本文提出的方法对基础信息素图方法的拓展,也是将该方法命名为相对位置的信息素图方法的原因。

函数为无人机的等效收益函数,该函数表达式为

是决策的依据,无人机将选择等效收益最大的路径行进。对于信息素价值的增长,也即的增长方式,尝试不同函数形式,以达到最优效果。

3.3 信息素增长及飞出损失

地面各点信息素,简单地可将地面做同样大小的网格分割,认为每个网格内存在一个锚节点,并构建对应各网格的矩阵,以其元素值反映各点信息素,即物理层中假设地面锚节点网格状均匀分布在待覆盖区域内。

假设各点信息素每一单位时间增加一个单位,则信息素值可反映当前点的2次接入时间间隔,而式(8)中出现的、无人机实际使用的信息素价值无需随时间线性增加。实际中可根据具体需要,决定关于的函数形式,这里对比以下2种常用函数形式,即

式中：为一定值,信息素随时间线性增长。根据仿真结果来看,为较好地满足通信覆盖均匀性的要求,需使的增长呈非线性。当然,无需预置这一点。

在待覆盖区外,可增加飞出损失,相应取信息素价值为负即可,这使得无人机能快速返回待覆盖区域。但不宜禁止无人机飞出待覆盖区域,否则在待覆盖区域与外界的交界处,覆盖效果将受到损害。在实际中可调整函数的具体形式,使得边界处收益迅速下降即可达到相同效果,或扩大锚节点布置范围亦可。因仿真检验中该量恒定未变,为一无关变量,在此不多赘述。

3.4 无人机覆盖评价及R 参量

接下来推导无人机通信覆盖中,不存在转弯半径约束下的待覆盖区域内信息素最优结果的上界。以方形的待覆盖区域为例,假设无人机的行进轨迹是最优的,设该状态下待覆盖区域内各点的信息素数值构成一随时间变化的×的矩阵。令与相同,记所有元素中的最大值为,所有元素的平均值为,中最大值为,所有元素平均值为,仿照无人机覆盖对矩阵更新,矩阵则每次均选择信息素最大的点覆盖。第一轮,对所有无人机而言,下一刻中被清零的点数值之和及中最大的个元素之和应满足：

且此时有：

依此进行轮,直到第+1轮执行时,对于中最大的个数值,至少存在一个数值的对应位置在轮内已取得一次,且是轮内第一次取得重复位置。则可知整个待覆盖区域内,当前情况下覆盖的间隔将不大于。且在前轮中,不等式(13)和不等式(14)恒成立(但不等式(12)可能在某些步中不成立)。因每点信息素随时间而线性增加,实际时间的变化(也即轮数的增加)不影响最终与的相对值,而仅受到最开始各点信息素初值的影响。

从初值均为0开始递推推导,并对各、取上界,可导出(在待覆盖区域面积能整除无人机数时。否则最终数值不会稳定在一个值上,而会有微小波动,但不会偏差过大)：

当度量单位取为单个无人机的覆盖面积时,则只需除以无人机数量即得结果,因此式(1)也保持了这一单位的选取。、为考察时间无限长时所得最优覆盖效果的上界,同时也是无转弯限制条件下,无限长时间的平均最优覆盖效果。实际覆盖得到的(,)与(,)相比,可以一定程度上反映该模型的覆盖效果。当然不同情况下,对于与两者的重视程度也可能不同。与在最优情况下,满足：

用来表征上述比值,最优情况下=2。但实际中,受到待覆盖区域内某些点临近边界,特别是位于具有较大转角的边界处时,覆盖该点可能需要飞出待覆盖区等,代价较大,无人机趋向于转弯返回而非将其覆盖。相应的,可以用与2的接近程度来表征覆盖的均匀性。

对于无人机密度较高时的值增长,可如下解释：当无人机密度较高时,由于此时无人机间运动发生直接相互影响的可能性已很高,不能通过忽略这一影响使得无人机间的运动解耦。此时若仍认为无人机之间的运动解耦,而对各无人机进行单独的航迹计算,将可能出现同一地点同时被多个无人机覆盖的情况。考虑极端情况：即此时存在2架无人机,下一刻都可能覆盖当前信息素最大的2点。若考虑无人机之间的直接影响,下一刻信息素最大的2点将被2无人机分别覆盖,在这种情况下也是符合前述理论分析的,因此值仍为2；当认为无人机之间运动解耦,而只考虑其间的间接影响时,2无人机都将覆盖信息素最大的一个点,而遗漏了信息素第2大的点。由于未减小待覆盖区域的面积,因此这一遗漏点对于信息素平均值的提升不明显,但该点下一时刻增加的信息素却全部作用到了极大信息素上(也即上)。故此时应用本文方法将导致值比理想情况下的值大,且无人机密度越大,上面的分析涉及的信息素最大点的数目就可能越多,也越偏离理想情况。一方面,上述值的增大反映了覆盖均匀性下降,另一方面,因无人机重复覆盖同一点而遗漏其他点将使得平均接入时间间隔上升,即总体而言应用本文方法所得到的覆盖效果与最优情况的差距随无人机密度增大而增大。

本文中,考虑到整个待覆盖区域重要程度是相同的,因此最终调整各函数形式,使得尽可能接近2。在变化不明显时,比较(,)与(,)的数值。在本问题的背景下,将待覆盖区域取为50×50的方格(单位为一架无人机可以覆盖的面积),则依据式(15)和式(16),对应覆盖效果描述参量、与无人机数量的关系如表1所示。

表1 描述参量与无人机数量关系Table 1 Relationship between description parameters and UAV quantity

直观发现,同样大小的覆盖区域,无人机数量极少时,信息素最大值与平均值均极大,也即平均而言,待覆盖区域需更长时间才能被收集一次信息；而无人机数量较多时,覆盖效果较好,但此时若继续提升无人机的数量,覆盖效果提升不明显,也即无人机资源被浪费了。同时需考虑到当前模型下无人机稀疏的假设,以保证无人机之间的运动是解耦的。

综合考量,可选择无人机数量为50架用以仿真检验,无人机转弯半径最小取为无人机有效覆盖半径的5倍。

4 仿真实验

依据本文方法进行数据验证,以判断其有效性。如上所述,无人机数量取50,则每时刻各无人机可覆盖面积之和,相较于待覆盖区域面积小1～2个数量级,基本满足稀疏的条件,应用本方法仿真。使用各方法所得仿真结果汇总于表2中,以本文方法得到的无人机均匀性描述参量,确实接近于理想无约束条件下计算出的值,可以从另一方面反映这一无人机密度确实基本满足了稀疏的条件。

表2 各方法仿真结果对比Table 2 Simulation results and data of each model

在效果图图5～图8中,因信息素与上一次被覆盖至今的时间长度成正比,所以图中的纵坐标信息素的大小,可认为反映了当前点至其上一次被无人机覆盖的时间间隔的长短：信息素值越小,则平均而言待覆盖区域内各点被无人机覆盖一次的时间越短；信息素最大值越小,说明待覆盖区域中当前时刻各点距上一次被覆盖的最大时间间隔越小,也即重访时间越短。

为方便对比不同方式的覆盖效果,将各仿真结果及无约束条件下3.4节所得计算结果(即各仿真结果图中的极值参考界、均值参考界)汇总于表2,仿真结果的图片及分析在4.1～4.4节中展示,各方法的对比讨论请参考4.7节。

4.1 本模型数值仿真结果

本模型中信息素价值的函数形式采用：

以保证能较快达到较高水平,其中取1.082,使、α两者在50 个时间单位处连续过渡。选择在此时间单位处连续过度,因其为3.4节计算所得的,在无转弯半径约束条件下的覆盖结果的最大值,也即用以配合在该条件下根据式(15)、式(16)所得数据。同时本模型中使用了2.2节定义的对于地理价值描述的矩阵,来反映待覆盖区域内不同点即使当前信息素值相同,但因其位置不同,所造成的不同点覆盖价值的差异。

因持续覆盖,取不同起末时间进行分析时,求得其平均接入时间间隔及最大接入时间间隔将略有不同。图5～图8中圆点线、菱点线为根据式(15)和式(16)所得无转弯半径约束下的无人机覆盖效果描述参量、,此二值作为衡量的参考基准线,分别称为极值参考界、均值参考界；星点线表示当前时间所有地块信息素的平均值；方点线表示当前时间所有地块的最大信息素。本文方法在两者基本稳定后,信息素平均值、信息素极大值分别在47及159左右波动。

图5 本模型覆盖效果图Fig.5 Covering results of this model

图8 j取正比例函数覆盖效果图Fig.8 Covering result when j is a positive proportional function

4.2 无地理价值数值仿真结果

信息素价值的函数形式仍采取式(18)的形式,但未引入地理价值的情况下,即式(9)中无人机的等效收益函数改为

所得仿真结果见图6。与4.1节对比,其平均信息素与极大信息素分别在50 及170 左右波动。与此相比,4.1节中两代表量47及159反映的平均接入时间间隔与最大接入时间间隔分别提升了6.4%与6.9%。特别是对于信息素全时段最大值,4.1节结果在180左右,而4.2节中接近200。因此对于假设无人机稀疏的本文方法而言,增加矩阵来反映待覆盖区域内不同点因位置不同而产生的差异,对于提升无人机的覆盖效果确有作用。

图6 无地理价值描述覆盖效果图Fig.6 Covering results without description of geographical value

4.3 半随机方向数值仿真结果

图7为无人机在允许的转角范围内随机挑选一方向行进的覆盖仿真结果。其全地块最大信息素在400个时间单位内持续增加,远差于4.1节的效果；其全地块信息素平均值在500个时间单位后仍存在上升趋势,约54。4.1节中本文结果与之相比,平均信息素指标(即平均接入时间间隔,因信息素随接入时间间隔线性增长)提升约15%。

图7 随机取向覆盖效果图Fig.7 Covering results of random orientation

本节信息素最大值在4.1 节结果的2 倍以上,且本节中这一数值波动幅度很大,4.1节中信息素最大值在仿真到200 个时间单位时基本稳定。因此,随着仿真时间的延长,这一比值可能继续增大。事实上,在无人机临近待覆盖区域边界时,本节仍采用了4.1 中的模型,故称半随机方向。否则,若允许无人机飞出该区域,采用完全随机方向,仿真结果显示其极容易飞出当前区域,而导致几乎没有任何覆盖效果。

4.4 j函数形式的影响

图8为存在地理价值描述,函数形式为正比例函数的仿真结果。其所有地块信息素的平均值比4.1节中略低,在40左右,该结果比4.1节中本文方法所得结果略好,但信息素全时段最大值远高于4.1节中对应数据(最大到达220以上,而4.1节在180以下),且表现出较大的波动性。

计算4.1节与4.4节2方法所得值以对比2方法对于待覆盖区域覆盖均匀性,4.1节对应值为3.8,而4.4节对应＞5.5(这里用大于5.5来描述,是因为4.4节中仿真所得信息素最大值波动大,随着仿真时间的进一步延长,可能会有进一步增加)。根据式(17),覆盖最均匀的情况下值为2,可见4.1节的覆盖效果的均匀性更好。

4.5 无人机稀疏性

本文提出的相对位置的信息素图方法的使用,建立在无人机数量相对于待覆盖区域面积较小的情况下,也即无人机较稀疏的情况下。图9展示了在待覆盖区域为50×50的方格这一情况下,不同无人机数量的全时段极大信息素这一参量的结果对比,图10展示了不同无人机数量对应的值,3.4节已计算出理论最优的无人机均匀性描述参量为2。

图9 不同无人机数量的极大信息素值对比Fig.9 Comparison of maximum pheromone values of different UAV numbers

图10 不同无人机数量情况下R 值对比Fig.10 Comparison of R values under different UAV numbers

图9反映出：当无人机密度较低时,极大信息素较大,或者说全部时段、全部区域内的最大重访时间较长,覆盖效果较差；当无人机密度较高时,覆盖效果较好,但此时随着无人机数量的继续增加,效果提升却并不明显,这与3.4节中的分析结果是相符的。图10 反映出：当无人机密度较低时,其值基本恒定,在3.7左右；而当无人机密度较大时,值将增长。对于本文所选取的待覆盖区域而言,可认为值小于4时基本了满足无人机稀疏的条件。

由此可知,当待覆盖区域面积较无人机可覆盖面积大1个数量级以上时(更可靠地需＞2个数量级左右,1个数量级已较勉强),基本可满足无人机稀疏的条件,应用本文方法能够得到好的结果。若不满足上述条件,结合图9 与表1,以250架无人机分析,不考虑转弯半径限制的理论信息素最大值为10,而实际覆盖效果为50,与理论分析差别较大,此仿真结果也证明,当无人机密度较大时,本文方法将有较大的局限。

当不满足无人机密度较小的条件时,有以下几种可能的方式来改进本文中的方法：一是将无人机之间的直接影响考虑进来,此时需增加无人机之间的信号交流,以保证在小范围内无人机之间的决策是相互影响的,可通过增加无人机之间的排斥等因素来描述无人机之间的影响；另一种可能的方法是重新分析待覆盖区域,由于此时无人机密度较高,同时分析各无人机的运动情况较困难,可对待覆盖区域进行计算,得出少量无人机对当前地块进行覆盖的方法,其余无人机沿着同样的轨迹,交错一时间间隔进行覆盖。对于需要计算的少量无人机,则转化为了密度较低的情况。此时并非所有无人机都进行决策,而仅有少量无人机之间进行决策,其他无人机则跟随其运行。

4.6 算法对比分析

本文中提出的方法在持续性通信覆盖应用外,对于单次全覆盖的路径问题也有一定作用。在边界不规则或有障碍物时,基于GBNN 算法及受生物启发的神经网络算法的覆盖路径规划方法效果图(局部)见图11。其中右下圈内为死锁位置,受生物启发的神经网络算法在死锁处会停留较长时间,而基于GBNN 算法则能立刻脱离死锁地点。

图11 神经网络、GBNN 算法UAV 脱离死锁地点轨迹Fig.11 Paths of UAV escaping from deadlock using Neural Network and GBNN-based algorithm

本文中基于信息素图的方法,因其行经地点的信息素随探测时间点至今的时间间隔变长而增大,因此在图中最右下角的覆盖死锁处,探测器(这里不单指无人机)将沿最下方行进到最左侧,再向上运动,回到开始箭头所指处,继而可以探测右方未探测区域,即图12中自右下方箭头标记,沿边界运行至左上方未覆盖区域处。

图12 本文方法UAV 脱离死锁地点轨迹Fig.12 Paths of UAV escaping from deadlock using present method

在效果上,本文的方法可通过简单地计算即使得探测器立刻脱离死锁地点向外移动,协助受生物启发的神经网络算法快速脱离死锁。但其移动至未探测区域所需的距离比GBNN 算法的略长,因此本文方法更适合无障碍物或边界比较规则的地区进行持续覆盖,在障碍较多或边界不规则性很强时,亦可结合GBNN 算法提升覆盖效果。对于受生物启发的神经网络算法,本文方法因计算简便,也可以作为其脱离死锁的一个备选方案。

对于本文方法脱离死锁,有以下几种可能的方法以缩短路径耗费：一是改变方法间转换的判断依据,图12对应的转换依据,是当得出的行走目标与当前点相同时,开始应用本文方法；当下一目标未被覆盖过时,重新回到受生物启发的神经网络算法。若修改为：行走目标与当前点不同时,回到受生物启发的神经网络算法,则与GBNN 算法得到的路径相比,所得路径仅在脱离死锁的开始点略有不同,总的路径耗费基本一致。另一种可能的方法是增加考虑的“步数”,采用分支界限等方法得到较短的路径,这里信息素图将为选取最初的路径提供方向。因实际未必需计算得到最短的结果,可得到一个较短的路径即返回,则能达到减小计算耗费时间的效果。同时,增加辅助的Dijkstra图,配合动态规划的方法得到最短路径也是可行的,在这一方法中,信息素图则只作为判断是否已经覆盖过的依据。上述3种方法中,改变方法转换判断依据效果比直接应用本文方法好,且计算量较小,但不一定能够得到最短的路径；采用分支界限或借助Dijkstra图都能够得到最短路径,但计算量大,耗费时间长。实际应用中可以对比计算耗费与探索耗费,决定选择的方法：若待覆盖区域较大,计算难度将迅速上升,此时改变方法转换判断依据的效果较好；若待覆盖区域较小,则可选择采用分支界限或借助Dijkstra图来减小探测器移动的消耗。

4.7 仿真结果讨论

从仿真结果来看,对比4种方法,本文方法的极大信息素值波动最小,稳定性最好。为进一步讨论各仿真结果,图13中4.1～4.4折线对应于4.1～4.4节所描述的方法,展示了本文方法与随机取向、简单临近信息素驱动等方法的覆盖效果对比。横坐标“平均值”等表示该方法覆盖所得各时刻信息素平均值等各参量；纵坐标“相对比值”是以本文方法4.1节所得结果为基准,得出的不同方法的各参量与本文方法所得参量比值,比值越低可以认为覆盖效果越好。其中,关于随机取向方法的结果因与其他方法差距较大,为对比清晰,超过上限(相对4.1节结果比值超过1.5倍)的数据已取上限进行绘制。

图13 各方法覆盖效果数据对比Fig.13 Comparison of values of different methods.

比较4.1节及4.2节对应折线以说明引入矩阵的影响：一方面,引入矩阵描述了不同地点地理价值的差异,降低了信息素平均值与极大值(即接入时间间隔减小)；但另一方面,引入矩阵使得待覆盖区域内不同点的覆盖价值——即使其当前信息素一样多——对于无人机而言也不再等价,可能在一定程度上导致不同点覆盖的均匀性恶化。观察覆盖均匀性描述参量,图12中2方法所得参量在保留两位有效数字的情况下大致都在3.8附近,无明显差别。说明在这种情况下,使用矩阵在提高平均覆盖效果的同时,没有造成覆盖均匀性的恶化,故对于本问题而言,引入矩阵是有益无害的。

比较4.1节及4.4节对应折线以说明不同函数形式的影响：对比两折线数据,4.4节的信息素平均值比4.1节略低,但极大值、极大均值以及值都远高于4.1节的结果,这反映出4.4节的覆盖均匀性差,不能保证待覆盖区域内全部点均获得良好通信覆盖。从模型假设而言,因其无人机的均匀性差,则即使在无人机平均密度较低的情况下,3.1节中推导某一无人机与其他无人机覆盖范围不发生交叠的概率仍可能迅速下降,也即无人机之间有较大的影响,解耦假设不成立。故不论从覆盖均匀性,或是方法的合理性上,取的函数形式如4.1节都是比4.4节更为优越的。

4.6节的仿真结果也反映在待覆盖区域边界极不规则的情况下,限制无人机转弯半径可能导致无人机在允许范围内不存在合理解,此时无人机能耗应作为次要考虑因素,故本文方法不适用于这类问题。

此外,关于模型中无人机飞行高度的问题讨论如下：模型假设无人机在一恒定高度上运行,当引入无人机飞行高度这一参量,考虑无人机运动中爬升率等因素时,需重新计算其耗能。不同爬升率下,无人机转弯半径的约束也将有所不同。

本文方法需在无人机高度近似不变的情况下使用,实际中减少无人机的爬升与下降也有利于减小无人机能耗,提升无人机续航能力。但增加无人机爬升速率因素,将可能提高其位于待覆盖区域边界处的行动效率,在无人机密度较大时进行无人机间的碰撞规避等也有其意义。这种情况下,无人机所能覆盖的范围与其高度相关,若无人机高度可变,则矩阵计算时所需的信号自然传播的有效接收范围随之变化。但物理层获得矩阵也是通过接收到的信号强度得出的(如2.2节所述),将检测信号强度的主体从地面锚节点变为无人机,可方便地获取新矩阵。

5 结 论

1)对于降低计算量,克服无人机异步问题,根据多无人机通信覆盖中无人机较为稀疏的假设,分析了无人机间的运动解耦,保证了利用小范围信息素图进行无人机航迹规划的合理性,并提出了用于检验当前情况是否满足无人机密度稀疏条件的参量。

2)提出了地理价值的描述函数,改进了简单利用临近信息素图驱动的方法,除单纯覆盖收益外增加考虑了无人机位置改变带来的收益。有利于在不增加计算开支的前提下提高覆盖效果,同时有利于达到整个区域的均匀覆盖。

3)增加地面锚节点并约束无人机的信号发送,保证了无人机的安全性；信息素在地面存储的设计,有利于节省无人机存储空间。