（通信与信息系统专业论文）移动自组织网络路由技术研究.pdf

摘要 随着通信和网络技术的发展，移动自组织网络m a 卜陋t ( m o b i l ea dh o c n e 咖r k s ) 得到了越来越广泛的应用，如何设计出性能良好的路由协议是一个具有 挑战性的任务。本文介绍了移动自组织网络及现有的适应于移动自组织网络的路 由协议，提出了一种基于组移动技术的自适应区域路由协议a z r ( a d a p t i v ez o n e r o u t i n gp r o t o c 0 1 ) 。应用网络仿真工具o p n e tm o d e l e r 对a z r 协议进行仿真，仿 真结果表明a z r 协议在控制开销和时延方面要优于传统的z i 冲( z o n er o u t i n g p r o t o c 0 1 ) 协议和f s r ( f i s h e y er o u t i n gp r o t o c 0 1 ) 协议。在a z r 的分析基础之上，本 文分别从分组方式、信道速率、移动速度和网络规模方面具体仿真和分析了基于 组移动的a z r 协议。另外，本文在a z r 的基础上提出了适用于m i m o ( m u l t i p l e i 印u tm u l t i p l eo u t p u t ) 信道的m a z r ( m i m 0a d a p t i v ez o n er o u t i n gp r o t o c 0 1 ) ，并从 理论上分析了m i m o 技术对网络容量的优化，最后对m a z r 协议完成了网络仿真 并在结果中验证了其综合性能优势。 关键字：移动自组织网络路由协议组移动m i m o a b s t r a c t w j 也也ed e v e l o p m e n to fc o m m u n i c a t i o na n dn e t w o r kt e d h n o l o g y m a n e t f m o b i l ea dh o cn e 啪r k s ) a r eu s e dm o r ea 1 1 dm o r e 谢d e l yi n “sw o r l d h o w t 0d e s 迢n al ( i n do fr o u t i n gp r o t o c o lw k c hi sa b l et os u p p o r tw e np e r f o 肌a n c em o b i l ea dh o c n e 柳o r l 岱i sac h a l l e n g i n gt a s k 1 1 1n l i sp a p e r ，m o b i l ea dh o c n e 肿o r k sa 1 1 d 也ee x l 5 t l n g r o u t i n gp r 渤c o l sf o rm o b i l ea dh o cn e t w o r k sa r ei n t r o d u c e d 1 1 1 e n ，a z r ( a d 印t i v e z o n er o u t 证gp r o t o c 0 1 ) w m et e c l l i l o l o g yo f 争o u pm o b i l 时i sp r o p o s e d t h e n ，a z r i sc o m p l e t e db yo p n e t m o d e l e ra 1 1 dt h es 蚰u l a t i o nr e s u l t ss h o wt h a ti ti ss u p e n o rt 0 t h e 枷i t i o n a lz r p ( z o n er o u t i n gp r o t o c 0 1 ) a n df s r ( f i s h e y er o u t i n gp r o t o c 0 1 ) l n o v e r h e a da l l dd e l a yb a s e do nt 1 1 es t u d yo fa z r ，a z rw i m t h et e c l l l l o l o g yo t 伊o u p m o b i l i t vi ss i m u l a t e da i l da n a l y z e ds p e c i f i c a l l yi nt e 衄so f 伊o u pm o d e ，c h 锄e lr a t e ， m o b i l es p e e da n dn e 似o r ks i z e a 1 s o ，m a z r ( m i m oa d a p t i v ez o n er o u t i n g p r o t o c 0 1 ) b a s e do nm i m o ( m u l t i p l ei n p u tm u l t i p l e0 u t p u t ) t e c i l o l o g yi sp r o p o s e dt ol m p r 0 v e 也ed e r f - o 咖a n c eo fa z r w ep e r f o m t h e o r e t i c a la n a l y s i so fm i m ot e c h n o l o g yo nt h e p e r f 0 锄a n c eo p t i m i z a t i o n0 fn e m o r kc a p a c i 够f i n a l l y ，s i m u l a t i o n s a r ei m p l e m e l l t e d a 1 1 dm e nt 1 1 es y n t h e t i c a l l yp e 哟肌a 1 1 c ea d v a n 嘲g e so fm 戍乙rp r o t o c o l a u r et e s t l f l e d t 1 1 r o u g l lt 1 1 er e s u l t s k e y w o r d ：m o b i i e a dh o cn e 柳o r k sr o u t ep r o t o c o lg r o u pm o b i l 时 m i m o 创新性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文 中不包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技 大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本 研究所做的任何贡献均已在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名置星一 日期碰：业 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研 究生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保 证毕业离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技 大学。学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布 论文的全部或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。 ( 保密的论文在解密后遵守此规定) 本学位论文属于保密，在一年解密后适用本授权书。 本人签名： 导师签名： 吕度 日期2 啦：f ：丛 日期一兰芝幺：左 第一章绪论 第一章绪论 1 1 移动自组织网络概述 目前的移动通信网络主要有两类，一类是有固定设施支撑的网络，如：g s m ， 移动节点借助于通信范围内最近的基站实现通信。另一类则是无固定设施支撑的 网络，即移动自组织网络m a n e t ( m o b i l e a dh o cn e 附o r k s ) 。它是分布式的网络， 由一组带有无线通信收发装置的移动节点组成，是一个多跳的临时性无中心网络， 可以在任何时刻、任何地点快速构建起一个移动通信网络。 在a d h o c 网络中，当两个移动主机在彼此的通信覆盖范围内时，它们可以直 接通信。但是由于通信覆盖范围有限，如果两个相距较远的主机要进行通信，则 需要通过其它的移动主机转发才能实现。因此，主机同时是路由器，负责寻找路 由和转发报文的工作，而路由一般都由多跳组成，数据通过多个主机的转发才能 到达目的地，故a d h o c 网络也被称为多跳无线网络。 移动自组织网络的前身，是美国国防高级计划研究署( d 眦) 于1 9 7 2 年所研 发的分组无线网( p r n e t ，p a c k e tr a d i on e 咖r k ) 项目，主要是研究战场环境下利用 无线通信手段多个独立节点间的数据分组传输。在此项目的基础上，1 9 9 3 年 d a r p a 又启动了高残存性自适应网络项目，研究如何将p r n e t 的成果加以扩展， 以支持更大规模的网络，在网络协议方面，要求具有自主组网的能力并且能够适 应战场环境的快速变化。1 9 9 4 年，d a 融) a 又启动了全球移动信息系统项目，在已 有成果的基础上全面深入研究军事应用需要的、可快速展开的、高抗毁性的移动 通信系统，并一直持续至今。1 9 9 1 年成立的i e e e 8 0 2 1 1 标准委员会采用了“a dh o c 网络”一词来描述这种特殊的对等式无线移动网络。 移动自组织网络具有极大的灵活性和可扩展性，它不需要依赖于固定的基础 结构，既可以与现有的网络结合形成多跳网络，有效地延伸传统网络的覆盖范围， 同时也可以通过临时组网的方式在恶劣环境中支持移动节点之间的数据、话音、 图像等业务的传输。9 0 年代以来，移动a dh o c 网络的研究在世界范围内方兴未艾， 已经从无线通信领域中的一个小分支逐渐扩大到相对较独立的领域。综合国内外 的研究现状，a dh o c 网络成果主要在以下几个方面： ( 1 ) 提出新的路由协议。a dh o c 路由面临的主要挑战是：传统的保存在节点中 的分布式路由数据库如何适应网络拓扑的动态变化。新协议一般以广播或组播方 式建立网络路由，核心是减少广播风暴。目前，一般普遍得到认可的代表性成果 有d s d v 、w r p 、a o d v 、d s r 、t o r a 和z r p 等。源头性的创新性研究主要集 2 移动自组织网络路由技术研究 中在2 0 0 1 年以前，后续的成果多为这些协议的改进，目前，路由协议的研究仍然 是a dh o c 网络成果最集中的部分。不过，从实现的难度来看，这些协议离适用性 还有一定的距离。 ( 2 ) 提出基于a dh o c 网络的媒体接入控制( m a c ) 协议。主要是解决隐藏终端和 暴露终端问题，影响比较大的有m a c a 协议，即r t s c t s a c k 方案，控制信道 和数据信道分裂的双信道方案和基于定向天线的m a c 协议，以及一些改进类的 m a c 协议。有一些研究则是侧重于将i e e e8 0 2 1 1 的m a c 协议移植到a dh o c 网 络中。基于定向天线的m a c 协议在理论上性能较为优越，但在技术上实现的难度 较大。 ( 3 ) a dh o c 网络与蜂窝网的互连互通。有文章提出了一种i c a r ( i n t e m e tc e l l u l a r a 1 1 d a dh o cr e a l y ) 系统，提供蜂窝小区内信号的补盲。该方案给出了在加入补盲点 之后系统性能改善的性能评价。从结果看，该系统只是针对2 g 系统，尚无法联系 到基于i p 方式的分组网络。最近，有人提出了一种在蜂窝网上覆盖一个无线多跳 网络的方案，其中用一些无线路由器来代替蜂窝网络中的一些节点。通过优化路 由、信道规划和功率控制等使系统在发射功率受限的情况下达到系统吞吐量最大 化，其他方面没有太多的贡献。 ( 4 ) 基于a dh o c 网络的多播组播协议、t c p 协议、地址分配、功率控制、安 全性问题、q o s 等方面有一些研究成果，但各部分的数量相对较少。其中，有些 研究试图把移动d 扩展到a db o c 网络，基本方案是要用特定的r j p 协议( r o u t i n g i n f 0 肌a t i o np r o t o c 0 1 ) 作为路由协议，但这种方案与a dh o c 网络的其他路由协议不 相容。 由于其组网快速灵活、抗毁性强、支持大范围内的移动性，无基站支持等特 点，移动自组织网络已经成为现代军事和民用通信系统的一个重要组成部分。这 些特性使得a dh o c 网络可以满足不同场合的特殊需要，其应用范围覆盖工业、商 业、医疗、家庭、办公环境、军事等各种场合和行业。特别是在军事应用领域中， 因其特有的无需架设网络设施、可快速展开、抗毁性强等特点，移动自组织网络 已成为数字化战场通信的首选技术。 1 2 移动自组织网络的路由协议概述 由于移动自组织网络的独有特点，使得路由技术成为这种网络的关键技术之 一。目前，国内外的许多学者对这一技术做了大量的工作，并且取得了相当的成 果。路由协议可以分为以下三种： ( 1 ) 平面式路由( f l a tr o u t i n g ) 算法。网络中的所有节点都处于同一层次上，各节 点在网络中获得的路由信息基本相同。根据其设计的具体原则可进一步的将平面 第一章绪论 式路由分为表驱动路由( p r o a c t i v er o m i l l g ) 算法和按需路由( r e a c t i v er o u t i n g ) 算法。 ( 2 ) 分层式路由( h i e r a r c l l i c a jr o u t i n g ) 算法。网络按一定的规则分为多个不同的层 次，在不同层次中又可以有不同的路由策略。分层的路由策略比较容易进行网络 规模的扩充。 ( 3 ) 地理位置辅助的路由( g e o g r a p m cp o s i t i o na s s i s t e dr o u t i n g ) 算法。网络中的节 点可以获得节点的地理位置信息，通过这些信息可以有效地降低路由算法中路由 建立或维护的开销。 一、平面式路由 在平面结构的路由协议中，网络结构比较简单。网络中的节点处于平等的地 位，它们所具有的功能完全相同，共同协作完成节点间的通信。平面式路由协议 包括：a o d v ，d s r ，a b r ，d s d v ，w r p ，t o r a ，f s l s ，o s l r ，f s r ，s s r 【l - 8 】 等路由协议。按照具体的寻址规则，一般又可划分为表驱动路由协议和按需路由 协议。 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 l l c ev e c t o r ) 和无线路由协议w r p ( w r e l e s s r o u t i n gp r o t o c 0 1 ) 等。 d s d v ( d e s t i i l a t i o ns e q u e n c e dd i s t a r l c ev e c t o r ) 路由协议是一种无环距离向量路 由协议，它是传统分布式b f 路由算法的改进。在d s d v 中，每个节点都维持一 个路由表，每个表都有一个由目的节点设定的序列号，用于区分路由的新旧程度。 因为需要周期性的更新，d s d v 为了建设一个可用的路由需要较长时间使路由协 议收敛，并不适合延时敏感业务。 w r p ( w i r e l e s sr o u t i n gp r o t o c 0 1 ) 是基于无环路路径发现算法，它也是一种距离 向量路由协议。每个节点包含距离表、路由表、链路费用表和消息重传表4 张表。 距离表包含通过每个邻居节点到达目的节点的距离，它也包含每条路径上的邻居 节点的下一跳节点。路由表包含到目的节点的距离、本节点的前驱节点和后继节 点以及该表项是一个简单路径或是一个回路或是无效路径的标签。链路费用表包 含从节点到所有邻居节点的链路的费用。消息重传表包含邻居节点是否确认它的 更新消息，如果邻居节点没有确认更新消息，就重传更新消息到邻居节点。 2 按需路由：相对表驱动路由协议而言，按需路由只有在需要发送数据时才开 始寻找路由，因此，源节点必须等待一段时间，等到路径建立完成才能开始发送 数据。按需路由的优点是不需要周期性的路由信息广播，从而节省了一定的网络 4移动自组织网络路由技术研究 资源，缺点是当有数据分组要发送时，如果没有去往目的节点的路由，数据分组 需要等待因路由发现引起的延时。典型的按需路由协议有源路由协议 d s r ( d y n a 缸cs o u r c er o u t i n g ) 和按需距离向量协议a o d v ( a db o co n d e m a n d d i s t a n c ev & t o r ) 等。 d s r ( d y n 锄i cs o u r c er o u t i l l gp r o t o c 0 1 ) 协议允许源节点动态地寻找路径，每 个待发送的数据包都带有完整的，包括从源节点到目的地所有节点( 包括源及目的) 的一张地址列表。这张地址列表指出了该数据包经过怎样的路径到达目的地。通 过该表，每个数据包都可以独立找到目的地，而不需要中间节点存储路径信息。 它的特点在于不需要维持路径信息表，只有在发送数据时才启动寻址协议。 a o d v ( a dh o co n d e m a l l dd i s t a l l c ev e c t o rr o u t i n g ) 是d s d v 的改进型，通过 按需路由来降低d s d v 中控制报文的数目，从而提高系统效率。为了查找到达目 的节点的路由，源节点广播一个路由请求砌汪q 消息。它的邻居收到广播消息后 再次广播，直到请求消息到达目的节点，目的节点发出路由响应消息，源节点收 到响应后，它就可以得知到达目的节点的路由。a o d v 还包括路由维护部分，实 现当路径上的中间节点移动时对缓存路由的修改和删除。 平面式路由协议的优点是：由于网络中不存在特殊的集中控制节点，节点间 的流量较均衡；当一个节点发生拥塞或故障时，其相邻节点可以承担起分组报文 的转发任务，系统的可靠性较高；减少了单点故障现象发生的概率，因此平面路 由协议的鲁棒性较好。 平面式路由协议的缺点是：由于平面路由协议一般没有节点移动性管理任务， 随着网络规模的扩大，节点个数的增加，路由时延和耗费将逐渐增加，因此平面 式路由协议的扩展性较差，主要用于中、小规模的网络。 二分层式路由 随着网络规模的逐步扩大，网络中节点个数不断增加，每个节点要想维护整 个网络的拓扑信息或选择合适的路由到远端节点将十分困难，而分层式路由则可 以很好地解决这个问题。 前面阐述的在平面式路由协议中，所有节点功能都是对等的。而在分层式路 由协议中，层次指的是一个“簇”( c 1 u s t e r ) 或“区 ( z 0 n e ) ，一般可以采用两种方 法进行分层。一种方法是隐式地分层，每个节点属于一个本地范围，范围内外使 用不同的路由策略，范围中的节点要进行选路，这种方式称为逻辑分层。另一种 方法是将地理上紧密相联的节点组成一个显式的簇，每个簇选举一个簇首，簇内 节点与簇首节点直接通信，是单跳的，这种方式称为物理分层。网络由若干个节 点组成，在层次内的节点间采用表驱动路由算法，在各层次间采用按需路由算法。 常见的分层式路由协议包括：c b r p ，h s r ，l a n m a r ，c g s r ，d d r ，c e d a r ， g s r ，h a r p ，z l 心等，下表1 1 对一些常见的分层式路由协议进行了比较。 第一章绪论 表11 分屡式路由协议的特性 e 女t m r m m b h m m f 蛔峰呻h 崎 分层路由协议的优点是：网络中的节点被划分为不同层次分别管理和路由， 网络的扩展能力强，因此适合大规模网络。分层路由协议通过组合使用按需获取 和预先获取等路由策略，避免了表驱动路由协议中过量的控制消息流量问题和按 需路由协议中的长时延问题。 分层路由协议的缺点是：由于簇首节点负责管理和维护本簇节点的通信，当 簇首节点出现故障时，可能会影响整个簇的通信，即簇首节点的稳定性和可靠性 将在很大程度上决定若整个系统的稳定性和可靠性。同时，随着节点不断地移动， 簇的维护和管理相对平面式路由协议也复杂得多。 三、地理位置辅助的路由 前面介绍的平面式和分层式路由协议中，节点仅仅知道自己的逻辑名称( 如地 址信息1 ，通过路由探测可咀获得网络中节点之间的链接关系和链路特性，由此确 定路由。随着定位技术的发展，节点可以方便地获得自己的地理位置信息。利用 这些位置信息可以改善自组网的路由性能，所以人们开始致力于研究使用位置 信息的路由协议。 l a r ( l 0 c “0 n - b a s e dr o u 血g ) 是利用源节点的物理位置信息来控制路由查找 范围的协议。主要思想就是利用g p s 数据信息，通过限制路由发现的洪泛，来减少 控制报文的数量。具体而言，就是利用g p s 数据信息，使洪泛在一个定义好的区域 ( 例如矩形区域1 内进行。类似的，还有r d m a r f r e l 撕v ed i s t a n c em i c 州i s c o v e r v a d h o cr m n i n g ) 协议和l o t a r ( l 0 c 缸i 叽t a i d e dr o u l i n g ) 协议。 地理位置辅助的路由协议的优点是：在自组网中利用位置信息，可以使节点 在寻找路由时避免简单的泛洪。若利用相邻节点或目的节点的位置信息，可以提 高路由寻找的效率。 地理位置辅助的路由协议的缺点是：节点获得自己的地理位置信息常常需要 专用定位系统如g p s ( g l o b 甜p o s 赫曲gs y n 盯n ) ，因此成本较高、建网相对复杂、 同时安全性比较低。尤其在战场环境下，敌方如果截获了作战军备的地理位置， 后果将不堪设想。 6移动自组织网络路由技术研究 综上所述，现有的路由协议可以归类为按需路由，表驱动路由，分层式路由 和地理位置辅助路由协议。但是在移动自组网中，这四种协议都存在着不足p 叫： 按需路由( 如a o d v ) 协议时延较大，并且q o s 不容易得到保证，如果节点移动比较 频繁，寻找路由的开销也较大；表驱动路由协议( 如d s d v ) 虽然寻找路由较快，但 是需要移动节点之间交互整个路由表的内容，从而消耗太多的带宽；地理位置辅 助路由协议虽然有发展前景，但是在当前要实现它，花费很昂贵。 采用分层路由方案虽然可以获得可扩展的路由，但是分层式路由协议的一个 特点是把节点划分成不同的群，并对群内外的节点指定不同的功能，网络拓扑结 构的细节通过节点的层层聚合被隐蔽起来。这种方式会使分层路由隐含着不足： 第一，大部分分层式结构协议的移动管理比较复杂；第二，一旦关键节点如群首 或网关节点失效，网络的可靠性可能会下降：第三，为了保证分群收敛，很多分 群算法都假设节点处于静止状态，但在实际的无线环境中，很难保证节点不出现 消失，开机或者移动的情况；最后，分群算法还要解决隔离问题，隔离问题是指 虽然存在可用的无线路径，但是分群却不相连。因此，分层式结构虽然具有可扩 展性，但是协议较脆弱，并且鲁棒性不如平面型路由协议。 正是因为现有的路由协议存在着不足，如何设计出性能良好的路由协议成为 了移动自组织网络所面临的一个挑战。 1 3 本文主要研究内容 本文内容主要分为以下几部分： 第一章介绍了移动自组织网络，并介绍了现有的适合于移动自组织网络的路 由技术，并分析其优缺点。 第二章重点研究了基于组移动的自适应路由协议a z r ( a d a p t i v ez 0 n er o u t i n g p r o t o c 0 1 ) 的工作原理。首先，构造了协议在网络仿真工具o p n e t 下的网络模型， 节点模型和进程模型；其次，仿真路由协议a z r 、f s r 和z i 冲，并将三者进行比较： 最后，从分组方式、信道速率、移动速度和网络规模方面对基于组移动的a z r 路 由协议完成详细的仿真和分析。 第三章在a z r 协议的基础上提出了适用于m i m o 信道的m a z r ( m i m 0 a d a p t i v ez o n er o u t i n gp r o t o c 0 1 ) ，并给出优化后的数学分析，最后从业务量、节点 密度和移动性方面进行仿真和性能分析。 第二章基于组移动的a z r 协议的设计和仿真 第二章基于组移动的a z r 协议的设计和仿真 在移动自组织网络中，路由协议会受到网络规模，无线信道通信质量，移动 性等因素的影响，而移动性被视为移动自组织网络中控制与管理的主要障碍。如 果节点的移动速率很快，网络的拓扑结构经常发生变化，原有的路由信息也将动 态地改变，随之而来节点广播更新的链路信息，将会极大地消耗有限的网络资源， 甚至造成网络拥塞。由节点的移动引起拓扑的变化，不同的移动模型对不同网络 协议的性能具有不同的影响。在对基于移动网络的系统或协议进行设计或分析评 价时，应该选择一种与现实情况相符合的、描述节点移动方式的模型。在基于不 同模拟环境的应用中，存在多种不同的移动模型：如果研究对象是一个单独的实 体，或者有很多移动实体但彼此之间是彼此独立的，则称之为实体移动模型；如 果研究对象是一组实体，它们之间的运动是彼此相关的，则称之为组移动模型。 本章主要研究的是组移动模型对协议的影响。 本实验室提出的鱼眼自适应区域路由协议f a z i 冲【眨1 ( f i s h e y ea d a p t i v ez o n e i 沁u t i n gp r o t o c 0 1 ) 是一种综合平面式路由协议和分层式路由协议的优点，适应于大 规模a dh o c 网络的路由解决方案。f a z r p 路由协议的基础是z r p 路由协议i ”】和 鱼眼技术l 】。f a z r p 与z i 冲的相同之处是：协议都属于分区路由协议，区内路由 采用主动路由协议，区间路由采用按需路由。但是它与z r p 有两点不同：首先， 它的区内路由协议采用了鱼眼技术，节点以不同的频率向邻居节点广播路由表条 目信息；其次，f a z i 冲协议采用区域半径自适应技术，区域半径会根据网络的实 际通信环境而自动调整到一个合适的值。因此，f a z r p 具有三个特点，首先它具 有区域路由协议的框架，其次它的区内路由协议引入了鱼眼技术，最后它的区域 半径会随着网络的变化并达到一个适应当前网络拓扑结构的值。 本文在前人研究的基础之上，对f a z i 冲协议进行改进，分析采用 l a n m a r ( l a i l d i l l a r kr o u t i n gp r o t o c 0 1 ) 1 5 1 7 】路由协议的组移动技术对路由协议的影 响。我们引用f a z r p 协议的区域路由技术和鱼眼路由技术，将协议简化命名为自 适应区域路由协议a z r ( a d a p t i v ez o n er o u t i n gp r o t o c 0 1 ) ，本章将重点研究基于组 移动的自适应区域路由协议a z r 的设计和仿真。 2 1a z r 协议的区域路由和鱼眼路由技术 一、区域路由技术 区域路由协议z r p ( z o n er o u t i n gp r o t o c 0 1 ) 是一种混合使用主动路由策略和按 移动自组织网络路由技术研究 需路由策略的自组网路由协议。网络中的所有节点都有一个以自己为中心的虚拟 区域，区域内的节点数目与设定的区域半径有关，因此z r p 的区域重叠程度很高。 这也是z r p 与显示分群路由的区别。在区域内使用先应式路由算法，中心节点使 用主动路由协议维护一张到区域内其他成员节点的路由表。对于区域外节点的路 由则使用按需路由策略。 z r p 协议实体主要由三部分组成：区域内路由协议i 6 时【1 8 l 、区域问路由协议 i e r p 以及边界广播解析协议b r p ，如图2 1 所示。 图2 1z r p 体系结构组成 其中，n d m ( n e i 曲b o rd i s c o v e r m a i n t e n a n c ep r o t o c 0 1 ) 主要是为i a p r 提供一个 中断，通知其发现有新的邻居节点加入或者是收到新的路由信息，一般是在m a c 或链路层中实现。区域内路由队i 心是一种有限区域内的主动式路由协议，通过 对本地网络中节点的监控，提供了一种有效的路由确认和维护手段。如果目标节 点是本地的话，路由直接可以获得，避免了路由发现过程中的控制报文开销和时 延；当路由目标节点位于区域外的情况时，则是通过正r p 协议发起全局路由查找 过程，同时使用更为有效的边界广播解析协议( b i 冲) 进行路由查询信息的转发与节 点查找。 二、鱼眼路由技术 在区域内路由策略中引入鱼眼技术，每个网络节点根据本区域内其他节点到 它的跳数动态调整路由表中对应路由条目的发送频率，使得节点之间交互的信息 量比传统的d s d v 大大减少，并且达到在大规模无线自组织网络中快速找到路由 的目的。 如图2 2 所示，黑色，灰色和白色的节点分别表示到中心节点距离为一跳，两 跳，和三跳及三跳以上的节点。对于中心节点5 ，它将它所维护的路由表中的不同 路由条目以不同的周期发送出去，与节点5 距离越近，交互路由信息就越频繁。 图2 2 鱼眼区域 第二章基于组移动的a 乙r 协议的设计和仿真9 与中心节点越近，信息交互就越频繁，反之则交换频率越小，这使得每个节 点都可以获得其邻近节点准确且详尽的信息。虽然随着与中心节点的距离加大， 信息的准确性降低，但这并不影响路由的正确选择。这是因为：即使网络节点没 有远距离节点的准确信息，但当传送的分组离目的节点越近，路由信息将越来越 准确。通过这种算法可以降低因交互路由信息而产生的网络负荷，比较适合大规 模的网络场景。 2 2 基于组移动的a z r 路由协议 2 2 1a z r 的组移动原理 组移动是指单个节点的运动方式和运动状态依赖于组内其他节点的运动状 态。组移动模型侧重于组内节点的相对运动，但组与组之间的相对运动又体现个 体移动的特点。组长是每个组的参考节点，负责设置每个组的移动参数。成员节 点收到组长的移动信息后，以和组长相同的移动参数进行相应的移动，表现出以 组为单位的整体移动。 l a n m a r ( l a n d m a r kr o u t i n gp r o t o c 0 1 ) 1 9 】是一种基于组移动模型的层次化路 由协议。在大型网络中，有些节点趋向于在一起作为一个群体做相同的运动，因 此根据群体的移动性，节点被划分为不同的群组。l a n m a r 使用路标( 1 a j l d m a r k ) 的观点来保持逻辑群组的路径，每个逻辑群组有一个动态选定的节点作为一个路 标。 基于组移动的a z r 协议采用了l a n m a r 的路标的选择和更新算法，具体的 原理为： ( 一) 当网络初始化时，我们按照一定的规则设置好节点所属的组号，通过一段 时间路由信息的交互，所有节点都可以获得网络的局部信息，如果某个节点的区 域内所含有的邻节点数目大予某个门限值则宣布自己为本组的组长。 ( 二) 如果一个组中有多个节点都宣称自己为组长节点，则推荐节点i d 号最小 的做为组长节点。网络中的所有节点都要按照对应的原则更新自己的状态，而节 点的移动都限制在一定的范围内。当不同小组的节点移动到了相互的通信区域内 时，路由表仍然根据所处的地理位置按照跳数更新，而运动状态表却只按照本组 组长节点的运动参数来更新。 ( 三) 当某个小组的组长失效或者不在小组成员的通信范围时，小组成员需要重 新选取一个组长节点，当新的组长选定后，该组长需要更新自己的运动状态表， 负责把自己的运动参数通过广播包发送给本组内的所有成员。 1 0移动自组织网络路由技术研究 2 2 2a z r 的组移动操作 a z r 协议中组移动策略的具体操作如下： 一、节点的初始化 在a z r 协议刚开始，节点知道自己所属的组号，这一条件符合大部分网络的 实际情况。若节点不知道自己所属的建制( 即组号) ，节点在开机后，如果先听到 某个组长的信息，就加入该组，成为该组的成员，否则，申明自己是组长，发布 新组的信息。 二、组长节点的选取和变更 若节点知道所属的建制，则根据路由表，如果发现在自己的路由范围内，与 自己在同一组号的节点有一定的数量( 如n ) ，则宣布自己为该逻辑小组的组长节 点，并通过随后的拓扑更新消息，捎带广播信息至邻居节点。如果有两个或两个 以上的节点宣布自己为同一个逻辑小组的组长节点，则选择i d 号最小的节点作为 组长节点。为了避免出现组长节点的频繁交替，a z r 采用滞后算法，仅当新的组 长节点可达的同一逻辑小组内的节点数目比旧的组长节点可达的同一逻辑小组内 的节点数目多出一个门限值时，才进行组长节点的更新。 若节点不知道所属的建制，则采用“先声明先赢的方法。节点开机后的一 小段时间内，首先查看是否收到过别的节点声明组长信息，如果没有，则认为自 己是组长，在下次发送s o p 信息的时候声明自己是组长。如果有两个或两个以上 的节点宣布自己为同一个逻辑小组的组长节点，则选择i d 号最小的节点作为组长 节点，同样采用滞后算法。 三、组长节点失效的处理 当一个逻辑小组的组长节点失效后，组长节点的邻居节点会在给定的时间后 发现这一情况，与组长节点在同一逻辑小组的邻居节点将宣布自己为新的组长节 点并广播这样消息，网络中开始一轮新的组长节点选举过程。 四、组长节点运动信息的发送 a z r 协议中，移动子网中的组长节点采用随机路点( r a l l d o m w a y p o i n t ) 的移动 模型。节点移动时，会随机地在地形范围内选择一个目标位置，以指定的速度到 达目标位置后，驻留一段指定的时间，然后再次随机的选择下一个目标位置继续 移动。在每个运动周期m o b i l i t yi n t e r 、，a l 内，产生此次运动的目的地点、移 动速度和停留时间。通过这三个参数，组长节点计算出每个时间步长因子r 内的 横向偏移量缸和纵向偏移量缈，并将缸和缈捎带在路由信息中发送给组内成员 节点。 五、组员节点运动信息的接收 组内成员节点接收到含有运动参数的路由信息时需要做出如下反应： 第二章基于组移动的a z r 协议的设计和仿真 ( 1 ) 如果节点收到的含有运动参数的路由信息不是本组组长发送的路由信息， 则直接丢弃该路由信息。 ( 2 ) 如果节点收到的含有运动参数的路由信息是本组组长发送的路由信息，判 断此时的运动周期。如果该节点属于此运动周期，更新运动状态表中的运动参数缸 和y ，否则丢弃该路由信息。 ( 3 ) 组内成员节点f 根据新收到的运动参数进行移动时，每个时间步长因子血 内的实际偏移量等于运动状态表中的运动参数加上节点f 随机生成的新偏移量。即 缸( f ) = 缸+ 缸f ，缈( f ) = 少+ 少f ，其中缸f ，酬是节点f 一个时间步长因子丁内 产生的小的随机偏移量：缸，缈是节点f 运动状态表中当前的运动参数，是通过 更新组长节点的路由信息获得；缸( f ) ，缈( f ) 是节点f 此次运动的实际步长。 六、组的移动模式 由于组长采用随机路点移动模型，因而，在网络中整个组的移动是随机的。 在移动速度很快的情况下，组与组之间将会产生较大的干扰，甚至有些组与其他 组隔离，不能通信。因此，我们采用一种地理分隔型的群组模型【2 们。 地理分隔的模型，与某些节点只能呆在特定的区域的建制符合，如图2 3 所示。 整个区域被分解成许多相邻区间，不同的组群在不同的区间中活动。就如同一个 公司的办公大楼里，不同的部门( 财务部、开发部、市场部、售后服务部等) 在各自 区域实施相同的操作，而每个部门掌管一个分区，每个职员可以在各自的办公区 内进行活动。 时务蕊并发每 。 市场舔膏后旺务部 俞 盆三 伶 。 uuo 上专9 。 圆 。固 埘务部凰工：o 开发靠员工：o 市场舔员工：o 售寿溉务部员工 图2 3 地理分隔模型示意图 因此，我们通过限制组长的可移动范围，进一步地地理分隔，保证了网络的 拓扑和连通性。具体来说，每个组的组长只能在其允许的区域范围移动。如果移 动的距离超过了边界，就立即停止，等待着下一次的移动，而紧接着的下一次的 移动将迫使组长回到区域范围之内。 图2 4 是a z r 组移动的一个例子。组长节点产生运动参数，并通过路由信息 的交互将此运动参数发送至组内的成员节点；成员节点收到本组组长的路由信息 时，根据运动状态表的状态及策略更新运动参数。 1 2移动自组织网络路由技术研究 f 拿 图2 4 组移动操作示意图 组长的运动状态决定了整个小组的运动状态。当组长运动到某一位置时，组 内成员节点会呈现出“跟踪”组长的痕迹，但是组内的每个成员节点具有一定的 随机运动行为，将会随机运动到组长节点的周围。 本章将在2 4 节将对a z r 协议进行仿真，并与f s r 和z r p 协议进行比较；2 5 节将引入组移动模型，对其进一步地扩展，仿真和分析基于组移动的a z r 协议。 2 3 仿真模型设计 随着信息时代的来临，无论是升级现有网络、搭建新网络、还是测试新协议 都需要对越来越复杂的网络性能进行有效而客观的评估。这些要求使得网络仿真 技术已经逐渐成为网络规划、设计和开发中的主流技术。当前的主流网络仿真软 件有0 p n e t 和n s 2 。下面的仿真以o p n e t 为主进行说明。 o p n e tm o d e l e r 提供了三层建模机制，分别在进程层、节点层和网络层进行 由下到上的建模。进程模型( p r o c e s sm o d e l ) 的基础是用有限状态机f s m ( f i n i t es t a t e m a c l l i n e ) 来描述各种协议，各个状态再分别进行编程实现。节点模型( n o d em o d e l ) 由进程模型构成，可以组成完整的协议栈，真实的反映所建模设备的特性，各模 块间通过数据包和状态信息的传递来进行各种操作，进而实现设备的功能。网络 模型( n e t m o d e l ) 由节点模型组成，可以通过不同的拓扑设计来构造出各种不同的网 络结构。 我们用o p n e t 对基于组移动的a z r 路由协议进行三层建模。本节分别对网 络模型，节点模型和进程模型进行说明。 一、网络模型 本章的仿真场景设置都为4 0 k m 堆4 0 k m ，节点间的通信半径为5 k m 。下面给出 详细的说明。 如图2 ：5 所示，场景中分布了3 2 个移动节点、和一个r x g r o u p _ c o l l f i g 节点， 应用于2 4 节未采用组移动模型的a z r 协议与z i 心和f s r 的仿真。网络中节点通 过a z r 协议寻找路由并传送数据，r x g r o u 小0 1 1 f i g 节点用来控制节点的通信半径 和链路更新频率等网络参数。 第= 章基于组咎自 z r 协# 设计目* 真 图2s3 2 个节点的网络模型 对丽络中的9 0 个节点，我们初始化网络时采用了固定分组，划分为3 个小组， 6 个小组，9 个小组分别进行仿真，仿真场景如下图的26 中的( a ) ，( b ) 和( c ) 所示。 网络中的9 0 个节点分为3 组，6 组和9 组，组内成员均在组长的通信半径范围之 内。移动呈现为组移动的方式，各个成员节点的移动是随着组长的移动而进行相 应的移动，表现出以组为单位的整体移动。 煎盏 ：；：； 一i ：；! 1 蔓一 ( c ) 9 组 ：5 ： ；3 ： ： 图26 9 0 个节点的网络模型 6 组 嚼 & ： -l 一；：扎 ：t；弘 ； ； ，jf龟芦f 羹霹簿 一批罐 瑶譬魏孵 &：j： 组o ；沁 ：j ij。 9t u。| 熬 # 自自组纸月镕镕自技术研究 我们对网络规模进行扩大，节点的数目增加为1 8 0 个节点，固定分为6 组和9 组，仿真场景如图27 ( a ) 和嘞所示。分为6 组的网络每个小组包含3 0 个节点分 为9 组的网络每个小组包含2 0 个节点，组内成员均在组长的通信半径范围之内。 黪韵 鹱豢 黎罄 伯砸组 图27 】8 0 个节点的网络模型 我们介绍的同络模型将分别在后面的仿真中使用，其中，圈25 的网络模型将 应用于24 节的仿真，图2 6 和图27 将应用于25 节的仿真。 = 、节点模型 如图2g 所示，我们给出了节点模型。该节点由应用层、路由层、m a c 接入 层、m a c 层和物理层组成。 卣4 白 图2 8 节点模型 应用层由s o u r c e 梗块和s 础模块构成：s o u 咣模块模拟用户产生业务需求； s i n k 模块负责数据处理及销毁；路由层主要运行a z r 协议；m a c 层采用c s m a c a 算法，缓冲区大小设置为1 02 4 m b 虹；物理层采用o p n e t 自带的收发信机，信道 速率可调。 三、进程模型 国歪黪 第= 章基于组移动a z r 协议口计w 真 在对路由协议的仿真过程中，我们分别对上层的s o u r c e 模型和路由层的a z r 模块，以及节点的移动模型进行说明。 图2 9 所示的是上层业务模型s 。u 肼的具体进程。由于上层的业务模型对整个 网络的性能有着重要的影响，按照区域内业务交互最为频繁，区域外业务