1、无线传感器网络论文编号： 无线传感器网络题 目： 位置辅助按需距离矢量路由协议 院 （系）： 电子工程与自动化学院 专 业： 控制理论与控制工程 学生姓名： 郝 涛 学 号： 102081405 同 作 者： 郝 涛 指导教师： 李小龙 职 称： 副 教 授 题目类型： 理论研究 实验研究 工程技术研究 2010 年 12 月 6 日一种位置信息辅助的Ad Hoc 网络按需距离矢量路由协议摘 要: 针对Ad Hoc 网络中按需距离矢量路由协议路由开销大, 以及位置路由中位置信息在获取方式上存在的缺点, 提出一种位置信息辅助的按需距离矢量路由协议( LAODV) , 协议结合AODV 以按需的方
2、式获取网络节点的位置信息, 并以泛洪、位置信息修正的贪婪转发和局部受限泛洪相结合方式进行路由发现, 同时提出了路由维护策略和局部多径备份路由策略.关键词: ad hoc 网络; 路由; 贪婪转发; 多径Abstract: To decrease o verhead of on?demand vector routing protocol and overcome shortcomings of location?aided routing s about getting location information, a novel location?aided ad hoc on demand
3、vector routing protoco l ( LAODV) is proposed. In LAODV, location information is got on demand. During ro ute discovery , flooding , location correct?based greedy forward strategy ( LCGF) and limited flooding in expected zone are combined to improve the performance. In addition, a no vel method for
4、routing maintenance and a strategy of local multi path backup routing are illustrated.Key words: ad hoc networks; ro uting; greedy forward; multi path1 引言 近年来Ad Hoc 网络的路由协议研究取得了很大进展, 大部分路由协议主要采取主动维护路由表或按需利用泛洪方式发现路由, 由于Ad Hoc 网络信道资源受限和动态拓扑, 使得降低路由发现和维护开销成为重要研究内容. 相比之下, 按需路由比主动式路由更适合动态拓扑环境下的应用. GPS、GL
5、ONASS、北斗等定位系统的普及, 使得网络中各个节点获得自己的位置信息变得可行, 基于位置信息的路由协议由于具有很强的鲁棒性近来引起了关注, 但当前的位置路由大多假设节点已知目的节点的位置信息, 且位置信息获取通过位置服务器分发各节点位置信息或周期性广播节点位置信息, 消耗了较多的网络资源, 且网络的动态拓扑也降低了位置信息的时效性.以按需方式获取节点位置信息既能够保证位置信息的时效性, 又能有效节省网络资源开销. AODV 路由算法是性能最好的按需路由算法之一, 但由于其路由发现过程只能形成一条从源至目的节点的单径路由, 在分组转发过程中, 一旦路径断裂, 便需重新进行路由发现. 由于Ad
6、 Hoc 网络的高动态拓扑, 必然导致要进行频繁的路由发现, 从而增加路由开销, 消耗过多网络资源. 因此, 如何降低AODV 的路由开销显得非常必要.本章正是基于以上考虑, 结合按需路由和位置路由的特点, 提出了一种位置信息辅助的按需距离矢量路由协议LAODV.2 LAODV协议描述 LAODV 协议是在传统AODV 中有效地引入位置信息进行混合路由发现、维护等操作, 降低路由发现开销, 提高协议可扩展性.2.1 位置信息获取与传播LAODV 的位置信息获取是反应式、按需的, 主要通过各种控制分组和数据分组学习获得, 以这种方式获取的位置信息比通过节点或位置服务器周期性广播获取的位置信息具有
7、更强的时效性. 因为后者获取的位置信息时效性与广播间隔周期相关, 周期越长, 时效性越差, 且存储的位置信息随着节点移动性加快, 时效性越差. 而按需的位置信息获取以及通过学习方式获得的其它节点位置信息, 其时效性较强, 这对于AODV 路由断裂后, 采用基于位置信息的路由发现是非常有利的.2. 2 路由发现策略2.2 1 路由发现基本过程根据目的节点位置信息是否可用, 路由发现过程主要有两种方式: 一是目的节点位置信息不可用时以传统AODV 方式的路由发现; 二是目的节点位置信息可用时以贪婪转发和受限泛洪相结合的混合路由发现.具体过程为: 当源节点需要发现一条到达目的节点的路由时, 首先检查
8、其本地路由表, 如果有可用路由, 则直接使用; 如果路由表中没有可用路由, 则在本地位置信息列表中查询目的节点的位置信息, 如果位置信息列表中有目的节点的位置信息, 则采用2. 2. 2 节提出的LCGF 转发策略进行路由发现; 如果没有目的节点的位置信息, 则采用AODV 的泛洪方式广播其路由请求分组RREQ 来查找路由.路由响应过程与传统AODV 的路由响应机制相同.2.2 .2 位置信息修正的贪婪转发策略LCGF贪婪转发策略是指在分组转发时, 中间节点将分组转发到位于目的方向上的一个邻节点, 通常情况下,分组能够被有效地转发至目的节点. 但有时贪婪转发在源和目的节点间存在路由的情况下也找
9、不到路由.当源节点利用目的节点位置信息进行基于位置的路由发现时, 采用这里提出的LCGF 策略.LCGF 策略遵循如下几个原则:1 目的节点位置信息修正在传统基于位置的贪婪转发中, 源节点将t0 时刻更新的目的节点d 的位置信息包含于RREQ 分组中, 中间参与转发的节点都以该时刻目的节点位置信息作为选择下一跳转发节点的参考方向. 而在本文的位置信息获取可以通过不断从其它分组中学习得到, 具有更强的时效性. 如图2 所示, 假设源节点S 位置信息列表中存在t 0 时刻更新的目的节点有效位置信息, 如果在t 1 t0 时刻节点S?需要与节点D 通信, 则节点B 会从节点D 发至S?的RREP 分
10、组中获得节点D 在t 2 t 1 时刻的更新位置信息. 所以当节点S 在t3 时刻需要与节点D 通信, 且路由表中无可用路由和t3- UT ( D) T ,UT ( D) 表示节点存贮的关于节点D 的位置信息更新时间, T 表示位置信息有效生存时间. 则S 将节点D 在t 0时刻更新的位置信息插入RREQ 分组中. 当S 发送的RREQ 分组以贪婪方式转发至节点B 时, 显然, 节点B存储的节点D 的位置信息比RREQ 中的时效性强, 则利用更新的位置信息替换RREQ 中的相应选项.在以贪婪方式转发分组的过程中, 如果中间转发节点存储的关于目的节点的位置信息比来自源节点的RREQ 分组中包含的
11、目的节点位置信息时效性更强时, 则在转发该RREQ 分组前, 利用本地关于目的节点的位置信息将RREQ 中的目的节点位置信息替代, 这一过程称为目的节点位置信息修正.2 采用最大前程的贪婪转发策略当源节点具有目的节点的位置信息时, 则利用贪婪转发策略进行路由请求. 在一个带宽受限的网络中,路径越长, 则端到端时延越大, 消耗的网络带宽也相应较多. 因此, 最小跳数的路由发现成为大多数路由协议进行路由发现时的度量准则. 本文的贪婪转发策略也以最短路径为目标, 在贪婪转发过程中, 选择具有最大前程的邻节点作为下一跳转发节点.3 局部受限泛洪的贪婪转发失败恢复策略所谓局部受限泛洪就是在贪婪转发失败时
12、, 由转发失败的节点确定的局部区域进行泛洪. 局部受限泛洪区域是一个矩形区域, 如图3 所示, 其中R= ?( t1-t 0) , 其中?、t0 和t 1 分别为目的节点平均移动速度、获知目的节点位置信息时的时刻以及发起路由请求时的时刻. 受限泛洪基本过程为: 源节点S 进行贪婪转发, 设贪婪转发过程中依次选择的下一跳节点为B, ?, E, F, G;当转发至G 时, G 在其与目的节点方向没有邻节点, 则发送一个贪婪转发失败分组G- FAIL 至上一跳节点F, G- FAIL 分组中包括修正后的目的节点D 的位置信息;节点F 收到G- FAIL 分组后, 对目的节点位置信息进行修正, 然后判
13、决区域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
14、发送路由响应RREP.根据以上三个准则, 利用位置信息进行路由发现的LCGF 策略的完整过程为:当源节点S 需要利用目的节点位置信息进行路由发现时, 将目的节点D 的位置信息插入RREQ 分组,采用最大前程的贪婪转发策略在其邻居节点集中选择一个距离目的节点最近的邻节点X 作为下一跳转发节点, 发送RREQ 分组至节点X ; 一个中间节点收到来自上一跳节点的RREQ 分组且需要转发时, 如果本节点是目的节点, 或者本节点路由表中存在一条到达目的节点的有效路由, 且目的节点序列号满足AODV 要求, 则向上一跳节点发送RREP 分组, 路由请求结束; 如果无有效路由存在, 则转入第三步 ;利用目的
15、节点位置信息修正机制进行位置信息修正, 并检查其邻居节点列表, 如果目的节点在其邻居节点集中, 则发送RREQ 至目的节点, 路由请求结束; 否则, 如果在到目的节点的方向上有邻节点, 则转入第四步;如果在到目的节点的方向上没有邻节点, 则转入第五步 ;选择距离目的节点最近的邻节点Y 作为下一跳转发节点, 发送RREQ 分组至Y, 转入第二步重复;采用局部受限泛洪的贪婪转发失败恢复策略转发RREQ 分组.对于路由请求的响应过程, 与传统的AODV 响应机制相同, 沿着路由请求的逆向路径发送RREP 分组至源节点.2. 3 路由维护策略在进行路由协议设计时考虑路由维护策略是必要的, 可以有效提高
16、数据分组的转发效率. 路由修复有两种情况: 当节点路由表中存贮的路由当前正在使用, 这类路由的断裂对网络的影响较大, 需要及时修复; 另一些路由当前可能未被使用, 当其断裂时, 在一定时间内不对网络产生影响, 不需要实时修复. 在LAODV 中, 我们将路由表中的路由分为两类: 活动路由( active, 正在被使用的路由) ; 后活动路由( postactive, 一个路由被使用过, 但现在没有被使用) , 对这两种路由分别进行不同策略的维护, 从而降低路由开销. 路由维护策略分为两部分: (1) 活动路由维护当一个活动路由的下一跳发生方向性链路中断时, 则节点发送一个Hello 消息至该邻
17、节点, 并设置定时器T 1; 在T 1 内如果收到该邻节点的响应分组, 则修复该链路;如果在T1 超时后, 没有收到响应分组, 且其至目的节点的距离小于MAX- REPAIR- TTL 1 时, 则转入第四步, 如果距离大于MAX- REPAIR- TTL, 则转入第五步 ;如果本节点存有目的节点位置信息, 则利用LCGF 算法向目的节点发送RREQ, 如果本地没有目的节点可用位置信息, 则本节点向目的节点广播RREQ;向所有前趋节点(precursor)广播一个路由错误分组RRER.(2) 后活动路由维护由于在路由表中的后活动路由长时间不被使用,对其进行实时修复没有必要, 而且消耗网络资源,
18、 所以采用被动的修复方式. 所谓被动修复是指当本地路由表中一条后活动路由的下一跳链路断裂时, 以链路层Hello 消息的周期TMAC作为超时间隔, 如果在TMAC内收到任何来自于该连链路的对端节点的分组(Hello, RTS,CTS,DATA 等) , 则自动修复该方向性链路, 如果在TMAC超时后没有收到来自该节点的任何分组, 则向所有前驱节点发送RERR.2. 4 局部多径备份路由策略为提高在高动态网络环境下, 路由频繁断裂时的路由性能, 提出了局部多径备份路由策略.定义: 节点A 至节点B 之间的一条主路径P, 主路径节点集合N( P ) , N( P) 中各节点邻居集的并集为N( al
19、l ) = ?v N( P )N( v ) , 其中N( v ) 为节点v 不包括P 中节点的邻居节点集. 如果在A 和B 之间除了路径P 以外,还存在由N( P) ? N( all ) 中节点形成的路径, 则称A和B 之间存在局部备份路由.局部多径备份路由策略设计目标是在尽量降低路由发现开销的情况下, 尽可能满足主路径上任何两个节点间存在局部备份路由, 使得在分组转发过程中, 当转发节点发现与下一跳节点链路断裂时, 能够选择备份路径进行转发. 该策略仅仅在路由响应过程中形成,对路由开销的影响很小. 主要过程如下:每个节点维护一个备份路由表( BRT?BackupRoute Table) ,
20、BRT 中到达同一目的节点的路由记录可能有多个, 主路径中节点的邻节点发送备份路由响应的分组为B- REPP;源节点S 和目的节点D 的主路径P 中某一个节点u 向上一跳节点发送RREP, ?w N ( u) 的节点监听到该RREP 时: 如果BRT 中有到D 的路由, 则节点w 向节点u 发送备份路由响应分组B- REPP, 其中指示该路由为备份路由; 如果BRT 中没有到D 的路由, 则在BRT中记录REPP 中到达D 的路由; ( ?v P, ?x N( all ) , 节点v 收到节点x 发送的B- REPP 分组时, 节点v 在其BRT 中记录该备份路由; ( ? x, y N (
21、all ) , 节点y 收到节点x 的B- REPP 分组时: 如果节点y 的BRT 中有到目的节点D 的备份路由, 且到目的节点的跳数小于该分组中包含的路由跳数, 则y 向x 发送B- REPP 分组; 如果节点y 的BRT 中没有到目的节点D 的路由, 则丢弃该R- REPP 分组.为了使得局部备份路由能够有效地满足主路径链路断裂时的应用, 局部备份路由应满足如下约束条件:约束1: BRT 中备份路由不用于路由请求RREQ 的响应;由于BRT 中可能存在到达同一目的节点的多个跳数不同的备份路由, 且通常不是最短路径, 如果利用局部备份路由进行路由响应会导致LAODV 非最短路径经常发生.约
22、束2: 对局部备份路由不进行本地修复;为了降低多径路由修复开销, 当局部备份路由发生断裂时, 不进行本地修复.约束3: 当主路径中的一个转发节点利用局部备份路由进行数据分组转发时, 该转发节点要将数据分组头部的剩余路由跳数选项改为剩余跳数的两倍, 以保证在该转发节点至目的节点之间存在任意一条备份路径情况下数据分组都能够成功转发.因为主路径上某个节点的局部备份路由的最长跳数是从该节点至目的节点跳数的两倍, 如图4 所示, 主路径P= S, A , B, C, E, D , 节点A 至目的节点D 的距离是4 跳, 节点A 在转发数据分组时, 最坏情况下, A至D 之间的主路径全断裂, 此时的备份路
23、径是 A , G,B,H , C, I , E, J, D , 距离为8 跳. 所以, 当采用局部备份路径进行分组转发时, 数据分组的跳数应该设为原跳数的两倍, 以保证在最坏情况下分组的成功递交.3 总结本文结合位置信息与按需距离矢量机制进行路由设计, 提出了一种位置信息辅助的按需距离矢量路由协议( LAODV) , 协议以按需的方式获取网络节点的位置信息, 并结合泛洪、贪婪转发和局部受限泛洪方式进行路由发现, 对路由进行区分维护, 同时提出了LAODV 协议的多径备份路由策略, 以提高路由协议性能. 仿真结果表明, LAODV 能够有效适应Ad Hoc 网络的动态拓扑, 具有较好的路由性能.
24、谢 辞这次论文我是在李小龙老师的精心指导下完成的，从他那里学习到了许多宝贵的知识和经验。他本人治学态度严谨、渊博的学术知识、不断进取的学习精神、和蔼的待人方式以及不拘一格的教育理念都让我深受启发。我还要感谢我们班以及我们系我所认识的老师和同学，是他们给了我好的环境和鼓励帮助，让我顺利地完成了这次的论文。在这段时间里，我有过不少的困难和挫折，不过我能够从困难中站起来，通过请教老师、同学和查阅大量资料，终于做完了论文。参考文献: 1 C Perkins, E Belding- Royer, S Das. Ad hoc On Demand Distance Vector ( AODV) Ro uti
25、ng S . IETF RFC3561, 2003. 2 David B Johnson, David A Maltz. The Dynamic Source RoutingProtocol for Mobile Ad Hoc Networks ( DSR) S . http: / /tools. ietf. org/ html/ draft?ietf?manet dsr 10. txt, July , 2004. 3 Mario Gerla, Xiaoyan Hong. Fisheye State Routing Protocol( FSR) for Ad Ho c Networks S .
26、 http: / / too ls. ietf. org/ html/draft?ietf?manet?fsr?03. txt, December , 2002. 4 T Clausen, P Jacquet. Optimized Link State Routing Protocol( OLSR) S . IETF RFC3626, 2003. 5 Zygmunt J Haas, Marc R Pearlman, Prince Samar. The ZoneRo uting Protocol ( ZRP) for Ad Ho c Networks S . http: / /tools. ietf. org/ id/ draft?ietf?manet zone zrp 04. txt, July, 2002.
