基于多传输手段的自组网路由协议研究

张晓东，韩卫占，张平

摘要：为了实现多手段通信资源的全局共用与优化使用，针对通信节点多传输手段的自组网特点，提出了一种基于节点MPR的OLSR路由协议（N-OLSR）。首先对HELLO报文格式进行修改，加入Port字段，根据通信手段的不同，对Willingnes字段的值做出修改，用接口索引来代替接口IP地址，将链路带宽大的信道用大索引号表示。以此为基础，从全局出发制定路由策略，将通信节点作为MPR的选举对象，改变传统方法在每个接口上进行MPR选举的机制。最后，通过仿真实验来测试N-OLSR路由协议的性能。结果表明，改进的协议完成了MPR从接口到节点的转移，降低了源节點将一跳邻居节点选为MPR的频率，从而减少TC报文的产生以及洪泛;改进的路由协议能够减少控制开销，降低丢包率，加快网络收敛速度。研究结果可为多传输手段的移动自组网提供一种可靠的路由协议方案，并且信道带宽越小越能发挥其性能。

关键词：计算机网络;多传输手段;移动自组网;OLSR;节点MPR;接口索引

中图分类号：TP393文献标识码：ADOI： 10.7535/hbgykj.2021yx06002

Research on routing protocol of Ad Hoc Network based on

multiple transmission methods

ZHANG Xiaodong，HAN Weizhan，ZHANG Ping

（The 54th Research Institute of CETC，Shijiazhuang，Hebei 050081，China）

Abstract：In order to realize the global sharing and optimal use of multi-means communication resources，an OLSR routing protocol based on node MPR （N-OLSR） was proposed according to the Ad Hoc Network characteristics of communication nodes with multi-transmission means.First，the format of the HELLO message was modified，the Port field was added，and the value of the Willingnes field was modified according to different communication methods.The interface IP address was replaced by the interface index，and the channel with a large link bandwidth was represented by the large index number.Based on this，the routing strategy was formulated from a global perspective，the communication node was regarded as the MPR election object，and the traditional method of MPR election mechanism on each interface was changed.Finally，the performance of the N-OLSR routing protocol is tested through simulation experiments.The results show that the improved protocol completes the transfer of MPR from interface to node，reduces the frequency of the source node selecting a one-hop neighbor node as the MPR，thereby reducing the generation and flooding of TC packets;the improved routing protocol can reduce the control overhead，decrease the packet loss rate and accelerate the network convergence speed.The research results provide a reliable routing protocol scheme for Mobile Ad Hoc Network with multiple transmission methods，and show that the smaller the channel bandwidth is，the better its performance is.

Keywords：computer network;multiple transmission methods;Mobile Ad Hoc Network;OLSR;node-based MPR;interface index

海上移动自组网是无线自组网（MANET）的一种应用场景[1]，其移动节点由飞机和船只等组成。因其组网环境，节点间只能通过无线通信手段联络，并且移动的节点导致网络拓扑无时无刻在无规则的变化[2-3]。对于本课题，更是急需研究一种主动式的路由协议，能够在多通信手段的移动自组网中表现出良好的网络性能。其中，上述网络具有去中心化、多跳路由、节点多信道和窄带等特点[4]。

OLSR（optimized link state routing）根据MANET的特点[5]，由LS（link state）协议演化而来。OLSR与LS相较而言最重要的便是引入多点中继节点（MPR）机制，优化了洪泛算法，降低了协议的开销[6-8]。MPRs是在广播洪泛的过程中被挑选为转发广播消息的中间节点[9]，MPR节点将会生成TC（topology control）消息并且转发TC消息[10-12]，网络通过周期性的TC消息保持拓扑表更新，通过拓扑表可以计算出全局路由表[13-15]，故研究MPR选举机制对于OLSR性能的提升显得格外重要。

基于单信道的OLSR是研究的一大热门，并且产生了许多研究成果。文献[16]提出基于能量消耗MPR的无人机OLSR路由协议评估，通过分析无人机节点运动速度与能量状态，实施MPR选举前就先预处理高速低能量的节点，在同一意愿值条件下重新以加权方式计算出节点能量消耗，由此获得最优的MPR节点集。文献[17]对OLSR协议进行如下优化：提出了基于节点链路传输质量和移动相似度的优化MPR集选择算法，以加权的综合链路评价指标取代节点连接度作为MPR集选择准则。文献[18]将单接口单通道OLSR协议扩展为多接口多通道OLSR协议，并在多接口多通道OLSR协议上进行分布式通道协商，可以提高网络性能。

对于以节点多传输手段为突出网络特点的海上异构自组网，以上基于接口选择MPR的路由协议研究不能够在异构网中很好地降低协议控制开销，因此上述协议无法直接运用到多传输手段的异构网络中来。针对日益增長的通信节点多传输手段的自组网需求，本文致力于研究一种基于全局的节点MPR路由协议，并且将传输手段带宽不同的因素加入到MPR的选举中来，对路由协议做进一步的优化，尤其在海上需要快速做出反应的情形下，该协议将起到至关重要的作用。

1OLSR路由策略

OLSR作为一种主动式的优化链路路由协议，其全网拓扑图和路由表的建立依赖于OLSR节点周期性的交互控制信息[19]。首先，节点通过定期发送HELLO报文来进行OLSR邻居发现;接着秉承MPR集最小原则，节点在一跳对称邻居中选出MPR节点;最后，MPR节点生成TC消息，并洪泛到全网以生成路由表。其中，HELLO报文只在一条邻居之间传递，某节点的MPR节点集能够覆盖该节点的全部两跳邻居，只有MPR节点有广播TC消息的任务。

1.1邻居发现

如图1所示，在开始阶段，节点A发送的HELLO报文中没携带B的地址信息，故节点B在收到报文后将A设为asymmetric（此时B认为是单向链路），并将邻居地址信息更新在邻居节点表中;当A在收到B的HELLO报文后，A发现了关于自己的地址信息，故将B设为symmetric（此时A认为是双向链路），并将邻居地址信息更新在邻居节点表中;当B再次收到来自A的HELLO报文时，B可以找到关于自己的地址信息，A被B设为symmetric（此时B认为与A形成双向链路）。基于此机制，通过广播HELLO包，网络中的OLSR节点能够建立一跳及两跳邻居信息，并以此完成链路探测。

1.2MPR选举算法

算法流程如下。

步骤1：计算一跳邻居节点的连接度L（i）。

步骤2：将能够到达孤立节点的一跳邻居节点加入到MPR集，删除此MPR节点及已被覆盖的两跳邻居节点。

步骤3：如果两跳邻居节点全覆盖，算法结束。否则，将剩余连接度S（i）高的节点加入MPR集，删除此MPR节点及已被覆盖的两跳邻居节点。返回步骤3。

其中：

L（i）=一跳邻居节点能够到达严格两跳邻居节点的数量。（1）

S（i）=L（i）-已经被覆盖的严格两跳邻居节点数量。（2）

以图2为例做简单说明。

首先，选择能够到达孤立节点4的一跳邻居节点b为MPR，并删除关于b，4和5的信息;在剩余一跳邻居节点中选择剩余连接度高的作为MPR节点，其中a为3，d，e和f为2，c为1，故选择a作为MPR节点，删除相关信息;此时只剩d，c和f，选择剩余连接度为2的一跳邻居节点d作为MPR，删除相关信息。此时两跳邻居节点已全部覆盖，选举结束。

2N-OLSR算法

2.1节点MPR的提出

如图3所示，在异构自组网中，假设节点最多有微波、电台和卫星3种通信手段，也就是说，由于不确定因素可能导致节点失去一种或者两种通信手段。因为原始的OLSR协议运行在接口之上，节点2要与节点4通信时，对于源节点2，节点1可能多次被选为MPR，3条链路都有可能产生TC报文。如此，从节点2到节点4 的通信需要TC报文描述3条链路的链路状态，开销随之变大，路由维护也将占用大量的网络资源。尤其在海上无线窄带通信的情况下，此种MPR选举机制不能表现出良好的性能。

又如另外一种情况，节点2要与节点3进行通信。此时节点2可以通过卫星一跳到达节点3，也可以通过节点1到达节点3。传统的OLSR基于接口选择MPR时，节点2必然会在电台子网中将节点1选择为MPR。而基于节点时，节点2不会考虑将节点1选为MPR，而是通过卫星一跳到达节点3。这样MPR集将变小，拓扑控制报文的数量也随之减少。

针对上述问题，在本文提出的基于节点MPR的OLSR路由协议（N-OLSR）中，以全局的角度，在具有多传输手段的通信节点上进行MPR选举。在N-OLSR中，用接口索引代替接口地址，节点主地址用router-id代替。卫星、电台和微波的接口索引依次为1，2和3。

2.2HELLO报文格式修改

根据传输手段设定Willingness值，加入Port字段，具体修改如图4所示。

08162432

ReservedHtimeWillingnessLink CodePortLink Message SizeNeighbor Interface Address

图4中各字段如下设定。

1）Reserved设为000000000000000。

2）Htime为该节点发送HELLO分组的周期。

3）Willingness为意愿度，表示该节点愿意为其他节点转发信息的愿意程度。

将HELLO分组中的意愿度分为4个等级：0—3，默认情况下，设定

Willingness=0， 从不转发，

1， 电台Default，

2， 卫星Default，

3， 微波Default。（3）

4）Link Code为标识了节点间链路状态类型和邻居状态类型。

5）Port为接口编号，一个节点只有一个IP地址，通过接口编号区分不同网络接口（电台网络接口为1、卫星网络接口为2、微波网络接口为3）。

6）Link Message Size为链路信息长度，起始于当前Link Code，终于下一个Link Code。

7）Neighbor Interface Address为邻居节点地址。

2.3MPR选举算法优化

2.3.1节点MPR的实现

既然要减少拓扑控制消息在异构网中的洪泛，从而降低路由控制消息的开销，那么将消息的扩散控制在产生的起点，将最大程度地完成路由协议的优化。

当接口通过HELLO消息完成邻居的探测之后，节点的各个接口首先判断自己Willingness值，如果非0，各接口将与其他接口通过比较Port字段来修改各自的Willingness值，最后只留一个Willingness非0的接口。例如，电台接口索引Port_Mic<微波接口索引Port_Rad，因此电台接口Willingness置为0，卫星接口索引Port_Sat<微波接口索引Port_Rad，故卫星接口Willingness置为0。之所以这样比较，是因为Willingness的值是根据带宽的大小来进行设置的，微波带宽最大，电台带宽最小。此时，具有多链路的节点在逻辑上只存在一个MPR。

2.3.2MPR选举算法修改

步骤1： 计算一跳邻居节点的连接度。

Li=a+b+c，（4）

式中：a为微波接口的连接度;b为卫星接口的连接度;c为电台接口的连接度。

步骤2：将能够到达孤立节点的一跳邻居节点加入到MPR集，删除此MPR节点及已被覆盖的两跳邻居节点。

步骤3：如果两跳邻居节点全覆盖，算法结束。否则，执行下面的步骤。

①如果剩余连接度不同，将剩余连接度S（i）（计算方法与传统的MPR选举算法一样，即式（2）高的节点加入MPR集，删除此MPR节点及已被覆盖的两跳邻居节点。否则，执行b））。

②比较链路参与度L_join，将L_join值大的节点加入MPR集，删除此MPR节点及已被覆盖的两跳邻居节点，返回步骤3。

其中，L_join表达式如下：

L_join=3×a1×α+2×b1×β+c1×γS（i），（5）

式中：a1表示微波接口的剩余連接度;b1表示卫星接口的剩余连接度;c1表示电台接口的剩余连接度;α，β和γ分别表示微波、卫星和电台接口的业务因子，依经验将其分别设为0.7，0.2和0.1，它们代表着业务从不同链路传输的意愿度。

3仿真分析

3.1仿真参数设置

根据本文背景，采用互联网路由协议运行模拟网络平台进行仿真，仿真软件由网络拓扑绘制软件、协议运行监控软件、网络环境仿真软件、仿真路由协议软件等部分组成。其中，网络拓扑绘制软件如图5所示，网络拓扑仿真时间300 s，HELLO发包间隔5 s，拓扑更新间隔10 s，比较不同网络节点个数的性能时，将节点移动速度设为10 m/s。具体参数配置如表1所示。

图5中存在3种异构子网，分别为卫星、微波和电台。网络拓扑采用全分布式结构，即所有节点地位等同。

3.2仿真结果分析

以表1 的参数设置为前提，通过改变节点的个数和移动速度来增加异构网络的复杂程度。通过图6—图9，分别在收敛时间、端到端时延和协议控制开销（路由收敛时协议数据包个数）3个方面对改进的N-OLSR路由协议和传统的OLSR路由协议进行对比，进而来测试N-OLSR路由协议性能。

1）收敛时间

由图6和图7可知，随着节点数以及节点速度的增加，传统OLSR路由协议和改进的N-OLSR路由协议收敛时间均逐渐变长。但是随着异构网中节点数量变多，节点速度增长，改进的N-OLSR路由协议比原路由协议在收敛时间上表现出来的性能要好，这说明改进的路由协议通过MPR选举机制的改变，降低了MPR集，从而减少了到达同一目的地的路由条目，加快了异构网络的收敛。

2）协议控制开销

由图8可知，随着节点个数的增加，运行N-OLSR路由协议的网络和运行传统OLSR路由协议的网络中的总数据包数均逐渐增加。但是，N-OLSR路由协议的控制开销始终比OLSR路由协议的控制开销要小，并且随着节点数的增加，两者的开销差距逐渐变大。这是由于随着MPR数量的减少，TC报文产生和转发的数量随之减少，大大提高了网络性能。

3）端到端时延

由图9可知，随着节点速度的增长，运行N-OLSR路由协议的网络和运行传统OLSR路由协议的网络端到端时延均变大。但是N-OLSR表现出来的端到端时延比OLSR要小，这是由于随着节点上MPR数量的减少，路由条目随之减少，路由表更新变快，端到端时延随之降低。

4结语

通过对传统OLSR路由协议HELLO报文格式和MPR选举算法的修改，使N-OLSR路由协议能够较好的在节点多传输手段的移动自组网背景中发挥作用。通过仿真分析可知，改进的路由协议较传统的OLSR路由协议，降低了路由的协议控制开销，加快了收敛速度。

首先在HELLO报文中，用索引号代替接口IP，通过这样的方式消除MID消息在网络中的传播，从而降低了协议的开销。然后通过Willingness的设置，使多传输手段的通信节点在转发阶段只具备一个逻辑接口。接着通过修改MPR选举算法，使路由协议从全局的角度选举出MPR，同传统的协议相比，缩减了MPR集，减少了拓扑控制报文的产生和传递，在很大程度上降低了对网络资源的占用，加快网络收敛。

但是此路由协议在负载分担方面还没有完善，对于不同的业务，无法合理地将其分散到不同的信道上，因此在多业务的负载均衡方面还有待进一步研究，这是下一步研究的重点。

参考文献/References：

[1]蒋清健.海上战术移动自组网路由技术研究[J].舰船科学技术，2016，38（1A）：136-138.

JIANG Qingjian.Research on marine tactical mobile ad-hoc networks routing technology[J].Ship Science and Technology，2016，38（1A）：136-138.

[2]吴佳琪，任智，王磊，等.一种基于链路稳定性的最小MPR选择算法[J].小型微型计算机系统，2020，41（11）：2386-2391.

WU Jiaqi，REN Zhi，WANG Lei，et al.Link-stability-based Minimum Multipoint Relay selection algorithm[J].Journal of Chinese Computer Systems，2020，41（11）：2386-2391.

[3]PATHAK S，DUTTA N，JAIN S.An improved cluster maintenance scheme for Mobile Ad Hoc networks[C]//2014 International Conference on Advances in Computing，Communications and Informatics（ICACCI）.Delhi：IEEE，2014：2117-2121.

[4]郭少雄，李正伟，宋志群.基于节点负载等级的自组网AOMDV路由协议改进方法[J].河北工业科技，2021，38（2）：109-115.

GUO Shaoxiong，LI Zhengwei，SONG Zhiqun.Improved method of AOMDV routing protocol in Ad Hoc network based on node load level[J].Hebei Journal of Industrial Science and Technology，2021，38（2）：109-115.

[5]BERRADI H，HABBANI A，MOUCHFIQ N，et al.Improvement of OLSR protocol using the hello message scheme based on neighbors mobility[J].Journal of Communications，2020，15（7）：551-557.

[6]ZHU Qizheng，ZHOU Zhou，YANG Jie，et al.An optimized routing OLSR protocol with low control overhead for UAV Ad Hoc networks[J].American Journal of Networks and Communications，2021，10（1）：6-12.

[7]GUO Xian，YANG Shengya，CAO Laicheng，et al.A new solution based on optimal link-state routing for named data MANET[J].China Communications，2021，18（4）：213-229.

[8]MOHAPATRA S，TRIPATHY T.MM-OLSR：Multi metric based optimized Link state routing protocol for wireless ad-hoc network[C]//2016 International Conference on Signal Processing，Communication，Power and Embedded System（SCOPES）.Paralakhemundi：IEEE，2016：153-158.

[9]孫一凡，米志超，王海，等.基于分簇的拓扑自适应的无人机蜂群OLSR路由协议[J].计算机科学，2021，48（6）：268-275.

SUN Yifan，MI Zhichao，WANG Hai，et al.Cluster-based topology adaptive OLSR protocol for UAV swarm network[J].Computer Science，2021，48（6）：268-275.

[10]熊轲，金鑫，刘强.QL-OLSR：一种基于Q-Learning思想优化的移动自组织网络路由协议[J].北京交通大学学报，2020，44（2）：66-73.

XIONG Ke，JIN Xin，LIU Qiang.QL-OLSR：An optimization routing protocol in MANET based on Q-Learning[J].Journal of Beijing Jiaotong University，2020，44（2）：66-73.

[11]NABOU A，LAANAOUI M D，OUZZIF M.New MPR computation for securing OLSR routing protocol against single black hole attack[J].Wireless Personal Communications，2021，117（2）：525-544.

[12]周亮，周天，周建國，等.基于能量感知的OLSR协议优化研究[J].计算机应用研究，2020，37（sup1）：250-252.

ZHOU Liang，ZHOU Tian，ZHOU Jianguo，et al.Research on OLSR protocol optimization based on energy sensing[J].Application Research of Computers，2020，37（sup1）：250-252.

[13]任智，周舟，吴本源，等.基于优化链路状态路由的低开销拓扑维护算法[J].计算机工程，2021，47（9）：120-127.

REN Zhi，ZHOU Zhou，WU Benyuan，et al.Low-cost topology maintenance algorithm for optimized link state routing protocol[J].Computer Engineering，2021，47（9）：120-127.

[14]杨行芳.移动Ad Hoc网络多径多信道路由协议研究[D].哈尔滨：哈尔滨工业大学，2018.

YANG Xingfang.Multi-Path Multi-Channel Routing Protocol for Mobile Ad Hoc Networks[D].Harbin：Harbin Institute of Technology，2018.

[15]YIN Jun，WANG Lei，CHEN Han，et al.NC-OLSR：A network coding based OLSR multipath transmission scheme for FANETs[C]//2017 4th International Conference on Systems and Informatics （ICSAI）.Hangzhou：IEEE，2017：1007-1012.

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

ZHANG Liang，FANG Yuan，CAI Mengchen，et al.OLSR routing protocol evaluation based on energy consumption MPR[J].Information Technology，2020，44（9）：157-160.

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

LI Ziheng.Research and Optimization of OLSR Protocol in FANETs[D].Harbin：Harbin Institute of Technology，2020.

[18]ZHONG Hui，PU Shengyuan.Analysis and research on OLSR protocol for multi-channel assignment of wireless mesh network[C]//2017 Chinese Automation Congress （CAC）.Jinan：IEEE，2017：2732-2737.

[19]MAKSIMOV V，PANASIUK M. Simulation of OLSR protocol using Network-Simulator 2[C]//2014 First International Scientific-Practical Conference Problems of Infocommunications Science and Technology.Kharkov：IEEE，2014：10-11.