无线传感器网络论文.docx

无线传感器网络论文.docx

《无线传感器网络论文.docx》由会员分享，可在线阅读，更多相关《无线传感器网络论文.docx（9页珍藏版）》请在冰点文库上搜索。

无线传感器网络论文

编号：

无线传感器网络

题目：

位置辅助按需距离矢量路由协议

院（系）：

电子工程与自动化学院

专业：

控制理论与控制工程

学生姓名：

郝涛

学号：

102081405

同作者：

郝涛

指导教师：

李小龙

职称：

副教授

题目类型：

理论研究实验研究工程技术研究

2010年12月6日

一种位置信息辅助的AdHoc网络按需距离矢量路由协议

摘要:

针对AdHoc网络中按需距离矢量路由协议路由开销大,以及位置路由中位置信息在获取方式上存在的缺点,提出一种位置信息辅助的按需距离矢量路由协议（LAODV）,协议结合AODV以按需的方式获取网络节点的位置信息,并以泛洪、位置信息修正的贪婪转发和局部受限泛洪相结合方式进行路由发现,同时提出了路由维护策略和局部多径备份路由策略.

关键词:

adhoc网络;路由;贪婪转发;多径

Abstract:

Todecreaseoverheadofon?

?

demandvectorroutingprotocolandovercomeshortcomingsoflocation?

?

aidedroutingsaboutgettinglocationinformation,anovellocation?

?

aidedadhocondemandvectorroutingprotocol（LAODV）isproposed.InLAODV,locationinformationisgotondemand.Duringroutediscovery,flooding,locationcorrect?

?

basedgreedyforwardstrategy（LCGF）andlimitedfloodinginexpectedzonearecombinedtoimprovetheperformance.Inaddition,anovelmethodforroutingmaintenanceandastrategyoflocalmultipathbackuproutingareillustrated.

Keywords:

adhocnetworks;routing;greedyforward;multipath

1引言

近年来AdHoc网络的路由协议研究取得了很大进展,大部分路由协议主要采取主动维护路由表或按需利用泛洪方式发现路由,由于AdHoc网络信道资源受限和动态拓扑,使得降低路由发现和维护开销成为重要研究内容.相比之下,按需路由比主动式路由更适合动态拓扑环境下的应用.GPS、GLONASS、北斗等定位系统的普及,使得网络中各个节点获得自己的位置信息变得可行,基于位置信息的路由协议由于具有很强的鲁棒性近来引起了关注,但当前的位置路由大多假设节点已知目的节点的位置信息,且位置信息获取通过位置服务器分发各节点位置信息或周期性广播节点位置信息,消耗了较多的网络资源,且网络的动态拓扑也降低了位置信息的时效性.以按需方式获取节点位置信息既能够保证位置信息的时效性,又能有效节省网络资源开销.AODV路由算法是性能最好的按需路由算法之一,但由于其路由发现过程只能形成一条从源至目的节点的单径路由,在分组转发过程中,一旦路径断裂,便需重新进行路由发现.由于AdHoc网络的高动态拓扑,必然导致要进行频繁的路由发现,从而增加路由开销,消耗过多网络资源.因此,如何降低AODV的路由开销显得非常必要.本章正是基于以上考虑,结合按需路由和位置路由的特点,提出了一种位置信息辅助的按需距离矢量路由协议LAODV.

2LAODV协议描述

LAODV协议是在传统AODV中有效地引入位置信息进行混合路由发现、维护等操作,降低路由发现开销,提高协议可扩展性.

2.1位置信息获取与传播

LAODV的位置信息获取是反应式、按需的,主要通过各种控制分组和数据分组学习获得,以这种方式获取的位置信息比通过节点或位置服务器周期性广播获取的位置信息具有更强的时效性.因为后者获取的位置信息时效性与广播间隔周期相关,周期越长,时效性越差,且存储的位置信息随着节点移动性加快,时效性越差.而按需的位置信息获取以及通过学习方式获得的其它节点位置信息,其时效性较强,这对于AODV路由断裂后,采用基于位置信息的路由发现是非常有利的.

2.2路由发现策略

2.21路由发现基本过程

根据目的节点位置信息是否可用,路由发现过程主要有两种方式:

一是目的节点位置信息不可用时以传统AODV方式的路由发现;二是目的节点位置信息可用时以贪婪转发和受限泛洪相结合的混合路由发现.具体过程为:

当源节点需要发现一条到达目的节点的路由时,首先检查其本地路由表,如果有可用路由,则直接使用;如果路由表中没有可用路由,则在本地位置信息列表中查询目的节点的位置信息,如果位置信息列表中有目的节点的位置信息,则采用2.2.2节提出的LCGF转发策略进行路由发现;如果没有目的节点的位置信息,则采用AODV的泛洪方式广播其路由请求分组RREQ来查找路由.

路由响应过程与传统AODV的路由响应机制相同.

2.2.2位置信息修正的贪婪转发策略LCGF

贪婪转发策略是指在分组转发时,中间节点将分组转发到位于目的方向上的一个邻节点,通常情况下,分组能够被有效地转发至目的节点.但有时贪婪转发在源和目的节点间存在路由的情况下也找不到路由.

当源节点利用目的节点位置信息进行基于位置的路由发现时,采用这里提出的LCGF策略.

LCGF策略遵循如下几个原则:

1目的节点位置信息修正

在传统基于位置的贪婪转发中,源节点将t0时刻更新的目的节点d的位置信息包含于RREQ分组中,中间参与转发的节点都以该时刻目的节点位置信息作为选择下一跳转发节点的参考方向.而在本文的位置信息获取可以通过不断从其它分组中学习得到,具有更强的时效性.如图2所示,假设源节点S位置信息列表中存在t0时刻更新的目的节点有效位置信息,如果在t1>t0时刻节点S?

需要与节点D通信,则节点B会从节点D发至S?

的RREP分组中获得节点D在t2>t1时刻的更新位置信息.所以当节点S在t3时刻需要与节点D通信,且路由表中无可用路由和t3-UT（D）

在以贪婪方式转发分组的过程中,如果中间转发节点存储的关于目的节点的位置信息比来自源节点的RREQ分组中包含的目的节点位置信息时效性更强时,则在转发该RREQ分组前,利用本地关于目的节点的位置信息将RREQ中的目的节点位置信息替代,这一过程称为目的节点位置信息修正.

2采用最大前程的贪婪转发策略

当源节点具有目的节点的位置信息时,则利用贪婪转发策略进行路由请求.在一个带宽受限的网络中,路径越长,则端到端时延越大,消耗的网络带宽也相应较多.因此,最小跳数的路由发现成为大多数路由协议进行路由发现时的度量准则.本文的贪婪转发策略也以最短路径为目标,在贪婪转发过程中,选择具有最大前程的邻节点作为下一跳转发节点.

3局部受限泛洪的贪婪转发失败恢复策略

所谓局部受限泛洪就是在贪婪转发失败时,由转发失败的节点确定的局部区域进行泛洪.局部受限泛洪区域是一个矩形区域,如图3所示,其中R=?

?

（t1-t0）,其中?

?

、t0和t1分别为目的节点平均移动速度、获知目的节点位置信息时的时刻以及发起路由请求时的时刻.受限泛洪基本过程为:

源节点S进行贪婪转发,设贪婪转发过程中依次选择的下一跳节点为B,?

E,F,G;

当转发至G时,G在其与目的节点方向没有邻节点,则发送一个贪婪转发失败分组G-FAIL至上一跳节点F,G-FAIL分组中包括修正后的目的节点D的位置信息;

节点F收到G-FAIL分组后,对目的节点位置信息进行修正,然后判决区域Fbcd与F的传输范围重叠区域内是否有除G以外的节点,如果有其它邻节点,则节点在Fbcd区域内以泛洪方式向目的节点发起路由请求,路由请求的源节点S替换为本节点F;

如果重叠区域内没有邻节点,则F向E发送一个错误分组G-FAIL;节点E收到G-FAIL分组后,与F的处理相同;

如果源节点S收到G-FAIL分组,则本次贪婪转发失败,S在全网泛洪路由请求;

至此,路径B,?

E,F中的某个节点能够确定一个受限的泛洪区域,并等待节点D的路由响应分组RREP,目的节点只对最先到达的RREQ进行响应;收到目的节点RREP后,向源节点S发送路由响应RREP.

根据以上三个准则,利用位置信息进行路由发现的LCGF策略的完整过程为:

当源节点S需要利用目的节点位置信息进行路由发现时,将目的节点D的位置信息插入RREQ分组,采用最大前程的贪婪转发策略在其邻居节点集中选择一个距离目的节点最近的邻节点X作为下一跳转发节点,发送RREQ分组至节点X;

一个中间节点收到来自上一跳节点的RREQ分组且需要转发时,如果本节点是目的节点,或者本节点路由表中存在一条到达目的节点的有效路由,且目的节点序列号满足AODV要求,则向上一跳节点发送RREP分组,路由请求结束;如果无有效路由存在,则转入第三步;

利用目的节点位置信息修正机制进行位置信息修正,并检查其邻居节点列表,如果目的节点在其邻居节点集中,则发送RREQ至目的节点,路由请求结束;否则,如果在到目的节点的方向上有邻节点,则转入第四步;如果在到目的节点的方向上没有邻节点,则转入第五步;

选择距离目的节点最近的邻节点Y作为下一跳转发节点,发送RREQ分组至Y,转入第二步重复;

采用局部受限泛洪的贪婪转发失败恢复策略转发RREQ分组.

对于路由请求的响应过程,与传统的AODV响应机制相同,沿着路由请求的逆向路径发送RREP分组至源节点.

2.3路由维护策略

在进行路由协议设计时考虑路由维护策略是必要的,可以有效提高数据分组的转发效率.路由修复有两种情况:

当节点路由表中存贮的路由当前正在使用,这类路由的断裂对网络的影响较大,需要及时修复;另一些路由当前可能未被使用,当其断裂时,在一定时间内不对网络产生影响,不需要实时修复.在LAODV中,我们将路由表中的路由分为两类:

活动路由（active,正在被使用的路由）;后活动路由（postactive,一个路由被使用过,但现在没有被使用）,对这两种路由分别进行不同策略的维护,从而降低路由开销.路由维护策略分为两部分:

（1）活动路由维护

当一个活动路由的下一跳发生方向性链路中断时,则节点发送一个Hello消息至该邻节点,并设置定

时器T1;

在T1内如果收到该邻节点的响应分组,则修复

该链路;

如果在T1超时后,没有收到响应分组,且其至目的节点的距离小于MAX-REPAIR-TTL[1]时,则转入第四步,如果距离大于MAX-REPAIR-TTL,则转入第五步;

如果本节点存有目的节点位置信息,则利用LCGF算法向目的节点发送RREQ,如果本地没有目的节点可用位置信息,则本节点向目的节点广播RREQ;

向所有前趋节点（precursor）广播一个路由错误分组RRER.

（2）后活动路由维护

由于在路由表中的后活动路由长时间不被使用,对其进行实时修复没有必要,而且消耗网络资源,所以采用被动的修复方式.所谓被动修复是指当本地路由表中一条后活动路由的下一跳链路断裂时,以链路层Hello消息的周期TMAC作为超时间隔,如果在TMAC内收到任何来自于该连链路的对端节点的分组（Hello,RTS,CTS,DATA等）,则自动修复该方向性链路,如果在TMAC超时后没有收到来自该节点的任何分组,则向所有前驱节点发送RERR.

2.4局部多径备份路由策略

为提高在高动态网络环境下,路由频繁断裂时的路由性能,提出了局部多径备份路由策略.

定义:

节点A至节点B之间的一条主路径P,主路径节点集合N（P）,N（P）中各节点邻居集的并集为N（all）=?

vN（P）N（v）,其中N（v）为节点v不包括P中节点的邻居节点集.如果在A和B之间除了路径P以外,还存在由N（P）?

N（all）中节点形成的路径,则称A和B之间存在局部备份路由.

局部多径备份路由策略设计目标是在尽量降低路由发现开销的情况下,尽可能满足主路径上任何两个节点间存在局部备份路由,使得在分组转发过程中,当转发节点发现与下一跳节点链路断裂时,能够选择备份路径进行转发.该策略仅仅在路由响应过程中形成,对路由开销的影响很小.主要过程如下:

每个节点维护一个备份路由表（BRT?

?

BackupRouteTable）,BRT中到达同一目的节点的路由记录可能有多个,主路径中节点的邻节点发送备份路由响应的分组为B-REPP;

源节点S和目的节点D的主路径P中某一个节点u向上一跳节点发送RREP,?

?

wN（u）的节点监听到该RREP时:

如果BRT中有到D的路由,则节点w向节点u发送备份路由响应分组B-REPP,其中指示该路由为备份路由;如果BRT中没有到D的路由,则在BRT中记录REPP中到达D的路由;（?

?

vP,?

?

xN（all）,节点v收到节点x发送的B-REPP分组时,节点v在其BRT中记录该备份路由;（?

?

x,yN（all）,节点y收到节点x的B-REPP分组时:

如果节点y的BRT中有到目的节点D的备份路由,且到目的节点的跳数小于该分组中包含的路由跳数,则y向x发送B-REPP分组;如果节点y的BRT中没有到目的节点D的路由,则丢弃该R-REPP分组.

为了使得局部备份路由能够有效地满足主路径链路断裂时的应用,局部备份路由应满足如下约束条件:

约束1:

BRT中备份路由不用于路由请求RREQ的响应;

由于BRT中可能存在到达同一目的节点的多个跳数不同的备份路由,且通常不是最短路径,如果利用局部备份路由进行路由响应会导致LAODV非最短路径经常发生.

约束2:

对局部备份路由不进行本地修复;为了降低多径路由修复开销,当局部备份路由发生断裂时,不进行本地修复.

约束3:

当主路径中的一个转发节点利用局部备份路由进行数据分组转发时,该转发节点要将数据分组头部的剩余路由跳数选项改为剩余跳数的两倍,以保证在该转发节点至目的节点之间存在任意一条备份路径情况下数据分组都能够成功转发.

因为主路径上某个节点的局部备份路由的最长跳数是从该节点至目的节点跳数的两倍,如图4所示,主路径P={S,A,B,C,E,D},节点A至目的节点D的距离是4跳,节点A在转发数据分组时,最坏情况下,A至D之间的主路径全断裂,此时的备份路径是{A,G,B,H,C,I,E,J,D},距离为8跳.所以,当采用局部备份路径进行分组转发时,数据分组的跳数应该设为原跳数的两倍,以保证在最坏情况下分组的成功递交.

3总结

本文结合位置信息与按需距离矢量机制进行路由设计,提出了一种位置信息辅助的按需距离矢量路由协议（LAODV）,协议以按需的方式获取网络节点的位置信息,并结合泛洪、贪婪转发和局部受限泛洪方式进行路由发现,对路由进行区分维护,同时提出了LAODV协议的多径备份路由策略,以提高路由协议性能.仿真结果表明,LAODV能够有效适应AdHoc网络的动态拓扑,具有较好的路由性能.

谢辞

这次论文我是在李小龙老师的精心指导下完成的，从他那里学习到了许多宝贵的知识和经验。

他本人治学态度严谨、渊博的学术知识、不断进取的学习精神、和蔼的待人方式以及不拘一格的教育理念都让我深受启发。

我还要感谢我们班以及我们系我所认识的老师和同学，是他们给了我好的环境和鼓励帮助，让我顺利地完成了这次的论文。

在这段时间里，我有过不少的困难和挫折，不过我能够从困难中站起来，通过请教老师、同学和查阅大量资料，终于做完了论文。

参考文献:

[1]CPerkins,EBelding-Royer,SDas.AdhocOnDemandDistanceVector（AODV）Routing[S].IETFRFC3561,2003.

[2]DavidBJohnson,DavidAMaltz.TheDynamicSourceRoutingProtocolforMobileAdHocNetworks（DSR）[S].http:

//tools.ietf.org/html/draft?

?

ietf?

?

manetdsr10.txt,July,2004.

[3]MarioGerla,XiaoyanHong.FisheyeStateRoutingProtocol（FSR）forAdHocNetworks[S].http:

//tools.ietf.org/html/draft?

?

ietf?

?

manet?

?

fsr?

?

03.txt,December,2002.

[4]TClausen,PJacquet.OptimizedLinkStateRoutingProtocol（OLSR）[S].IETFRFC3626,2003.

[5]ZygmuntJHaas,MarcRPearlman,PrinceSamar.TheZoneRoutingProtocol（ZRP）forAdHocNetworks[S].http:

//tools.ietf.org/id/draft?

?

ietf?

?

manetzonezrp04.txt,July,2002.