一种无人机自组网DSR协议优化方法

刘庆华，黄声培，叶金才，康一鸣

桂林电子科技大学信息与通信学院，广西 桂林 541004

集群无人机协同通信的无线组网技术简称无人机自组网，网络中每个无人机（unmanned aerial vehicle，UAV）节点均配置收发信机，具有拓扑不固定、通信自组织、无控制中心的特点。无人机自组网规模易于扩展，节点动态加入和退出并不影响网络的通信。无人机自组网突破了依靠地面基站的限制，可以进行快速部署，在军事行动、救灾、边防等方面具有广泛应用。

相比于传统的地面移动自组网，无人机自组网的网络拓扑变化更快，网络节点的能量和带宽均有限，如何建立高效稳定的传输路径，保证通信质量，同时控制好网络的路由开销，是无人机自组网研究的热点问题。其中，路由协议是协调无人机节点组网通信、维护网络的关键，是无人机自组网高效运行的保障。

动态源路由（dynamic source routing，DSR）协议和其他路由协议相比，具有更低的路由开销。但该协议在路由请求洪泛的过程中，只保证了链路的连通性，忽略了链路的稳定性，通信质量并不高。文献[1]加入了节点能量因素，对DSR 协议路由发现过程进行了相应的修改，提高路由发现的效率和网络能量的利用率。文献[2]用多播算法与DSR 协议相结合的方式，提高了自组网的分组传递率和网络吞吐量。文献[3]用MIKBIT（mobile internetwork broadcast infrastructure technique）的组播方式来减少请求分组开销，提高了DSR 协议的性能。文献[4]提出一种拥塞感知与多路径相结合的方法，利用相关因子处理DSR 协议端到端时延的问题。文献[5]利用相邻节点之间的距离和移动性来评估路由发现、路由维持和路由切换过程，保证数据包的传递率。

除了上述优化方法，还可利用群智能优化算法解决DSR 协议的路由优化问题。群智能优化算法是近年来研究的热点，其中具有代表性的有蚁群算法（ant colony optimization，ACO）[6-7]、粒子群算法（particle swarm optimization，PSO）[8]、萤火虫算法（firefly algorithm，FA）[9-10]等，FA算法由Yang教授提出，该算法的鲁棒性强，目前已应用于解决特征选择优化[10]、多模态函数优化[11]等问题。本文针对无人机场景，提出了一种基于萤火虫算法的DSR协议优化（firefly algorithm dynamic source routing，FA_DSR）方法，利用萤火虫算法来优化传统的DSR路由协议，均衡网络节点的资源消耗，提升无人机自组网的性能。仿真实验结果表明，相比传统DSR 协议的路由方法，优化方法降低了路由开销，提高了无人机自组网的性能。

1 相关算法和协议介绍

1.1 萤火虫算法

萤火虫算法的灵感来源于观察自然界中萤火虫的习性[12]。萤火虫的荧光作为一种信号，主要作用是为了吸引异性和诱捕猎物，同时也是一种预警保护机制。萤火虫算法最初用于处理连续优化问题，起始时刻，萤火虫随机分布于搜索空间中，其位置代表了待求问题的可行解，萤火虫的荧光亮度表示该萤火虫的适应度，亮度低的萤火虫会被亮度高的萤火虫吸引，亮度越高吸引力越强，由于距离的增加会导致亮度衰减，因此，吸引力与距离成反比。一般地，萤火虫算法的步骤描述如下：

步骤1 初始化算法参数。

步骤2 初始化萤火虫位置，计算适应度函数。

步骤3 计算萤火虫的相对吸引力，其吸引力公式为：

其中，β0表示初始吸引力，即rij为0 时的吸引力；γ表示介质对光的吸收系数；，rij表示萤火虫i和j之间的欧氏距离，公式为：

其中，d表示空间的维度，xi,v表示萤火虫i的第v维数据。

步骤4 萤火虫向荧光亮度更高的萤火虫移动，其移动公式如下：

其中，xi(t)表示萤火虫i在第t次迭代时的位置，xj(t)为萤火虫i在第t次迭代移动的对象j的位置，α表示扰动因子，rand为0～1之间的随机数。

步骤5 计算萤火虫移动后所到新位置的适应度值，若该位置优于移动前的位置，则该萤火虫移动到该位置；否则，萤火虫停留在移动前的位置。

步骤6 达到搜索精度或迭代极限Gmax，搜索完成，输出结果，否则转到步骤3。

1.2 DSR协议

DSR协议算法流程主要包括两部分：路由发现和路由维护[13]。该协议查找路由的方式如图1 所示，源节点S有业务传输需求时，首先将路由请求广播到一跳邻居节点(A,B)，收到路由请求的节点判断是否缓存有到达目的节点的路由。如果有，则向源节点S发送缓存路由回复；如果没有，一跳中间节点(A,B)继续广播该路由请求，通过中间节点不断重复，最终到达目的节点D，其路径为(S→B→C→D)。D收到路由请求后，逆着请求得到的首条路径往源节点S发送路由回复(D→C→B→S)，源节点S收到路由回复，路由寻路过程结束，从而建立源节点S到目的节点D的传输路径。

图1 DSR协议的路由发现过程Fig.1 Routing discovery process of DSR protocol

路由维护过程为：当某一节点检测链路的下一跳不可达时，表明传输链路断开，该节点首先检查缓存区是否缓存有到达目的节点的路由，如果有，则继续沿着缓存的路由向目的节点发送数据；如果没有，该节点沿着传输路径逆向往源节点发送路由错误，收到路由错误的节点删除故障链路，更新路由缓存[14]。当源节点收到路由错误后，重新启动路由发现过程。

本文为了提高DSR 协议的路由发现效率，保障无人机自组网传输链路的稳定性，将萤火虫算法运用于DSR 协议的路径优化问题中，综合优化DSR 协议的路由发现过程，提出了一种基于萤火虫算法的无人机自组网DSR协议优化（FA_DSR）方法。

2 DSR协议优化（FA_DSR）方法的原理和实现

为了评估萤火虫的荧光亮度，算法需要构建适应度函数，萤火虫算法利用适应度函数来衡量每个萤火虫的亮度，选取荧光亮度更高的萤火虫作为下一跳节点，从而提高DSR协议的路由请求效率，保证传输链路的稳定性。

2.1 适应度函数

为了均衡优化无人机自组网的网络性能和路由开销，根据无人机自组网的特点，优化方法考虑以下四点因素构建适应度函数：

（1）节点的能耗。节点的存活时间由节点的剩余能量决定，在路由选择的过程中，应尽可能选择能量消耗较小的节点，防止通信链路过早中断，延长通信链路的生存时间。能量适应度值表示节点消耗的能量与初始能量的比值，体现了节点的能耗情况，表达式如下：

其中，Ej_con表示节点j消耗的能量值，Einitial表示节点初始能量值，nj表示节点j发送数据包的数量，ET(k)表示发送k比特数据包的能量消耗，mj表示节点j接收数据包的数量，ER(k)表示接收k比特数据包的能量消耗。

（2）节点的移动速率。由于无人机的运动状态随机变化，导致网络拓扑时刻发生变化，移动速率越大拓扑变化越快，因此，选取移动速率相对较小的节点构建传输链路，要比移动速率大的节点更稳定。速率适应度值衡量了节点的移动速率大小，其表达式如下：

其中，Sj_current表示节点j的当前移动速率值，Smax表示节点移动速率的最大值，速率适应度值衡量了节点的移动速率大小。

（3）节点的缓冲拥塞率。缓冲拥塞率体现节点发送数据包的繁忙程度。缓冲区的容量有限，如果拥塞程度较高，说明此节点待发送的数据包较多，丢失数据包的概率大，因此，优先选择繁忙程度低的节点作为转发节点。拥塞适应度值表示节点缓冲区的拥塞率大小，其表达式如下：

其中，Cj_current表示节点j当前的缓冲区队列大小，Cmax表示节点缓冲区总容量大小。

（4）节点的传输损耗。传输损耗主要由传输距离决定。由于节点之间的距离不同，导致节点的接收功率产生差异，接收功率大小反映了节点之间通信连接的稳定性，距离越近，传输损耗越小，接收功率越大，业务接收越稳定，距离越远则相反。传输损耗适应度表达式如下：

其中，Dij_prop表示发送节点i和接收节点j传播的欧氏距离，Dmax表示两节点之间的最大传播距离，Ptx_power表示节点发送的功率值，Pth表示接收功率门限值。

为了便于将各项适应度值映射转化萤火虫的荧光亮度，同时也为了更精确的衡量节点的适应度，需要将各项适应度函数整合为非线性的综合适应度函数，由于线性度量在相近的数值区分不如非线性明显，采用非线性适应度函数计算更精确，更贴合实际情况，定义FA_DSR的综合适应度函数为：

本文将节点的能量消耗、移动速率、缓冲拥塞和传输损耗因素构建综合适应度函数，利用综合适应度函数衡量萤火虫的荧光亮度，选取荧光亮度高的萤火虫作为下一跳节点，综合优化DSR协议的路由请求过程，降低网络的路由开销，提高无人机自组网的性能。

2.2 FA_DSR的实现

利用萤火虫优化算法，对传统DSR 协议的请求洪泛策略进行优化，保证通信链路的稳定性。FA_DSR的路由请求流程如图2所示。

图2 FA_DSR的路由请求流程Fig.2 Routing request flow of FA_DSR

（1）源节点初始化路由请求选项。为了传递位置信息和综合适应度函数值，优化的DSR 协议对原DSR 协议请求选项进行了更改，FA_DSR的请求选项信息如表1所示。

表1 FA_DSR的请求选项信息Table 1 Request option information of FA_DSR

表中，x_position、y_position、z_position和fitness_fun_value为新增的选项信息。

（2）初始化萤火虫。源节点的一跳邻居收到路由请求后，将节点的位置作为初始萤火虫的位置，即xi,v=Xj,v，初始化适应度取值范围[Fmin,Fmax]和最大迭代数Gmax等基本参数，适应度取值范围的选取需要均衡网络中可用节点的数量和节点的稳定性，Fmin过小则节点稳定性不足，Fmin过大则网络中可用节点数量不足，其具体数值见仿真实验部分。根据公式（8）计算萤火虫的综合适应度值，根据适应度取值范围舍弃低适应度的萤火虫，剩余的萤火虫将适应度值作为萤火虫的荧光亮度，即Ii=Fj。

（3）萤火虫向更高亮度的萤火虫移动。由于路径选择属于组合优化问题，而萤火虫算法适用于处理连续优化问题，所以，为了能将萤火虫算法应用于路径选择问题中，本文不再按照公式（3）移动，而是按照一定的概率选择移动公式[16]，即萤火虫个体的每一维坐标按照一定的概率做随机离散移动，其离散移动公式如下：

其中，rand(v)表示第v维向量随机产生的0～1 之间的随机数，pset表示设定的概率阀值，Pset∈[0,1]，xj为萤火虫个体xi在第t次迭代移动的对象，式（9）表明萤火虫个体i在第t次迭代移动时以概率1-Pset转移到个体j对应的第v维向量，以Pset的概率维持原来的第v维向量。

（4）调整萤火虫位置，更新荧光值。由于移动后的萤火虫与具体的无人机节点位置可能存在偏差，因此，需要将移动后的萤火虫映射调整到具体的无人机节点上，并更新调整后萤火虫的荧光值。萤火虫与无人机节点的位置映射函数[17]为：

其中，xi为萤火虫i的位置，Xn为表示无人机节点n的位置，l(xi,Xn)表示萤火虫xi与无人机节点Xn之间的欧氏距离。

（5）判断是否满足终止条件。如果搜索到达目的节点或达到最大迭代数，则算法搜索结束，否则转到步骤（3）。

3 仿真实验

使用OPNET Modeler 网络仿真软件[18]来模拟具体的无人机自组网通信，其主要仿真参数如下：

网络部署面积为5 km×5 km，节点总个数为30 个，各节点随机分布在部署区域内，节点海拔高度为0.1 km，节点的移动模型为default random waypoint[19]。节点传输速率为5.5 Mb/s，通信连接数量为4 条单向CBR 数据流，发包间隔为0.2 s，数据包大小k为1 024 bit，节点初始能量Einitial设为40 J，ET(k)设为8.5 mJ，ER(k)设为6.3 mJ，概率阀值pset设为0.05，发送功率Ptx_power设为5 mW。最大迭代数Gmax设为32，适应度取值范围[Fmin,Fmax]设为[0.2，1.0]，仿真时长为10 min。

DSR 为原始协议，DT_DSR（decition tree dynamic source routing）为基于决策树算法的优化协议，FA_DSR为提出的基于萤火虫算法的优化协议。为了比较DSR协议优化前后性能，仿真对比分析了网络的平均端到端时延、业务接收速率、路由开销和丢包率指标。

端到端时延统计了数据包从源节点产生到目的节点接收经历的时间。如图3对比了仿真时间内3种不同协议的平均端到端时延。从图中可以看出，随着仿真时间的进行，3 种协议产生了不同程度的时延，由于采用了萤火虫算法对节点的能耗、移动速率、缓冲拥塞和传输损耗来构建综合适应度函数，利用综合适应度函数衡量萤火虫的荧光亮度，选取荧光亮度更高的萤火虫作为下一跳节点，提高了传输链路的稳定性，减少了链路断裂导致的路由重启现象，FA_DSR的端到端时延要比DT_DSR 和DSR 协议要低，虽然DT_DSR 相比原始DSR协议的端到端时延也有所下降，但远不及FA_DSR的表现，DT_DSR 的端到端时延相比DSR 协议降低了26.99%，而FA_DSR 的端到端时延相比DSR 协议则降低了73.91%。

图3 平均端到端时延Fig.3 Average of end-to-end delay

业务接收速率反映了目的节点接收源节点发送业务数据的快慢程度。从图4可以看出，仿真开始后，3种协议的业务接收速率逐渐增加，逐渐接近业务发送速率。随着仿真时间的推进，3种协议的业务接收速率开始受到网络拓扑变化的影响，业务接收速率出现波动下降的情况，DSR 协议的业务接收速率下降最明显，DT_DSR的业务接收速率也开始缓慢下降，但下降幅度总体小于DSR 协议。由于FA_DSR 利用适应度函数衡量萤火虫的荧光强度，综合选取传输路径的下一跳节点，通信链路比DSR和DT_DSR的更稳定，受到网络拓扑变化的影响最小，FA_DSR的业务接收速率总体高于DT_DSR和DSR协议。统计数据显示，DT_DSR的业务接收速率比DSR 协议提高了17.42%，而FA_DSR 的业务接收速率相比DSR协议提高了33.80%。

图4 业务接收速率Fig.4 Receiving rate of traffic

如图5 的路由负荷发送速率和图6 的路由负荷接收速率共同反映了网络的路由开销。路由负荷发送速率记录了整个网络中发送的路由负荷流量，路由负荷接收速率记录了整个网络中接收的路由负荷流量。由于FA_DSR融入了适应度函数，减少了一部分低效的路由洪泛，提高路由发现的效率，减少了路由负荷流量，降低了网络的路由开销。仿真结果显示，DT_DSR的路由负荷发送速率比DSR协议减少了13.62%，而FA_DSR的路由负荷发送速率比DSR协议减少了44.99%；DT_DSR的路由负荷接收速率比DSR协议减少了15.25%，而FA_DSR的路由负荷接收速率比DSR协议减少了37.55%。

图5 路由负荷发送速率Fig.5 Sending rate of routing load

图6 路由负荷接收速率Fig.6 Receiving rate of routing load

如图7 为3 种协议的丢包率对比结果，丢包率为丢失的数据包与源节点发送数据包之比，其大小反映了传输链路的可靠性。从图中可以看出，仿真一开始，传输路径还没有建立，3种协议均丢失大量数据包，随着路径建立完成，丢包率开始下降，随着仿真时间的进行，传输路径受到网络拓扑变化的影响，DSR协议不能很好的适应网络的拓扑变化，其丢包率迅速提高。DT_DSR的丢包率相比DSR 协议有了一定的程度的降低，说明其优化策略起了一定的作用，而FA_DSR根据网络资源实施更加科学的算法机制来选取路径，FA_DSR的传输路径相比DSR 和DT_DSR 更稳定，从而大大降低了丢包率。仿真结果显示，DT_DSR的平均丢包率比DSR协议减少了36.33%，而FA_DSR 的平均丢包率比DSR 协议减少了68.01%。

图7 丢包率Fig.7 Packet loss rate

仿真实验结果充分表明，与传统DSR 协议和现有的DT_DSR优化方法相比，本文所提的FA_DSR优化方法能有效降低网络的路由开销，减少端到端时延，提高业务的接收速率，降低丢包率。该优化方法可以为无人机自组网提供稳定高效的路由服务，保障无人机自组网的通信质量。

4 结论与展望

本文在传统DSR 协议的基础上，提出了一种基于萤火虫算法的无人机自组网DSR 协议优化方法，利用萤火虫算法来优化DSR协议的路由发现过程。本文方法虽然增加了路由算法的复杂度和请求报文的长度，但仿真实验表明，提出的协议优化方法与传统的DSR 协议相比，提高了网络的性能，降低了网络的路由开销。

本文的优化方法有效解决了无人机自组网通信质量不佳，路由开销较大的问题。然而，本文仅考虑了节点能量、移动速率和传输损耗等少数几个因素，无人机自组网是一个庞大而复杂的通信系统，需要考虑的因素还有很多。因此，如果能更细致地研究无人机自组网的网络特性，将路由协议与不同的优化算法相结合，一定能提出更好的路由方案，甚至是高性能的、全新的路由协议。