基于HWMP协议的无线Mesh网络多网关路由协议研究

26卷󰀁第12期2009年12月

微电子学与计算机

MICROELECTRONICS&COMPUTER

Vol.26󰀁No.12December2009

基于HWMP协议的无线Mesh网络多网关路由协议研究

杨孟珂1,杨亚涛1,2,白中英1

(1北京邮电大学计算机科学与技术学院,北京100876;2北京电子科技学院,北京100070)

摘󰀁要:在HWMP协议的基础上,提出了支持多网关的M󰀁HWMP协议,使数据传输分散在多个网关上进行,进而提高Mesh网络的传输能力.另外,还提出了一种如何对多个网关进行选择的策略,该策略综合考虑了当前节点到网关节点的传输成本和该网关节点的剩余传输能力.经过仿真验证,M󰀁HWMP协议可以很好地正确运行,并有效地提高Mesh网络的传输能力.

关键词:无线Mesh网络;HWMP协议;多网关路由协议;网关选择策略

中图分类号:TP393󰀁󰀁󰀁󰀁󰀁文献标识码:A󰀁󰀁󰀁󰀁󰀁文章编号:1000-7180(2009)12-0004-05

ResearchonMulti󰀁PortalRoutingProtocolforWireless

MeshNetworksBasedonHWMP

YANGMeng󰀁ke,YANGYa󰀁tao

1

1,2

,BAIZhong󰀁ying

1

(1SchoolofComputerScience&Technology,BeijingUniversityofPostsandTelecommunications,Beijing100876,China;

2BeijingElectronicScience&TechnologyInstitute,Beijing100070,China)

Abstract:Amulti󰀁portalroutingprotocolbasedonHWMPwhichiscalledM󰀁HWMPisproposedinthispaper.Inthisprotocol,datatransmissionisscatteredonthenumberofportals,whichincreasestransmissioncapacityofMeshnetworks.Additionally,astrategyofportalselectionisalsopresentedinthepaperbywhichthetransportcosttotheportalandthesurplustransmissioncapacityoftheportalisconsidered.ThesimulationprovesM󰀁HWMPcanworksuccessfullyandim󰀁provetransmissioncapacityofMeshnetworkseffectively.

Keywords:WirelessMeshNetworks;HWMP;themulti󰀁portalroutingprotocol;astrategyofportalselection

1󰀁引言

随着网络技术的不断发展,无线化趋势变得越来越明显,人们迫切地需求一种高质量实用的无线网络接入技术.当前的IEEE802.11协议和IEEE802.16协议都有各自的缺点.因此,作为一种新的宽带无线网络架构,无线网状网(WirelessMeshNetwork,WMN)技术应运而生.

Mesh网技术在业界已经被认为是下一代无线网络的主流技术.从整体概念上来讲,Mesh网络的实体包括Mesh网用户终端和Mesh网路由器两部分.其中,Mesh网路由器构成了Mesh网络的骨干网部分.它可以是一个完全的无线节点,只是转发

收稿日期:2008-11-24

[1]

Mesh网内部的数据;也可以是和有线网络相连的路由器节点,用于实现Mesh网和外网的数据传输.用户终端可以通过选择最优的路由器进行注册,并链接到Mesh网络中.依照这种自组织、动态配置的网络体系架构,Mesh网络为用户终端提供了一种灵活的多跳无线网络接入方式[2].

具体的Mesh网技术标准正在被IEEE802.11、IEEE802.15和IEEE802.16标准工作组所制定.其中802.11s工作组负责制定基于IEEE802.11协议的无线Mesh网络的相关标准.

2󰀁HWMP路由协议

HWMP(HybridWirelessMeshProtocol)协议是

󰀁第12期杨孟珂,等:基于HWMP协议的无线Mesh网络多网关路由协议研究

5

IEEE802.11s草案中默认使用的路由协议[3].它是将反应式路由协议和基于树状拓扑的先验式路由协议相结合的综合性路由协议.也是针对Mesh网的基本特点而提出的,即大部分Mesh节点位置相对固定,骨干部分的Mesh节点很少变化并且可以灵活地加入和移除一些Mesh节点等.

当一个Mesh网络刚开始构建时,可以通过配置一个Mesh节点(一般为连接有线域的节点)为网关节点(MeshPortalPoint,MPP),由它作为根节点实现树状结构的路由网络.其他Mesh节点(MeshPoint,MP)先验式地维护到达根节点的路径,而根节点维护每个Mesh节点的路径,由此Mesh网络建立和维护起一个先验式的双向的距离矢量路径树.在MP节点有数据要发送时,它会根据路径树先向网关节点发送数据.如果该数据是向外网发送的数据,则MPP网关就会直接通过外网链路将数据包发送出去.如果该数据是向本Mesh网内其他MP节点发送的数据,则网关会将该数据转发至相应的MP节点,当该目的MP节点收到来自内网的源MP节点数据后,它会向源MP节点启动按需路径发现机制,并发送相应的路由请求包,而源节点会根据收到的该路由包添加直接通过Mesh网内的其他MP节点多跳地连接目的MP节点的路径.如果新的路由路径效率更高,则当接下来的数据需要发送时,就会通过这条内部的新路径进行传输.由于一个Mesh网络中网关节点离大部分的MP节点较远,所以这种直接通过网内节点相连的多跳传输方式一般更节省网络资源,效率也较高.

当HWMP路由协议配置为采用混合寻径策略时,就会按照以上的过程进行路由寻路.一旦先验式的路径树建立起来,这种方式可以实现要发送数据时的路径查询零等待时间;并且,由于反应式路由机制的加入,Mesh网内数据传输时可以选择最有效率的路径进行传输.然而,HWMP协议由于采用了以MPP节点为根的树状拓扑路由结构,这样靠近根部的链路和节点会成为整个网络流量的瓶颈,特别是在Mesh网内和网外有大量数据信息需要传输时,如图1所示,情况会变得更加严重[4].

图1󰀁Mesh网络场景图

就是网关节点MPP发送RANN帧或广播式PREQ帧,各节点收到后就可以填写自己到网关节点的路径并且更新这两类帧后进行转发.在RANN帧和PREQ帧中的Flags域,可以很清楚地标识出源节点是否是网关节点.所以,新的多网关路由协议对帧的结构不用做任何修改,每个网关节点都可以按照HWMP协议的规定进行路径树的构建.这样,只要对每个节点接到帧后的处理方式作出修改,以能建立合适的、正确的路径树就可以了.3.2󰀁多网关路由协议(M󰀁HWMP)

每个网关节点相对于别的网关节点都可以把自己作为普通节点来看待.例如,有两个网关节点MPP󰀁A和MPP󰀁B,当MPP󰀁A收到来自MPP󰀁B的广播包后(RANN帧或广播式PREQ帧),它会标识MPP󰀁B为网关节点,将到MPP󰀁B的路径信息记录在自己的路由表内,建立起到MPP󰀁B的路径,并向MPP󰀁B发送PREP帧.MPP󰀁B收到MPP󰀁A的广播包后也会做相应的处理.对于中间的MP节点,它们分别建立到MPP󰀁A和MPP󰀁B的路径.这样的结果就是一个Mesh域内,可以有多条路径树,每条路径树都以一个MPP为根节点.具体情况如图2所示,在这个3󰀂3的方阵所组成的Mesh域内,有两个网关节点,它们分别建立自己的路径树

[5]

.

3󰀁基于HWMP的多网关路由协议(M-HWMP)

3.1󰀁以HWMP为基础构建多网关路由协议的可

行性󰀁󰀁HWMP协议建立路径树的过程其实比较简单,

图2󰀁一个Mesh域内的多条路径树

6

微电子学与计算机2009年

因为每条路径树的建立有时间的先后,当MPP󰀁A建立起路径树后,对于每个中间节点MP,都将MPP󰀁B作为普通节点来看待的.这样当MPP󰀁B开始建立路径树时,中间的MP节点收到相应的包后就不能像原HWMP协议规定的那样判断Met󰀁ric而决定是否更新路由信息.在M󰀁HWMP中,对每个网关节点发送的路由信息包都必须强制性地更新,并标识是到网关节点的路径.否则后建立的路由树将可能失败.

当节点有数据要发送时,它应该查找每个网关节点的路由信息,根据Metric信息找到最优的网关节点作为当前的网关节点,将数据向该网关节点进行传送.这样就把整个Mesh网络的数据流量分配在了不同的出口网关节点上.一个例外的情况是每个网关节点自身,当它们自己有数据要发送时,首先是把自己作为当前网关节点,将数据向外网直接发送.当自己的外部网络出现问题时,它可以根据自己的路由信息向其他网关发送数据.因此,M󰀁HWMP协议的一个显著优点就是增加了网络的健壮性.3.3󰀁网关选择策略

既然是多网关路由协议,那么必然存在选择哪个网关的问题.在上节提到根据Metric信息来找到最优的网关节点,但是Metric域要如何填写还有待更进一步的研究[6].我们的目标是尽可能地使Met󰀁ric域表征当前节点到网关节点的成本度量和该网关节点所构建路径树的剩余能力度量.

IEEE802.11s对于两个节点间链路的成本度量是有提及的,但没有进行强制性规定,只是提供了一种参考建议.即将路径上所有链路参数Ca简单地累加起来,Ca表示链路的成本,它是一个基于射频敏感的链路参数[7].到目前为止已经有一些论文在讨论更好的度量节点间传输成本的方法,只需要很简单的改变Metric域的赋值定义就可以在现有的HWMP机制下运行.文中不涉及这方面的内容,所以仍采用链路参数Ca来讨论.

对于由该网关节点所构建的路径树的剩余能力度量应该包含两方面的内容:该网关节点的剩余传输能力和该路径树瓶颈区域的竞争传输情况度量.在实际组网中,不能要求每个网关节点的传输能力都是一样的,各网关节点之间在运行时必然存在一定的差异,那么如何表示这种差异性呢?可以采用一种较简单的方法,即用网关节点网络接口的输入缓冲区剩余情况来表征该网关的剩余能力,我们称为网关剩余能力系数(󰀁):Lmax-Lrecv

(1)

Lmax

式中,Lmax表示输入缓冲区最大长度,Lrecv表示收

󰀁=

到的数据包已经占有的缓冲区长度.当网关节点刚接入网络时󰀁等于1;当其缓冲区充满时,󰀁等于0.

路径树瓶颈区域一般是指靠近网关节点的区域,因为整个Mesh网络的出网流量在此区域大量汇集,易造成对此区域网络资源的激烈竞争.为了简化实现,我们只取和网关节点一跳相连的节点集合作为瓶颈区域,由在此区域的节点和网关节点之间链路的参数Ca算出平均链路参数Ca:

(n!0)(2)n

式中,n表示瓶颈区域的节点个数.因为Ca可以表示节点间链路的质量,所以Ca必然可以表示路径树瓶颈区域的传输情况.特例,当n=0时,即网关节点刚加入网络或周围没有任何一跳节点时,Ca取0.由以上讨论,可以将一个网关节点所构建的路径树的剩余能力度量Ctree定义为

Ctree=(1-󰀁)󰀂Ca

(3)

Ctree越大,表示该路径树的剩余传输能力越小.因此,在网关节点发送RANN帧和广播式PREQ帧时,Metric域不再像HWMP协议一样赋值为0,而是会计算Ctree,并将Ctree赋成Metric的初值.这样节点收到这些帧时会计算出将该网关节点作为当前网关的成本度量Metricto-mpp:

Metricto-mpp=󰀂󰀂Ctree+(1-󰀂)

i=0

Ca=

i=0

(Ca)i

n

(Ca)k

(4)

k

式中,

i=0

(Ca)k

k

表示该节点到网关节点的传输成

本,即将路径上所有链路参数简单地累加起来.󰀂是个可调参数Ca,用于综合考虑路径树的剩余能力和该节点到网关的传输成本.如果󰀂取0,表示不考虑此路径树的负载能力,而只是像HWMP那样将路径上所有链路参数Ca累加起来作为选择网关节点的依据.

当Mesh网内的一个节点有数据要发送时,他会比较到各个网关的Metricto󰀁mpp值,然后选择Metricto󰀁mpp值最小的网关节点作为当前网关节点进行传送.

4󰀁仿真实验

文中在NS2网络仿真工具[8]上对M󰀁HWMP󰀁第12期杨孟珂,等:基于HWMP协议的无线Mesh网络多网关路由协议研究

7

协议进行了仿真.目的是想观察M󰀁HWMP协议的运行情况和比较在网络负载逐渐加大的情况下,不同网关数目对Mesh网络传输能力的影响.仿真的场景为:由5󰀂5的MP节点构成Mesh网络方阵,其中位于四个角的节点将充当4个MPP;另外加上一个Mesh网外的节点作为Mesh网内节点发送数据的目的节点,该节点和4个MPP节点有线地相连.系统仿真环境参数如表1所示.

表1󰀁仿真环境参数表

名称MAC类型传输速率无线传输范围流量发生器类型数据包大小仿真时间节点队列类型节点队列长度

参数802.11b11Mb/s50mCBR1000bytes50sPriQueue100

况会有明显好转,特别是在网络重载的情况下,多网关的Mesh网络表现明显好于单网关的网络.另外,还可以观察到,随着负载逐渐增加,刚开始时网络传输效率急剧下降,当到达一定程度时,传输效率的下降开始趋缓,这是因为在当前的环境下,网络逐渐达到了一种饱和的状态.

图4是观察网关节点逐渐加入网络时,各网关节点吞吐量的变化情况.每个MP节点的CBR流量发生器速率为0.3Mb/s,仿真时间为100s,网关1在0s加入,网关2在10s加入,网关3在20s加入,网关4在30s加入,MP节点自5s时开始进行传输.可以看到,M󰀁HWMP协议在网关动态加入网络的情况下可以成功地运行.另外,在仿真的后半段,随着网络情况的稳定,四个网关节点的吞吐量趋于平衡,即每个网关都很好地分担了网络的传输负担.

在仿真阶段,每个MP节点都有数据要传送,传送的目的地址都设为Mesh网外节点,即这些数据都要经过网关节点向外网传送.仿真实验思路是:在不同的网关数目环境下,在CBR流量发生器的发送速率逐渐增加的情况下(网络负载逐渐加重),观察Mesh网络的传输能力.为了更好地说明问题,引入网络有效传输率 :

=

整个仿真时间内到达目的节点的数据总和

.整个仿真时间内所有节点CBR流量发生器发出的数据总和

图4󰀁网关节点吞吐量仿真

通过 值,不仅可以观察M󰀁HWMP协议的运行情况,也可以非常清晰地观察出各种情况下Mesh网络的传输能力.

图3即为仿真结果.可以看到,单个网关的Mesh网络传输能力是很弱的,在网络负载加大的情况下,传输效率急剧下降.随着网关数目地增加,情

5󰀁结束语

提出M󰀁HWMP协议,通过对HWMP做较少地改动,使整个Mesh网络形成以每个网关节点为根的多棵路由树,使出网流量尽可能均衡分担在这多棵路由树上,进而增加网络的传输能力.另外,既然有多个网关,就需要对其进行有效地选择,文中因此还提出了一种网关选择策略.该策略综合考虑了当前节点到网关节点的传输成本和该网关节点的剩余传输能力.仿真结果表明M󰀁HWMP协议能够很好地正确运行,并且在一定程度上有效地提高Mesh网络的传输能力.参考文献:

[1]AkyildizIanF,WangXudong,WangWeilin.Wireless

meshnetworks:asurvey[J].ComputerNetworks(S1389-1286),2005,47(4):445-487.

[2]蒙应杰,王雪芳.基于无线Mesh网络的分布式协调功图3󰀁M󰀁HWMP协议下网络传输能力图

8

微电子学与计算机2009年

能的研究[J].微电子学与计算机,2008,25(9):229-232.

[3]IEEEP802.11s(tm)/D2.0.DraftStandardforinforma󰀁

tiontechnology-telecommunicationsandinformationex󰀁changebetweensystems-localandmetropolitanareanet󰀁works-specificrequirements-part11:wirelessLANmediumaccesscontrol(MAC)andphysicallayer(PHY)specificationsamendment:meshnetworking[S].2008.[4]TsaiTzuJane,ChenJuwei.IEEE802.11MACprotocol

overwirelessmeshnetworks:problemsandperspectives[C]//19thInternationalConferenceonAdvancedInformationNetworkingandApplications.Taiwan,Hsinchu,2005(2):60-63.

[5]张勇,蔡杰,宋梅,等.无线mesh网络公平性研究[J].

中国科学技术大学学报,2007,37(2):164-170.[6]KoksalCE.Quality-awareroutingmetricsinwireless

meshnetworks[C]//WirelessMeshNetworks:Architec󰀁

turesandProtocols.Berlin:SpringerPress,2008:227-243.

[7]HouJC,ParkKJ,KimTS,etal.Mediumaccesscon󰀁

trolandroutingprotocolsforwirelessmeshnetworks[C]//WirelessMeshNetworks:ArchitecturesandProtocols.Berlin:SpringerPress,2008:77-112.

[8]肖晓丽,张卫平,康忠毅,等.HWMP协议的路径选择参

数的研究与改进[J].计算机工程与应用,2008,44(23):107-109.

作者简介:

杨孟珂󰀁男,(1983-),硕士研究生.研究方向为无线Mesh网络.

杨亚涛󰀁男,(1978-),博士研究生.研究方向为无线网络安全.

白中英󰀁男,(1941-),教授,博士生导师.研究方向为计算机体系结构.

(上接第3页)

[2]TanP,ZengG,WangJ,etal.Image-basedtreemodel󰀁

ing[J].ACMTrans.onGraphics,2007,26(3):877-884.

[3]VandenHengelAnthony,DickThorsten,Thormahlen

Torr,etal.VideoTrace:rapidinteractivescenemodellingfromvideo[C]//ProceedingsofSIGGRA󰀁PH.California;AcmPress,2007.

[4]BarbaraZitova,JanFlusser.Imageregistrationmethods:a

survey[J].ImageandVisionComputting,2003(21):977-1000.

[5]MikolajczykK,SchmidC.Aperformanceevaluationoflocal

descriptors[J].IEEETrans.PatternAnalysisandMachineIntelli-gence,2005,27(10):1615-1630.

[6]王国美,陈孝威.SIFT特征匹配算法研究[J].盐城工学

院学报:自然科学版,2007,20(2):1-5.

[7]LoweDG.Distinctiveimagefeaturesfromscale-invariant

keypoints[J].InternationalJournalofComputerVision,2004,60(2):91-110.

[8]田伟刚,郭雷,黄雷.一种应用于图像配准中的点特征匹

配算法[J].微电子学与计算机,2008,25(3):172-174.[9]BougnouxS.Fromprojectivetoeuclideanspaceunderany

practicalsituation,acriticismofself-calibration[C]//Proceedingsofthe6thInternationalConferenceonCom󰀁puterVision.India,Bombay,1998:790-796.

作者简介:

易成涛󰀁男,(1975-),博士研究生,讲师.研究方向为交通信息工程及控制.