基于负载均衡的路由协议的设计

1、基于负载均衡的路由协议的设计基于负载均衡的路由协议的设计摘要在移动自组网中，减少移动节点电池能量消耗，延长网络总的寿命时间，已经成为路由协议性能评价的重要方面。本文提出了一种新的路由选择度量，它综合考虑了节点的剩余能量，路径的延时和跳数，试图通过一种最优路径选择算法来保护网络中的低能量节点。结合该度量方式还提出一种路由选择协议 LBAODV (Load Balancing based Ad-Hoc On-Demand DistanceVector Routing) ，仿真结果表明，该协议能够使节点能耗与负载的分布更为均匀，相比以前相关的路由算法有效提高了吞吐量。关键词 Ad hoc 网络；路由

2、协议；负载均衡；AODV；能量1引言移动 Ad Hoc 网络(MANET) 1 是由一组移动节点通过自组连接形成的多跳无线网络。不同于有线网络，它不需要固定的基础设施。由于其自组织性、快速部署和无须任何固定设施的特点，MANET 有广泛的应用，如战地指挥控制、紧急灾难恢复、矿场操作和研讨会信息共享。MANET 正作为重要的、有前途的研究领域受到极大关注。如今按需路由协议是移动 ad hoc 网络中应用最广泛的一种路由协议。作为按需路由协议代表的 AODV2 和 DSR3 都是以最短路径作为路由选择的标准，它们在网络轻负载情况下表现良好。然而，在高业务量的情况下，AODV和 DSR 的性能都急剧

3、恶化4 ，部分原因是由于其在路径选择时倾向于使用相同的节点作为中间节点，大量的数据通过少量节点传输，引起网络的阻塞，从而导致较高的分组时延，部分节点也会过早地电池耗尽。许多研究者认识到，当网络负载较重时，最短路径并非是 MANET 中用于路径选择的最佳度量5 ,6 。与此同时，网络负载平衡正受到越来越多的关注。MANE 网络的各个节点在充当终端角色发送和接收信息的同时，还作为路由中继节点转发信息。由于 MNANET 网络特点，路由的选择会直接影响网络吞吐量，端到端时延，终端节点的能量消耗等参数。多数终端节点都采用有限电源模式，因此剩余能量就作为节点最宝贵的资源，一旦资源耗尽，终端节点就无法工作

4、，也无法作为中继节点继续工作，进而导致整个网络无法正常运行。然而，在一些节点能量耗尽的时候，其它节点还有过多剩余能量，这就造成了 MANET 网络的能耗不公平性，还有些节点担负着比其它节点更为重要的作用，一旦能量耗尽会对整个网络造成巨大损失。因此，就需要在基于最短路径路由的常规路由协议基础上，更多的考虑网络的能量损耗公平性，即负载均衡性能。本文第 2 节介绍 MANET 中负载平衡路由的相关工作;第 3 节描述路由协议 LBAODV，提出一种新的路由选择度量，它综合考虑了节点的剩余能量，路径的延时和跳数，试图通过一种最优路径选择算法来保护网络中的低能量节点 7第 4 节给出仿真环境、性能参数和

5、仿真结果；最后提出结论和进一步的研究工作。2负载均衡路由协议的研究目前提出的负载均衡路由算法主要有：MRP LB (Multi - PathRouting with Load Balancing) 7 、MSR(Multi - Path Source Routing)8 、DLAR (Dynamic Load- Aware Routing) 9 、LWR (Load AwareRouting) 10 、LSR(Load - Sensitive on Demand Routing) 11 和LBAR(Load - Balanced Ad Hoc Routing) 12 。这些算法的选路准则不再象

6、普通的 MANET 中的路由算法(如：AODV、DSR 等) 那样，以“路由最短”作为选路准则，而是通过一些能够反映网络负载状态的信息来作为选择准则。表 1从选路准则、性能评价、是否需要周期性发送信息三个方面列出了目前已提出的主要的负载均衡路由算法的特点。由于现有的 ad hoc 路由协议缺乏网络负载平衡能力，而且没有考虑网络中的每个节点的寿命，面对大量数据业务，协议不能提供令人满意的性能。针对上述的不足之处，本文提出了 LBAODV 协议是综合路由的负载均衡，延时和跳数来选择最优路径的。改进主要基于以下几个方面：1）当中间节点收到 RREQ 消息后，首先判断自己的剩余能量所处的状态，进而来判

7、断是否进行转发，从而防止了 RREQ 分组在全网范围内的不必要转发和某些节点的失效，减少了网络拥塞，提高了系统吞吐量，并且平衡网络负载，延长了重负荷节点的生存时间。2）当中间节点（或者目的节点）收到来自不同路径的同一个路由请求识别码的路由请求时，对收到的各请求分组中包含的路径信息进行缓存，然后本节点将从收到的多个来自不同路径的路由应答分组中按照一定的算法综合考虑路由的负载均衡，延时和跳数来选择最优路径进行记录，以便数据分组可以选择到目的节点代价最优的路径进行传输。表 1负载均衡路由算法特点比较3LBAODV 协议描述3.1三级电池能量阈值保护状态考虑到 Ad Hoc 网络的节点能量受限，一旦能

8、量耗尽就不能继续工作。而骨干节点停止工作后将很容易导致整个网络的失效。所以路由选择应该尽量避免使用那些剩余能量少的那些节点。LBAODV 协议按式（3-1）定义电池剩余能量率 RER（Residual Energy Ratio）：（3-1）此外根据节点的剩余能量，每个节点根据自身的能量等级对路由请求做出相应的响应。本协议采用了 3 个能量级别，分别为：Danger，Warning ，Normal，分别对应于 rer1，rer2，rer3 三级阈值。其中三者顺序为：rer1rer2rer3。当中间节点收到 RREQ 消息后，首先判断自己的剩余能量所处的状态，进而来判断是否进行转发该消息。1）若当

9、前节点的处于 Danger 状态时，该节点将丢弃所有路由请求信息，不再进行任何的消息转发，从而保护了该节点。它只为自己作为源节点或者目的节点的路径服务；2）若当前节点处于 Warning 状态时，该节点将在它的路由表中查找符合条件的替换节点，并且通知它的上下游节点实现本地路径的更新；3）若当前节点处于 Normal 状态时，在路由请求 RREQ 中添加一个字段来记录所经过节点的最小剩余能量率，以及来记录 RREQ 从源节点发出到目的节点的延迟。然后继续广播 RREQ。3.2LBAODV 协议描述3.2.1路由发现操作当源节点需要和另一节点进行通信但没有到目的节点的有效路由可使用时，协议通过对

10、RREQ 进行广播的方式发起路由发现过程。RREQ 消息携带有源节点和目的节点地址、初始化值为 0 且每次递加 1 的序列号、和源节点的剩余能量率 RER 添加到相应的域。收到 RREQ 消息的各中间节点将对本节点的剩余能量状态进行判断。剩余能量不足而导致功能受限节点通过丢弃 RREQ 而防止本节点成为新路径的中间节点，以避免 RREQ 风暴。使产生的路由在避开受限节点的同时减少了受限节点转发 RREQ 带来的附加控制开销。非功能受限状态的中间节点在收到第一个 RREQ 时，对 RREQ 中携带的节点序列号和相应路径的信息进行记录之后，然后对 域进行设置为原始值和该节点延迟转发的时间之和，再将

11、本节点的剩余能量率 RER 和该请求消息中的 域中的值进行比较，如果小于该值，则把当前节点的剩余能量 RER 添加到该域中。以实现对 RREQ 的更新，并将更新后的 RREQ 再次向目的节点广播。源节点和目的节点地址、序列号相同的两个 RREQ 应被认为是同一个 RREQ 分组。当一个中间节点收到RREP 分组时，直接按照 RREP 中包含的路径对 RREP 继续进行转发。另外，当中间节点收到 RREP 分组时，还会更新本节点到目的节点的路由。3.2.2源节点的操作在 AODV 协议中，源节点只接收第一个到达的 RREP 报文。在改进的LBAODV 协议中，主要做了两方面的改进。第一：节点收到

12、数据包后不是一律立即转发，而是按照剩余能量的多少，延迟一个与剩余能量成反比的时间 （能量越少，延迟时间越长）转发，如（3-2）式所示。这也是需要综合考虑负载均衡，延时和跳数的原因（不再是简单的跳数越多，延时越长）。第二：源节点收到第一个 RREP 报文后，启动延迟器。当延时器超时后，源节点根据以下策略在所有到达的可选路径中选择最优路径。如（3-3）式所示：（3-2）其中，为该节点根据剩余能量而进行的延迟， RE 为剩余能量。（3-3）其中为最优路径，为该路径中的最小剩余能量率，为该路径的总的延迟，为该路径的总的跳数，为各个参数的权重。在 LBAODV 协议中采用。3.2.3中间节点的操作当源节

13、点需要发送数据包且在它的路由表中没有有效路径时，就调用路由发现过程。源节点广播一个路由请求（RREQ）消息，中间节点接收到（RREQ）后，将按照下列步骤执行操作。if(路由表中有到目标节点的路径)反向向源节点发送 RREP 消息；删除该请求包，不再往前发送；else if （本节点 ID 在 RREQ 记录的 ID 序列中）删除该请求包，不再往前发送；else 计算该节点 RER 值if(RERrer1 then)删除该请求包，不再往前发送；else if(RERrer2)寻找替换路径else 进行路径信息更新，然后继续广播该请求信息。3.2.4目的节点的操作目的节点收到 RREQ 以后，利用

14、 RREQ 中的反向路径信息以单播的方式向源节点发送 RREP。3.2.5路由维护阶段在无线 Ad hoc 网络中由于节点可以自由移动，网络拓扑结构的动态变化会导致路由失效，并考虑到节点剩余能量的变化，一旦源节点、活动路径上的中间节点或目标节点剩余能量不能够满足要求，就必须找到一条替换路径。当由于路由中间节点的剩余能量发生变化而不能满足传输要求，则需要当前节点向周围发送 RERRRE 分组寻找满足要求的替代节点或替代节点群进行替代路由的建立。若周围节点中满足要求的节点，此时需要看当前节点剩余能量在和范围内，处于 warning 域内，则可继续转发信息，若节点剩余能量是处于功能受限的 dange

15、r 域内，则此情况被视为等同于路由断裂情况，发送 RERR 分组通知源节点。论文出处(作者):可见，LBAODV 协议避免了在网络断链情况下总是重新发起路由发现带来的附加开销和时延，将业务流负载均衡和网络抗毁性进行了较好的结合。4 仿真和分析4.1 仿真环境本文使用的模拟工具是由 Berkeley 大学开发的 NS2.30 ，并在 NS2.30的基础上实现了 LBAODV 协议。50 个节点在一个 500500 的矩形区域按照random waypoint 模型移动。仿真的时间为 800 秒。MAC 层协议采用的是802.11，详细参数见表 2 所示。表 2 LBAODV 模拟环境参数的设置区

16、域大小500500节点数50节点移动场景 由 setdest 工具来生成场景文件网络流量场景 由 cbrgen 工具来生成场景文件传播模型TwoRayGroundMAC 协议802.11路由协议LBAODV初始电量500J发射消耗功率 1.33W接收消耗功率 0.85W仿真时间800s4.2 性能参数和仿真结果为了验证 LBAODV 协议的性能，选择以下仿真参数：网络的发包成功率(Packet DeliveryFraction :PDF)；节点的平均能耗 (Average EnergyConsume)；能量不为零的节点数目（Number ofNodes）。1、网络的发包成功率(Packet D

17、eliveryFraction :PDF)在仿真过程中，采用了不同的停留时间为：0s，100，200s，300s，400s，500s，600s，700s，800s。仿真结果如图 1 所示，LBAODV 协议的性能明显的提高了发包的成功率，当节点停留时间比较短的时候，该协议性能明显高于原来的协议。图 1 节点不同的停留时间下的发包成功率2、节点的平均能耗(Average EnergyConsume)图 2 为节点在停留时间为 0 秒的情况下的平均耗能的情况，从图中可以看出，仿真刚开始的 100 秒，两个算法的能量消耗几乎相同，这是因为刚开始每个节点的能量都处于 normal 状态，都进行对 RR

18、EQ 消息的处理，但是随着时间的推移，两个算法的能量消耗差距越来越明显，到 800 秒的仿真结束时，LBAODV 协议比 AODV协议节省了将近 170 焦耳的能量。这是因为当节点处于danger 状态的时候已经不再进行处理不属于源或目的节点的路径请求信息。一是节省了能量，均衡了网络中每个节点的耗能，延长了节点的寿命；二是减轻了网络负担，增加了网络的带宽利用率。图 2 节点在停留时间为 0 秒的情况下的平均耗能3、能量不为零的节点数目（Number ofNodes）图 3整个网络时间内能量不为零的节点数目图 3 是整个网络时间内能量不为零的节点数目情况。从图中可以看出节点一直运行到 400 秒

19、的时候，两个协议下有效的节点数目都为总的节点数目，但是随着时间的推移，AODV 协议由于没有考虑到节点剩余能量的情况，所以在高业务量的情况下，造成了某些节点耗能不均衡而过早的电池耗尽，而改进的协议 LBAODV协议性能有了明显的提高。所以说 LBAODV 协议能够延长移动节点的寿命，均衡了网络中每个节点的耗能。5总结本文在 AODV 基础上提出了一种基于负载均衡的改进协议 LBAODV，该协议综合考虑了节点的剩余能量，路径的延时和跳数，通过一种最优路径选择算法来保护网络中的低能量节点。它有效地均衡网络流量并保护网络中的低能量节点，避免了网络中的节点电池能量过早耗尽。通过 Ns-2 仿真与原有的

20、 AODV 协议相比较，该算法可提高网络的发包成功率，减少了网络的平均耗能情况，并且延长网络中的节点生存时间。下一步研究的主要工作是如何充分利用该协议能到的多条路径，进行数据的分组传送。参考文献1 IETF Mobile AdHoc Working Group Charter2 Perkins C,Royer E, “Ad hoc OnDemand Distance VectorRouting (AODV),” July2003, RFC 35613 Johnson D,Maltz D, “Dynamic sourcerouting in ad hocwireless networks,”Mo

21、bile Compute, 1996,pp.153-1814 Perkins C,Royer E, Das S ,et al ,“Performance comparisonof two on demand routingprotocols for Ad hocnetworks,” IEEE PersonalCommunications, 2001, 8(1) , pp.16-285 Perkins D D,Hughes H D, Owen C B,“Factors affecting t heperformance of ad hocnetworks,”Communications , 20

22、02.ICC 2002, IEEEInternational Conference,2002, 4, pp.2048-20526 ZhongXiaofeng, Wang Youzheng,Mi Shunliang, et al, “AnExperimental PerformanceStudy of Wireless ad hocSystem Utilizing 802. 11aStandard Base ondifferent RoutingProtocols,” Asia PacificOptical and WirelessCommunications, October20027 P Pham, SPerreau, “Multi - pathrouting protocol withload balancing policy inmobile ad hoc networkA,” 4th InternationalWorkshop on Mobile andWireless CommunicationsNetworkC, 2002, pp.48-528 L Zhang, ZZhao, Y Shu, et al,“Load balancing of multipath source routing in a