一种自适应的负载均衡按需路由算法

刘军帅,郝聚涛

(1.天津石油职业技术学院,天津 301607;2.上海理工大学,上海 200093)

一种自适应的负载均衡按需路由算法

刘军帅1,郝聚涛2

(1.天津石油职业技术学院,天津 301607;2.上海理工大学,上海 200093)

文章中,一种新的路由准则被引入到协议中,该准则用来从众多的路径中选择负载最轻且剩余能量最大的路径,用来提高分组传递率降低端到端时延。为了验证算法的性能,对所提协议进行了全面的仿真研究。研究结果表明,文章所提协议在包投递率和延迟性能方面均优于现有的路由协议。

路由协议;负载均衡;移动自组织网络;能量感知路由

一、引言

移动自组网(Mobile Ad Hoc Netw orks,MAN ET)是由一组移动节点构成的,不依赖于任何固定基础设施的无线网络[1]。处于无线传输范围内的节点可以直接通信,而相距较远的节点则需要依靠中间节点的转发进行通信。中间节点就充当了路由器的角色。由于不需要固定基础设施的支持,以及迅速部署的特点,Ad Hoc网络非常适合通信基础设施不存在或者无法正常使用的环境,其潜在的应用领域非常广泛,例如,军事战术网,灾难救助,移动会议、传感器网络和个人域网等。Ad hoc网络中,由于通信半径的限制,网络节点之间是通过多跳数据转发机制进行数据交互的,需要路由协议完成分组转发决策。与传统路由协议相比,Ad hoc路由协议的设计面临着网络拓扑动态变化、带宽受限、信道容量变化、移动终端有限的可用资源等新的问题和挑战。为MAN ET设计一个高效的路由协议是非常重要的,需要智能策略来确定最小开销的路由,以及保证路由具有很高的可扩展性。

在为数众多的已有移动自组织网络的路由协议中,动态源路由DSR[2,3]和AODV[4]是最为显著的两个代表。DSR利用源路由在移动自组织网络中寻找源节点到目的节点的路由。这类先验式路由,尽管每个数据分组都携带通往目的地的节点路径上的各节点信息,但同时也增加了大量的信号传输开销和能量消耗。由于带宽和电池电量是稀有资源,这也给这类路由协议的很大的局限性。在AODV协议中,只要源节点需要发送数据便维护路由。如果源节点移动,或者源节点到目的节点中间的某个步骤变为不可到达,路由发现过程便被重新发起。

然而,这些协议都没有涉及到路由中的负载均衡问题。在实际应用中,一些路由可能被拥塞,而另外一些则未被利用到。在这种情况下,部分节点将承担过重的负载,网络拥塞加剧,导致延迟增加、低包投递率和高路由开销等不满意的后果,最终导致网络性能降低。在负载均衡方面,目前文献中的负载均衡方法可以被分为两大类:多路径方法和单路径方法[5]。

在多径路由方面,Yin和Lin提出了一种多径负载均衡机制MALB,该机制通过循环调整每条路径上的流量比例,达到最小化网络端到端延迟的目的[6]。Wu和 Harms在两条互不相较的路径之间定义了一个系数作为分离路径上节点间的连接数[7]。结果显示,随着系数增加,沿着路径的时延也随即增加。Zhang提出了一个多路径源路由算法MSR[8],作为对DSR协议的扩展。MSR采用一种探测机制按需获得动态路径状态。这种机制可以被用来刷新缓存中的信息,删除陈旧路径并及时发现新路径。多路径负载平衡问题就是寻求最优解使得每条路径上的流量最小。然而,在单路径方法中,源节点和目的节点之间仅存在一条路径。因此,在文献中许多不同的负载均衡机制被提出。这些机制试图引导数据包避开拥塞的路径,以达到在网络内均衡负载的目的。例如,Zhu和Hassanein提出了一个新颖的路由协议称为LBAR[9],在该协议中定义了一个新的路由准则为节点的活动性,用节点的活动性来表示节点的负载。在文献[10]中,Lee和Riley也提出了一种机制,该机制给与负载过重的节点一自由,可以拒绝额外的通信通过它们,直到这种过载情况结束。Souihli和Frikha提出了将流量推向远离网络中心的机制以达到负载均衡的机制[11]。在该机制中使用了节点中心度作为路由准则。该机制提高了负载分布,使得网络性能在平均时延和可靠性方面得到提升。

能量高效也是移动无线网络重点关注的一个问题。由于多数移动节点是由电池供电,那么负载比较重的节点的电能可能被首先消耗完,并退出网络,导致网络节点的减少,并引起完网络的分割。此外,如果退出节点此时正处于某条通信链路中,那么可能导致链路的中端,从而引起路由发现开销和包投递延迟,同样降低了网络性能。

在文献[12]中,作者研究发现多数最短路径路由都要经过网络的中心,且节点越是接近网络中心所拥有的路由表条目也越多。基于这个观察结果,Souihli提出了一个新的路由准则,采用路由表的大小来选择路由。尽管这种负载均衡机制可以将数据流推向远离网络的中心,从而达到提高网络性能的目的,但是也并非非常完美。负载非常重的应用场景中,所有节点可能都想与其它节点进行通信,因此每个节点所拥有的路由表大小基本接近,那么在这种情况下,靠近网络中心的节点仍然是负载最重的节点,成为整个网络的瓶颈,制约网络性能。

基于上面的分析,在文本中我们提出了一个按需负载均衡的路由协议,在该协议中一个兼顾节点能量和负载的路由准则被提出,可以有效克服Souihli算法中所存在的问题。该路由准则会从众多路径中选择负载最轻且平均剩余能量值最大的路径。而负载的表示采用了Souihli所提出的用节点路由表大小来表示节点目前的负载。

二、自适应负载均衡路由:原理和实现

按需路由协议是一种按需路由协议,只有在两个节点需要进行通信,且源节点没有到达目的节点的路由时,才进行路由发现过程。以AODV为例,在AODV中使用广播式路由发现机制。当源节点想与另一节点进行通信,而它的路由表中又没有到达目的节点的路由条目时,就广播一个路由请求(RREQ)报文。中间节点在收到RREQ报文时,首先比较本节点和目的节点的IP地址,如果自己是目的节点,就向源节点回复路由响应(RREP)报文,如果自己不是目的节点,则根据RREQ报文中的源IP地址和广播ID判断是否收到过该RREQ报文,如果收到过,则丢弃该RREQ报文,若没有收到过该RREQ报文,就记录相关信息,用以形成反向路由。记录的信息主要包括目的地址、源地址、广播ID、源序列号、反向路由超时时长,同时将RREQ报文中的跳数字段(hop count)值加1,并向邻居节点转发RREQ报文。当中继节点或目的节点沿着反向路径回复RREP报文时,这条路径上的节点建立前向路由。当RREP报文到达源节点后,源节点就可以使用已经建立的路由发送数据报文。

由按需路由协议的原理可以看出,该类协议非常适合结点移动比较频繁的无线网络。然而当网络一旦运行平稳,数据传输总是集中在所选的最短路径上,导致处在多条通信链路上的节点成为网络瓶颈,引起网络性能下降。这主要是由于协议使用最短路径作为路由选择标准所导致的。

在本文中,我们所提的协议仍然是一个按需路由协议,并且也包括路由发现和路由维护两个过程。在每个阶段,协议采用AODV相似的机制,区别就是路由选择的标准。新的路由标准同时考虑了节点的负载和节点的剩余电量,目的就是从众多可能的路径中选出平均负载最小同时剩余电量最大的一条路径。该路由准则可以表示为:

式中sizeof(rtb(i))表示节点i的路由表大小。N表示当前路径中的所有节点数量,Er(i)反映了节点i的剩余能量。

在实施这个协议时,需要在路由请求包的头部增个三个项,分别用来表示路由的平均负载、平均剩余能量和新的路由标准。在本文中所采用的能量模型能量模型计算公式为:

即当一个节点发送或者接收一个包时所消耗的能量是由该节点发送或接收的功率和处理该包所需要的时间决定的。式中,处理一个包所需要的时间为:

式中,Ptx、Prx分别代表发送和接收时的功率。

对于转发一个包所消耗的全部能量为:

在路由发现阶段,当发送点想要向目的节点发送数据,而此时发送节点并没有可用路由,源节点就要发送一个 RREQ消息,该消息包含它的路由表大小、剩余能量和一个新的路由准则作为它的附加信息。此时,新的路由准则的计算公式为:

当中间节点I收到RREQ消息后,它会根据自己的实际情况,更新消息中的三个字段值。对于路由表项和剩余能量平均值的计算公式为:

式中,X表示路由表大小或者是剩余能量项,n表示由源节点到目前节点所经历的跳数。Avgx(n)代表 X项在前一节点处的平均值。

最后,当目标节点D收集到来自于不同路径的RREQ消息后,目的节点会从中选出对应于新的路由标准值最小的那条路径,而不是最短路径,并沿此路径发送一个RREP消息给源节点。至此,源节点和目的节点之间的路由建立。

三、协议仿真和性能评估

为了验证所提协议性能,本文在网络模拟平台NS2上进行了模拟试验,并与AODV协议和Souihli的方法[11]进行了比较。

1.仿真环境设置

在仿真模型中,设置了50个移动节点,随机分布在1200mx1200m的矩形区域内。无线传输模型采用双径地面反射模型,MAC层协议采用 IEEE802.11。传输层使用UDP,数据流采用CBR业务,包长度为512B,数据流辆分别设为:1Mb/s,5 Mb/s,10 Mb/s,15 Mb/s and 25 Mb/s.,最大连接数为100。节点的无线发射半径均为250m.。节点的移动模型采用随机移动模型,节点速度在0到25正态分布,节点在运动到一个目的地后不做停留继续运动。所有节点的初始能量设置为60焦,发射功率和接收功率分别为200mW和600mW。仿真时间设为300秒。

2.性能准则

在仿真试验中,我们重点对各种协议采用如下准则进行了对比:

(1)包投递率(PDR)

包投递率表示为目的节点接收到的包的数量与源节点发送包数量之比。

(2)端到端延迟

端到端延迟代表了所有包由源节点到达目的节点所经历时间的平均值。

3.性能评价

(1)包投递率(PDR)

在图1中,给出了三种协议在负载分别为1Mb/s,5 Mb/s,10 Mb/s,15 Mb/s和25 Mb/s的情况下,包投递率方面的比较结果。由图可以看出,在网络负载较重的情况下,Souihli的方法[11]和本文所提的方法在包投递率性能方面要强于AODV协议。同时伴随着负载逐渐增大,本文所提的算法在包投递率方面较之Souihli的方法[11]有更加突出的表现。

图1 包投递率比较

(2)端到端延迟

图2给出了三种协议在六种不同的负载下在端到端时延上的表现。在相对较轻的负载情况下,三种协议产生的时延大小差别不大。当给网络增大负载时,由AODV协议所产生的延迟逐渐变大,大大超过Souihli的和本文所提的方法。同时可以看出,本文所提协议在时延方面也要优于Souihli的方法。

图2 端到端延迟对比

四、结论

路由协议设计是移动自组织网络能否正常运作的重要条件。通常的一些协议在路由设计时仅考虑路径的长度问题,而没有结合路径上各节点的其它特征。这种路由准则虽然简单,但也容易导致各节点负载分配不均衡问题的产生。本文引入了一个新的路由准则,该准则同时考虑了节点的负载和节点的剩余能量问题。通过采用新的路由准则,路由协议会在众多可选的路径中选择一条负载最轻且剩余电量尽可能大的路径来传输数据。实验仿真结果也显示,本文所提的协议在包投递率和端到端时延方面有着显著的性能。

[1]Toh C.K.,Ad Hoc Mobile Wireless Networks:Protocols and Systems[M].Prentice Hall,2001.

[2]David B.Johnson,Davis A.Maltz,“The Dynamic Source Routing Protocol for Mobile Ad HocNetworks”[S].IETF Draft,Oct.1999.

[3]David B.Johnson,Davis A.Maltz,“Dynamic Source Routing in Ad Hoc Networks[J]”.Mobile Computing,T.Imielinski and H.Korth,Eds.Kulwer,1996,pp.152-81.

[4]Charles E.Perkins,Elizabeth M.Royer,Samir R.Das,“Ad Hoc On-demand Distance Vector Routing[S]”.IETF Draft,Oct.1999.

[5]Ganjali Y.,Keshavarzian A.,Load balancing in ad hoc networks:single-path routing vs.multi-path routing[C].in:Twenty-third Annual Joint Conference of the IEEE Computer and Communications Societies(INFOCOM 2004),March 2004.

[6]Yin S.,Lin X.,MALB:MANET adaptive load balancing[C].in:IEEE Vehicular Technology Conference(VTC2004-Fall),vol.4,September 2004,pp.2843-2847.

[7]Wu K.,Harms J.,Performance study of a multipath routing method for wireless mobile ad hoc networks[C].in:Proceeding of the Ninth International Symposium on Modeling,Analysis,and Simulation of Computer and Telecommu2 nications Systems(MASCOTS’01),August 2001.

[8]Zhang L.,Zhao Z.,Shu Y.,et al.Load balancing of multipath source routing in ad hoc networks[C].in:Proceed2 ing of the IEEE International Conference on Communications(ICC 2002),May2002.

[9]Zhou A.,Hassanein H.,Load-balanced wireless ad hoc routing[C].in:IEEE Canadian Conference on Electrical and Computer Engineering,vol.2,2001,pp.1157-1161.

[10]Lee Y.J.,Riley G.F.,A workload-based adaptive load-balancing technique for mobile ad hoc networks[C].in:IEEE Wireless Communications and Networking Conference(WCNC’2005),vol.1,2005,pp.2002-2007.

[11]Oussama Souihli,Mounir Frikha,Mahmoud Ben Hamouda,Load-balancing in MANET shortest-path routing protocols[J].Ad Hoc Networks xxx(2008)xxx-xxx).

[12]Pham P.,Perreau S.,Performance analysis of reactive shortest path and multi-path routing mechanisms with load balance[C].IEEE Conference on Computer Communications(INFOCOM 2003).

An Adaptive Algorithm of L oad Balancing on Demand Circuit

LIU Jun-shuai1,HAO Ju-tao2

(1.Tianjin Petroleum Vocational and Technical College,Tianjin 301607 China;2.University of Shanghai for Science and Technology,Shanghai 200093 China)

This essay introduces a new route principle into the treaty,which chooses the lightest and most powerf ul load f rom many circuits to imp rove the transfer speed and reduce the end-to-end time-lag.To imp rove its f unction,it makes a complete simulate research.The result shows that it is superior to existing circuits’treaty on package delivery f raction and delay.

route treaty;load balance;mobile self-organized network;energy perception route

TP393

A

1673-582X(2011)08-0032-05

2010-10-10

刘军帅 (1977-),男,天津石油职业技术学院讲师,硕士,主要从事焊接技术及自动化教学与研究。