（计算机应用技术专业论文）基于aodv的qos路由优化算法研究.pdf

重庆邮电大学硕士论文 摘要 2 0 世纪来，i n t e r n e t 和通信技术的蓬勃发展，人们对通信的要求也越来 越高，希望在网上能够做更多的事情，希望摆脱传统网络线路的束缚。真 正做到“无处不在、随心所欲、随时随地”的连上网络。所以移动计算、 无线通信、动态网络具有广阔的前景。a dh o e 网络正是在这种背景下提出 来的。它的目标是让人们摆脱传统通信设施的束缚，能够在任何时间、任 何地点实现通信的需要。a d h o c 网络技术已经被列为下代网络的关键技 术。a dh o c 网络是一种动态、分布式、多跳的移动无线网络。因此无论足 设计还是应用，都还有许多问题等待解决。 q o s 已经成为a dh o e 网络研究的一个热点问题。原因在于a dh o c 网络不同与已有的网络，所以为a dh o e 的业务提供q o s 保证面临着许多 新的挑战。本文首先分析了a dh o e 网络路由算法研究现状，并对几个典 型的路由算法的优缺点进行了分析和比较。接着，本文详细分析了a d h o c 网络的动态性及其对路由的影响，尤其是对q o s 路由的影响。在此基础上， 提出了一种基于路径稳定性的路由选择机制l l p ：该机制通过统计一段时 间at 内局部区域节点拓扑变化的程度，来判断局部拓扑的稳定性，然后 根据比较不同路径沿途各节点局部拓扑稳定度量值的累乘值，选择相对稳 定的路径转发数据。然后利用此机制对a o d v 路由算法进行改进，并对算 法进行了详细的描述。利用此机制选择的路由不仅稳定性较好，而且路由 跳数小。改进后的算法，称为l l p a o d v ，具有较好的网络规模扩展性和 负载适应性。本文给出了这种方法的具体实现。并且通过n s 2 仿真模拟， 给出了l l p a o d v 和a o d v 路由算法在路径中断次数、归一化路由开销、 分组投递率、端到端延迟、端到端时延抖动五个方面的比较。最后 l l p a o d v 和e b l l d 进行了比较。仿真结果证明了改进方案的有效性。 关键诃： a dh o c 网络，l l p - a o d v 路由算法，路径稳定性，q o s 路由 重庆邮电大学硕+ 论文摘要 a b s t r a c t s i n c e2 0 “c e n t u r y , i n t e r n e ta n dc o m m u n i c a t i o nt e c h n o l o g yh a v eb e e n d e v e l o p m e n tg r e a t l y s op e o p l en e e dm o r ef r o mc o m m u n i c a t i o nn o w t h e y w a n tt od om o r et h i n g sa n dg e ta w a yf r o mt h en e t w o r kl i n e a n dt h ed r e a m u b i q u i t o u sc o m m u n i c a t i n gw i l lb er e a l i t ys om o b i l ec o m p u t i n g ，w i r e l e s s c o m m u n i c a t i o na n dd y n a m i cn e t w o r kp r e s e n tg r e a ta p p l i c a t i o na r e a a dh o c n e t w o r kw a sp r e s e n t e du n d e rt h i sb a c k g r o u n d i ti sas o l u t i o no fm a k i n g p e o p l ec o m m u n i c a t ea ta n y t i m ea n da n y w h e r e a dh o cn e t w o r kt e c h n o l o g y h a sb e e nr e g a r d e da so n eo ft h ek e yt e c h n o l o g i e so ft h en g n a dh o c n e t w o r ki sak i n do fd y n a m i c ，d i s t r i b u t e d ，a n dm u l t i - h o pm o b i l ew i r e l e s s n e t w o r k s ot h e r ea r em a n yp r o b l e m se x i s t i n gi nn e t w o r kd e s i g n i n ga n d a p p l i c a t i o nt ob es o l v e d q o si st h eh o tr e s e a r c hf i e l do fa dh o en e t w o r k t h e r ea r em a n yn e w c h a l l e n g e st op r o v i d eq o ss e r v i c e si na dh o en e t w o r k ，b e c a u s eo ft h e d i f f e r e n c eb e t w e e na dh o en e t w o r ka n do t h e rw i r e l e s sn e t w o r k s f i r s t l y , t h i s p a p e ra n a l y s e st h er e s e a r c hs t a t e o fa dh o en e t w o r kr o u t i n ga l g o r i t h m p r e s e n t e da n dc o m p a r e ss e v e r a lt y p i c a lr o u t i n ga l g o r i t h m s s e c o n d l y , o nt h e b a s i so fa n a l y z i n gt h ed y n a m i co fa dh o en e t w o r k ，t h el o n g e s tl i f e t i m ep a t h ( l l p ) i sp r o p o s e d ，t h a ti sap a t h s t a b i l i t yb a s e dr o u t i n gs e l e c t i n gs c h e m e t h i ss c h e m eu s e st h e e n t r o p yt h a t i s p e r i o d i c a l l yc o m p u t e d a st h e m e a s u r e m e n to ft h en e t w o r ko rl o c a la r e as t a b i l i t y t h i r d l y , t h es c h e m ei s b e e nr e a l i z e di na o d v r o u t i n ga l g o r i t h m t h ei m p r o v e m e n ta l g o r i t h m ，n a m e d l l p a o d v ，p e r f o r m se x c e l l e n ti nl a r g es c a l ea n dh e a v yl o a dn e t w o r k t h i s p a p e rs h o w st h es i m u l a t i o nc o d ef o rn s 2s i m u l a t i o np l a t f o r m ，t h es i m u l a t i o n s c h e m ew i l lc o m p a r ew i t ht h es t a n d a r da o d va n dl l p a o d vi nf i v ei t e m s ( p a t hb r e a kt i m e s ，n o r m a lr o u t i n go v e r h e a d ，p a c k e td e l i v e r yr a t i o ，e n dt oe n d d e l a y , j i t t e ro fe n dt o e n dd e l a y ) a tl a s t ，t h es i m u l a t i o nh a sc o m p a r e d l l p a o d va n de b l l di nn u m b e ro fr o u t ec o n s t r u c t i o n s t h es i m u l a t i o n r e s u l ts h o w st h ev a l i d i t yo ft h ei m p r o v e ds c h e m e k e yw o r d s ：a dh o cn e t w o r k ，l l p - a o d vr o u t i n ga l g o r i t h m ，p a t h s t a b i l i t y , q o sr o u t i n g l i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得重迭塑电盔堂或其他教 育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何 贡献均己在论文中作了明确的说明并表示谢意。 学位论文作者魏同书禾签字日期卅年z 月铲同 学位论文版权使用授权书 本学位论文作者完全了解重庆邮电塞堂有关保留、使用学位论文的规 定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查 阅和借阅。本人授权重废竖立盔堂可以将学位论文的全部或部分内容编入 有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论 文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名 习壮家 导师签名 签字日期：z ，d 1 年二月铲日签字日期：力兜 阀净 ) 钐月乒r 重庆邮电大学硕士论文 箢一章绪论 第一章绪论 1 1a dh o c 网络概述2 a dh o e 网络。又称移动自组织网络，英文名称有：m o b i l ea dh o c n e t w o r k 、w i r e l e s sa dh o en e t w o r k 、 s e l f - o r g a n i z i n gn e t w o r k 、 i n f r a s t r u c t u r e l e s sn e t w o r k 、m u l t i h o pn e t w o r k 和p a c k e tr a d i on e t w o r k 。 a dh o e 网络的前身是分组无线网( p a c k e tr a d i on e t w o r k ) ，早在19 7 2 年， 美国的国防部高级研究训划署( d a r p a ) 就启动了分组无线网项目p r n e t 研究在战场环境下利用分组无线网进行数据通信。在此之后，d a r p a 于1 9 8 3 年启动了高残存性自适应网络项目s u r a n ( s u r v i v a b l ea d a p t i v e n e t w o r k ) 研究如何将p r n e t 的研究成果加以扩展，以支持更大规模的 网络。1 9 9 4 年，d a r p a 又启动了全球移动信息系统g l o m o ( g l o b l e m o b i l e i n f o r m a t i o ns y s t e m s ) 项目，旨在对能够满足军事应用需要的、高抗毁性的 移动信息系统进行全面深入的研究。成立于1 9 9 1 年的1 e e e8 0 2 “标准委 员会采用了“a dh o e 网络”一词来描述这种特殊的自组织对等式多跳移动 通信网络，a d h o c 网络就此诞生。 a dh o e 网络是由一组带有无线收发信装置的移动终端组成的多跳临时 性自治系统，移动终端具有路由功能，可以通过无线连接构成任意的网络 拓扑，这种网络可以独立工作，也可以与因特网或蜂窝无线网络连接。a d h o c 网络中，每介移动终端兼备路由器和主机两种功能：作为主机，终端 需要运行面向用户的应用程序；作为路由器，终端需要运行相应的路由 协议，根据路由策略和路由表参与分组转发和路南的维护工作。在a dh o e 网络中，节点间的路由通常由多个网段( 跳) 组成，由于节点的无线传输 范围有限，两个无法直接通信的终端节点往往要通过多个中间节点的转发 来实现通信。如图l 所示为典型的a d h o e 网络拓扑。 ，- 屹。彳矿弋 d 重庆邮电大学硕士论文 第一章绪论 起源于军事通信的a dh o c 网络技术近年来的发展，使其可望成为下一 代网络的核心。a dh o c 网络无需预先架设通信基础设施，可以灵活纽网。 传统的蜂窝移动通信网络，必须预先架设通信基础设施，否则终端不能通 信。而a dh o c 技术的出现，就可以解决这个难题。无法直接连接蜂窝 6 9 络的终端，利用a dh o c 技术通过多个终端的多跳中继转发，可以实现同 蜂窝网络的互联。因此a dh o e 网络既可以作为蜂窝网络或者其他网络的 扩展，也可以独立组网，且不需要专门的基站、路由器等传统网络中的互 联设备。网络拓扑自由，不受通信基础设施的约束。a d h o c 网络的可快速 组网、系统抗毁性强、自组织、不依赖预设的基础设旌、组网灵活等优点。 正吸引着越来越多的研究者的关注。组网理论、路由算法、接入控制、安 全管理等方面足众多研究的热点。 1 2a dh o c 网络特征 同其他网络相比，a dh o c 网络具有如下特点： 动态拓扑结构 在a d h o c 网络中，由于用户终端的随机移动、节点的随机开关机、无 线发信装置发送功率的变化、无线信道问相互干扰以及地形等综合因素的 影响，移动终端问通过无线信道形成的网络拓扑结构随时可能发生变化， 而且变化的方式和速度都是不可预测的，具体的体现就是拓扑结构中代表 移动终端的顶端的增加或消失、代表无线信道的有向边的增加和消失、网 络拓扑结构的分割和合并等。 对等性和分布式 a dh o e 网络没有严格的控制中心，所有的节点地位平等，是一个对等 网络。节点之间可以直接互通，不必借助类似蜂窝网中的基站等设备。自 组网内的成员节点之间通信，无需中心控制节点，通过分布式控制算法来 协调相互之间的行为。因此，节点之间可以在任何时刻、任何地点快速展 开并自动组网。 a dh o c 网络中的用户终端都兼备独立路由和主机功能，不需要网络中 心控制点，用户终端之间的地位是平等的，网络路由协议通常采用分布式 控制方式，因而比采用集中式控制的网络具有更强的鲁棒性和抗毁性。在 常规通信网络中，存在基站、网控中心或路由器这样一类的集中控制设各， 用户终端与他们所处的地位式不对等的。 多跳组网方式 重庆邮电大学硕士论文 第一章绪论 当a dh o c 网络中的节点要与其覆盖范围之外的节点进行通信时，需要 通过中间节点的多跳转发，所姒a dh o c 网络是一个多跳的移动计算机嘲 络，多跳是研究a dh o e 网络路由协议的前提基础。与固定网络的多跳路 由不同，a d h o c 网络中的多跳路由由普通的网络节点完成，而不是由专用 的路由设备( 如路由器) 完成。 不通过某些技术手段来扩大节点的通信范围，从而将多跳网络简化为 一跳网络的主要原因有以下几个。其，扩大通信覆盖范围，主要是通过 加大发射功率、加高天线的高度等手段。这种方式对于许多移动终端而言， 在功耗、电磁屏蔽、便携性、灵活性和设计成本等方面都是巨大的挑战。 在多跳的情况下，由于收端和发端的节点都可以使用比两者直接通信小得 多的功率进行通信，因此大大节约电池能量的消耗。即使从全局的角度看。 其对电池能量的利还是比直接通信情况下的效率高。其次，当所有的终 端都同处于一个通信覆盖域中，共享的无线信道将变得更加拥挤，信号碰 撞的概率将加大，信道的有效利用率将急剧下降。在a dh o e 网络环境中。 可以通过中间节点参与分组转发，从而有效地降低对无线传输设备的设计 难度和成本，同时也扩大了a d h o e 网络地覆盖范围。 在a dh o e 网络中。节点覆盖范围有限，一方面，较短地传输距离使路 由的更新跟不上移动所带来地拓扑结构地变化，但一方面，过多地中继又 可能使路由变得很脆弱。 有限的无线传输带宽 由于a dh o e 网络采用无线传输技术作为底层通信手段，而无线信道本 身的物理特性决定了它所能提供地网络带宽比有线信道要低得多，再加上 竞争共享无线信道产生的碰撞、信号衰减、噪音干扰及信道间干扰等多种 因素，因此移动终端可得到的实际带宽远远小于理论的最大带宽值。 移动终端的自组织性 a dh o e 网络不依赖于基站等基础设施的支持，可以在任何时刻、任何 地点构成网络，以实现移动节点的信息交互。具体而言，在a dh o e 网络 中。网络路由的计算、网络临时结构的形成不需要外部参与，都可以依据 当时的情况自我组织，并随环境变化自适应地自我调整。 移动终端的局限性 通常的移动计算机网络中的移动终端主要承担主机的角色，有关信息 交换的智能性主要体现在移动路由器。与台式机相比，a dh o e 网络中的移 动终端 0 ，则两个节点o ，) 之间的距离经过t 后增加了； ( 2 ) 如果a p 0 ，则两个节点( f ，j ) 之间的距离经过a t 后减小了； 重庆邮电大学顶+ 论文 第三章基于路径稳定性的路由选择机制设计 ( 3 ) 如果廿= 0 ，则两个节点( f ，j ) 之间的距离经过。后不变； ( 4 ) 两个节点之酬的距离增加，表明链路中断的可能性越大；两个节 点之间的距离减小，表明链路中断的可能性越小。 我们假设节点的相对运动速度i i 矿( f ，) i i 墨 l ，这也是符合实际情 况的。根据这个前提，可知： 置 p o s ( i ，j ，) _ i i p o s f f ，j ， 足 那么a ，便具有以下属性： ( 1 ) o ， l ； ( 2 ) q ，越大，链路( f ，力的稳定性越差，q ，越小，链路( f ，) 的稳定性 越好。 基丁以上定义，我们引入了熵： 一最( f ，) 1 0 9 e ( f ，) q ) = 气面矿 3 5 ) 其中 见= 导 厶 “ ( 3 6 ) h a t ，a ) 表征在t 内节点i 的局部拓扑变化程度。如果是计算网络局 部区域的稳定性，f ( i ) 就是节点i 的邻居节点集；如果是计算一条路径的 局部稳定性，( i ) 就是节点i 的上下游邻居节点。a f o ) ) 是集合f ( t ) 的势。 根据熵的定义可知： ( 1 ) q 以) 值越大，节点i 的局部拓扑越稳定；而b ( f ，) 值越小，节 点i 的局部拓扑变化激烈。”3 1 ( 2 ) o 珥【f ) 1 。 现在我们给出了评价一条路径上某个节点i 的局部拓扑稳定性的尺 度，而一条路径是由多个节点构成的。因此仅知道各个节点的局部区域稳 定性，还无法进行路径问的稳定性的比较。所以我们下面将构造评价一条 路径的稳定性的尺度。 源节点s 到目的节点d 可能存在多条路径，目的节点d 选择相对稳 定的路径进行数据转发。确定相对稳定路径时考虑以下因素：1 ) 尽可能选 择局部拓扑变化小的节点参与数据转发，避免局部拓扑变化激烈的节点参 与数据转发，因为路径中局部拓扑变化大的节点越多，则路径中断的概率 重庆邮电人学硕士论文 第三章基于路径稳定性的路由选择机剖设计 越大；2 ) 尽可能选择短路径，一方面a dh o c 网络拓扑动态变化，长路径 中断的概率比短路径大，另一方面a dh o e 网络采用多跳共享窄带无线信 道，长路径的端剑端通信性能( 如分组投递率、时延等) 通常比短路径差。 【2 5 】 基于以上考虑，路径稳定性度量计算公式如下： 五= ilq o ，) 袖 ( 3 , 7 ) 是路径沿途各节点局部稳定性度量的乘积。根据前面的分析， 值越大， 路径稳定性就越好；否则，路径稳定性就越差。 由于e ( f ，) ( 0 ，1 ) ，采用式( 3 7 ) 的累乘处理方法，一方面可以选择 局部拓扑变化小的节点进行数据转发，避免局部拓扑变化激烈的节点参与 数据转发；另一方面选择跳数少的路径进行数据转发。而如果采用累加的 方式，则无法根据 的值判定路径的稳定性是好还是坏，而且目的节点趋 向于选择长路径。两种处理方法的差异可以由图3 2 示例说明。图中源节 点和目的节点之间存在两条路径。表3 1 给出两种处理方法的结果，如果 按累加的方法，选择的路径将是( i ，1 ，2 ，3 ，4 ，j ) ；如果按累乘的方法， 选择的路径将是( i ，5 ，6 ，7 ，j ) 。 图3 2 两种计算方法选择的路径对比 表3 1 路径稳定性处理方法比较 l p a t h累乘方法 累加方法 l ( i ，1 ，2 ，3 ，4 ，j ) 0 1 0 0 83 2 i ( i ，5 ，6 ，7 ，j ) 0 1 6 82 6 3 2 2 邻居节点位置信息的检测 节点i 通过周期性广播包含节点位置信息的广播消息包获得邻居节点的 位置信息，从中提取出节点i 同各个邻居节点之间链路的特征变量 2 0 重庆邮电大学硕士论文 第三章基于路径稳定性的路由选择机制设计 q ，u e f ( f ) ) 。i e e e 8 0 2 1 1m a c 协议的一跳单播分组投递率为9 9 8 ，一跳广 播分组投递率仅为9 2 6 。”因此，设计邻居节点位置信息检测机制时， 应考虑m a c 层不可靠广播分组传输的影响，具体机制包括： ( 1 ) 邻居节点位置信息获取：每隔h e l l 0 一i n t e r v a l 周期，节点广播一个 跳数为1 的广播消息包。节点通过收听邻居节点发送的广播分组检测邻居 节点位置信息，同时维护邻居节点集。如果在过去的a l l o w h e l l o h e l l 0 一i n t e r v a l 周期内，节点没有收到某个邻居的任何广播分组( 包括 h e l l o n 息) ，节点认为与该邻居节点的连接已经中断，把该节点从邻居集 中删除。a l l o w h e l l o 是t 内离散时刻t 。的个数。 ( 2 ) 链路特征变量计算： 设s 一：u p o * u , j , , ) _ l l - i l l p 。s u , j , t o ) 一l l + r , ，屯：+ h e i i 0 _ i n t e r v a l ，那么 z t 置一岛= 墨一 + k 竺堕立尘崆些竺堡出。 如此重复求和，直到 z 一 一f o = a l l o w h e l l o h e l l o i n t e r v a l 时，n _ a l l o w e l l o ，通过q f = = 电生求得链 v 路“，7 ) 在a t 内的特征变量值。依此类推，便可以获得在a t 内与节点i 覆盖 范围内邻居节点的特征变量值。 ( 3 ) 然后按式( 3 5 ) 计算e ( f ，) ，获得节点i 局部拓扑稳定性度量值。 并更新邻居节点列表中节点局部拓扑稳定性度量值。凰( f ，) 表征节点i 局 部拓扑的变化程度。 m a c 层广播分组的不可靠传输和节点移动是h e l l o 消息丢失的两个主要 原因。上述原因直接影响a l l o w h e l l o 参数设置，进而影响链路特征变量 和熵值的计算。如果a l l o w h e l l o 参数设置得太小，将无法减小m a c 层广播 消息不可靠传输的影响；如果a l l o w h o l l o 参数设置得太大，则又无法及时 反映因节点移动导致节点局部拓扑的变化。本文采用仿真方法，通过比对 不同a l l o w h e l l o 参数值对应的路由性能来确定最佳a l l o w h e l l o 参数值。 当a l l o w h e l l o = 3 时，路由性能最优。 3 2 3 路由发现 当源节点需要同某个目的节点进行通信，而又没有相应的路由时，启 动路由发现过程。源节点广播r r e q ( r o u t er e q u e s t ) 路由请求分组，r r e q 重庆邮电大学硕士论文第三章基1 路径稳定性的路由选择机制设计 分组包含目的节点序列号、源节点和目的节点地址、跳数、路径稳定性度 量 和最小链路稳定性度量。只有目的节点可以向源节点回复r r e p ( r o u t e r e p l y l 分组。 中间节点收到第1 个r r e q 分组后，根据收到的更新最小链路稳定性 度量日；( f ，) 和路径稳定性度量 ，然后建立到达源节点的反向路由。反向 路由的目的节点是源节点，下一跳节点是将r r e q 分组发送给本节点的邻 居节点。然后向邻居节点继续广播r r e q 分组，如此反复。节点在转发 r r e q 分组的过程中，可能会收到来自不同邻居节点的统一r r e q 的多个 副本。对后续收到的重复r r e q 分组，只有在序列号相同并且 值更大时， 中间节点才更新路由表并转发r r e q 分组。 目的节点收到第1 个r r e q 分组后，目的节点建立到源节点的反向路 由，并发送一个r r e p 单播分组给r r e q 分组的发送者。目的节点可能会 收到来自同一源节点的多个r r e q 分组。如果后续收到的r r e q 分组的序 列号更大，或者序列号相同但 值更大时，目的节点修改反向路由表项， 并再次发送r r e p 分组。r r e p 分组沿着刚刚建立的反向路由向源节点传 送，收到r r e p 分组的节点将建立到目的节点的转发路由。转发路由的目 的节点是r r e p 分组的生成节点，下一跳是将r r e p 分组发送给本节点的 邻居节点。 3 3 本章小结 本章在前面两章工作的基础上，改进了e b l l d 算法中路径稳定性评 价尺度一熵，避免了实现复杂，路由跳数偏大的问题。进一步提出了基于 路径稳定性的路由选择机制一l l p 。然后详细描述了l l p 机制的原理。 重庆邮电大学硕士论文 第四章路由优化算法的设计及实现 第四章q o s 路由优化算法的设计及实现 a o d v 路由协议属于典型的按需路由算法，目的是选择路由跳数 最小的路径进行数据转发。a o d v 的路由算法具有实现简单、直接和 能够避免路由环路的优点。但是它的缺点也像其他按路由跳数选择路 径的算法一样，选择的路径稳定性不好，存在频繁路由修复或重建的 问题。如果数据转发路径在数据转发期问中断，那么节点必须频繁的 进行路由重建或者路由修复，消耗了有限的网络资源。这个也是造成 a o d v 协议承载q o s 业务能力差，网络规模无法扩展的关键。我们用 l l p 机制对a o d v 的路由算法进行扩展，旨在最大限度地减少节点移 动造成的路径中断次数，提高网络性能提高网络承载q o s 业务的能 力。扩展后的路由算法称为l l p a o d v 。 4 1 a o d v 路由协议的基本原理 a o d v 是在1 9 9 7 年由c h a r l e s e p e r k i n s 等提出的。随着协议的不 断发展和完善，现有a o d v 协议的i n t e r n e td r a f t 已经有了 d r a f t i e t f - m a n e t a o d v 一1 2 t x t ，由n o k i a 研究中心的c h a r l e se p e r k i n s 和c a l i f o r n i a 大学s a n t ab a r b a r a 的e l i z a b e t hm b l e d i n gr o y e r 以及 c i n e i n n a t i 大学的s a m i r r d a s 等共同开发，被i e t f m a n n e t 工作组 与2 0 0 3 年6 月1 8 日正式公行为a dh o e 网络络路由的r f c 标准 ”】。 a o d v 实质上就是d s r 和d s d v 的综合，它借用了d s r 中路由 发现和路由维护的基础程序，及d s d v 的逐跳( h o p b y h o p ) 路由、 顺序编号和路由维护阶段的周期更新机制，以d s d v 为基础，结合d s r 中的按需路由思想并加以改进。 a o d v 的操作是无环路的。在避免了通常b e l l m a n f o r d 算法的无 穷记数( e o u n t t o - i n f i n i t e ) 问题的同时，还提供了很快的收敛速度。 a o d v 有别于其他协议的晟显著特点是路由表中每个项都使用了目的 序列号。目的序列号是目的节点创建，并在发给发起节点的路由信息 中使用的。使用目的序列号可以避免环路的发生，并且很容易编程实 现。 a o d v 使用3 种消息作为控制信息：r o u t e r e q u e s t ( r r e q ) 、r o u t e 重庆邮电大学硕士论文第四章路由优化算法的设计及实现 r e p l y ( r r e p ) 和r o u t ee r r o r ( r e r r ) 。这些消息都在u d p 上使用 6 5 4 端口号。 当源节点需要和目的节点通信时，如果在路由表中已经存在了对 应的路由时，a o d v 就不会进行任何操作。当源节点需要和新的目的 通信时，它就会发起路由发现过程，通过广播r r e q 信息来查找相应 路由。当这个r r e q 到达目的节点本身，或者是一个拥有足够新的到 目的节点路由的中间节点时，路由就可以确定了。所谓“足够新”就 是通过目的序列号来判断的。目的节点或中间节点通过原路返回一个 r r e p 信息来向源节点确定路由的可用性。 a o d v 使用了分布式的、基于路由表的路由方式，所以建立路由 表项以后，在路由中的每个节点都要执行路由维持、管理路由表的任 务，在路由表叶1 都需要保持一个相应目的地址的路由表现，实现逐跳 转发。这就与d s r 所采用的源路由方式有很大的不同。后者在路由时， 只有源节点知道到目的节点的完整路由。而中间节点都不知道有关的 路由信息。 表4 1a o d v 协议路由表内容 目的i p 地址( d e s t i n a t i o ni pa d d r e s s ) 口的序列号( d e s t i n a t i o ns e q u e n c e n o ) 接口( i n t e r f a c e ) 跳数计数( h o pc o u n t ) 上一次地跳数( l a s th o pc o u n t ) 下一跳( n e x th o p ) 前驱列表( l i s to f p r e c u r s o r s ) 生存时间( l i f e t i m e ) 路由标志( r o u t i n gf l a g s ) 在维护路由表的过程中，当路由不再被使用时，节点就会从路由 表中删除相应的项。同时，节点会监视一个活性路由( a c t i v er o u t e ， 有限跳的，可用于数据转发的路由表项) 中，下一跳节点的状况。当 发现有链路断开的情况时，就发出r e r r 消息通知其他节点。换句话 说，当一条活性路由发生断链时，上游的节点就会使用r e r r 消息通 知更上游的节点。在r e r r 消息中，指明了由于断链而导致无法到达 重庆邮电大学硕士论文 第四章路由优化算法的设计及实现 的目的节点。每个节点都保留了一个“前驱列表”( p t r e c u l s o 1 i s t ) 来 帮助完成错误报告的功能，这个列表中保存了把自己作为到当前不可 达节点的下一跳的相邻节点( 可以通过记录r r e p 很容易地获得) 。 存路由表中针对每一个表项，需要记录如表4 1 所示的内容。 其中，管理序列号是防止路由环路的关键所在。当发生断链时，通过 增加序列号和度量值( 跳数) 来使路由表项无效。 a o d v 的各步操作如下： ( 1 ) a o d v 路由发现 a o d v 路由协议是一种典型的按需驱动路由协议，该算法可被称 为纯粹的需求路由获取系统，那些不在活跃路径上的节点不会维持任 何相关路由信息，也不会参与任何周期路由表的交换。此外，节点没 有必要去发现和维持到另一个节点的路由，除非这两个节点需要进行 通信。移动节点间的局部连接性可以通过几种方法得到，其中包括使 用局部广播h e l l o 消息。这种算法的主要r 的是：在需要时广播路由 发现分组；区别局部连接管理( 邻居检测) 和一般的拓扑维护：向需 要连接信息的邻居移动节点散播拓扑变化信息。 a o d v 使用广播路由发现机制，它依赖中间节点动态建立路由表 项来进行分组的传送。为了维持节点间的最新路由信息，a o d v 借鉴 了d s d v 中的目的序列号的思想。但与d s d v 不同的是，每一个节点 都维持了独立的序列号计数器，利用这种机制就能有效的防止路由环 的形成。 当源节点想与另外一个节点通信而它的路由表中又没有相应的 路由信息时，它就会发起路由发现过程。每个节点维持两个独立的计 数器：节点序列号计数器和广播标识。源节点通过向自己的邻居广播 r r e q ( r o u t er e q u e s t s ) 分组来发起一次路由发现过程。r r e q 消息 的格式如图4 1 所示。 0l2 3 0123456 78 90l2345678 90123 4 567890 1 类型jr g du 保留跳数 r r e qi d 目的i p 地址 目的序列号 源i p 地址 源序列号 图4 1r r e q 分组格式 重庆邮电大学硕士论文 第四章路由优化算法的设计及实现 类型 1 j ( j o i nf l a g ) ：是为组播预留的加入标识 r ( r e p a i rf l a g ) ：是为组播预留的修复标识 g ( g r a t u i t o u sr r e pf l a g ) ：用于指示一个r r e p ( r o u t er e p l y ) 是 否向目的i p 地址字段指明的节点进行单播 d ( d e s t i n a t i o no n l yf l a g ) ：只有目的节点才对该r r e q 做回复 u ( u n k n o w ns e q u e n c en u m b e r ) ：i n d i c a t e st h ed e s t i n a t i o ns e q u e n c e n u m b e ri su n k n o w n 对唯一地确定了一个r r e q 分组，当源节点发 起一个新的r r e q 时，广播标识计数器就增加1 。收到r r e q 的邻居 节点或者向源节点发送路由响应r r e p ，或者在增加了这个r r e q 分 组跳数后，重新向自己的邻居广播这个r r e q 分组。 一个节点可能会从不同的邻居收到同一个广播的多个副本，如果当 中问节点收到一个r r e q 分组它会对收到的分组进行判断：如果节 点已经收到了相同广播标识和源节点地址的r r e q 时，它就会丢掉这 个分组；如果节点以前并没有收到这样的r r e q 分组，它就会保存一 些信息用于建立反向路径，然后再把这个r r e q 分组广播出去。 a o d v 反向路由的建立 在r r e q 分组中包含了两个序列号：源节点序列号和源节点所知 道的最新的目的序列号。源节点序列号用于维持到源的反向路由的最 新特性，目的序列号表明了到目的地的最新路由。 当r r e q 分组从一个源节点转发到不同的目的地时，沿途所经过 地节点都要自动建立到源节点地反向路由。节点通过记录收到的第一 个r r e q 分组的邻居地址来建立反向路由，这些反向路由项将会维持 一定时间，该段时间足够r r e q 分组在网内转发以及产生的r r e p 分 组返回源节点。当r r e q 分组到达了目的节点，目的节点就会产生 r r e p 分组，并利用建立的反向路由来转发r r e p 。 r r e p 消息的格式如图4 2 ； o123 01 234567 890l 234567 89012 34667 890l 重庆邮电大学硕士论文 第四章路由优化算法的设计及实现 图42r r e p 分组格式 类型：2 r ( r e p a i rf l a g ) ：用于组播 a ( a c k n o w l e d g m e n tr e q u i r e d ) ：用于确认。 a o d v 正向路由的建立 r r e q 分组最终将到达一个节点，该节点可能就是目的节点，或 者这个节点有到达目的节点路由，这个节点首先检查收到的r r e q 分 组是否是从双向链路上来的。如果这个中间节点有到达目的的路由项， 它就会通过比较路由项里的目的序列号和r r e q 分组里的目的序列号 的大小来判断自己已有的路由是否是比较新的。如果r r e q 分组里目 的序列号比路由项中的序列号大，则这个中间节点不能使用已有的路 由来响应这个r r e q 分组，只能是继续广播这个r r e q 分组。中间节 点只有在路由项中的目的序列号不小于r r e q 中的目的序列号时，才 能直接对收到的r r e q 分组做出响应。如果节点有到目的地地最新路 由而且这个r r e q 还没有被处理过，这个节点将会沿着建立地反向路 由返回r r e p 分组。 在r r e p 转发回源节点地过程中，沿着这条路径上地每一个节点 都将建立到目的节点地正向路由，也就是记录下r r e p 是从哪一个邻 居节点来地地址，然后更新有关源和目的路由地定时器信息以及记录 下r r e p 中目的节点地最新序列号。对应那些建立了反向路由，但 r r e p 分组并没有经过的节点，它们中建立的反向路由将会在一定时 间( a c t l v er o u t et i m e o u t ) 后自动变为无效。 收到r r e p 分组的节点将会对到某一个源节点的第一个r r e p 分组 进行分组转发，对于其后收到的同一个源的r r e p 分组，只有当后到 的r r e p 分组中包含了更高的目的序列号或虽然有相同的目的序列 号，但所经过的跳数较少时，节点才会重新更新路由信息，以及把这 个r r e p 分组转发出去。这种方法有效的抑制了向源节点转发的r r e p 分组数，而且确保了最新及最快的路由信息。源节点将在收到第一个 r r e p 分组后，就开始向目的节点发送数据分组。如果以后源节点了 解到有更新的路由，它就会更新自己的路由信息。 ( 2 ) a o d v 路由表的管理 节点的路由表中除了存储源和目的节点的序列号以外，还存储了其 他有用的信息，这些信息成为有关路由项的软状态。与反向路由相关 重庆邮电大学硕+ 论文第四章路由优化算法的设计及实现 的是路由请求定时器，这些定时器的日的是清除一定时间内没有使用 的反向的路由项。定时器的设置依赖于自组网的 | ! l ! 模大小，与路由项 相联系的另外一个重要的参数是路由缓存时间，即在超过这个时间之 后，对应的路由项就变为无效。 此外，在每一个路由表项中，还要记录下本节点用于转发分组的活 跃邻居。如果节点在最近一次活跃期间( a c t i v et i m e o u t ) 发起或 转发了到某个目的节点的分组，那么就可以称这个节点为活跃节点。 这样当到达某一个目的节点的链路有问题时，所有与这条链路有关 的活跃节点都可以被通知到。一个路由表项如果还有活跃邻居在使用， 就可以认为是有效的。通过各个活跃路由项所建立的源节点到目的节 点的路径，也就是一条活跃路径。路由表项中的目的节点序列号，正 如在d s d v 路由协议中所使用的那样，可以在无序分组的传送和节点 高度移动的极端条件下避免路由环路的产生。 移动节点为每一个相关目的节点维护了一个路由表。每一个路由表 项包含以下一些信息：目的地址、下一跳地址、跳数、目的序列号及 路由项的生存时间。 路由表项在每一次被用来传送一个分组时，它的生存时间都要重新 开始计算，也就是用当前时间加上a c t i v er o u t et i m e o u t 。 如果一个移动节点被提供了到达某一个目的节点的新路由，那么它 就会把这个新路由的目的序列号与自己路由表中已有的日的序列号做 比较，并将目的序列号大的作为到达目的节点的路由项。如果目的序 列号相同，则采用到目节点所经过的节点数( 跳数) 最少的那个路由。 f 3 1a o d v 路由维护 如果节点的移动不是沿着活跃路径进行的，那么就不会影响以经建 立的路由。如果一个源节点在活跃路径上移动，它就要向e t 的节点重 新发起一次路由发现过程。如果移动的节点是中间节点或目的节点， 那么一个特殊的r r e p ( r o u t e r e p l i e s ，路由应答) 分组将转发到那些 受移动影响的源节点。周期性发送h e l l o 分组可以用来确保链路的对 称性，并检测不能用的链路。如果不采用h e l l o 分组，也可以采用链 路层通告机制来报告链路的无效性，这样可以减少延迟。此外，节点 在尝试向下一跳转发分组失败后，也能检测