一种基于萤火虫算法的飞行自组织网络路由协议

王红茹，赵红硕

哈尔滨工程大学 信息与通信工程学院，黑龙江 哈尔滨 150001

飞行自组织网络(flying Ad-Hoc networks，FANETs)是移动自组织网络 (mobile ad-hoc network, MANET)在空天领域的扩展应用。无人机等飞行器的稀疏分布和高动态特性导致网络拓扑结构频繁变化[1]，应用在MANET 的路由协议无法在FANETs 中取得良好的通信效果。如何设计一个适用于FANETs 的路由协议，对于实现无人机之间可靠通信具有重要的现实意义。

按照建立路由的方式，基于拓扑的路由协议分为先验式路由协议和反应式路由协议。反应式路由协议如动态源路由(dynamic source routing protocol，DSR)协议，在出现数据传输需求时才开启路由发现进程。相关的研究集中在如何评估链路路由质量并获取最佳路由[2-4]。先验式路由协议如最优化链路状态(optimized link state routing，OLSR)协议，每个节点维护反映网络最新路由信息的路由表，相关的研究集中在握手消息(Hello)发送间隔的调整[5-7]、路由选择准则[8-10]以及多点中继（multipoint relay，MPR）选择机制的设计[11-19]。相比于DSR 协议，OLSR 协议更适合低时延、高可靠性要求的飞行自组织网络。

OLSR 协议中，每个节点的部分一跳邻居节点被选作MPR，只有MPR 可以洪泛拓扑控制(topology control，TC)信息，网络拓扑结构通过MPR 与其多点中继选择节点(MPR selector)间的链路拓扑信息建立。如何设计适用于FANETs 特点的MPR 选择机制是实现无人机节点之间稳定通信的关键所在。OLSR 协议使用一跳邻居节点的连接度作为MPR 选择准则，尽量减少数据包的重复转发情况。然而该准则不能反映链路通信质量，连接度高的节点不能确保具备稳定有效的链路通信功能。文献[11]通过统计物理层的信噪比信息评估链路质量并作为MPR 选择准则，文献[12]通过节点间的距离和邻居变化率选取MPR，文献[13]优先选择具有较高剩余能量和较低速度的节点作为MPR。以上相关研究通过设计链路质量评定准则获取最优的通信链路。然而以上相关研究只能对当下链路拓扑质量做评估，缺少对网络拓扑稳定性的考虑，难以适应高动态的飞行自组织网络。针对飞行自组织网络的高动态特性，文献[14-16]通过全球定位系统(global positioning system，GPS)获取节点的速度和位置信息并计算节点之间的链路持续时间，将链路持续时间加入到衡量链路质量的标准之中。文献[17]使用计算一段时间周期内2 个节点之间Hello 消息的收发成功比例以及移动相似度作为MPR 的评选指标。通过对节点移动状态的评估和预测，MPR 选择机制得到优化，所建立的拓扑路由能够保证一定的稳定性，然而使用贪心策略的MPR 选择机制会使得MPR 集合CMPR产生冗余。MPR 选择问题被证明是一个多项式复杂程度的非确定性问题(non-deterministic polynomial, NP)[18]。对于该类问题，使用启发式算法可获取近似最优解。文献[19]将量子计算与遗传算法相结合，提出了一种基于量子比特与量子叠加的MPR 选择算法，该算法能有效地减少CMPR冗余情况，但会引入大量的计算量，对无人机的计算能力有较高要求。

针对上述研究问题，本文提出基于萤火虫算法(firefly algorithm，FA)的FA-OLSR 协议，通过使用节点间链路持续时间和链路质量评估链路性能，组合链路持续时间和链路质量指标计算链路稳定性并将其作为选择MPR 集合的准则。萤火虫算法具有参数少、收敛快、求解精度较高的优点，因此FA-OLSR 协议的MPR 选择机制利用萤火虫算法来求取CMPR的最优解。文中提出的FAOLSR 协议能够较为准确地评估链路质量、减少CMPR冗余度并建立稳定的通信路由，使无人机之间的通信性能得到明显提升。

1 系统理论

1.1 OLSR 协议

OLSR 协议是一种表驱动的路由协议，OLSR 的处理流程下：

1) 节点通过接收和发送Hello 消息填充并更新本地链路信息表、一跳邻居表、二跳邻居表；

2) 节点在一跳邻居表中选取部分邻居节点作为MPR，建立CMPR；

3) MPR 建立MPR Selector 表，将包含MPR与MPR Selector 之间的链路状态信息的TC 分组洪泛到全网络；

4) 节点根据TC 分组建立网络拓扑表，根据一跳邻居表、二跳邻居表和网络拓扑表建立并维护网络路由表；

5) 节点根据自身维护的路由表发送数据包。

1.2 萤火虫算法

FA 是一种求解优化问题的启发式算法。该算法的灵感来自于萤火虫的闪烁行为，种群中每个萤火虫代表一个候选解，萤火虫亮度取决于在目标函数上的性能表现[20]。FA 算法有以下核心思想：首先，每个萤火虫都有可能被其他萤火虫吸引；其次，萤火虫对其他萤火虫的吸引力与自身的亮度成正比、与2 只萤火虫之间的距离成反比。这种吸引机制使得整个萤火虫种群都会向优质解的方向移动，而萤火虫之间的移动却是相对独立的，因此可以获得局部最优解和全局最优解。FA 的算法流程如下所述：

1) 设置算法的各项参数，初始化种群中萤火虫位置；

2) 将目标函数映射为萤火虫的绝对亮度；

3) 定义相对吸引度；

4) 萤火虫位置移动和更新；

5) 根据终止条件决定是否从步骤4)继续执行。

2 FA-OLSR 协议

FANETs 中，节点之间的相对运动状态决定了节点之间的链路持续时间，FA-OLSR 协议使用节点间的相对速度信息计算链路持续时间指标。此外，节点之间的相对距离反映了节点之间的链路通信质量，为了更好地衡量通信链路的可靠性和中继性，FA-OLSR 协议引入Beta 分布函数计算链路质量指标。

FA-OLSR 协议利用萤火虫算法求取CMPR的最优解。在使用萤火虫算法求取CMPR的过程中，采用0-1 编码对萤火虫进行编码，使用节点的连接度初始化萤火虫的位置，利用MPR Selector 和MPR 之间的链路稳定性计算萤火虫的亮度。通过移动更新萤火虫的位置探索最优的CMPR，经过一定的迭代次数后得到最优CMPR。

2.1 链路稳定性计算

本文在仿真过程中，忽略无人机在垂直方向上的坐标信息和速度信息。设无人机节点a、k的速度分别为va、vk， 坐标信息分别为(xa,ya)、(xk,yk)。根据相对运动学，无人机节点a、k之间的相对速度、相对距离为

根据无人机节点a、k之间的相对速度，计算得到a、k之间的链路持续时间：

中继节点在源节点通信范围内时，便可以承担转发中继的功能。如果中继节点靠近源节点通信范围边缘时，链路通信效果较差，反之中继效果较差。如图1 所示，节点O为源节点，节点a、b、c为中继节点。节点O选择其中一个作为自己的中继节点。其中节点a靠近源节点，中继效果很差；节点c处在源节点O通信范围边缘，通信链路容易中断；节点b处在相较合适的位置，具有较好的链路通信效果和中继效果。为了评估节点之间的链路质量，FA-OLSR 协议引入了Beta 分布函数。

图1 中继点位置示意

Beta 分布函数为

式中：Beta 分布的定义域为[0,1]，α、β为不小于0 的参数。

Beta 分布函数的概率密度函数为

对无人机节点a、k之间的相对距离归一化处理得到参数rak：

式中R为无人机节点的通信距离。

通过以上分析可知，源节点临近区域与通信范围边缘区域具有相同的通信质量，因此取Beta 分布中参数值α=β=2，代入rak到Beta 分布的概率密度函数并计算链路质量指标为

链路质量指标是对链路通信效果和中继效果的综合评价。链路质量和链路持续时间指标组合形成链路稳定性指标，并将其作为衡量链路性能的准则。

2.2 萤火虫编码

CMPR是节点一跳邻居的子集，CMPR的选择问题是一种离散型问题。因此，在利用萤火虫算法求取MPR 集合时，需要对萤火虫离散化。一跳邻居节点只有非MPR 和MPR 这2 种类型，因此采用0-1 编码策略对萤火虫编码。设定节点i的一跳邻居集合为Ni={Ni1,Ni2,···,Nin}，n为一跳邻居节点数目，则对于节点i的一跳邻居Nik，萤火虫i的对应维度xik编码方式为

2.3 初始化萤火虫种群

萤火虫种群中的萤火虫个体都需要满足MPR 集合的性质，即萤火虫个体代表的CMPR能够覆盖所有的严格对称二跳邻居节点；其次，萤火虫种群应该具有多样性，避免陷入局部最优的情况。因此FA-OLSR 采用轮盘赌策略初始化萤火虫个体，单个萤火虫个体的初始化流程如下所述：

1) 设置序号为i的一跳邻居节点的连接度为D(i)，被选中为MPR 的概率定义为pi；

2) 在一跳邻居集N1={N11,N12,···,N1n}中选择对某一二跳邻居唯一可达的节点为MPR；

3) 计算每个一跳邻居节点被选择为MPR 的概率pi：

4）计算每一个一跳邻居节点代表的累加概率值qi：

5）在[0,1)内取随机数r，选择满足条件qi-1＜r≤qi的一跳邻居为MPR；

6）重复步骤5），直到萤火虫个体具备CMPR的性质。

采用上述流程对萤火虫种群中的萤火虫个体进行初始化，得到初始萤火虫种群。

2.4 计算萤火虫亮度

CMPR承担着洪泛TC 消息分组的任务，最小数量的CMPR能够减少网络中消息的洪范数量，降低路由开销。考虑到FANETs 的高动态性，使用本文提出的链路持续时间和链路质量组成的链路稳定性指标作为MPR 选择准则。文献[17]中指出，MPR 是作为中继节点覆盖某个节点的2 跳邻居，计算链路稳定性指标的时候要考虑其传递性与中继放大的特性。因此计算萤火虫i的适应度函数为

式中：f(rak;2,2)为本地节点a与一跳邻居节点k之间的链路质量，tak为本地节点a与一跳邻居节点k之间的链路持续时间，两者之和组成链路稳定性指标；tk j为一跳邻居节点k和与其连接的二跳邻居节点j之间的链路持续时间，f(rk j;2,2)为一跳邻居节点k和与其连接的二跳邻居节点j之间的链路质量参数，average 表示节点k与通过该节点到达的所有严格对称二跳邻居节点的链路指标的算术平均值，两者之和作为一跳邻居节点k和与之相连的二跳邻居之间的平均链路稳定性指标。

萤火虫的亮度直接由萤火虫的适应度函数值设定：

2.5 萤火虫位置移动

FA-OLSR 协议的MPR 选择问题设置为最小化问题，萤火虫的亮度与MPR 解集的质量成反比，萤火虫亮度较亮者会被萤火虫亮度较暗者吸引。萤火虫之间的吸引力和萤火虫之间的距离成反比，由于萤火虫编码方式为0-1 编码，因此设定萤火虫的吸引力程度为使萤火虫维度值发生变化的不同概率值 β1、β2(0 ＜β2＜β1＜1)。

萤火虫与代表最优解的萤火虫在相同维度上的值相同时，表明萤火虫在此维度的值接近最优解的位置，以较大概率 β1保持原值不变；反之，以较小概率 β2保持原值不变。另外，为了避免陷入局部最优，萤火虫移动时引入随机策略。当2 个萤火虫处于同一位置时，即2 个萤火虫各个维度相同时，随机改变其中1 个萤火虫的某一维度值。萤火虫的移动算法（Algorithm 1）如下所示：

输入：萤火虫种群。

输出：移动操作后的萤火虫种群。

参数设置：萤火虫xi的亮度为I[i]、0～1 范围内的随机数为r、不同的吸引度参数 β1、 β2。

计算过程：

forxi∈populations do

ifI[j]＞I[i] then

fork=0 toDdo

ifxik==xjkANDr＞β1then

xjk←NOTxjk

else ifxik≠xjkANDr＞β2then

xjk←NOTxjk

end if

end for

end if

end for

2.6 萤火虫个体筛选

萤火虫的移动操作也会破坏MPR 性质，使得萤火虫个体代表的CMPR不能够覆盖所有的严格二跳邻居。因此需要对萤火虫个体进行筛选，将不能完全覆盖二跳邻居节点的萤火虫个体剔除。为了保证移动操作的有效性，在迭代开始前，筛选出不具备MPR 性质的萤火虫个体，并使用周围亮度较亮的萤火虫覆盖，保证萤火虫处在有效位置。如果萤火虫出现位置重合，对其中一个萤火虫进行随机移动。

2.7 MPR 选择机制

萤火虫表示为xj,j∈[0,s)，s为种群规模，imax为最大迭代次数。FA-OLSR 的MPR 选择机制如下：

输入：萤火虫种群。

输出：最优CMPR。

计算过程：

whileit＜imaxdo

forj=0 tosdo

if (xjis not a MPR)

xj←xj-1

end if

end for

forj=0 tosdo

ComputeI(j) according to Eq (1)

end for

sort(xj,I(j)),j∈[0,s)

Apply the move operation according to Algorithm 1

end while

return the best solution,CMPR

萤火虫之间通过相互吸引、移动的方式，最终聚集到最优萤火虫的周围，获取最优CMPR的过程与萤火虫种群这种行为极为相似。MPR 选择机制需要根据不同的网络拓扑状况寻找最合适的部分一跳邻居节点转发TC 分组消息，因此，在设计MPR 选择机制的过程中，将萤火虫个体作为CMPR的解，通过移动、迭代操作不断接近最优CMPR。

3 仿真结果与分析

FANETs 路由协议的仿真在OMNET++平台上完成。 FA-OLSR、 LD_OLSR、 OLSR、 OLSRr2 协议的仿真参数设置如表1 所示。端到端时延、节点间数据包的传递成功率和网络吞吐量作为衡量路由协议的性能指标。仿真记录不同的节点速度下路由协议的性能变化。

表1 仿真环境参数表

端到端时延、数据包传递成功率和网络吞吐量的定义如下：

1) 端到端时延：数据包传输时延通常包括缓存区时延、路由查找时延以及数据包传送时延等，表现为节点产生消息到消息被接收之间的时间段。

2) 数据包传递成功率：数据包传递成功率定义为目的节点成功接收的数据包数目与源节点发送的数据包数目的比值，反映了网络通信的可靠性。

3) 网络吞吐量：吞吐量定义为单位时间内成功发送的数据量，表示网络传输数据包的能力。

图2～图4 分别给出了FA-OLSR、LD-OLSR、OLSR、OLSR-r2 在不同的节点速度下的各种性能。

如图2 所示，在网络拓扑相对稳定的阶段，FA-OLSR、LD-OLSR、OLSR、OLSR-r2 协议的数据包传输成功率相差不大，随着节点移动速度的提高，几种协议的数据包传输成功率均呈现下降的趋势。以节点连接度为MPR 选择准则的OLSR 协议和以链路带宽为MPR 选择准则的OLSR-r2 协议不太适应频繁变化的网络拓扑结构，数据包传输成功率较差。在选择MPR 时考虑节点间链路持续时间因素的LD-OLSR 和FAOLSR 协议能够较好地适应快速变化的网络拓扑结构，数据包传输成功率较高。FA-OLSR 相对于LD-OLSR 协议，在节点较高移动速度场景下具有更好的数据传输成功率表现，这是因为FAOLSR 协议综合考虑了链路持续时间和链路质量的因素，而且在MPR 选择机制中利用了启发式算法，更容易获取最优解，使得获取的路由链路更加稳定。

对于表驱动路由协议，每个节点都维护一张具有到全网络节点路径的路由表。如图3 所示，随着节点移动速度的提高，节点之间的通信链路断裂风险提高， FA-OLSR、 LD-OLSR、 OLSR、OLSR-r2 协议的平均端到端时延均呈现出上升的趋势。以节点连接度为MPR 选择准则的OLSR协议和以链路带宽为MPR 选择准则的OLSRr2 协议不太适应频繁变化的网络拓扑结构，通信链路断裂概率较大，因此具有较大的网络端到端时延。相比于LD_OLSR，FA-OLSR 协议在选取MPR时参考了链路质量因素，所选择通信链路中的节点具有更好的中继性，因此FA-OLSR 协议具有较小、更平稳的平均端到端时延。

图3 节点传输数据平均端到端时延性能

如图4 所示，在网络拓扑相对稳定的阶段，FA-OLSR 协议因为具有比其他路由协议更多的路由开销，吞吐量相对较低。随着节点移动速度的提高，FA-OLSR、LD-OLSR、OLSR、OLSR-r2 协议的吞吐量呈现出下降的趋势。由于数据包传输成功率的差异，FA-OLSR、LD-OLSR 协议相比OLSR、 OLSR-r2 协议吞吐量较高。 相比于LD_OLSR 协议，FA-OLSR 协议的MPR 选择机制使用了萤火虫优化算法，虽然带来了一定的路由开销，但优化的CMPR成员更加稳定，路由维护阶段的路由开销较少，因此具有较高的吞吐量。

图4 网络吞吐量性能

4 结论

1）FA-OLSR 协议提出了链路持续时间和链路质量指标衡量链路性能，组合链路持续时间和链路质量指标计算链路稳定性并将其作为选择CMPR的准则。

2）FA-OLSR 协议在萤火虫算法的基础上设计了MPR 选择机制，采用0-1 编码对萤火虫进行编码，使用节点的连接度初始化萤火虫的位置，确保了萤火虫个体代表合格的CMPR。MPR Selector和MPR 之间的链路稳定性被用来计算萤火虫的亮度。萤火虫的移动操作被用来探索最优CMPR。

实验结果证明，相比于LD_OLSR、OLSR、OLSR-r2 协议，所提出的FA-OLSR 协议在端到端时延、吞吐量、数据包成功率指标均有所提升，在大多数场景下有着更加优异的网络性能，因而FA-OLSR 协议对高动态的FANETs 网络具有良好的适用性。