基于无线多跳自组网的混合路由研究

刘颖，唐艺玮，邵小桃，李旭

(北京交通大学 电子信息工程学院, 北京 100044)

基于无线多跳自组网的混合路由研究

刘颖，唐艺玮，邵小桃，李旭

(北京交通大学 电子信息工程学院, 北京 100044)

随着大规模无线多跳自组网在军队通信、应急通信等领域的广泛应用，域路由协议(ZRP)作为一种混合路由协议，其灵活的路由发现和维护策略，使其在大规模网络中的应用受到了更多的关注。ZRP的域内路由协议以及域间路由协议的选取，对协议整体性能影响巨大。面向具有一定拓扑变化的大规模无线多跳自组网，基于传统ZRP框架，优化设计得到改进的域路由协议。改进协议中，域内路由协议采用具有更高路由有效性以及较小资源消耗的主动路由策略，域间路由协议则通过增加过期路由缓存机制降低网络控制开销。通过建模分析验证了改进协议的域内路由具有更高的有效性；通过软件模拟平台NS2仿真，验证了改进协议具有更优的性能。

通信技术；无线多跳自组网；混合路由；协议性能

0 引言

无线多跳自组网是一种新型的无线网络架构，自组织、易架设、可扩展性强等优势特点使其在军队通信、应急通信等领域得到广泛应用。因无线多跳自组网具有无基础设施，无中心，网络中的节点具有移动性，网络规模可达数百甚至数千个节点的特点，如何保证网络性能，对路由协议设计来说是较大的挑战。目前应用于无线多跳自组网的路由协议主要分为3类：主动路由协议、按需路由协议以及混合路由协议。主动路由协议与按需路由协议均采用固定的路由策略，随着网络规模的扩大，这两种协议均暴露出明显的问题，主动路由协议因其周期性的路由更新产生过大的路由消耗，而按需路由协议则因业务发送前的寻路过程导致全网时延性能较差。域路由协议(ZRP)结合了主动路由策略与按需路由策略，平衡了两者的优缺点，为大规模无线网络中的路由寻找和维护提供了一种更为灵活的解决办法。ZRP草案中给出：域内路由协议(IARP)是一种限制跳数的主动链路状态路由协议,维护到达节点R跳范围内的所有域内节点的路由信息；域间路由协议(IERP)是一种按需路由协议，用以获取到达R跳以外节点的路由。

因ZRP在无线多跳自组网中的应用具有较大的潜力，为了能够使得ZRP具有更优的性能，大量学者对ZRP作出了探索性的优化改进。文献[1-3]对ZRP的性能针对不同的场景与其他路由协议做出了仿真对比分析，仿真结果表明ZRP性能具有较大提升空间。文献[4]中将误比特率作为选路度量值，从而获得质量更优的路由。文献[5]中提出了根据移动速度和节点密度来动态调整区域半径的算法，但运动中的节点移动速度很难估计，导致实际工程中采用该算法动态调整区域半径很难实现。文献[6-8]均针对区域重叠问题提出了改进优化方案：文献[6]提出了动态调整节点发射功率和区域半径的方案，提高分组投递率；文献[7]提出基于位置信息的区域路由协议，但由于需要定位技术支持，使用该方案将提高设备成本和实现复杂度；文献[8]则提出了一种基于簇域机制的ZRP改进协议(C-ZRP)，在域间利用分层结构进行路由查找，从而降低了路由和网络开销，使得协议获得更高的运行效率，但该改进协议同样由于需要地理位置信息辅助路由表的建立和更新，且主要针对的网络规模不是很大的场景，同时需要簇的维护机制，成本高，实现复杂。文献[9]为了减小路由协议开销的同时不影响路由精确度，提出了一种基于鱼眼状态路由协议(FSR)的ZRP改进协议(FZRP)，将FSR的思想运用到IARP中，这种改进协议在大规模网络中，在不明显增加时延的同时节省了开销，但该改进协议并未考虑节点的移动性。文献[10]为降低开销，提出了区域缓存机制，但该机制很难适用于网络拓扑变化快、流量较大的网络中。

尽管上述研究对于ZRP性能均可起到改善作用，但本文认为IARP以及IERP的正确选取是使得ZRP获得良好性能的根本。因此，本文基于传统ZRP框架，结合移动Ad-hoc 网络更优方案(BATMAN)[11]的基本思想以及Ad-hoc 网络按需距离矢量(AODV)路由协议过期路由缓存机制，优化设计得到一种基于BATMAN的ZRP改进协议(ZRP-B)。ZRP-B首先采用了一种新的基于BATMAN协议的IARP，该协议可及时扩散域内链路信息并形成域内路由[12]，相比传统ZRP协议：域内路由有效保持时间更长，且节省了重新计算路由表的资源消耗；增加了域间过期路由缓存机制，通过对过期路由的充分利用，避免了短时间内反复多次通过洪泛的方式寻路带来的不必要开销。通过软件模拟平台NS2对协议性能进行仿真验证，仿真结果表明改进协议可有效地降低时延，对路由开销稍有改善。

1 改进协议ZRP-B

1.1 ZRP存在问题

ZRP域内主动路由是一种链路状态路由协议，邻居维护消息与路由更新消息具有相同的周期且分开完成，且每个节点在接收到域内路由更新包后均需要重新计算路由表，资源消耗大，处理时延长，路由收敛性差。某条链路状态经几跳传输以后很可能已经失效，这就导致了路由更新消息中的链路信息陈旧，有效性差，影响整体路由质量，进而会增大端到端时延、投递率等；域内邻居维护消息与主动路由更新消息均是以相同周期发送，这种方式使得邻居维护消息与路由更新消息做了重复性的工作，浪费了网络资源。

为了解决上述域内路由存在的问题，本文提出的改进协议中取消了邻居维护消息，网络中的每个节点周期性发送路由包，域内节点接收到路由包以后直接继续广播路由包，使得域内节点能够及时获取邻居信息以及到达域内其他节点的路由，提高域内路由有效性。

除上述问题外，在传统ZRP路由机制中，路由具有一定的生存时间，这意味着路由过期删除以后节点再次需要到同一目的节点的路由时，需要再次启动寻路过程。若本次寻路与上一次寻路间隔时间较短，节点运动范围有限，大规模全网广播寻路消息是不必要的，会造成网络资源浪费[13]。

为了减少域间寻路不必要的转发，改进协议中将过期的域间路由进行缓存，在短时间内再次需要到达该目的节点的路由时，无需全网搜索，只需将搜索方向限定在上一次获取路由的下一跳节点方向，从而减少无用的转发。

1.2 ZRP-B具体算法描述

1.2.1 域内路由协议

1)源节点生成并广播IARP路由包。源节点周期性地广播IARP路由包来通知域内节点发现它的存在。源节点需将本机地址添加到路由包中的路由区域，将生存时间(TTL)值设为区域半径值R(单位为跳数)。

2)域内节点接收并转发IARP路由包。

①更新路由表。接收到IARP路由包的中间节点将本节点地址顺序添加至IARP路由包路由区域内，并记录下路由区域内的路由及链路信息，更新本地路由表，继续步骤②；

②缓存IARP路由包信息。查看IARP路由包信息缓存表，若已接收过同一源节点发来的相同序列号的路由包，则将该路由包丢弃；否则，缓存路由包信息，缓存内容包括：源节点地址和包的序列号，继续步骤③；

③更新IARP路由包TTL值。更新路由包中TTL值，若TTL值小于等于0，则将该路由包丢弃；否则，向邻居节点广播IARP路由包。

图1为一个区域半径为2的IARP例图。节点S到期广播IARP路由包，在IARP路由包的路由区域中添加本机地址，并将TTL值设为2；A、B、C、D接收到IARP路由包，并分别将本机地址添加至路由区域，分别记录下链路S-A、S-B、S-C、S-D，并更新到节点S的路由，然后查看缓存中是否记录该包信息，若有，则丢弃；否则，更新TTL值，此时TTL值为1，为大于0的值，因而继续广播该路由包；下面以A节点为例，节点A继续广播包，节点S、G、C均会收到，节点S、C已收到过该路由包，因此节点S只会记录下链路S-A，节点C会记录下链路S-A和A-C，并分别更新到达节点A的路由，然后节点S和节点C将包丢弃；节点G收到路由包，更新TTL值，发现TTL值为0，记录下链路S-A和A-G并更新到节点A与节点S的路由以后将该路由包丢弃，其他节点接收到域内路由包具有相同处理过程。

图1 IARP例图Fig.1 Example of IARP

1.2.2 域间路由协议

1)启动IERP. 源节点产生数据包，首先查看本节点路由表中是否含有到目的节点的路由条目，若有，则直接发送；否则，查看过期路由缓存表中是否有到目的节点的路由条目，若有，生成路由请求(RREQ)包，并发送至该缓存条目中的下一跳；否则，生成RREQ包，并边界广播。

2)中间节点转发处理IERP RREQ包。

①缓存IERP RREQ包。中间节点接收到IERP RREQ包后，首先查看本节点的请求缓存中是否存在该RREQ包的相关信息，若存在，则将该RREQ包丢弃；否则建立到达源节点的反向路由，并将该请求包的相关信息添加至缓存中，主要包括请求源节点、目的节点、请求包ID，继续步骤②；

②转发RREQ包。中间节点首先查看目的节点是否位于本节点区域内，若在则将RREQ包单播至目的节点；否则，将上一跳节点的区域内节点标记为已覆盖，并查看RREQ包的多播树节点地址区域是否有本节点的地址，若有则将原RREQ包中多播树节点地址区域的所有地址修改为可到达本节点所有边界节点的邻居节点地址，并将本节点地址顺序添加至源路由列表中，继续边界广播包。

3)目的节点响应RREQ包。目的节点生成路由响应(RREP)包，并沿反向路由将该RREP包单播给源节点。

图2为一个区域半径为2的IERP例图。节点S第1次需要一条到节点J路由(路由缓存中没有到节点J路由的相关信息)，节点S将进行边界广播路由请求包(RREQ报文沿虚线箭头方向向外广播)，其中节点S的邻居节点A、B、C、D位于边界广播树上，它们的地址将被添加至RREQ包的多播树节点列表中；邻居节点M不在边界广播树上，于是节点M收到RREQ消息以后，发现自己缓存中没有该RREQ消息相关信息，于是记录下该RREQ消息信息，然后查看RREQ消息中的边界广播树节点地址列表发现自己不在其中，于是将包丢弃不再继续广播；节点A、B、C、D接收到RREQ包，首先同M记录下RREQ包信息，然后发现自己在边界广播树节点地址列表中，节点A、B、C查看域内路由，没有到节点J的路由，于是继续边界广播RREQ包，而节点D发现节点J位于自己的路由区域，于是将 RREQ包单播发送至节点J，同时继续边界广播RREQ包，沿路的进行转发的节点均会按顺序将本节点地址添加至路由请求包的源路由列表中；目的节点J收到路由请求包，将创建路由响应包，将路由请求包中的源路由列表复制到路由响应包中，并按照反向路由方向(J-F-D-S)将包发送至源节点S，源节点S将到达节点J的路由(S-D-F-J)缓存在域间路由表中，设置过期时间，然后可向节点J发送数据。一段时间以后，域间路由表中节点S到节点J的路由过期，于是节点S将到节点J的路由缓存至域间过期路由缓存中，并设置过期移除时间(本次过期将删除该条路由)。在此期间内节点S再次有到节点J的数据需要发送，本次节点S首先查看路由表中是否有到节点J的路由，没有查到，于是查看域间过期路由缓存，发现有到节点J的路由，于是节点S直接沿路由S-D-F-J单播路由请求包至节点J，节点J再生成路由响应回复节点S，完成本次路由查找过程。

图2 IERP例图Fig.2 Example of IERP

1.2.3 路由维护相关机制

1)断链维护。若节点在发送数据包过程中，若检测到断链，节点将首先删除本地链路状态表中存储的该条链路以及路由表中的相关路由表项，通过链路状态表重新计算相关路由。若仍存在可到达该数据包目的节点的路由，则更新数据包路由区域路由，继续转发包；若没有，则将包丢弃，并生成路由错误(RERR)包，在包中添加断链信息，然后将RERR包广播，TTL值设为区域半径值R，用以通知域内的节点该条断链。

2)域间路由过期处理。当节点路由表中一条到达域外节点的路由过期后，将该条路由信息在过期路由缓存中缓存，并从路由表中删除该条路由信息。过期路由缓存定时到期，过期路由将从过期路由缓存中被删除。

2 域内路由有效性分析

本文使用节点存储的平均链路有效保持时间作为路由有效性的衡量标准，定义为链路平均保持时间与链路信息传递平均端到端时延(包括处理时延与传输时延)之差。

(1)

(2)

ZRP-B IARP中，域内路由包发送周期与传统ZRP IARP中路由更新消息周期相同，为T. 由于源节点不携带与邻居节点间的链路信息，因此可直接生成路由更新包，并发送，节点在接收到来自其他节点的域内路由包以后，无需重新计算路由，可直接记录下路由更新包中的路由信息，并直接转发。因此域内链路信息在中间节点平均驻留时间近似为0，因此网络中的节点与邻居节点之间的链路信息到达域内k跳的节点所需平均端到端时延为

(3)

则ZRP-B IARP中节点存储的平均链路有效保持时间为

(4)

经上述分析可知ZRP-B域内路由有效性高于传统ZRP.

3 ZRP-B仿真与分析

3.1 仿真环境

本文基于软件模拟NS2平台对ZRP-B进行仿真。由于混合路由协议的产生主要是为了适应大规模且网络拓扑变化较快的场景下，因此，本文仿真中设置具体仿真场景参数如表1所示。

表1 仿真场景参数Tab.1 Parameters of simulation scene

根据上述表格设置的场景参数，使用NS2下的移动场景生成工具，选用随机路点模型生成移动场景，并使用流量生成器采用等概率随机产生每对连接的收发节点的方式生成流量场景。

为提高仿真数据可靠性，针对表1场景参数设置生成多组移动场景文件与流量场景文件进行多次试验，最终通过平均仿真结果来估计路由协议性能。

3.2 仿真结果及分析

通过仿真结果，本文主要从平均端到端时延τ、包投递率ρ以及控制开销占比η3个方面对ZRP-B与传统ZRP进行对比分析。

如图3所示，ZRP-B的端到端时延明显优于传统ZRP. 由第2部分路由有效性分析知，当ZRP-B与ZRP具有相同更新周期的情况下，ZRP-B所获得的域内路由有效性更高，因而可有效降低发包过程中因路由质量导致的重传概率，进而降低了整体的端到端时延。

图3 ZRP与ZRP-B平均端到端时延对比图Fig.3 Average end-to-end delay comparison of ZRP and ZRP-B

图4 ZRP与ZRP-B投递率对比图Fig.4 Delivery ratios of ZRP and ZRP-B

图5 ZRP与ZRP-B路由开销对比图Fig.5 Routing overheads of ZRP and ZRP-B

图4为两个路由协议投递率的对比关系，从图4中可以看出，ZRP-B投递率相对传统ZRP稍有提高，这是因为ZRP-B获得的路由具有更好的有效性，降低了数据包发送途中因路由失效或中断导致丢失的概率。

图5为仿真得到的ZRP与ZRP-B路由控制开销占比对比图。两种协议在3.1仿真场景设置之下，IARP开销基本相当，而ZRP-B的IERP增加了过期路由缓存机制，有效减少了域间路由寻路过程洪泛导致的开销，因此ZRP-B相比传统ZRP协议路由开销稍有减少。

4 结论

本文针对传统的ZRP协议在域内路由有效性、资源消耗以及域间寻路开销方面的不足之处，提出了一种改进的混合路由协议ZRP-B，通过采用类似BATMAN的主动路由策略以及域内断链维护提高了路由有效性，减小了资源消耗，降低了端到端时延，同时通过增加域间过期路由缓存机制降低了路由控制开销。通过仿真结果和对比分析，改进协议ZRP-B在整体性能上优于传统ZRP，尤其在时延方面改善显著。

References)

[1] Loutfi A, Elkoutbi M. Evaluation and enhancement of ZRP performances[C]∥International Conference on Multimedia Computing and Systems. Ouarzazate, Morocco: IEEE, 2011.

[2] Gandhi S, Chaubey N, Shah P, et al. Performance evaluation of DSR, OLSR and ZRP protocols in MANETs[C]∥International Conference on Computer Communication and Informatics. Coimbatore, India: IEEE, 2012.

[3] Khatkar A, Singh Y. Performance evaluation of hybrid routing protocols in mobile ad hoc networks[C]∥International Conference on Advanced Computing and Communication Technologies. Rohtak, India: IEEE, 2012:542-545.

[4] Yelemou T, Meseure P, Poussard A M. Improving ZRP performance by taking into account quality of links[C]∥IEEE Wireless Communications and Networking Conference. Bratislava, Czechoslovakia: IEEE, 2012:2956-2960.

[5] 黄小岭.基于节点密度和速度的新型路由协议ZRP-DV研究与仿真[J].电脑知识与技术,2010,6(9):2115-2118. HUANG Xiao-ling. Ad Hoc network routing protocol ZRP research and simulation[J]. Computer Knowledge and Technology,2010, 6(9):2115-2118.(in Chinese)

[6] 杨羽.基于ZRP的Ad Hoc网络路由协议的优化研究[J].辽东学院学报:自然科学版,2009,16(3):227-231. YANG Yu. ZRP-based optimization for Ad Hoc routing protocol[J]. Journal of Eastern Liaoning University:Natural Science, 2009,16(3):227-231. (in Chinese)

[7] 施荣华,罗棋峰.一种MANET中基于位置信息的ZRP路由协议[J].湖南大学学报:自然科学版,2009,36(8):38-42. SHI Rong-hua,LUO Qi-feng. Location-aided ZRP in MANET[J]. Journal of Hunan University:Natural Science, 2009, 36(8):38-42. (in Chinese)

[8] 付光辉.基于簇域机制的ZRP改进研究[D].重庆：西南大学,2011. FU Guang-hui. The research of the zone routing protocol based on cluster[D]. Chongqing: Southwest University, 2011. (in Chinese)

[9] 樊琛洁.Ad Hoc网络路由协议FZRP协议研究[D].西安：西安电子科技大学,2009. FAN Chen-jie. The research of Ad Hoc network routing protocol FZRP[D]. Xi’an:Xidian University,2009. (in Chinese)

[10] 朱丽亚,冯军,陈彦辉，等.区域缓存机制在ZRP协议中的应用[C]∥2005年中国西部青年通信学术会议.成都：中国通信学会，2005:388-391. ZHU Li-ya,FENG Jun,CHEN Yan-hui, et al. Application of zone caching scheme in ZRP[C]∥2005 Western China Young People Conference on Communication Technology. Chengdu: China Institute of Communications, 2005: 388-391. (in Chinese)

[11] Sanchez-Iborra R, Cano M D, Garcia-Haro J. Performance evaluation of BATMAN routing protocol for VoIP services: a QoE perspective[J]. IEEE Transactions on Wireless Communications, 2014, 13(9):4947-4958.

[12] 申爽,李绍文,罗军. 无线mesh网络B.A.T.M.A.N.adv路由协议的分析与优化[J]. 微计算机信息,2012(10):327-329. SHEN Shuang,LI Shao-wen,LUO Jun. Analysis and optimization of wireless mesh network B.A.T.M.A.N. Adv routing protocol[J]. Microcomputer Information, 2012(10):327-329. (in Chinese)

[13] Koyama A, Honma Y, Arai J, et al. An enhanced zone-based routing protocol for mobile ad-hoc networks based on route reliability[C]∥International Conference on Advanced Information Networking and Applications. Vienna, Austria: IEEE Computer Society, 2006:61-68.

Hybrid Routing Protocol for Wireless Multi-hop Ad Hoc Networks

LIU Ying，TANG Yi-wei，SHAO Xiao-tao，LI Xu

(School of Electronic and Information Engineering, Beijing Jiaotong University, Beijing 100044，China)

Since the large-scale wireless multi-hop ad hoc networks have been widely used in military communications, emergency communications and other fields, the zone routing protocol (ZRP), as a hybrid routing protocol, has been paid more attention in the large scale network application because of its more flexible routing discovery and maintenance strategy. The selection of intrazone routing protocol and interzone routing protocol of ZRP has great impact on the overall protocol performance. An improved zone routing protocol based on the traditional ZRP framework is proposed for large-scale wireless multi-hop ad hoc network that has certain topological changes. In the improved protocol, the intrazone routing protocol uses a more effective and less resource consumption routing strategy, and the interzone routing protocol uses an expired routing cache mechanism to reduce network overhead. The modeling and analysis results show that the improved routing protocol has higher validity. It is verified through NS2 simulation that the improved protocol has better performance.

communication technology; wireless multi-hop ad hoc network; hybrid routing protocol; protocol performance

2016-04-05

国家自然科学基金项目(61371068)；国家“863”计划项目(2015AA01A705)；国家科技支撑项目(2014BAK02B04)；中央高校基本科研业务费专项资金项目(2014JBZ002)

刘颖(1964—)，女，教授，博士生导师。E-mail: liuying@bjtu.edu.cn

TN915.04

A

1000-1093(2017)01-0184-06

10.3969/j.issn.1000-1093.2017.01.024