（计算机应用技术专业论文）基于链路可靠性的ad+hoc网络路由协议研究.pdf

重庆邮电大学硕士论文 摘要 摘要 a dh o c 网络由于其动态网络拓扑和高抗毁性，被广泛应用于军事、消 防、安全、救援和会议等场合，随着a dh o c 网络应用范围的逐渐扩大， 人们希望能将a dh o c 网络融入到现有的无线网络中来，形成一个统一的 网络。在a dh o c 网络中，由于其网络结构与传统网络有很大差别，使得 路由技术成为一个关键的问题。针对a dh o e 网络的特点，人们虽然提出 了一些路由协议，如d s d v 、d s r 、a o d v 和t o r a 等，但它们都存在一 些不足。目前a dh o c 网络的路由技术仍处于发展研究之中，还没有形成 成熟的协议标准。现有的路由协议在可靠性和稳定性存在的问题使得协议 的适应能力和网络吞吐量比较低，不能很好适应a dh o c 网络进一步发展 的需要。 路由失效是导致路由协议可靠性下降的一个主要因素，同时路由失效 必然引起路由再发现和数据重传，这无疑增加了网络的开销和传输的时 延。针对这个问题，论文在随机移走( r a n d o mw a l k b a s e d ) 模型的基础 上，对a dh o c 网络链路通信的可靠性进行了分析，给出链路可靠性的简 单数学模型，并结合a o d v 路由协议实现了基于链路可靠性的自适应路由 算法l r b a ( l i n kr e l i a b i l i t yb a s e da o d v ) 。改进协议将链路可靠性作为 路由选择以及更新的参数之一，可根据网络拓扑的动态变化，选择具有较 高可靠性的路由来传输数据，从而提高了协议的可靠性。 为了验证l r b a 算法的可行性和性能，论文采用o p n e t 网络仿真工 具对改进协议进行了仿真验证。通过在o p n e t 中搭建仿真平台，将l r b a 和a o d v 协议在不同的仿真场景中进行了对比实验。实验结果表明：改进 算法l r b a 能够有效减少路由错误出现的概率，降低系统的传输时延和分 组丢弃数目，在抑制路由失效上取得了较好的效果。 关键字：a dh o c 网络，路由算法，随机移走( r a n d o mw a l k ，b a s e d ) ，链路 可靠度 重庆邮电大学硕士论文摘要 a b s t r a c t d u et oi t s d y n a m i cn e t w o r kt o p o l o g y a n dr e m a r k a b l e a b i l i t y o f d e s t r u c t i o nr e s i s t a n c e ，a dh o cn e t w o r k sa r eu s e dw i d e l yi nm a n yf i e l d ss u c h a sm i l i t a r y ，p u b l i cs e c u r i t y , d i s a s t e rr e s c u e ，e x t e m p o r a n e o u sm e e t i n ga n ds o o n w i t ht h es c o p eo fa p p l i c a t i o no fa dh o cn e t w o r k sg r a d u a le x p a n d i n g ，i ti s h o p e dt h a tt h ea dh o cn e t w o r kc a nj o i nt ot h ee x i s t i n gw i r e l e s sn e t w o r kt o f o r mau n i t e dn e t w o r k b e c a u s eo fg r e a td i f f e r e n c ei nn e t w o r ka r c h i t e c t u r e b e t w e e na dh o cn e t w o r ka n dt r a d i t i o n a ln e t w o r k s ，r o u t i n gt e c h n o l o g yh a s b e e nak e yi s s u ei na dh o cn e t w o r kr e s e a r c h a l t h o u g hp e o p l em a d es o m e r o u t i n gp r o t o c o l ss u c ha sd s d v ，d s r ，a o d va n dt o r a ，t h e r e i sn os t a n d a r d f o ra dh o en e t w o r k sy e t f o rt h ep r o b l e m so fr e l i a b i l i t ya n ds t a b i l i t yi n e x i s t i n gr o u t i n gp r o t o c o l s ，t h ea d a p t a b i l i t ya n dt h r o u g h p u to fn e t w o r k si s r e l a t i v e l yl o w , w h i c hr e s t r i c tt h ea p p l i c a t i o no fa dh o cn e t w o r k s r o u t i n gf a i l u r ei s am a j o rf a c t o rt od e c r e a s et h er e l i a b i l i t yo fr o u t i n g p r o t o c o l s ；o t h e r w i s et h ef a i l u r ec o u l dl e a dt or o u t i n gr e d i s c o v e ra n dd a t a r e t r a n s m i s s i o n ，t h i sw i l li n c r e a s et h et r a n s m i s s i o nc o s t sa n dt h ed e l a yo f n e t w o r k s t os o l v et h ei s s u e ，o ut h eb a s i so fr a n d o mw a l k b a s e dm o d e l ，t h i s p a p e ra n a l y s e sl i n kc o m m u n i c a t i o nr e l i a b i l i t y ，p r e s e n t sas i m p l em a t h e m a t i c a l m o d e lo fl i n kr e l i a b i l i t yo fa dh o cn e t w o r k sa n dg e t sal i n kr e l i a b i l i t yb a s e d a d a p t i v er o u t i n gp r o t o c o l ：l r b ab yi n t e g r a t e dt h ep r o p o s e dm o d e lw i t h a o d va l g o r i t h m u n d e rt h ed y n a m i cn e t w o r kt o p o l o g yc h a n g e s ，t h ea d a p t e d a l g o r i t h mc h o o s e st h ep a t hw i t hh i g hr e l i a b i l i t yo ft h et r a n s m i s s i o no fd a t at o r o u t i n g ，t h e r e b ye n h a n c i n gt h er e l i a b i l i t yo ft h ep r o t o c 0 1 t ov e r i f yt h ef e a s i b i l i t ya n dp e r f o r m a n c eo fl r b aa l g o r i t h m ，t h i sp a p e r i m p l e m e n t sl r b ar o u t i n ga l g o r i t h mi no p n e t n e t w o r ks i m u l a t i o nt o o l s b y p u tu ps i m u l a t i o np l a t f o r m ，t h ep a p e rc o m p a r e st h ep e r f o r m a n c eo fl r b a t o a o d v s i m u l a t i o nr e s u l t ss h o wt h a tl r b aa c h i e v e sab e t t e rp e r f o r m a n c ei n r e s t r a i n i n gr o u t i n gf a i l u r eb yr e d u c i n gt h ep r o b a b i l i t yo fr o u t i n ge r r o r s ，t h e t r a n s m i s s i o nd e l a ya n dt h en u m b e ro fp a c k e t sd r o p p e d k e yw o r d s ：a dh o en e t w o r k ，r o u t i n ga l g o r i t h m ，r a n d o mw a l k b a s e d ，l i n k r e l i a b i l i t y 1 1 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及 取得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论 文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得重廑 邮虫盍堂或其他教育机构的学位或证书而使用过的材料。与我一同工作 的同志对本研究所做的任何贡献均已在论文中作了明确的溅明并表示谢 意。 学位论文作者签名；尊百名公签字日期：幺1 年占月z 日 学位论文版权使用授权书 本学位论文作者完全了解重废业皇太堂有关保留、使用学位论 文的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘， 允许论文被查阅和借阅。本人授权重庆邮电盔堂可以将学位论文的 全都或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等 复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：茵可凇 签字日期：。唧年6 月2 日 导师签名：0 1 宴生 签字日期：2 “年b 月2 日 重庆邮电大学硕士论文 第一章绪论 第一章绪论 随着信息技术的不断发展，人们对移动通信的需求越来越强。近年来， 移动通信技术得到了飞速发展和普及，新技术不断涌现。蜂窝移动通信系 统的发展历程就是最有力的证明。短短十几年时间，它就完成了从第一代 到第二代和二代半的跨越，第三代系统也已初步成熟。此外，无线局域网、 蓝牙( b l u e t o o t h ) 等移动通信新技术也纷纷涌现。使得人们渴望已久的 “任何人”( a n y o n e ) 在“任何时间”( a n y t i m e ) 、“任何地点”( a n y w h e r e ) 进行“任何形式”( a n y t h i n g ) 的信息交换成为了可能。这些技术让人与人 这问的通信变得更加方便快捷，也使人们的生活变得更加丰富多彩。 目前，无线网络根据其结构可分为有中心网络( i n f r a s t r u c t u r e n e t w o r k ) 和无中心网络( i n f r a s t r u c t u r el e s sn e t w o r k ) 。我们经常提及的移动通信技 术一般都是针对集中式控制的有中心网络。它们通常要基于预先架设的网 络基础设施才能运行。例如，蜂窝移动通信系统【2 】要有基站和移动交换中 心等功能设施的支持；无线局域网w l a n 列一般也工作在有接入点( a c c e s s p o i n t ) 和有线骨干网的模式下。这些系统可以有效地利用现成的基站等基 础设施，在基站的覆盖范围内方便地实现数据通信。但这种方式存在的主 要问题是建网成本高，建设周期长。 无中心网络如移动a dh o e 网络【4 i 和智能传感器网络p j ，它们都是一个 由自组织节点或终端组成的集合，这些节点或终端相互通信构成了一个多 跳无线网络，分布式地维护网络的连接性。在本论文中讨论的a dh o c 网 络主要是指移动a dh o e 网络。 由于不需要有中心网络结构的支持，a dh o e 网络在很多有中心网络 技术并不能胜任的场合得到了广泛的应用。比如，战场上部队的快速展开 和推进，发生地震或水灾等大型灾害后的营救，野外科考，偏远地区自然 环境监测作业以及临时性组织的大型会议等。在这些场合中，通信不能依 赖于任何预先架设的网络设施，或预先架设的网络基础设施已经因损毁而 失去效用，而a dh o e 网络的分布式控制方式，动态拓扑结构、快速的组 网能力和网络抗毁性极大地满足了上述特殊环境中的通信需求，也正是这 些应用的需求才推动了a dh o e 网络技术的不断发展。 重庆邮电大学硕士论文第一章绪论 1 1a dh o e 网络概述 a dh o c 网络是一种特殊的无线移动通信网络。a dh o e 网络中所有节 点的地位平等，无需设置任何中心控制节点，具有很强的抗毁性。网络中 的节点不仅具有普通移动终端所需的功能，而且具有报文转发能力。当通 信的源节点和目的节点不在直接通信范围之内时，它们可以通过中间节点 转发报文进行通信。有时节点间的通信可能要经过多个中间节点的转发， 即报文要经过多跳( h o p ) 才能到达目的地，这是a dh o e 网络与其他移动 通信网络的最根本区别。a dh o c 网络的节点通过分层的网络协议和分布 式算法相互协调，实现网络的自动组织和运行因此它又被称为多跳无线 网( m u l t i h o pw i r e l e s sn e t w o r k ) 、自组织网络( s e l f - o r g a n i z e dn e t w o r k ) 或无固定设施的网络。 1 1 1a dh o e 网络的产生 a dh o c 网技术首先主要用于军事移动通信领域，其前身是分组无线 网( p a c k e tr a d i on e t w o r k ) 。对分组无线网的研究源于军事通信的需要。 早在1 9 7 2 年，美国d a r p a ( d e f c n s e a d v a n c e dr e s e a r c hp r o j e c t a g e n c y ) 就启动了分组无线网( p r n e t ，p a c k e tr a d i on e t w o r k ) 项目，研究分组无 线网在战场环境下数据通信中的应用。之后，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 en 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 a lm o b i l ei n f o r m a t i o ns y s t e m s ) 项目，对能够满足军事应用需求的、可快速展开、高抗毁性的移动信息系 统进行全面深入的研究。1 9 9 6 年是美国国防部提出了j t r s ( 联合战术无 线网系统) ，主要应用于美军师、旅及旅以下作战部队构建联合战术无线 通信系统。i e e e 8 0 2 1 1 标准委员会采用了“a dh o e 网络”一词来描述这 种特殊的自组织、对等式、多跳无线移动通信网络，a dh o e 网络就此诞 生。i e t f 则将a d h o e 网络称为移动a d h o e 网络( m a n e t ，m o b i l e a d h o c n e t w o r k ) 。 重庆邮电大学硕士论文 第一章绪论 i i 2a dh o c 网络的特点 a dh o c 网络中，每个移动终端具备路由器和主机两种功能：作为主 机，终端需要运行面向用户的应用程序；作为路由器，终端需要运行相应 的路由协议，根据路由策略参与分组转发和路由维护工作。由于终端的无 线传输范围有限，两个无法直接通信的终端节点往往会通过多个中间节点 的转发来实现通信。a dh o c 网络同时具备移动通信网络和计算机网络的 特点，可以看作是一种特殊的移动计算机网络。图1 1 为一个典型的a dh o c 网络。图中，终端a 和终端j 无法直接通信，但可以通过路径 a 付b 付f 付g j 进行通信。 图1 i典型的a dh o e 网络结构 a dh o c 网络具有以下特点 6 1 ： ( 1 ) 独立组网。a d h o e 网络的布设无需依赖于任何预先架设的网络 设施，节点开机后可以快速、自动地组成一个独立的网络。 ( 2 ) 无中心。a dh o c 网络采用无中心结构，所有节点的地位平等， 组成一个对等式网络，其中的节点可以随时加入和离开网络，任意节点的 故障不会影响整个网络的运行。具有很强的抗毁性。 ( 3 ) 自组织。a d h o c 网络没有严格的控制中心，所有节点通过分层 的网络协议和分布式算法协调各自的行为。 ( 4 ) 多跳路由。由于节点发射功率的限制，节点的覆盖范围是有限 的，当要与其覆盖范围之外的节点进行通信时，需要中间节点的转发，即 采用多跳。与普通网络中的多跳不同，a dh o c 网络中的多跳路由是由普 通节点共同协作完成的，而不是由专用的路由设备( 如路由器) 完成的。 另一方面，使用多跳路由，节点可以降低其发射功率，从而达到节省电能、 重庆邮电大学硕士论文第一章绪论 延长电池工作时间的目的。 ( 5 ) 动态拓扑。a dh o c 网络中，移动终端能够以任意可能的速度和 移动模式移动，并且可以随时关闭和开启电台，加上无线发射装置的天线 类型多种多样、发射功率的变化、无线信道间的相互干扰、地形和天气等 综合因素的影响，移动终端间通过无线信道形成的网络拓扑随时可能发生 变化，而且变化的方式和速度都难以预测。网络拓扑的变化主要体现为节 点和链路的数量及分布的变化。 ( 6 ) 特殊的无线信道特征。a dh o c 网络采用无线传输技术，由于无 线信道本身的特性，其网络带宽要比有线信道的低得多。考虑到竞争共享 无线信道产生的冲突、信号衰减、噪音和干扰等因素，移动终端所获得的 实际带宽远远小于理论上的最大带宽。 ( 7 ) 移动终端的局限性。移动终端具有携带方便、轻便灵活等优点， 但也存在其固有缺陷，如能源受限、内存较小、c p u 处理能力较低和成本 较高等。 ( 8 ) 安全性差。a dh o c 网络是一种特殊的无线移动网络，由于采用 无线信道、有限电源、分布式控制等技术，它更加容易受到被动窃听、主 动入侵、拒绝服务等网络攻击。另外，a dh o c 网络由节点自身充当路由 器，不存在命名服务器和目录服务器等网络设施，也不存在网络边界的概 念。这就使得a dh o c 网络中的安全问题非常复杂。 1 1 3a dh o c 网络与现有无线网络的对比 由于a dh o c 网络的特殊性使得其在体系结构、网络组织、协议设计 等方面都与现有的无线通信系统( 如蜂窝移动通信系统和无线局域网) 有 着显著的区别l ，j 。 蜂窝移动通信系统的网络基础设施包括基站、基站控制器、移动交换 机以及相关的中继链路等。这种网络的架设周期较长，网络维护和管理需 要耗费相当多的人力、物力。而a dh o e 网络不需要固定网络设施的支持 就可以独立组网，部署速度要快得多。在蜂窝移动通信系统中由于设备 故障等原因也会导致网络结构出现变化，但总的来讲，网络结构比较稳定。 而在a dh o c 网络环境下，网络的拓扑结构是动态变化的。 在无线局域网中，移动节点一般通过接入点( a p ) 连接到固定网络， 从网络层的角度看，无线局域网是一个单跳网络，而a dh o c 网络则是一 个多跳网络。无线局域网的研究内容主要集中在物理层和数据链路层，而 重庆邮电大学硕士论文第一章绪论 a dh o e 网络的研究内容覆盖了协议的所有层。表1 1 列出了a dh o c 网络 与现有无线网络的主要区别。 表1 1 a dh o e 网络与现有无线网络的主要区别 现有无线网络 a dh o e 网络 无线网络结构 有中心，单跳无中心，多跳 拓扑结构 固定动态建立，灵活变化 有无基础设施支持有 无 安全性和服务质量较好较差 配置速度慢快 生存时问长短 路由选择与维护 容易困难 网络健壮性低 高 研究重点物理层和链路层 协议的所有层 中继设备基站和有线骨干网 无线节点和尤线骨干网 基站有多部收发信机，全双工方式通 节点通常只有一部收发信机，半双 中继节点的特性 工方式工作，不易实现拿网同步 信，有专用硬件，易于实现全网同步 无线节点的由基站集中负责，无线节点 由节点本身负责， 控制管理通过基站与目的节点通信 通常采用分布式方式 1 2 相关研究背景 由于a dh o e 网络的动态拓，再加上传输的多跳性和无线信道不可靠 性，随着网络规模的增大，网络中用于计算路由的开销将变得难以控制。 常规路由协议不能满足a dh o c 网络的需要，这使得路由协议成为了a d h o c 网络研究的一个重要方向。a dh o c 网络中节点的移动性和节点状态等 不确定因素造成网络在某些时刻会发生分割( n e t w o r k p a r t i t i o n ) 哺j ，从而 中断节点间的链路，而组成路由的任何一条链路的失效都将导致该路由的 失效。路由失效将会给协议性能带来严重的影响，主要包括如下的方面： ( 1 ) 路由失效往往也意味着多次的链路层重传或者网络层重传、传 输层重传甚至应用层重传，这些重传在造成网络开销的同时也增加了业务 的传输延迟。 ( 2 ) 发现路由失效的节点需要向源节点发送路由错误消息，如果源 重庆邮电大学硕士论文 第一章绪论 节点并不存在到达目的节点的另外一条路由，则需要发起新的路由发现过 程。路由发现过程的路由请求泛洪是协议开销的一个重要组成部分，同时 发送路由错误和等待路由发现的过程将会造成业务传输延迟的巨大抖动。 大的延迟抖动对于某些实时业务( 如l i v ea u d i o 、l i v ev i d e o 等) 来说是 不能接受的1 9 】。 ( 3 ) 在路由错误消息到达源节点之前，源节点会继续通过这条已经 失效的路由发送业务分组，而这些业务分组会被存放在发现路出失效的节 点的缓冲区内，如果节点的缓冲区溢出或者该节点并没有包含在新发现的 路由中则这些分组就会被丢弃。此外，源节点在发送了路由请求而尚未收 到路由应答的过程中也会将业务的分组放在缓冲区内，如果缓冲区溢出同 样也会导致分组的丢失。 ( 4 ) 分组丢失对于不响应( u n r e s p o n s i v e ) 业务( 如u d p ) 来讲，可能造 成数据传输的不完整：而对响应( r e s p o n s i v e ) 业务( 如t c p ) 来讲，将会造成 源端的发送窗口降低，大大影响t c p 的吞吐率和网络利用率i l 。 在现有的大多数a dh o e 按需路由协议中，路由发现仅根据路由的 f r e s h 程度和路由跳数等参数进行路由选择如a o d v i l ，这在很大程度上 增加了使用不可靠路由的概率；路由维护都是在发现路由失效后才进行路 由维护如a o d v 、d s r 1 2 ，在路由维护过程中，节点需要向业务的源节点 发送路由错误，然后由源节点进行路由切换或者发起新的路由发现过程。 在这段时间内，分组被缓冲并且可能被丢弃，这将在很大程度上降低协议 的性能和网络的吞吐率。 由于而路由失效将会对协议的性能和网络服务质量造成非常不利的 影响，虽说使用泛洪可以提高数据分组到达目的节点的成功率，但是这样 带来的开销也会非常大。如何尽量避免路由失效是a dh o c 路由协议研究 中一个相当重要的组成部分。针对上述问题，人们提出了一些路由协议来 避免路由失效： r o h i td u b 等提出了一种使用链路状态的协议s s a ( s i g n a ls t a b i l i t y b a s e da d a p t i v er o u t i n g ) f ”】。s s a 是基于信号强度的自适应路由协议， 该协议旨在选择连接性最强的路由。s s a 由两个互相合作的协议构成：动 态路由协议( d r p ) 和静态路由协议( s r p ) 。d r p 负责维护信号稳定度表 ( s s t ) 和路由表( r t ) ，s s t 记录邻节点的信号强度。信号强度通过接 收链路层发出的周期性信标获得，s s a 将信号强度作为选择路由、确定路 由的生存期的唯一参数。 w i l l i a mw e i l i e ns u 提出了一种基于移动预测的面向流的路由协议 6 重庆邮电大学硕士论文 第一章绪论 f o r p ( f l o wo r i e n t e dr o u t i n gp r o t o c 0 1 ) i “j ，它根据节点的移动预测相邻 节点间链路的有效期l e t ( l i n ke x p i r a t i o nt i m e ) ，传输路径上各l e t 的 最小值决定了该路径的有效期r e t ( r o u t e e x p i r a t i o n t i m e ) 。目的节点选 择r e t 最大的作为路由，当r e t 快到时提前重构路由。但是节点移动速 度提高将使l e t 减小，从而减小了r e t 。因此算法在节点高速移动时会 产生路由的不断重构。 文献【1 5 】提出了一种基于拓扑预测的路由算法，该算法利用e l m a n 递归 神经网络模型对a dh o c 网络节点间的跳数进行预测，从而预测节点的移 动和网络拓扑结构的变化。但该算法实现较复杂只适用于小规模网络，此 外，在节点高速移动时其预测误差较大。 一些协议也采用多路径的方法来消除不准确路由的影响，协议在路由 发现过程中能搜索多条路径并选择其中一条作为路由传输数据，其余则作 为备份路由加以缓存。在路由失效后，协议直接从备份路由中选取新路由。 如t b p ( t i c k e t b a s e dp r o b i n g r o u t i n gp r o t o c 0 1 ) 1 6 1 ，它使用基于“票”的 方式来探询多条路由，票的数量表示可能获得路径的最大数目。但是采用 多路径方法，系统要维护的路由数也随之增加，协议开销较大。 1 3 课题研究内容 本课题来源于重庆市科委攻关和自然科学基金项目“支持4 g 的无线 网络资源预分配及优化技术研究”。该项目研究具有q o s 保障的4 g 系统 动态资源预分配、任务调度理论以及适合4 g 系统中传感器网络的路由协 议。在参加该项目的背景下，本论文针对a dh o e 网络路由失效的问题进 行了研究，主要的研究内容为： ， 对a dh o e 网络进行了研究，详细研究了移动a dh o e 网络的定义、 主要功能和体系结构以及当前存在的主要技术问题和与之相适应 的网络路由协议所要达到的主要目标。 对目前a d h o e 网络的路由协议进行了研究，广泛参考并比较了多 种a dh o c 网络路由协议之后，选取a o d v 协议作为工作协议， 从节点闻通信链路可靠性的角度对a o d v 协议进行了改进，得到 了基于链路可靠性的自适应路由算法：l r b a 。 学习o p n e t 网络仿真软件的使用，利用o p n e t 搭建网络仿真平 台，并在这个平台的基础上对a o d v 路由协议和改进协议l r b a 进行对比仿真实验。 重庆邮电大学硕士论文第一章绪论 1 4 论文结构 本论文第一章首先对a d h o e 网络进行了简单的介绍，然后介绍了a d h o c 网络研究的主要特点，最后介绍了相关的研究现状和课题的主要内容。 第二章详细介绍了a d h o c 网络的体系结构和a d h o e 网络中的路由协 议，包括a dh o e 网络路由协议的分类、几种典型a dh o e 网络的路由协议， 最后说明了a dh o c 网络路由协议的评价标准。 第三章根据随机移走( r a n d o mw a l k b a s e d ) 模型对a dh o e 网络的节 点运动进行了分析和研究，给出了链路可靠度的简单数学模型。 第四章在a o d v 路由协议的基础上引入链路可靠度模型，实现基于链 路可靠性的自适应路由协议。 第五章搭建仿真平台，对l r b a 协议和a o d v 协议进行对比验证。 第六章总结论文的工作并指出下一步的工作。 重庆邮电大学硕士论文第二章a dh o e 网络的体系结构和路由协议 第二章a dh o e 网络的体系结构和路由协议 2 1a dh o e 网络的体系结构 a dh o e 网络采用分布式控制方式，其节点具有自组织功能。在a dh o e 网络中需要解决的一个关键问题是如何发现、收集和使用拓扑信息来形成 较为合理的网络结构，从而提高网络的性能和业务的服务质量。体系结构 对于网络协议和各功能模块的设计起着至关重要的指导性作用，基于以上 考虑，本章介绍了a d h o e 网络的体系结构及其相关问题。 2 2 1a dh o e 网络的节点结构 i 固 u 路由器 主机 ( a ) 单主机单电台 路由器 主机 路由器 q p 图2 1a d h o e 网络节点的结构 a dh o e 网络的节点不仅要具备普通移动终端的功能，还要具备摄文 转发能力，即具有路由器的功能。因此，就完成的功能而言，可以将节点 分为主机、路由器和电台三部分。主机部分完成普通移动终端的功能，路 由器部分负责维护网络的拓扑结构和路由信息，完成报文转发功能a 电台 部分为信息传输提供无线信道支持。从物理结构上分，节点可以分为以下 几类：单主机单电台、单主机多电台、多主机单电台和多主机多电台，如 图2 1 所示。对于一般的简单节点( 如手持设备) 通常采用单主机单电台 的结构；对于需要在两个或多个网络间互通的中继节点可以采用单主机多 电台的结构；多主机单电台的结构可以运用在复杂的车载设施之上，使一 重庆邮电大学硕士论文第二章a dh o e 网络的体系结构和路由协议 个结点能包含通信车内的多个主机；多电台节点的好处是不仅可以用来构 建叠加( o v e r l a y ) 式的网络，还可以用作网关节点来互联多个a dh o e 网 络以及其他网络。 2 2 2a dh o c 网络的拓扑结构 拓扑可变的网络包含四种基本结构：中心式控制结构、分层中心式控 制结构、完全分布式控制结构和分层分布式控制结构。前两种属于集中式 控制结构不适用于a d h o c 网络，故a d h o c 网络一般采用分布式控制结构， 即完全分布式控制结构和分层分布式控制结构。这两种结构又分别称为平 面结构和分级结构【1 7 1 如图2 2 所示。 o 簇 簇头 簇成员 ( a ) 平面网络结构( b ) 分级网络结构 图2 2a d h o c 网络拓扑结构 平面结构的a dh o e 网络如图2 2 ( a ) 所示。这种网络结构的特点是 比较简单，所有节点在网络控制、路由选择和流量管理上都是平等的，故 又称为对等式结构。这种结构原则上不存在瓶颈，网络比较健壮。源节点 和目的节点之间一般存在多条路径，可以较好地实现负载平衡和选择最优 化的路由 与平面结构不同的是分级结构，在分级结构中，a dh o e 网络被划分 为一到多个簇( c l u s t e r ) 。每个簇由一个簇头( c l u s t e rh e a d e r ) 和多个簇 成员( c l u s t e rm e m b e r ) 构成，所有簇头又形成了更高一级的网络。在商 一级的网络中又可以继续分簇。如图2 3 ( b ) 所示。 重庆邮电大学硕士论文 第二章a dh o e 网络的体系结构和路由协议 2 2 3a dh o c 网络的协议栈 根据a dh o e 网络的特征，参照o s i 的7 层协议模型和t c p i p 的体系 结构，可以将a dh o c 网络的协议栈划分为5 层，如图2 4 所示，其中虚 线框表示可选部分。 数 据 链 路 层 应用层：实时业务、自适应应用、数据业务 ： 移动定位、自动配置，安全策略 ： i ，0 传输层：( w ) t c p 、u d p 、 t： j ：信令协议：( d ) r s v p ，i n s i g n i a： r 霪 网络互联层：i p v 4 ，i p v 6 ，m o b i l ei p 网络层：邻居发现、路由协议 ，一生一， ：分簇： 。一t j r 逻辑链路控制( l l c ) 子层：分组转发确认、差错控制 媒体接入控制( m a c ) 子层：t d m a 、c d m a 、i e e e 8 0 2 1 i r苎竺竽燮一 磊蕊百j 物理层：扩频技术、调制解调、发送接收 反 馈 和 自 适 应 调 节 机 制 图2 4a dh o e 网络通用协议栈结构 在通用协议栈结构中，物理层负责频率的选择、信号的收发和调制解 调、信道的加密解密等。数据链路层中的m a c 子层控制移动节点对共享 信道的访问，l l c 子层负责数据流的复用、数据帧的检测、分组的确认、 优先级排队、差错控制和流量控制等。网络层完成邻居发现、分组路由、 接纳控制、拥塞控制和网络互联功能，其中邻居发现用于收集网络拓扑信 息，路由协议则是用于发现和维护去往目的节点的路由。传输层用于向应 用层提供可靠的端到端服务，特别是当a dh o e 网络需要接入i n t e r n e t 等外 厂iill，iiil 重庆邮电大学硕士论文第二章a dh o e 网络的体系结构和路由协议 部网络时，尤其需要传输层协议的支持。应用层协议用于提供面向用户的 各种应用服务。 2 2 4a dh o c 网络体系结构的设计策略 a dh o e 网络体系结构的设计与i n t e r n e t 有显著区别。i n t e r n e t 的网络 是准静态的，相邻路由器之间的链路速率很高，网络的瓶颈是路由器的处 理能力和存储容量。因此i n t e r n e t 中的网络协议常常通过使用较多的链路 带宽来减少路由器的处理和存储资源，即强调相邻路由器的对等实体之间 的水平方向的通信，而使路由器内协议栈各层之间的垂直通信尽可能少。 但a dh o c 网络中链路的带宽和主机的电源都比较紧缺，能量主要消耗在 发送和接收分组上，主机的处理能力和存储空间相对来说比较充裕，无论 是从节能还是节省带宽来看，都应尽量减少节点间水平方向的通信，通过 增加协议栈各层之间的垂直交互来减少协议层对等实体之间的水平通信， 如图2 5 所示。按照这种方式设计的协议栈中的各层协议在逻辑上是相互 耦合的，各层协议之间垂直通信量的增加使得上下层协议能更好的结合， 从而能够减少不必要的水平通信造成的资源( 带宽和能量等) 浪费。 应用层应用层 、r i i l l i i 1 i i 物理层物理屡 应用层应用层 、， i i i i l i i i i r 物坪层物理层 ( a ) i n t e m e t 协议设计原则( b ) a dh o e 协议设计原则 图2 5 两种网络的体系结构设计原则 从优化性能的角度来看，a dh o e 网络适宜采用专用的封闭式的系统 设计方法；但是从灵活运用的角度来看，a d h o e 网络应该是一个开放的、 可扩展的、支持i p 技术的移动网络。因此，在设计系统体系结构时需要 在网络性能、灵活性以及互操作性上进行合理的折衷，在保证系统具有较 高的灵活性的同时尽量减少系统的开销。 在a dh o c 网络中，随着节点移动，网络拓扑结构在不断变化。如何 - 1 2 重庆邮电大学硕士论文第二章a dh o c 网络的体系结构和路由协议 准确、迅速地选择到达目的节点的路由，是a dh o c 网络中的一个重要的 核心问题。本章详细介绍了a d h o c 网络中的路由协议，包括a d h o c 网络 路由协议的分类、a dh o c 网络路由协议的评价标准，最后详细介绍了几 种典型a dh o c 网络的路由协议。 2 2a dh o c 网络路由协议的分类 目前国内外的研究人员基于各种不同的角度提出了许多针对无线a d h o c 网的路由协议，如：d s d v ( d e s t i n a t i o ns e q u e n c e dd i s t a n c ev e c t o r ) 【1 8 】、 c g s r ( c l u s t e r h e a dg a t e w a ys w i t c hr o u t i n g ) 【l 、a o d v ( a dh o co n d e m a n d d i s t a n c e v e c t o r ) t l l 、d s r ( d y n a m i cs o u r c e r o u t i n g ) 【12 1 、t o r a ( t e m p o r a l l y o r d e r e dr o u t i n ga l g o r i t h m ) 1 2 0 1 、a b r ( a s s o c i a t i v i t yb a s e dr o u t i n g ) f 2 i j 等，其中一部分也提交到m a n e t ( m o b i l ea dh o cn e t w o r k ) 工作小组成 为r f c 草案。 根据路由发现的驱动模式的不同，a dh o c 网络中的路由协议可以大 致可以分为两类：表驱动路由协议( t a b l ed r i v e np r o t o c o l s ) 和按需路由 协议( s o u r c e i n i t i a t e do n d e m a n dp r o t o c o l s ) 【22 1 ，如图2 6 所示。 d s d vw r pa o d vd s rl m ra b r i + c g s rt o r as s r 图2 6a dh o c 网络路由协议按驱动模式的分类 2 3 表驱动路由协议 表驱动路由协议采用周期性的路由分组广播，来交换路由信息。每个 节点维护到达全网所有节点的路由。表驱动路由的优点是当节点需要发送 一个到达其他节点的数据分组时，只要路由存在，发送分组的延时就很小； 重庆邮电大学硕士论文第二章a dh o c 网络的体系结构和路由协议 缺点是表驱动路由协议需花费较高代价( 如带宽、电源、c p u 资源等) ，使 路由表能够跟上当前网络拓扑结构的变化，但动态变化的拓扑结构又可能 使高价得来的路由表中内容变成无效信息，路由协议始终处于不收敛状 态。 2 4 按需路由协议 按需是a dh o e 网络中的一种路由机制，按需路由基于如下的前提： 如果所有的问题和矛盾都可以被监测到，则解决这些问题或者消除这些矛 盾的工作可以被推迟到十分需要的时候。因此，按需路由不使用周期性的 路由信息更新而是仅在需要的时候才进行路由信息的更新。 按需路由主要由路由发现和路由维护两部分组成【2 3 1 。当源节点欲发送 信息到达某个目的节点而路由表中并不存在到达该目的节点的路由时，节 点会通过广播路由请求分组发起一次新的路由发现过程，以发现到达目的 节点的路由。当正在进行通信的路由失效后，节点会通过路由维护过程进 行路由的切换。 2 4 1 路由发现 路由发现的目的在于发现从源节点到达目的节点的路由，源节点通过 广播路由请求分组发起路由发现过程。路由发现过程可以划分为如下几个 子过程：路由请求发送、路由请求转发、路由应答发送、路由应答转发和 路由选择策略。 路由请求发送过程由源节点发起，源节点在欲发送分组到达目的节点 而此时源节点路由表中不存在到达目的节点的路由，源节点就会通过广播 路由请求分组来发起一次新的路由发现过程，如果在一定时间何隔内源节 点没有收到任何的路由应答消息，源节点会尝试再次发送路由请求分组， 如此过程直至到达规定的最大重传次数或者其它的限制条件，即认为此次 路由发现过程失败。 任何中间节点收到路由请求分组后，都应该进行相应的处理。为了防 止同一个节点多次收到同一个路由请求分组并进行多次处理，按需路由机 制需要使用一种策略来处理这种问题，最简单的方式就是使用一个数据结 构，该数据结构中保存了在过去一段时间内收到的路由请求分组的相关信 息，该数据结构以源节点地址和路出请求分组的i d 作为索引。如a o d v 重庆邮电大学硕士论文第二章a dh o c 网络的体系结构和路由协议 使用了b r o a d c a s t l d 链表而d s r 使用了路由请求表来完成上述的功能。如 果节点刚刚收到的路由请求分组是以前没有收到过的，则节点需要添加一 条临时反向路由用来转发将来可能会存在的路由应答。如果为目的节点或 者虽然不是目的节点但是存在到达目的节点的路由，则节点需要根据路由 请求分组携带的信息和已有的路由信息构造并发送路由应答，否则，节点 应该再次转发该路由请求分组。 目的节点在发送路由应答时需要将路