魏 涛，张治国

(河南工程学院 计算机学院，河南 郑州 451191)

与传统的WLAN相比，MESH是一个多跳性的网络，任何无线设备节点都可以作为无线接入点.无线MESH网络更加注重网络的中继多跳能力，能实现更加灵活的组网方式，数据包可以根据网络的情况，路由到与其最近的下一个节点进行，不一定非要通过网络中的单点传输数据.它与传统的点到多点的无线接入方式相比有很多优点[1].MESH本质上属于移动自组网络(Ad hoc 网络)，但与Ad hoc比较，其网络节点的移动性较弱，拓扑变化较小.这种组网方式节省了网络建设初期的基础设施投资.另外，无线MESH网络已作为解决“最后一公里”的网络接入问题的方案写入IEEE标准之中.

MESH网络路由算法一直是研究的热点和难点.近年来，有许多新的路由协议方案提出[2].由于MESH网络本质上是一种特殊的Ad hoc网络，所以部分传统的Ad hoc网络路由协议在MESH中仍然可用，如AODV，DSR，DSDV等路由协议.本研究首先分析了应用于MESH网络中的路由协议，然后在AODV协议的基础上提出了一种新的路由算法，即利用多径路由与在多路径之间随机选择的路由，仿真结果表明这是一种有效的路由算法.

1 Ad hoc路由协议分析

应用于Ad hoc网络的路由协议大体上可以分为3种类型：(1)先验式的路由协议，如基于目的序列号距离矢量(DSDV)协议；(2)反应式的路由协议，如AODV，DSR等协议；(3)混合式的路由协议，如ZRP[3]协议，混合式的路由协议是先验式路由协议和反应式路由协议的组合.

1.1 先验式路由协议

先验式路由协议也被称为表驱动路由选择协议，也就是网络中的每个节点都需要维护本节点到其他节点的路由信息，所有节点都要定期更新路由表以反映网络拓扑的变化.如果源节点要发送报文，可以立即得到到达目的节点的路由信息.显然，先验式的路由协议在网络拓扑变化不大的情况下性能较好，但如果网络拓扑变化较大，则各节点需要频繁地发送路由检测信息，从而会占用很多网络资源，开销很大.显然，对于无线网络而言，由于其拓扑变化较大，单纯地使用这种路由协议并不适合.

1.2 反应式路由协议

反应式路由协议也称为按需要路由，它并不需要网络中的每个节点都维护实时准确的路由信息，只在需要发送数据时才做路由探测，找到正确的传送路径.这种方式推迟了路由信息的建立，不需要时时探测网络拓扑的变化，因而占用的网络资源较小，网络的利用率也能得到提高.在Ad hoc这种拓扑结构随时间变化很大的网络中，应用反应式路由协议显然是一种较好的选择.但由于在进行数据传输时才寻找路由，所以对单个业务的传输在时延等方面存在缺陷.

1.3 混合式的路由协议

混合式路由协议结合了先验式路由和反应式路由的优点，它的主要思想是网络内的节点维护一个以自己为中心的簇，在簇内使用先验式路由算法，簇外节点的路由使用反应式路由算法.但该路由协议的实施存在困难，如簇的选择、算法的实现有较大的系统开销等问题.

2 AODV路由机制

AODV路由协议是一种反应式的路由协议，当一个移动节点要向其他节点发送数据而本节点的路由表中不存在到达目的节点的路由信息时，就会发起路由发现过程，通过广播路由请求(RREQ)信息来查找相应路由[4]，路由请求报文包括源节点地址、源节点序号、目的节点地址、目的节点序号、上一跳地址、跳数等信息.每个接收到路由请求报文的节点会先建立到达源节点的反向路由信息，然后检查自己是否是目的节点.如果是，则通过反向路由信息向源节点发送路由响应报文；如果不是，则检查自己的路由表中是否有到达目的节点的路由信息，若有，则代替目的节点向源节点发送路由响应报文，路由发现过程结束,否则将更新路由请求报文，并将更新后的报文以广播方式转发出去，直到目的节点收到或路由请求报文超时而报错.在AODV协议中，如果存在多个到达目的节点的路径，源节就点会根据路由请求报文中跳数最小的路径作为最优路径存储到路由表中，丢弃其他的路由信息.

在路由维护过程中，每个路由节点周期性地发送状态通知报文，如果节点在一定时间内没有收到邻居节点发来的状态通知报文，则认为该邻居节点不可达，它马上检查路由表中被使用的该邻居节点的路由信息，并发送路由失败报文.AODV协议不需要维护无用的路由，当网络拓扑变化时，它能及时地发现过期、失效的路由.因此,在拓扑结构变化较大的网络环境中能达到较好的效果.

3 AODV路由改进设计

无线MESH网络的通信链路不像有线网络那样稳定，需要MESH路由协议保证当一条链路有问题时能及时找到新的路径替代，以增强网络的健壮性.同时，为了公平地共享网络资源，当某处出现拥塞时，路由协议要能调整分组路由到负载较轻的链路上.因此,使多路径路由能够很好地分配通信量、平衡负载，成为近年来研究的热点.

图1 路由请求报文从节点1转发到节点5Fig.1 Route request message from node 1 to node 5 forwarding

在传统的AODV路由协议中，只保存了从源节点到目的节点的跳数最小的路径，显然如果每个节点能够保存多条到达目的节点的路径，则当其中的一条路径不可达时，数据包也可通过其他的路径到达目的节点，具体实例见图1.

如图1所示，虽然存在两条路径，即1-2-5和1-3-4-5，但路径1-3-4-5发送信息时，所经跳数多，将会被节点1丢弃.显然如果节点2失效，或由于节点5的移动，超出了节点2的信号覆盖范围，节点1就需要重新发起路由探寻过程.同样在数据传输中，如果所有的数据都经1-2-5路径，发生拥塞的概率将会比较大.上述问题的产生，主要是因为AODV协议采用的是单路径路由，如果采用多路径路由，则会有效地提高网络利用率，减少拥塞现象的发生.

改进后的AODV路由协议采用多路径路由，以下简称为RAODV.在进行路由探测时，如果发现多条能够到达目的节点的路由，则将保存这多条路径信息，在进行路由选择时，将分组转发分散到这多条路径上，从而实现负载均衡,提高分组转发的可靠性.改进后的算法借鉴了随机早期检测[5](RED)算法的思想.RED算法是一种主动队列管理算法，其主要思想是在分组队列发生拥塞之前，利用概率判定机制丢掉部分分组来预防可能发生的拥塞，即分组以概率P被丢弃，概率P的值与当前平均队列的长度有关.

RAODV协议在路由探测阶段，首先广播路由请求报文，而后源节点可能会收到多个路由响应报文，在源节点中，保存多条路径，并且保存从源节点到目的节点的路由跳数，用于在转发分组时确定选择路径的概率.在图1中，节点1发出能够到达节点5的路由探测报文RREQ，此时会收到两条路由响应报文，而且有可能节点3的路由响应报文比节点2的路由响应报文先到达节点1，这是因为节点3中有可能存在有到节点5的路由信息，而节点2中还没有到达节点5的路由信息，需要节点2再次进行探测.RAODV将保存这两条路由信息，当节点1向节点5发送数据时，将从这两条路径中选择一条转发数据包，选择时，跳数最少的路径被选中的概率大，因为在无线网络中，跳数越少表明数据包途经的中间节点数越少.

分裂式多路径协议SMR[6]是基于DSR的多路径路由协议，由于在进行路由探测时需要携带源节点到目的节点的完整路由信息，所以其有效数据负载不大；NDMR[7]路由协议是在AODV协议和DSR协议的基础上改进的多路径路由，研究重点在于发现多条独立的路径，而要发现多条独立的路径需要的路由请求包较多，因而路由建立的时间较长，路由开销也较大，在拓扑变化较快的网络环境中并不合适.RAODV协议并不把重点放在建立独立路径之上，因为路由开销不大，在转发时以随机方式选择转发的路径即可.具体选择哪条路径进行数据包转发可按如下概率来计算：

P=1-(本路径所经跳数)/所有路径跳数之和.

(1)

这样，跳数越小的路径，被选中的概率越大.在进行报文发送时，如果两条路径上到达目的节点的跳数相同，则它们被选中的概率相同.通过生成的随机数与两个相同的概率值比较，使得数据包以相同的可能性在两条路径之间传递.其他的路径也有被选中的机会，因为在传递数据包的时候，从源节点到目的节点，不再是从一条路径传递，而是分散在多条路径上传递数据包，这样使单一路径上出现拥塞的可能性降低，从而可以较好地平衡流量，提高分组传输的可靠性.在路由维护阶段，当跳数最短的路径失效时，将重新启动路由发现过程，而其他路径失效时不作处理.在AODV.cc文件中，计算发送数据时所选路径代码如下：

for (rt=rtable.head(); rt; rt=rtn) //对于每一条路由信息

{intp=1-rt->hops/rtable.counts; //计算每条路由的跳数

if (random()>p) //以随机方式选择路径

{forward(rt, Packet, No_delay);

break;}}

4 仿真结果

性能仿真在Linux系统下的NS2[8]平台进行.50个节点随机分布在500 m×500 m的矩形区域，仿真时间为100 s，传送CBR业务，最大移动速度为20 m/s，分别在节点的停留时间为0 s,20 s,40 s,60 s,80 s,100 s时进行测试.利用工具cbrgen.tcl生成业务场景文件，利用NS自带的setdest生成移动场景文件.仿真比较了DSR协议、AODV协议及改进的RAODV协议的端到端平均时延及分组投递率，如图2和图3所示.

节点移动的速度反映了网络拓扑变化的快慢.从图2中可以看到随着网络节点停留时间的延长，端到端的时延有明显的下降，从图3中可以看出AODV的分组投递率略高于DSR，而改进后的RAODV协议的分组投递率高于AODV协议.

图2 端到端平均时延Fig.2 Average delay of end-to-end

5 结语

多路径路由协议是无线MESH网络中的一个研究热点，多路径路由能很好地平衡通信量、平衡网络负载，具有加快传输速度、减少时延的优点.本研究提出了一种改进的AODV协议，采用多路径路由机制，以从源节点到目标节点跳数的多少为依据选择路径，从实验结果来看，改进后的路由协议在时延和分组投递率方面有了改进.

参考文献：

[1] Akyildiz I F，Wang X D．A survey on wireless mesh network [J].IEEE Communications Magazine,2005,43(9):23-30.

[2] 秦裕斌，陈建华，黄晓．无线MESH网络技术及其应用[J]．通信技术，2009，42(12)：152-154.

[3] 杨羽.基于ZRP的Ad Hoc网络路由协议的优化研究[J].辽东学院学报:自然科学版,2009(3):227-231.

[4] 谢世欢，郭伟．实现Ad hoc按需路由协议的关键技术[J]．计算机应用，2006，26(3)：11-13.

[5] Floyd S,Jacobson V.Random early detection gateways for congestion avoidance[J]．ACM/IEEE Transactions on Networking,1993,1(4):397-413．

[6] 李悦,陈翔.基于Ad Hoc网络的SMR优化算法的研究[J].计算机与现代化，2012(5)：21-24．

[7] Li X F，Laurie C．On-demand node-disjoint multipath routing in wireless ad hoc networks[C]∥In 29th Annual IEEE International Conference on Local Computer Networks.Washington:LCN，2004：419-420．

[8] 徐雷鸣,庞博,赵耀．NS与网络模拟[M]．北京:人民邮电出版社,2003.