（计算机软件与理论专业论文）移动自组网上的多播路由研究.pdf

摘要 移动白组网是一组带有无线收发装置的移动结点组成的一种多跳的无线网 络，没有基站等基础设施支持。本文首先通过刈其定义与历史的阐述，对其特点 和与其他移动网络系统的区别的分析及对其应用领域的讨论，简要介绍了这种 网络。接着阐述了移动白组嘲的体系结构驶关键技术，介绍了在该类网络上的几 种典型的路由方式然后集巾于多 爵路由的研究，网顾了在这种网络卜已有的多 播路由算法，探索了多播路由算法的设计与性能评估。 在已有的研究成果的基础【：，我们提出了基于动态蜂窝的多播路由协议 ( d c b m r p ) ，采用分层路由的思想，将表驱动与按需路由方式结台起来。该协 议首先使用分布式动态蜂窝生成协议d d c c 1 ，网络内的结点丰动获取局部网 络信息并按蜂窝结构组织起来，然后在有多播数据需要发送时，源结点所在蜂窝 的核心结点起动路由探测过程，以有限广播( 即仅蜂窝的核心结点与边界结点参 与信息处理) 的方式建立网格结构的多播路由，并且这个网格是共享的，也就是 说所有的同组的源结点，i - 同建立和使用这个捌格，多播数据沿9 c i | | 格发布即可到达 所有接收结点。 我们在网络仿真系统n s 2 上对d c b m r p 议进行了仿真实验，研究它的 性能。实验结果表明该算法具有延迟小、可靠性高、数据传播效率高，扩展性强 等特点，具有较岛的总体- 陛能。 关键字：移动自组网，多播路由协议，动态蜂窝，其享网格 ab s t r a c t m o b d ea dh o cn e t w o r k ( m a n e t ) i sa n e wk i n do fm u l t i h o pw i r e l e s sm o b i l e n e t 、v 1 1 k sw i t h1 1 ( 1f i x e dm f r a s l l l l c t u l e1 1c o n s i s l s 汀m o b i l el l t ) l e s ，w h i c ha r ce q u i p p e d w i t hw i r e l e s ss e n d e r sa n dr e c e i v e rsi nt h i s p a p e rw ei i r s t d e s c r i b et h i sn e t w o r kb y s t a t i n gi t sd e t i n i t i o na n dd e v e l o p i n gh i s t o r y , b ya d d r e s s i n gi t s c h a r a c t e r i s t i c sa n dt h e d i f f e r e n c e sb e t w e e ni ta n do t h e rm o b i l en e t w o r k s ，a n db yd i s c u s s i n gi t s p o t e n t i a l a p p l i c a t i o n w et h e ns t u d yt h ea r c h i t e c t u r ea n dp i v o t a lt e c h n o l o g yo ft h en e t w o r k s o m e t y p i c a lr o u t i n gm e t h o d s o ft h en e t w o tka r ei n t r o d u c e da l s oa f t e rt h a tw ef o c u s o nm u l t i c a s t r o u t i n gi n t h en e t w o r kw er e v i e was e to fc u r r e n tm u l t i c a s t r o u t i n g p r o t o c o l sf o r t h en e t w o r k s t u d yt h ed e s i g no t t h e p r o t o c o l sa n dt h e i rp e r f o r m a n c e o v a l u j a t i o n w e p r o p o s et h ed y n a m i c c e l l u l a r - b a s e dm u l l i c a s tr o u t i n gp r o t o c o l ( d c b m r p ) f o r m o b i l ea dh o cn e t w o r k si nt h i sp r o t o c o l ，w ee m p l o yt h ei d e ao fh i e r a r c h i c a lr o u t i n g ， w h i c hc o m b i n et h em e t h o d so fb o t h t a b l e d r i v i n g a n d o n - d e m a n d w e u s e d i s t r i b u t e dd y n a m i cc e l l u l a rc r e a t e ( d d c c ) p r o t o c o lt oo r g a n i z et h em o b i l en o d e s i nd d c c p r o t o c o l ，t h em o b i l en o d e s a r eo r g a n i z e di n t os o m e d y n a m i c c e l l u l a rs e t sb y g a t h e r i n gt h ei n f o r m a t i o no ft h ep a t i o f t h en e t w o r kp r o a c t i v e l yw h e nan o d eh a s s o r t i em u i t i c a s td a t a , t h ec o r eo ft h ec e l l u l a r ，i tb e l o n g st o ，b u i l d sam e s hb y l i m i t l f l o o d i n g ，i nw h i c ho n l yc o r ea n db o r d e rn o d e sp a r t i c i p a t et h em e s hi ss h a r e dw i t ha l l s e n d e r so ft h em u l t i c a s tg r o u pt h e nt h em u l t i c a s td a t ac a nb ed i s t r i b u t e dt h r o u g ht h e m e s ha n dr e c e i v e db ya l lr e c e i v e r s w es l u d yt h e p e r f o r m a n c e o fd c b m r i o nn s 一2n e t w o r ks i m u l a t i o n s y s t e m s i m u l a l i o nr e s u l t ss h o wt h a tt h e p r o p o s e dp r o t o c o l i sc h a r a c t e r i z e dw i t hi t ss h o r t d e l a y ，h i g hr e l i a b i l i t y , e f f i c i e n c ya n ds c a l a b i l i t y k e yw o r d s ：m a n e t , m u l t i c a s tr o u t i n gp r o t o c o l ，d y n a m i cc e l l u l a r , s h a r e dm e s h 移动自组网上的多擂路由研究 第一章移动自组网简介 引言 随着人们对摆脱有线例络束缚、随时随地可以进行如通信的渴望，近几年 来无线网络通信得到了迅速的发展。人们可以通过配有无线接口的便携计算机或 个人数字助理来实现移动中的通信。常见的移动网络通常是以蜂窝网络或无线局 域网等形式出现的，这些移动网络和无线通信技术是对固定有线网络的补充和发 展，它们需要同定基础设施的支持，并且一般采用集中式的控制方式。但在某些 特殊环境或紧急情况下，没有固定基础菠施，或者是有中心的移动通信技术并不 能胜任。比如，战场上部队快速展开和推进、发生地震等自然灾害后的搜索和营 救、野外科考等。因此在以上场合中迫切需要一种不依赖基础设施能够快速和灵 活配置的移动通信网络技术，移动自组网就是为满足这种特殊应用需求而产生 的。 移动自组网可以看作是移动通信和计算机网络的交叉，它是由移动结点组成 的一种临时自治的分布式系统。在移动自组网中，移动结点一般是带有无线收发 装置的便携式计算机、个人数字助理( p d a ) 等移动终端设备，它既是主机又是 路由器，网络通信使用计算机网络的分组交换机制，而不是电路交换机制。这种 网络具有无中心接入和多跳等特征。这些特性使得移动自组网技术涉及到了o s l 分层模型中的每一个层面。研究者已经在媒质接入问题、路由问题、多播路由问 题、电能管理问题、q o s 闯题、安全问题、传输层问题等方面发布了相关的研究 成果。在众多的难题中，多播，即一对多和多对多的信息交互，作为通讯网络中 的重要功能，在这种网络的适用场合中得到了广泛的应用，具有很高的研究及使 用价值，因而也成为我们关注的焦点。 在本文中，我们首先介绍了移动自组网的定义、历史、特点、与其他移动网 络系统的区别及应用领域，接着阐述了该类网络的体系结构及关键技术，介绍了 在该类网络上的几种典型的路由方式，然后集中于在该网络上一对多与多对多的 信息交互多播路由的研究，回顾了在这种网络上已有的多播路由算法，探索 了多播路由算法的设计与性能评估，接着我们提出了自己设计的一个多播路由算 法，基于动态蜂窝的多播路由协议d c b m r p ，并在网络仿真器上对该协议 做了仿真实验以考察其性能，最后对我们的研究进行了总结并对以后的研究作一 些展望。本文的内容将安排如下： 第一章，移动自组网简介。 壁型皇塑塑圭竺墨堡堕虫婴塞 第二章， 第三章， 第四章， 第五章， 第六章 移动自组网上的路由设计思想。 移动自组网上现有多播路由回顾。 d c b m r p 协议设计。 d c b m r p 协议性能评估。 结论及研究展望。 1 1 移动自组网的定义及历史 何为移动自组网? 根据m u r p h y & & a l 所给出的定义，一个移动自组网就是 “不依赖于任何固定通信基础设施的移动节点的短时间互联。连接与否取决于节 点间的距离和结合的自发性”。 移动自组网是移动通信技术和计算机网络技术的交叉。一方面，网络的信息 采用了计算机网络中的分组交换机制，而不是电话交换网中的电路交换机制；另 一方面，用户终端通常是配置有无线收发设备的便携式终端，可以随意移动或处 于静止状态。 在移动自组网中，取消了传统蜂窝移动通信网络中中心节点的概念，所有的 节点都可以随意移动并且是地位平等的，通过端对端( p e e r t op e e r ) 的对等通信 方式直接互联。每个移动终端兼备路由器和主机两种功能：作为主机，终端需要 运行面向用户的应用程序；作为路由器。终端需要运行相应的路由协议根据路 由策略和路由表参与分组转发和路由维护工作。在移动自组网中，由于终端的无 线传输范围有限，两个无法直接通信的终端节点就通过多个中间节点的转发来实 现通信。 移动自组网的历史要追溯到上个世纪7 0 年代，1 9 7 2 年美国国防部高级研究 规划署( d a r p a ) 资助了一项特别的研究分组无线网络( p a c k e tr a d i o n e t w o r k ，p 鼢厄t ) ，即让报文交换技术在不受固定或有线的基础设施限制的环 境下运行。最初的动机之一就是满足战场生存的军事需求。在战场恶劣的环境下， 通信设备不可能依赖已经敷设的通信基础设施，一方面这些设旌可能根本不存 在，另一方面，这些设施会随时遭到破坏。因此，研发一种能够快速自组成网的 网络技术，用以实现战场环境下安全可靠的通信就成了一种迫切的要求。在结构 上，这种网络是由系列移动结点组成，是种自组织的网络，它不依赖于任何 已有的网络基础设施。网络中的结点动态且任意分布，结点之间通过无线方式互 连，它将分组交换网络的概念引伸到广播网络的范畴。p r n e t 的研究开辟了移 移动真纽列上的多播路由研究 动自组网研发的先河。在此之后，d a r p aj 二1 9 8 3 年启动了廓残存性自适应网络 项目s u k a n ( s u r v i v a b l e a 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 l em o b i l ei n f o r m a t i o ns y s t e m s ) 项目，旨在对能够满足军事应用需 要的、可快速展开、高抗毁性的移动信息系统进行全面深入的研究。成立于1 9 9 1 年5 月的i e e e s 0 2 “标准委员会采用了“a dh o c 网络”一词来描述这种特殊的自 组织对等式多跳移动通信网络，a d h o c 的意思是“f o r t h i s ”引申为“内r t h i s p u r p o s e o n l y ”，即“为某种目的设置的，特别的”意思，即a dh o c 网络是一种有特殊用途 的网络。a dh o c 网络就此诞生。i e t f 也将a dh o c 网络称为m o b i l ea dh o c n e t w o r k 简称m a n e t ( 移动a dh o c 网络) 。不过，在2 0 世纪7 0 年代到9 0 年 代早期，这些研究内容在当时并没有公开，我们很难从公开的出版物上获得有价 值的理论与技术成果。由于移动自组网可以广泛地应用于战场通信指挥与控制、 警察与医疗部门的抢险救灾、传感器网络、课堂教育等众多领域，其战略意义非 常重要。9 0 年代中期，随着一些技术的公开，a dh o c 网络开始成为移动通信领 域个公开的研究热点。而后经过全世界科研工作者多年的共同努力，移动自组 网技术得到了巨大的发展，取得了长足的进步。 1 2 移动自组网的特点 移动自组刚主要具有如下显著特点： l 、无中心和自组织性 移动自组网中没有绝对的控制中心，所有节点的地位平等，网络中的节点通 过分布式算法来协调彼此的行为，无需人工干预和任何其他预置的网络设施，可 以在任何时刻、任何地方快速展开，并自动组网。它消除了中心节点，是一种完 全分布式的网络结构，因此具有很强的健壮性和抗毁性。 2 、多跳性 受节点发射功率的限制，节点的覆盏范围有限。当它要与其覆盖范围之外的 节点进行通信时，就需要中间节点的转发。此外，移动自组网中的多跳路由是由 普通节点协作完成的，而不是由专用的路由设备( 如路由器) 完成的。 3 、动态变化的网络拓扑结构 在移动自组网中，节点具有很强的移动性，还可以随时开机和关机，加之无 线收发器发射功率的时变性、地形对无线信号的影响，以及无线信道之间的相互 移动r f 纽阿j 二的多播路山研究 干扰使得移动终端间通过无线信道形成的网络拓扑随时可能发生变化，两且变 化的方式和速度都难以预测。具体的表现就是网络拓扑结构中代表移动结点的顶 点的增加和减少，代表无线信道的有向边的增加和减少，网络拓扑结构的分割和 合并等等。 4 、移动终端的局限性 移动自组网t k 移动终端具有灵巧便携的优点，但是这些便携式终端受体积、 容量的限制存在着固有的缺陷。例如，处理器性能较低，存储器容量较小，显示 屏等外设较为简单等，这些都给开发移动自组网上的应用程序带来一定的挑战。 5 、安全性较差 移动自组网面临的安全性威胁主要来自无线信道和网络的拓扑结构。无线信 道容易被窃听和干扰，而无中心和无组织的网络结构很容易受到主动攻击。由于 移动自组网节点处理能力有限，无法实现复杂的加密算法，更增加了被窃密的可 能性。 6 、有限的传输带宽 移动自组网底层采用无线传输方式，而无线传输所能提供的带宽资源较之于 有线传输方式要低很多。此外，无线信道之间的竞争所产生的信号衰减、冲突阻 塞以及噪声的影响，使得在移动自组网实际的传输带宽要远远低于理论上的最大 带宽值。 7 、网络的可扩展性不强 在目前i n t e r n e t 环境下，由于可以采用子网、无级域问路由( c i d r ) 和变氏 子网掩码( v l s m ) 等技术，从而增强了i n t e m e t 的可扩展性。但是动态变化的 拓扑结构使得具有不同子网地址的移动终端可能同时处于一个移动自组网中，因 而子网技术所带来的可扩展性无法应用在移动自组网环境中。 8 、存在单向无线信道 移动自组网采用无线信道，由于地形环境或发射功率等因素影响可能产生单 向无线信道。例如，车载移动结点的发射功率比便携移动结点大，因此可能产生 便携移动结点可以收到车载移动结点的信号，而车载移动结点收不到便携移动结 点的信号。即存在一条从车载移动结点到便携移动结点的单向信道，在常规固定 网络中则不存在这种情况。 9 、生存时间短 移动自组网不需要固定基础设施，通常是由于某个特定原因而临时创建的， 4 移动自纽删上的多播站由研究 使用结束后，网络环境会自动消失，因此其生存时问相对于固定网络而畜是短暂 的。 1 0 、 l 电涧题突出 考虑到成本和易于携带，移动自组网中的移动节点通常采用电池等易耗品作 为能量来源，所以如何减少应用程序的复杂度和计算量，以帮助移动终端节省能 量损耗、延长工作时问就是一个关键的问题。 1 3 与其他典型的无线网络的区别 1 、与常规移动通信网络的区别： ( 】) 有无网络通信基础设旌支持的差异 对于常规移动通信网络，如g s m 、c d m a 、c d p d 等，现有的网络通信基 础设施是指基站、基站路由器、收，发天线、移动交换机和相关的连接中继线路 等。这些设施的建设与运行维护的成本高、周期长。而移动自组网的主要特点就 是不需要同定基础设旖的支持，独立组网，网络的构成周期远远小于常规移动通 信网络。 ( 2 ) 通信模式上的差异 常规移动通信网络普遍采用基站支持，相应的通信模式是用户通信终端只能 与基站交互，而相互之间不能直接通信，因此这些网络的控制及处理功能主要由 移动交换机和基站完成，采用了集中控制的方式；而移动自组网中，结点之间是 对等的每个结点既是主机又是路由器，都必须承担为其他结点转发信息的义务， 所以控制方式是分布的。 ( 3 ) 交换机制及承载的业务类型的差异 常规移动通信网络的通信业务以话音业务为主，因1 i i | i 信息交换采用服务质量 有保证的、面向连接的电路交换机制；而移动自组网则是以数据业务为主( i p 流) ，幽_ 瓶采用的是分组变换机制，是计算机网络的种。 ( 4 ) n 络拓扑的稳定性不同 常规移动通信网络，尽管终端是移动的但由于基站的长期性网络结构是 比较稳定的；而移动自组网中，网络拓扑结构是变化的，这是它的个重要特征。 2 、与无线局域网的区别 ( 1 ) 结构不同 对于无线局域网和红外网络，从网络屠来看。是一个“单跳”的网络：而移 移动自组鄹上的多播路由研究 动自组网足一个“多跳”的网络。这个差异造成了下面的不同。 ( 2 ) 研究重点不同 无线局域网和红外网络，作为单跳的网络，报文的处理不通过网络层，其主 要的研究方向是物理层和数据链路层，如信号的编码、纠错、频率的复用、天线 的设计等：而移动自组网的研究方向是网络层，其中尤以路由协议为重点。 ( 3 ) 无线局域网和红外网络的通信模式与常规移动通信网络类似，通常是移动结 点通过无线访问a p ( 类似于基站和h u b 的功能) 与其他结点通信；而移动自 组网的通信模式是移动结点之间的对等通信。 1 4 移动自组网的应用 移动自组网的许多优良特性为它在通信领域占据一席之地提供了有利的依 据。首先网络的自组性提供了廉价而且快速部署网络的可能。其次，多跳和中 间节点的转发特性可以在不降低网络覆盖范围的条件下减少每个终端的发射范 围，从而降低设计天线和相关发射，接收部件的难度，也降低了设备的功耗，从 而为移动终端的小型化、低功耗提供了可能。从共享无线信道的角度来看，移动 自组冈降低了信号冲突的几率，提高了信道利用率。从对使用者的保护来看，高 功率的无线电波产生的电磁辐射对用户的身体健康也有影响。另外，网络的鲁棒 性、抗毁性满足了某些特定应用需求。它的应用场合主要分为军事领域和民用领 域两个方面。 1 4 1 军事领域 移动自组网是源于军事领域，并且军事应用始终是移动自组网技术的主要应 用领域。在现代化战争环境中，由于没有基站等基础设旖可用，或者出于保密的 目的不能使用卫星等大范围的通信系统，移动自组网因其特有的无需架设网络设 施、可快速展开、抗毁性强、通信范围有限等特点，成为了数字化战场通信的首 选技术，并已经成为战术互联网的核心技术。它可以支持野外联络、独立战斗群 和舰队战斗群通信、无人侦察与情报传输等任务，从而完成集中统一指挥，协调 作战。美国军方已经研制出大量的无线自组织网络设备用于单兵、车载、舰载、 指挥所等不同的场合，并大量装备部队。 例如：2 0 0 0 年2 0 0 3 年，美国国防部高级研究规划署( d a r p a ) 资助了一 6 移动自组网上的多插路由研究 项名为“自愈式雷场系统”的研究项目。系统采用智能化的移动反坦克地雷阵米挫 败敌人对地雷防线的突破。参与布阵的地雷都配备了无线通信和自组织联网模 块，通过某种方式布撒之后，这些地雷能够迅速地组成移动自组网。当地雷阵遭 到敌方的坦克突破之后，各个地雷节点通过无线方式传递拓扑结构变化的信息， 然后各：符点通过自动弹跳功能迅速自愈使通信网络重新连通，形成新一轮的地 雷阵。如此反复，直到系统无法重构为止再全部自行引爆。“自愈式雷场系统” 大大地限制了敌军的机动能力，延缓了敌军的行进速度，具有很强的战略意义。 1 4 2 民事领域 移动自组网不仅在军事领域r i l 得到了，。泛的应用，也开拓了广阔的民事应用 领域，可以归纳为以下几类： 1 、传感器网络 传感器可以工作在危险的环境中，对于很多应用场合来说传感器网络只能使 用无线通信技术，并且传感器的发射功率很小，将分散的传感器通过移动自组网 技术自组成网，可以实现传感器之间及与控制中心之间的通信。这种网络具有非 常广阔的应用前景。 2 、紧急和突发场合 在发生了地震、水灾、火灾或遭受其它灾难后，固定的通信网络设施都可能 无法正常工作。此时移动自组网能够在这些恶劣和特殊的环境下提供通信支持， 对抢险和救灾工作具有重要意义。此外当警察或消防队员紧急执行任务时，可以 通过移动自组网来保障通信指挥的顺丰q 进行。 3 、偏远野外地区 当处于边远或野外地区时，无法依赖固定或预设的网络设施进行通信。移动 自组网技术具有单独组网能力和自组织特点，是这些场合通信的最佳选择。 4 、临时场合 移动自组网的快速、简单组网能力使得它可以用于临时场合的通信。比如会 议、庆典、展览等场合。可以免去布线和部署网络设备的工作。 5 、动态场合和分布式系统 通过无线连接远端的设各、传感节点和激励器，移动自组网可以方便地用于 分布式控制，特别适合于调度和协调远端设备的工作，减少分布式控制系统的维 护和重配置成本。移动自组网还可以用于在自动高速公路系统中协调和控制车 7 移动自组耐f ：的多播蹄由研究 辆，对工业处理过程进行远程控糊等。 6 、个人通信 通过移动自组网把个人通信、娱乐、办公等设备联网，这些设备可以不需要 与因特网相连，但在执干亍用户的某项活动时肯定需要彼此通信。考虑到电磁波的 辐射问题个人域通信设备的无线发射功率应尽量小，这样移动臼组网的多跳通 信能力将再次展现它的独特优势。 7 、商业应用 组建家庭无线网络、无线数据网络、移动医疗监护系统和无线设备网络，开 展移动和可携带计算以及无所不在的通信业务等。 8 、传统话音通信网络的末端网络 移动自组网已经开始被当作下一代移动通信嘲络的种应用方案，它作为传 统通信网络的末端网络，提供了移动用户无线接入核心网的一种方式。目前， 3 g p p 和3 g p p 2 已经把移动自组网的标准化作为了一项重要的研究内容。 9 、其它应用 考虑到移动自组网具有很多优良特性，它的应用领域还有很多，这需要我们 进一步去挖掘。比如它可以用来扩展现有蜂窝移动通信系统的覆盖范围，实现地 铁和隧道等场合的无线覆盖，实现汽车和飞机等交通工具之间的通信，用于辅助 教学和构建未来的移动无线城域网和自组织广域网等。 经过3 0 多年的发展，移动自组刚技术取得了巨大的进步，目前已经有一些 移动自组网产品投入市场。前些年，瑞士的s w i s s c o m 公司推出了“好友地带”服 务。该服务通过移动自组网设备进行通信，可以帮你认识周围的新朋友，和朋友 聊天，甚至对朋友盼位置进行定位。最近，手表制造商s w a t c h 发布了一种置于 手表内的名为s y n c h r ob e a t 的移动约会设备。该设备通过手表发出的声音向另一 手表传送信息。然后，根据双方各自在s y n c h r ob e a t 内填入的用户信息，相应的 算法就可以辨识出用户双方个人信息的匹配程度。 堡堡旦堡型! 塑童堡墅堕婴塞一 第二章移动自组网上的路由设计思想 2 1 移动自组网的体系结构 与o s l 的七层模型相对应，移动自组刚技术主要涉及到下三层，但同日j 对 上层也有部分关联和影响。其中物理层完成无线信号的编码、译码、发送和接收， 数据链路层控制对无线信道的访润，嘲络层则是移动自组嗣技术的核心。我们将 从结点结构和网络结构两个方面来分析移动自组网的体系结构。 2 1 1 结点结构 移动自组网中的结点不仅要具备普通移动终端的功能，还要具有报文转发能 力，即要具各路由器的功能。因此，就完成的功能而言可以将结点分为主机、路 由器和电台三部分。其中主机部分完成普通移动终端的功能，包括人机接口、数 据处理等应用软件，对应o s i 七层模型中的高四层；路由器部分主要负责维护 网络的拓扑结构和路由信息，完成报文的转发功能，对应o s i 模型中的网络层； 电台部分为信息传输提供无线信道支持，对应o s i 模型中的数据链路层和物理 层。从物理结构上，移动结点可以被分为四类：单主机单电台、单主机多电台、 多主机单电台和多主机多电台。手持机般采用单主机单电台的简单结构。作为 复杂的车载台，一个结点可能包括通信车内的多个主机。多电台不仅可以用来构 建叠加的网络，还可用作网关结点来互联多个移动自组网，或将其与i n t e r n e t 进 行互联。 2 1 2 网络结构 移动自组网一般有两种结构：平面结构和分级结构。 在平面结构中，所有结点的地位平等，所以又可以称为对等式结构。 分级结构中，网络被划分为簇。每个簇由一个簇头和多仓簇成员组成。这些 簇头形成了高一级的网络。在高级网络中，又可以分簇，再次形成更商一级的 网络，直至最高级。在分级结构中，簇头结点负责簇间数据的转发。簇头可以预 先指定，也可以由结点使用算法自动选举产生。 分级结构的网络又可以被分为单频分级和多频分级两种。荜频率分级网络 移动自绍网上的多播跆由研究 中，所有结点使用网一个频率通信。为了实现簇头之间的通信，要有网关结点( 同 时属于两个簇的结点) 的支持。而在多频率分组网络中，不同级采用不同的通信 频率。低级结点的通信范围较小，丽商级结点要覆盖较大的范围。高级的结点同 时处1 ：多个级中，有多个频率，用不吲的频率实现不同级的通信。在两级网络中， 蔟头结点有两个频率。频率l 用p 簇头与簇成员的通信。析频率2 用于簇头之问 的通信。分级网络的每个结点都可以成为族头，所以需要适当的簇头选举算法， 算法要能根据网络拓扑的变化重新分簇。 平面结构的网络比较简单，网络中所有结点是完全对等的，原则上不存在瓶 颈，所以比较健壮。它的缺点是可扩充性差：每一个结点都需要知道到达其他所 有结点的路由。维护这些动态变化的路由信息需要大量的控制消息。在分级结构 的网络中，簇成员的功能比较简单，不需要维护复杂的路由信息。这大大减少了 网络中路由控制信息的数量，因此具有很好的可扩充性。由于簇头结点可以随时 选举产生，分级结构也具有很强的抗毁性。分级结构的缺点是，维护分级结构需 要结点执行簇头选举算法簇头结点可能会成为网络的瓶颈。 因此，当网络的规模较小时，可以采用简单的平面式结构；而当网络的规模 增大时，应用分级结构。美军在其战术互联网中使用近期数字电台( n t d r ，n e a r t e r m d i g i t a lr a d i o ) 组网时采用的就是双频分级结构。 2 2 移动自组网上路由设计面临的挑战 路由技术是移动结点通信的基础，也是移动自组网的关键技术之一。 与一般的网络不同，移动自组网各结点问通过多跳数据转发机制进行数据交 换，需要专门的路由协议进行分组转发操作。无线信道变化的不规则性、结点的 移动、加入，退出等都会引起网络拓扑结构的动态变化。移动自组网路由协议就 是在这样的背景下产生的，其主要作用是在自组织网络环境中，建立各结点的路 由，同时，通过监控网络拓扑结构的变化来更新和维护路由。 传统的路由算法有两类：一是距离矢量路由算法( d i s t a n c ev e c t o r a l g o r i t h m ， d v a ) ，另一类是链路状态算法( l i n ks t a t ea l g o r i t h m ，l s a ) 。传统路由算法在有 基础设施的网络中运行得很好，但是在移动自组网环境中却存在以下问题和挑 战： 快速变化的网络拓扑结构 当拓扑结构发生变化后，传统路由算法需要花费较大的代价才能到达收敛状 移动丘 组网r 的多播蹄由研究 态，给网络造成很大的控制负荷。 有限的无线信道带宽 相对于有线信道，无线信道的带宽要有限得多；同时，路由消息的交换大大 减少了有效系统带宽，可利用的无线信道带宽殳是有限。 移动节点性能受限 移动结点一般采用可耗尽能源进行供电，而周期性的路由刷薪造成固定网的 睡眠模式无法应用，并加大了节点的能量消耗。 单向信道的存在 传统路由算法通常认为，底层的通信信道是双向的，但是在移动自组网中， 由于发射功率或地理位置等因素的影响，可能存在单向信道。它为传统路由算法 带来三个严重影响：认知的单向性、路由单向性和汇点不可大。 基于分布式无线网络体系结构，在无线带宽受限、多跳路由频率变化及网络 拓扑动态变化条件下，传统的路由算法和协议无法满足这些特性，需要专门的应 用于移动自组网的路由协议。路由协议的设计必须满足以下条件： 具备分布式操作功能，能对网络拓扑结构动态变化进行快速应变，尽量避免路 卣环路的产生，提供方便简单的网络结点定位方法。 高效利用有限的无线信道带宽资源，压缩不必要的开销。 尽量减少转发的数据量和转发时间，支持睡眠周期操作，节省结点受限的工作 能源。 支持单向信道连接，使在移动自组嘲中可能出现的单向信道连接可以正常操 作。 具有一定的安全性，降低结点遭受入侵、攻击和窃听的可能性。 具有良好的可扩展性，当网络规模扩大时，网络性能不至于大幅下降。 2 3 移动自组网上的路由方式 i e t f 的m a n e t 工作小组目前正专注予移动自组网路由协议的研究，提出 了许多协议草案，如d s r 、a o d v 、z r p 等路由协议。此外，研究人员也发表 了大量关于移动自组网路由协议的相关文章，提出了d s d v 、w r p 等协议。根 据路由触发原理，目前的路由协议大致可以分为表驱动路由协议、按需路由协议 和层次型路由协议三种。 移动自组网l ：的多播路由研究 2 3 1 表驱动方式 表驱动路由队议也称为主动路由协议或者先验式路由忱、议。其原理足每个结 点维护张包含到达结点路由信息的路由表。源结点一旦需要发送报文，可以立 即获得到达目的结点的路由。当网络拓扑发生变化时，更新路由表信息，并把这 个更新消息传遍整个网络。目前常用的表驱动路由协议主要有d s d v 、w r p 等。 ( 1 ) d s d v 2 】 在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 ) 协议中，每个结点都保 存着一个路由表，凡是有可能与该结点有连接的结点都记录在表中，并且连同到 这个结点的跳数也一并记录在其中。每一条记录都有一个相应的序列号，用来标 记所记录路径的陈旧与否，有效避免使用陈旧的路径，防止可能产生的环路路由。 其缺点是不支持单向信道，每一个结点都必须维护一个全网的路由信息表。因此， 在网络规模比较大的情况下，所需要的更新信息量是巨大的。 ( 2 ) w r p 3 w r p ( w i r e l e s s r o u t i n gp r o t o c 0 1 ) 协议中，每一个结点必须维护四个表：路 由表、距离表、链路状态表和消息重传列表。结点都通过这些保存着所有邻近结 点与该结点的连接状态。结点通过距离和倒数第二跳信息来进行寻路。如果一个 结点没有消息需要发送。它必须定期发送h e l l o 消息以声明其存在。在该协议中， 因为每个结点存储着与所有邻近结点的连接信息，因此可以使所建立的路径相对 优化。但是网络中维护了更多的信息，当拓扑变化导致结点间连接变化时，更新 网络中的信息所需要的开销也就更火。 2 3 2 按需方式 按需路由协议又称为随选型路由协议或者反应式路由协议，是专门针对移动 自组网环境提出来的。与表驱动路由协议相反，该类协议并不事先生成路由，而 是仅在源结点需要时才这样做。因此。路由表信息是按需建立的，它可能仅仅是 整个拓扑结构信息的一部分。按需路由一般包括两个阶段，路由发现和路由维护。 该类型中各路由协议的差别表现在发现路由的过程、取得和维护信息的方法、传 输数据的方式。主要包括a o d v 、d s r 和a b r 等协议。 ( 1 ) a o d v 4 】 1 2 移动自组网上的多插路由研究 a o d v ( a d h 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 ) 仂议在建立路由的方式 上对d s d v 进行了改进。在路由过程中，中问结点不需维护路由信息或参与路 由表交换。在路由发现阶段，当结点需要发送信息而又没有目的结点的有效路由 时，启动一个路由发现过程，向嘲络j 、播一个r r e q 分组。a o d 、r 允许中问结点 响应r r e q 。发现路由后，中间结点或目的结点以单播的方式向源结点发送一个 r r e p 分组，r r e p 沿着刚建立的逆向路径传输。因此，a o d v 不支持单向链路。 在路由维护阶段，当源结点得到链路中断消息后重启路由发现过程。a o d v 的 显著特点是引入了组播路由协议扩展，并通过序列号的方式解决了无限计数问 题。但与w r y 相似，它需要定期地发送h e l l o 报文，造成了一定的额外开销。 ( 2 ) d s r s 】 d s r ( d y n a m i c s o u r c er o u t i n g ) 协议基于源路由概念，数据分组头部必须包含 完整的路由信息，因此和a o d v 协议一样，中问结点可以响应r r e q ，但不需 要维护路由信息。与a o d v 不同的是，d s r 支持单向链路，并且在路由发现的 中继r r e q 阶段，中间结点需要将自己的地址加入到请求分组中，然后转发。 它的缺点是每个数据分组都携带了路径信息，造成协议开销较大，降低了带宽利 用率。 ( 3 ) a b r 6 】 a b r ( a s s o c i a t i v i t y - b a s e dr o u t i n g ) 协议的设计主要考虑到了移动自组网动 态拓扑的特点，引进了能表征链接持久性和传输质量的相关性稳定度 ( a s s o c i a t i v i t ys t a b i l i t y ) 概念。a b r 通过向相邻结点闻定期产生信标( b e a c o n ) 来表示自己的存在。当一个结点收到邻近结点发送过来的信标时，本结点就会对 相关性表( a s s o c i a t i v i t yt a b l e ) 进行更新。对于相邻的每一个结点相关性表中都 有其相关性计数，表示着该结点相对于本结点的稳定程度。这个相关性计数为路 由选择中路由的稳定度提供了一个重要的参考。该路由协议把所选路径的稳定性 考虑在内t 在一定程度上避免了路由在传输过程中发生中断，选挥的路由持久性 较好，质量也较高：同时由于结点运算量比较火，源结点需要等待比较长的时间。 2 3 3 分层方式 针对网络所采用的逻辑拓扑结构形式，路由协议又可以分为平面型( f i a t ) 和 层次型( h i e r a r c h i c a l ) 。前面阐述的表驱动路由协议和按需路由协议都属于平面型 的路由协议；而层次型路由协议则混合了表驱动路由协议和按需路由协议的优 壁塾皇堡翌圭堕查堡塑垒堑茎 点，因此又被称为混合型路由协议。在平面型路由协议中，所有结点功能都是对 等的；而在层次型路由协议中，层次指的是一个“群”( “c l u s t e r ) 或“区”( “z o n e ”) ， 它 1 】由若干个结点组成，在层次内的结点问采用表驱动路由算法，在各层次间采 j e l j 按需路由算法。 ( 1 ) c g s r 【7 】 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 ) 协议是在d s d v 协议基础上融 合分层次的思想设计的。协议采用l c c ( l e a s t c l u s t e rc h a n g e ) 算法，把移动自 组网划分成若干个簇，每一个簇中有个“簇首”( c l u s t e r h e a d ) ，而同时位于多 个簇的节点被称为网关。每个结点维护两种数据结构：路由表和簇成员表。结点 使用d s d v 协议，周期性地与同簇内的邻居结点交换簇成员表，更新表信息。 当一个结点要通信时，数据包首先传递给自己所在簇的簇首，然后通过网关到达 另外一个簇首，以此种方法穿过中间的分簇，到达目的结点所在簇的簇首，然后 再转发给目的结点。c g s r 通过分簇，大大减少了维护路由表所需要的信息量。 另外，采用这种路由的网络有比较好的扩展性，但其缺点是算法相对复杂，需要 定的执行代价。 ( 2 ) z p p s 】 z r p ( z o n er o u t i n gp r o t o c 0 1 ) 协议巧妙地结合了表驱动和按需路由协议的优 点，网络内的所有结点都有一个以自己为中心的虚拟区，区内的结点数与设定的 区半径有关。在区内使用表驱动路由算法，中心结点使用区内路由协议i a r _ p 维 持一个到区内其他成员的路由表，对区外节点的路由使用按需路由算法，利用区 间路由协议i e r p 建立临时的路由。z p p 的性能依赖于区域半径参数值。区域半 径应根据网络特征( 例如节点密度、节点速度等) 来确定。 2 3 4 三种路由协议比较 表驱动路由协议使结点维护的路由表可以较准确反映网络的拓扑结构。结点 一旦发送报文，可以立即获取目的结点路由，因此，该路由协议的时延较小，但 是协议需要付出大量的路由控制报文，开销较大。在网络规模和移动性增大到一 定程度时，大部分表驱动路由协议将不可行。 相反，按需路由协议不需要周期性维护尚未需要的路由，只有在发送报文之 前才需要获取路由，因此，产生的路由控制信息比表驱动路由协议要少得多。但 因为数据传输之前必须先获取路由，所以存在一定的时延。按需路由协议适用于 1 4 移动自组网上的多播路由研宄 | 硎络载衍不太重、节点移动速度不太人的场合。 虽然按需路由咖议和表驱动路由协议都备有其优缺点，但总体析言，按需路 由协议是针对移动自组网的特点设计的，更适合于移动自组网。而在层次型路由 协议巾，路由信息分层次转发，需要在全局传播的路由信息较少，降低了大型网 络的存储要求和通信载荷。因此，与前两种路由协议相比，具有更好的可扩展性 和更高的效率。但另一方面，层次性路由协议的移动管理比较复杂，在实施上存 在很多困难。 第二章移动自组网上现有多播路由叫顾 多插足种允i i ：个, - , j r 彩个发送一川ii i , j 锭趑r 、1 7 l n 0 数捌也刘多个| ；j 收斤的 h 络 术，jer fr 彩j 前数j j ：发送行你为彩j 衙汕j ! ，彩播数川 & 收打称为彩j 币升【按【改成 - j # 搔lr i 巴数 “【4 发送- j + j l ：l i j t 彩，衙p i l ，j fj l ! ，j 抽：jl 颤彩j 嚣引l | 1 i jj t t g j l l ，j 能 立l f 父j 、0 敬撕：乜，彩捕f 【i 人人的1 i 竹例? k ，船一! ：_ ：，i l 如 j 沦仃彩一p 个i l b l 、? 。7 j i ，r 牝个州 fr - h 条链蝻t f l - 送l t l的数删也