基于AODV的无线自组织网络负载均衡路由算法

陈昕韡，袁晓兵，李宝清

（中国科学院上海微系统与信息技术研究所微系统技术国防科技重点实验室，上海200050）

基于AODV的无线自组织网络负载均衡路由算法

陈昕韡，袁晓兵，李宝清

（中国科学院上海微系统与信息技术研究所微系统技术国防科技重点实验室，上海200050）

传统无线自组织网络的负载不均，导致端到端时延增大、传输比下降、节点大量死亡等问题。为此，以无线自组织网络按需距离矢量（AODV）路由协议为基础，提出一种改进的负载均衡算法。采用单路径负载均衡方法，考虑节点的即时负载和过往负载，使用节点缓冲区的队列长度、节点剩余能量等指标反映节点的负载情况，并关注瓶颈处的关键节点对网络性能的影响。仿真结果表明，与AODV、改进能量路径等传统算法相比，该算法在不同负载情况下的适应性较好，能提供较为稳定的网络性能。

无线自组织网络；排队等待时间；负载均衡；路由算法；网络时延

1 概述

无线自组织网络（M obile Ad Hoc Network，MANET）是一种无线节点以动态、自组的方式互连形成的网络［1-2］。网络中的节点可以随机移动，拓扑结构的变化难以预测［3］。因此，路由问题是自组网研究的难点。Pham等人通过理论分析［4］，证明了传统路由算法会造成负载不均的问题。文献［5］通过仿真验证了Pham的理论。无线自组织网络中的负载不均现象会造成严重的后果：在重负载节点上出现的拥塞，会增加分组的排队等待时间甚至引起分组丢失，导致传输比下降，传输时延增加［6］；重负载节点能量消耗大甚至因能量耗尽而死亡，导致网络连通性下降甚至造成网络分裂，网络生存时间下降。因此，对负载均衡问题的研究具有重要意义。

无线自组织网络按需距离矢量（Mobile Ad Hoc Network On-demand Distance Vector，AODV）路由协议是一种在自组网中广泛应用的协议，仿真结果显示，它在负载问题中有更好的表现［7］。负载均衡优化算法主要分为单路径算法和多路径算法。在单路径算法中，一对源、目的节点之间只建立一条路径。在多路径算法中，一对源、目的节点之间将建立多条路径。研究显示，单路径算法在自组网路由负载均衡问题中更有效［5，8］。因此，本文采用单路径算法，选择AODV协议作为基础协议，从负载均衡的角度对该协议进行优化。

2 改进的负载均衡路由算法

网络中的负载可以从2个方面进行分析：即时负载和过往负载。即时负载反映了节点当前的负载情况。例如，当节点的缓冲队列较长，说明节点当前的负载较重，较多的分组经由该节点转发，缓冲区内的分组将经历较长的等待时延，甚至被丢弃，节点的能量也将被迅速消耗。过往负载反映了自网络开始运行至当前时刻节点所承担的负载。某个节点可能当前的即时负载不大，但是在过去曾经承担大量的转发任务，消耗了大量的能量。此时如果让该节点继续承担较多的转发任务，则容易导致节点的死亡。节点的剩余能量是反映节点过往负载的较好指标，剩余能量较小说明节点在过去承担的负载较重，之后应该尽量减小该节点的负载。因此，在改进中将综合考虑即时负载和过往负载这2种负载的均衡。

2.1 节点即时负载

节点缓冲区的队列长度是反映节点即时负载的较好指标［9］。在已有的负载均衡算法中，通常采用虚拟呼叫准入的方式处理队列长度信息，即在转发路由请求（Route Request，RREQ）分组时，若转发节点的缓冲区队列长度较大，则丢弃RREQ不进行转发，从而迫使最终形成的路径避开该节点［10］。但是，由于需要丢弃RREQ分组，队列长度阈值的选择对于算法的性能影响较大。并且，直接丢弃的方式容易造成路由发现的失败，导致源节点重启路由发现过程，不但增加了网络的时延，也造成了更多的能量消耗。因此，本文通过将队列长度信息记录在AODV的控制分组中，使得节点可以在比较不同路径的情况下决定是否丢弃分组，避免了直接丢弃导致的路由发现失败。具体地，在RREQ、路由应答（Route Reply，RREP）和节点的路由表项中增加一项，用于存储路径中节点的最大队列长度max-qlen。选取一个阈值，当max-qlen大于等于该阈值时，认为节点负载较重。因此，当节点收到一个新的RREQ分组时，将路由表项中已有路径和RREQ中的max-qlen分别和一个阈值进行比较，若两者均小于阈值，则说明2条路径上的节点负载都较轻，根据其他指标进行选路。若一条路径的max-qlen小于阈值，而另一条大于等于阈值，则选用负载较轻的路径。若2条路径的max-qlen均大于等于阈值，此时，将综合考虑2个max-qlen的大小差异和其他指标。特殊的，当只存在一条路径时，即使路径上存在重负载节点，该路径也将被使用，从而避免虚拟呼叫准入算法中路由发现失败的问题。节点在转发AODV控制分组的时候，会根据自身队列长度对分组中的max-qlen进行更新。

2.2 节点过往负载

节点剩余能量能够反映节点的过往负载。广播是路由发现过程的重要组成部分［11］，在已有的算法中，通常在广播RREQ的过程中将路径中节点的剩余能量累加，用累加剩余能量最小替代原有的跳数最小准则。但是，一条路径的性能主要受到瓶颈节点的限制。因此，路径上剩余能量最小的节点的影响更值得算法考虑，因为该节点的死亡将直接导致路径的失效，而且用于存储单个节点的剩余能量所需要的存储空间远小于存储累加剩余能量的空间，所以可以在一定程度上减小算法的开销。因此，在RREQ、RREP和节点的路由表项中增加一项，用于存储路径中节点的最小剩余能量。对于跳数相差不大的多条路径，选择最小剩余能量最大的路径。

2.3 算法改进

改进的算法综合考虑节点的即时负载和过往负载，路由表更新过程如图1所示。

图1 路由表更新过程

当中间节点接收到RREQ分组时，首先根据分组中的序列号以及节点本地记录的信息判断是否已经接收过该分组。若已经收到过，则丢弃，否则进行进一步处理。节点在自身的路由表中查找该分组的源节点，若不存在相应的表项，则将信息写入路由表中。否则判断是否需要更新相应的路由表项。将RREQ和路由表中的max-qlen分别和阈值th进行比较。若rq-max-qlen＜th而rt-max-qlen≥th，说明出现了负载更轻的路径，则更新路由表。否则比较2条路径的跳数。改进算法对原有的跳数准则进行了放宽，引入宽松因子ε。只要新出现的路径的跳数和原有路径相差不大，均根据最小剩余能量进行选路。若2条路径的最大队列长度均小于阈值，则选择最小剩余能量较大的路径。若2条路径的最大队列长度均大于等于阈值，则同时比较队列的长度和最小剩余能量。队列长度较小并且剩余能量较大时才进行路由表的更新。经过改进，算法可以选择剩余能量较大、队列较短的路径，避开负载较重的瓶颈节点。

3 仿真场景与评价准则

3.1 仿真场景与参数

使用NS2软件进行仿真。仿真场景及参数如表1所示。节点的移动场景使用NS2软件内置的setdest工具自动生成。使用CBR流，用NS2软件中的cbrgen.tcl生成。使用cbrgen工具时采用的种子数分别取1 500，2 000，2 500，仿真结果是这3种情况下结果的平均值。

表1 仿真参数设置

3.2 评价准则

算法的评价指标包括2类：路径有效性指标和能量有效性指标。路径有效性指标主要包括传输比和端到端时延，定义如式（1）、式（2）所示。

其中，ratio为传输比；ns为成功传输的分组数；nt为发送的总分组数；delay为端到端时延；ti为第i个分组的传输时延；pi为第i个分组；sucess为成功传输的分组集合。

能量有效性指标主要包括分组平均能耗、节点死亡数、网络生存时间。其中，网络生存时间通常以第一个死亡节点的死亡时间来表示。分组平均能耗如式（3）所示。

其中，ep为分组平均能耗；et为网络总能耗。

由于负载不均主要导致网络的吞吐能力下降、时延增大、节点过早死亡等，因此传输比、端到端时延、分组平均能耗、节点死亡数、网络生存时间这些指标对于评价负载均衡路由算法的性能具有重要的意义［12］。

分别对4种算法进行仿真与性能比较，分别为AODV算法、本文提出的改进负载均衡算法、改进的能量路径算法和队列虚拟呼叫准入算法。其中，改进的能量路径算法选用文献［13］中的M LNR-LM算法，使用路径中节点剩余能量的累加和代替AODV算法中的跳数作为首要选路准则，当2条路径的剩余能量累加值相等时，将跳数最小作为第2准则。队列虚拟呼叫准入算法在中间节点收到RREQ广播时，根据节点当前的缓冲队列长度进行判断，超过一定的阈值则不进行RREQ的转发。

4 结果分析

4.1 仿真结果

在节点最大速度为20 m/s，连接数为60的情况下对4种算法进行仿真。成功传输分组数随时间的变化如图2所示。

图2 成功传输分组数随时间的变化

队列虚拟呼叫准入算法使用了2个不同的阈值，分别为缓冲区的9/10和1/2。

从图中可以看出，负载均衡算法成功传输的分组数最多，较AODV算法和能量路径算法，性能有了很大的提高。而队列虚拟呼叫准入算法受阈值的影响较大，当阈值选择较好时，网络中成功传输的分组数较大，但是当阈值选择不当时，性能较差。

AODV、负载均衡算法、能量路径算法、队列虚拟呼叫准入算法（9/10）的时延分别为0.096 s，0.065 s，0.006 02 s，0.224 72 s。传输比分别为89.7%，93.1%，86%，90.5%。分组平均能耗分别为3.614 J/packet，2.239 J/packet，3.233 J/packet，2.745 J/packet。平均死亡节点数分别为1.33，0.67，2.67，5。第一个死亡节点的死亡时间均为100 s。改进能量路径算法的时延最小，但是传输比也是最低的，并且节点死亡数量最多。因此，该算法是牺牲了其他性能来实现网络传输时延性能的提高。而本文提出的负载均衡算法的综合效果最好。具有较小的网络传输时延，最大的传输比，最低的节点死亡数量，每个分组消耗的能量也最少。

图3和图4比较了端到端时延以及传输比随连接数的变化情况。能量路径算法具有不错的时延性能，但是传输比性能不理想。队列虚拟呼叫准入算法（9/10）的传输比性能不错，但是时延性能较差。而本文提出的负载均衡算法，在时延和传输比上均有较好的表现。尤其在连接数较多的重负载情况中，较AODV算法的性能有了大幅度的提升。和其他3种算法相比，改进算法在不同的负载情况下的适应性较好，能提供较为稳定的网络性能。

图3 端到端时延与连接数的变化

图4 传输比与连接数的变化

死亡节点数随连接数的变化如图5所示。本文的改进算法在不同的连接数下均能保持较小的节点死亡数量，具有较好的性能。

图5 死亡节点数与连接数的变化

4.2 参数敏感度分析

改进算法中使用了队列长度阈值th和宽松因子ε，为了了解算法对这2个参数的敏感度，分别对这2个参数取不同的值进行仿真。仿真参数如表1所示。连接数取60，节点最大速度为20 m/s。仿真结果如表2、表3所示。

表2 宽松因子ε敏感度

表3 队列长度阈值th敏感度

由表2可以看出，当宽松因子ε取不同值时，仿真结果不变。对改进算法进行分析，可以发现宽松因子的存在主要对2种特殊情况进行限制。一种情况，当最小剩余能量较大的路径的跳数远大于另一条路径时，由于仍存在跳数限制，因此可以避免选择跳数过大的路径。另一种情况，当2条路径的跳数相差不大时，可以让跳数略大，但是在能量上有优势的路径有机会成为最终选择的路由。从仿真结果可以看出，这2种情况在仿真中较少出现，因此，在最终的平均结果中，它们的影响几乎可以忽略不计。改进算法的性能提升，主要来自于选路准则在节点能量问题上的强化。但是从考虑全面性的角度来说，仍然在算法中加入带宽松因子的跳数限制。一方面，虽然之前提到的2种特殊情况出现较少，但是一旦出现可能会造成不良的后果，尤其是第一种情况，跳数过大的路径，由于存在大量的转发节点，会造成大量的能量浪费，跳数过大同时也意味着更大的时延，甚至造成分组的丢失。另一方面，对于一些扩展的需求，例如文献［13］中提出的不同类型电源供电的情况，在考虑能量的同时对跳数的考量也具有重要的意义。因此，改进算法仍然保留对跳数的考虑，保证算法今后的可扩展性。从仿真结果可以看出，改进算法对宽松因子ε不敏感。在一定范围内可以自由选择ε。

由表3可以看出。改进算法在不同的th下的性能较为稳定。从图2中可以看出，队列虚拟呼叫准入算法取不同的阈值时，算法的性能差异非常大，而本文提出的改进算法可以克服这个问题。这是由于，改进算法并不会由于缓冲区队列长度超过阈值就直接将新到的RREQ分组丢弃，而是会记录下缓冲区队列的长度，将它作为选路的参考。在队列虚拟呼叫准入算法中，当较多节点均具有较重的负载时，将没有可用的路径，导致路由发现的失败，重传等机制又进一步加重了网络的负担，造成网络性能的下降。改进算法在较多节点负载较重时，仍能从中选择负载相对较轻的路径建立路由，保证了网络的性能。因此，阈值th的大小对算法性能的影响较小。

5 结束语

针对传统无线自组织网络路由协议存在的负载不均问题，本文在AODV协议的基础上提出一种改进的负载均衡算法。考虑到节点的负载分为即时负载和过往负载。即时负载反映了节点当前的繁忙程度，而过往负载反映了节点在过去所承担的负载的总和，两者并不一定相同。因此，对两者进行综合考虑。用节点缓冲区队列的长度反应即时负载，在RREQ分组中记录路径经过节点的最大队列长度，尽量避免使用当前负载较重的节点进行分组的转发，用节点剩余能量表征节点的过往负载。重视瓶颈关键节点对网络性能的影响，在RREQ分组中记录路径经过节点的最小剩余能量，利用宽松因子对经典AODV协议的跳数准则进行放松，在选路时倾向于选择具有较大的最小剩余能量的路径。仿真结果表明，改进算法在网络时延、传输比、分组平均能耗等方面均有较好的性能。今后还需要对算法的扩展性进行进一步的研究，例如在节点异构、节点供电方式不同、节点分布不均等情况下算法的扩展，从而提高算法对不同应用场景的适应性。

［1］ 姚忠邦，曹志刚.移动Ad Hoc网络中的负载均衡路由算法［J］.电讯技术，2004，6（1）：45-49.

［2］ Sunsook J，Nisar H，A lex Z.Node Caching Enhancement of Reactive Ad Hoc Routing Protocols［C］//Proceedings of IEEE Wireless Communications and Networking Conference.Washington D.C.，USA：IEEE Press，2005：1970-1975.

［3］ Hsiao P H，Hwang A，Kung H T，et al.Load-balancing Routing for Wireless Access Networks［C］//Proceedings of IEEE International Conference on Computer Communications.Washington D.C.，USA：IEEE Press，2001：986-995.

［4］ Pham P P，Perreau S.Performance Analysis of Reactive Shortest Path and Multi-path Routing Mechanism with Load Balance［C］//Proceedings of IEEE International Conference on Computer Communications.Washington D.C.，USA：IEEE Press，2003：251-259.

［5］ Souihli O，Frikha M，Hamouda M B.Load-balancing in MANET Shortest-path Routing Protocols［J］.Ad Hoc Networks，2009，7（2）：431-442.

［6］ 王莎莎，朱国晖，王 鑫.Ad Hoc网络负载均衡路由协议研究［J］.现代电子技术，2013，35（3）：40-46.

［7］ 贾站峰.Ad Hoc网络按需路由算法优化研究［D］.哈尔滨：哈尔滨工程大学，2010.

［8］ Ganjali Y，Keshavarzian A.Load Balancing in Ad Hoc Networks：Single-path Routing vs.Multi-path Routing［C］// Proceedings of IEEE International Conference on Computer Communications.Washington D.C.，USA：IEEE Press，2004：1120-1125.

［9］ Young JY，George F R.A Workload-based Adaptive Loadbalancing Technique for Mobile Ad Hoc Networks［C］// Proceedings of IEEE Wireless Communications and Networking Conference.Washington D.C.，USA：IEEE Press，2005：2002-2007.

［10］ Sunsook J，Nisar H，Alex Z.Energy Efficiency of Load Balancing in MANET Routing Protocols［C］//Proceedings of the 6th International Conference on Software Engineering，Artificial Intelligence，Networking and Parallel/ Distributed Computing and ACIS International Workshop on Self-assembling Wireless Networks.Washington D.C.，USA：IEEE Press，2005：476-483.

［11］ Xiao Shiliang，Pei Jun，Chen Xinwei，et al.Minimum Latency Broadcast in the SINR Model：A Parallel Routing and Scheduling Approach［J］.IEEE Communications Letters，2014，18（6）：1027-1030.

［12］ 郑相全，郭 伟.自组网中的负载均衡路由协议［J］.计算机科学，2004，31（13）：40-45.

［13］ Javad V R，Venkatesha P，Ertan O，et al.Enery-aware Routing Algorithm s for Wireless Ad Hoc Networks with Heterogeneous Power Supplies［J］.Computer Networks，2011，55（15）：3256-3274.

编辑 刘 冰

Load Balancing Routing Algorithm Based on AODV for Mobile Ad Hoc Network

CHEN Xinwei，YUAN Xiaobing，LI Baoqing
（Key Laboratory of National Defense for Science and Technology on Microsystem，Shanghai Institute of Microsystem and Information Technology，Chinese Academy of Sciences，Shanghai200050，China）

Unbalanced load of traditional Mobile Ad Hoc Network（MANET）results in bad consequences such as the increase of end-to-end delay，the decrease of delivery ratio and the death of nodes.In order to solve this problem，this paper proposes amodified load balancing routing algorithm based on Ad Hoc On-demand Distance Vector（AODV）.The algorithm adopts the single path method and considers both current load and occurred load.Queue lens and energy consumption of the nodes are used to evaluate the loads.The modified algorithm pays attention to the importance of the bottleneck nodes. Simulation results show that compared with the traditional algorithm such as AODV，improvement of energy path，this algorithm has good adaptability in different load cases，and can provide more stable network performance.

Mobile Ad Hoc Network（MANET）；queue waiting time；load balancing；routing algorithm；network delay

10.3969/j.issn.1000-3428.2015.11.025

陈昕韡，袁晓兵，李宝清.基于AODV的无线自组织网络负载均衡路由算法［J］.计算机工程，2015，41（11）：142-146.

英文引用格式：Chen Xinwei，Yuan Xiaobing，Li Baoqing.Load Balancing Routing Algorithm Based on AODV for M bile Ad Hoc Network［J］.Computer Engineering，2015，41（11）：142-146.

1000-3428（2015）11-0142-05

A

TP391

国家部委基金资助项目。

陈昕韡（1990-），女，硕士研究生，主研方向：无线传感器网络；袁晓兵、李宝清，研究员。

2014-11-21

2014-12-17 E-m ail：xinw eichen08@163.com