（计算机应用技术专业论文）移动自组网中泛播路由协议研究.pdf

摘要 移动自组网是一种自创建，自组织，自管理的网络。它是由一组 移动节点组成的多跳无线通信网络。与传统网络不同，移动自组网络 不需要固定的地面设备支持和管理。本文主要研究移动自组网络中泛 播路由协议对网络性能的改善，以及泛播在传输路径恢复中的应用。 本文对移动自组网的研究情况，包括发展历史，网络特点进行了 介绍和对路由协议进行了分类。并且讨论了泛播的基本概念，网络模 型和服务选择标准，对移动自组网络中的泛播研究现状进行了回顾和 分析。在此基础上，提出了两种移动自组网中的泛播路由协议a d s r ， a a o d v 。它们通过选择最优的泛播方法有效缩短传输路径，均衡网 络的负载，从而显著的提高网络性能。通过利用最权威网络模拟工具 之一n s 一2 对这两种协议进行测试，证实了泛播协议可以有效的改善 移动自组网的数据包传输率，数据包平均端到端延时，平均路由开销 等三项重要性能指标。鉴于泛播路由协议的优越性能，本文提出了一 种基于泛播和d s r 的改进协议q r d s r ，它充分利用节点路由缓存， 在源节点组和目的节组建立最短路径来恢复断裂的路径，从而降低路 径恢复时间，有效的提高移动自组网络的实时性能。模拟测试结果证 实了q r _ d s r 的优越性能。 关键字移动自组网，泛播，路由协议，快速恢复 a b s t r a c t m o b i l ea dh o c n e t w o r k ( m a n e t ) i s a s e l f c r e a t i n g ，s e l f o r g a n i z i n g ， s e l f _ a d m i n i s t r a t i n g ，n e t w o r k ，w h i c hc o n s i s to fm o b i l en o d e sc o r u l e c t e d b y m u l t i - h o pc o m m u n i c a t i o np a t h s u n l i k ec o n v e n t i o n a lw i r e l e s sn e t w o r k s a dh o cn e t w o r k sh a v en of i x e dn e t w o i k i n f r a s t l l l c t u r eo ra d m i n i s t r a t i v e s u p p o n t h i sp a p e rm a i n l ya d d r e s s e st ot h ea n y c a s t a p p l i e d i nr o u t i n g p r o t o c o l sa n d r e c o v e rm e b r o k e n 仃；m s m i s s i o n p a t h sq u i c k l y t oi m p r o v e n e t w o r k i n gp e r f b n l l a n c eo fm o b i l ea dh o cn e 聃o r k t h i s p 印e rs u m m a r i z e sa 1 1 da n a l y z e sm o b i l ea dh o cn e t w o r ki n a s p e c t s o fi t s h j s t o r ) p r o p e r t i e s ， a n dt h ec u r r e n t r o u t i n gp r o t o c 0 1 s r e s e a r c h e so na n y c a s ti nm o b i l ea d h o cn e t w o r ka r ea 1 1 a l y z e dw i t h t h ed i s c u s s i o no f c o n c e p t i o n ，n e t w o d d n gm o d e l ，a i l dt 1 1 es e r v i c ec h o o s i n g m e a s u r e so fa n c a s tt w oa n y c a s tr o u t i n g p r o t o c o l s ，a d s r p r o t o c o la n d a _ a o d v p r o t o c 0 1 ，a r ep r o p o s e d o nt h eb a s i so fa b o v e p a r t s t h e yi m p r o v et h ep e r f b n l l a l l c eo fm o b i l ea dh o cn e 铆o r kb y b a l a n c i n g n e t w o r kt r a 衔ca 1 1 dc h o i c i n gt l l es h o r t e s t p a t h t oa n y c a s t s e r v e r g r o u p a n dm e nm et w op r o 幻c 0 1a r eb o mt e s t e db yo n eo fm o s ta u t h o r i z e d n e t w o r k i n gs i m u l a t i n gt o o l s ，n e t w o r ks i m u i a 幻rv 2 ( n s 2 ) t h eb e t t e r n e t w o r k i n gp e r f b h i l a n c eo np a c k e td e l i v e r y 丹a c t i o n ，p a c k e te n d t o e n d d e l a y ，a n dn o r m a l i z e dr o u t i n gl o a di sp r o v e db yt e s tr e s u l t s aq u i c k r e c o v e r yp r o t o c o l ，q r - d s ri sp r o p o s e dw i t ha d v a n t a g e so fa n y c a s t i i q r - d s rp r o t o c o l c a n m l l y u s et h ec a c h e d r o u t i n g i n f o m l a t i o nt o e s t a b l i s has h o r t e s tp a t hb e t 、v e e ns o u r c en o d e s g r o u p a n dd e s t i n a t i o n n o d e sg r o u pt or e c o v e rt t l eb r o k e nt r 姐s m i t t i n gp a t h s s ot h er e a l t i m e n e t w o r k i n gc a nb ee n h a n c e de f f e c t i v e l yw i t has h o r t e rd u r a t i o no np a m r e c o v e r y t h i s p m t o c 0 1 sg o o dp e r f o m a n c ei s a l s o p r e s e n t e d i nt h e s i m u l a t i o nt e s t s k e yw o r d sm o b i l ea dh o c n e t w o r k ，a 1 1 y c a s t ，r o u t i n gp r o t o c o l s ，q u i c k r e c o v e n r i i i 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了论文中特别加以标注和致谢的地方外，论文中不包 含其他人已经发表或撰写过的研究成果，也不包含为获得中南大学或其他单位的 学位或证书而使用过的材料。与我共同工作的同志对本研究所作的贡献均已在在 论文中作了明确的说明。 作者签名：逢避日期：巡年二l 月三趾日 关于学位论文使用授权说明 本人了解中南大学有关保留、使用学位论文的规定，即：学校有权保留学 位论文，允许学位论文被查阅和借阅：学校可以公布学位论文的全部或部分内容， 可以采用复印、缩印或其它手段保存学位论文；学校可根据国家或湖南省有关部 门规定送交学位论文。 作者签名：辈坠锄签名避蹶塑年且月半日 硕士学位论文笫一章绪论 第一章绪论 1 1 移动自组网概述 移动自组网，又可被称为m a n e t ( m o b i i ea dh o cn e t w o r k l ，作为一种全新 的网络架构体系，已经成为目前移动计算的研究热点之一。它是由一系列移动主 机节点实时组成的多跳无线数据包交换和传输网络。与传统的无线移动网络不 同，移动自组网络中的所有节点都具有同等的地位，没有集中控制和管理的机制。 同时，每个节点也具有同等的功能，既充当主机又充当路由器，也不需要固定基 站与基干网的支持。因此，这种网络可以被运用于各种特殊和不利的环境，具有 更强大的适应性，更广泛的实用性。 11 1移动自组网络的历史发展 为了在没有地面设施支持和敌对的战场环境下，给移动的作战人员提供数据 包交换网络，美国国防部早在1 9 7 2 年就提出了包交换无线网络( p a c k e tr a d i o n e t w o r k ，或p r n e t ) 的研究，p r n e t 采用了a l o h a 和c s m a 作为媒体访问协 议，并且利用距离矢量协议作为路由协议。到了2 0 世纪8 0 年代初，美国国防部 在p r n e t 的基础上提出可靠自适应无线网络( s u r v i v a b l ea d a p t i v er a d i o n e t w o r k s 、或s u r a n ) 。与p i t n e t 相比，它的节点更小，更经济，并且更加节省 能量。由于采用了分层的链路状态路由算法，s u r a n 具有较好的可扩展性】。 移动自组网络在1 9 9 0 年以后开始步入民用化阶段。随着民用移动计算设备 的普及，以及各种射频和红外通信模块的涌现，基于商业化的无线自组网络( a d h o cn e t w o r k ) 的概念【2 j 也被正式提出，该种网络架构也迅速成为新的研究热点。 与此同时，美国国防部资助了两项无线自组网络的研究计划，分别是近距数 字无线通信系统( n e a r t e 肌d i g i t a lr a d i o ，或n t d r ) 和通用移动信息系统( g 1 0 b a l m o b l l ei n f 0 h n a t i o ns y s t e m s ，或g l o m o ) n 其中，n d t r 采用了两层自组织结构。 采用结合了分簇和链路状态路由。同时，n t d r 也成为了第一个真正投入军用， 而不只是原型的移动自组网络。它被美国第数字化师( f i r s t d i g i t a id i v i s i o n ，或 f d d ) 所采用，在3 0 k m + 3 0 k m 的范围内部署了1 0 4 个网络节点n 该系统可以 提供多个战术指挥中心( t a c t i c “o p e r a t i o nc e n t e r 或t o c ) 与多个战术旅( ，r a c t i c a i b r i g a d e s l 之间的宽带数字移动通信。1 9 9 6 年因特网任务工程组( i e t f ) 的移动 自组网工作小组( m a n e tw o r k i n gg r o u p ，或m a n e tw g ) u j 诞生，其目前的 核心任务是研究移动自组网环境下基于i p 的路由协议规范和接口设计1 7 】。在 m a n e tw g 以及i e t f 的主导下，移动自组网络路由协议的设计开始出现先应 硕士学位论文 第一章绪论 式( p r o a c t i v e ) 和后应式( r e a c t i v e ) 两类。另外，8 0 21 1 协议和8 0 2 1 1p c m c i a 卡的出现，以及h i p e r l a n 和蓝牙( b l u e t o o t l l ) 技术的普及也为迅速搭建基于 移动计算设备的m a n e t 原型系统提供了极大的方便。 1 1 2 移动自组网络的特点 移动自组网中，两个节点间的通信可以分为两种方式。当通信双方均在彼此 的传输范围之内时，双方可以直接进行无线通信；否则，双方就必须通过其它中 间节点的转发来完成信息交换。并且后者是最常用的通信方式，因此移动自组网 通常是一个多跳( m u l t i h 叩) 无线移动网络。图1 一l 描述了一个由三个节点组 成的简单移动自组网络。 图1 1 一个简单的移动自组网 在图1 1 中，节点主机a ，c 均在节点主机b 的传输范围内，反之亦然。因 此，a 与b ，c 与b 均可直接通信。同时，节点主机c ，a 均不在彼此的传输范 围内，故a ，c 之间进行通信，必须通过节点主机b 转发实现。 移动自组网作为一种自创建( s e l f - c r e a t i n g ) ，自组织( s e l f _ o r g a i l i z i n g ) ，和自 管理( s e l f _ a d m i n i s t e r i n g ) 的全新网络架构【1 9 j ，与传统无线移动网络有着截然不 同的的特点。移动自组网络的特点主要可以归纳为以下几点【6 j ： 1 易部署，由于移动自组网不需要固定的地面设施和主干网络支持，当需 要时，只需要将多个带有收发装置的节点置于需要部署的区域，这些节点主机就 可以自动组成一个网络。 2 健壮性强，因为移动自组网是一种对等网络，无集中的控制和管理中心， 故当某些节点出现故障时，并不导致整个网络瘫痪，但是网络的性能将会受到不 同程度的影响。 3 移动快，移动自组网本身就是由一些既充当主机又充当路由器的移动节 点组成，网络随着节点的移动，不断的进行搬迁。 硕士学位论文第一章绪论 4 带宽小，由于无线通信本身的物理特性，它的网络带宽要比有线信道要 低得多，另外考虑到节点之间通信的竞争与共享，某个节点可能得到的实际带宽 远小与理论上的最大带宽值。 5 单向性，移动自组网络节点之间的通信可能存在单向性。例如当节电的 能源不足时，或者节点的通信设备的发射功率不同时，就可能出现a 节点发射 的信号b 节点可以收到，而b 节点发射的信号a 节点却收不到。 6 动态性，由于移动自组网中的节点可以任意运动，这就使得节点之间的 连接链路不断的产生和断裂，因此网络的拓扑结构将不断的在改变。 1 2 移动自组网中的路由协议 由于移动自组网络中的节点是不断移动的，网络的拓扑结构也在不断发生变 化，这就对移动自组网络的路由协议提出了更高的要求。传统的基于因特网的路 由协议已经无法适应移动自组网络拓扑快速变化的需要，因此，研究人员对 m a n e t 的路由协议进行了大量的研究工作，针对移动自组网络的动态变化网络 拓扑结构，单向信道存在，无线传输的有限带宽，以及无线移动终端的局限性提 出多种路由策略。目前，移动自组网中路由协议 6 的最常见分类方式是基于路由 发现策略，将路由协议按驱动方式分为表驱动路由和按需驱动路由两种协议类 型，如图卜2 所示。 图卜2 移动自组网路由协议 硕士学位论文第一章绪论 1 2 1 表驱动( t a b i e d r iv e n ) 路由 该种路由协议又被称为先应式( p r o a c t i v e ) 路由协议。在这类协议中，网络 内每个节点都维护一张最新路由表，它记录了本节点去往所有其它节点的路由 信息。其路由发现策略与传统路由协议类似，节点不断广播路由信息包来实现路 由信息交换，这样做虽然可以保证节点得到最新的全局路由信息，明显的降低节 点路由找寻的潜伏时间，但是大量宝贵的网络带宽被消耗在了路由表的维护过程 中。典型的表驱动路由协议有d s d v 协议、c g s r 协议、w r p 协议、g s r 协议、 f s r 协议、h s r 协议、z h l s 协议等等m 】。 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 ) 路由协议是一种无环路距离 向量路由协议，它是传统的b e l l m a i l f o r d 路由协议的改进。协议使用目的端顺序 号来避免因使用过时路由信息而产生无效路径。它基于传统b e l l m a t l f o r d 算法 的路由选择协议，通过对路由编号等措施来避免路由环路的产生。在该协议实现 过程中，节点周期地向邻居节点广播一个报文，报文内容为节点路由表或表中发 生改变的表项，相关节点根据收到的报文更新路由表。这种协议的优点为利用目 的端顺序号来避免出现路由环，同时通过使用触发性路由更新，在网络链路状态 改变时收敛较快。缺点是周期的广播报文增大了网络开销，不适应变化速度快的 移动自组网络，且不支持单向信道。 c g s r ( c l u s t e rg a t e w a ys 、v i t c hr o u t i n gp r o t o c 0 1 ) 是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 m t o c 0 1 ) 也是一种距离向量路由协议，每个节点包 含距离表、路由表、链路权值表和消息重传表四张表。协议本质上是一个距离向 量路由协议，是在路径发现算法p f a ( p a t h f i n d i n g a l g o r i t h m ) 基础上改进设计的。 它利用去往目的节点的路径长度和相应路径的倒数第二跳节点信息加速路由协 议收敛速度。在这个协议中的每个节点都保持路由表、距离表、链路费用表和信 息重传列表，并通过其邻节点的最短路径生成树s s t ( s h o n e sp a ms p a l l l l i n gt r e e ) 生成自己的s s t ，然后再向邻节点传递更新信息。优点是通过对接收到的所有信 息的检测，消除了路由环问题，加快了算法的收敛速度。缺点是需要更新的信息 较多，占用较多资源。 4 硕士学位论文第一章绪沦 g s r ( g 1 0 b a ls t a t er o u t i n g ) 是一种链路状态路由协议。每个节点存储邻居 列表、拓扑表、下一跳表和距离表四张表格。 f s r ( f i s h e y e s t a t er o u t i n g ) 对g s r 进行了改进。f s r 的更新消息只包含附 近节点的信息，显著地减小了更新消息的大小。 h s r ( h i e r a r c l l i c “s t a t er o m i n g ) 是一种用于分级网络的路由协议。高级的 节点保存它所有子孙节点的位置信息。沿从最高级的根节点到最低级的叶节点的 路径为节点分配逻辑序列地址。序列地址指示了节点的位置，可以简单地使用序 列地址进行寻址。网络还配各了位置管理服务器来实现物理地址到逻辑序列地址 的映射。 z h l s ( z o n eb a s e dh i e r a r c h i c a ll i i l l ( s t a t e ) 路由协议是一种基于区域的路由 协议。网络被分割成不重叠的区域，区域与簇不同，它没有首领。并定义了两级 拓扑：节点级和区域级。节点级拓扑指一个区域内的节点的物理连接。区域级拓 扑指各个区域如何互相连接。网络中存在两种链路状态报文：节点链路状态报文 和区域链路状态报文。节点链路状态报文包含节点的邻居信息，只在区域内传播。 区域链路状态报文包含区域间的链路状态，在全网中传播。通过分区可以减少路 由控制报文的个数。 1 2 2 按需( 0 n d e m a n d ) 驱动路由 按需路由，又被称为后应式( r e a c t i v e ) 路由，它与表驱动路由不同，只有 源节点需要进行通信，并且在已有的路由表中找不到有效的传输路径时，才被使 用。当源节点需要与目的节点通信时，它会在网络中发起一个路由寻找过程。这 个过程只有在找到一个有效路由的情况下，或是当所有的找路尝试都失败的情况 下，才会结束。一旦一条路由被建立起来，该路由将由一个路由维护过程来进行 维护，直到目的节点变成不可到达，或是该路由已经不再需要。典型的按需驱动 路由协议包括d s r 协议、a o d v 协议、l m r 协议，t o r a 协议、a b r 协议、 s s r 协议，c b r p 协议等。 d s r ( d y n 锄i cs o u r c er o u t i n g ) 协议是最早采用按需路由思想的路由协议。 它使用了源路由，且在每个分组的分组头中包含整条路由的信息。该协议包含 路由建立与路由维持两个阶段，在路由发现阶段采用f 1 0 0 d i n g 法。为减少路由发 现过程的开销，每个节点都包含一个c a c h e ，存放已有路由信息。路由维持过程 是源节点用来检测网络拓扑是否发生变化的机制。当拓扑发生变化，源路由产生 中断时，源节点将收到一个路由错误信息，并通过查找c a c h e 中信息获得新的路 由。如果不通，则重新启动路由寻找过程。这种协议的优点是中间节点不必存储 转发报文所需的路由信息，而改由分组自己携带。因无周期性的广播操作，减少 硕士学位论文 第一章绪论 了网络开销。缺点是存在陈旧路由问题，以及在数据流突发性较强的情况下可能 会带来较大的丢失率。 a o d v ( a d h o c o n d e m a l l d d i s t a l l c e v e c t o r ) 协议是一种改进了的距离向量 路由协议，它建立在d s d v 协议基础之上，通过使用目的端顺序号来避免产生 无效路径。它并不维持一个路由表，而是在需要的时候才启动路由选择过程，因 而大大降低了路由维持的开销。事实上它是d s d v 协议和d s r 协议的组合，它 借用了d s r 中路由发现和路由维持机制，利用了d s d v 中按跳( h o p b y - h o p ) 路由、顺序编号和周期更新的机制。优点是使用目的端顺序号可以避免路由环， 利用按需方式减少了网络开销。缺点是该协议是基于双向链路的假设，当出现单 向链路时将产生无效路径，同时周期性广播h e l l o 信息，具有较大的网络开销。 l m r ( l i 曲t 、v e i g h tm o b i l er o u t i n g ) 和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 l g o r i t h m l 协议均为按需单播路由协议。它们都是建立在g a f n i b e r t s e k a s 算法基 础上的【9 】，通过构造一个根节点在目的节点上的有向无环图来实现多路径路由 的协议。利用该协议可以将数据包从图的上游节点发往下游节点，直到数据包被 目的节点获得。在l m r 中，有向无环图是保存在节点中的网络链路状态表中的 每个链路的信息来建立的。而在t o r a 中，节点利用“高度”，一种特殊的标准， 来建立路由的有向无环图。由于采用的标准不同，t o r a 比l m r 具有更高的可 用性和性能。 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 ) 协议使用一个新的路由选择度量：联合 稳定度，即移动主机节点和链路在时间与空间上的稳定程度。网络中每个节点周 期地。播一个标志，与它相邻的节点每收到一次，就表明发标志的节点还存在于 该网络中。收到标志的邻节点根据路由稳定的时间和路由信号的强度作为路由选 择的测度，每收到一次，相应的节点稳定度增加一点。点数越高，说明路由越稳 定。若路由断裂，稳定度将被重置。这种协议优点是使用了稳定度，很容易发现 稳定路由。缺点是由于节点不能长时间保持静默，需周期性产生标志，占用较多 网络资源。 s s r ( s i 叠n a ls t a b i l i t yr o u t i n g ) 协议选择路由的标准是利用节点之间信号的 强度和节点的位置稳定度。s s r 可分成两个相关协议：动态路由协议d r p 和静 态路由协议s r p 。d r p 的任务是负责维持信号稳定度表与路由表，信号稳定度 表记录邻节点信号强度，通过周期性地与链路层交换信息得到。s r p 负责分组的 处理和发送，利用d r p 建立的路由表完成。若没有现成的路由，则重新启动路 由寻找过程。 c b r p ( c l u s t e r b a s e d r o u t i n g p r o t o c 0 1 ) 被用于单频两级网络中。c b r p 也使 用源点选路，路由查找使用与d s d v 类似的请求一回应方式。为了减少报文丢失 硕士学位论文第一章绪论 率，引入了中间节点本地修复机制。 此外，还有一种基于表驱动和按需驱动之间组合路由协议，即z r p ( z o n e r o u t j n g p r o t o c o i ) 协议扣j 。在该协议中，网络内所有节点都有一个以自己为中心 的虚拟区，区内的节点数和设定的区半径( 按跳数计算) 有关，因此区是重叠的， 这是与分级路由的区别。在区内使用表驱动路由算法，中心节点使用区内路由协 议i a r p ( i n t r a z o n er - o u t i n g p r o t o c 0 1 ) 维持一个到区内其它成员的路由表。对区 外节点的路由使用按需路由，利用区间路由协议i e r p ( i n t e r z o n er o u t i n g p r o t o c 0 1 ) 建立路由m j 。z r p 协议的性能很大程度上由区域半径参数值决定。通 常，小的区域半径适合在移动速度较快的节点组成的密集网络中使用，大的区域 半径适合在移动速度较慢的节点组成的稀疏网络中使用。目前z r p 采用预置固 定区域半径值的做法，无疑限制了它的可适应性。 1 23 两类路由方法的比较 综上所述，表驱动的路由方法类似于无连接的数据包发送方法，无论是否需 要路由信息和对路由信息的需求有多么频繁。它依赖于潜在路由表更新机制，而 这一机制必定导致路由信息在网络中被大量的复制。而这种问题在按需路由方式 中将不会存在。当源节点利用按需路由协议来获得去往目的节点的路由时，它必 须要等待一段时间，从而找到有效包传输路径。另一方面，在表驱动方式中，因 为网络中的路由信息不论是否需要，总是在被不断复制和更新维护，所以路由信 息总是可用的。虽然这一个特点对于数据报文的通信十分有用，但是它也同样导 致了网络带宽的大量消耗和节点能源的消耗。由于这两种资源在移动自组网络都 是非常有限的关键资源，这就使得表驱动路由具有极大的局限性1 2 。表l l 对 两类路由协议进行几个方面的比较。 表l 一1 按需路由协议与表驱动路由协议的比较 比较的方面按需路由协议表驱动路由协议 路由信息的可用性当需要时，才可用无论是否需要，总是可用 路由结构平坦式主要是平坦式，除了c g s r 对路由信息的维护不需要周期性的更新要求周期性的更新 如何应付节点的运动进行局部路由发现，比如通知其他节点，保持所有 a b r s s r节点路由表的一致性 产生的网络开销随着节点运动和路由需远远超过按需路由方式 求增加恧上升，比如，a b r 对服务质量( 0 0 s ) 的支几乎不支持q o s ，但基本大都支持最短路径和q o s 持都支持最短路径 硕士学位论文 第一章绪论 1 3 研究的内容和本文所做的工作 根据移动自组网特有特性，研究适合这种特殊网络的实用性强，可靠性高的 路由协议是当今移动自组网络研究中急需解决的问题。本课题的主要研究目标是 研究基于移动白组网下的泛播路由仂、议，分析泛播路由协议在移动自组网络中对 网络的各项性能指标的影响，为获得具有较优网络性能的泛播路由协议提供科学 参考，也为在实用移动自组网络中部署泛播路由协议提供理论依据。主要研究内 容包括：设计并实施移动自组网中的泛播路由协议；以及设计和实施移动自组网 中基于选播策略的路由恢复方法。针对以上研究内容，本文在以下方面进行了深 入研究，并取得了较好研究成果。 ( 1 ) 泛播作为一类新型的通信协议，能有效平衡网络负载分布和提高网络性 能。本文针对移动自组网的特点，提出了一种全新的选播路由协议。它通过在网 络层中，利用路由方式选取距源节点最近目的节点方案，代替了单播通信中固定 目的节点的方法，最大限度利用了原有资源和避免了对整个网络架构的改变，减 少了网络控制开销，使网络性能得到进一步提高。并且在最具权威的网络模拟器 之一的n s 2 平台上，实现了该协议。通过对包传输率，包平均延时，己及平均网 络控制字节数等指标测试表明了泛播协议的良好性能。 ( 2 ) 在移动自组网络中，传输路径破裂后迅速恢复可以对该网络各种音频， 视频服务提供可靠的保障。为此，本文提出了一种基于泛播协议的移动自组网路 由恢复方策略。当链路断裂时，整个传输路径被分成包含源节点的源组和包含目 的节点的目组两个部分。该策略利用源组和目组所有节点已有路由缓存信息来选 取最短传输路径来恢复破裂路由，从而最快速，最高效的完成恢复断裂路径。在 n s 2 平台上的模拟测试表明该方法能够有效的提高网络的性能。 1 4 论文的组织 论文全文共分五章： 第一章为绪论，简要介绍了移动自组网的概念、特点，以及移动自组网络的 应用前景。并且对目前已有的移动自组网络协议进行了分类介绍，对按表驱动和 按需驱动两类路由协议进行了比较。最后，对全文的研究内容以及本文的主要工 作进行了描述。 第二章介绍泛播原理，对移动自组网络中，泛播研究的现状进行了总结和分 类，指出基于网络层的移动自组网泛播协议研究具有较高的研究价值和实用性。 描述移动自组网中的泛播路由模型。并且对泛播路由中的最优评判标准进行了多 方面深入的讨论。随后详细介绍和比较了两种按需路由协议：d s r 协议和a o d v 协议。最后，在d s r 协议和a o d v 协议基础上，以最短路径为准则，设计了全新 的泛播路由协议a d s r 协议和a a o d v 协议。 第三章介绍并比较了移动自组网络的3 种权威的模拟测试工具，它们分别是 o p n e t ，g l o m o s i m ，n s 2 。然后利用n s 2 对a d s r 协议和a a o d v 协议进行 8 硕士学位论文第一章绪论 了中等网络负载，网络吞吐率和泛播组规模等3 组测试。并且对模拟结果进行了 详尽分析。 第四章在泛播模型的基础上，利用泛播策略提出了一种快速路由恢复协议 o r d s r 协议。它利用节点路由缓存中已有的路径信息，在源节点组和目的节点 组中选取具有最短路径来恢复破裂路由。利用n s 一2 平台对q r d s r 协议进行了 模拟测试。并对测试结果进行了详尽的分析。 第五章是总结。对本文所做工作进行了总结，并阐述了进一步的研究内容。 硕士学位论艾第二章移动自组网的泛播协议设计 第二章移动自组网的泛播协议设计 2 1 泛播与移动自组网 目前在i n t e m e t 上，有4 种i p 通信模型它们分别是单播，多播，广播i l o j 和 泛播。最常用的单播通信模型定义了一种单点到单点的数据包流通信模型。而 多播与单播不同，它定义了一种单点到多点数据包流通信模型。在该模型中，源 节点只有一个，而目的节点至少是一个，在大多数的情况为多个。从通信模型的 角度看，广播可以被看成多播的极限情况。但是，它们的实现方式却完全不同。 广播定义了一种单点到整个网段中的全部节点的数据包流通信模型。在广播模型 中，源端只有一个节点，而目的端则是网络中的所有节点。 21 1 泛播通信模型 泛播与上面所说的单播，多播和广播都不一样。它定义了一种特殊的点到点 数据包流通信模型吩1 3 】。在这个模型中，源节点是单个节点，而目的节点则是在 一组相同的候选节点中，离源节点最近的一个。采用泛播技术表明一个客户端只 想获得某种特殊的服务或应用，它并不关心是由哪台服务器来提供这种服务或应 用。为了实现泛播服务，一个单一的泛播服务地址将被分配给一个泛播组，其中， 可能包括一个或多个泛播服务器1 5 。在通信过程中，客户端将首部标有泛播 组地址的数据包发往泛播服务器，路由器则尽量将该数据包发往符合泛播组地址 的服务器节点。 图2 1 展示了泛播通信模型的原理。在图中，有一个泛播组包括3 台泛播 服务器，分别为泛播服务器1 ，2 ，3 。另外，还有两个客户端1 ，2 。当客户端向泛 播组发起服务请求时，服务请求包被分别定位到距离最近( 即，跳数最短) 的一 台泛播服务器上。因此，客户端2 的请求被发往泛播服务器3 ，而客户端1 的请 求则被发往泛播服务器1 。 图2 1 泛播通信模型示意图 l o 硕士学位论丈第二章移动自组网的泛播协议殴计 2 12 泛播路由选择标准 为识别出泛播服务，在姒n e t 必须有泛播路由协议( a r p ) 。一般说来，a r p 由建立路由，传送数据和维持路由三个步骤组成f 2 8 2 。后两者与单播协议一致， 唯一不同的是路由建立，因而它在a r p 中就显得很重要。假设移动自组网拓扑图 g = ，其中v 代表图的顶点( 节点) 集，e 是边集，v = f v ，v 。，v 。 ，e = f e 。 l i m ，1 j m ，g ( a ) = a 。，a 2 ，a k ) 代表一组泛播顶点集。当一个节点 有意发送数据包到目的地组g ( a ) 时，它就会检查路由信息以找到一条到g ( a ) 中 任一节点的合适路径。如没找到这样条路径，它将向所有节点广播路由请求信 息，那些收到此消息但从它没有到g ( a ) 的合适路径的节点就再将此消息向其他 节点广播。如果从源节点或某一中间节点到g ( a ) 有多条路径，那么就需要选择 其中一条路径。根据以下标准来选择 3 0 1 ： ( 1 ) 跳数度量准则 关于服务选择，跳数是一个值得考虑的因素。在无线网中，跳数越少，传输 费用就越少，网络被阻塞的概率也越小，用到的网络资源当然也越少。因而在评 价路由协议性能时跳数是一个很重要的衡量尺度。 ( 2 ) 时延准则 沿最短路径传送的包可能花费相当长的时间才到达目的节点，因每次选中的 中间节点转发消息时有一个较长的延迟。这将导致严重的拥塞，特别是在带宽较 窄的无线网络中，端到端的延迟与跳数之间的相互影响通常很少，除了在超低负 载时。路由的延迟在某种程度下反映了其拥塞度。有时，我们为了某些特殊的应 用必须选择时延最少的路径。 ( 3 ) 路径维持时间 如果从源节点到目的节点的路径被频繁的切断，这就会加重修复路由的额外 开销，对应用很不利。这时按最少跳数或最少时延选择的路径就不一定是最优路 径了。研究人员提出了一种通过预测每条链路的维持时间来选择更可靠的路径的 方法。 ( 4 ) 服务器平衡准则 有两种选择方针：一是用最近连接较多的节点的服务器作为目的节点，另一 个是最近连接较少的节点的服务器作为目的节点。 ( 5 ) 能量平衡准则 移动自组网中的节点能量是有限的。为保持网络生存和延长网络寿命，在 路由时必须尽量使得每个节点的能量平衡。 ( 6 ) 混合准则 以上五个准则都只考虑了有线网络的个方面，有时不能单独使用，而是 硕士学位论文 第二章移动白组网的泛播协议改计 结合各种准则来选择路径。 2 13 移动自组网络中的泛播技术研究现状 目前，姒n e t 中的泛播研究以及泛播路由协议的提出，主要是在网络层，数 据链路层以及应用层进行的( 图2 2 ) ，并且利用流行的网络仿真工具，例如， n s 2 ( n e t w o r ks i m u l a t i o n2 ) ，o p n e t 以及g l o m o s i m 来对提出的泛播实现方案 进行仿真与评测。 移 动 自 主 网 络 由 的 泛 播 技 术 基于应用层 基于网络层 基于数据链路层 基于服务域名解析的泛播技术 基于传统路由的泛播技术 基于现存路由协议的泛播技术 基于全新协议的泛播技术 基于数据链路状态的泛播技术 图2 2 移动自主网络中的泛播技术研究现状 ( 1 ) 网络层中的泛播技术研究 网络层中的泛播研究一般是针对移动自组网络中已有路由协议提出扩展方 案，或设计全新的路由 力、议来加以实现。这些方案的核心在于通过泛播路由器的 泛播路由算法将泛播组地址解析成某个特定的泛播服务器地址，如下图2 3 所 示。研究人员已经公认在网络层中实现泛播路由协议，只需要最小程度的修改网 络协议栈，并且也不需要在网络中部署其它的服务架构。这样的做法，对于整个 上层应用是完全透明，也便于相关应用的实现与部署。 图2 3 基于网络层的泛播路由原理图 现有的网络层泛播技术研究主要有3 类： a 基于传统路由表和路由算法的泛播技术研究 在利用泛播组“虚拟节点来实现泛播路由的方案中，传统的经典路由方法， 链路状态和距离矢量，被用来实现泛播路由口0 】。在链路状态方式中，在实际泛 播组成员节点的路由表中，都有一条虚拟链路通往的泛播组“虚拟节点”。利用 硕士学位论文第二章移动自组网的泛播协议设计 经典算法d 1 j k s t r a 算法可以得到一条通往虚拟节点的最短路径，当数据包沿着 这条最短路径向前发送时，必然会到达真正的泛播组节点，完成泛播路由。而在 距离矢量模式中，每个泛播组成员的路由表中，都设置了一条代价为0 的虚拟路 径通往虚拟节点。利用经典算法b e l l 一f o r d 可以得到一条通往虚拟节点的代价最 小路径，当数据包沿着代价最小路径向前传递时，必然会到达泛播组成员，完成 泛播包传递。这两个基本路由模式都是表驱动的，它们要求节点保存了准确的网 络全局路由信息才能达到较好的泛播路由效果，而在移动自组网络中，全局信息 的收集需要较大的控制和通信代价。因此，这两种方案在实际的应用中，会有相 当大的困难。 b 基于移动自组网络现存协议的泛播技术研究 在基于泛播路由的g e o c a s t 方案中，通过扩展t o r a 协议来实现泛播路由方 法被提出。根据t o r a 的现有算法，泛播组每个成员都被看成是一个s i n k ，成员 与成员之间用无向逻辑链路连接在一起。而其他成员对泛播组成员的访问仍然按 照t o r a 协议来进行。这样就可以实现其他移动自组网络节点对最近泛播成员的 访问。但是在这个方案中，只允许存在一个泛播组，并且这个算法在路由过程中， 无法避免环路的出现，从而造成路由失败口“。 在基于a o d v 协议的泛播路由实现方案中，源节点利用a o d v 协议的r r e q 包 携带泛播组地址，通过泛洪来寻找网络中的泛播组成员1 2 2 】。泛播组成员收到泛 播r r e q 之后，向源节点发送带有本节点单播地址的r r e p 包。源节点在一段时问 内接收泛播组成员的回复，将泛播组成员回复信息中的路由信息存入路由表中， 并对这些路由条目进行特定的时钟管理。另外，源节点将选出与其距离最短( 或 跳数最小) 的泛播组成员节点，作为发送目的地，进行数据包的发送。这个泛播 路由方案虽然允许多个泛播组的存在，但是它并没有对泛播路由进行相关的优 化。它只能通过源节点泛洪来寻找最近节点，路径的中间节点并不记录有效的泛 播组信息，使得该种信息无法很有效的向外传播。 a d s r 协议是移动自组网络中的第一个被正规描述的泛播协议睇“。它在d s r 协议的r r e q ，r r e p 包中都加入了泛播标志和泛播组信息。路由协议包在网络传递 过程中，中间节点将自动保存有效的泛播组成员信息。通过对路由表的扩展， a d s r 协议的网络层可以有效支持多个泛播组并存。同时它还采用了多种不同的 最优路由衡量标准，包括最小跳数，负载均衡等等。在n s 2 平台上的模拟结果显 示，泛播协议a d s r 具有相当好的性能。 c 基于全新协议的泛播研究 在基于s i n k 的泛播路由协议中，每个泛播组成员s i n k ，都将向外广播发送 一种跳数为l 的兴趣包，以此向网络中的其它节点说明自己的存在。s i n k 的邻 硕士学位论文 第二章移动自组网的泛播仂议设计 居节点收到该兴趣包之后，将保留上一跳节点的地址，并且将包中h o dc o u n t ( 跳 数) 字段加1 ，再向外发送。直到网络中的所有节点都得到去往s i n k 的跳数信 息和路由信息。当一个节点收到多个兴趣包时，它只选取这些信息包中最小跳数 的，每个节点都将保存去往s i n k 的最短路径的跳数，以及去往这些s i n k 的最短 路径。该实现方案的核心是，s i n k 主动向整个网络发布自己的相关信息。如果 一个泛播组的成员数量较多，或是有多个泛播组存在时，每个s i n k 每隔一段时 间就向外广播一次兴趣包，网络资源将因为兴趣包的传递消耗大量带宽。同时， 该协议是针对无线自组传感器网络提出的，所以，它也不是真正的基于m a n e t 的泛播协议。 ( 2 ) 媒体访问层中泛播技术研究 尽管在路由层中实现泛播协议具有很多的优越性，但是与有