摘 要：提出了一种基于负载均衡的DYMO路由协议改进，通过仿真证明改进的DYMO路由协议实现了网络的优化，增加了移动自组网的性能。
关键词：移动自组网；Ad Hoc路由协议；DYMO

　移动自组网MANET（Mobile Ad Hoc Networks）是由若干移动节点自行组成的网络，整个网络没有固定的基础设施，每个节点都可以自由地移动、加入以及退出网络。移动自组网的研究最初是以一个独立网络存在的，随着近年来移动自组网研究的不断深入以及固定接入网的普及，实现Ad Hoc网络与接入网技术的结合成为了移动自组网的一个重要研究方向。
　移动自组网中的路由协议分为两大类。一是先验式路由协议，又称为表驱动路由协议，这类协议类似于固定网络的路由协议，在任何情况下，无论是否传输数据，每个节点都必须维护一张整个网络的路由表。二是后验式路由协议，又称为按需路由协议，这类路由协议是基于移动自组网的网络拓扑不断变化特性而研究出的。DYMO是最新的按需路由协议，由IETF的移动自组网工作组提出，是AODV路由协议的后继协议，大量继承了AODV路由协议的方法和机制，并且包含了一些DSR路由协议的特性。
　本文针对DYMO路由协议和接入网的结合，提出了基于网关发现以及网关负载均衡算法的改进LB-DYMO路由协议，使得网络内的节点能够有效地分担流量和能耗，延长节点存活时间。并通过仿真验证LB-DYMO路由协议能更好地与接入网结合。
1 DYMO路由协议
　DYMO路由协议的基本操作分为路由发现和路由维护两个阶段。
　在DYMO路由协议的路由发现阶段，当源节点要发送数据到目标节点时会先查找源节点内部的路由表，如果不存在目的节点的路由条目，源节点就先缓存要发送的数据，然后开启一个路由发现进程。首先，源节点广播发送一个路由查询包（RREQ）到它所有的邻居节点，这些邻居节点收到了RREQ后再查找它们内部的路由表，如果还是没有目的节点的路由条目，则这些邻居节点继续向它们的邻居转发这个RREQ包直到目的节点收到为止。DYMO包含了源动态DSR路由协议的特性，在RREQ包转发的过程中加入了中间节点的节点信息。当RREQ包到达目的节点时，目的节点会往源节点地址单播发送一个路由回应（RREP）包。源节点收到这个RREP包时，源节点与目的节点之间的路由便建立起来了。
　路由维护阶段分为两个部分。当一个活跃的节点检测到其某条邻接的链路断裂时，这个节点就会发出一个路由错误（RRER）包来表示这条路由已经破损且目标节点不可达。在更新路由条目时，DYMO路由协议使用序列号来检查条目的时效性，序列号数值越大则表明时效性越高，每个节点内都保存其自身的序列号用来维持这个序列号机制，该机制能很好地保证路由无环。
2 改进的LB-DYMO路由协议设计
　为了提高DYMO与接入网链接的效率，本文提出一种基于负载均衡算法的LB-DYMO路由协议。
2.1 基本思想
2.1.1网关发现
　为了实现自组网与有限接入网的结合，路由协议必须具备网关发现的能力。整个自组网络至少需要一个连接外网的节点作为网关，这样才能使网络中的各个节点实现与Internet互联。在移动自组网拓扑高度动态变化的环境下，能够高效地发现网关并不容易。
　网关发现算法可以分为主动式和被动式两大类，改进的LB-DYMO采用被动式网关发现算法。由于DYMO路由协议本身是一个被动式路由发现的路由协议，因此被动式的网关发现算法的应用能起到更好的效果。为了实现被动路由协议发现，可以在路由协议的路由回应阶段RREP包中加入IGW（网关）字段，表明该节点为网关。新的RREP格式如图1所示，新加入的IGW字段利用了原来RREP报文所设置的保留位（Rsv）。
2.1.2 Load-balance（负载均衡）算法实现机制
　在LB-DYMO路由协议的网关发现过程之后，由于移动自组网的特性，网络中可能存在多个网关。简单地选取一条跳数最短的路由并不一定是最合适的路由。在多网关的移动自组网环境下，采用负载均衡算法不但能够使得数据流避开带宽较小的网关，选择阻塞较小的网关，还能均衡各个节点的业务流量以及能耗。

2.2 实现方案
　路由发现阶段：LB-DYMO和DYMO使用同样的方法，如果发现到达目的地址在源节点的路由表中找不到对应路由，那么源节点就会广播发送RREQ包至所有邻居节点。
　路由回复阶段：当源节点所要到达的目的地址不存在于整个自组网中，那么LB-DYMO的被动网关发送算法就会被触发。IGW收到通往外网网段的RREQ查询包后，会在RREP包后加入IGW字段，表明本节点为网关。同时在RREP包按原路径返回源节点时，还会综合计算整个链路上的负载以及带宽。在多网关的情况下，源节点会收到多个RREP包用来告知源节点有多条通往目的地址的路由存在。LB-DYMO通过RREP包返回时计算出的链路MetricGW值选择合适的网关，在源节点的路由表中写一条通往外网的默认IGW，暂时未使用到的IGW会在路由表的默认路由下写为备份IGW。默认网关的使用会分配GWtmin和GWtmax。分别表示默认网关的最小生存以及最大生存时间。
　路由维护阶段：一旦默认IGW的使用时间到达了最大生存时间，LB-DYMO则会实行新一轮的路由发现策略，目的地为前默认IGW节点以及各个备份IGW节点，然后通过收到的RREP包得到最新的链路MetricGW值，权衡之后再选出新的默认IGW节点。
3 仿真结果及分析

　本文仿真采用NS2网络仿真模拟软件，设计的仿真场景为1 500 m×1 500 m，节点数量为100个的矩形区域，仿真时间为300 s。NS2中选择的节点运动模式为Random waypoint，MAC层采用IEEE 802.11介质访问控制协议。传输层采用UDP协议，应用层发送包大小为512 B的恒定比特率（CBR）数据流，整个自组网络中的IGW数量为3。
　实验结果如图2~图4所示，图2和图3显示的是数据包传输速率在5~40 packet/s情况下，LB-DYMO与DYMO的端到端时延与归一化路由开销比较。由图可知，LB-DYMO的路由开销和时延都在一定程度上比DYMO高，这是由于LB-DYMO在路由回应以及路由维护阶段均比DYMO复杂。图4显示的是在不同数据包传输速率下，LB-DYMO与DYMO分组投递率的比较。由图可知，加入了负载均衡算法的LB-DYMO的表现比DYMO有一定提高。

　本文在DYMO路由协议的基础上进行了改进，根据各自的MetriGW值来选择不同路径到达不同的网关实现负载均衡。仿真结果表明，LB-DYMO的分组投递率较DYMO有一定程度的提高，但是由于协议复杂度的增加，路由开销和端到端延时也相应增加。今后的工作将是研究如何能进一步提高LB-DYMO路由协议的各项性能，以及如何从理论出发更好地实现自组网的网关负载均衡。
参考文献
[1] 陈林星，曾曦，曹毅.移动Ad Hoc网络：自组织分组无线网络技术[M].北京：电子工业出版社，2012.
[2] PERKINS C， CHAKERES I. Dynamic MANET on-demand（DYMO）routing[EB/OL]. http：//tools.ietf.org/html/draft-ietf-manet-dymo-26.
[3] 徐炜，周少琼，柏诗玉.移动Ad hoc网络基于路由协议的拥塞控制[J].微型机与应用，2011（4）：65-67.
[4] 刘锐，曾素华.AODV路由协议负载均衡的改进[J].四川兵工学报，2008（6）：147-148.