摘 要 在移动自组网中，减少移动节点电池能量消耗，延长 网络 总的寿命时间，已经成为路由协议性能评价的重要方面。本文提出了一种新的路由选择度量，它综合考虑了节点的剩余能量，路径的延时和跳数，试图通过一种最优路径选择算法来保护网络中的低能量节点。结合该度量方式还提出一种路由选择协议LBAODV (Load Balancing based Ad-Hoc On-Demand Distance Vector Routing) ，仿真结果表明，该协议能够使节点能耗与负载的分布更为均匀，相比以前相关的路由算法有效提高了吞吐量。
关键词 Ad hoc 网络；路由协议；负载均衡；AODV；能量
1 引言
移动Ad Hoc网络(MANET) [1 ]是由一组移动节点通过自组连接形成的多跳无线网络。不同于有线网络，它不需要固定的基础设施。由于其自组织性、快速部署和无须任何固定设施的特点，MANET 有广泛的 应用 ，如战地指挥控制、紧急灾难恢复、矿场操作和研讨会信息共享。MANET 正作为重要的、有前途的 研究 领域受到极大关注。
如今按需路由协议是移动ad hoc 网络中应用最广泛的一种路由协议。作为按需路由协议代表的AODV[2 ] 和DSR[3 ]都是以最短路径作为路由选择的标准，它们在网络轻负载情况下表现良好。然而，在高业务量的情况下，AODV和DSR 的性能都急剧恶化[4 ] ，部分原因是由于其在路径选择时倾向于使用相同的节点作为中间节点，大量的数据通过少量节点传输，引起网络的阻塞，从而导致较高的分组时延，部分节点也会过早地电池耗尽。许多研究者认识到，当网络负载较重时，最短路径并非是MANET 中用于路径选择的最佳度量[5 ,6 ] 。
与此同时，网络负载平衡正受到越来越多的关注。MANE网络的各个节点在充当终端角色发送和接收信息的同时，还作为路由中继节点转发信息。由于MNANET网络特点，路由的选择会直接 影响 网络吞吐量，端到端时延，终端节点的能量消耗等参数。多数终端节点都采用有限电源模式，因此剩余能量就作为节点最宝贵的资源，一旦资源耗尽，终端节点就无法工作，也无法作为中继节点继续工作，进而导致整个网络无法正常运行。然而，在一些节点能量耗尽的时候，其它节点还有过多剩余能量，这就造成了MANET网络的能耗不公平性，还有些节点担负着比其它节点更为重要的作用，一旦能量耗尽会对整个网络造成巨大损失。因此，就需要在基于最短路径路由的常规路由协议基础上，更多的考虑网络的能量损耗公平性，即负载均衡性能。
本文第2节介绍MANET 中负载平衡路由的相关工作;第3节描述路由协议LBAODV，提出一种新的路由选择度量，它综合考虑了节点的剩余能量，路径的延时和跳数，试图通过一种最优路径选择算法来保护网络中的低能量节点7第4节给出仿真环境、性能参数和仿真结果；最后提出结论和进一步的研究工作。
2 负载均衡路由协议的研究
目前 提出的负载均衡路由算法主要有：MRP –LB (Multi - Path Routing with Load Balancing) [7 ] 、MSR(Multi - Path Source Routing) [8 ] 、DLAR (Dynamic Load- Aware Routing) [9 ] 、LWR (Load Aware Routing) [10 ] 、LSR(Load - Sensitive on Demand Routing) [11 ] 和LBAR(Load - Balanced Ad Hoc Routing) [12 ] 。这些算法的选路准则不再象普通的MANET 中的路由算法(如：AODV、DSR 等) 那样，以“路由最短”作为选路准则，而是通过一些能够反映网络负载状态的信息来作为选择准则。表1 从选路准则、性能评价、是否需要周期性发送信息三个方面列出了目前已提出的主要的负载均衡路由算法的特点。
由于现有的ad hoc 路由协议缺乏网络负载平衡能力，而且没有考虑网络中的每个节点的寿命，面对大量数据业务，协议不能提供令人满意的性能。针对上述的不足之处，本文提出了LBAODV协议是综合路由的负载均衡，延时和跳数来选择最优路径的。改进主要基于以下几个方面：
1）当中间节点收到RREQ消息后，首先判断自己的剩余能量所处的状态，进而来判断是否进行转发，从而防止了RREQ分组在全网范围内的不必要转发和某些节点的失效，减少了网络拥塞，提高了系统吞吐量，并且平衡网络负载，延长了重负荷节点的生存时间。
2）当中间节点（或者目的节点）收到来自不同路径的同一个路由请求识别码的路由请求时，对收到的各请求分组中包含的路径信息进行缓存，然后本节点将从收到的多个来自不同路径的路由应答分组中按照一定的算法综合考虑路由的负载均衡，延时和跳数来选择最优路径进行记录，以便数据分组可以选择到目的节点代价最优的路径进行传输。
表1 负载均衡路由算法特点比较
3 LBAODV协议描述
3.1 三级电池能量阈值保护状态
考虑到Ad Hoc 网络的节点能量受限，一旦能量耗尽就不能继续工作。而骨干节点停止工作后将很容易导致整个网络的失效。所以路由选择应该尽量避免使用那些剩余能量少的那些节点。LBAODV协议按式（3-1）定义电池剩余能量率RER（Residual Energy Ratio）：
（3-1）
此外根据节点的剩余能量，每个节点根据自身的能量等级对路由请求做出相应的响应。本协议采用了3个能量级别，分别为：Danger，Warning ，Normal，分别对应于rer1，rer2，rer3三级阈值。其中三者顺序为：rer1<rer2<rer3。当中间节点收到RREQ消息后，首先判断自己的剩余能量所处的状态，进而来判断是否进行转发该消息。
1）若当前节点的处于Danger状态时，该节点将丢弃所有路由请求信息，不再进行任何的消息转发，从而保护了该节点。它只为自己作为源节点或者目的节点的路径服务；
2）若当前节点处于Warning状态时，该节点将在它的路由表中查找符合条件的替换节点，并且通知它的上下游节点实现本地路径的更新；
3）若当前节点处于Normal状态时，在路由请求RREQ中添加一个字段 来记录所经过节点的最小剩余能量率，以及 来记录RREQ从源节点发出到目的节点的延迟。然后继续广播RREQ。
3.2 LBAODV协议描述
3.2.1 路由发现操作
当源节点需要和另一节点进行通信但没有到目的节点的有效路由可使用时，协议通过对 RREQ 进行广播的方式发起路由发现过程。RREQ 消息携带有源节点和目的节点地址、初始化值为 0 且每次递加 1 的序列号、和源节点的剩余能量率RER添加到相应的域。收到 RREQ 消息的各中间节点将对本节点的剩余能量状态进行判断。剩余能量不足而导致功能受限节点通过丢弃 RREQ 而防止本节点成为新路径的中间节点，以避免RREQ风暴。使产生的路由在避开受限节点的同时减少了受限节点转发 RREQ 带来的附加控制开销。非功能受限状态的中间节点在收到第一个 RREQ 时，对 RREQ 中携带的节点序列号和相应路径的信息进行记录之后，然后对 域进行设置为原始值和该节点延迟转发的时间 之和，再将本节点的剩余能量率RER和该请求消息中的 域中的值进行比较，如果小于该值，则把当前节点的剩余能量RER添加到该域中。以实现对 RREQ 的更新，并将更新后的RREQ 再次向目的节点广播。源节点和目的节点地址、序列号相同的两个RREQ 应被认为是同一个 RREQ 分组。当一个中间节点收到 RREP 分组时，直接按照 RREP 中包含的路径对RREP 继续进行转发。另外，当中间节点收到 RREP 分组时，还会更新本节点到目的节点的路由。
3.2.2 源节点的操作
在 AODV协议中，源节点只接收第一个到达的 RREP 报文。在改进的 LBAODV 协议中，主要做了两方面的改进。第一：节点收到数据包后不是一律立即转发，而是按照剩余能量的多少，延迟一个与剩余能量成反比的时间 （能量越少，延迟时间越长）转发，如（3-2）式所示。这也是需要综合考虑负载均衡，延时和跳数的原因（不再是简单的跳数越多，延时越长）。第二：源节点收到第一个 RREP 报文后，启动延迟器。当延时器超时后，源节点根据以下策略在所有到达的可选路径中选择最优路径。如（3-3）式所示：
（3-2）
其中， 为该节点根据剩余能量而进行的延迟， RE 为剩余能量。
（3-3）
其中 为最优路径， 为该路径中的最小剩余能量率， 为该路径的总的延迟， 为该路径的总的跳数， 为各个参数的权重。在LBAODV协议中采用 。
3.2.3 中间节点的操作
当源节点需要发送数据包且在它的路由表中没有有效路径时，就调用路由发现过程。源节点广播一个路由请求（RREQ）消息，中间节点接收到（RREQ）后，将按照下列步骤执行操作。
if (路由表中有到目标节点的路径) {
反向向源节点发送RREP消息；
删除该请求包，不再往前发送；
}
else {
if （本节点ID在RREQ记录的ID序列中）
删除该请求包，不再往前发送；
else {
计算 该节点RER值
if (RER<rer1 then) {
删除该请求包，不再往前发送；
}
else if (RER<rer2) {
寻找替换路径
}
else {
进行路径信息更新，然后继续广播该请求信息。
}
}
}
3.2.4 目的节点的操作
目的节点收到 RREQ 以后，利用 RREQ 中的反向路径信息以单播的方式向源节点发送 RREP。
3.2.5 路由维护阶段
在无线Ad hoc网络中由于节点可以自由移动，网络拓扑结构的动态变化会导致路由失效，并考虑到节点剩余能量的变化，一旦源节点、活动路径上的中间节点或目标节点剩余能量不能够满足要求，就必须找到一条替换路径。当由于路由中间节点的剩余能量发生变化而不能满足传输要求，则需要当前节点向周围发送 RERRRE 分组寻找满足要求的替代节点或替代节点群进行替代路由的建立。若周围节点中满足要求的节点，此时需要看当前节点剩余能量在和范围内，处于 warning 域内，则可继续转发信息，若节点剩余能量是处于功能受限的 danger 域内，则此情况被视为等同于路由断裂情况，发送RERR分组通知源节点。
关键词 Ad hoc 网络；路由协议；负载均衡；AODV；能量
1 引言
移动Ad Hoc网络(MANET) [1 ]是由一组移动节点通过自组连接形成的多跳无线网络。不同于有线网络，它不需要固定的基础设施。由于其自组织性、快速部署和无须任何固定设施的特点，MANET 有广泛的 应用 ，如战地指挥控制、紧急灾难恢复、矿场操作和研讨会信息共享。MANET 正作为重要的、有前途的 研究 领域受到极大关注。
如今按需路由协议是移动ad hoc 网络中应用最广泛的一种路由协议。作为按需路由协议代表的AODV[2 ] 和DSR[3 ]都是以最短路径作为路由选择的标准，它们在网络轻负载情况下表现良好。然而，在高业务量的情况下，AODV和DSR 的性能都急剧恶化[4 ] ，部分原因是由于其在路径选择时倾向于使用相同的节点作为中间节点，大量的数据通过少量节点传输，引起网络的阻塞，从而导致较高的分组时延，部分节点也会过早地电池耗尽。许多研究者认识到，当网络负载较重时，最短路径并非是MANET 中用于路径选择的最佳度量[5 ,6 ] 。
与此同时，网络负载平衡正受到越来越多的关注。MANE网络的各个节点在充当终端角色发送和接收信息的同时，还作为路由中继节点转发信息。由于MNANET网络特点，路由的选择会直接 影响 网络吞吐量，端到端时延，终端节点的能量消耗等参数。多数终端节点都采用有限电源模式，因此剩余能量就作为节点最宝贵的资源，一旦资源耗尽，终端节点就无法工作，也无法作为中继节点继续工作，进而导致整个网络无法正常运行。然而，在一些节点能量耗尽的时候，其它节点还有过多剩余能量，这就造成了MANET网络的能耗不公平性，还有些节点担负着比其它节点更为重要的作用，一旦能量耗尽会对整个网络造成巨大损失。因此，就需要在基于最短路径路由的常规路由协议基础上，更多的考虑网络的能量损耗公平性，即负载均衡性能。
本文第2节介绍MANET 中负载平衡路由的相关工作;第3节描述路由协议LBAODV，提出一种新的路由选择度量，它综合考虑了节点的剩余能量，路径的延时和跳数，试图通过一种最优路径选择算法来保护网络中的低能量节点7第4节给出仿真环境、性能参数和仿真结果；最后提出结论和进一步的研究工作。
2 负载均衡路由协议的研究
目前 提出的负载均衡路由算法主要有：MRP –LB (Multi - Path Routing with Load Balancing) [7 ] 、MSR(Multi - Path Source Routing) [8 ] 、DLAR (Dynamic Load- Aware Routing) [9 ] 、LWR (Load Aware Routing) [10 ] 、LSR(Load - Sensitive on Demand Routing) [11 ] 和LBAR(Load - Balanced Ad Hoc Routing) [12 ] 。这些算法的选路准则不再象普通的MANET 中的路由算法(如：AODV、DSR 等) 那样，以“路由最短”作为选路准则，而是通过一些能够反映网络负载状态的信息来作为选择准则。表1 从选路准则、性能评价、是否需要周期性发送信息三个方面列出了目前已提出的主要的负载均衡路由算法的特点。
由于现有的ad hoc 路由协议缺乏网络负载平衡能力，而且没有考虑网络中的每个节点的寿命，面对大量数据业务，协议不能提供令人满意的性能。针对上述的不足之处，本文提出了LBAODV协议是综合路由的负载均衡，延时和跳数来选择最优路径的。改进主要基于以下几个方面：
1）当中间节点收到RREQ消息后，首先判断自己的剩余能量所处的状态，进而来判断是否进行转发，从而防止了RREQ分组在全网范围内的不必要转发和某些节点的失效，减少了网络拥塞，提高了系统吞吐量，并且平衡网络负载，延长了重负荷节点的生存时间。
2）当中间节点（或者目的节点）收到来自不同路径的同一个路由请求识别码的路由请求时，对收到的各请求分组中包含的路径信息进行缓存，然后本节点将从收到的多个来自不同路径的路由应答分组中按照一定的算法综合考虑路由的负载均衡，延时和跳数来选择最优路径进行记录，以便数据分组可以选择到目的节点代价最优的路径进行传输。
表1 负载均衡路由算法特点比较
3 LBAODV协议描述
3.1 三级电池能量阈值保护状态
考虑到Ad Hoc 网络的节点能量受限，一旦能量耗尽就不能继续工作。而骨干节点停止工作后将很容易导致整个网络的失效。所以路由选择应该尽量避免使用那些剩余能量少的那些节点。LBAODV协议按式（3-1）定义电池剩余能量率RER（Residual Energy Ratio）：
（3-1）
此外根据节点的剩余能量，每个节点根据自身的能量等级对路由请求做出相应的响应。本协议采用了3个能量级别，分别为：Danger，Warning ，Normal，分别对应于rer1，rer2，rer3三级阈值。其中三者顺序为：rer1<rer2<rer3。当中间节点收到RREQ消息后，首先判断自己的剩余能量所处的状态，进而来判断是否进行转发该消息。
1）若当前节点的处于Danger状态时，该节点将丢弃所有路由请求信息，不再进行任何的消息转发，从而保护了该节点。它只为自己作为源节点或者目的节点的路径服务；
2）若当前节点处于Warning状态时，该节点将在它的路由表中查找符合条件的替换节点，并且通知它的上下游节点实现本地路径的更新；
3）若当前节点处于Normal状态时，在路由请求RREQ中添加一个字段 来记录所经过节点的最小剩余能量率，以及 来记录RREQ从源节点发出到目的节点的延迟。然后继续广播RREQ。
3.2 LBAODV协议描述
3.2.1 路由发现操作
当源节点需要和另一节点进行通信但没有到目的节点的有效路由可使用时，协议通过对 RREQ 进行广播的方式发起路由发现过程。RREQ 消息携带有源节点和目的节点地址、初始化值为 0 且每次递加 1 的序列号、和源节点的剩余能量率RER添加到相应的域。收到 RREQ 消息的各中间节点将对本节点的剩余能量状态进行判断。剩余能量不足而导致功能受限节点通过丢弃 RREQ 而防止本节点成为新路径的中间节点，以避免RREQ风暴。使产生的路由在避开受限节点的同时减少了受限节点转发 RREQ 带来的附加控制开销。非功能受限状态的中间节点在收到第一个 RREQ 时，对 RREQ 中携带的节点序列号和相应路径的信息进行记录之后，然后对 域进行设置为原始值和该节点延迟转发的时间 之和，再将本节点的剩余能量率RER和该请求消息中的 域中的值进行比较，如果小于该值，则把当前节点的剩余能量RER添加到该域中。以实现对 RREQ 的更新，并将更新后的RREQ 再次向目的节点广播。源节点和目的节点地址、序列号相同的两个RREQ 应被认为是同一个 RREQ 分组。当一个中间节点收到 RREP 分组时，直接按照 RREP 中包含的路径对RREP 继续进行转发。另外，当中间节点收到 RREP 分组时，还会更新本节点到目的节点的路由。
3.2.2 源节点的操作
在 AODV协议中，源节点只接收第一个到达的 RREP 报文。在改进的 LBAODV 协议中，主要做了两方面的改进。第一：节点收到数据包后不是一律立即转发，而是按照剩余能量的多少，延迟一个与剩余能量成反比的时间 （能量越少，延迟时间越长）转发，如（3-2）式所示。这也是需要综合考虑负载均衡，延时和跳数的原因（不再是简单的跳数越多，延时越长）。第二：源节点收到第一个 RREP 报文后，启动延迟器。当延时器超时后，源节点根据以下策略在所有到达的可选路径中选择最优路径。如（3-3）式所示：
（3-2）
其中， 为该节点根据剩余能量而进行的延迟， RE 为剩余能量。
（3-3）
其中 为最优路径， 为该路径中的最小剩余能量率， 为该路径的总的延迟， 为该路径的总的跳数， 为各个参数的权重。在LBAODV协议中采用 。
3.2.3 中间节点的操作
当源节点需要发送数据包且在它的路由表中没有有效路径时，就调用路由发现过程。源节点广播一个路由请求（RREQ）消息，中间节点接收到（RREQ）后，将按照下列步骤执行操作。
if (路由表中有到目标节点的路径) {
反向向源节点发送RREP消息；
删除该请求包，不再往前发送；
}
else {
if （本节点ID在RREQ记录的ID序列中）
删除该请求包，不再往前发送；
else {
计算 该节点RER值
if (RER<rer1 then) {
删除该请求包，不再往前发送；
}
else if (RER<rer2) {
寻找替换路径
}
else {
进行路径信息更新，然后继续广播该请求信息。
}
}
}
3.2.4 目的节点的操作
目的节点收到 RREQ 以后，利用 RREQ 中的反向路径信息以单播的方式向源节点发送 RREP。
3.2.5 路由维护阶段
在无线Ad hoc网络中由于节点可以自由移动，网络拓扑结构的动态变化会导致路由失效，并考虑到节点剩余能量的变化，一旦源节点、活动路径上的中间节点或目标节点剩余能量不能够满足要求，就必须找到一条替换路径。当由于路由中间节点的剩余能量发生变化而不能满足传输要求，则需要当前节点向周围发送 RERRRE 分组寻找满足要求的替代节点或替代节点群进行替代路由的建立。若周围节点中满足要求的节点，此时需要看当前节点剩余能量在和范围内，处于 warning 域内，则可继续转发信息，若节点剩余能量是处于功能受限的 danger 域内，则此情况被视为等同于路由断裂情况，发送RERR分组通知源节点。
收藏