（通信与信息系统专业论文）基于aodv的路径稳定性优化度量研究.pdf

重庆邮电大学硕士论文 摘要 摘要 随着现代无线通信技术和因特网的发展与进步，任何人在任何时间地点都能 够获取信息并与他人通信的要求已经成为人们对现代信息网络的切实要求。由于 a dh o e 网络无需固定基础设施支持，能快速简单组网，而且能够自组织、自修复， 正在成为下一代无线网络的有力竞争者，其所涉及的学术与实用化问题也日益成 为国内外的研究热点。其中路由协议用来建立从源节点到目的节点之间的可达路 径，是数据通讯的前提。鉴于路由协议的重要性，路由协议一直是a dh o c 网络中最 为活跃的研究领域。 动态拓扑是a dh o e 网络的主要特征。拓扑的动态变化引起a dh o e 网络路由 中断频繁，这使得网络性能下降，网络规模扩展受限。寻找稳定路径是减少路由 中断是提高路由动态拓扑适应性的有效手段。现有稳定路径寻找方法存在以下局 限：需要m a c 层将无线信号强度上传到网络层，或需要节点具有地理位置定位的 硬件功能支持。此外大多数稳定路径寻找方法缺乏减少信道竞争和避免数据拥塞 的机制。 在a dh o c 网络中，一方面，存在网络中的无线信道容量和网络拓扑结构等多 种因素的时变性，另一方面，存在节点所面临竞争和拥塞程度的非公平性，这两 个方面的问题将导致网络中的节点难以及时获得全网的拓扑结构。相对而言，局 部拓扑结构会比较容易获取和更新。 本课题充分利用节点的连接性反应局部拓扑结构，并以此为依据建立节点稳 定度尺度。该尺度的获取不需要从底层协议获取接收信号强度，也不需要地理位 置定位硬件功能的支持。这使得该尺度的计算和有关该尺度信息的获取比较容易。 在获取节点稳定度所需的本地连接信息时，本课题利用文献 3 9 】提出的机制。 这种机制的优点是：一方面，节点m a c 层收到任何帧时都可将有关信息传给路由 层以更新路由表项，这使得不用增加额外开销就可以减少h e l l o 消息麴0 另一方 面，将h e l l o 消息的发送和处理机制由原来的路由层控制改为m a c 层控制，缩减 了h e l l o 消息帧的大小。 同时，由于节点稳定度尺度考虑了信道竞争和数据拥塞，通过对节点度的利 用，在不增加系统开销的情况下，使得高稳定度的节点不但面临的信道竞争铰小， 同时还能尽力避免数据拥塞。 在建立了节点稳定度尺度的基础上，本课题建立了路径稳定度度量，并以此 为依据选择路由。依据该度量，协议倾向于选择一条稳定的、信道冲突较少的， 重庆邮电大学硕士论文 摘要 且不易发生数据拥塞的路由。由于路径稳定度度量采用累积法计算，这使得协议 还倾向于选择转发跳数较少的路径形成路由，这也从另一个角度提高了路由的稳 定性和质量。 为了评估基于路径稳定度的路由选择方法对a dh o c 网路由选择的指导意义， 本课题以a o d v 路由协议为基础，利用路径稳定度，对其进行了扩展，我们在根 据文献 3 9 】的机制所扩展的n s 2 仿真平台上，实现改进的a o d v 路由协议： s t a a o d v ( b a s e do nt h es t a b i l i t yo f p a t ha o d v ) ，并设计两种典型的网络场景用 于评估改进后协议的性能。仿真结果表明，与a o d v 路由协议相比，s t a a o d v 路由协议能够有效减小路径的中断次数，降低归一化路由控制开销，提高端到端 分组投递率，降低端到端时延。由此可见，路径稳定度度量的应用可以提高路由 的动态拓扑适应性和网络规模扩展的适应性。 关键字：信道竞争；数据拥塞；局部连接性；节点度；节点稳定度；路径稳 定度 2 重庆邮电大学硕士论文 a b s t r a c t a b s t r a c t w i t ht h er a p i da n de x t e n s i v ed e v e l o p m e n to fw i r e l e s sc o m m u n i c a t i o na n di n t e r a c t ， i th a sb e e ns u b s t a n t i a l l ye s s e n t i a lt oa c q u i r ei n f o r m a t i o na n dc o m m u n i c a t ew i t ho t h e r p e o p l ea ta n y t i m e ，a n y w h e r ea n df o ra n y b o d y t h ea b i l i t yt ob es e tu pq u i c k l ya n d o p e r a t ew i t h o mw i r e di n f r a s t r u c t u r em a k e sa dh o cn e t w o r kap r o m i s i n gc a n d i d a t ef o r n e x tg e n e r a t i o nw i r e l e s sn e t w o r k s r e s e a r c ho na dh o cf r o ms c i e n c ea s p e c tt op r a c t i c a l a s p e c ti sn o w ah o ts p o t r o u t i n gp r o t o c o li su s e dt oe s t a b l i s ht h ep a t hf r o mt h es o u r c e t ot h ed e s t i n a t i o n ，i ti st h ep r e m i s eo fd a t ac o m m u n i c a t i o n ，o w i n gt oi t si m p o r t a n c e ，i t h a sb e e nt h em o s th o ts p o ti nt h er e s e a r c ho f a dh o cn e t w o r k t h ed o m i n a n tf e a t u r eo fm o b i l ea dh o cn e t w o r ki sd y n a m i ct o p o l o g y , w h i c h c a u s e st h er o u t e sb r e a kf r e q u e n t l y , d e c r e a s e st h en e t w o r kp e r f o r m a n c ea n dr e s t r i c t st h e n e t w o r ks c a l a b i l i t yf u r t h e r s e l e c t i n gs t a b l ep a t h si sa ne f f e c t i v ew a yt or e d u c et h e r o u t e sb r e a ka n di m p r o v et h er o u t i n g sa d a p t a b i l i t yt od y n a m i ct o p o l o g y c u r r e n t m e t h o d s o fs e l e c t i n gs t a b l ep a t h si nm o b i l ea dh o cn e t w o r k ss u f f e rf r o ms e v e r a l s h o r t c o m i n g s t h e ym a yn e e dm a cl a y e rf u n c t i o ns u p p o r tf o rs e n d i n gs i g n a ls t r e n g t h i n f o r m a t i o nt ou p p e rl a y e r so rah a r d w a r ef u n c t i o ns u p p o r tf o rg e o g r a p h i c a lp o s i t i o n l o c a t i o n i na d d i t i o n ，m o s tw a y st of i n ds t a b l ep a t ht oi sl a c ko fr e d u c i n gt h ec h a n n e l c o m p e t i t i o na n da v o i d i n g “h o tn o d e si s s u e s ” ( b e c a u s eal a r g ea m o u n to fd a t a t r a n s m i s s i o nt h r o u g has m a l ln u m b e ro fn o d e s ，d a t at r a n s m i s s i o nc o n g e s t i o ni nt h e s e n o d e s ，r e s u l t i n gi nas e r i e so fn e t w o r kp e r f o r m a n c ed e c l i n e ) m e c h a n i s m f o ra na dh o cn e t w o r k , d u et ot h ef r e q u e n t l yc h a n g e dw i r e l e s sc a p a c i t y , n e t w o r k t o p o l o g y , t h et i m e - v a r y i n gc h a r a c t e r i s t i cb e c o m e sa l li m p o r t a n tp r o b l e m i na d d i t i o n , h i d d e nt e r m i n a l ”a n d ”e x p o s e dt e r m i n a l ”p r o b l e m sa r ea n o t h e rw e l l k n o w ni s s u e s ， w h i c ha r ec a u s e db yt h ei n e q u a b l ea w a r e n e s so ft h ew i r e l e s sc h a n n e lf o rd i f f e r e n tn o d e s 1 1 1 et w ob a s i cp r o b l e m sm a k ei tv e r yd i f f i c u l tt oo b t a i na l lt h en o d e s s t a t e sf o ra n yn o d e o ft h en e t w o r k h o w e v e r , t h el o c a ln e t w o r kt o p o l o g yi se a s i l yo b t a i n e da n du p d a t e d i n t h i sd i s s e r t a t i o n ，w ef u l l yu t i l i z et h i si n f o r m a t i o n t h i st h e s i sp r o p o s e st h es t a b i l i t yo fn o d e sm e t r i c sb a s e do nl o c a lc o n n e c t i v i t ya n d l o c a lw h i c hc o u l dr e f l e c tt h en e t w o r kt o p o l o g y a n di td o e sn o tr e q u i r er e c e i v es i g n a l s t r e n g t hc r o s sl a y e rs u p p o r to ra n ys p e c i a lh 盯d w a r es u p p o r t s oi tw i l lb ee a s i e rt o c a l c u l a t et h em e t r i c sa n dg e tt h ei n f o r m a t i o nn e e d e d 3 重庆邮电大学硕士论文 a b s t r a c t i no r d e rt or e d u c et h er o u t i n gc o n t r o lc o s t s ，i nt h ea c q u i s i t i o no fl o c a lc o n n e c t i o n n e e d e db yt h es t a b i l i t yo f n o d em e t r i c s ，t h i st h e s i su s em e c h a n i s m sr a i s e di nl i t e r a t u r e 【3 9 ，w h i c hp r o v i d e sl o c a lc o n n e c t i o ni n f o r m a t i o nb yt h en e wm a c h e l l om e s s a g e i n s t e a do fh e l l om e s s a g e a tt h es a m et i m et h i sm e t h o dc o n s i d e r st h ec o m p e t i n gc o n d i t i o no fe a c hn o d e a l o n gt h er o u t e sa n d “h o tn o d e si s s u e s ”，t h r o u g ht h eu s eo fn o d ed e g r e e ，a tt h e c o n d i t i o no fi n c r e a s i n gs y s t e mo v e r h e a dal i t t l e t h es t a b l en o d ei sa l s o f a c i n g m i n i m u mc o m p e t i t i o na n da v o i d i n g “h o tn o d ep r o b l e m ”a sf a ra sp o s s i b l e o nt h eb a s i so ft h es t a b i l i t yo fn o d em e t r i c s ，t h i st h e s i se s t a b l i s has t a b l ep a t h m e t r i c s t h r o u g hi t ，t h en e wp r o t o c o lc a ns e l e c tt h er o u t ew i t hs m a l ll o c a lc h a n g e 、 m i n i m u mc o m p e t i n ga n da v o i d i n g “h o tn o d e si s s u e s ”f o ra sm u c ha ss t a b l ep a t h m e t r i c su s i n gt h ec u m u l a t i o nm e t h o d ，t h en e w p r o t o c o ls e l e c t sp a t hh a v i n gs m a l lh o p c o u n t sa n ds t a b l el o c a lt o p o l o g i e s i tw i l la l s oi m p r o v et h es t a b i l i t yo fr o u t e i no r d e rt oe v a l u a t et h eg u i d i n gs i g n i f i c a n c eo ft h i sm e t h o df o ra dh o er u o t i n g c h o i c e ，t h i st h e s i sc h o o s e sa o d vp r o t o c o lt oe x p a n da n du s e se x p a n d i n gn s 2 a c c o r d i n gt ot h el i t e r a t u r e 【3 9 】m e c h a n i s ma sam u t i n gp r o t o c o lt e s ts i m u l a t i o nt 0 0 1 w e m e e tt h er e q u i r e m e n t so fi m p r o v e d r o u t i n gp r o t o c o le m u l a t i o nm o d u l e a n dd e s i g nt w o t y p i c a ln e t w o r ks c e n e st oe v a l u a t et h ep e r f o r m a n c eo ft h en e wp r o t o c o l ：s t a - a o d v ( b a s e do nt h es t a b i l i t yo fp a t ha o d v ) ，t h es i m u l a t i o nm s u l t ss h o wt h a tc o m p a r e dt o t h ea o d vp r o t o c o l ，t h en e wp r o t o c o lh a sr e d u c e dt h el o n g - p a t h s b r e a k p r o b a b i l i t y ，l o w e dr e t u r no fr o u t i n gc o n t r o lo v e r h e a d ，i m p r o v e de n d - t o - e n dp a c k e t d e l i v e r yr a t e ，r e d u c e dt h ee n d - t o - e n dd e l a y , a n di m p r o v e dt h en e t w o r kp e r f o r m a n c e i t m e a n st h a tt h en e wm e t h o dc a ni m p r o v et h er o u t i n g sa d a p t a b i l i t yt od y n a m i ct o p o l o g y k e yw o r d s ：c h a n n e lc o m p e t i t i o n ；d a t at r a n s m i s s i o nc o n g e s t i o n ；l o c a ln e t w o r k c o n n e c t i v i t y ；n o d ed e g r e e ；s t a b i l i t yo f n o d e ；s t a b i l i t yo f p a t h 4 重庆邮电大学硕士论文 第一章绪 论 1 1a dh o c 网概述 第一章绪论 随着信息技术的不断发展，人们对移动通信的需求越来越强。近年来，移动 通信技术得到了飞速发展和普及。蜂窝移动通信系统、无线局域网( w i r e l e s sl o c a l a r e a n e t w o r kw l a n ) 、蓝牙技术( b l u e t o o t h ) 、家庭无线网( h o m er f ) 等移动通 信新技术也纷纷涌现。这些技术的出现，极大方便了人们的生活，同时也推动了 无线通信技术的发展。 无线通信网按照其组网控制方式一般分为两类：一类是集中式控制的，即有 中心的。这一类无线网的运行要依赖预先部署的网络基础设施。典型的例子有：蜂 窝移动通信系统，它需要基站，移动交换中心，接入点和有线骨干网等基础设施 的支持。但对于某些特殊场合，不可能有预先部署的固定设施可以利用。比如， 战场上部队的快速展开和推进、发生地震或水灾后的营救、野外科学考察、临时 会议等。在这种情况下，就需要一种能够临时快速自动组网的移动通信技术。这 也形成了另一类无线通信网技术a dh o e 网通信技术【l j 。 “a dh o e 一词来源于拉丁语，意思是“专用的、特定的”。a dh o e 网通常 也可称为“无固定设施网 或“自组织网 。由于组网快速、灵活、使用方便，目 前a dh o c 网已经得到了国际学术界和工业界的广泛关注，并得到越来越厂泛的应 用，已成为移动通信技术向前发展的一个重要方向，并将在未来的通信技术中占 据重要地位。 a dh o e 网的前身是分组无线网( p a c k e tr a d i on e t w o r k ，p r n e t ) 【2 j ，对p r n e t 的研究源于军事通信的需要。早在1 9 7 2 年，美国国防部高级计划研究署( d a r p a ) 就启动了p r n e t 项目，研究战场环境下利用分组无线网进行数据通信。在此之后， d a r p a 于1 9 8 3 年启动了高残存性自适应网( s u r v i v a b l ea d a p t i v en e t w o r k , s u r a n ) 项目，研究如何将p r n e t 的研究成果加以扩展，以支持更大规模的网。 1 9 9 4 年，d a r p a 又启动了全球移动信息系统( 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 ， g l o m o ) 项目，旨在对能够满足军事应用需要的、高抗毁性的移动信息系统进行 全面深入的研究。1 9 9 1 年成立的i e e e8 0 2 1 1 标准委员刽3 】采用了“a dh o c 一词 来描述这种特殊的自组织对等式多跳移动网，a dh o e 网就此诞生。i e t f ( t h e i n t e m e te n g i n e e r i n gt a s kf o r c e ) 1 4 l 专门成立了( m o b i l e a dh o en e r t w o r k ，m a n e t ) 小组【1 】来研究无线a dh o e 网的相关问题。 重庆邮电大学硕士论文 第一章绪 论 与其它传统通信网相比，a dh o e 网具有以下几个特点： 网络的自组织性 相对常规通信网络而言，a dh o c 网最大的特点就是在不需要固定基础网络设 施( 如基站等) 支持的条件下，可以在任何时刻和任何地点，快速构建起一个移 动通信网络。因此，a dh o c 网络有时也称为移动自组织网络( s e l f - o r g a n i z e d n e t w o r k s ) 。它也是个人通信的一种体现形式。 动态变化的网络拓扑结构 在a dh o c 网中，节点可以以任意速度和任意方式在网络中移动，再加上节点 发送功率变化、无线信道干扰、衰落等综合因素的影响，节点间通过无线信道形 成的网络拓扑结构随时可能发生变化。 分布式控制 在常规通信网络中，存在基站、网控中心或路由器这样一类的集中控制设备， 节点与它们的地位是不对等的。a dh o c 网中的每个节点都兼备路由和主机的功能， 不存在一个网络中心控制点，节点之间的地位是平等的。网络路由协议通常采用 分布式控制方式，因而具有较强的鲁棒性和抗毁性。 传输信道基于无线信道，且带宽有限 a dh o c 网采用无线传输技术作为底层通信手段，由于无线信道本身的物理特 性，它所能提供的网络带宽相对有线信道要低得多。同时考虑到竞争共享无线信 道产生的碰撞、信号衰减、噪音干扰、信道间干扰等多种因素，节点可用的实际 带宽远远小于理论上的最大带宽值。 网络安全性较差 a dh o c 网络是一种特殊的无线移动网络，由于采用无线信道，网络的控制方 式多为分布式控制，因此更加容易受到被动窃听、主动入侵、拒绝服务、剥夺“睡 眠 ( 终端无法进入睡眠模式) 、伪造等各种网络攻击。 a dh o c 网的许多优良特性为它在民用和军事通信领域占据一席之地提供了有 利的依据。总的来说，它的应用可以归纳为以下几类： 军事应用 它是a dh o c 网技术的主要应用领域。a dh o c 网技术是数字化战场通信的首 选技术，并已经成为战术互联网的核心技术。 传感器网 传感器的发射功率很小，大量地理分散的传感器通过a dh o c 网技术组成网， 可实现传感器之间以及与控制中心之间的通信，这种网有非常广阔的应用前景。 紧急和突发场合 在发生了地震、洪水、火灾或遭受其它灾难后，固定的通信网设施很可能无 2 重庆邮电大学硕士论文 第一章绪论 法正常工作。而a dh o c 网能够在这些恶劣和特殊的环境下提供通信支持。 偏远野外地区 偏远或野外地区的通信通常无法依赖固定或的网络设施进行。a dh o c 网技术 具有单独组网能力和自组织性，是这些场合实现通信的最佳选择。 临时场合 一些临时场合的通信，如会议、庆典、展览会等，均可以使用a dh o c 网，可 以免去布线和部署网络设备的工作并且快速简单的组网。 个人通信 a dh o c 网技术可以用于个人域网、手机、掌上电脑等个人通信设备之间的通 信，并可以构建虚拟教室和讨论组等崭新的移动对等应用。 商业应用 使用a dh o c 网技术可组建家庭无线网、无线数据网、移动医疗监护系统和无 线设备网，开展移动和可携带计算等。 其它应用 a dh o c 网的应用领域还需要我们进一步去挖掘，如它可以扩展现有蜂窝移动 通信系统的通信模式和覆盖范围，实现地铁和隧道等场合的无线覆盖，实现汽车 和飞机等交通工具之间的通信，用于辅助教学和构建未来的移动无线城域网和自 组织广域网等。 目前a dh o c 网络研究的主要问题包括以下几个方面： 媒体接入控制 主要研究设计具有更高传输速率和通信容量的无线链路媒体接入控制协议， 解决隐终端、暴露终端等问题。 路由协议 针对a dh o c 网的特点，如网络拓扑结构动态变化，信道带宽受限等等，设计 出高效的路由协议。 q o s 保证 研究各种q o s 保证策略，以支持a dh o c 网中各种多媒体业务对q o s 的需求。 低能耗设计 主要包括两个方面的内容：调整移动节点的功率，以便在传输范围和干扰之间 进行折衷；减少节点的电池消耗。 异构网络的互连 研究a dh o c 网络和其它网( 如i n t e r a c t 、蜂窝移动通信网) 的互连互通问题。 安全性问题 在a dh o c 网络中实现保密性、完整性、服务有效性以及鉴权和认证等安全需 重庆邮电大学硕士论文 第一章绪 论 求方面将面临极大的挑战，这是因为节点的移动性给鉴权中心的确定和密钥管理 带来很大困难。 1 2a dh o c 网路由协议概述 由上可知，a dh o c 网是一种多跳对等式无线网络，每个节点同时具有主机和 路由器功能。当源节点不能与目的节点直接通信时，就需要其他一些中间节点通 过存贮转发帮助其完成通信，这样也就构成了多跳网络。从源节点依次经过多个 中继节点到达目的节点就形成了一条通信“路径 ( 路由) 。如何寻找一条合适的 路由就是路由发现问题( 也称路由计算) ；当网络拓扑发生变化时，如何自适应地 调整路由就是路由维护问题。路由计算和路由维护的方法合起来就是路由协议。 路由协议是影响自组网性能的关键，路由协议的好坏直接影响通信业务的各项指 标，影响通信系统资源使用的有效性，它是白组网研究中最重要的问题之一。 1 2 1a dh o c 网路由协议分类 对于已经提出的自组网路由协议，可以从不同的角度进行分类。根据发现路 由的策略，可以将其分为主动式路由协议和按需路由协议。 主动式路由协议( p r o a c t i v ep r o t o c o l s ) 此类协议是有线网络协议的自然扩展。在该类协议中，每个节点都维护一张 或几张到网络中其它节点的信息表。当网络拓扑结构发生变化时，节点通过交互 信息来实时地维护网络路由信息表。典型的主动路由算法有：1 ) 目的序列距离矢 量路由协议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 rr o u t i n gp r o t o c 0 1 ) p 1 ；2 ) 鱼眼状态路由协议f s r ( f i s h e y es t a t er o u t i n g ) 1 6 j ；3 ) 群首网关交换路由协议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 ) 7 1 ；4 ) 无线路由协议w r p ( w n l e s sr o u t i n g p r o t o c 0 1 ) 【8 】等。 被动式路由协议( o nd e m a n dp r o t o c o l s ) 与主动式路由协议相比，在这类协议中，节点并不实时地维护网络路由，只 有在节点有数据发送时，才激活路由发现机制寻找到达目的地的路由。常用的被 动式路由协议有：1 ) 按需距离矢量路由协议a o d v ( a dh o co n d e m a n dd i s t a n c e v e c t o rr o u t i n gp r o t o c 0 1 ) 9 1 ；2 ) 动态源路由协议d s r ( d y n a m i cs o u r c er o u t i n g ) 【1 明；3 ) 临时序列路由算法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 l 】等。 主动型路由继承了传统的距离矢量路由，但在消除路由环路和过期路由等方 面做了适应于自组网特性的改进。节点无论当前是否有数据需要发送，都计算出 4 重庆邮电大学硕士论文 第一章绪论 到所有其他节点的路由，并且周期性地维护、更新这些路由表，以适应网络拓扑 变化。其优点是路由发现无延迟，缺点是有时维护的大部分路由可能没被使用， 造成移动节点存贮和计算的负担，且浪费了大量网络带宽i l2 。在网络拓扑变化较 快时，这些大量交换的控制信息将影响数据信息的传送。主动型路由协议基于路 由表更新机制，其更新间隔对协议性能的影响很大。间隔太大，协议将不能快速 反应拓扑结构的变化；间隔太小，网络可能因充满路由表更新消息而阻塞。当网 络中活动的通信连接数目较大时，该类协议更有效率，因为浪费的路由开销相对 减少，反之则利用率较低。当网络规模和移动性增加( 超过一定的阈值) 时，大 部分主动型路由方案将不再可行，因为仅用于保持与拓扑变化一致而需要传送的 路由更新消息就将消耗大部分的网络容量和节点处理能力。在路由优化策略上， 主动型路由协议关注于如何有效地减少路由更新的周期和频率。 按需路由协议中节点并不维护尚未需要的路由，而且其路由请求应答控制 分组通常比主动型方案中用于路由表更新的分组小，因此所产生的路由控制开销 比主动型协议少得多。在网络的载荷不太重、节点移动速度不太大的情况下，即 使对于非常大型的网络，按需路由协议通常也能显示出低路由开销和低存贮要求 的优点。但是随着移动性的增强，正在传输数据的路由可能会中断，需要再次调 用路由发现过程。在移动性较高和负载较重( 有大量通信连接) 的情况下，路由 高速缓存将变得无效，路由控制开销趋于快速增长。按需路由协议仅在节点有数 据要发送时，才广播路由请求，寻找最佳路由，而不是维护所有路由信息。这样 有效地节省了带宽和内存，但显然是以路由建立时延的增加为代价的，并且考虑 到路由建立过程是靠洪泛方式广播路由信息，这在一定程度上使其优点有所削弱。 1 2 2 本课题优化路由协议的选定 目前存在多种移动a dh o c 网路由协议，针对不同的环境特点它们都有自己的 特点和长处【1 3 l ，没有一种协议在任何场合都是最好的。如何在这么多种协议中选 择出最合适于本课题的协议呢? 这需要在众多移动a dh o c 路由算法之间进行性能 分析和比较，挑选出综合性能最好并且符合本课题要求的算法。要在众多协议中 实现一一的比较对于本课题来说费时费力并不现实，因此课题参考了国外研究人 员在这方面已经完成的工作，以此为依据对几种最流行的a dh o c 网路由算法的性 能进行了比较和分析。 c a r n e g i em e l l o n 大学的j o s hb r o c h 等人【1 4 l 在n s 2 网络仿真工具上开发了模拟 无线移动网的模块，并且在相同的模拟环境下分析和比较了d s d v 、d s r 、t o r a 和a o d v 四种a dh o c 网路由算法的性能。根据他们的仿真结果，j o s hb r o c h 等得 5 重庆邮电大学硕士论文 第一章绪论 出结论：四种算法在一些情况下都能良好的运行，而同时在另一些情况下具有某 些缺点。d s d v 的运行具有相当的可预测性，在节点移动率和移动的速率都不高 ( 暂停时间长) 的情况下几乎可以传输全部的数据包，但随着节点移动性的增加， d s d v 的收敛性却越来越差。t o r a 在四种协议中性能最差，在1 0 至2 0 个数据源 的情况下仍能够传输9 0 的数据包，但随着数据源的增加，t o r a 产生了大量的 路由控制报文，使得网络无法容纳而导致大量数据报文丢失。仿真中在各种移动 率和移动速率情况下d s r 都运行良好，报文发送率在9 5 以上，只是它使用源路 由增加了数据报文的字节数。a o d v 在各种移动率和移动速率的情况下也可以达 到和d s r 几乎相同的效果，并且减少了数据报文的字节数，但它却需要发送更多 的路由控制报文，这需要更多的信道获取，同样需要耗费更多的网络资源。 p e rj o h a n s s o n 等人l l5 】在上面研究成果的基础上又进一步研究d s d v 、a o d v 和d s r 协议的性能。他们仿真了三种不同的真实环境会议环境，事件环境和灾 祸现场环境。会议环境下节点具有较低的移动率。事件环境具有相对较高的移动 率，代表了一群记者采访一个政治事件或者一群股票代理正在进行股票交易的情 况。灾祸现场环境的特点是某些节点移动较慢，而同时具有一些快速移动的节点。 根据他们的仿真结果，在三种仿真环境下，按需协议d s r 和a o d v 的性能都比先 验式协议d s d v 好很多。在中等的流量负载下，d s r 的性能要比a o d v 协议好， 而在高负载的情况下a o d v 的性能高于d s r 。前者是因为a o d v 在信道获取上 消耗了较多的网资源，后者是因为d s r 数据包中的源路由增加了网的负载。 s a m i rr d a s 等人【1 。7 】使用不同的网络负载、移动性和网络大小，对两种按 需路由协议d s r 和a o d v 进行了性能比较，论证出虽然d s r 和a o d v 有相似的 按需路由的特性，但是协议机制的不同使得它们在性能上有显著差异。d s r 使用 源路由和路由缓存，但不依赖于任何周期或时间活动。a o d v 使用路由表并使用 目的序列号机制来防止环路。通过仿真得知，就时延和吞吐量来说d s r 在诸如节 点数目少，低负载或低移动性的情况下性能优于a o d v ，而a o d v 在更高负载， 高移动性情况下性能较好。 根据上面的结果可以得出结论：在各种不同的情况下比较时，按需方式的路 由算法要比先验式的路由算法在性能上有着明显的优势，因此在考虑本课题的路 由算法时，决定采用按需方式的算法来实现。 此外，在网负荷较重，网规模较大的情况下，a o d v 路由协议具有更好的可 扩展性。课题最后选择了a o d v 路由协议为研究基础，充分研究了a o d v 路由协 议的设计思想，针对适应网络动态拓扑性对其加以改进，从而得到改进的a o d v 路由算法。 6 重庆邮电大学硕士论文 1 2 3a dh o c 网的路由度量 在自组网路由协议的设计中，每个协议各自采用了不同的最优路径选择标准 ( 即路由度量) ，并在给定的环境下取得较好效果。目前已提出的路由度量主要有 路径跳距、路径稳定性、链路状态和最小功率等，根据应用条件的不同，它们或 是单独使用，或是组合使用。 路径跳距 按需路由协议大多选用路径跳距作为度量尺度计算最优路由，它不需要网络 的其他信息，具有简单实用的特点，许多有名的协议，如d s r 、a o d v 等都是以 跳距作为度量。基于跳距的算法在业务流量较低和节点移动速度较慢的情况下有 较好的效果，但难以适应高速和高负载场合，此时最短路径并不一定是最优路由。 由于按需路由协议在路由发现过程中通常使用洪泛法，因此会发现跳距相同的多 条路径，在附加其他因素考虑之后，最短路径经常与其他度量结合使用。 路径稳定性 路径稳定性是自组网路由协议设计中必须考虑的一个重要因素。节点移动对 自组网路由协议的性能有重大影响。在给定的一系列移动模式下具有优良性能的 协议可能在另一种移动模式下完全失败。因此，如果节点移动的某些概念或者它 对网络路径的影响能被描述的话，或许可以利用这些信息来选择更稳定的路径。 基于稳定性的路由算法能保证沿着经历最小链路失效概率的路由传递数据，可以 减少链路中断的次数，从而减少路由发现洪泛。目前路径稳定性路由算法主要有 两种： 1 ) 信号强度 一 s s a 1 8 1 通过链路层信标的信号强度来区分强弱链路。s s a 以相邻两个节点通 信信号的强弱来判断它们之间路径的好坏，即各个节点判断自己与邻节点的通信 信号是强还是弱，从而将它与邻节点的通信信道分为“强信道”和“弱信道”。其 中，信号强度门限对s s a 协议的性能有较大影响，在各种不同环境下，协议缺乏 有效的手段来确定此门限。g e u n h w il i m 等人【1 9 l 对s s a 算法进行改进，提出一 种基于信号强度的链路稳定性估算方法。l b r l 2 0 l 通过传播模型将信号强度转化为 链路间距离，并利用以前的距离抽样值使用线性回归法估算链路寿命。 2 ) 移动预测 o d m r p 2 1 】通过g p s ( g l o b a lp o s i t i o n i n gs y s t e m ) 提供的方位信息，借助移动 预测公式计算链路过期时间。该预测公式是依据两个节点当前的方位、速度和移 动方向计算的，并且假定两个节点的移动方向并不改变的。此外，c h u n y e nh s u 等 人利用链路寿命的历史记录来实现l b r ( l o n g 1 i v e dr o u t ep r e d i c t i o n ) 算法嘲， 7 重庆邮电大学硕士论文 第一章绪论 y u c h e et s e n g 等人在离散时间、随机游走模型( d i s c r e t e - t i m e ，r a n d o m w a l km o d e l ) 上推导出一个给定路由的寿命的概率分布团】。在提供q o s 保证的路由选择算法 中，链路稳定性( 或链路生存时间) 是必须考虑的一个重要参数【2 4 1 。 在节点密度增大的情况下，基于稳定性的路由协议可以选择更稳定的路径， 从而减少拓扑的变化频率，取得比基于最短路径的路由协议更好的性能。但基于 稳定性的路由选择方案无法处理拓扑的快速变化和稀疏网络造成的二次路由洪泛 ( 当第一次路由洪泛无法找到满足稳定条件的路径时，源节点降低条件启动第二 次路由洪泛) 。但是，无论基于稳定性或者是基于最短性的方法都没有考虑所选路 径的链路状态，处于运动区域中心的节点或者运动速度较慢的节点容易同时参与 多条活动路径，大量的数据通过少量结点来传输，会引起m a c 层的阻塞，从而 导致较高的包延迟，使数据传输在此点形成拥塞，产生所谓的“热点问题 ，同时 这些结点还会消耗大量的电池能量。大多数路由协议缺乏自动避免这种现象发生 的机制，并且在路由建立过程中并没有提供与负载和链路质量相关的状态信息， 因而不能在不同的路径上实现负载平衡。 链路状态 随着网络负载的增加，基于最短路径和基于稳定性的路由无法避免热点问题 和实现负载平衡，在路由选取过程中将链路状态作为最优路径的依据之一，是克 服这两个问题的途径。链路状态包括延迟、带宽、丢失率和差错率等，由于节点 的移动性和受限的网络资源，获取和管理链路属性是非常困难的。获取链路状态 也是实现q o s 保证的前提，q o s 路由的基本功能就是发现一条满足给定约束条件 的路径，同时也要考虑资源使用上的优化。 实际上任一链路状态或者他们的组合都可以作为路径选择的依据，但都只能 针对于特定的应用环境，没有适应于任何条件的判断标准。例如，d s a r p ( d e l a y s e n s i t i v ea d a p t i v er o u t i n gp r o t o c 0 1 ) 1 2 5 】协议将最短路径和最低平均延迟作为路由选 择的约束条件，缓解了最短路径算法无法避免的“热点问题”。不过其平均延迟并 不是基于端到端的测量，而是以队列中等待发送的包的数目来衡量的。l b a r 2 6 】 将通过活动路径的节点数目定义为测量节点活动性的度量，使用活动度( a c t i v i t y ) 来实现业务流量的平衡。节点越活动，节点所承受的负荷越多。l b a r 用节点活跃 度来表示移动节点的负载情况，通