一种支持高速移动自组织网络的路由协议*

杨共燕,邝育军,隆克平

(电子科技大学 光互联网与移动信息网络研究中心,四川 成都 611731)

移动自组网（MANET）是由一系列移动终端组成的无固定基础设施的多跳自组织网络系统[1]，其拓扑结构因为节点电量不足或是移动而变化，所以MANET的路由协议与传统网络的路由协议有着很大的区别。

目前,移动网络中较成熟、较典型的路由协议有DSDV、DSR、AODV、ZRP 等[2]。 其中，AODV 路由协议[3]是一种经典的按需路由协议，它在一定程度上比其他协议有较小的路由开销和更好的扩展性能，但是这种路由协议在网络拓扑频繁变化的情况下,路由断链的几率很大，其网络性能下降很快，无法保证较高要求的服务质量。

针对高速移动自组网的特性，本文提出一种基于AODV的改进路由协议，即IMAODV，它在路由度量值、断链修复策略以及HELLO消息机制上做了修改，使之能有效地降低网络延迟，提高网络的吞吐量。通过NS2仿真可以看到，本文提出的IMAODV路由协议与传统的AODV路由协议相比具有一定的优势：它既能降低中高速移动自组网的网络延时，又能在一定程度上提高网络吞吐量；同时，IMAODV路由协议能够较好地适应无线网络环境，有效提高网络性能。

1 IMAODV路由算法

1.1 AODV

传统自组网路由协议可分为主动路由协议和按需路由协议[4]，由于移动自组网存在着动态多变特性，主动路由协议应用在移动网络中有着明显的缺陷，所以实际中经常使用的都是按需路由协议[5]。

AODV是Ad-hoc网络的经典路由协议，它是由路由发现和路由维护组成。路由发现过程如图1所示。而在路由维护中,节点通过周期性地发送HELLO包维持与邻居节点的连接，若一段时间后还未收到邻居节点的HELLO包，则开始链路修复过程。若本节点离目的节点较近，则进行本地修复，发送RREQ进行路由重建，当中间节点有到不可达节点的有效路由或者不可达节点收到此RREQ后就发送一个路由回复RREP给源节点，这样路由就得到了重建。若链路修复失败，则节点向所有的邻居节点广播RERR包，RERR包中的不可达节点列表不仅包括了链路断开的邻居节点，还包括了以此邻居节点作为下一跳的所有目的节点。通过RERR的广播，其他节点便知道链路断开了，当此包传到源节点时，将进行新一轮的路由发现。

1.2 IMAODV路由算法

AODV虽然也能适应动态变化的网络，但是它的机制并不灵活,不能根据网络环境动态调节发送频率，再者路由度量值仅仅考虑了跳数信息，且路由单一，所以不能满足移动环境较为复杂或移动速度较高的网络环境。为了更好地满足移动自组网的服务要求，本文将针对高速移动环境提出的IMAODV，在AODV协议的基础上做出以下改进，以改善网络的吞吐量和平均端到端延迟。

1.2.1 节点度量值的选取

以跳数为度量的AODV,容易造成大量数据通过少量节点传输引起网络的阻塞，而导致分组延时过大，吞吐量下降[6]。为了缓解这种情况，本文在路由度量值的选取中将考虑以下因素：

节点移动速度：节点的移动速度越大，链路越不稳定，所以在选择路由时要选移动速度较低的中间节点，避免因节点移动造成断链的路由重启过程，以降低网络开销。

延迟：路由过程中，延迟越小，数据传输才能显示其时效性。

跳数：跳数越少，在某种程度上，所消耗的网络资源越少。

考虑到节点的计算复杂度，路由度量值：

其中hop代表跳数，nodenum表示网络总的节点数，delay代表上一跳节点到本节点的延迟，speed代表本节点的移动速度，maxspeed代表网络中节点的最大移动速度，w1、w2和w3分别代表权值,其中，w1+w2+w3=1，本协议中w1、w2和w3的值分别取为 0.7、0.2和 0.1。当metric的值越小，路由链路的稳定度越高，网络延迟越小。

1.2.2 节点功能的改进

传统AODV中源节点只保留一条到目的节点的路由，当主路由上的链路断开时，源节点重新开始进行路由发现几率较大，容易造成过大的路由开销和较大时延。为改善这种情况，本文提出的IMAODV，利用无线通信中广播信道侦听到的相邻节点发给其他节点的RREP信息建立备用路由[7-8],通过增加节点的功能,使之具有监听路由控制信息的能力。

1.2.3 Hello机制的改进

IMAODV中对HELLO消息做两方面改进：(1)是为HELLO消息设置了一个标志。初始化为TURE，节点发送HELLO消息，当节点有路由或数据信息需要广播时，标志设为FALSE。如果HELLO发送周期再次到来，先检查标志，如果为FALSE，则改变状态为 TURE后不作任何处理，直至下一个周期的到来，再继续检查标志；当标志为TURE时，则发送HELLO消息，同时每个节点在接收路由包或是数据包的时候，要更新邻居的生存时间，这样可以降低发送HELLO消息的开销。(2)由于节点的移动，会造成网络拓扑的变化，HELLO消息的固定发送肯定不能有效地捕捉到网络拓扑信息，为了保证链路的有效性，本文将根据节点自身的速度来调节HELLO包的发送频率,发送频率与节点的移动速度成正比，流程如图2所示。

1.2.4 链路修复的改进

由于IMAODV路由中每个节点对路由应答包具有侦听功能，所以主路径上节点的一跳邻居都能够侦听到此包，所以都能通过主路径上的节点建立到目的节点的路由，这样就形成了多个到目的节点的备份路由。当主路由上的某条链路断开时，便可以通过路由请求RREQ进行局部修复。为了减小路由请求的开销，本文设置了路由请求的生存期为2跳，中间节点收到路由请求时，若路由生存期不为0，则查找自己是否有到目的节点的路由。若有，则按原AODV的方式进行应答，若没有则继续广播路由请求消息，直到生存期变为0时丢弃包。当局部修复失败时，节点再广播路由错误包。

图2 HELLO消息发送机制

1.2.5 IMAODV路由协议

IMAODV在路由请求、路由应答以及路由表中添加metric字段，以记录路径上每个节点的累计路由度量值。当源节点需要通信路由时，先初始化metric为0，再广播这个RREQ包启动路由发现过程。中间节点的路由表段中添加一个rt_metric，记录从源节点到该节点路径上的路径度量最小值，中间节点收到非重复的RREQ包时，将自身的metric值累加到路由RREQ中的rq_metric上，再继续转发。如果节点已经收到了同一源节点相同的广播ID的RREQ，且包的目的序列号大于路由表中序列号，则直接更新路由，若相等就通过比较rq_metric与 rt_metric，选较小者作为本路由表项中的 rt_metric，即更新路由表项再转发包。当路由请求包到达目的节点时，目的节点将选择一个拥有较小metric的路由，发送路由回复RREP。路由应答是以单播的方式传送，接收到此包的节点时,首先根据接收包中下一跳信息判断本节点是监听节点还是正常的路由应答节点,如下一跳 ID不等于本节点ID，则本节点是监听节点，此时记录到目的节点的路由后不再转发,否则是主路径上的节点，则按照传统AODV路由应答的方式进行处理。图3为IMAODV路由建立的流程。

在图3中，路由建立或更新是根据路由序列号和路由度量值来决定的。如果是第一次收到路由请求包，则建立路由；若收到请求包中的目的节点序列号大于路由表中存储的目的节点序列号或是等于路由表中存储的目的序列号，但路由表中的路由度量值大于请求包中的路由度量值，则更新路由。“是否忽略”检查是否收到重复的包，若是，则丢弃；否则更新路由表和请求包信息再转发。

2 仿真分析

2.1 仿真环境

仿真工具采用NS-2.30[7]版本，网络的拓扑环境是一个包含50个移动节点的网络模型，节点随机分布在1 000 m×1 000 m的正方形区域内，并设置节点的移动速度在0 m/s～40 m/s之间,每个节点的无线接口带宽为2 Mb/s,有效无线发射范围为250 m,链路层采用无线802.11 MAC协议,在50个节点中随机产生4对恒定比特率的CBR连接，每个分组的长度为512 B,每秒发送4个包,为了考察改进的协议在网络仿真环境中的性能，本文将模拟节点速度在0～20 m/s时由于停留时间(pause time)、网络中节点间最大连接数以及节点的速度的变化对网络吞吐量的影响，还有节点移动速度变化对网络平均端到端延迟的影响,设置了在相同环境下与AODV作比较，给出了仿真结果。

2.2 仿真结果及性能分析

图4显示了端到端延迟与节点移动速度的关系，由此可知IMAODV协议的平均端到端延迟随节点移动速度的增大优于AODV协议，其原因是在路由度量中考虑了每一跳的延迟，且改进的HELLO机制的发送频率与节点移动速度有关，能较快地发现路由断链情况并做出相应处理。图中节点最大速度为5 m/s时，由于处于低速状态，IMAODV优势并不突出，较AODV的延迟大，但是随着节点的移动速度的增加，IMAODV的平均端到端延迟低于AODV；当节点最大移动速度达到40 m/s时，IMAODV的延迟约为 AODV延迟的 1/2。从总体来看,随着节点移动速度的增加，IMAODV延迟有所下降。

图5中IMAODV在路由度量值和HELLO消息机制中考虑到节点移动速度的影响，并且节点具有侦听路由应答的功能，使其具有多条到目的节点的路由。这样在断链的时候能够及时地恢复路由，进行数据传输，随着节点速度的提高，IMAODV的吞吐量明显优于AODV，如图5所示,在节点最大移动速度为10 m/s和15 m/s时，IMAODV能提供比AODV高29.4%和34.3%的网络吞吐量。

图6中反映了节点停留时间与吞吐量的关系，此时场景中节点的最大移动速度为20 m/s,停留时间在40 s、50 s以及150 s时，IMAODV的吞吐量较AODV略有下降，原因是这些场景中中间节点的移动速度较小，由于新协议中路由度量是多个方面的折中考虑，所以在移动速度不明显的时候，IMAODV的优越性就不太明显，但总体性能较AODV好。

图7是最大节点移动速度为20 m/s时，网络中节点连接增加对网络吞吐量的影响。图中两个协议的吞吐量都随着网络中节点连接数的增加而增大。明显地，由于考虑了节点的移动速度，改进后的协议能够较快地捕捉节点间的断链情况，并做出较快的路由重建处理，使得图中IMAODV比AODV能产生较高的吞吐量。

本文针对移动自组织网络中节点的移动速度对路由协议的影响对AODV协议做了改进，提出了一种新的改进路由协议IMAODV(Improved AODV)。该协议在对HELLO消息机制及路由修复机制做出优化的同时，在MAC层做了优化以使节点具有侦听功能，使之能够在节点以中高速运动的条件下建立较稳定的路由，降低了分组传输端到端的平均延迟，并提高了网络的吞吐量。仿真结果表明，该协议能较好地适应移动自组织网络的通信环境。

下一步工作将对路由协议做多接口扩展和跨层的优化处理，以进一步提高路由算法的性能。

[1]RFC2501.Mobile Ad hoc networking(MANET):Routing protocol performance issues and evaluation considerations[s]

[2]王金龙，王呈贵.Ad Hoc移动无线网络[M].北京：国防工业出版社，2004：81-83

[3]RFC3561.Ad hoc on-demand distance vector(AODV)Routing[S].

[4]PERKINS C E.Ad hoc on demand distance vector Routing[J].Mobile Computing Systems and Applications,1991.

[5]王力超,林绿洲,陆起涌.基于 AODV的改进型 ad hoc路由协议,仪器仪表学报，2006,27(6).

[6]PERKINS D D,HUGHES H D,OWEN C B.Factors affecting the performance of Ad hoc networks[C].IEEE International Conference on Communications,2002.Michigan State University,2002:2048-2052.

[7]LWW S J,MARIO G AODV-BR:Backup routing in Ad hoc networks[C].IEEE Wireless Communications and Networking Conference,2000(WCNC 2000),2000,3:1311-1316.

[8]郑相全，郭伟，李帆.自组网AODV路由协议中锻炼修复的改进[J].电子科技大学学报，2003,32(5).

[9]NS2[OL].http://nsnam.isi.edu/nsnam/index.php.