无人机自组网中基于蚁群优化的多态感知路由算法

孙明杰,周 林,于云龙,顾金玲

(1.空军工程大学防空反导学院,陕西 西安 710051;2.中国人民解放军93861部队,陕西 咸阳713800;3.中国人民解放军32272部队,甘肃 兰州 730060)

0 引 言

当前,无人机的应用越来越广泛,已涵盖到民用和军用多个领域。而且无人机已成为现代战争中不可缺少的重要组成部分,其主要用于战场侦察监视、情报搜集、通信中继、快速打击等任务。现代战场具有对抗程度高、覆盖范围广、信息量大等特点,单架无人机已无法满足现代战争的需要,多无人机协同作战成为当今研究热点。多无人机协同完成任务时,通常组成飞行编队。

多无人机编队协作执行任务时,可通过无人机自组织网络来交换彼此的任务规划、飞行状态和情报信息等数据,以提高无人机编队对实时态势的感知,实现大于多架无人机独立执行任务的整体效能。无人机自组织网络属于航空自组网,而航空自组网又是无线自组织网络(mobile AdHoc network,MANET)在航空领域的典型应用。该网络能够保证无人机在战场环境下,快速地入网和退网,同时,为了提高网络的鲁棒性,各架无人机在通信体系中的地位是平等的。在无人机自组织网络中,将每架无人机作为节点处理。

然而,无人机自组织网络与移动自组织网络相比,具有节点移动性更强、网络拓扑结构变化更快、应用环境复杂、数据交互频繁等特点。这些特点为无人机自组织网络中路由算法的设计带来了很大的挑战。传统的路由算法在这种环境下不能满足多无人机协同执行任务的需求,而其他基于服务质量(quality of service,QoS)保证的路由算法又有各自特定的应用场合,因此需要设计出适用于无人机自组织网络的路由算法,以满足复杂通信环境下无人机协同执行任务的要求。

对于无人机自组网中的路由算法,本文认为,应满足如下要求:① 数据传输延时小;② 丢包率低;③ 可靠性高;④ 无拥塞现象出现;⑤ 路由开销小;⑥ 可针对编队变化,随时调整路由算法,以保证网络性能不下降。传统的路由算法无法同时满足上述要求。本文总结出了设计该路由算法时需要注意的3个关键点:路径长度、路径拥塞度和路径稳定性。需要将这3者综合考虑来设计无人机自组网中的路由算法。同时,在无人机自组网中,认为每个节点能量充足,能量不是影响路由性能的因素。

近年来,航空自组织网络的路由协议已呈现多样化趋势。按照路由信息的更新机制,可将这些路由协议划分为3大类:① 表驱动(主动)路由协议,如DSDV[1]、FSR[2]、STAR[3]、OLSR[4]、WRP[5]、TBRPF[6]等。在主动路由协议中,每一个节点都要维护一个或多个路由表,表中包含了该节点到网络中所有其他节点一致的、最新的路由信息。为了维护这样的路由表,每个节点需要周期性地向整个网络广播路由更新信息,以便时刻维护并记忆全网的拓扑结构与节点路由信息。表驱动路由协议的优点主要是能够很好地保证网络传输低延时性和服务质量,但是,使用该协议需要较高的代价,数量庞大的路由控制包会大大地增加路由开销,因此也会导致节点的拥塞度增加。② 按需(被动)路由协议,如AODV[7]、DSR[8]、TORA[9]、SSR[10]等。在被动路由协议中,当源节点有通信需求时,才根据事先设定的算法搜索路由,由于不需要周期性地广播路由更新信息,所以其路由开销小,节省了网络资源,但是当源节点有通信需求时,若没有到达目的节点的路由,则需要重新搜索创建,数据传输也会因此被迫延时。③ 混合路由协议,如ZRP[11]。该路由协议将上述两种协议结合起来,但依然无法解决主动路由协议路由开销大的问题。

蚁群优化算法是由意大利学者Dorigo在1992年提出的,该算法是一种启发式算法,主要通过模拟自然界蚂蚁觅食行为来实现[12]。随着蚁群算法的发展,越来越多地被应用于移动自组织网络的路由问题中。根据文献[13],可以得到基于蚁群算法路由协议的分类,与航空自组网划分相同,主要分为3大类。本文就其中具有代表性的且与本文相关的路由协议进行评述。

对于Ant-DSR算法[14],单一传播的蚂蚁用于建立和更新路由,余下的两种蚂蚁则用于探测邻居节点。该方法属于主动型路由算法,可以使数据传输延时变小,但是依然无法避免路由开销的增加,以至于出现节点拥塞现象。

ADSR算法[15]在路由发现阶段使用了前向蚂蚁与后向蚂蚁,属于被动型路由算法。但ADSR算法没有评价路径的可靠性,在节点移动性较强的无人机自组网中,极易出现链路断路现象,从而使得数据包成功传输率降低。

HOPNET算法[16]与HRAZHLS算法[17]均属于混合型路由算法,且均包含4种类型的蚂蚁。但是HOPNET算法只适用于小型网络,对大型网络的扩展性不好。HRAZHLS算法的路由开销较大。

综上所述,无论是主动路由协议、被动路由协议还是混合路由协议,无论是否与蚁群算法相结合,都无法满足无人机自组织网络对路由算法提出的要求。同时,上述路由算法都无法有效地避免移动自组网中常见的问题,如节点拥塞、链路断路等,上述问题的发生会使得丢包率大大增加。

对于传输路径稳定性的判断,首先要对其中包含的链路的稳定性进行判断。目前,针对链路稳定性的判断方法主要有两种,但都存在不足。第一,基于距离的链路稳定性判断[18-19]。认为两节点距离越近越稳定,可通过全球定位系统(global positioning system,GPS)定位或者接收Hello消息功率来判断两点距离。该种方法判断形式单一,不能对节点建立长效监督机制。而且,采用GPS定位进行链路稳定性判断,容易引入定位误差和外界GPS信号干扰,使得判断失败。第二,基于节点移动性的链路稳定性判断。一种是通过节点的位置信息[20]计算节点的运动方向、速度,进而计算链路的稳定度。但是容易引入GPS误差。另一种是基于概率方法的链路稳定性估计,文献[21]采用的概率稳定性估计方法较复杂,计算开销大;文献[22]以邻居节点数量的变化来估计当前节点的稳定度,计算不准确,误差大;文献[23]虽然对链路稳定度的计算较为简单,但是由其筛选出的稳定性高的链路可能处于节点通信范围的边缘,易造成该链路的中断。

近年来,多篇文献针对网络拥塞问题提出了多种解决方案,但也存在一定不足。文献[24]根据MAC层接口队列长度对缓冲区总长度的比值来表征网络负载,避免将重负载节点作为中间节点而导致网络拥塞,但测量形式单一。文献[25]从缓冲占有量、信道负载程度、掉包率3个方面来评估节点的拥塞度,但其将低能耗放在了第一位,造成了拥塞度测量结果并不准确。

上述文献仅为单方面考虑路径稳定性或者是路径拥塞度,并没有对二者进行联合的判断。文献[26]对路径稳定性和路径拥塞度同时进行判断,有效地避免了移动自组网中的常见问题,但是就其方法来看,改进的余地还很大。

因此,本文重新设计了无人机自组网中的路由算法,将DSR算法与蚁群算法相结合,并做出诸多改进,提出了一种高效的路由算法——APAR算法,使之满足数据传输延时低、数据成功传输率高、路由开销小的要求,并且能够避免链路断路、网络拥塞等常见问题,同时能够根据编队的变化调整路由算法,最终,克服了传统路由算法存在的诸多不足。

1 控制数据包定义

在移动AdHoc网络中,主要包含两类路由控制包,路由请求控制包(routing request control packet,RREQ)和路由应答控制包(routing reply control packet,RREP)。RREQ包括目的节点地址、目的节点序列号、广播序列号、源节点地址、源节点序列号、上一跳地址和跳数等信息。RREP包括源节点地址、目的节点地址、目的节点序列号、跳数和生存时间等信息。本文将蚁群算法与动态源路由算法相结合,并做了诸多改进,因此需要对RREQ和RREP的数据结构进行修改,使之满足本文所提新路由算法。修改后的两类路由控制包分别称为RREQ.Ant和RREP.Ant,在本文中,这两类控制包也被称为前向蚂蚁、后向蚂蚁。其修改后的数据结构如图1所示。

图1 控制数据包格式Fig.1 Format of control data packet

源节点和目的节点的地址为MAC地址而不是IP地址,主要为了防止节点与网络断开链接而分配不到IP地址。HC代表了RREQ.Ant从源节点到目的节点所经过中间节点的个数,在RREQ.Ant中,HC的初始值为0。在RREP.Ant中,HC为一恒定值。RC与RS分别代表了从源节点到目的节点路径的拥塞度和稳定度,a值仅在RREP.Ant中有效,主要用于确定后向蚂蚁的转发路径。Type代表路由控制包的类型,当Type=1时,路由控制包为RREQ.Ant;当Type=0时,路由控制包为RREP.Ant。最后一部分用于存储在路由发现过程中,RREQ.Ant从源节点到目的节点所经过的中间节点的地址。

2 路径稳定性感知

在无人机自组织网中,由于无人机的移动速度较快且每架无人机的任务分配不同,所以其网络拓扑变化较快,链路中断的现象十分普遍。因此,为了避免链路中断造成的网络性能下降,本文提出了一种链路稳定性的评价方法,该方法主要通过接收Hello消息的信号强度并对其建立长效的监督机制,不但能够综合的评判某一链路的稳定性,还能预测并提前删除可能中断的链路,克服了之前方法的不足,从而提高了网络性能。同时,为了避免GPS定位误差或者外界干扰GPS信号对本文方法的影响,本文不使用节点的位置信息。

在无人机编队对战场环境的侦察过程中,由于任务不同的需要,编队往往由不同种类的无人机构成,所以各个平台的速度、天线增益、最大发射功率不同。因此,本文对Hello消息的数据包进行改进,最终包括:源节点地址、节点拥塞度、天线增益、传输功率、移动速度。

根据自由空间衰减模型[27],当前节点接收到距离d处的邻居节点i的Hello消息的信号强度Pri为

(1)

式中：λ为无线电波的波长；Gr是接收天线的增益；Gt是发射天线的增益；Pt为邻居节点Hello消息发射功率。

本文假设天线的覆盖范围为一个半径为R的圆形区域。由文献[28]可知,在半径为R的圆形区域内,两个移动节点之间的平均距离为0.905 4R。因此,本文将接收到邻居节点Hello消息的信号强度的临界值定义为

(2)

当前节点可以根据本节点已知信息和邻居节点Hello消息中包含的信息计算出接收信号强度的临界值,并与实测的信号强度进行比较,对链路的稳定性进行初次的评判。过程如下:

(3)

LSi值的大小代表了当前时刻第i条链路的稳定度,LSi越大代表该链路稳定性越好,但不超过1。当LSi为0时,该链路被认定为不稳定的链路,并从存储区删除。为了保持LSi值的实时性,需要不断对其进行更新,更新的时间间隔(Hello消息的广播周期)t为

(4)

式中：V1代表当前节点的最大移动速度；V2代表邻居节点的最大移动速度。由于邻居节点的类型不同,所以对应的t也是不同的。采用此时间间隔来更新LSi值,能够保证在时间t内,存储区中的邻居节点都未移出其通信范围,有效地利用了节点的存储空间,为路由发现阶段提供了可靠地选择。有效地解决了固定Hello消息周期存在的缺陷。

上述过程仅对某一时刻链路的稳定性进行了评价,并没有建立长效机制,对链路的稳定度进行综合的评价。因此,本文根据不同时刻Hello消息信号强度的变化,对邻居节点的移动性进行估计,将当前节点存储区内移动性强的邻居节点删除。

根据文献[29],可以得到比安内梅-切比雪夫不等式：

(5)

式中：X为离散变量;E(X)为X的数学期望;var(X)为X的方差；ε为任意正数。

当var(X)=0时,有P{|X-E(X)|<ε}=1,说明了变量X与其期望值相等,同时也说明了变量X的方差越小,变量X越接近其期望,变量X的变化量越小。

根据变量X的多次测量值,可以得到其方差var(X)为

(6)

将LSi不同时刻的值作为变量X的多次测量值,并代入式(6)中,得

(7)

通过式(7),可以得到某一邻居节点的移动性,var(LSi)越小,代表该邻居节点运动越不明显,第i条链路也就越稳定。此方法仅对当前节点存储区内的邻居节点移动性进行判断。

综上所述,具体的链路稳定性判断过程为:每个节点都对进入本节点0.905 4R范围内邻居节点进行编号,并将其写入存储区,而且根据式(3),计算出每条链路当前时刻的稳定度LSi。当某一链路的LSi值为0时,存储区将删除该链路。当某一链路连续得到两个不为0的LSi时,便对其节点移动性进行判断,只要LSi不为0,就一直对该链路的节点移动性进行判断。当某一链路的var(LSi)累计3次超过预先设定的临界值varthreshold时,说明了此邻居节点移动性强,同时也说明了该链路不稳定,因此将该链路从当前节点的存储区中删除。同时,为了节省存储空间,本文定义节点存储区内只存储最近5个时刻的LSi值。

在路由发现阶段,通常需要选出最稳定的路由来传输数据,因此需要对当前一跳链路的稳定度进行综合量化。本文提出了一种当前一跳链路稳定性的综合量化方法,如下：

(8)

式中：CLSi(tm)为第i条链路tm时刻的综合稳定度;LSi(tm)为tm时刻的LSi值;varm(LSi)为tm时刻的var(LSi)值。当该时刻,某一邻居节点第一次进入当前节点的存储区时,var(LSi)值为空,在此方法中,令该时刻的varm(LSi)=1。并且,CLSi(tm)值越大,代表该链路的综合稳定性越高。

在本文中,每一个路由控制包都包含一个RS值,其大小由RREQ在路由发现过程计算得到。源节点发出一只前向蚂蚁,并令RS的初始值为1。当该前向蚂蚁在网络中移动时,每经过一个中间节点,就将该中间节点与上一跳节点之间的链路稳定度CLSi与当前RS值相乘,得到一个新的RS值。当该前向蚂蚁到达目的节点时,便可以得到源节点到目的节点之间路径的稳定度RS:

(9)

3 路径拥塞度感知

多架无人机以编队形式对热点地区侦察的过程中,需要共享和回传大量的目标数据。如果采用传统的路由算法来构建传输数据的路由,那么极易造成网络拥塞现象。在无人机自组网中,如果出现网络拥塞,会使网络的数据传输性能下降,例如掉包率增加、平均端到端延时增大等。

本文提出了一种路径拥塞度测量方法,主要根据缓冲占有量、信道负载程度来测量节点的拥塞度,并采用了非线性化处理手段,结合路由发现过程使得路径拥塞度测量结果更符合实际。

3.1 缓冲占有量

节点Ni的MAC层接口队列长度与缓冲区总长度的比值代表了当前节点缓冲占有量BOi,表示如下:

(10)

式中：Qi为节点Ni的MAC层接口队列长度;Qmax为当前节点缓冲区的总长度,本文假设所有节点缓冲区的总长度相同。

节点Ni周期性地对BOi值进行测量,便可以得到一定时间内缓冲平均占有量Ave_BOi(t)。本文假设,在t时间内共进行了N次测量,则

(11)

式中：BOi(j)为节点Ni对BOi值进行的第j次的测量结果。

通常情况下,MAC层接口队列长度占缓冲区总长度65%以上就认定该节点缓冲占有量大[30]。因此,为使其符合实际需要，本文对Ave_BOi(t)进行非线性化处理：

NBOi=1-(1-Ave_BOi(t))5

(12)

式中：NBOi为节点Ni的非线性化缓冲平均占有量。

3.2 信道负载程度

根据文献[26],通过一段时间内周期地对信道进行采样,便可以得到信道负载CLi，可表示为

(13)

式中：Nbusy表示该段时间内信道处于繁忙状态的次数;Nidle表示该段时间内信道处于空闲状态的次数。

信道采样过程如图2所示。

图2 信道采样过程Fig.2 Sampling process of channel

随着信道负载CLi的增加,网络中的拥塞现象会越来越严重。本文对CLi值进行了多次连续测量,得到了时间t内信道的平均负载:

(14)

式中：CLi(j)为第j次CLi值的测量结果;N为时间t内的测量次数。通常情况下,时间t取30 s,每次的测量时间为5～10 s。

类似于缓冲占有量,信道负载程度依然要进行非线性化处理。本文认为,Ave_CLi(t)大于等于0.7就代表该信道负载程度高,因此对其进行如下非线性化处理：

NCLi=1-(1-Ave_CLi(t))4

(15)

为了综合评价某一节点的拥塞度,定义如下等式:

(16)

CNCi(t)=νMi(t-1)+(1-ν)Mi(t)

(17)

式中：Mi(t)为当前时间窗节点的拥塞度；ν和(1-ν)为赋予前一时间窗和当前时间窗节点拥塞度的权重因子；CNCi(t)为该节点拥塞度的综合值。

每一个路由控制包都含有一个RC值,由路由发现过程计算得到。源节点发出一只前向蚂蚁,该蚂蚁负责建立从源节点到目的节点的路由,当前向蚂蚁到达目的节点时,其所经过的所有节点的节点拥塞度CNCi(t)的最大值将成为该路径的拥塞度RC,表示为

(18)

4 基于蚁群优化的多态感知路由算法

4.1 路由发现过程

由于执行的任务不同,无人机存在多种形式的编队,本文主要关注其编队中无人机的密度对无人机自组网网络路由的影响。因此,本文根据其网络中节点密度提出了两种不同的路由发现算法。

根据文献[31],本文认为平均网络分区(average network partitioning,ANP)小于等于3%时,无人机编队为密集编队;否则为稀疏编队。路由发现过程对这两种情况处理的不同点主要体现在RREQ.Ant的转发方法上,在其他方面方法均相同。

4.1.1 路由请求控制包传递过程

(1)稀疏编队

当某一无人机获取到目标信息,并需要将该信息共享至其他无人机时,当前节点首先对本节点缓冲区内已经存在的路由进行比对,如果存在能够完成此次信息传输的路由,那么根据路由选择过程,选取最优的路径来传输该目标信息;如果当前节点找不到向目的节点传输目标信息的路由,那么将从当前节点启动路由发现过程,向其邻居节点中所有稳定的节点发出前向蚂蚁。与文献[32]提出的洪泛方法相比,本文提出的方法能够有效地避免洪泛广播消息的无方向性、盲目性,提高了所发现路由的可靠性。

对于中间节点,如果接收到上一节点转发来的前向蚂蚁,首先对其数据包内的跳数HC值进行判断,由于存储空间的限制,HC的最大值为127,如果发现HC为最大值,那么该中间节点将销毁该数据包,不再转发,以免引起路由长度测量的误差。

其次,针对无人机自组网中可能出现的路由环路问题,本文提出了一种预防机制,能够避免路由环路对网络性能产生的不利影响。当中间节点在RREQ.Ant的中间节点存储区(INA)中发现本节点的地址时,就认为该路由发现过程已进入环路状态,本文首先对RREQ.Ant进行修改,将进入环路的节点删除,随后从当前中间节点的邻居节点中筛选出不会进入环路的稳定节点作为下一跳节点,并向这些节点转发RREQ.Ant。

最后,如果未发生路由环路问题,当前节点会查找本节点缓冲区内是否存在能够到达目的节点的路由,若存在,则需要对前向蚂蚁中的相关信息进行更新(例如跳数、稳定度、拥塞度等),并启动路由应答过程,该方法能够降低端到端延时和路由开销;如果不存在可用路由,当前节点会更新前向蚂蚁,并且转发至其稳定的邻居节点。

对于目的节点,如果接收到RREQ.Ant,需要对其进行更新并启动路由应答过程。

(2)密集编队

对于密集编队,若其路由算法与稀疏编队相同,由于节点密度的增加,RREQ.Ant的转发数量也大大增加,极易造成广播风暴,致使网络性能急剧下降,因此本文对密集编队路由算法的改动有两处。其一是对Hello消息的改动,在密集编队中,Hello消息在原有基础上附加了当前节点的稳定邻居节点列表;其二是对前向蚂蚁转发方法的改动,本文受文献[31]的启发,提出了一种概率转发方法,能够减少RREQ.Ant的转发数量,降低广播风暴发生的可能性,同时也保证了所发现路径的冗余性,在战场环境中具有抗击毁性。

该概率转发方法仅适用于中间节点,对于源节点,依然采用稀疏编队的前向蚂蚁转发方法,以保证发现路径的冗余。当某一中间节点D接收到上一节点F发来的前向蚂蚁时,首先对F节点Hello消息中的节点列表与本节点的作比较,计算出前向蚂蚁的转发概率p,节点D以概率p将更新过的前向蚂蚁转发至稳定的邻居节点。转发概率计算如下:

(19)

式中：m为两节点稳定邻居节点中公共部分的数量;n为属于节点F但不属于节点D的稳定邻居节点的数量;q为属于节点D但不属于节点F的稳定邻居节点的数量。

虽然对Hello消息的改动增加了数据包对无线媒介的占用时间,但是概率转发机制能够大大地降低所转发前向蚂蚁的数量,降低了路由开销,而且能够保证所发现路径的可靠性,因此利大于弊。

4.1.2 路由应答控制包传递过程

当目的节点接收到RREQ.Ant时,需要将其数据包类型转换为RREP.Ant,并沿原路径返回至源节点。对于中间节点,如果接收到RREP.Ant,那么该节点只需要按路径转发即可;如果中间节点接收到RREQ.Ant并找到了到达目的节点的路由,则需要将数据包变为RREP.Ant,同样将其按原路径返回源节点。当源节点接收到RREP.Ant时,需要启动路由选择过程,选出最优路径来传输目标数据。

4.1.3 路由选择

源节点每接收到一个后向蚂蚁,都会从中提取出HC值、RC值和RS值,用来计算该路径的信息素,计算方法如下:

(20)

源节点会对每一条路径的信息素进行计算,并选择信息素最高的路径来传输目标信息。用于传输信息的路径通常有跳数小、稳定性高、拥塞度低等特点。源节点针对一个目的节点通常会保留多条可用路径,以防最优路径遭到破坏。同时,为了降低平均端到端延时,本文定义了如下机制:当源节点接收到第一个RREP.Ant时,便开始沿着该后向蚂蚁提供的路径传输目标信息;如果接收到第二个RREP.Ant,源节点会选择信息素最高的路径来传输信息,以此类推,直到最后一个RREP.Ant。由于本文引入了信息素挥发机制,所以每接收到一个后向蚂蚁,需要对所有已知路径的信息素进行重新选择,不能沿用之前的信息素值。

4.1.4 目标信息传递过程

在传输目标信息之前,需要将已选择路径的中间节点地址写入到目标信息中,使得目标信息能够沿着该路径到达目的节点。当目的节点接收到目标信息时,会立即发送ACK消息至源节点,表明此次信息传输成功。如果源节点在一定时间内未接收到ACK消息,那么会选用备用路径来传输目标信息,若没有路径可以使用,则需要重新启动路由发现过程。

4.2 路由维护过程

在无人机自组织网络中,节点的可移动性、网络拓扑结构的动态变化都使得路由维护显得十分重要。路由断路和路由死循环是路由维护中必须解决的两个关键问题。

根据蚁群算法可知,当蚂蚁寻找食物时,会经过不同的路径到达食物源。在返回蚁穴的过程中,蚂蚁会留下信息素,信息素值的大小代表了该路径的可用程度。当某一路径不断地存在蚂蚁返回时,会增加该路径的信息素值;当食物消耗殆尽,不再有蚂蚁返回时,该路径的信息素由于挥发会逐渐减弱,直至消失。

受蚂蚁觅食以及文献[33]的启发,本文对信息素的挥发机制[34-35]进行了改进,使之满足本文算法的需要。当前时刻某一路径的信息素值表示如下:

(21)

式中：Ph[k]t为t时刻某一路径的信息素值;α为衰减系数,用于改变信息素的衰减幅度,可以根据实际应用随时调整该系数;vmax为所有节点移动的最大速度;n为源节点接收到ACK消息的数量。

当某一路径接收到后向蚂蚁时,路由维护过程随之启动。在该过程,后向蚂蚁具有和ACK消息一样的作用,因此在t=0时,n=1。当该路径正常的传输数据时,其信息素值会不断“增加”,当然,这种“增加”是相对于无数据传输时信息素值变化的,总体来看,正常传输数据的路径,其信息素水平也会下降,但下降速度较慢;当该路径未被使用或者已经出现断路时,其信息素水平会迅速下降,当低于某一门限值β时,该路径失效被移出源节点存储区。同时,节点的最大移动速度也是影响信息素水平的重要因素,节点的移动速度越大,造成链路中断的可能性就增加,因此信息素的衰减程度与节点的移动速度成正相关。

在路由维护部分,α和β的大小可根据实际情况随时调整,以便于满足不同的要求。通常来说,被选定用于传输数据路径的α值要比未被使用路径的α值高,这是因为,选出的用于传输数据的路径信息素水平是最高的,如果该路径因某一节点遭击毁而出现断路,那么其信息素水平会迅速下降,且下降速度与其他未使用路径的信息素下降速度相同(如果所有路径的α值相同),当该路径的信息素值小于β时,才认为路径失效,但此时所有的备用路径早已被认定是失效的了,重新启动路由发现过程,增加了路由开销。因此,本文将路径信息素的衰减程度区分开来,对于正在使用的路径,其信息素衰减程度大,一旦路径遭到破坏,可使其信息素迅速下降并失效;备用路径由于其信息素衰减程度小,可在主路径失效时迅速切换至备用路径,而不用启动路由发现过程,降低了路由开销。

对于路由循环问题,在路由发现阶段就已经解决了。前向蚂蚁所经过的中间节点都会将自己的地址加入到蚂蚁信息当中,蚂蚁对此都有记录并且只经过从未到达的节点。因此,算法自身就很有效地避免了循环问题。

5 仿真分析结果

在仿真环境下,本文将APAR算法与部分主流算法进行了性能比较,这些算法包括:DSR算法[8]、Ant-DSR算法[14]、HOPNET算法[16]。其中,运用的仿真软件为NS-2(Network Simulator v2.34)。由于本文针对无人机的稀疏编队与密集编队提出了两种不同的路由策略,所以需要分成两种情况来测试其性能,这两种情况除了节点数量不同,其他仿真参数均相同。假设无人机为低空低速小型无人机,其通信距离较近,但由于执行任务的多样性,所以该无人机自组网中的节点移动性较强,具体仿真参数如表1所示。仿真参数的选择主要参考了文献[4,8,16]。为了真实地模拟战场环境,体现出本文提出的无人机自组网路由算法——APAR算法在战时的优异性能。仿真过程中选择随机地关闭一些节点,以此来表示无人机自组网在战时遭到一定程度破坏,某些无人机被击毁。同时,为了减少随机误差,所有实验结果为30次实验的平均值。仿真结果如图3～图8所示。

表1 仿真参数Table 1 Simulation parameter

图3 稀疏编队下数据包成功传输率比较图Fig.3 Comparison diagram of data packet delivery ratio in sparse formation

图4 密集编队下数据包成功传输率比较图Fig.4 Comparison diagram of data packet delivery ratio in concentrated formation

图3和图4给出了无人机自组织网络在无人机稀疏编队和密集编队的情况下,分别采用DSR、Ant-DSR、HOPNET、APAR算法在数据包成功传输率性能上的比较。可以清楚地看到,无论是稀疏编队还是密集编队,本文提出的APAR算法与之前的3种算法相比,数据包成功传输率有较大幅度的提升。具体来说,在稀疏编队下,APAR算法比HOPNET、Ant-DSR、DSR算法将数据包成功传输率分别提高了30%、60%、130%以上;在密集编队下,本文算法比上述3种算法分别提高了40%、90%、200%以上。由于在无人机密集编队中,节点与节点之间链接的可能性更大,所以APAR算法在密集编队中有更高的数据包成功传输率。

图5和图6给出了无人机自组织网络在无人机稀疏编队和密集编队的情况下,采用上述4种算法在平均端到端延时性能上的比较。可以看出,APAR算法无论在何种情况下,与其他3种算法相比,都具有较低的端到端延时。该性能的取得主要得益于本算法的路由发现过程和路由维护过程。

图5 稀疏编队下平均端到端延时比较图Fig.5 Comparison diagram of average end to end delay in sparse formation

图6 密集编队下平均端到端延时比较图Fig.6 Comparison diagram of average end to end delay in concentrated formation

图7 稀疏编队下路由开销比较图Fig.7 Comparison diagram of routing overhead in sparse formation

图8 密集编队下路由开销比较图Fig.8 Comparison diagram of routing overhead in concentrated formation

图7和图8给出了无人机自组织网络在无人机稀疏编队和密集编队的情况下,采用上述4种算法在路由开销性能上的比较。可以看出,APAR算法在无人机稀疏网络和密集网络中,都具有相对较低的路由开销,在一定程度上降低了该网络中节点能量的消耗。同时,由于DSR算法在路由发现过程中采用了洪泛机制,所以其路由开销相对较大。

综上所述,APAR算法在平均端到端延时、数据包成功传输率和路由开销方面都有较为优异的性能,能够为战场环境下多无人机编队执行任务提供有效的通信保障。

6 结 论

本文针对无人机自组织网络中,采用传统的路由算法容易使该网络在数据包传输率、端到端延时和路由开销等方面性能降低,以至于不能满足多无人机编队执行任务信息共享需要的情况,提出了一种基于蚁群优化的多态感知路由算法——APAR算法,该算法主要受蚁群相关行为的启发,并与动态源路由算法相结合,通过感知路径长度、路径稳定性和路径拥塞度来建立选路标准,有效地避免了拥塞和链路断路现象的发生。同时,该算法能够根据无人机编队的变化适时地调整路由策略,以保证相关性能不下降。针对其他主流算法路由开销较大的问题,本文改进了信息素的挥发机制,对于不同的路径采用不同的衰减系数,降低了路由开销。APAR算法与DSR、Ant-DSR和HOPNET算法在仿真部分进行了性能比较,结果表明,在战场环境下,无论多无人机是稀疏编队还是密集编队,APAR算法都能保证较低的平均端到端延时、较高的数据包成功传输率和较低的路由开销,能够满足多无人机编队组网执行任务的需要。