（计算机科学与技术专业论文）manet网络qos路由技术和安全路由技术的研究.pdf

国防科学技术大学研究生院工学硕士学位论文 摘要 随着无线网络技术的发展，移动自组织网络( m a n e t ) 逐渐成为人们研究的 焦点。m a n e t 网络与传统的无线网络技术不同，它不需要固定的基础设施，具有 更好的灵活性。该网络支持多跳通信，使得距离较远的节点间的通信可以通过中 间节点的路由来实现，这就要求每个节点都具备路由功能。 本文对m a n e t 网络及其现有的各种路由协议进行了深入的研究，提出了一 种q o s 路由解决方案。这种解决方案使用了m q r d 路由发现机制和p r m 路由维 护机制。m q r d ( 依赖m a c 层的q o s 路由发现机制) 通过m a c 层对节点的延迟 进行估算，源节点发送的路由请求报文将路由中每个节点估算的延迟值收集起来 并进行叠加，最终由路由响应报文将该值返回给源节点，源节点选择一条符合延 迟要求的路径作为路由。p r m ( 基于探针的路由维护机制) 通过探测包在源节点 和目的节点间往返一周的方式估算当前路由延迟，源节点根据探测包的探测结果 判断当前路由是否仍满足q o s 要求，并决定是否需要重新建立路由。仿真实验表 明论文提出的q o s 路由解决方案可以在不增加太多开销的情况下明显降低延迟。 加密技术与信用机制都可用于安全路由技术。然而，二者各有侧重点，加密 技术重在保护路由信息，而信用机制则用于检测恶意节点。本文融合二者优点， 提出了一种新型的安全路由解决方案。在这种方案中，节点通过监测邻居节点行 为评估其信用。考虑节点下一跳的下一跳( 论文称之为“第二跳”) ，节点通过 “第二跳”节点反馈的ra c k 报文获得其下一跳节点的报文转发情况，以此实现 对邻居节点行为的监测。该安全路由方案通过基于信用的路由发现机制将恶意节 点隔离出去。理论分析表明，论文提出的安全路由解决方案能够防止针对路由信 息和数据报文的攻击。 最后，基于论文提出的q o s 路由方案和安全路由方案，本文设计了一种既支 持q o s 也支持安全的路由协议。 主题词：m a n e t ，路由协议，q o s ，安全，信用，数字签名 第i 页 国防科学技术大学研究生院工学硕十学位论文 a b s t r a c t a l o n gw i t h t h ed e v e l o p m e n to fw l a nt e c h n o l o g y ，m o b i l ea dh o cn e t w o r k ( m a n e t ) i sg e t t i n gm o r ea n dm o r ep o p u l a ra m o n gr e s e a r c h e r s u n l i k et h et r a d i t i o n a l w l a n ，m a n e tn e e d sn of i x e di n f r a s t r u c t u r e ，a n di ti sm u c hf l e x i b l ea sar e s u l t m a n e tc o m m u n i c a t e si nam u l t i h o ps t y l e ，t h u sm a k e si tp o s s i b l ef o rn o d e sf a ra w a y f r o me a c ho t h e rt ok e e pi nt o u c hw i t ht h ef o r w a r d i n go fi n t e r m e d i a t en o d e s t os u p p o i r t t h i sf o r w a r d i n g ，e v e r yn o d ei nm a n e tm u s th a v et h ef u n c t i o no fr o u t i n g t h et h e s i sm a k e sa ni n - d e p t hs t u d yo fm a n e ta n di t sr o u t i n gp r o t o c o l s ，a n d p r o p o s e saq o sr o u t i n gs o l u t i o n t h es o l u t i o nc o m p r i s e sam a c d e p e n d e n tq o s r o u t i n gd i s c o v e r ym e c h a n i s m ( m q r d ) a n dap r o b e - b a s e dr o u t i n gm a i n t e n a n c e m e c h a n i s m ( p r m ) i nm q r d ，d e l a yi s e s t i m a t e da tm a cl a y e r ，a c c u m u l a t e db y r o u t i n gr e q u e s tm e s s a g e ( r r e q ) w h i l ei tt r a v e l sf r o ms o u r c et od e s t i n a t i o na n df i n a l l y g i v e nb a c kt os o u r c ew i t ht h er o u t i n gr e p l ym e s s a g e ( r r e p ) t h es o u r c en o d ew i l l c h o o s ear o u t i n gm e e t i n gt h ed e m a n di nd e l a y a c c o r d i n gt op r m ，t h es o u r c en o d e s e n d sa p r o b et od e s t i n a t i o na n di nt e r m so ft h ed e l a yf r o mt h et i m et h ep r o b el e a v e s s o u r c et ot h et i m ei tc o m e sb a c kf r o md e s t i n a t i o n ，i td e c i d e sw h e t h e rt h er o u t i n gs t i l l s u p p l i e st h er e q u i r e dq o sa n dw h e t h e rt oi n i t i a t ear o u t i n gr e c o v e r y t h es i m u l a t i o n s h o w st h a tt h eq o sr o u t i n gs o l u t i o nw ep u tf o r w a r dr e d u c e st h ee n d t o - e n dd e l a y o b v i o u s l yw h i l ei n c r e a s eo n l yal i t t l eo v e r h e a d b o t he n c r y p t i o nt e c h n i q u e sa n dt r u s tm o d e l sc a nb ea d o p t e di ns e c u r i t yr o u t i n g h o w e v e r ，e a c ho ft h et w oh a si t ss t r o n gp o i n t e n c r y p t i o nt e c h n i q u e sf o c u so nt h e p r o t e c t i o no fr o u t i n gi n f o r m a t i o nw h i l et r u s tm o d e l so nt h ed e t e c t i n go fm a l i c i o u sn o d e s t h es e c u r i t yr o u t i n gs o l u t i o nw ep r o p o s e dh a si n t e g r a t e dt h eb o t ha d v a n t a g e s i no u r s o l u t i o n ，t h en o d em a k e st h ee v a l u a t i o no ft r u s to ni t sn e i g h b o r sb yo b s e r v i n gt h e i r b e h a v i o r s t l en o d ei si n f o r m e dt h en u m b e ro fp a c k e t si t sn e x t h o pn o d ef o r w a r d s b yi l a c k s e n tf r o mi t s “s e c o n d h o p ”n o d e ( t h en e x t - h o pn o d eo fi t sn e x t - h o pn o d e ) a f t e rf i n d i n go u tt h em a l i c i o u sn o d e ，i ti si s o l a t e df r o mo t h e rn o d e sb yat r u s t - b a s e d r o u t i n gd i s c o v e r ym e c h a n i s m t h et h e o r e t i ca n a l y s i ss h o w st h a tt h es e c u r i t yr o u t i n g s o l u t i o nw eb r i n gf o r w a r dc a np r e v e n tt h ea t t a c ka i m e da tr o u t i n gi n f o r m a t i o na n dd a t a p a c k e t s a tt h ee n do ft h et h e s i s ，w ed e s i g naq o ss e c u r i t yr o u t i n gp r o t o c o lb a s e do nt h e r o u t i n gs o l u t i o np r o p o s e da b o v e k e yw o r d s ：m a n e t ，r o u t i n gp r o t o c o l ，q o s ，s e c u r i t y ，t r u s t ，d i g i t a ls i g n a t u r e 第i i 页 国防科学技术大学研究生院工学硕十学位论文 表目录 表3 1 用探针延迟测量法进行延迟估算的均方误差2 3 表3 2 用统计延迟测量法进行延迟估算的标准差2 3 表3 3 探针延迟测量法和统计延迟测量法的对比2 4 第1 l l 页 国防科学技术大学研究生院丁学硕十学位论文 图目录 图2 1 节点n 的多点中继7 图2 2a o d v 协议r r e q 报文格式9 图2 3a o d v 协议r r e p 报文格式1 0 图2 4a o d v 协议r e r r 报文格式1 0 图2 5a o d v 协议r r e p a c k 报文格式l l 图2 6a o d v 协议的路由发现过程1 1 图3 1c l ，所传输的报文的端到端延迟情况2 2 图3 2 路径的延迟近似看做每个结点( 不包含目的结点) 的m a c 层延迟之和2 5 图3 38 0 2 1 1d c f 单播帧的正常发送过程2 5 图3 48 0 2 1 1d c f 单播帧错误重传过程2 6 图3 5 修改后的r r e q 报文格式。阴影部分表示原始r r e q 报文2 8 图3 6 修改后的r r e p 报文格式。阴影部分表示原始r r e p 报文2 9 图3 7 不同结点移动速度下两种协议的归一化开销3 l 图3 8 不同结点移动速度下两种协议的端到端延迟3 l 图3 9 不同网络规模下两种协议的归一化开销3 2 图3 1 0 不同网络规模下两种协议的端到端延迟3 2 图4 1 一种基于摘要的数字签名技术的工作过程3 5 图4 2 节点a 对其邻居结点b 的行为的监测过程3 6 图4 3ra c k 报文格式3 8 图4 4 每个节点的收发包数目3 8 图4 5ra c k 报文的发送过程3 8 图4 6 每个节点发送的ra c k 报文3 9 图4 7 利用ra c k 向上游节点通报收包数目的过程4 0 图4 8 基于信任的路由报文格式4 l 图4 9 路由中恶意节点收到ra c k 报文后的可能行为4 2 图5 1q o s 安全路由协议基本结构4 5 图5 2q o s 安全路由协议信用评估模块4 5 图5 3q o s 安全路由协议延迟评估模块4 6 图5 4q o s 安全路由协议的r r e q 和r r e p 报文格式4 6 图5 5q o s 安全路由协议路由发现模块的工作流程4 7 图5 6q o s 安全路由协议的路由维护4 8 第1 v 页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的币珂究工作及取倜的研 究成果。尽我所知，除了文中特别力i ，以标注和致谢的地力外，论文中彳：包台其他人已 经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它教育机构的学 位或证书而使用过的村料。与我一同工作的同志对本研究所做的任何i ，l - j r 献均n 在论文 中作了明确的说明并表示谢意 学位论文题日： 丛g ! 圈终q ! 查竖l 垫j 盔塑! 窒垒竖凼i 丕曲型童 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定。本人授权国 防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子文档，允 许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据库进行检索， 可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密学位论文在解密后适用本授权书。) 学位论文作者签名：一j 昏b 址 作者指导教师签名： 日期：可勿萝年f 1 月迈日 日期：j 妒乎年，p 月 p 日 ，、 国防科学技术大学研究生院工学硕士学位论文 第一章绪论 随着无线网络技术的发展以及应用需求的不断增长，m a n e t 网络逐渐成为人 们研究的热点。m a n e t ( m o b i l ea dh o cn e t w o r k ) 网络，也叫移动自组织网络或 移动a dh o c 网络，与传统的无线网络技术不同，它不需要固定的基础设施，具有 更好的灵活性，与此同时，该网络支持多跳通信，使得距离较远的节点间的通信 可以通过中间节点的中转来实现。m a n e t 网络在灾难救援、战场等恶劣环境和特 殊场合下拥有巨大的应用前景。 1 1m a n e t 网络简介 1 1 1 无线网络技术现状 无线网络是指利用无线电波作为信息传输媒介而构成的无线局域网。 现在比较流行的几种无线网络模型有：无线局域网( w l a n ) 、无线蜂窝网 络以及移动自组织网络( m a n e t ) 。 w l a n 是最常用的无线网络之一，几乎所有的移动电脑都支持该技术。在 w l a n 中，节点可以采用无中心控制的方式进行单跳通信，以竞争的方式使用无 线介质，也可以由a p ( a c c e s sp o i n t ) 集中控制无线介质的访问。这两种访问方式 分别称作分布协同功能( d c f ) 和点协同功能( p c f ) 。w l a n 的节点移动性较 差，但由于存在中心控制( a p ) ，w l a n 能很容易的实现与有线网络的互联。 无线蜂窝网络组成主要有以下三部分：移动站、基站子系统、网络子系统。 移动站就是网络终端设备，如手机和其它一些蜂窝工控设备。基站子系统包括我 们日常见到的移动基站、无线收发设备、专用网络( 一般是光纤) 、无线数字设 备等等。我们可以把基站子系统看作是无线网络与有线网络之间的转换器。无线 蜂窝网络的覆盖范围非常广，节点具有很好的移动性。 1 1 2m a n e t 网络的基本特征 移动自组织网络产生于上世纪七十年代，最早由美国国防部研究并应用于军 事领域。a dh o c 网络既不需要固定的网络结构，也没有专用的固定基站或路由器 作为网络的管理中心。网络中的每个节点均具有路由器功能，能够发现和维护到 其它节点的路由、向邻居节点发送和转发数据报文。a dh o c 网络由一系列具有无 线收发功能的移动节点组成，每个节点可以动态的加入和离开网络。 m a n e t 网络具有以下几个基本特征： 第1 页 国防科学技术大学研究生院工学硕十学位论文 移动性：网络中的节点都是不断运动的，网络的拓扑结构不是i 直i 定的，而是 随着时间动态的变化。 多跳通信：网络中某两个节点的距离可能会超过它们的通信距离，这时，它 们的通信过程需要经过中间节点对数据报文进行路由转发才能进行，数据报文从 源节点发送出后，需要经过多次中转才能到达目的节点，故称之为多跳通信。 共享信道：节点间通过无线电波进行通信，共享无线信道，因此，需要考虑 不同节点竞争信道的问题，而且，由于无线信号极易受干扰，所以共享信道也带 来了安全方面的隐患。 缺少集中控制：a dh o c 网络中，不设专门的控制中心，把网络的控制功能分 散到各个节点中，节点兼具主机和路由器两种角色。所有的网络节点使用相同的 通信设备，具有相同的功能，网络的建立和调整是通过各节点的有机配合实现的， 即a dh o c 网络均衡了各节点的特殊性和重要性。从控制能力上看，各节点没有主 次之分，从而不会出现控制中心被破坏而引起全网瘫痪的情况，提高了网络的抗 毁性。 1 1 3m a n e t 网络的应用背景 由于a dh o c 网络的本身具有的一些特性，它的应用领域与传统的无线通信网 络有着显著的区别。它适用于无法或不便预先构建网络设施和需快速自动组网的 场合。移动a dh o c 网络的研究最早是针对军事应用的。目前，军事应用仍是a dh o c 网络的主要应用领域，但是，近些年来，在民用方面，a dh o e 网络也得到了广泛 的应用。它的应用场合主要有以下几类： 军事领域：军事应用是a dh o e 网络技术的主要应用领域之一。因其特有的无 需架设网络设施、组网速度快、抗毁性强等特点，它成了数字化战场通信的首选 技术。a dh o e 网络技术已经成为美军战术互联网的核心技术。美军的数字电台和 无线互联网控制器等主要通信装备都使用了a dh o e 网络技术。 传感器网络：传感器网络是a dh o c 网络技术的另一大应用领域。对于很多应 用场合来说传感器网络只能使用无线通信技术。而考虑到体积和节能等因素，传 感器的发射功率不可能很大。使用a dh o c 网络实现多跳通信是非常实用的解决方 法。分散在各处的传感器组成a dh o c 网络，可以实现传感器之间和与控制中心之 间的通信。这在爆炸残留物检测等领域具有非常广阔的应用前景。 灾难救援等恶劣场合：在一些重大灾难( 如地震、水灾、强热带风暴或其它 灾难) 发生后，原有的固定网络设施( 如有线通信网络、蜂窝移动通信网络的基 站等网络设施、卫星通信地球站以及微波接力站等) 可能被全部摧毁或无法正常 工作，对于抢险救灾来说，这时就需要a dh o e 网络这种不依赖任何固定网络设施 第2 页 国防科学技术大学研究生院工学硕士学位论文 又能快速靠设的自组织网络技术。类似地，处于边远或偏僻地区时，同样无法依 赖固定或预设的网络设施进行通信。a dh o e 网络技术的独立组网能力和自组织特 点，是这些场合通信的最佳选择。 个人通信：个人局域网( p a n ，p e r s o n a la r e an e t w o r k ) 是a dh o c 网络技术的 另一应用领域。不仅可用于p d a 、手机、手提电脑等个人电子通信设备之间的通 信，还可用于个人局域网之间的多跳通信。蓝牙技术中的超网( s c a t t e m e t ) 就是 一个典型的例子。 与移动通信系统的结合：a dh o c 网络还可以与蜂窝移动通信系统相结合，利 用移动台的多跳转发能力扩大蜂窝移动通信系统的覆盖范围、均衡相邻小区的业 务、提高小区边缘的数据速率等。 在实际应用中，a dh o c 网络除了可以单独组网实现局部的通信外，它还可以 作为末端子网通过接入点接入其他的固定或移动通信网络，与a dh o e 网络以外的 主机进行通信。因此，a dh o e 网络也可以作为各种通信网络的无线接入手段之一。 1 2m a n e t 网络路由技术概述 1 2 1 路由协议在m a n e t 网络中的地位 移动自组网是一种多跳通信的网络，它的每个节点都具有路由功能。两个在 彼此通信范围内的移动节点可以直接通过无线信道进行通信。然而，当目的节点 超出了源节点的信号覆盖范围时，就要通过具备路由转发功能的中间节点进行多 跳通信了。显然，在多跳通信的网络中，路由协议占据相当重要的地位。 1 - 2 2m a n e t 网络路由协议的分类 传统的路由协议都是基于固定不变的拓扑结构，在面对移动a dh o e 网络时， 就无能为力了。因此必须设计一种适用于a dh o c 网络环境特点的路由协议。经过 多年的研究，许多协议方案相继被提了出来。 根据路由建立的方式不同，m a n e t 网络路由协议可分为先应式路由协议( 如 d s d v 2 1 ，o l s r f 3 1 ，t b r p f 4 1 等) 、按需路由协议( 如d s r 5 1 ，a o d v 6 1 ，a b r 7 】等) 和混合式路由协议( 如z r p t 8 1 ，c e d a r 9 】等) ；根据路由协议所适用的网络规模不 同，可分为中、小规模的路由协议( 如a o d v ，d s r 等) 和大规模的路由协议( 如 f s r 10 1 ，c g s r r l1 1 ，l a n m a r 1 2 】等) 。 某些路由协议具备提供q o s 保证的能力，称为q o s 路由协议( 如c e d a r s r l t l 3 j ，q o s o l s r m 】等) 。根据q o s 的内在属性，将链路上的q o s 量度分类为瓶 颈型、求和型等类型。瓶颈型q o s 量度是指一条多段链路组成的路径上，路径的 第3 页 国防科学技术大学研究生院t 学硕士学位论文 q o s 量度是该路径上各段链路的q o s 量度的最小值；而求和型q o s 量度是指一条 多段链路组成的路径上，路径的q o s 量度是该路径上各段链路的q o s 量度之和。 路径的数据报文递交率是更复杂的q o s 量度，一般认为它是组成路径的各段链路 的数据报文递交率的乘积。 在m a n e t 网络中，q o s 路由的任务是找到并维护从源到目的节点的资源充 足的路由，以满足端到端的q o s 需求，并且尽量提高网络资源的利用率。q o s 路 由的关键问题是路由量度指标的选择、链路状态信息的获得和更新、q o s 路由的 维护。 为了支持q o s ，诸如时延、带宽、抖动、数据报文递交率以及数据错误率等 性能特征参数必须是可用可管理的。为获得并维护带宽参数信息，不可避免地要 增加一定数量的控制流量【l 引。由于拓扑动态变化，加之数据业务及实时业务的动 态性，这些控制流量开销有时可能会占用较多的带宽，必须在q o s 路由协议获得 的q o s 性能与引入的额外开销之间进行折衷。 m a n e t 网络由于其固有特性( 自组织、无中心控制等) ，存在着一些安全方 面的缺陷，需要研究者设计出安全路由协议来弥补m a n e t 网络的这些固有缺陷。 现有的几种主要的安全路由协议有：s a o d v 1 6 】、s e c m r 】和s r p 等。 当前，对于安全路由技术的研究主要有两种：一是通过观察节点行为进行恶 意节点检测并做出相应的处理【1 8 1 ；二是使用加密技术【1 9 】，加密技术在传统的网络 安全技术中已经得到了很好的应用，但对于m a n e t 网络的动态性( 节点可以动 态的加入或离开网络) 却仍然不能较好的支持。 1 3 课题研究的主要内容 论文认真分析了m a n e t 网络的固有特征，尤其对m a n e t 网络路由技术进 行了深入的研究，在q o s 路由技术和安全路由技术上取得了一些研究成果。课题 的主要内容分为以下几个方面： 1 移动自组织网络中q o s 保证的研究 与传统的网络不同，m a n e t 网络本身存在着许多问题，比如移动的网络基础 结构、频繁变化的网络拓扑、无线的通信信道等。正是这些问题的存在，在无线 移动自组网络中，路由协议的主要作用是监控网络拓扑结构变化，交换路由信息， 产生、选择和维护路由，并根据选择的路由转发数据，以提供网络的连通性。然 而，由于终端的移动性、网络拓扑结构的动态变化、传输的多跳性、无线信道的 不可靠性、网络资源的有限性等众多移动自组网特性，使得m a n e t 路由协议的 研究面临着巨大挑战。 在有线网络领域，q o s 选路日益受到重视。q o s 选路的作用就是要有足够的 第4 页 国防科学技术大学研究生院t 学硕士学位论文 资源来满足q o s 需求。在自组网环境下也存在q o s 需求。但是，有线网络的q o s 选路算法不能直接用于自组网，主要原因有：首先，大多数有线网络选路算法依 赖于精确的状态信息，这是动态变化的自组网所不能提供的。其次，节点可以随 时随地加入、退出、重新进入一个自组网，随着节点的移动，己有的链路可能消 失，新的链路可能形成，所以，已经建立的链路随时可能中断，这就提出了新的 问题即在数据传输的过程中，维持且动态地重建路由。 针对以上问题，本课题将在现有的q o s 协议基础上进一步研究，使用尽量小 的协议控制开销实现尽可能高质量的服务。 2 m a n e t 网络安全路由的研究 y a nl i n d s a ys u n 等人【2 0 】提出了信任模型的四个定理，对于信用度做出量化， 并研究了信用度的产生和传递规则。这是安全路由技术发展过程的一大创新，利 用量化的信用度，我们可以定量的去分析一条路由的安全情况，在路由的层面上 更好的保证了m a n e t 网络的安全。 当前，m a n e t 网络路由协议主要通过加密技术和信用机制保证安全。本课题 将着重设计一种高效的信用机制，并将其同加密技术相结合，提出一种新型的安 全路由解决方案。 3 q o s 安全路由协议的设计 课题将根据理论研究的成果，设计一种既支持q o s 又具有安全功能的路由协 议。 本论文结构组织如下： 1 4 论文结构 第一章对于m a n e t 网络的特点、 第二章介绍了m a n e t 路由技术， 究现状； 应用背景进行了概要的论述； 特别是q o s 路由技术和安全路由技术的研 第三章针对m a n e t 网络固有特性，提出了一种基于q o s 的路由发现和路由 维护机制，进而在a o d v 协议中实现了该机制并用n s 2 进行了仿真； 第四章提出了一种加密技术与信用机制相结合的安全路由解决方案，在该方 案中，通过对邻居节点行为的监测获得其信用情况； 第五章基于第三章和第四章的研究成果，设计了一种安全的q o s 路由协议； 结束语部分对本文工作进行总结，并探讨了下一步的研究工作。 第5 页 国防科学技术大学研究生院工学硕士学位论文 第二章m a n e t 网络路由技术的研究现状 本章对于当前m a n e t 网络路由技术的研究工作现状做了一些总结，分析了 路由技术研究中取得的成果，以及现有的技术中存在的不足。本章按照先应式路 由、反应式路由、q o s 路由和安全路由四种不同的分类方式，比较全面的概括了 当今m a n e t 网络领域常见的路由协议特点，并针对各类路由技术，挑选了一种 最具代表性的路由协议在工作原理和实现方法上进行了详细的介绍。 2 1 先应式路由协议 2 1 1 先应式路由协议简介 先应式路由协议( p r o a c t i v er o u t i n gp r o t o c 0 1 ) 2 1j ，也叫先验式路由协议、主 动式路由协议或表驱动路由协议。其原理是网络中的每个节点都在本地维护一个 包含到达其它所有节点路由信息的路由表。当节点检测到网络拓扑发生变化时， 更新本地路由表，并把这个更新消息发布到整个网络。先应式路由协议类似于有 线网络的路由协议，每个节点知道到达其它所有节点的路由，因此一旦有节点需 要发送报文，可以立即获得到达目的节点的路由。目前常用的表驱动路由协议主 要有o l s r 、d s d v 、w r p 等。这些协议的区别在于路由信息的更新、检测方式 以及路由表中保存并维护的信息类型。 先应式路由协议使节点维护的路由表可以较准确反映网络的拓扑结构。一旦 有节点要发送报文，可以立即获取目的节点路由，因此，该路由协议的时延较小， 但是协议需要大量的路由控制报文，开销较大，占用较多的网络带宽。而且，在 网络规模( 节点数目) 和移动性( 网络拓扑变化速率) 增大到一定程度时，大部 分表驱动路由协议的效率将急剧下降。 下面，我们通过介绍一种典型的先应式路由协议刈l s r ，来了解一下先应 式路由协议的工作机理。 2 1 2o l s r 路由协议 2 1 2 1o l s r 协议的基本原理和优势 o l s r ( o p t i m i z e dl i n ks t a t er o u t i n g ) 【3 】称为优化链路状态路由协议，是针对 无线自组织网络的特点对传统的纯链路状态协议进行优化得到的先应式路由协 议，其核心概念是多点中继( m p r ，m u l t i p o i n tr e l a y s ) 。节点n 的m p r 集是其一 跳邻居节点集合的子集，该集合能够覆盖节点n 的所有两跳邻居节点。 第6 页 国防科学技术大学研究生院丁学硕十学位论文 o l s r 协议主要从两个方面进行了优化，从而大大减小了路由控制丌销。第一， 当节点广播链路状态信息时，只有属于其m p r 集合的结点再次进行广播，不属于 m p r 集合的结点只需对报文进行相应处理而不必广播，减少了同一区域中的冗余 重传；第二，节点在广播链路状态时只需通报节点与其m p r 集合节点间的链路， 而不是与其全部邻居结点间的链路。 节点n 的邻居集合n e i g h b o r ( n ) 由那些与节点n 拥有双向链路的一跳节点组 成。节点n 的多点中继集m p r ( n ) 是n e i g h b o r ( n ) 的任意子集且满足以下条件：n 的每个两跳邻居节点都必须拥有到达m p r o x l ) 中节点的双向链路。m p r 集越小， 协议获得的优化越多，图2 1 表示了节点n 的m p r 节点。 r 7 、 囝 r e t r a n s m i t t i n g n o d e s o r m u l t i p o i n tr e l a y s 图2 1 节点n 的多点中继【3 1 多点中继集合m p r ( n ) 覆盖了节点n 的全部两跳邻居节点，从而，在完成一 遍广播后，网络中每个节点都能获得关于整个网络的拓扑信息，并将之存在一个 拓扑表罩，根据拓扑表和邻居结点表，节点就可以计算出到达每个节点的最优( 按 跳数) 路由。 2 1 2 2m p r 集构造 在o l s r 协议中，m p r 集的构造是一个关键问题，在很大程度上影响着协议 的性能。节点n 的m p r 集合是n 的一跳邻居节点的子集，覆盖了n 的全部两跳 邻居节点，也就是说，节点n 的m p r 集合的邻居节点集要包含其两跳邻居节点集。 节点n 通过它接收到的h e l l o 报文，可以获得与自己存在双向链路的节点表， 从而在本地构建两跳节点表，然后，就可以构造m p r 集了。在选择节点n 的多点 中继时，可以按照以下算法进行。 1 节点n 的一跳邻居集合中每个节点x ，计算出自己的度( d e g r e e ) ：d ( x ) = 节 点x 的一跳邻居节点数量，并将该值通报给节点n ； 第7 页 国防科学技术大学研究生院下学硕十学位论文 2 如果节点n 的一跳邻居节点集合中的节点x 提供到达n 的两跳邻居节点集 合中某个节点的唯一路径，那么把x 选择为n 的一个m p r ； w h i l e ( n 的两跳邻居集合中还有节点没有被a 的m p r 集中的节点所覆盖) b e g i n 找出能够覆盖节点n 尚未被覆盖的两跳邻居最多的一跳邻居节点y ； i f i 这样的节点y 不只一个) t h e n 选择度( d e g r e e ) 较大的节点作为m p r ； e l s e 把y 添加到m p r 集； e n d 3 在节点n 的一跳邻居表中，把选为m p r 的邻居节点的链路状态标记为m p r 。 这样，一个节点的m p r 集就构造完毕了。 o l s r 协议是一种最短路径路由协议，路径上的中间节点由m p r 组成。相对 于其它的先应式路由协议，o l s r 能够有效的降低因链路状态信息的广播带来的开 销，然而，随着网络规模的增大，路由造成的开销和因路由计算带来的计算量仍 然是m a n e t 这种资源有限的网络难以容忍的。 2 2 反应式路由协议 2 2 - 1 反应式路由协议简介 反应式路由协议( r e a c t i v er o u t i n gp r o t o c 0 1 ) 又称为随选型路由协议或者按需 路由协议，是专门针对m a n e t 环境提出来的。与表驱动路由协议不同，该类协 议并不事先生成全部路由，而是仅在源节点需要时才去建立相应路由，也就是说， 节点路由表的信息是按需建立的，它可能仅仅是整个拓扑结构信息的一部分。按 需路由一般包括两个阶段，路由发现和路由维护。该类型中各路由协议的差别主 要表现在发现路由的过程、取得和维护路由信息的方法、传输数据的方式。主要 包括a o d v 、d s r 和a b r 等协议。 相比先应式路由协议，按需路由协议不需要周期性维护尚未用到的路由，只 有在有数据发送时才需要获取路由，因此，产生的路由控制信息比先应式路由协 议要少得多。但因为数据传输之前必须先获取路由，所以存在一定的启动时延。 按需路由协议适用于网络载荷不太重、节点移动速度不太大的场合。 a o d v 是一种最常用的反应式路由协议，该协议灵活、简洁，比较适合在移 动自组织网络中应用，接下来我们将详细的讨论一下这种路由协议的工作原理， 并对其优缺点作出评价。 2 2 2a o d v 路由协议 第8 页 国防科学技术大学研究生院工学硕士学位论文 a o d v 协议( a dh 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 ) 1 6 j 是一种典型的按 需路由协议，实质上是d s r 和d s d v 的结合，它继承了d s r 的路由发现机制和 d s d v 的逐跳路由、序列号等机制，集成了二者的优点，无论在延迟和协议开销 方面，还是在计算资源的消耗上，都优于一般的路由协议。 2 2 2 1a o d v 路由协议的报文格式 在a o d v 协议规范里，定义了四种报文：r r e q ( r o u t er e q u e s tm e s s a g e ，路由 请求报文) ，r r e p ( r o u t er e p l ym e s s a g e ，路由响应报文) ，r e r r ( r o u t ee r r o rm e s s a g e ， 路由错误报文) ，r r e p a c k ( r o u t er e p l ya c k n o w l e d g m e n tm e s s a g e ，路由响应确认报 文) 。a o d v 利用这四种报文实现了路由发现和维护的功能。 1 路由请求报文r r e q 当某结点要发送数据时，如果当前路由表中没有到目的结点的路由，那么该 结点通过广播r r e q 报文来发起一个路由请求，该报文包含源结点和目的结点的 地址和序列号，当某个结点接收到这个报文，首先在本地建立一个指向源结点的 路由( 一般称为反向路由) ，然后将报文中的目的地址字段和目的结点序列号字 段同r r e q 报文相应字段进行对比，如果满足条件( 当前结点即为目的结点或当 前结点中含有到达目的结点的路由并且其序列号不小于r r e q 中的目的结点序列 号) ，则向发起路由请求的源结点发送响应报文。a o d v 协议r r e q 报文格式如 图2 2 所示。 o123 o1234567890l2345678901234567 890l t y p e j i i 4dd | u | r e s e r v e d h o pc o u n t r r e qi d 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 en u m b e r o r i g i n a t o ri pa d d r e s s o r i g i n a t o rs e q u e n c en u m b e r 图2 2a o d v 协议r r e q 报文格式1 6 1 2 路由响应报文r r e p 结点响应r r e q 报文时，会向路由请求发起结点发出一个r r e p 报文。这个 报文是单播报文，它会沿着刚建立的反向路由传播，最终由源结点接收。收到一 个r r e p 报文时，结点会在本地建立一个指向路由请求的目的结点的路由，接下 来判断当前结点是否是发起路由请求的源结点，如果不是，则将r r e p 报文转发 出去。如果当前结点即为请求发起结点，那么此时就得到了一条源结点和目的结 点之间的双向路由。a o d v 协议r r e p 报文格式如图2 3 所示。 第9 页 国防科学技术大学研究生院丁学硕十学位论文 0l 23 o1234567890l23456 7890l2345678901 t y p e 刊刽 r e s e r v e dp r e f i xs z h o pc o u n t 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 en u m b e r o r i g i n a t o ri pa d d r e s s l i f e t i m e 图2 3a o d v 协议r r e p 报文格式【6 1 3 路由错误报文r e r r 当结点发现某条链路出现故障，并导致该结点的邻居结点的某些路由变得不 可达时，那么该结点将向相关邻居结点发出一个r e r r 报文。a o d v 协议r e r r 报文格式如图2 4 所示。 结点在三种情况下会发出一个r e r r 报文： ( 1 ) 结点在发送数据时检测到路由表中一个活跃路由的下一跳的链路出现故 障，且未得到成功修复； ( 2 ) 结点收到了一个数据报文，但是结点路由表中不存在到报文目的结点的 活跃的路由或正在修复的路由； ( 3 ) 结点从其邻居接收到一个r e r r 报文，通过分析该报文发现本地路由表 中的某个或某些活跃路由出现不可达现象。 o123 o12345 67890l2 34567890l2345678901 t y p en r e s e r v e d h o pc o u n t u n r e a c h a b l ed e s t i n a t i o ni pa d d r e s s ( 1 ) u n r e a c h a b l ed e s t i n a t i o ns e q u e n c en u m b e r ( 1 ) a d d i t i o n a lu n r e a c h a b l ed e s t i n a t i o ni pa d d r e s s e s ( i fn e e d e d ) a d d i t i o n a lu n r e a c h a b l ed e s t i n a t i o ns e q u e n c en u m b e r s ( i fn e e d e