无线Mesh网络多路径路由协议的研究

贾小慧，刘乃安，李晓辉，时　鹏

(西安电子科技大学 通信工程学院，陕西 西安 710071)



无线Mesh网络多路径路由协议的研究

贾小慧，刘乃安，李晓辉，时鹏

(西安电子科技大学 通信工程学院，陕西 西安 710071)

L2MPM路由协议工作在第2层，属于多经路由中的备份路由，但并未考虑主路经与备份路径之间存在链路相交的问题，降低了网络的容错能力。因此，在L2MPM协议的基础上，提出了LD-L2MPM路由协议。该协议通过采用链路不相交策略，在Hello包中添加第一跳和最后一跳字段来确保所选的两条路径是链路不相交。仿真结果表明，与原有协议相比，数据包投递率提高约6%，平均端到端时延降低约5%。

无线Mesh网络；多路径；链路不相交

无线Mesh网络是一种具有自组织、自修复的网络。最大特点是由Ad-hoc的单一型网络节点演变成了由MAP(Mesh Access Point)、MP(Mesh Point)和MPP(Mesh Portal Point)组成的混合型网络节点，其中MAP可给移动用户提供接入Mesh网络的功能[1]。

作为一种新型的无线网络，无线Mesh网络从早期走向成熟，有一系列的关键性技术问题亟需解决。就目前来看，对数据链路层的主要研究工作体现在信道干扰、吞吐量和负载均衡等方面；在网络层，关键点是路由协议的开发，其最终目标是选择业务流传输路由；在MAC(Medium Access Control )层，无线 Mesh 网络中的 MAC 是分布式的，需要互相协调，实现多跳通信[2]。

无线 Mesh 网络是一种多跳中继网络，数据传输时面临如何选择一条快速、稳定、高效的最佳路径的问题。无线Mesh网络路由的设计一般考虑路由判据、容错的多路径路由、扩展性、减少路由开销等方面。本文针对多路径路由协议中存在的链路相交的问题提出了解决方案，可获得更好的时延，提高网络吞吐量，改善负载均衡。

1　无线Mesh网多路径协议

1.1多路径基本概述

无线Mesh网本身就支持节点之间的多路径，在需要传输数据的两个节点之间可选择多条路径。多路径协议的主要目标是能够获取多条高质量的传输路径来增强无线网络性能，当所使用的路径上某链路由于信道质量较差或移动性而失效时，便可选择备份路径中其他路径继续传输。因此，由于无需重新建立路由，端到端时延、吞吐量和容错性都能得到一定的改善。

多路径按照相关性准则可分为3种类型的路径：节点不相关(Node Disjoint Paths)、路径不相关(Link Disjoint Paths)和路径相关(Link Joint Paths)[3]。

1.2多路径协议分类

多路径协议也可划分成两类：一是先应式路由协议，包括MOLSR[4](Multipath Optimized Link State Routing Protocol)、MESH[5](Multipath MESH)；第二类是反应式路由协议，包括AOMDV[6](Ad hoc on Demand Multipath Distance Vector)、AODV-BR[7](AODV Backup Routing)、MSR[8](Multipath Source Routing)。

2　L2MPM协议

2.1L2MPM工作原理

上述协议都在 OSI(Open System Interconnect)参考模型的第三层， L2MPM(Layer 2 Mesh Protocol for Mobile)是一种先应式二层 Mesh 路由协议。网络中所有节点周期性广播Hello包消息来通告网络中其他节点自身的存在，邻居节点收到此 Hello 消息后根据相应的转发规则进行重播。该路由协议的工作原理：源节点通过在网络中周期性地洪泛 Hello 数据包，建立自身的路由表并对路由表进行更新。当网络中的节点需要到目标节点的路由时，L2MPM 路由协议会确定一个到目标节点的最佳本地邻居节点作为下一跳路由[9]。

L2MPM 协议的特点只存储到达目标节点的最优和潜在下一跳，这样一方面可减少存储开销，另一方面，当最优下一跳节点突然离开时，可直接选择潜在下一跳来路由。L2MPM路由协议属于多径路由中的备份路径，但是未考虑路由表中存储的两条路径之间存在链路相交的可能，结果会导致所用路径出现链路错误同时，备份路径也会存在断路的风险。因此，在原有协议的基础上进行多路径的改进，保证主路径与备份路径是链路不相交路径，提高工作效率，减小端到端时延。

2.2L2MPM路由协议优化方案—LD-L2MPM

为使一个节点到另一个节点建立的主路径和潜在路径是链路不相交路径，此次优化方案参考了AOMDV协议的工作原理。这两种路由协议皆是通过逐跳的形式来发现路由，源节点通过选择和添加邻居节点来发现到达目标节点的路径，并使用所选择邻居节点来作为业务流转发的下一跳节点，无需维护整个网络的拓扑及路由信息。因此，LD-L2MPM(Link Disjoint-Layer 2 Mesh Protocol for Mobile)协议在Hello包格式和路由表上做了些改进，在Hello包格式中添加第一跳，在路由表中加入最后一跳字段。在发送Hello包的整个过程中，中间节点均要检查第一跳和最后一跳是否相同，只有第一跳和最后一跳不同才加入路由表，保证每一条路径是链路不相交路径。

图1说明链路不相交的思路，图1(a)在路径发现过程中到B节点时，有两条路径(S-A-B)和(S-C-B)，满足具有不同的第一跳和最后一跳的条件，但是到C节点时，两条路径有共同链路，因此就不属于链路不相交路径，图1(b)中两条路径满足上述条件，为链路不相交路径。

图1　链路不相交策略

2.3LD-L2MPM的路由建立和更新

路由信息表的建立和维护涉及到接收和转发Hello包的过程，本地节点为声明自身的存活性而周期性地广播包含自身物理地址的Hello包。当前节点收到某节点发来的Hello包后，第一步是要判断是否由本身所发的数据包，若是则直接释放，若不是则判断是否是邻居节点发来的Hello包，如果是，且前一跳的地址等于源节点地址，则将第一跳的地址置为该节点MAC地址。若是邻居节点发来源节点自身的Hello包，则进行相关路由信息的建立或更新。如果不是，要在路由表中查找到始发Hello包源节点的路由是否存在，如果路由表中存在到源节点的路径，再将该路径与原有路径比较，看是否为链路不相交路径，如果是链路不相交，就将该路径添加到该节点路由表项中；若路由表项中不存在到发送Hello包源节点的有效路径，则直接将新路径添加到当前节点到源节点的路径表项中。然后，对Hello包进行相关字段的更新，转发给下一邻居节点。

3　仿真测试及分析

利用NS2[10]仿真软件对LD-L2MPM多路径路由协议进行仿真测试，并与L2MPM协议在平均端到端时延、分组投递率等方面进行性能比较。

3.1传输模型选择

本次仿真与以往不同的是，此次在无线传输模型上选取了Shadowing模型，以往则是选取Two-Ray-Ground模型。NS2中实现了3个无线模型，分别是：Free -Space(自由空间)模型、Two-Ray-Ground(双径地面)模型及Shadowing(阴影)模型。这3个模型的主要功能是来监测每个数据包的接收信号，每一个无线节点的接收阈值均存在于物理层中，若是一个数据包的接收信号功率低于此处接收阈值，MAC层会判为错误并丢弃此数据包。Free-Space模型、Two-Ray-Ground模型采用的接收功率公式主要以距离参数来决定，其通信范围是一个理想的环。Shadowing模型[11]包括两部分：一是路径损耗模型；二是反映了距离一定时接收功率的变化。Shadowing模型不再是理想的环模型，而是基于统计的模型，所以节点在接近通信范围边界处只是有可能进行通信，而不是绝对。

3.2仿真参数设置

场景参数设置如表1所示。

表1　参数设置

3.3仿真结果分析

仿真数据比较如图2和图3所示。

图2　平均端到端时延

图2为在不同的数据包发送速率中，L2MPM和LD-L2MPM协议在平均端到端时延的曲线对比图。从图中可看出，随着发包速率的增大，时延也在不断增加，这是因随着发包速率的增加，网络节点出现过载，致使网络中业务流拥塞的几率升高，平均时延也随之增加。而LD-L2MPM协议的平均端到端时延总小于L2MPM协议，说明LD-L2MPM在加入链路不相交的路由选择机制起到了较好的作用，降低了网络时延，提高工作效率。

图3表明，LD-L2MPM协议在分组投递率性能上要优于L2MPM协议，主要是因为L2MPM协议并未考虑到链路相交的问题，使得不同的数据流可能使用相同的链路在传输，导致链路负载加重，分组投递数量降低。随着节点发包率的增加，节点负载加重，会导致缓存队列拥塞而丢弃数据组，两个协议的分组投递率都会随之下降。

图3　分组投递率

4　结束语

本文所提出的LD-L2MPM协议确保所选出的主路经与备份路径是链路不相交路径，在不增加路由开销的基础上，提高网络工作效率，降低端到端时延。利用NS2仿真软件，对L2MPM协议、LD-L2MPM协议进行了仿真测试比较。以上仿真数据曲线表明，LD-L2MPM协议在平均端到端时延、分组投递率方面的性能要优于L2MPM协议。

[1]宋立梅,刘乃安,曾兴雯.无线,Mesh网络路由协议研究[J].电子科技,2008,21(7):30-33.

[2]柴远波,郑晶晶.无线Mesh网络应用技术[M].北京:电子工业出版社,2015.

[3]史晓晨.无线MESH网络多路径路由协议的研究与设计[D].北京:北京邮电大学,2011.

[4]Xuekang S,Wanyi G, X Xiao,et al.Node discovery algorithm based multipath OLSR routing protocol[C].Taiyuan：WASE International Conference on Information Engineering, 2009.

[5]杨艳.WMN多路径路由协议研究[D].南京:南京航空航天大学,2011.

[6]李波,潘进,李国鹏,等.基于NS2的AOMDV路由协议的改进与性能仿真[J].计算机应用与软件,2010,27(2):56-58.

[7]Lee S J, Gerla M.AODV-BR: backup routing in ad hoc networks[C].Chicago:Wireless Communications and Networking Conference, 2000.

[8]乔平安,邵凯,刘运爽.基于无线Ad hoc的多路径多信道路由度量准则[J].电子科技,2015,28(8):60-62.

[9]时鹏.WMN中节点部署算法和网关自适应的设计与实现[D].西安:西安电子科技大学,2014.

[10] 吉祖勤,蔡长安.NS2仿真技术在网络实验教学中的应用[J].实验室技术与管理,2012,28(12):96-99.

[11] 于斌,孙斌,温暖,等.NS2与网络模拟[M].北京:人民邮电出版社,2007.

Research on the Multi-Path Routing Protocol in the Wireless Mesh Network

JIA Xiaohui, LIU Naian, LI Xiaohui, SHI Peng

(School of Telecommunications Engineering, Xidian University, Xi’an 710071, China)

The L2MPM (Layer 2 Mesh Protocol for Mobile) routing protocol works on the second layer which belongs to the backup route in the multi-path routing, but it does not consider the link intersecting between main and backup path to reduce the tolerance of the network. An LD-L2MPM (LINK_DISJOINT_L2MPM) routing protocol based on L2MPM is proposed in the paper, which adopts the strategy of non-intersecting link that adds the first hop and the last hop to the packet of Hello to ensure that the two paths selected by the protocol are link-disjoint．The simulation results show that the rate of packet delivery increases by about 6%, and the average end-to-end delay reduces by about 5% compared with those of the original routing protocol.

wireless mesh network; multi-path; link-disjoint

10.16180/j.cnki.issn1007-7820.2016.08.036

2015-11-11

陕西省科学技术研究发展计划基金资助项目(2014K05-13)

贾小慧(1991-)，女，硕士研究生。研究方向：扩频技术与通信与对抗。刘乃安(1966-)，男，教授。研究方向：无线扩频通信与射频电路。李晓辉(1972-)，女，博士，教授。研究方向：宽带无线通信。

TN915.04；TP393

A

1007-7820(2016)08-124-03