（计算机软件与理论专业论文）ad+hoc中一种基于移动agents的按需路由协议.pdf

摘要 摘要 随着a dh o c 网络的出现，它的应用前景越来越被看好。在a dh o c 网络 中，路由协议是极为重要的一环，已有的路由协议可以分为表驱动路由、按 需路由和基于蚁群仿生的路由思想，它们都有自己的局限性。传统的表驱动 路由协议总是维护移动节点到其它所有节点的路由表，浪费了宝贵的无线资 源。传统的按需路由协议，需要等到路由被发现后才可以进行通信。而基于 蚁群仿生似n t b a s e d ) 的路由协议的缺点是路由开销过大和没有路由维护策略。 本文详细分析了d s r 路由协议和基于蚁群仿生的路由思想，总结出它们 优缺点的互补性，从而提出了一种新的移动a dh o c 网络f m a n e t s l 路由协议 一d s r a n t 混合路由协议。它将d s r 按需获取路由的能力和行为类似蚁群的 移动a g c n t 离散式的探索网络拓扑结构的能力结合起来，利用它们优缺点较 强的互补性克服了d s r 因为较长的端到端延迟而不适合于实时通讯和蚁群仿 生算法路由开销过大且没有路由维护策略的缺点，并加入新的路由更新机制。 最后，在g l o m o s i m 中实现了d s r a n t 路由协议，并将它和d s r 进行了仿真 测试比较。仿真结果显示，d s r a n t 降低了系统中相互通讯节点间的平均端 到端延迟和整个系统的路由发现的次数，并保持了较高的连通性。降低了两 节点通讯开始前的延迟使得d s r a m t 更适合于实时通讯。而获得以上优点的 代价只是比d s r 稍高的路由开销。 关键字：m a n e bd s r 移动g e n t 路由协议 a b s t r a c t a b s t r a c t 舢o n gw i t ht h ea p p e a r a j l c eo fa dh o cn e t w o r k s ，i t sf u t u r ei sf i l uo fp r o s p e r i ty r o u t j n gp r o t o c o li sav e r yi m p o r t a n tp a r to ft h ea dh o c e t w o r k s ，t h ea l r e a d ye x j s t i o u t i n gp r o t o c o l sc a nb es o n i n t ot h r e e c a t e g o r i e s ，p r o a c t i v et o u t i n gp r o t o c o l ， o n - d e m a i l di o u t i n gp r o t o c o la n da n t l i k em o b i l ea g e n t s ，w l l i c ha r ea uh a v et h e i fo w n d r a w b a c k s 1 1 1 et r a d j t j o n a lp r o a c t i v er o u t j n gp m t o c o lc o n t i n u o u s l yu p d a t et h er o u t j n g t a b l e s0 fm o b i kn o d c sc o n s u m i n gl a t g ep o n i o no ft h es c a r c en e t w o i kc a p a c i t yf o i e x c h a i l g i i l gh u g ec h u i d ( so fr o u t i n gt a b l ed a 协t h et r a d i t i o n a lo n - d e m a n dr o u t i n g p m t o c o l ，s u c ha sd s r ，r e q u i r e dt h ea c t u a lc o m m u n i c a t j o n b ed e l a y e du n t i l t h em u t ei s d e t 锄i n e d ，w h e i e a st h ea n t l b a s e dr o u t i n gp f o t o c 0 i si n k n td r a w b a c ki st h et o o m u c hm u t i n go v c r h e a da l l dh a v i n gn or o u t em a i n t e n a i l c ep o l i c y _ a f t e ra n a l y z i n gt h ed s ra n da m l 搬em o b i l ea g e n t sm u t i n ga l g o r i t h m ，w e c o n c l u d e dt h ec o m p k m e n t a m i e so ft h e m ，b a s e do nw h i c han o v e lr o u t i n gs c h e m ef o r m o b i l ea dh o cn e t 、v o f k s ( m a n e t s ) d s r - a n th y b r i dr o u t i n gp r o t o c o l i sp f o p o s e dj n t h i sp a p c r t h en e wr o u t i n gp r o t o c o lc o m b i n e st h eo n d e m a n dr o u t i n gc a p a b j l i t yo f d s r 咖t i n gp r o t o c 0 1w i t had i s t r i b u t e dt o p o l o g yd i s c o v e r ym e c h a n i s mu s i n ga n t l i k e m o b i l e a g e n t s i to v e r c o m e st h ed s r ss h o r 忙o m i n g st h a tm a yn o ta p p l i c a b i e t o r e a l t i m ed a t ab e c a u s eo ft h el o n ge n d - t o e n dd e l a ya n dt h ed r a w b a c k so fa i l t l i k e m o b i l ea g e i i t s 也a th a v i n gn 0r o u t em a i n t e r l 题c ep o l i c ya n dt h eh i g hr o u t i n go v e r h e a d b ym a k i n gu s eo ft h ec o m p l e m c n t a i i d e so ft h e ma 1 1 da d d j i l g e wr o u t j i 曙m e c h a n i s m s t oe n h 缸c et l l e i fc a p a b j l i t i e sa n da l l e v i a l et h e i rw e a l ( n e s s e s f i n a l l y ，m ed s r - a j l th a s b e c ni m p l e m e n t c di nt h cs i m u l a t i o n 咖lg l o m o s i i n a c o n t r a s t i v es i m u l a t i o nb e t w e e n d s ra n dd s r a m tw a se x e c u t e d s j i n u l a t i o nr e s u l t ss h o wt h a td s r - a n i h y b 耐 m u t i n gp r o t o c o l i sm o r ep r o p e rt or e a l t i m ec 0 衄u n j c a t i d u et oi t sl o we n d t o e d d c h ya n dh i g hc o i l r l c c t i v i t y m o r eo v e r ，t h ec o s t0 fo b t a i n i n gt h eb e n e f i t sa b o v ei so n l y as l i g h t l yh i g hr o u t i n go v e r h e a dc o m p a i e dt od s r k e y 、v o r d ：叫e t d s rm o b i l ea g e n ir o u t i n gp m t o c o l 创新性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或 其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做 的任何贡献均已在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：蓬旭桶本人签名：夏塑塑日期抽，f 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕 业离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。 学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全 部或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。( 保密的论文 摘解密后遵守此规定) 本学位论文属于保密，在一年解密后适用本授权书。 本人签名 导师签名： 耋垫鳋 墨：垄殳 日期知口f 心 第一章绪论 第一章绪论 1 1 引言 常见的移动网络通常是以蜂窝网络或无线局域网等形式出现的。在蜂窝网络 中，移动终端之间的通信必须借助于基站和( 或) 移动交换机的转接完成：在无 线局域网中，移动终端通过无线接入点连接到现有的固定网络。与此同时，蓝牙 ( b l u e t 0 0 t h ) 1 8 j 、家庭无线网( h o m e r f ) 1 9 】等移动通信新技术也纷纷涌现。这些移动网 络和无线通信技术是对固定有线网络的补充和发展，它们需要固定基础设施的支 持，并且一般采用集中式的控制方式。但在某些特殊环境或紧急情况f ，有中心 的移动通信技术并不能胜任。比如，战场上部队快速展开和推进、发生地震等自 然灾害后的搜索和营救、野外科考等。因此在以上场合中迫切需要一种不依赖基 础设施能够快速和灵活配置的移动通信网络技术，a dh o c 网络就是为满足这种特 殊应用需求而产生的。 在a d h o c 网络中，结点具有报文转发能力，结点间的通信可能要经过多个中 间结点的转发，即经过多跳( m u n i h o p ) ，这是a dh o c 网络与其他移动网络的最 根本区别。结点通过分层的网络协议和分布式算法相互协调，实现了网络的自动 组织和运行。因此它也被称为多跳无线网( m u l t i h o pw i r e l e s s t w o r k ) 、自组织 网络( s e l f o r g a | 1 i z e dn e 似o r k ) 或无固定设施的网络( h l 舶s t n l c t u r e l e s sn e t w o r k ) 。 在各层的网络协议中，a d h o c 网络的路由问题尤其关键，r f 已经成立了m a n 耵 工作组集中从事a dh o c 网络单播路由协议及其性能评定的研究，现已发布了一些 路由草案，r f 下一步还将就如何实现多播路由以及q o s 等问题展开讨论。 1 2 研究现状 a dh o c 网络作为一项技术，虽然已经存在了3 0 多年，但其研究现状却并不 成熟，仍然处于试验和研究阶段，目前还面临许多难题，概括起来主要有以下几 个方面： 1 特殊的信道共享方式 通信网络中的信道共享方式一般有三种：点对点、点对多点和多点共享。点 对点是最简单的共享方式，两个结点可以共享一个信道( 有线或无线) 。点对多点 共享一般用于有中心站控制的无线信道，例如蜂窝移动通信系统的无线信道。在 a dh o c 中一种基丁移动a g e n i 的按需路由协议 这种方式中，终端( 如移动电话) 在中心站( 如基站) 的控制f 共享一个或多个 无线信道，所有终端均处存中心站的覆盖范围内。多点共享指多个终端共享一个 广播信道，以太网就是最典型的多点共享方式。在多点共享方式巾，一个终端发 送报文，所有的终端都可以昕到，即相当于一个全互联的网络，我们称这种共享 方式下的信道为一跳共享广播信道。 a dh o c 网络的信道共享方式与它们不同。虽然a dh o c 网络的无线信道也是 一个共享的广播信道，但它不是一跳共享的。因为当一个结点发送报文时，只有 在它覆盖范围内的结点( 称为邻居) 才能够收到，而覆盖范围外的结点则感知不 到任何通信的存在。这恰恰也是a d h o c 网络的优势所在，发送结点覆盖范围外的 结点不受发送结点的影响，它们也可以同时发送报文。我们称a dh o c 网络的共享 信道为多跳共享广播信道。 多跳共享广播信道带来的直接影响就是报文冲突与结点所处的位置相关。在 一跳共享的广播信道中，报文冲突是个全局事件。所有结点要么都收到正确的报 文，要么都会感知到报文冲突。而在a d h o c 网络中，报文冲突只是局部事件，并 非所有结点都可以感知到。一个结点正确收到了一个报文，该报文可能会在另一 个结点处发生冲突。也可能报文在接收结点处发生了冲突，而发送结点丝毫觉察 不到。也就是说发送结点和接收结点感知到的信道状况不一定相同，由此将会带 来隐终端、暴露终端等一系列的特殊问题。 由于a dh o c 网络特定的信道共享方式，基于点对多点共享信道和一跳共享广 播信道接入协议无法被a dh o c 网络直接使用，需要为它设计专用的信道接入协 议。信道接入协议是报文在信道上发送和接收的直接控制者，它的行为对a d h o c 网络的性能起着决定性的作用。因此，信道接入协议一直是a dh o c 网络技术的研 究重点之一。 2 动态拓扑 a d h o c 网络中的结点不仅可以自由移动，还可以随时开机和关机。这将造成 网络拓扑的动态变化。考虑到a dh o c 网络的多跳特性，结点要有报文转发功能， 这要求结点实现相应的路由协议。传统的基于因特网的路由协议是为相对稳定的 网络拓扑而设计的，它们无法满足快速变化拓扑网络的需要。因此，路由协议也 成了a d h o c 网络的研究特点。 现有的a d h o c 网络路由协议可以分为先应式( p m a c t j v e ) 、反应式( r e a c t i v e ) 和混合式三种。先应式路由协议又被称为表驱动( t a b l e 一“v c n ) 路由协议，它通 过连续地检测链路质量，时刻维护准确的网络拓扑和路由信息。其优点是发送报 文时可以立即得到正确的路由，缺点是开销太大。反应式路由协议，又称为随选 路由( 0 n - d e m a n dr o u t i n g ) ，并不时刻维护准确的路由信息，仅当需要时才查找 路由。其优点是降低了路由维护的开销，缺点是查找路由会引入较大的时延。结 第一章绪论 点先应式和反应式特点的路由协议称为混合式路由协议。它在局部范围内使用先 应式路由协议，以缩小路由控制消息传播的范围。当目标结点较远时，通过查找 发现路由。这样既可以减少路由协议的丌销，时延特性也得到了改善。 鉴于路由协议的重要性，t f 的m a n e t 工作组目前专注于a dh o c 网络路 由协议的研究。虽然已经取得了一定的成果，但仍有很多问题没有解决。 3 其他问题 安全问题：a dh o c 网络面临的安全性威胁来自无线信道和网络。无线信道容 易被窃听和干扰。此外，无中心和自组织的网络组织形式不仅容易遭受冒充、欺 骗等形式的攻击，还对网络的安全体系结构提出了新的要求。需要研究适用于a d h o c 网络的安全体系结构和用户认证、加密等安全技术。目前，针对a dh o c 网络 安全的问题已丌展了一些研究，但还没有较完善的解决方案。 电源问题：作为移动终端的a dh o c 网络结点一般采用电池供电，这与普通的 网络设备使用电源线供电有着显著的差异。为了延长电池的使用时间，在设计网 络协议时，要尽量节约电池的电能。这可以通过功率控制和在适当的时候关闭发 射机来实现。 协议设计：a dh o c 网络使用无线通信技术。与有线信道相比，带宽窄，信道 质量差。这对协议的设计提出了新的要求。为了节约有限的带宽，a dh o c 网络协 议设计的原则要尽量减少结点间交互的信息量。此外，由于无线信道的衰落、结 点移动等因素会造成报文冲突和丢失，这将严重影响t c p 的性能。因此，在a d h o c 网络中要对t c p 的传输层服务进行改进，以满足数据传输的需要。 网络管理：a dh o c 网络的自组织网方式也给网络管理提出了新的要求。不仅 要对网络设备和用户进行管理，还要有相应的机制解决移动性管理、服务管理、 结点定位、地址配置等特殊问题。 由于a dh o c 网络的特殊性，它将面临许多特有的问题。这些问题涵盖了网络 组织、协议设计、网络运地维护的方方面面，需要进行专门的研究才能解决。针 对a d h o c 网络已经开展了大量的研究，目前的研究方向主要集中在信道接入协议 和路由协议等方面。现有的研究成果都有它特定的使用环境，对很多问题而言， 寻找一个通用的解决方法是非常困难的。这也是a d h o c 网络协议至今难以标准化 的原因。目前，针对网络安全、广播和多播的支持、服务质量保证、网络管理、 网络互联等问题都开展了一些初步的研究，但还未有完善的解决方案。这为a d h o c 网络技术的深入研究留下了非常广阔的空间。 4 a dh o c 中一种基于移动a g e n t 的按需路由协议 1 3 研究内容及主要目标 由于现在的移动a dh o c 网络技术在各个方面还不是特别完善，尤其是在重 要性非同寻常的网络层路由协议方面，虽然已经存在许多可用的路由协议，但是 这些协议都是有自身特殊的适用环境的，是针对a d h o c 网络不同的参数配置的。 比如，d s d v 适用于节点运动速度缓慢、拓扑结构变化不大的网络环境；而d s r 和a o d v 则适合节点运动速度较快、拓扑结构变化快的网络环境；还有其它的一 些路由协议均有自己适用的不同环境。可以肯定一点，那就是目前还没有哪一种 a dh o c 网络层的路由协议是万能的，可以在任何环境下都具有最高的性能。而且 就现在而言，发明出这样一种路由协议也是不现实的。基于这种思想，我们认为 a dh o c 网络层的路由协议的性能和多样性还是有很大的提高余地的。 本文主要的目标是提出一个新的路由协议。基于上面的思想，新协议的目的 并不是成为一个万能的路由协议，它的主要适用环境是节点运动速度较快，又要 求实现实时通讯的移动a dh 0 c 网络环境，即要求节点间试图通信时达到较短的 端到端延迟。为了实现这个目的，本文作了以下工作，深入研究了一种典型的按 需路由协议一d s r ，详细了解了它的各种机制。还详细研究了另一种路由方法， 基于移动a g e n 的蚂蚁路由算法。发现了这两种路由方式的优缺点存在着很强的 互补性，如果把按需路由中节点发起路由发现的主动性和蚂蚁路由中共享网络中 其它节点路由为己所用的特点相结合，就可以有效的降低节点问通信的端到端延 迟。随后的目标就是如何在可以接受的开销增大范围内达到减少端到端延迟的目 的。然后，提出了一种新的路由协议一一d s r m 盯，它结合了按需路由和蚂蚁路 由的优良特性，以达到降低端到端延迟的目的，开销的增大也控制在可以忍受的 程度以内。最后，在g l o m o s i m 仿真工具内具体实现了d s r a 皿t 路由协议，将移 动a g e n t 的机制融合到了d s r 路由协议中去，并在0 l o m o s i m 中对比测试了d s r 和d s r a m t 两种路由协议，证明了d s r a 皿t 具有前面设想的优点。 1 4 论文的组织结构 余下的章节作了如下安排： 第二章介绍了移动a dh 0 c 网络的基本概念，它的起源、定义、特点以及各 个应用领域。然后按照表驱动路由协议、按需路由协议和蚂蚁路由协议分类介绍 了a d h o c 网络中的路由协议，并举例说明。 第三章前半部分以d s r 例子分别详细分析了按需路由协议和蚂蚁路由协议 的运行机制并分析了它们的优缺点，阐述了为什么要提出d s r a m t 混合路由协 第一章绪论 议。后半部分详细叙述了d s r a n t 混合路由协议的设计。 第四章开始简单介绍了网络仿真工具g l o m o s i m ，重点放在d s r a m t 混合路 由协议的具体实现及其在g l o m o s i m 中的仿真结果，还将它与d s r 的仿真结果进 行了分析比较，对新弥议的性能进行了评价。 第五章同顾全文，总结自己的工作，提出d s r 舢i 的不足之处和对下一步工作的展望。 a dh o c 中一种基丁移动a g e n t 的按需路由协议 第二章a dh o c 网络路由协议 本章主要介绍了a dh o c 网络的基础知识和路由协议。首先，概述了a dh 0 c 网络的起源、特点和应用。随后又将a d h o c 网络中的路由协议分为表驱动路由、 按需路由和蚂蚁路由协议三类详细介绍，力求让读者对a dh o c 网络有一个基本 了解。 2 1 无线移动a d h o c 网络概述 2 1 1a dh o c 网络的特点 a dh o c 网络的前身是分组无线网( p a c k e tr a d i on c m o r k ) 【1 0 】。早在1 9 7 2 年， 美国功姒就启动了分组无线网项目p 咖，研究在战场环境下利用分组无线 网进行数据通信。在此之后，妞p a 于1 9 8 3 年启动了高残存性自适应网络项目 s u r a n ( s u r v i v a b l e a d a p t i v en e m o r k ) i ”j ，研究如何将p 鼢嘎t 的研究成果加以 扩展，以支持更大规模的网络。1 9 9 4 年，d a r p a 又启动了全球移动信息系统 g 1 0 m o ( g l o b l em 0 b i l ei n f o r l a t i o ns y s t e m s ) 项目1 1 2 】，旨在对能够满足军事应用需 要的、可快速展开、高抗毁性的移动信息系统进行全面深入的研究。成立于1 9 9 1 年5 月的砸e e 8 0 2 1 1 标准委员会f 1 3 】采用了“a dh o c 网络一词来描述这种特殊的 自组织对等式多跳移动通信网络，a dh o c 网络就此诞生。砸t f 也将a d h o c 网络 称为m a n e t ( 移动a dh o c 网络) 【1 4 】。a d h 0 c 的意思是“f o r t h i s ，引申为“f o r t h i s p u r p o s eo n l y ”，即“为某种目的设置的，特别的”意思，即a dh o c 网络是一种有特 殊用途的网络。 在a d h 0 c 网络中，当两个移动主机( 如图2 1 中的主机a 和q 在彼此的通信 覆盖范围内时，它们可以直接通信。但是由于移动主机的通信覆盖范围有限，如 果两个相距较远的主机( 如图2 1 中的主机a 和b ) 要进行通信，则需要通过它们 之间的移动主机c 的转发才能实现。因此在a dh o c 网络中，主机同时还是路由 器，担负着寻找路由和转发报文的工作。在a dh o c 网络中，每个主机的通信范 围有限，因此路由一般都由多跳组成，数据通过多个主机的转发才能到达目的地。 故a dh o c 网络也被称为多跳无线网络。 第二章a d h o c 网络路由协议 ，j 一一、* 、，7 ，一、 f ，7、， 7 7 ?，7。7j7、 、c 少弋 一，。 。 l 、。， 、一一 图2 1 节点a ，b 通过c 的转发进行通讯 a dh o c 网络可以看作是移动通信和计算机网络的交叉。在a dh o c 网络中， 使用计算机网络的分组交换机制，而不是电路交换机制。通信的主机一般是便携 式计算机、个人数字助理( p d a ) 等移动终端设备。a dh o c 网络不同于目前因特网 环境中的移动i p 网络。在移动i p 网络中，移动主机可以通过固定有线网络、无 线链路和拨号线路等方式接入网络，而在a dh o c 网络中只存在无线链路一种连 接方式。在移动1 p 网络中，移动主机通过相邻的基站等有线设施的支持才能通信， 在基站和基站( 代理和代理) 之间均为有线网络，仍然使用因特网的传统路由协议。 而a dh o c 网络没有这些设施的支持。此外，在移动i p 网络中移动主机不具备路 由功能，只是一个普通的通信终端。当移动主机从一个区移动到另一个区时并不 改变网络拓扑结构，而a dh 0 c 网络中移动主机的移动将会导致拓扑结构的改变。 与其它传统通信网络相比，a d h o c 网络具有以下显著特点： 1 ) 无中心和自组织性：a dh o c 网络中没有绝对的控制中心，所有节点的地 位平等，网络中的节点通过分布式算法来协调彼此的行为，无需人工干预和任何 其它预置的网络设旌，可以在任何时刻任何地方快速展开并自动组网。由于网络 的分布式特征、节点的冗余性和不存在单点故障点，使得网络的健壮性和抗毁性 很好。 2 ) 自动配置：自动配置是a dh o c 网络的基本特征，节点必须检测其它节点 以及它们可以提供的服务。由于网络动态变化，自动配置过程需要确保网络能够 f 常工作，这涉及到连接h l t e m c t 的网关节点的更换，簇头的更新等。在网络形 成阶段，节点可以就网络拓扑进行协商( 星形、环形、点到点、点到多点、平面 a d h 0 c 中一种基丁移动a g e n t 的按需路由协议 和分级) ，这依赖于网络的类型、底层的无线技术和应用的需求。 3 ) 动态变化的网络拓扑：a dh o c 网络中，移动终端能够以任意速度和任意 方式在网中移动，并可以随时关闭电台，加上无线发送装置的天线类型多种多样、 发送功率的变化、无线信道问的互相干扰、地形和天气等综合因素的影响，移动 终端间通过无线信道形成的网络拓扑随时可能发生变化，而且变化的方式和速度 都难以预测。 4 ) 受限的无线传输带宽：a dh o c 网络采用无线传输技术作为底层通信手段， 由于无线信道本身的物理特性，它所能提供的网络带宽相对有线信道要低得多。 此外，考虑到竞争共享无线信道产生的冲突、信号衰减、噪音和信道之问干扰等 多种因素，移动终端得到的实际带宽远远小于理论上的最大带宽。 5 ) 移动终端的局限性：a dh o c 网络中，移动终端具有携带方便、轻便灵巧 等好处，但是也存在固有缺陷，例如能源受限、内存较小、c p u 性能较低等，从 而给应用程序设计开发带来一定的难度，同时屏幕等外设较小，不利于开展功能 较复杂的业务。 6 ) 安全性较差：a dh o c 网络是一种特殊的无线移动网络，由于采用无线信 道、有限电源、分布式控制等技术，它更加容易受到被动窃听、主动入侵、拒绝 服务、剥夺“睡眠”等网络攻击。信道加密、抗干扰、用户认证和其它安全措施都 需要特别考虑。 7 ) 网络的可扩展性不强：在目前i n t e m e t 环境下，可以采用子网、无级域间 路由( c i d r ) 和变长子网掩码( v l s m ) 等技术，增强了h t e m e t 的可扩展性。 但是动态变化的拓扑结构使得具有不同子网地址的移动终端可能同时处于一个 a d h o c 网络中，因而子网技术所带来的可扩展性无法应用在a d h o c 网络环境 8 ) 多跳路由：由于节点发射功率的限制，节点的覆盖范围有限。当它要与其 覆盖范围之外的节点进行通信时，需要中间节点的转发。此外，a dh o c 网络中的 多跳路由是由普通节点协作完成的，而不是由专用的路由设备( 如路由器) 完成 的。 9 ) 存在单向的无线信道：a dh o c 网络采用无线信道通信，由于地形环境或 发射功率等因素影响可能产生单向无线信道。 1 0 ) 特殊的信道共享方式：传统的共享广播式信道是一跳共享的。而在a d h o c 网络中，广播信道是多跳共享的，一个节点的发送，只有其相邻一跳节点可以听 到。 1 1 ) 供电问题突出：考虑到成本和易于携带，节点不能配备太多数量的发送 接收器，并且节点一般依靠电池供电。因此如何节省节点电源、延长工作时间是 个突出问题。 篇二章a d h o c 网络路由协议 2 1 2a dh o c 网络的应用 a di o c 网络的应用范围很广，总体上来说，它可以用于以下场合： a ) 没有有线通信设施的地方，如没有建立硬件通信设施或有线通信设施遭受 破坏。 b ) 需要分布式特性的网络通信环境。 c ) 现有有线通信设施不足，需要临时快速建立一个通信网络的环境。 d ) 作为生存性较强的后备网络。 a dh o c 网络技术的研究最初是为了满足军事应用的需要，军队通信系统需要具有 抗毁性、自组性和机动性。在战争中，通信系统很容易受到敌方的攻击，因此， 需要通信系统能够抵御一定程度的攻击。若采用集中式的通信系统，一旦通信中 心受到破坏，将导致整个系统的瘫痪。分布式的系统可以保证部分通信节点或链 路断开时，其余部分还能继续工作。在战争中，战场很难保证有可靠的有线通信 设施，因此，通过通信节点自己组合，组成一个通信系统是非常有必要的。此外， 机动性是部队战斗力的重要部分，这要求通信系统能够根据战事需求快速组建和 拆除。 a dh o c 网络满足了军事通信系统的这些需求。a dh o c 网络采用分布式技术， 没有中心控制节点的管理。当网络中某些节点或链路发生故障，其他节点还可以 通过相关技术继续通信。a d h 。c 网络由移动节点自己自由组合，不依赖于有线设 备，因此，具有较强的自组性，很适合战场的恶劣通信环境。a dh o c 网络建立简 单、具有很高的机动性。目前，一些发达国家为作战人员配备了尖端的个人通信 系统，在恶劣的战场环境中，很难通过有线通信机制或移动i p 机制来完成通信任 务，但可以通过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 d h o c 网络可以解决这些环境中的通信问题。a dh o c 网络还可以用于临时的通信需求， 如商务会议中需要参会人员之间互相通信交流，在现有的有线通信系统不能满足 通信需求的情况下，可以通过a dh o c 网络来完成通信任务。 a dh o c 网络在研究领域也很受关注，近几年的网络国际会议基本都有a di i o c 网络专题，随着移动技术的不断发展和人们日益增长的自由通信需求，a dh o c 网 1 0 a dh d c 中一种基于移动a g e n t 的按需路由协议 络会受到更多的关注，得到更快速的发展和普及。 2 2 a dh o c 网络中的路由办议 现存a dh o c 网络路由协议可以分为以下几类： 表驱动( t a b l e d r i v e n ) 、源发起的按需路由( s o u r c e i n i t i a t e do n d e m a n d r o u t i n g ) 和基于蚂蚁群仿生的路由协议。下面就对这几类路由分别进行介绍。 2 2 1 表驱动路由协议 表驱动型路由协议的特点是节点总是要维护到其它节点的路由信息，通过不 断更新路由表来保持路由信息的完整性。节点要对网络的拓扑结构变化做出反映， 不仅要不本节点的路由信息更新，还要将更新信息传播出去，这样很大部分宝贵 的网络资源被用于交换大量的路由表数据，而减少了实际用于数据通信的网络资 源。不同的协议之间的区别是相关路由信息的数量和路由信息的更新方式。下面 介绍现有的表驱动路由协议。 1 目的序号距离矢量算法d s d v ( d e s t i 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 r o u t i l l g ) 在目的序号距离矢量算法中，路由表维护本节点至网络内部所有可能的目的 节点的路由，每个路由表项都被目的节点赋予一个序号( s e q u e n c e u m b e r ) ，其目 的是用以区别新旧路由。 通过周期性的“全播”( f i l ud u m p ) 的方式，把完整的路由信息转送出去。两 次“全播”之间，如果有更新信息则用小的“增长”数据包( i n c r e m e n t a l 口a c k e t ) 传送。新的路由广播包括目的节点的地址、到目的节点的跳数、请求信息包的序 号和新的发送序号。新路由的序号比旧路由的序号要大，如果路由序号相同，则 选择更短路由的路由。 d s d v 算法采用序号来区别新旧路由，利用更新延迟来防止稍后会收到的更 好的路由信息。此算法的缺点是有可能导致信息洪泛，尤其是在网络节点较多的 时候。对于移动性较强的网络，d s d v 的数据包丢失率较高。 2 无线路由协议算法w r p ( w i r e l c s sr o u t i n gp m t o c 0 1 ) 为解决d s d v 数据包丢失率较高的问题，无线路由算法着重处理链路失效的 问题，算法维护的完整路由表信息包括距离表、路由表、链路开销表、信息重传 节点列表四个部分。节点通过邻居的状态变化对路由表作出调整，并通知邻居节 点；收到来自邻居节点的信息有，更改路由信息。如果节点没有更新信息转发， 第二章a dh o c 网络路由协议 则要定期发送h e l l o 消息，以确保节点的连通性。如果节点不发送h e l l o 消 息，那么认为节点的链路信息无效。新节点加入网络系统时，要发送h e l l o 消 息，如果某个移动节点收到了新节点的h e l l o 消息，则把新节点的信息填入路 由表，并且把它自己的路由表发给新节点。通过记录距离信息和先驱( p r e d e c e s s o f ) 信息，解决了死环问题。所谓先驱是所选路由上，目的节点的前一个节点，也称 为“倒数第二跳”( s e c o n d t o 1 a s th o p ) 由前面的介绍可知，w r p 是一种l s ( 1 i n ks t a t e ) 算法。w r p 对链路失效的情 况有较好的适应性。 3 全局状态路由算法g s r ( g l o b a ls t a t er o u t i n 曲 g s r 算法于d s d v 类似，但节点收到请求信息后，在把信息包转发之前将自 己的地址填写到请求信息数据包的路由中。如果发现已经存在自己的地址，就把 该数据包丢弃。避免了信息洪泛。 节点维护了整个网络的拓扑信息，并在本地优化路由信息。拓扑表维护了链 路状态信息，下一跳信息和信息时间戳。路由信息在链路状态改变时立即更新。 在移动性较强并且带宽有限的情况下，g s r 较d s d v 和传统的链路状态算法更 好。g s r 对移动性不敏感是因为g s r 仅仅维护的是邻居节点的状态信息，收移 动的影响相对较小。g s r 的缺点是需要传播的路由信息数量随网络节点的增多呈 指数级增长。 为了减少g s r 算法的路由信息传播数量，人们提出了f s r 唧s h e v es t a t e r o u t i n 曲来解决上述问题，如图2 2 所示： 图2 2f s r 模型实例( a 节点表示源节点) f s r 的基本思想是距离源节点近的节点经常与源节点交换信息，距离越远， 交换的信息越少，这样就有效的避免了信息的泛滥。这种算法的拓扑组织结构想 鱼的眼睛，所以称之为f s r 。 4 “群首”网关交换路由算法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 曲 a dh o c 中一种基于移动a g e n t 的按需路由协议 c g s r 是为了减少网络中的路由信息而设计的一种算法。该算法的基本思想 是把网络分为“簇”，簇内节点l 匈中心节点( 群首) 集中信息，群首负责簇阃信息 的交换，这样既保证路出信息的准确性，又可以减少信息数量，提高网络运行效 率。算法要求网络系统分为多个“簇”m u s t e n ，即将移动节点分为多个区域，每 个区域包含若干个节点，每个簇有一个“群首”( c l u s t e r h e a d ) 。采用最小群首改变 策略l l c ( k a s tc l u s i e rc h a l l g e r ) ，避免频繁地改变群首。只有当两个群首可以直 接通信或者有一个节点与所有群首失去联系的时候才能改变群首。“群首”负责收 集本簇的信息，簇内所有节点都把路由信息发送给“群首”。两个“群首”之间通 过网关交换路由信息。如图2 3 所示： 图2 3c g s r 的路由信息传播实例 c g s r 算法有效地解决了信息的洪泛问题，限制了路由请求信息的传输范围， 但是选择群首是该算法的核心问题，群首选择得好，不仅是本簇的信息传播得到 有效的控制，而且会使全局性能得到意想不到的改观。反之，群首就会成为系统 的瓶颈，使得算法的优越性无法体现。 2 2 2 按需路由 按需路由协议不需要像表驱动路由协议那样实时地维持每个节点的路由信 息，而只在源节点需要路由的时候才发起路由，从而降低了对网络带宽和能量的 过度消耗。当源节点需要一个到达某一目的节点的路由时，它在网络中发起一个 路由发现过程：路由建立之后，会由一个路由维护程序进行维护，直到每条路径都 断裂或不再需要路由为止。典型的源发起按需路由包括：a o d a d h o co n d e m a n d v e c t o r o u t i n g ) 。圳，d s r 唑d y n a m i cs o u r c em u t i n 酚，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 g a 1 9 0 f i t h m ) 【5 】等。 按需距离矢量路由( a o d v ) 第二章a dh o c 网络路由协议 a o d v ( a dh o c o n d e m a i l dd i s t a n c cv e c t o r ) 是采用基于距离矢量的算法的 一种路由协议0 1 ，他是建立在d s d v 算法上的。a o d v 是d s d v 的一种改进，因为他 典型的缩小了需要广播的数量。a o d v 是一种纯粹的按需路由协议。它只在必要的 时候请求路由，而且不要求节点维持当前通信中不使用的路由，也就是说，只要 通信连接的节点之间有可用路由，a o d v 不起任何作用。a o d v 中的两个重要卧 议规程是路由发现和路由维护。a o d v 使用不同的消息来发现和维持路由。当在a d h o c 网络中的一个节点要发送一个数据包给一个目的节点时，如果它不知道到达 该节点的路由或者到该节点的路由已经过期，它采用路由发现( p a t hd i s c o v e r v ) 规程来动态地决定这条路径。路由发现规程广播一个路由请求( r o u t er e q u e s t ， r r e q ) 消息给它所有的邻节点并等待路由应答( r o u t er e p l y ，r r e p ) 消息。a o d v 协议使用目的节点的序列号机制来保证路由信息的及时性和不产生循环路由。每 个节点维护一个本地的“序列号”( 递增) 和一个“广播标识”( b r o a d c a s ti d ， 保证每次广播被唯一标识) 。当产生r r e d 分组时，此中包括：“序列号”、“广 播标识”和自己的i p 地址，这样就唯一地表示了这次路由请求同时，源节点还 在r r e q 分组中放入了所请求路由( 已经过期或不存在) 的最近的序列号。通过 “广播标识”和源节点i 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 分组到达目的节点或是知道更新的路由的中间节点时，它会沿着反向路由发送“路 由答复”( r o u t er e p l y ，r r e p ) 分组。在反向将r r e p 分组转发给源节点的过 程中，中间节点又会建立到目的节点的正向路由。而且，路由表中的每条路由信 息都和一个计