（计算机应用技术专业论文）基于混沌算法的安全aodv路由协议研究.pdf

中文摘要 无线自组网( a dh o c ) 被广泛地应用于军事、救灾等各种需要临时建立通讯 网络的场合。自组网网络结构的建立是为了提高无线网络的灵活性、移动性，使 之易于管理。安全问题是自组网络研究中的一个很重要的课题，自组网的安全目 标包括：可用性、机密性、完整性、安全认证和抗抵赖性。由于自组网应用场合 及自身的特殊性使得实现安全性能成为在研究自组网时一个重要而又具有挑战 性的任务。 a o d v 是一种按需驱动路由协议，是自组网中重要的协议，当源节点要与目 的节点进行通信时，才发起路由寻找过程，对于自组网这样节点能源，计算与存 储能力都有限的应用场合而言，降低了节点能源的损耗。a o d v 是无线自组网的 研究热点，有着广泛地应用前景，组合以上两个方面，本课题将研究的重心放在 无线自组网的a o d v 路由协议的安全性能上。 本文先分析了两种流密码算法：r c 4 算法与混沌算法的时间性能，在l i n u x 下编写c + + 程序进行了比较。密码算法在本文中不仅被用作实现加密解密，而且 被用于实现身份的认证。 其次，在简单描述了现有的不同的安全路由协议的基础上，对a o d v 路由协 议在安全性能上进行扩充与修改，提出了改进方案：基于混沌密码算法的安全 a o d v 路由协议。协议把数据分成固定不变域以及可变域分别进行分析，对于可 变域采用哈希链的方式，不变域的路由信息，提出了实现身份认证，信息完整性 等方面问题的方法，并且列出了改进的协议具体的流程，进行安全性能的分析。 最后将改进的方案在n s 仿真软件下进行仿真，修改原a o d v 路由协议中的文 件，对仿真软件进行重新编绎；在新的环境下对端到端延迟时间、节点数、移动 速度、包接收率这几个与时间性能联系紧密的参数进行测试，将结果进行汇总， 再绘图分析，迸行总结：适用于时间以及安全性能有较高要求的应用场合。 关键字：无线自组网，a o d v ，混沌，安全，n s a b s t r a c t a dh o cn e t w o r k si sw i d e l ya p p f i e dt os i t u a t i o n sn e e d e dt os e tu pt e m p o r a r y c o m m u n i c a t i o nn e t w o r kl i k em i l i t a r ya f f a i r s ，d i s a s t e rr e s c u e ，e t c a dh o cn e t w o r k si s u s u a l l yu s e dt oe n h a n c et h es c a l a b i l i t y , m o b i l i t yo ft h ew i r e l e s sn e t w o r ka n dm a k ei t t ob em a n a g e de a s i l y s e c u r i t yi s s u ei saq u i t ec r u c i a lt a s ki nt h es t u d yo ft h ea dh o c n e t w o r k s n c s e c u r i t yt a r g e t s o ft h ea dh o cn e t w o r k si n c l u d e a v a i l a b i f i t y , c o n f i d e n t i a l i t y , i n t e g r a l i t y , a u t h e n t i c a t i o na n dn o n r e p u d i a t i o n d u et ot h ep a r t i c u l a r i t y o f t h e a dh o cn e t w o r k s ，s e c u r i t yb e p o m e st h ec h a l l e n g ei nt h e a dh o cn e t w o r k s a o d vi sa no nd e m a n dd r i v e nr o u t i n gp r o t o c o la n da ni m p o r t a n ta n dp o p u l a r p r o t o c o li nt h ea dh o en e t w o r k s s o u r c en o d ei n i t i a l i z e st h er o u t ef i n d i n gp r o c e s s w h e ni tn c p m i st oc o m m u n i c a t ew i t hd e s t i n a t i o nn o d e 1 1 圮n o d e si nt h ea dh o c n e t w o r k sh o l dl i m i t e de n e r g y , l i m i t e dp r o c e s s i n ga n ds t o r i n gc a p a c i t y o nd e m a n d d r i v e nr o u t i n gp r o t o c o lr e d u c e se n e r g ys p o i l a g e a o d vi st h eh o t s p o ti nt h e r e s e a r c ho ft h ea dh o en e t w o r k sa n dh a sw i d e l ya p p l i c a t i o nf o r e g r o u n d w h e r e f o r e t h i sp a p e rf o c u s e so nt h es e c u r ea o d v p r o t o c o lf o rt h ea dh o cn e t w o r k s f i r s t l yt h i st h e s i se v a l u a t e st i m ep e r f o r m a n c eo ft h et w os t r e a mc i p h e r , r c 4a n d c h a o s t h ee v a l u t u t i n gp r o g r a m sw r i t t e nb yc + + a r et e s t e di nh n u x i nt h ep a p e r , c i p h e ra l g o r i t h mi sn o to n l yu s e dt oi m p l e m e n te n c r y p t i o na n dd e c r y p t i o nb u ta l s o u s e dt os o u r c ea u t h e n t i c a t i o n s e c o n d l y , a f t e rr e v i e w i n gs o m ed i f f e r e n ts e c u r er o u t i n gp r o t o c o l ，e x p a n s i o na n d m o d i f i c a t i o no nt h es e c u r i t yo ft h ea o d vp r o t o c o la r ep e r f o r m e d , a l la m e l i o r a t e p r o j e c ti sp u tf o r w a r d ：s e c u r i n ga o d vr o u t i n gp r o t o c o lb a s e do nc h a o se n c r y p t i o n t h es c h e m ed i v i d e st h ed a t ai n t on o n v o l i a t i l ef i e l d so rv o l a t i l ef i e l d s a n dh a s hc h a i ni s a p p l i e dt oa u t h e n t i c a t ev o l a t i l ef i e l d s t h e nc h a o t i cc i p h e r sa r ei n t r o d u c e dt op r o v i d e s o u r c ea u t h e n t i c a t i o na n dm e s s a g ei n t e g r i t yf o rt h en o n v o l a t i l ef i e l d s 他p a p e r d e s c r i b e st h ed e t a i l so ft h ei m p r o v e dp r o t o c o la n dt h ep r e s e n t st h es e c u r i t ya n a l y s i s t h i r d l y , f o rs i m u l a t i n gt h ei m p r o v e dp r o t o c o lo nn s 一2 ，o r i g i n a la o d v r o u t e p r o t o c o l i s e x p a n d e d a f t e rr e c o m p i l e s n s 2 t h em e t r i cr e l a t e dt ot h et i m e p e r f o r m a n c es u c ha se n dt oe n dd e l a y , s p e e do ft h em o b i l en o d e s ，p a c k e t sd e l i v e r y f r a c t i o na r et e s t e d f i n a l l yt h ep a p e rp l o t sa n da n a l y s e st h er e s u l t sa n dm a k e so u tt h e c o n c l u s i o n s k e y w o r d s ：a dh o e ，a o d v , c h a o s ，s e c u r i t y , n s i i 独创性声明 本人声明，所里交的论文是我个人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢 的地方外，论文中不包含其他人已经发表或撰写过的研究成果， 也不包含为获得武汉理工大学或其它教育机构的学位或证书而使 用过的材料。与我一同工作的同志对本研究所做的任何贡献均已 在论文中作了明确的说明并表示了谢意。 研究生签名：与姒日期童羔安兰l 关于论文使用授权的说明 本人完全了解武汉理工大学有关保留、使用学位论文约规定， 即：学校有权保留送交论文的复印件，允许论文被查阅和借阅； 学校可以公布论文的全部内容，可以采用影印、缩印或其他复制 手段保存论文 ( 保密的论文在解密后应遵守此规定) 研究生签名：吾蚪导师签名 j 期a 。o 鱼二! 武汉理工大学硕士学位论文 第1 章引言 1 1 研究背景及课题来源 a dh o e 一词来源于拉丁语，意思是特别地，专门地为某一即将发生的特定 目标，事件或局势而不为其他的”意思。一般把a dh o cn e t w o r k s 称为无线自组 网、自组网、多跳无线网、移动分布式多跳无线网络等等，无线自组网强调的是 多跳、自组织、无中心设施。 无线自组网的起源可以追溯到1 9 6 8 年的a l o h a 网络和1 9 7 3 年a r p 磊开始研 究的分组无线网：一种是有结构的分组无线网，即无线局域网：另一种是自组织 的分组无线网，即无线自组网。无线自组网最初是应用于军事领域的，是2 0 世 纪7 0 年代美国国防部高级研究计划局( d a r p a ，d e f e n s ea d v a n c e dr e s e a r c h p r o j e c ta g e n c y ) 资助研究的，在战场环境下采用分组无线网( p r n e t 。p a c k e t r a d i on e t ) 进行数据通信的项目中产生的一种新型的网络构架技术。其后，又由 d a r p a 资助，于1 9 8 3 年和1 9 9 4 年进行了具有抗毁性的自适应网络( s u p a n ， s u r v i v a b l ea d a p t i v en e t w o r k ) 和全球移动信息系统( g l o m o 。g l o b a lm o b i l e i n f o r m a t i o ns y s t e m s ) 项目的研究。无线自组网就是吸取了p r n e t 、s u r a n 以及 g l o m o 等项目的组网思想，从而产生的一种新型的网络构架技术。成立于1 9 9 1 年的i e e e 8 0 2 1 1 标准委员会采用a dh o e 网络一词，此后a dh o c 网络开始成 为计算机网络领域一个公开的研究热点。目前a dh o e 网络尚未达到完全实用阶 段，大部分工作仍处在仿真和实验阶段。负责互联网相关技术规范的研发和制定 的互联网工程任务组( i e t f ，i n t e r n e te n g i n e e r i n gt a s kf o r c e ) 在1 9 9 7 年建立 了一个专门的无线自组网工作组m a n e t ( m o b i l ea dh o cn e t w o r k s ) ，对自组网进 行研究与开发。 无线自组网没有严格的控制中心，所有的节点地位平等，是一个对等式网络。 节点可以随时加入和离开网络，也无需事先建立如基站这样的中心节点，任何节 点的故障不会影响整个网络的运行。自组网是一个多跳的移动计算机网络，当网 络中的节点要与其覆盖范围之外的节点进行通信时，需要通过中间节点进行多跳 转发，多跳是研究自组网路由协议的前提基础。在常规的计算机网络中，主机和 路由器是两个完全不同的物理设备，承担了不同的功能角色：主机主要是运行面 向用户的应用程序，提供用户使用网络的人机接口；路由器作为网络互联设备， 运行相应的路由协议，进行分组转发和路由维护工作。在无线自组网中，移动终 端需要同时承担这两个角色，这将意味着参与无线自组网的移动终端之间存在某 武汉理工大学硕士学位论文 种协同工作的关系，这种关系使得每个终端都承担为其他终端进行分组转发的义 务。 近年来，无线自组网的应用领域从最初的军事领域逐渐被应用于商业和民用 的环境，适用于如下几个方面。1 ： 紧急服务：由于停电、地震、台风等灾害的出现，当网络基础设施受到破坏 的时候，无线自组网的建立可以让救援人员进行通信。 军事无线通信：在战场上，不可能建立类似基站的基础设施，为了保持作战 单位，如车辆，士兵等之间的联系，a dh o c 实现了集中统一指挥，协同作战。 传感器网络：传感器可以工作在危险的环境( 如化学有害物质泄露现场) 或者 环境监控中，通过在传感器上装备位置指示器，将传感器所在现场的信息传送到 危险现场以外，收集和辨别事故信息，避免救援人员进入现场，也可以为野外随 机性研究数据的获得提供方便。 移动会议：在室外临时环境中，工作团体的所有成员可组成一个临时网络来 协同完成一项大的任务，或协同完成某个计算任务。在室内办公环境中，办公人 员携带的包含a dh o c 收发器的p d a ，可以通过无线方式自动从台式机上下载电 子邮件，更新工作日程表等。 家庭网：通过移动联网的方式把办公室的办公环境延伸到家庭，必要时在家 庭办公。或者利用我们随身携带的个人无线a dh o c 设备与装备了a dh o c 收发器 的家庭电器通信，自动完成开锁、开灯、打开娱乐设备、调节空调等操作。 个人域网络：通过a dh o c 网络把个人通信、娱乐、办公等设备联网。 其他商业应用：如未来装备a dh o c 收发设备的机场预约和登机系统可以自 动地与乘客携带的个人无线a dh o c 设备通信，完成目前的换登机牌等手续。 在无线自组网的通信过程中，特别在军事及应急通信下，安全性能显得尤为 突出，无线自组网面临着诸多的安全问题“1 ： ( 1 ) 共享无线环境的潜在不安全使得其比有线网络更容易受到恶意攻击。 ( 2 ) 由于节点的移动性，a dh o c 网络的拓扑结构和成员处于动态变化之中。 ( 3 ) 当节点在战场上移动时，由于缺乏足够的保护，很有可能被占领。 ( 4 ) 分布式操作要求不同的认证和管理方案。 ( 5 ) 由于节点的能源有限，并且c p u 的计算能力较低，无法实现复杂的加密算 法。 ( 6 ) 可能受到特定的安全攻击，如不停发射信号直至消耗完其电源。 ( 7 ) 无线链路本身引入的不可靠问题( 有限传输距离、无线介质的广播特性，如 隐藏终端问题、移动性导致的分组丢失以及数据传输差错) 。 ( 8 ) 无线自组网中可能包括成百上千个节点。安全策略应该具有可扩展性，以 2 武汉理工大学硕士学位论文 适应大规模的网络。 a o d v ( a dh o co nd e m a n dd i s t a n c ev e c t o r ) 是一种按需路由协议嘲，在无线 自组网的环境下，仅在有节点需要发送数据，又没有去往目的节点路由的时候才 按需发起路由请求，而没有象表驱动一样，不论有无通信需求，都要进行路由信 息交换，并且维护去往其他所有节点的路由。网络拓扑结构以及路由信息是按需 建立的，只查找和维护自己需要使用的路由，而不是到所有节点的路由。这对于 自组网在能量，信道的利用上都具有较好的特性，是无线自组网研究的一个热点。 作为无线自组网中的路由协议，安全性也是a o d v 中的一个关键问题。在a o d v 建立路由的时候，需要和其它的节点协作，交换路由信息，没有采取相应的安全 措施，很容易成为恶意节点攻击的目标。 1 2 课题研究内容及意义 1 2 1 研究内容 本课题从无线自组网中的a o d v 路由协议存在的安全缺陷和混沌( c h a o s ) 密 码算法的特点和性能两方面入手： 一方面在分析了a dh o c 网络中的路由协议的特点后，对a o d v 路由协议作进 一步的论述，列举对路由协议的攻击的方式以及a o d v 路由协议在恶意攻击下存 在的问题；另一方面从混沌密码算法出发，给出了混沌密码算法的特点，以及混 沌算法与其它密码算法在时间上的性能分析和比较。 在此基础上提出把混沌算法引入到a o d v 路由协议中的方案，以加强a o d v 路 由协议的安全性能。具体分析了引入混沌算法后的路由包及数据包发送的过程， 并作安全分析。最后利用仿真工具n s ( n e ts i m u l a t o r ) ，给出了在不同场景下的 仿真性能分析，并与引入同为流密码算法的r c 4 算法后的a o d v 协议进行比较分 析。 1 2 2 意义 无线白组网可以通过临时组网的方式在恶劣环境中支持移动节点之间的数 据、语音、图像和图形等业务的无线传输，应用范围可以覆盖工业、商业、医疗、 家庭、办公环境、军事等各种场合，尤其在未来战场上，无线自组网络对于高技 术武器装备、集中指挥、协同作战和提高作战机动性等具有非常重要的意义。由 于自组网的特殊性使得在实现这些安全目标时，面临诸多挑战。而在自组网的协 议中实现安全性，就成为在研究自组网时的一个重要而又具有挑战性的任务。 而a o d v 路由协议是自组网中的一个重要的协议，是无线自组网的研究热点， 3 武汉理工大学硕士学位论文 有着广泛地应用前景，因此本课题将研究的重心放在无线自组网的a o d v 路由协 议的安全性能上。 1 3 论文结构 本文第2 章对a dh o c 网络的路由协议进行了描述，从发现路由的策略的角 度上，可以将路由协议分成表驱动路由协议和按需路由协议，并且对这两类协议 中典型的具体协议作了比较。 第3 章介绍了密码算法，对当前流行的密码算法做了阐述。由于本文涉及到 了流密码算法，因此本章分析了流密码的特点，并对混沌密码算法作了进一步的 分析。最后给出混沌算法的自编程序，并与r c 4 算法在l i n u x 下进行了测试，给 出了时间性能的分析结果。 第4 章对第2 章的内容进行了延伸，从a o d v 路由协议的安全性能的目标出 发，先列举了国内外的研究现状，再给出a o d v _ c 路由协议中包发送及验证的流 程，并进行安全分析。 第5 章在l i n u x 操作系统下，利用n s 2 仿真平台，对于利用混沌算法改进的 a o d v 路由协议进行仿真，并与应用r c 4 流密码算法的a o d v 协议以及原a o d v 路 由协议进行对比。 第6 章对整个论文的工作作出了总结，并且对后续的工作进行了简要的描 述。 4 武汉理工大学硕士学位论文 第2 章无线自组网路由协议 无线自组网中不存在中心节点，每个节点都充当路由器和主机的功能，这就 使得自组网的路由发现、维护等机制和常规的路由协议不同，都必须由节点来完 成。无线自组网中的节点处于不断地运动状态中，并且每个节点的发射功率有一 定的半径，路由的建立与断开都经常发生，这就要求有合适的路由协议，来对路 由进行建立、维护以及撤消。而且由于自组网中的节点是依靠电池来进行供电， 因此路由协议不能象常规路由一样运行大规模的查找，存储等过程。 本章从路由发现策略的角度上，比较了主动路由协议与按需路由协议，并对 a o d v 路由协议进行了详细地分析。 2 1 无线自组网路由协议特征 常规的因特网的路由协议如：r i p 是基于距离矢量的路由协议，o s p f 是基 于链路状态的路由协议，这两类协议都应用在网络的拓扑结构是相对固定的，不 会出现大的变化的情况下。常规的路由协议一般是通过与相邻路由器交换路由信 息来达到网络拓扑的收敛状态。 由于无线自组网的节点可以不断地移动位置，导致网络的拓扑结构处于不断 地变化中，要维持通信，就必须重新寻找路由。常规的因特网路由协议如果应用 于自组网上，就会在重新进行路由发现这个过程上花费很多的时间，使得网络一 直处于非收敛的状态下。 自组网不能采用常规路由协议主要由于以下几种因素“1 ： ( 1 ) 无线自组网络中无线传输设备功率的差异以及无线信道中的大量干扰导致 单向信道的存在。 ( 2 ) 无线信道的广播特性使得常规路由的网络选路过程中产生许多冗余链路。 ( 3 1 常规路由的周期性广播路由更新分组会消耗大量的网络带宽。 ( 4 ) 常规路由协议周期性地发送路由更新分组会消耗大量的节点能源。此外， 某些常规路由协议需要的复杂计算使得c p u 始终处于很高的负载下，这也 同样消耗了大量的能源，并将对有限的节点能源带来更多的压力。 因此需要有适用于无线自组网的路由协议。自组网路由协议的任务是实现路 由，又由于与常规路由的不同特性，如具有动态拓扑、有限带宽、终端受限、存 在单向信道等特点，因此对于无线自组网的路由协议提出了更高的要求： ( 1 ) 收敛迅速。自组网的拓扑结构是动态的，随时处于变化之中，这就要求路 5 武汉理工大学硕士学位论文 由协议必须对拓扑的变化具有快速反应能力，在计算路由的时候能够迅速 收敛，及时获得有效的路由，避免出现目的节点不可达的情况。 ( 2 ) 提供无环路由。无论在有线网络还是无线网络下，提供无环路由是对路由 协议的一项基本要求。但在自组网中，由于拓扑结构动态变化会导致大量 已有路由信息在短时间内作废，从而更容易产生路由环路。因此，在自组 网中提供无环路由就显得尤为重要而且更难做到。 ( 3 ) 避免无穷计算。经典的距离矢量算法在某条链路失效时，有可能出现无穷 计算的情况。在自组网中，链路由失效是经常发生的事，这就要求在自组 网中运行的路由协议必须能够避免无穷计算，不采用或者改进会出现无穷 计算的算法。 ( 4 ) 控制管理开销小。自组网中无线传输带宽有限，传送控制管理分组不可避 免地会消耗掉一部分带宽资源。为了更有效地利用宝贵的带宽资源，需要 尽可能地减小控制管理的开销。 ( 5 ) 对终端性能无过高要求。无线终端使用可耗尽能源，c p u 性能、内存大小、 外部存储容量等都低于固定的有线终端，因此，在自组网中不能对终端性 能要求过高有线网络中用计算的复杂度来换取路由协议性能的做法，在 自组网中不再适用。 ( 6 ) 支持单向信道。在自组网中，经常有可能出现单向信道。支持单向信道， 也是对路由协议的要求之一。 ( 7 ) 尽量简单实用。简单有助于提高可靠性，也有助于减少各种开销。在实现 路由功能的前提下力求简单，是自组网路由协议的原则之一。 ( 8 ) 安全性。路由算法提供防止路由包或者数据被篡改，假冒等情况的发生。 2 2 路由协议分类 移动自组网的路由协议结构主要建立在i s o 0 s i 模型和t c p i p 结构基础之 上。参照o s i 七层模型，自组网协议可以分层归纳如下嘲： 6 武汉理工大学硕士学位论文 应用层 高层应用 表示层 w p坷峨应用 移动核心同业务 会话层 中间件地址服务，群通讯共享内存 传输层 无线1 p ，u d p 表驱动路由 按需驱动路由 其它 同络层 d s d vw r p d s ra o d vt o r a z r p 实现技术( 物 i 髓e b 0 幺1 1 苴牙技术 h i l a a l a n 理层、数据链 路层) 包括媒介接入控制层( m a c ) ，逻辑链路层( l l c ) ，天线，能源控制荨 图2 - i 无线自组网的分层结构 在自组网中，物理层完成无线信号的编码、译码、发送和接收等功能；数据 链路层控制对共享无线信道的访问以及对链路的控制：数据链路层又分为m a c 层 ( 媒介接入控制层) 和l l c ( 逻辑链路控制层) ；网络层是移动自组网技术的重点， 无线自组网的路由协议就是在网络层实现，提供网络层数据服务、路由服务、o o s 支持等功能；传输层主要完成端到端通信的建立，目前主要是对有线网中使用的 t c p l i d p 协议进行改造，使之适应无线环境；高层应用主要是建立在自组网络之 上的无线应用及移动通信核心网的各种业务。 对于已经提出的自组网路由协议，可以从不同的角度进行不同的分类“】： 武汉理工大学硕士学位论文 其中主动路由协议和按需路由协议是从发现路由的策略的角度上进行分类 的。下面对平面路由中的主动路由协议和按需路由协议作进一步的讨论。 2 3 主动路由协议 主动路由协议旧也称为表驱动路由协议( t a b l ed r i v e n ) 、先应式路由协议。 协议中每个节点都要周期性地向其它节点传送最新的本节点的路由状态；每个节 点都维持一个到其它节点的相对稳定的最新的路由表，当网络的拓扑状态发生变 化的时候，通过在网络内广播路由更新信息来反映网络拓扑的变化，使网络拓扑 达到收敛状态。 主动路由协议会周期性地进行路由信息的交换，通过在全网内的广播来交换 以及更新路由信息。当源节点发送数据分组时，只要在源节点的路由表中，到达 目的节点的路由存在，所需延时就很小。主动路由协议比较适合有实时和服务质 量要求的网络通信。由于节点处在运动状态中，为了使路由更新能紧随当前拓扑 结构的变化，主动路由协议需要花费较大开销；而且动态变化的拓扑结构可能使 路由信息过时，路由协议不易收敛 2 3 1d s d v d s d v “3 ( d e s t i n a t i o n - s e q u e n c e dd i s t a n c e v e c t o r ) ：目的节点序列距离矢 量协议，是一个从传统的b e l i m a n - f o r d 路由选择算法扩展的主动路由协议，被 认为是最早的自组网路由协议，采用了序列号的机制，来防止路由环路的产生。 在d s d v 协议中，每个节点都维护了一张路由表，其中的表项包含了本节点可以 到达的目标节点的、路由跳数、目的节点路由序列号等等。 在d s d v 进行路由发现的过程中，每个节点周期性地把自己的路由表向全网 进行广播，其中包含了该节点的路由表中已知的目的节点序列号；还包含了该节 点本身的序列号，每广播一次就进行加1 的操作。当与这个节点相邻的节点接收 到这个路由表时，先比较源，目节点路由序列号的大小，序列号大的路由信息就 会更新本身的路由表项，把发送者作为下一跳，并将距离加1 ；如果目的序列号 相同，但跳数较小，则表示找到了距离更短的路径，也更新节点本身的路由表项； 如果目的序列号较小，则不进行任何操作。在这里，目的序列号被作为一个重要 的标志，以区分路由的新旧，来防止路由环路的产生。 d s d v 进行路由在进行路由维护过程中，当节点的路由表发生变化的时候， 会将其路由信息传给相邻的节点；当一个节点发现链路失效的时候，将所有通过 这条链路的目的路由的距离设为无穷，并将序列号加l ，这个更新了序列号的路 由表也会被发送到其相邻的节点，由于序列号较大，则更新了接收节点的路由表， 8 武汉理工大学硕士学位论文 使得这条链路的状态被全网的节点接收。 d s d v 更新路由表有两种方式，增量更新和海量更新。当网络拓扑变化较快 的时候，只更新移动节点的路由，这样可以降低路由的开销；而且网络拓扑变化 较慢的时候，可以采用整个路由表更新的方式。 2 3 2 w r p w r p t s j ( w i r e l e s sr o u t i n gp r o t o c 0 1 ) ：无线路由协议，是一种基于距离向 量的路由协议，是利用每个节点记录的路由表来完成路由工作，通过与其邻居节 点交换路由更新消息来维持最新的路由信息。路由表的表项包含目的节点、到目 的节点的最短距离和倒数第2 跳节点构成。网络内每个节点都维护4 张表来进行 操作，分别为距离表，路由表，链路状态表以及信息重传列表。当源节点检测到 与其相邻的一个目标节点的路由发生变化的时候，源节点会去检查所有邻居节点 关于倒数第2 跳节点信息的一致性；而且每个节点会向其邻居节点传送距离和第 2 跳到最后一跳的路由信息，通过检测收到的信息，消除路由环路的出现，使得 路由协议的收敛速度加快。当节点路由表中没有任何变化的时候，目标节点需传 回一个空闲的h e l l o 分组以表示本条连接的存在，否则就修改距离表，寻找更 新的路径，新的路由信息需要反馈给原始节点以便其修改路由。 w r p 可以在当检测到任意相邻节点变化的时候，检查所相邻节点的状态以消 除回路，具有较快的收敛速度。在协议中的四张表中包含的路由信息较详细，有 利于寻找路由，但是占用的资源较多。 2 4 按需路由协议 按需路由协议也被称为反应式路由协议、源启动按需路由协议( s o u r c e i n i t i a t e do nd e m a n dd r i v e nr o u t i n gp r o t o c 0 1 ) 。仅在需要路由的时候由源节 点发起路由请求，因此，拓扑结构和路由表的内容是按需建立的，可能仅仅是网 络中整个拓扑结构信息的一部分。在通信过程中维护路由，通信完毕后便不再进 行维护。 通常，按需要路由包括3 个过程：路由发现过程、路由维护过程和路由拆除 过程。这种路由选择方式只有当源节点需要时才建立路由。 当一个节点需要到目的节点的路由时，它会在全网内通过洪泛的方式发起路 由发现过程，即当源节点发现没有去往目的节点的路由时，触发路由发现过程， 当检验完所有可能的路由排列方式或找到新的路由后就结束路由发现过程；路由 建立后，由路由维护程序在通信过程中来维护这条路由，一般依靠底层提供的链 路失效检测机制来完成，直到它不再被需要或者发生链路断开现象；通信完毕后， 9 武汉理工大学硕士学位论文 路由拆除过程将路由取消。 2 4 1d s r d s r j ( d y n a m i cr o u t i n gp r o t o c 0 1 ) 动态路由协议，是一种最早采用的典型 的按需路由协议。采用了两种机制：源路由机制和按需路由机制。源路由机制是 指每个分组头部都包含了整条路由的信息，这样在节点发送分组的时候，就已经 拥有到达目的节点整条的路径，而且每个节点都拥有一个c a c h e ( 缓冲器) 来存储 路由信息，中间节点就不必再添加新的路由信息，网络开销较小；按需路由机制 是指在节点需要发送数据到另一个节点的时候，才由源节点进行路由发现过程。 d s r 包含两个部分的操作：路由发现和路由维护。 在路由发现阶段，由于d s r 是按需路由协议，当源节点需要发送数据到目的 节点的时候，先在本节点的c a c h e 中去查找是否存在有到达目的节点的路由。如 果这条链路存在，就把该路由信息放在分组头部，进行发送；如果没有这条链路， 那么源节点就用洪泛( f l o o d i n g ) 的方式进行查找路由的操作。源节点发送的路由 请求包中包含了序列号和源节点的i d ，当相邻的节点收到路由请求的时候，在 一般情况下，将自己的地址添加到路由请求包头部的路由序列中，再向所有相邻 节点洪泛发送更新后的路由请求包；如果在该节点的缓冲器中已经包含了一条到 达源节点所要求的目的节点的路径或者本身就是源节点所要求的目的节点，则就 发送一个路由响应包给源节点；如果不满足上面的情况，而且这个节点接收过相 同的路由请求包，则不再向邻居节点转发，以防止出现环路。 路由维护阶段是发生在一个节点发送或中转数据的时候，从头部的路由信息 中发现到达下一跳的链路中断，则进行路由维护的过程。由发现链路中断的节点 向上游节点发送错误分组( r o u t ee r r o r ) ，沿着路径返回源节点，中途的节点在 转发这个分组的时候，把本节点缓冲区中的相关的信息也删除。错误分组信息传 送到源节点后，源节点先在缓冲区中寻找是否存在到达目的节点的冗余路由，如 果有，则用新的路由进行发送数据，如果没有，则再发起路由发现过程。 2 4 2t o r a t o r a “”( t e m p o r a l l yo r d e r e dr o u t i n ga l g o r i t h m ) ；临时预定路由算法采用 了链路反转( l r ，l i n kr e v e r s a l ) 分布式算法的按需路由协议，并且引入了有向 无环图( d a g ，d i r e c t e da c y c l i cg r a p h ) 算法及高度机制，由源节点发起，能得 到多条源节点到目的节点路由的协议。 t o r a 包含三个部分的操作：路由建立( r o u t ec r c a t i o n ) ，路由维护( r o u t e m a i n t e n a n c e ) 和路由拆除( r o u t ee r a s u r e ) 。 1 0 武汉理工大学硕士学位论文 在路由创建和维护阶段，每个节点都被指定了一个高度( h e i g h t ) ，建立一个 以目的节点为根的有向无环图。这样链路可以根据相邻节点的高度来决定发送数 据的方向。 当一个节点需要一条路由到特定的目的节点时，就广播一个包含目的节点地 址的路由请求分组( q r y ) ，接收到路由请求分组的中间节点会广播一个拥有到达 目的节点路径中各节点高度的u p d 分组，如果中间节点没有这样的信息，则从目 的节点开始，向源节点进行广播，这个时候，目的节点的高度就为0 。当这个u p d 更新分组在全网内进行传送的时候，每个接收到的节点都重新设置它到这个目的 节点的高度值，当高度值比当前节点的高度值来得小的时候，表示当前有一条到 达目的节点的更短的有效路由，则进行设置。当这个u p d 分组返回到了源节点的 时候，就生成了一条从源节点到目的节点的链路。 当节点移动导致原d a g 图断开的时候，则进行路由维护过程，由发生中断的 节点负责向上游节点进行更新，把新的高度值传回源节点。t o r a 还可以传送一 个c l r 分组来删除无效的链路。 2 4 3a v a o d v “1 ( a d h o co n - d e m a n dd i s t a n c ev e c t o rr o u t i n g ) ：按需距离矢量路 由协议，以d s d v 算法为基础，是对d s d v 算法的改进。 a o d v 是一种按需驱动路由协议，即当源节点要与目的节点进行通信时，才 发起一个路由发现的过程。最早由c h a r l e se p e r k i n s 和e 1 i z a b e t hm b e l d i n g r o y e r 和s a m i rr d a s 三个人共同提出的。协议包含了两类操作：路 由发现和路由维护。a o d v 是一个纯粹的按需路由协议，那些不在路径内的节点 不保存路由信息，也不参与路由表的交换。 由于下面要对a o d v 协议作进一步的讨论，这里把a o d v 协议的流程进行说明： 当源节点要与目的节点通信时，首先去查找源节点的路由表，如果表中已经 存在到达目的节点的路由，则跳过路由发现阶段。当源节点的路由表中没有相应 的路由信息时，它就会发起路由发现过程。由源节点向其邻居节点洪泛广播一个 r r e q ( r o u t er e q u e s t s ，路由请求) 包，在a o d v 中，路由请求包有固定的格式， r r e q 包的格式如图2 3 所示： 武汉理工大学硕士学位论文 ol23 01234567890l23456789012345678901 + + + + + + 一+ + + + + 一+ 一+ + + + + 一+ + 一+ + + 一+ + 一+ + + + + 一+ + + - + i t y p e l j i r i g i d i u l r e s e r v e d h 印c o u n t i + 叫+ 叫 + _ + + - - + + _ + h + - 卜+ 1 - 4 - - 4 - ；：一+ 叫 _ 1 + 叫 + + i胩明idl + + h h + + + + + + + 一卜_ + h + + p 叫+ + p h + + - + l d e s t i n a t i o ni pa d d r e s s l + + p + + 一+ + 十p p + 卜+ + 一+ p + + 一+ h + + p + l d e s t i n a t i o ns e q l i e n c ei t i + + + 叫+ + + p 十+ 一+ + p d h - + + + 一+ + + 一+ p h + + + - + io r i g i n a t o ri p d d r e 8 8l 1 11 1 11111111 - - + - 4 - - + + + 一+ + 一+ + + 一+ + + + + + + + 叶 l o r i g i n a t o rs e q u e m e 确曲e r l + p h + p + 一+ + 一+ 卜+ + 一+ + + + + + + 卜+ + p + + p _ + 图2 - 3a o d v 的r r e q ( 路由请求) 包 r r e q 第一个字节( t y p e ，消息类型) ，被设置为1 ，表示为r r e q 包；j ( j 0 i n f 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 i e s ，路由响应) 是 否向目的i p 地址字段指明的节点进行单播。h o pc o u n t 字段为跳数。r r e qi d 是表明源节点发起的不同的路由请求的标识号。 当源节点向目的节点发送r r e q 包的时候，中间节点接收并转发这个r r e q 包 的同时也建立起了一个反向的路由，同时这个反向路由拥有一个 a c t i v e r o u t e t i m e o u t 变量，即活跃路由的失效时间，当目的节点返回的r r e p 包在这个时间范围内到达时该节点时，这个节点就会沿着建立起来的反向路由来 转发r r e p 包。否则就算职e p 包到达这个节点，也被认为是过时的路由，不予以 转发。 当中间节点收到一个r r e q 包的时候，一般情况下，中间节点把跳数字段加 1 ，然后转发这个路由请求包。如果这个中间节点拥有到达目的节点的路由，而 且该节点的路由表项中的目的节点序列号比r r e q 包中的目的节点序列号 ( d e s t i n a t i o ns e q u e n c en u m b e r ) 来得大，这时就表示该中间节点拥有一个到达 目的节点的最新的路由，就沿着建立起来的路由返回一个r r e p 分组；如果不是， 这个中间节点还要继续转发这个r r e q 包，直到到达目的节点或者中间节点拥有 到达目的节点的最新的路由为止。 源节点还保留一个定时器，当在定时器规定的时间范围内没有收到一个r r e p 包，则认为本次的路由请求已经失效，则由源节点重新发起路由请求过程，本次 的路由请求包的其它部分与上一次r r e q 包相同，但是r r e qi d 就比上一个的路 由请