无线Ad hoc网络机会路由的实现与仿真

殷亚敏， 徐春秀， 武穆清， 宿景芳， 张 婷

（北京邮电大学 信息与通信工程学院，北京 100876）

0 引言

无线自组织网络Ad hoc网络是由一组带无线收发装置的移动设备组成的多跳临时性自组织网络，由于无有线基础设施支持、组网迅速等特点常为需建立临时通信的特殊场合提供了便利[1]，而Ad hoc网络中节点的移动性和无线网络环境的不稳定性，使路由问题成为研究热点。当前Ad hoc网络路由协议根据不同的路由策略可以分为表驱动路由协议（如：DSDV[2]、OLSR[3]等）和按需路由协议（如 DSR[4]、AODV[5]等）。传统的按需路由协议都是利用一定的算法为数据包选择一条最好的路径（比如利用Dijskstra算法选择最短的路径），然后数据包沿着这条选好的路径依次传送。当链路状况好的时候这类协议能表现出很好的性能，但由于实际无线信道的不稳定性经常使所建路径中的下一跳不可达，导致通信中断、路由重建，使它们的效率大大降低。

机会路由的概念就是为适应实际无线信道的不稳定性而提出的，当链路状况好的时候，它可以利用距离很远的传送，当链路状况不好的时候它又可以利用中间节点的转发，继续向前传。这里实现的应用于无线Ad hoc网络的机会路由协议（WAOR）引入了“机会转发”的思想，该协议采用按需路由方式，并通过数据包的广播和多径路由来增强链路的可靠性，从而提高网络的整体性能。

1 WAOR的设计思想

机会路由不提前选路，它在源节点和目的节点之间建立一个转发节点集，源节点以广播的方式发送数据包，所有转发节点集中的节点收到数据包后以某种规则将其继续广播，直至目的节点。由于数据包的广播容易造成碰撞和有限带宽资源的浪费，在机会路由的设计中，应该限制有可能参加转发的节点数目并尽可能减少重复包的广播。

WAOR在实现中采用了机会路由的思想，通过传统路由建立时的路由请求（RREQ）和路由回复（RREP）机制为数据包建立节点转发列表（FL），这个列表中包含了源节点到目的节点的多条路径。数据包携带FL被广播，只有FL中的节点才可以转发数据包，且只能转发一次。当链路状况好时，WAOR可以利用距离远的传送减少分组的端到端时延；当某条链路中断时，由于数据包的广播和多径的存在，WAOR可以立即利用其它路径使数据包继续传送，而不会向源节点发送路由错误（RRER）消息，也不会重新发起路由查找过程。这样，比起传统的Ad hoc路由协议，WAOR不会因为路由中断丢弃分组，也不会因为路由重建增加端到端时延，同时也不会产生大量路由控制分组增加路由开销，从而可以在一定程度上提高网络性能。

2 WAOR的实现

2.1 Forward List的建立

WAOR中FL的建立借鉴DSR中源路由的建立过程。网络中的每个节点都有一个节点转发列表缓存（FLC），当源节点有数据包要发送时首先查看 FLC中是否有到目的节点的FL，若有，则将其添加到数据包的头部，广播该数据包，若没有，则启动RREQ过程。为了使源节点搜集足够多的有用节点，中间节点对同一RREQ处理多次，目的节点回复多个RREP，源节点按照时间顺序处理优先到达的几个RREP。中间节点记录处理的RREQ的次数，当超过此次数时将不再处理。当源节点收到多个RREP时，将RREP中的节点无重复地添加到FL中。这样建立起来的FL中实际上包含了源节点到目的节点的多条路径，同时由于源节点只处理优先到达的RREP保证了FL中节点的有用性并限制了其数量。

2.2 数据包的处理

由于数据包是以广播的方式被发送的，为了减少重复包的广播，每个FL中的节点对同一数据包只转发一次。实现中，在协议头部为数据包添加了网络层的序列号，在网络中的每个节点添加了记录本节点所收到的数据包信息的链表，节点将记录所收到数据包的源、目的节点地址和序列号以检查自己是否重复接收。当节点收到一个数据包时，所做的处理流程如下：

①检查本节点是否在数据包携带的FL中，若在转向步骤，若不在则转向步骤⑤；

②检查本节点的记录中是否有此数据包的记录，若有，转向步骤⑤，否则转向步骤③；

③将所收到数据包的信息插入到本节点的数据包信息链表中，转向步骤④；

④广播数据包；

⑤丢弃数据包。

2.3 Forward List的更新

由于 FL中包含了源节点到目的节点的多条路径，故WAOR没有传统路由协议中的路由维护机制。WAOR为FLC中的每个FL都设置了定时器，当定时器超时若节点仍有数据包要发送，将重新发起RREQ过程建立FL。

3 NS2仿真及结果分析

NS2是非常适合报文交换网络和无线网络仿真[6]，支持众多协议，在Ad hoc网络仿真方面，它所提供的Nakagami-m信道模型更接近于实际的无线信道，为研究路由协议在实际信道中的性能提供了很大的便利。现采用NS2网络仿真器，将WAOR在Nakagami-m信道模型的不同参数下进行仿真并与DSR和AODV的性能进行了对比。

3.1 仿真场景的建立

信道模型的设置：Nakagami-m模型是NS2新添加的一种无线信道模型，它可以模拟信道的时变特性、设定信道对不同距离有不同程度的衰减。在提出的仿真中信道参数设置如下表所示，其中信道衰落情况根据设置从0到5逐渐变坏。

表1 Nakagami-m模型信道参数设置

仿真环境设置：9个节点分布在1000×1000的正方形区域，位置关系如图1所示。每个节点使用IEEE802.11的MAC层协议。仿真中节点0到8产生一条CBR数据流，包大小为512 Bytes，发包间隔为0.02 s，持续时间为50 s。

图1 节点分布

3.2 仿真结果分析

这里评价路由协议的性能指标主要采用了体现网络可靠性的分组投递率、平均端到端时延以及影响无线网络带宽利用率的路由开销，结果如图2、图3和图4所示。

图2 投递率随信道参数的变化

图3 平均端到端时延随信道参数的变化

图4 路由开销随信道参数的变化

图2给出了无线信道参数变化对分组投递率的影响。从图2中可以看出，随无线信道参数变化，AODV和DSR的分组投递率变化较大，而 WAOR基本不变，且始终接近于100%。这是因为，无线信道参数变差，使节点间链路的不可靠性增强，可能导致AODV和DSR刚建立起来的路由不可用，导致通信中断、分组被丢弃。而 WAOR中数据包是通过多径传输的，当其中某条链路失效，数据包仍可通过其它链路传输而不被丢弃。所以，WAOR在信道参数较差时更能体现其优势。

图3给出了无线信道参数变化对分组平均端到端时延的影响。图3中显示，随无线信道参数变差，AODV和DSR的分组平均端到端时延变化较大，且明显高于WAOR，在某些信道参数下，它们的平均端到端时延已超出上层应用所能容忍的100 ms（图3中只画到了100 ms）；而WAOR的分组平均端到端时延始终低于30 ms，可以满足上层应用的需要。这是因为，无线信道参数变差使得节点间链路失效的概率增加，使AODV和DSR重建路由的概率增加，由重建路由所带来的时延使得二者的平均端到端时延升高。而由于WAOR中包含了源到目的的多条路径，没有路由重建所增加的时延。

图4给出了无线信道参数变化对路由开销的影响。可以看出，当无线信道参数变差时，AODV和DSR的路由开销明显增加，而 WAOR的此项性能基本没有变化。无线信道参数的变差导致节点间链路失效的概率增大，此时，AODV和DSR会向源节点发送RERR消息，源节点会重新建路而洪泛 RREQ消息，从而使路由控制分组大量增加。由于WAOR没有路由维护，只有FL过期时才会重新发起RREQ过程，所以路由控制开销不会因为某条链路的失效而增大。

4 结语

针对无线信道参数变化对Ad hoc网络主要性能的影响，采用机会路由的设计思想，在NS2平台实现了无线Ad hoc网络中的机会路由WAOR。该协议在FL的建立过程中包含了多条路径的转发节点，数据包采用广播的方式被发送，从而增强了链路的可靠性，减小了无线信道参数变差对网络性能的影响。仿真结果表明，此协议能有效地减小由于信道参数变差而导致的链路失效的概率，从而提升了分组投递率，降低了端到端时延，减小了路由控制开销。这对于提高实际应用中无线Ad hoc网络的性能来说是十分有益的。

[1] 侯祥博,王一强,杨金政. 移动Ad Hoc网络技术研究及应用[J].通信技术,2008,42(08)：15-17,20.

[2] CLAUSEN T,JACQUET P. Optimized Link State Routing Protocol(OLSR) [EB/OL].[2003-10-12] (2009-12-12) http：//tools.ietf.org/rfc/rfc3626.txt,2003.10.

[3] 郑创明. Ad hoc网络多目标发送的 DSDV路由协议[J].通信技术,2005,28(04)：6-10.

[4] JOHNSON D,HU Y, MALTZ D. The Dynamic Source Routing Protocol(DSR) for Mobile Ad Hoc Networks for IPv4 [EB/OL].(2007-02-12)[2009-12-15].http：//tools.ietf.org/rfc/rfc4728.txt.

[5] PERKINS C,BELDING-ROYER E, DAS S. Ad hoc On-Demand Distance Vector (AODV) Routing [EB/OL].(2003-01-01)[2009-12-15].http：//tools.ietf.org/rfc/rfc3561.txt.

[6] 韩勇,陈强,王建新. 移动 Ad Hoc网络仿真工具比较[J].通信技术,2008,41(12)：305-307.