摘要：近年来，随着多无人机系统在抗灾救险、环境勘测、军事作战等场景中的广泛应用，高效、灵活的无人机群组网研究已成为当下热点之一。现阶段无人机自组网存在拓扑变化频繁，网络开销增大和能量有限等特点，对OLSR(Optimized Link State Rout⁃ing)路由协议进行了分析研究。分析发现现阶段OLSR协议存在HELLO和TC消息包冗余或不能及时更新路由信息等问题，为此提出了一种基于SL-MPR选择算法的M-OLSR路由协议。首先综合考虑节点移动性、链路的变化情况等因素反映网络的拓扑变化情况，通过拓扑的变化控制节点HELLO消息的广播周期；其次提出一种新的MPR选择算法，考虑链路稳定问题和节点剩余能量(生存时间)因素，根据MPR集的更新频繁程度控制TC消息的洪泛周期。通过NS2仿真实验表明，相比传统的OLSR协议，M-OLSR在数据传输率方面提高了1%以上，能量消耗和网络开销均降低了10%左右。

　　关键词：自组网；无人机；OLSR路由；MPR；节点剩余能量

　　0引言

　　飞行自组织网络(Flying Ad-Hoc Networks，FANET)是移动自组织网络(Mobile Ad-Hoc Networks，MANET)在无人机领域的扩展应用。但相对于MANET，FANET在空中移动不受地形因素限制，节点速度更快，网络拓扑变化更频繁。在无人机群的协同作业中，其路由技术是核心技术之一，现阶段很大一部分应用于移动自组网中的路由协议技术是由无线传感器网络(Wireless Sensor Network，WSN)嫁接而来，但并不适合高速移动的FANET。因此要根据FANET对网络环境的需求改进原有的路由协议。

　　参考MANET网络，基于拓扑结构划分，路由协议可以分为平面路由协议和分级路由协议。平面路由协议又可以划分为主动式路由协议和被动式路由协议，又叫先验式和反应式。综合主动路由和被动路由特点分析应用的场景[1-8]，这里本文以主动式路由中的具有代表性的一种路由OLSR协议基础，对其进行优化以适应所需场景。

　　国内外对OLSR路由协议和无人机自组网做了大量研究。文献[9-10]都考虑了通过优化HELLO和TC消息的方式来对OLSR路由协议进行改进。文献[10]还提出了通过增加路由获取途径维护多跳链路的稳定性。文献[11-14]都对OLSR路由协议的MPR集的选择算法提出了新的想法。在MPR集的选择上综合考虑节点运动状态、连接时间、节点链路速率变化率、链路拥塞度和节点剩余能量等各方面因素达到提高数据传输成功率和网络的稳定性，降低丢包率、网络开销和时延的目的。文献[15-17]参考了智能集群算法对无人机自组织网络进行了优化应用，但其最大的缺陷是此类算法对无人机的计算能力要求很高，且启动时间较长，可应用的实际场景范围十分有限。

　　综上所述，目前国内外针对于OLSR的优化方案大多集中于MPR选择算法的优化和通过集群求解最优解优化等方面，但是过度复杂的优化算法反而会导致无人机群在算法数据处理上面得开销更大，反应灵敏度降低。因此，考虑到以上因素和OLSR协议本身特性，为达到降低网络开销，提高网络稳定性和增加网络生存时间的目的，本文提出了基于SL-MPR选择算法的OLSR优化协议，将链路稳定问题和节点剩余能量(生存时间)因素考虑进来，根据MPR集的更新频繁程度对TC消息的洪泛周期进行控制。最后开展NS2仿真实验进行验证。

　　1 OLSR路由协议的优化

　　优化链路状态路由协议(Optimized Link State Routing，OLSR)是主要用于MANET网络(Mobile Ad-Hoc Network)的路由协议。传统的链路状态路由算法中，网络中的每个节点向其他节点广播自己的链路状态分组，这个过程称为泛洪。每个链路状态分组都包含节点所连接的链路标识和开销，最终经过泛洪，网络中的每个节点都能得到一副相同的网络拓扑图[18]。而OLSR对传统算法进行了优化，这里边的核心机制就是MPR(多点中继)集的选取和MPR工作机制。选取少量节点作为MPR节点，只允许MPR节点进行广播泛洪传播控制消息，以此减少泛洪次数和泛洪节点数从而减少信息的传输量来降低网络开销[19]。OLSR适合使用于大规模，节点密度高的场景。

　　对于OLSR的优化，本文给出了两个优化方案，一是通过拓扑变化控制消息的广播周期，二是针对传统MPR选择算法存在的缺陷，提出了新的MPR选择算法。通过以上两种优化方案，实现在原OLSR协议的基础上，M-OLSR协议性能上更优，如路由开销和能量消耗更小，消息投递率更高等。

　　1.1 HELLO消息的广播机制

　　OLSR维护路由信息是由网络中的节点定期的广播HELLO消息和MPR集转发TC消息来进行的，HELLO消息用来建立本地链路信息库以及相邻接点信息库。但是在网络拓扑变化不大，节点状态稳定时，如果还按照原来的广播周期来进行进行消息的发送，就会产生不必要的操作，导致大量冗余的网络开销和能量消耗。而如果网络拓扑变化频繁，网络波动大，节点状态不稳定时，而原来设定的消息发送间隔又会使OLSR不能及时对网络状态进行更新，导致网络性能下降。所以本文考虑通过节点的信息来定义网络的拓扑状态，通过网络的拓扑状态来控制消息的泛洪周期。

　　对网络拓扑状态的判断，本文通过网络中每个节点与其所有一跳邻居节点的相对移动性和链路状态判断。

　　(1)节点相对移动性

　　定义节点i为网络中的任意节点，j为节点i的任意一跳邻居，则t1时刻节点j相对于节点i的移动速度为：

　　其中，因在工作场景中，无人机的移动过程可以近似看做同一平面，大幅度三维动态变化情况较少，且变化较小，故此数学建模将无人机看做同一水平面移动，并未建立三维坐标系。Vix为节点i在坐标系中水平方向速度，Viy为节点i在坐标系中竖直轴方向速度；Vjx为节点j水平方向速度，Vjy为节点j竖直方向速度。

　　t1时刻节点j相对于i的相对距离为：

　　Xi和Xj为节点i和节点j在坐标系中水平方向的位置变化，Yi和Yj为节点i和节点j在坐标系中竖直方向的位置变化。

　　T为节点i泛洪周期，t1定义为T前一刻时间，t2为T时间后时刻，则t2时刻的节点j相对于i节点移动速度为Vij′，则t2时刻的节点j相对于i节点相对移动距离为S j。T时间范围内的速度变化和距离变化分别表示为：

　　式中：a、b为权值，且a+b=1。定义节点i的一计数变量Na和节点间移动性阈值m，Na初始化值为0，当节点i与节点j的相对移动性M＞m时，Na值加1。

　　(2)节点链路状态

　　节点链路状态由式(6)定义：

　　式中：Nlinks为节点当前链路状态，通过监控节点自身信息表的变化推断周围节点网络拓扑的变化情况。Nnei为一个Hello消息发送时间间隔内节点周围邻居节点的变化数目(增加和减少)；NSym为一个Hello消息发送时间间隔内节点新增的对称一跳节点数目，NAsym为一个Hello消息发送时间间隔内节点减少的对称一跳节点数目。因为邻居的变化和链路变为非对称都需要对网络重新进行探测，一般需要3次HELLO消息的发送。所以此处的Nnei和NAsym为3次Hello消息间隔的平均值，链路状态变为对称只需要进行一次通知即可，所以NSym为当前值。

　　由以上节点相对移动性和链路状态得到了节点周围的网络拓扑变化，所以定义网络稳定度Ns的计算公式为：

　　式中系数的不同是由于链路状况的好坏对网络状况的反映状况更为明显一些，而移动性的状况更多反映的是物理层面节点的移动状况，更多的是具备一些预测性的功能。因为在节点移动性有波动变化时可能还没有引起网络拓扑层面变化，但是照此情况下去，网络拓扑层面的变化会有预见性的出现，此时就起到一个预警监测的作用。但是更多的情况链路状态变化引起的或者两者同时发生作用。

　　定义发送间隔增量ΔH=1 s，Ht为OLSR路由协议默认HELLO消息发送间隔，为2 s。定义Hsi为自适应Hello消息发送间隔，本文综合考量链路和移动性对Ns的影响，将His分为了3个区间，设定当Ns=0时，认为网络状态处于一个相对稳定状态，His=Ht+ΔH；当Ns=1时，认为网络处于正常状态，His=Ht；当Ns≥2时，认为网络处于剧烈波动状态，为了及时更新网络状态，设定His=Ht-ΔH[18]；故His表达为：

　　为了兼顾在网络状态变化过程中因为中间态的存在而引起的His变化具有的滞后性，将表达式作出优化：

　　1.2 TC消息洪泛机制

　　TC消息不同于HELLO消息的广播机制和一跳的通信范围，TC消息的存在是为了维护整个网络的拓扑结构，所以它的消息转发范围是整个网络，由MPR节点集负责转发，其时间间隔比HELLO要长，为了确保TC消息的时效性，TC消息有效时间也比HELLO消息存在的时间长。因此，要维护TC消息的发送间隔只需要对MPR集的变化进行监控就可以获知网络拓扑的变化情况。TCt为默认洪泛周期，为5 s，定义维护后的TC消息洪泛周期为TCis，定义M为计数单位，设置初始状态泛洪周期为TCt，当MPR集没有发生变化时，令M=0，定义当前间隔为TCtcur，令下一消息泛洪周期TCis=TCtcur+1，直到达到TCis达到最大门限值，设最大发送间隔为8 s；当MPR集发生变化时(节点集合、链路的增减)，令M=1，令TCis=TCtmin，TCtmin设为4 s。故TCis表达式为：

　　1.3 MPR选择算法

　　在OLSR路由中，MPR机制是其比较核心的思想，一个节点通过其一跳邻居节点和二跳邻居节点，选出MPR节点集。所有节点都可以接收到消息，但只有选定为MPR集中的节点才可以进行对此节点消息的转发。MPR集的计算所需的信息通过周期广播的HELLO消息获得。

　　注意，在Hello分组数据中，存在willingness选项。携带willing_never的节点永远不会被任何节点选为MPR。一个具有willing_always的节点则优先会被选为MPR。默认情况为willing_default。

　　目前传统的MPR选择算法是在标准OLSR协议文档RFC3626中被提出。这是一个贪婪选择算法，它设计了一个可以保证节点通过wilingness不为willing_never的MPR节点中继到达所有严格对称两跳邻节点的MPR集[10]。算法流程如图1所示。

　　同时传统的MPR选择算法还存在一些问题，比如会存在冗余，选择的MPR集不是最优，产生不必要的网络开销，没有考虑MPR的能量消耗问题，被选为MPR的节点稳定性等问题。针对以上问题，本文提出了基于SL-MPR算法的M_OLSR协议，在MPR的选择上考虑了节点能量，链路和移动性等因素，在原算法基础上优化的MPR的选择方法，具体如下。

　　1.3.1候选节点影响因子建模

　　在OLSR路由协议中，MPR机制是核心机制，选择合适的MPR节点将会直接影响到路由开销、能量消耗和网络的可靠性。因此，为建立可靠的路由，保证良好的网络性能，必须选择合适的MPR节点。相较于一般的mesh网络和Ad Hoc网络，在FANET中，节点的高移动性会使得链路通断和信息交互变得更加频繁，能量消耗越高。所以在考虑MPR节点的选择时，应该考虑节点剩余能量，节点链路情况等因素。为了综合考虑以上因素，使所选MPR尽量稳定，降低切换MPR的概率，提出一种SL-MPR(Survival and Link，SL)选择算法。

　　(1)对于节点生存问题，通过节点的剩余能量Er始能E0预测节点生存时间。相关义如下：

　　式中η为当前所剩能量所占总能量的百分比。

　　(2)对于节点的链路问题，引入节点链路变化情况。定义如下：

　　其中，因为要保证MPR集转发TC消息，只有对称节点才可以被选为MPR集，为节点当前Hello消息间隔时间内新增和减少的严格一跳对称节点数目，Nn为节点当前总的一跳对称节点数，δ为对称节点变化率，反映节点链路稳定度。

　　(3)节点链路传输质量问题[17]，节点之间的链路传输质量(Link Transmission Quality，LTQ)通过节点在一定周期范围内收到邻居节点所发送的HELLO消息的消息比例计算正向链路(Forward Link，FL)和反向链路即邻居链路(Neighbor Link，RL)质量的数值得到的。计算公式如下：

　　通过分析，发现对于准MPR节点i来说，i可以获得的关于HELLO消息的数目只有“i发送给j的HELLO消息数”和“i收到j发送的HELLO消息数”，仅凭此数据无法计算FL和NL，进而无法计算LTQ。因此，优化后的计算方式可以转换成以下方式求得LTQ。

　　根据以上定义的3个变量，进一步定义SL为MPR判定的整体影响因子，通过加权计算的方式表征出SL，因δ对称节点变化率与SL值呈负相关，故具体表达式为：

　　式中：a、b、c为节点属性对应的权重系数，且a+b+c=1，针对网络不同侧重方向调整取值。LTQ1是当前节点与执行MPR集计算的节点之间链路传输质量值，aver⁃age(LTQ2)为当前节点与其严格一跳对称节点(即执行MPR集计算的节点的严格二跳对称节点)之间链路传输质量值的平均值。

　　根据SL值，将候选MPR节点从大到小进行排序，SL值越大的节点其剩余能量越高，反映其生存时间将会越长，链路稳定度和链路传输质量相对较高。由此可见，SL值越高的候选节点更容易也更适合被选为MPR节点。本文网络偏重于节点生存时间，因此a、b、c比重确定分别为0.4、0.3、0.3。

　　1.3.2 SL-MPR选择算法具体步骤

　　综上，本文提出的改进算法核心思想是：在拓扑结构中，在节点i在选择MPR节点时，设定一个优先级判定关系，节点生存状态和链路稳定优先级大于节点深度优先级。在选择时优先判定SL值的大小其次才是节点深度，依次来进行MPR的选择。

　　算法流程如图2所示。

　　设Mi为节点i的MPR集，Q1为节点的一跳邻居节点集，Q2为节点的二跳邻居节点集。D(y)为初始时一跳邻居节点的深度。

　　Step1：初始化集合Mi为空；

　　Step2：计算Q1中所有节点的SL值和D(y)；

　　Step3：将Q1中存在到达某个两跳节点的唯一通路的节点，选为MPR节点，添加到中Mi，并从Q2中删除该节点所覆盖的节点，判断Q2集是否为空，若为空则算法结束，否则执行step4。

　　Step4：将Q1中剩余的节点中SL值最大的节点加入到Mi集中，若存在SL值相等的节点，则比较节点深度D(y)，选择深度最大的节点加入到Mi中，若D(y)也相等，则任选一个节点加入到Mi中，并从Q2中删除该节点所覆盖的节点，判断Q2集是否为空，若为空则算法结束，否则执行Step3。

　　2算法仿真分析

　　2.1仿真环境

　　本文使用Linux平台上的NS2仿真软件，设置了5个仿真场景，每个节点计算能力相同，通信范围和其他信息参数也一样。具体网络参数配置如下。

　　(1)无人机自组网覆盖面积800 m×800 m，通过节点个数反应拓扑复杂度，节点个数为20，40，60，80，100。节点通信半径为250 m。

　　(2)节点位置采用随机分布，每个节点的无线覆盖范围内有5个邻居节点，运动方向随机，其中节点移动速度为10 m/s。

　　(3)节点初始能量为1 000，发送功率和接收功率均为1，睡眠功率为0.1，空闲功率为0.5，过度功率为0.2，过渡时间为0.005 s。传输层采用UDP协议，发送包采用CBR数据流。

　　(4)数据发送在10 s后进行，仿真前10 s用于组网，节点只发送控制分组。

　　本仿真实验为多次实验取平均值得到的结果。

　　2.2仿真结果

　　2.2.1路由开销分析

　　相比于其他路由协议，OLSR协议的运行机制决定了他的路由开销注定是相对较大的，路由的开销是指在数据包由源节点发往目的节点的路径上的路由代价，影响因素有线路占有率、数据收发量、跳数等与协议相关因素，不同的动态路由协议会选择以上的一种或几种因素来计算路由开销。这里选取的是计算总的发送和收到的有效数据包作为衡量开销标准。

　　M-OLSR协议与传统OLSR协议相比，在节点数较少(80节点以前)，也就是拓扑结构和变化相对简单时，两路由协议开销是很接近，差异不大，如图3所示，在节点数较多，拓扑结构和变化相对复杂时，M-OLSR协议具有明显优势。修改后的M-OLSR针对的是通过拓扑的变化控制HELLO消息和TC消息的发时间改进后的M-OLSR相较于原OLSR的路由开销至少降低了10%左右。

　　2.2.2分组投递率

　　分组投递率是评估路由协议的重要指标，指目的节点成功接收的数据包的数量与源节点发送数据包的总数之比，比值越接近1代表网络性能越好。OLSR协议与M-OLSR协议分组投递率比较如图4所示。

　　M-OLSR协议的成功率相对于OLSR协议提高了不少，尤其是在节点数量多，和拓扑变化复杂时。在M-OLSR协议中，在原来协议基础上减少了消息泛洪的冗余，一定程度上减少了消息的拥塞。在SL-MPR选择算法上，考虑了链路变化情况和节点能量问题，确保了提高了链路的利用率和稳定性，仿真显示协议的分组投递率有明显提高。

　　2.2.3能量消耗分析

　　协议的能量消耗这里是统计多次试验中固定节点的剩余能量，通过与节点初始能量值求出的差值。由图5协议能量消耗比较图可知，在能量消耗上两种协议在节点数量较少时相差无几，但是在节点数量较多时M-OLSR协议的能量消耗是优于传统OLSR协议。这是由于在拓扑结构较为复杂时，合适的MPR节点选择使得网络的开销减少，节点生存时间延长，且自适应的HELLO广播消息和TC控制消息洪泛更有效的降低了节点冗余的损耗。能量的剩余量侧面反映了节点的生存时间。

　　3结束语

　　针对于原OLSR协议存在的广播消息机制不灵活和MPR选择算法考虑因素较少等问题，本文在OLSR的优化方案上考虑了节点协议在泛洪时的泛洪周期，使得协议能灵活调整消息泛洪时间，减小拓扑变化给协议带来的影响。在MPR选择算法的优化上综合考虑了多种因素对选择MPR的影响。仿真实验表明，改进后的M-OLSR协议的网络整体性能优于传统的OLSR协议。

　　在无人机组网中，通信和路由问题是一个相当复杂的问题，本文研究的只是其中比较重要的方面，后期的组网研究需要考虑的问题还有很多，这些问题还有待于后续的继续研究。但本文提出的优化方案对于完善无人机组网的路由协议研究具有一定参考意义。

　　参考文献：

　　[1]CLAUSENT H,JACQUET P.Optimized Link state routing proto⁃col(OLSR)[J].RFC,2003,3626.

　　[2]YANG X,SUN Z,MIAO Y,et al.Performance optimization for DSDV in VANETs[C]//Uksim-Amss International Conference on Modelling and Simulation.IEEE,2016:514-519.

　　[3]GORRIERI A,FERRARI G.Irresponsible AODV routing[J].Ve⁃hicular Communications,2015,2(1):47-57

　　[4]MANDHARE V V,MANTHALKAR R R,THOOL V R.Novel Approach for Cache Update on Multipath DSR Protocol in MA⁃NET for QoS Support[J].Wireless Personal Communications,2017:505-519.

　　[5]卓琨,张衡阳,郑博,等.无人机自组网研究进展综述[J].电信科学,2015,31(4):134-144.

　　[6]聂睿瑞.无人机自组网路由协议性能分析与优化[J].信息化研究,2020,46(4):12-16.

　　[7]张靖文,石振刚.车辆自组织网络路由协议研究[J].科技资讯,2021,19(13):6-9.

　　[8]谢勇盛,杨余旺,李操,等.高动态迁移下无人机自组网路由协议研究[J].舰船电子工程,2020,40(12):51-55.

　　[9]羊杰,任智,朱其政.高效的MPR选择算法[J].计算机应用研究,2022,39(1):221-225.

　　[10]胡春.无人机自组网OLSR路由协议研究[D].重庆:重庆邮电大学,2020.

　　[11]董思妤,张洪,王路.无人机自组网OLSR路由协议的优化[J].军械工程学院学报,2017,29(2):67-70.

　　[12]金鑫.大规模移动自组织网络OLSR路由协议优化[D].北京:北京交通大学,2020.

　　[13]张亮,方圆,蔡梦臣,等.基于能量消耗MPR的无人机OLSR路由协议评估[J].信息技术,2020,44(9):157-160.

　　[14]李子恒.无人机自组织网络中的OLSR路由协议的研究与优化[D].哈尔滨:哈尔滨工业大学,2020.

　　[15]Leonov A V.Modeling of bio-inspired algorithms Ant Hoc Net and Bee Ad Hoc for Flying Ad Hoc Networks(FANETS)[C]//In⁃ternational Scientific-Technical Conference on Actual Prob⁃lems of Electronics Instrument Engineering,2017:90-99.

　　[16]SINGHK,VERMAA K,Applying OLSR routing in FANETs[C]//IEEE International Conference on Advanced Communica⁃tions,Control and Computing Technologies,2014.

　　[17]OUBBATI O S,MOZAFFARI M,CHAIB N,et al.ECaD:ener⁃gy efficient routing in flying Ad Hoc networks[J].International Journal of Communication Systems,2019,32(18):e4156.

　　[18]周懿.Ad Hoc网中多信道OLSR路由协议研究[D].成都:电子科技大学,2005.

　　[19]郑伟明.OLSR路由协议研究及仿真[D].成都:电子科技大学,2011.

　　[20]杨彬,刘健,冯家刚.基于拓扑快速变化的OLSR改进路由协议研究[J].计算机工程与应用,2015,51(4):105-109.

　　[21]杨彬.MANET网络中OLSR路由协议研究与改进[D].成都:电子科技大学,2013.