基于链路拥塞的无人机动态路由组网

黎云，李健

（四川大学电子信息学院，成都 610065）

0 引言

复杂的战场环境导致单无人机无法完成战场侦查、攻击目标等任务，多个无人机作战将会成为一种重要的作战方式。多无人机作战首要任务是无人机之间自组网，是由多个无人机动态组成的、无中心的多跳网络，FANETs（Flying Ad hoc NETworks）是一种特别的移动自组织网络（Mobile Ad hoc NETworks，MANETs），具有高速移动的特点[1,2]。FANETs比MANETs拓扑变化的更快，很多路由协议是为MANETs设计的，如BABEL[3]、OLSR（the Optimized Link-State Routing）[4,5]协议都不能对网络拓扑的变化做出快速的反应，因此路由的研究变成了关键问题，Stefano Rosati等人[6]提出了P-OLSR（Predictive-OLSR）路由协议,该协议引入了GPS，考虑到了无人机之间的相对速度，比OLSR协议能更快的适应拓扑的变化，但是P-OLSR协议引入的ETX链路评价机制只考虑到了探针包的接收率和节点之间的相对速度，并未考虑到延迟。本人依据前面的相关工作，对P-OLSR协议进行改进。

1 P-OLSR路由协议

Ad Hoc网络中OLSR协议是目前比较流行的网络协议，是基于链路状态路由选择的协议，在原始的OL⁃SR协议中设计没有考虑无线链路的质量，路径的选择是根据跳数决定，对于FANET这是不适用的。DR提出了P-OLSR算法考虑了链路的质量和节点的相对速度，利用改进ETX度量[7]，P-OLSR可以保证链路的质量，ETX度量标准定义为：

其中R是两个节点之间的路径，η是R中的一跳路径，ϕ（η）是发送节点的接收比，ρ（η）是接收节点的接收比是节点i和节点j的相对速度，β是一个非负的参数。OLSR协议选择ETX最小的路径，可能不是跳数最短的路径。如果R中所有的跳数都是正确无误的（如：ϕ（η）=ρ（η）=1），且相对速度为0，ETX（R）就等于路径R的跳数。

接收比是通过链路探针来估计的，OLSR的链路探针通过Hello消息来实现。ϕ通过指数移动平均的方法计算，如下：

其中：

α是OLSR的一个参数，叫做链路质量老化。α在准确性和反应性之间取的平衡，然后去估计接收比。

如果α很大，接收比将会反应很慢，会非常稳定可靠。如果α很小，接收比将会反应地很快。

如果节点i和节点j之间的距离在变小，相对速度就为负数，ETX则会乘一个小于1的权重系数。如果节点i和节点j之间的距离在变大，相对速度就为正数，ETX则会乘一个大于1的权重系数。也就是说在2条一跳路径具有相同的ϕ和ρ会选择节点在相互靠近的一跳路径，而不是2个节点相互远离的一跳路径。根据GPS获取地理信息然后加入Hello消息中，然后就可以计算节点之间的相对速度了，计算相对速度的公式如下：

其中tl是最后一次接收到Hello的时间，tl-1是最后一次的上一次接收到Hello的时间，和分别对应2个不同时间的节点i和节点j之间的距离，由于GPS存在误差，可以通过指数移动平均的方法进行处理，方法如下：

其中γ是P-OLSR的一个参数。但是P-OLSR协议考虑了节点的移动状态，所利用的ETX机制只考虑了探针包丢包的状态，并没有考虑探针包的延迟。

2 基于拥塞的P-OLSR

原始的ETX并未考虑探针包的延时，探针包的延迟，可以反应出链路的质量，对ETX的探针包进行修改，如下：

其中：

其中p为P-OLSR的参数，Δtl为最后一次接收到探针包的延时，Δtl-1为最后一次的前一次接收到探针包的延时。Δt的计算如下：

其中trl为探针包发送的时间，tsl为探针包接收的时间。在相对速度为0的情况下，如果二个一跳链路具有相同的ϕ和ρ，修改后的ETX会选择延时在减小的链路，从而可以提前避免链路的拥堵。

3 仿真分析

3.1 仿真平台

利用NS-2仿真平台[8]来仿真OLSR、P-OLSR、POLSR的协议改进，在不同的运动速度下。NS-2是个开源的软件，NS-2是用C++和OTCL编写的，能够仿真不同的网络传输协议，例如：TCP、UDP[9]，还能方便添加各种路由协议如：OLSR[10]。

3.2 仿真参数

表1

3.3 性能参数

本文选取了分组投递率和平均时延对三个路由协议的性能进行比较，分组投递率定义为数据包成功传输的比例，等于总共接收到的数据包比上总共发送的数据包。分组投递率的值越大，协议的性能越好。端到端的延迟定义为数据包发送到目的点所花时间的平均值，端到端的延迟越小，协议的性能越好。

3.4 仿真结果

取α=0.2,γ=0.04,β=0.004,p=0.5的情况下，分别在不同的速度下重复10次取平均值，OSLR，P-OL⁃SR，P-OLSR-IMPROVE的分组投递率的对比如图1所示，P-OLSR，P-OLSR-IMPROVE协议的分组投递率都好于原始协议OSLR，P-OLSR-IMPROVE在6个速度仿真中，5个速度点优于P-OSLR。OSLR，P-OLSR，P-OLSR-IMPROVE的端到端的时延的对比如图2所示，P-OLSR，P-OLSR-IMPROVE协议的端到端的时延都好于原始协议OSLR，同时与P-OLSR协议比较，POLSR-IMPROVE的时延更低，因为 P-OLSR-IM⁃PROVE选择了拥塞较小的链路，因此时延会较P-OL⁃SR会下降。

图1 OLSR、P-OLSR、P-OLSR数据分组到达率

图2 OLSR、P-OLSR、P-OLSR端到端的延迟

4 结语

本文在ETX的算法上考虑了链路的延迟，提出了改进后的路由协议。仿真实验表明，改进后的网络能提前避开拥塞的链路，在数据分组投递率上有一定的提升，在端到端的延迟上有较大的提升，改进后的协议更加适合无人机自组网。

参考文献：

[1]Oubbati O S,Lakas A,Zhou F,et al.A Survey on Position-based Routing Protocols for Flying Ad Hoc Networks（FANETs）[J].Vehicular Communications,2017.

[2]I.Bekmezci,O.K.Sahingoz,S.Temel.Flying Ad-Hoc Networks（FANETs）:A Survey.Ad Hoc Networks,2013（11），3：1254-1270.

[3]J.Chroboczek.The Babel Routing Protocol.RFC 6126,2011.

[4]T.Clausen，P.Jacquet.Optimized Link State Routing Protocol（OLSR）.RFC 3626,2003.

[5]C.Dearlove,T.Clausen,P.Jacquet.The Optimized Link State Routing Protocol Version 2.IETF Draft RFC Draft-ietf-manet-olsrv2-10,2009.

[6]Rosati S,Kruzelecki K,Heitz G,et al.Dynamic Routing for Flying Ad Hoc Networks[J].IEEE Transactions on Vehicular Technology,2016,65（3）:1690-1700.

[7]D.S.J.De Couto,D.Aguayo,J.Bicket,R.Morris.A High-Throughput Path Metric for Multi-hop Wireless Routing.in Proceedings of the 9th Annual International Conference on Mobile Computing and Networking,ser.MobiCom'03.New York,NY,USA:ACM,2003：134-146.

[8]ZhibinWu,Rutgres University,Available:http://www.winlab.rutgres.edu/~zhibinwu/html/network_simulator_2.html,2007.

[9]Issariyakul,Teerawat,Hossain,Ekram.Introduction to Network Simulators[online]Available.http://www.springer.com/engineering/signals/book/978-0-3871759-3,2009.

[10]Francisco J.Ros,OLSR.Available:http://masimum.inf.um.es/fjrm/development/um-olsr/,September,2013.