（计算机应用技术专业论文）移动自组网路由协议的分析与改进.pdf

华东师范大学硕士学位论文 论文摘要 移动自组网( 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 o d v ) ，包括其组成， 特点，存在的问题和不足，并引出本文需要解决的问题。 通过分析比较，提出改进算法从链路退避算法、路由发现和自愈路由修复 三方面进行改进。算法的基本思想是利用无线移动节点间的链路状态信息，在 路由发现过程加入路由失效时间、路由新鲜度等作为参考，尽量保证路由的可 靠性并为路由上各节点提供后备节点，而在当监测到路由中的某条链路即将失 效后，在有效的小范围内进行快速的本地修复，减少路由失效造成的延迟抖动 和分组丢失。该算法由三部分组成：链路状态分析模块、路由发现模块和路由 修复模块。 最后通过设计仿真实验验证结论。仿真结果证明：采用改进路由协议的网 络路由信息量低，网络吞吐率高，在一定条件下网络时延减小，性能指标都较 普通路由协议有所提高。 关键字 移动自组网，路由协议，链路状态，链路监测，路由发现， 自 愈路由修复 华东师范大学硕士学位论文 a b s t r a c t m o b i l ea dh o cn e 鲰r ki sak i l l do fs l e f - o r g a n i z e dc o m m u i l i c a t i o nn e t w o r k w i 血a u tc e m 盯b e c a u s eo fi t s 1 1 i g h - p c r f o r m a n c es e l f _ o 瑁a 1 1 i z a d o n ，s u p p o r t i n g d y d 锄j ct o p o 咖t 1 1 r ec h a l l g e ，m u n i h o pf o n v a r d i n gt e c h l l 0 1 0 9 y 姐da b i l i 哆o f r o b l l s 缸e s sa 1 1 da n t i 司e s 仃0 y i i l 吕i ti sw i d e l ya p p l i e di n 也e ：丘l e d so fm m t a r y ，a c c i d e n t e n v i r o n m e l l t sa n dc i v i lw i r e l e s sd a t ac o n i m l l i c a t i o n b u tb e c a u s eo f 廿a n s 工n i s s i o nc b a r a c t e r i s 石c so fw i r e l e s sc h a n n e l ，a n du n c e 】恤t y o fn o d cp o s “i o i l n 时l i o r kt o p os 缸l c t i 】r ei si 1 1u n s t a _ b l es t a l i l s ，s o 口a d i t i o n a 王r o u t e 口r o t o c o l sc a nn o tb e 丘tf o rt h ec h a r a d e r i s d c so f m o b i l ea dh o cn e t w o r k e x i s d n ga d h o cn e t w o r kp r o t o c o l s “s oh a v et 1 1 e i rl i m i t s ，a n da r es d ui nr e s e a r c h s oh o wt o m o d i 白e x i s t h l gr o u t ep m t o c 0 1 si no r d e rt oi m p r o v e 血er o b l l s 缸e s s ，s om a tt l l e n e t w o r kc a 堇1b em o r es t a b l ea n dr e l i d b l eu n d e rb a dc i r c 啪s t a l l c e s i m _ p r o v m gt 1 1 e n e t w o r ks e r 、，i c ei st h e 胛o s eo f 也i sp a p e r 1 1 1 也i sp a p 盯，w e 丘璐f l yh 血o d u c ot l l eh i s t o r ya n dd c v e l o p m e l l to fa dh o c r 劬o r ki t ss 咖c 骶a n da r c l l i t e c t l 】r e d i s c u s sa 1 1 dc o m p a r cs 甜e so fa dh o cr o u t e p r o t o c o l s t h 衄w ei n t r o d u c ea dh o co n d 锄a n dd i s t a n c ev b c t o rr d u t i n g( a o d v ) i n d e t a i l ，i 1 1 c l u d i n gi 乜c o m p o n e n t s ，吐l a r a c t e r i s t i c s ，p r o b l e m sa n dd i s a d v 趾t a g e s 1 飞r 0 1 1 曲姐a l y z i n ga n dc o m p a r i i l 舀w ep u tf b r w a r do u rm o d i 丘c da l g o 州b m i 叫，m v i n g 也ep e r l 0 r n l a l l c eb a s e do nr e t r e a ta 1 9 0 r i 1 1 n ，r o u t ed i s c o v e r ya n ds l e fr 0 1 工t e r 印a r i n g m0 1 l ra l g o r i 也m ， w i 也也eh n ks t a t ei n f o m a l i o no f m o b i l ew i r e l e s sn o d c s ， w e 璐ed 啪e r ss u c ha st h er o u t ef a i l u r et i l n e ，t h em u t e 丹e s h n e s sd u r i n gt h er o u t e d i s c 0 v e r yp m c e d u r e i 1 10 r d e rt 0a s s l l r e l eq u a 王i t yo fm u t e sa n dp r o 、，i d eb a c k u p n o d 昭、7 l ，l m em o 工1 i t o r 也a t 也e1 i n k 谢1 l 御，m ea l g 嘶n ns t a n sa1 0 c a lr 印a i ri na s m a l ls c o p et or e d l l c e 也ed e l a ya n dp a c k c tl o s t t h ea l g o r i 也mi sc o n s i s to f3 c o m p o n e n t s ：1 谊ks 诅t e 锄a l y s e ，r o u t ed i s c o v e r y ，r o u t er e p a i r e ht h ee n d ，w ed e s i l 皿as i m u l a t i o ne x p a 恸e n tt op r o v eo u rc o n c l u s i o n t h e s i m l l l a t i o nr e s u l ts h o w s 血a t ：谢也t h em o d i 五e dr o u t e 口r o t o c o l ，w eg e tl e s sr o u t e i 1 1 f 0 皿a d o na n dl l i g h e ri n p ma n do u i p u tp e r f o m a l l c e ，u n d e rw i r i u sn o d ed e n s 讹e s ， 8 d e e d s 趾d1 0 a d k e yw o r d s m o b i l ea dh o cn c t w o r k ，r o u t ep r o t o c o l ，1 i r l ks t a t e ， l i n km 伽i t o r ， r o u t ed i s c o v e r y ，r o u t es e l f - r 印a i r i i 学位论文独创性声明 本人所呈交的学位论文是我在导师的指导下进行的研究工 作及取得的研究成果。据我所知，除文中已经注欢引用的内容外， 本论文不包含其他个人已经发表或撰写过的研究成果。对本文的 研究做出重要贡献的个人和集体，均已在文中作了明确说明并表 示谢意。 学位论文授权使用声明 本人完全了解华东师范大学有关保留、使用学位论文的规定，学 校有权保留学位论文并向国家主管部门或其指定机构送交论文的电 子版和纸质版。有权将学位论文用于非赢利目的的少量复制并允许论 文进入学校图书馆被查阅。有权将学位论文的内容编入有关数据库进 行检索。有权将学位论文的标题和摘要汇编出版。保密的学位论文在 解密后适用本规定。 1 学位敝储张歃? b 础峙师始盯 j 日期：洲。l 、计日期：沙t 多印 华东师范大学硕士学位论文 1 。1 本章提示 第一章绪论 本章给出了本文的研究背景，指出随着无线网络的飞速发展，自组网得到 了长足的发展。但与传统网络相比，也遇到了新的问题。路由问题是无线自组 网面临的一个挑战，快速建立可靠的路由成为第一要解决的问题。本文正是基 于这样的背景下产生的。 1 2 无线自组网发展及研究现状【1 胴 当前存在着两种移动无线网络：第一种是有基础设施的网络，该网络由若干 移动节点和被称之为“基站”的基础设施组成，网络中的移动节点直接与其通信 半径之内的最近的基站连接并完成通信。当移动节点离开了某一基站的通信范围 而进入另一基站的通信范围时，原基站与新基站之间要进行转接，从而使移动节 点可以不受妨碍地继续进行网络通信。第二类移动无线网络是无基础设旆的，通 常被称为a dh o c 网络。 a dh o c 网络的前身是分组无线网( p a c k e tr a d i on e t w o r k ) 。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 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 1 0 b a lm o b i l e i n f o r i i l a t i o ns y s t e m s ) 项目，对能够满足军事应用需要的、可快速展开、高抗 毁性的移动信息系统进行全面深入的研究。成立于1 9 9 1 年5 月的i e e e 8 0 2 1 l 标准 委员会采用了“a dh o c 网络”一诃来描述这种特殊的自组织对等式多跳移动通 信网络，a dh o c 网络就此诞生。i e t f 也将a dh o c 网络称为m a n e t ( 移动a dh o c 网 络) 。 华东师范大学硕士学位论文 a dh o c 网络是由一组带有无线收发装置的移动终端组成的一个多跳临时性 自治系统，移动终端具有路由功能，可以通过无线连接构成任意的网络拓扑， 这种网络可以独立工作，也可以与i n t e m e t 或蜂窝无线网络连接。在后一种情 况中，a dh o c 网络通常是以末端子网( 树桩网络) 的形式接入现有网络。考虑 到带宽和功率的限制，m a n e t 一般不适于作为中间传输网络，它只允许产生 于或目的地是网络内部节点的信息进出，而不让其它信息穿越本网络，从而大 大减少了与现存j n i e m e t 互操作的路由开销。a dh o c 网络中，每个移动终端兼 备路由器和主机两种功能：作为主机，终端需要运行面向用户的应用程序；作 为路由器，终端需要运行相应的路由协议，根据路由策略和路由表参与分组转 发和路由维护工作。在a dh o c 网络中，节点间的路由通常由多个网段( 跳) 组成，由于终端的无线传输范围有限，两个无法直接通信的终端节点往往要通 过多个中间节点的转发来实现通信。所以，它又被称为多跳无线网、自组织网 络、无固定设旌的网络或对等网络。a dh o c 网络同时具备移动通信和计算机网 络的特点，可以看作是一种特殊类型的移动计算机通信网络。 随着无线技术的进一步发展，a dh o c 网络以其方便灵活的特点越来越受到人 们的重视，关于该网络中的路由协议及其性能评价成为了当前研究的一个热点。 1 3 研究背景 与传统的有线网络相比，a d h o c 网络具有：无中心和自组性、自动配置、 动态变化的网络拓扑结构等特点。这些特点使得a dh o c 网络在军事领域、灾 害救助、传感器网络、偏远野外等场合有着广阔的应用前景。但由于a dh o c 网 络自身的无线传输带宽受限、网络拓扑结构变化频繁、信道传输质量较差、终 端资源受限和分布式控制等特性，使得它与有线局域网、无线局域网以及蜂窝 网络有很大的区别。“，目前，对它的研究主要集中在以下几个方面：有效的路 由协议、媒体接入控制( m a c ) 协议、能量耗、安全性问题以及网络的q o s 机制。 在a dh o c 移动网络中如何建立、维护和选择路由，提高网络的可靠性和效率 最大限度地利用受限的无线资源是a dh o c 网络的一个根本问题。 华东师范大学硕士学位论文 a dh o c 网络使用带宽较窄的无线信道，且节点的移动性会导致频繁的路由失 效。路由失效后需启动路由重建过程。在路由重建过程中，待发送或者待转发分 组被存放在缓冲区内，如果存放分组的缓冲区溢出或者路由重建失败，分组就会 被丢弃。同时由于分组缓冲造成的分组延迟抖动对于有些实时业务如l i v e a u d i o ，l i v ev i d e o 等来说是不能接受的，而分组丢弃会导致响应业务的发送窗 口降低，严重影响网络的利用率和吞吐率。路由失效会严重影响a dh o c 路由协议 的性能，而现有的a dh o c 按需路由协议都没有提供对路由失效的有效防范与处 理。路由发现中路由选择，没有充分考虑节点移动对路由有效性的影响。当路由 失效后采取路由失效处理效率较低。 因此需要提供一种机制来保障路由选择的质量，并对路由失效做快速及时的 处理。本文正是针对上述问题提出一系列解决方案。 1 4 本文的研究内容 本论文提出了针对无线a dh o c 网络按需路由协议的一种扩展算法。算法的 基本思想是利用无线移动节点间的链路状态信息，在路由发现过程尽量保证路由 的可靠性并为路由上各节点提供后备节点，而在当监测到路由中的某条链路即将 失效后，在有效的小范围内进行快速的本地修复，减少路由失效造成的延迟抖动 和分组丢失。该算法由三部分组成：链路状态分析模块、路由发现模块和路由修 复模块。链路状态分析主要用于保证路由发现质量，该模块通过对i e e e8 0 2 1 1 协议的扩展来完成。路由发现和路由修复主要通过对路由协议层的扩展来完成。 本论文的主要内容如下 ( 1 ) 介绍a dh o c 网络体系结构，网络类别，与其他网络的比较。介绍a dh o c 网络路由协议，具体介绍几种典型的路由协议的运行机制，并对它们优缺点作初 步的分析比较。 ( 2 ) 根据己有的关于a dh o c 网络节点运动和节点间信号变化规律的理论分 析，提出了一种针对无线链路的链路状态算法。仿真结果表明，该算法可以较大 的提升路由发现的质量。 华东师范大学硕士学位论文 ( 3 ) 对a dh o c 按需路由协议的路由发现过程提出了一种改进方案，改进后 的路由发现机制综合地使用路由f r e s h 程度、路由失效时间和路由跳数等参数进 行路由选择。 ( 4 ) 采用自愈路由维护，将路由恢复时间限定在一个较短的时间内。 ( 5 ) 在n s 2 中完成了上述算法的i e e e8 0 2 1 l 和a o d v 的扩展，并进行了相应 的仿真实验，对扩展前后的路由协议性能进行了比较和评价 1 5 本文的组织结构 本文组织结构如下： 第二章：a dh o c 网络路由协议综述。对自组网进行简单介绍，并阐述了其路 由协议类型及各类的代表协议。着重论述了a dh o c 路由协议的特点，与传统移动 通信系统路由协议的区别。介绍了几种典型的路由协议。 第三章：a dh o c 按需距离向量路由协议( a o d v ) 。系统地介绍了a d o v 路由 协议的组成，及工作流程，分析了它的特点并指出其存在的缺陷。根据分析比较， 针对它的缺陷提出数据链路分析、路由发现和路由维护三个方面的改进方案。 第四章：链路分析。链路分析是整个改进方案中最核心的部分，链路状态决 定了路由发现和路由维护的动作。首先介绍了链路层面临的几个问题和现存的解 决方法，然后具体分析了m a c 层的各种退避算法及其优缺点，给出改进的退避算 法。 第五章：路由发现。本章介绍了抢先式路由发现的机制，给出改进的路由转 发的流程和路由选择策路，并根据改进对数据结构进行了扩充。最后，介绍了一 种关于建立路由备份的新的思路。 第六章：本地自愈路由修复。路由监测模型是自愈路由修复的基础，首先介 绍了监测模型，然后提出自愈路由协议，给出实现的算法、进行路由自愈修复的 时机选择和整个协议的工作流程。 第七章：性能分析。介绍了性能分析的工具和实现环境，给出在具体参数下 整个协议在改进前后的数据对比，并从具体的数据得出本文的结论。 第八章：总结与展望。对全文的工作进行总结，指出本文的研究成果和存在 的不足和有待改进之处，及进一步研究的方向。 华东师范大学硕士学位论文 第二章a dh o c 网络及其路由协议概述 2 1 本章提要 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 网络的体系结构和路由协议0 1 。 2 2a dh o c 网鳍体系结构【1 心 a dh o c 网络通常采用分布式控制方式，节点具有自组织功能。a dh o c 网络 一般有两种结构：平面结构( 见图2 1 ) 和分级结构( 见图2 2 、图2 3 ) 。平面 结构中，所有节点的地位平等，所以又可以称为对等式结构。而分级结构中， 网络被划分为簇( c l u s t e r ) ，每个簇由一个簇头( c l u s t e r h e a d e r ) 和多个簇 成员( c l u s t e rm e m b e r ) 组成，这些簇头形成了高一级的网络，在高一级网络中， 又可以分簇，再次形成更高一级的网络，直至最高级。分级结构中，簇头节点 负责簇间数据的转发。根据不同的硬件配置，分级结构又可以分为单频分级和 多频分级两种。单频率分级网络( 图2 2 ) 只有一个通信频率，所有节点使用同 一个频率通信。为了实现簇头之间的通信，要有网关节点( 同时属于两个簇的节 点) 的支持。簇头和网关形成了高一级的网络，称为虚拟骨干。而在多频率分级 网络中( 图2 3 ) ，不同级采用不同的通信频率。低级的节点的通信范围较小， 而高级的节点要覆盖较大的范围。高级的节点同时处于多个级中，有多个频率， 用不同的频率实现不同级的通信。在图2 3 所示的两级网络中，簇头节点有两 个频率。频率l 用于簇头之间的通信，而频率2 用于簇头与簇成员的通信。 华东师范大学硕士学位论文 图2 1 平面厢络结构图2 2 单频分级结构 2 2 1 平面结构 圉2 3 双频分缓结构 员 上层 一频率1 下层 一频率2 平面结构的网络比较简单，无需任何的结构维护过程。源站和目的站之间一 般存在多条路径，可以使用多条路径实现负荷分担，也可以为不同的业务类型选 择适当的路径。网络中所有节点是对等的，原则上不存在瓶颈，所以比较健壮。 平面结构中节点的覆盖范围比较小，相对较安全。平面结构的最大缺点是网络规 模受限。在平面结构中，每一个节点都需要知道到达其它所有节点的路由，由于 节点的移动性，维护这些动态变化的路由信息需要大量的控制消息。网络规模越 大，路由维护的开销就越大。当网络的规模增加到某个程度时，所有的带宽都可 能会被路由协议消耗掉。所以平面式结构网络的可扩充性较差。 2 2 2 分层结构 分级结构的最大优点是可扩充性好，网络规模不受限制。必要时可以通过增 加簇的个数或级数来提高网络的容量。分级结构中，簇内成员的功能比较简单， 基本上不需要维护路由，这大大减少了网络中路由控制信息的数量。簇头节点复 杂一些，它要维护好到达其它簇头的路由，还要知道所有节点与簇的所属关系。 但总的来说，在相同网络规模的条件下路由开销要比平面结构的小。如果簇内通 华东师范大学硕士学位论文 信的信息量占较大比例时，各簇可以互不干扰地进行通信，系统的吞吐量要比平 面结构的要高。但是分级结构也有它的缺点。首先，维护分级结构需要较复杂的 簇头选择算法，簇头选择算法需要仔细设计。其次，簇问的信息都要经过簇头寻 路，不一定能使用最佳路由。比如在不同簇中但互为邻居的节点，在平面结构中 可以直接通信，但分簇后要通过两个簇的簇头转交。分级结构要比平面结构有优 势。第一，分级结构有较好的可扩展性。第二，分级结构通过路由信息局部化提 高了系统的吞吐量。分级结构使路由信息局部化，簇内节点无须知道其他簇的拓 扑结构，一个簇的拓扑变化不会被其它簇感知，这减小了路由控制报文的开销。 第三，分级结构中节点的定位要比平面结构简单得多。在平面结构中，想知道一 个节点的位置，需要在全网中执行查询操作。而在分级结构中，簇头知道自己簇 成员的位置，只要查询簇头就可以得到节点的位置信息。第四，分级结构可通过 移动性管理来实现序列寻址。按照节点与簇的关系为节点分配逻辑序列地址，由 簇头充当类似与 i l r 和v l r 功能的位置管理服务器，就可以简单地实现节点定位 和寻址。分级结构是无中心和有中心模式的混合体，可以采用两种模式的技术优 势。虽然采用分级结构后有了相对的控制簇头，但是簇头和簇成员是动态变化的， 节点仍是自动组网的。分级后网络被分成了相对独立的簇，每个簇都有控制中心。 基于有中心的t d 姒、c d 姒、轮询等技术都可以在分级的网络中使用。基于有中心 控制的路由、移动性管理、网络管理技术也可以移植到a dh o c 网络中来。随着 对a dh o c 网络中q o s 要求的提高，采用基于有中心的技术可能是最佳的选择。 所以随着应用的增加，a dh o c 网络逐渐呈现出分级化的趋势。 2 3a dh o c 网络模型分层 参照o s i 七层模型，从各个层面上来分析a dh o c 网络的技术特点，并就各个 层次的构成来逐一介绍。 构筑网络时如果采用a dh o c 方式，所选用各层次的构建方式是可选的。物 理层完成无线信号编码译码、发送和接收等工作；数据链路层控制对共享无线 信道的访问以及对逻辑链路的控制，数据链路层又分为m a c ( 媒质接入控制) 层和l l c ( 逻辑链路控制) 层；网络层是a d h o c 技术的重点，也是它与其他现 有网络的主要区别所在。口v 4 协议、口v 6 协议或其他网络层协议提供网络层数 华东师范大学硕士学位论文 据服务；网络层的单目标路由协议维护路由表，使其与当前的a d h o c 网络拓扑 结构一致：多目标路由协议提供群组通信的底层支持；网际互联支持a dh o c 网 络中与其他现有网络互联，q o s 支持提供可保证的q o s 服务，路由安全提供对 路由协议的安全保障。传输层主要完成端到端通信的建立，目前一般的思路是 对有线网中的t c p 舢d p 进行改造，使之适应无线环境；a dh o c 的高层主要包 括的是建立在a dh o c 之上的无线应用以及接入移动通信核心网的各种业务。 一、 物理层 实际应用中，a dh o c 物理层的设计要根据实际的需要而定。 基于接收发信主要功能的物理层首先要考虑的是通信信号的传送媒质，一般 而言，a dh o c 网络都是基于无线通信，a dh o c 物理层所面临的首要问题就是无线 频段的选择、购买以及分配。目前大家一致采用的都是基于2 4 g h z 的i s m 频段， 因为这个频段是免费的，不需要购买，成本就会得到降低。其次，物理层必须就 各种无线通信机制做出选择，从而完成性能优良的收发信功能。 目前为止，a dh o c 物理层可以选择和参考的标准主要来自构建无线局域网的 各种标准，其中包括i e e e8 0 2 1 l 系列、蓝牙( b l u e t o o t h ) 、h y p e rl a n 等标准 所定义的物理层。 具体说来，a d h o c 物理层所采用的传输技术基本上有三种：正交频分复用技 术( o f 工) m ) 、采用红外线辐射传输技术、宽带扩展频谱技术。 二、数据链路层 数据链路层解决的主要问题包括媒质接入控制，以及数据的传送、同步、纠 错以及流量控制等。因此，a dh o c 数据链路层又分为姒c 和l l c 层。在一般情况下， 我们所关注的主要是m a c 层，因为m a c 决定了数据链路层的绝大部分功能。 针对媒质共享竞争的问题，已经有a l 0 a 、时隙a l o h a 、c s m a ( 载波侦听多路 访问) ，以及i e 髓8 0 2 1 l 所采用的c s 6 f i a c d 。m a c 层主要就是由这些媒质接入方 案充当。由于a l o h a 、时隙a l o h a 、c s m a 都存在媒质冲突、终端暴露以及终端隐藏 等严重的问题，所以，后来就有带冲突检测和冲突避免的c s m a 媒质接入方案的 提出，被用在了i e e e8 0 2 1 l 无线局域网方案中。研究发现，基于无线a dh o c 环 境的c s m a c a 仍然存在着一些问题，于是，一些学者就提出了各种相应的改进形 式作为姒c 层的解决方案，包括针对基于c s 眦c am a c a ( m u l t i p l ea c c e s sw i t h 华东师范大学硕士学位论文 c 0 1 1 i s i o n a v o i d a n c e ) 的改进：m a c a w ( m a c a f o r w i r e l e s s ) 、p a m s ( p 0 w e r a w a r e m u l t i a c c e s sp r o t o c o lw i t hs i g n a l i n g ) 、f a m a s ( f 1 0 0 ra c q u i s i t i o nm u l t i p l e a c c e s s ) 、m a r c h ( m e d i aa c c e s sw i t hr e d u c e dh a n d s h a k e ) 、c a t a ( c o l l i s i o n a v o i d a n c et i m ea l l o c a t i o n ) 、r t m a c ( r e a lt i m em a c ) ，以及 基于p c d 姒姗d 的心层协议( 具有定位功能基于多用户检测的c d 凇系统的m a c 层协议) 。 三、网络层 a dh o c 网络不能采用常规路由协议主要由于以下几种因素：1 a d h o c 网络中 主机间的无线信道可能存在单向信道。2 无线信道的广播特性使得常规路由的网 络选路过程中产生许多冗余链路。3 常规路由的周期性广播路由更新报文会消耗 大量的网络带宽。4 常规路由协议周期性的路由更新报文会消耗大量的主机能 源。此外，某些常规路由协议需要的复杂计算使得c p u 始终处于很高的负载下， 这也同样消耗了大量的能源。这将对有限的主机能源带来更多的压力。 从以上的分析可以看出，一个好的a dh o c 网络层的路由协议应当满足以下特 性要求：分布式运行方式；提供无环路路由；按需进行协议操作；具有可靠的安 全性：提供设备“休眠”操作特性；对单向信道的支持等。 对一个a dh o c 网络层路由协议定量衡量比较的指标应该包括：端到端的平均 时延：分组的平均递交率：路由协议开销；路由请求时间等。 正是由于a dh o c 网络层路由协议基于a dh o c 网络的重要性，它便成为了研究 的一个热点。到目前为止，已经有相当多的标准推出。i e t f 也发布了相关的草案 供讨论。 从总体上说，目前所提出的各种路由协议基本上可以归纳为三种思路： ( 1 ) 把路由协议分为三类：一类是基于路由表驱动( 1 a b l ed r i v e n ) 的路由 协议，一种是按需驱动( o n d 锄锄dd r i v e n ) 的路由协议，还有一种是两种模式 的混合形式。 ( 2 ) 平面结构路由和层次结构路由。这是从逻辑结构方面考虑进行的划分。 平面结构中，节点地位平等，维护的信息量相同。层次结构路由中，网络结构按 级分层，分为骨干网和子网，这样，维护的工作就统一由骨干网承担。 ( 3 ) 基于q o s 的路由。多媒体业务的传输需要不同q o s 保障( 包括带宽、时 华东师范大学硕士学位论文 延、时延抖动、吞吐量、丢失率等) 。在a d h o c 网络路由协议中，对于0 0 s 的支 持还很不成熟，只有少数的如a b r 、s s r 以及清华提出的l sq o s 有此功能，它 们多是以链路的稳定性作为q o s 的衡量标准。目前a d h o c 网络中对q o s 的支持一 般借鉴i n t e r n e t 上建立区分服务和集成服务的模型，做适当的修改。 四、传输层 到目前为止，a dh o c 网络的传输层还是借鉴有线网络中传输层的方法，把 t c p ，u d p 基于无线环境进行修改，以适应无线环境，完成传输层的功能。 传统的t c p 会使无线a dh o c 网络分组丢失很严重，这是因为无线差错和节点 移动性而使t c p 将所有的分组丢失都归因于拥塞并启动拥塞控制和避免算法，所 以若在无线a d h o c 网络中直接采用传统的t c p 协议将可能导致端到端的吞吐量 的降低。所以，必须针对传统的t c p 进行改进。到目前为止，已经有多个t c p 改 进方案提出，比如t c ps a c k 和t c p a s a c k 等等。 针对l ) p 的改进与t c p 相似。 五、应用层 a dh o c 网络的应用层指定的是各种各样类型的业务。在实际的实施的时候， 可以采用各种各样的应用层协议和标准，比如w a p ( 无线应用协议) 协议等。 基于a dh o c 技术的网络所承载的业务同其他各种类型网络一样，主要是传统 的业务和人们给予厚望的“无线宽带数据业务”。 2 4 a dh o c 路由协议 在a dh o c 网络中，节点移动导致网络拓扑结构不断变化。如何迅速准确地选 择到达目的节点的路由，是a d h o c 网络的一个重要和核心的问题。 2 4 1a dh o c 网络路由与传统移动通信系统的区别 目前常见的移动通信系统有两类：蜂窝移动通信系统和无线局域网。 在蜂窝移动通信系统中，移动节点间呼叫的路由选择及建立主要是通过固定 网络设各，如交换机，r m l r 等完成。而在a dh o c 网络中，不存在这样的固 定设备，节点问路由选择完全由移动节点完成。同时，蜂窝移动通信系统网络结 构比较稳定，a d h o c 网络拓扑结构经常变化，影响路由选择。 华东师范大学硕士学位论文 在无线局域网中，移动节点配有无线网卡，通过无线接入点连接到固定网络， 因此，无线局域网可以看成是一个单跳网络，分组处理不用通过网络层；而a dh o c 网络则是一个多跳的网络，终端主机一方面作为主机，另一方面作为路由器运行 路由协议，参与分组转发和路由维护。a dh o c 网络研究的一个主要内容是以路由 协议为核心的网络层设计。 因此，a dh o c 网络与传统移动通信网络在路由选择方面有很大差异，必须采 用合适的路由协议以解决路由选择问题。 2 4 2a dh o c 路由协议分类 根据源端何时获得路由信息，可以将路由协议分为先应和反应路由协议。在 先应路由协议，或称为表驱动( t a b l e d r i v e n ) 路由协议6 1 中，每个节点试图维护到 所有已知目的节点的路由表，节点之间周期性或在网络拓扑改变时交换路由信 息，减少了获得路由的延迟，能够立即判断目的节点的可达性，但是消费了网络 资源，此外它完全浪费了一些资源来建立和重建那些根本没有被使用的路由。反 应路由协议1 7 】 8 ，或称为按需路由协议，包括路由发现和路由维护两个过程。反 应路由协议平时并不实时地维护网络路由，只有在节点有数据要发送时才激活路 由发现机制寻找到达目的节点的路由。它不需要花费资源来维护无用的路由，但 路由发现过程比较昂贵而且不可预测，同时路由延迟与先应路由协议中恒定的查 表时间相比，更加多变。 _ _ _ _ h h - _ _ _ _ “_ “一 l 垂臻壁垫垒! ! ! ! 髓宴怒塑 r ； ； 奏墅叠照皂照堡j l 燕最照! 韭塑一 i 烹， ，j 一一 ，董，。j ，j 、 ；旦熙y ji 册里j垡笾嬲 。腿| | 熙煦j 一。j l 一 毽熙 图2 4a d1 1 0 c 路由协议分类图 根据网络中各节点的作用是否相同，可以将协议分成平面协议( u n i f o 衄 p r o t o c 0 1 ) 和分层协议( n o n 一彻面衄p r o t o c 0 1 ) 。在平面协议中各节点以相同的方式 发送和响应路由控制信息，避免了维护高层结构的费用，但扩展性差。在分层协 华东师范大学硕士学位论文 议中，每个节点或者从邻居节点中选出一部分节点进行路由计算或转发分组；或 者被分成簇，其中一些节点成为簇头( c l u s t 小h e a d ) 或网关( g a t e w a y ) 。分层协议 通过减少参与路由计算的节点数来限制路由计算的复杂性，增加了扩展性，减少 了通信开销，但在高度动态的网络中，维护拓扑结构需要大量资源。 2 4 3a dh o c 路由协议的评价标准 主要包括以下几个方面的指标1 0 】 1 1 】： ( 1 ) 端到端的数据吞吐量和时延：通过报文质量衡量路由协议性能。 ( 2 ) 路由协议的效率：即归一化路由开销，控制信息与用户数据信息的比 例。 ( 3 ) 路由失效数：衡量路由协议的健壮性。 不同路由协议在不同环境中，其性能好坏有很大差异。即使是同一路由协议， 在不同的网络环境中，其性能指标也有很大差异。a d h o c 网络环境主要涉及：网 络规模、节点移动速度、信道传输带宽、单向信道比率、“休眠节点”比率等。 2 5 几种典型的路由协议 2 5 1d s d v 路由协议 d s d v ( d e s t i a t i o n s e q u 髓c e dd i s t a n c e v e c t o r ) 路由算法【1 2 】是一种平面的、 表驱动路由协议，是传统的距离向量算法的改进版本。每个移动节点维护一张路 由表，包含所有可到达的目的节点、到达目的节点的跳数和由目的节点指定的序 列号( s e q u e n c e n u m b 哪。序列号用于从新的路由中区分过时路由，避免环路。 每个节点周期性和在路由发生显著改变时向邻居节点发送当前路由表。接收 节点将收到的到每个目的节点的序列号与自己路由表中到该目的节点的序列号 进行比较，如果收到的路由信息中的序列号较高，则接收节点更新自己的路由表 项，同时将发送者作为下一跳；如果收到的路由信息的序列号和自己的序列号相 同，但路由度量较小，接收节点也更新自己的路由表。路由表采用全表更新( 血u d 1 1 1 p ) 和部分更新( i n c r e m e n t du p d a t e ) 两种方式进行更新。前者向邻居节点发送 整个路由表，适用于拓扑结构快速变化的网络，而后者仅仅发送从上次更新以来 华东师范大学硕士学位论文 度量发生变化的路由表项，适用于拓扑结构相对稳定的网络。 d s d v 算法收敛速度慢，需要周期性地向外发布路由信息，效率低下。 2 5 2d s r 路由协议 d s r ( d y n 锄i cs o u r c er 0 u 血g ) 中每个节点维护一个路由缓存存储它所知 道源路由，并在学到新路由时更新路由缓存。d s r 协议包含路由发现和路由维 护两个部分。 当源节点有数据要向目的节点发送时，它首先检查路由缓存中是否已经包含 到目的端的、未过期的路由，若有，则使用该路由发送分组：否则，广播路由请 求分组发起路由发现过程。路由请求分组具有源和目的节点地址以及一个惟一的 标识符。每个中间节点同样检查是否有到目的端的路由，若没有则在分组记录中 增加它的地址，并向邻居转发。为了限制路由请求传播的数量，节点在第一次收 到某路由请求分组，并且在分组记录中不含有它的地址时，才处理该路由请求。 路由应答分组可以在两个地方产生：当目的端产生路由应答分组时，它将路由 请求分组中的路由记录放入路由应答分组中。当含有末过期的到目的端路由信 息的中间节点收到路由请求分组时，也产生路由应答分组，此时它将路由缓存中 的路由信息，以及路由请求分组中记录的路由共同放入路由应答分组中。应答节 点可以采用三种方式发送路由应答分组。如果应答节点含有到源端的路由，则使 用该路由直接进行发送；否则，如果网络链路是对称的( 双向链路) ，则可以利用 所发现的路由逆向发送，如果链路不对称，则应答节点将找到的路由放入路由发 现分组中，发起向源端的路由请求。 d s r 协议采用路由错误分组和确认分组进行路由维护。当节点在数据链路 层遇到传输错误时，向源端发送路由错误分组。收到路由错误分组的节点，从路 由缓存中删除错误的路由。确认分组用于证实路由的正确运行，同时节点也可以 通过检测到沿路由的下一跳节点转发分组来被动的获得确认。 2 - 5 _ 3a o d v 路由协议 a o d v ( a d h o co n d 锄dd i s t a n c ev e c t o rr o m i l l 曲【1 4 】是d s r 和d s d v 的结 合，它借用了d s r 中按需进行路由发现和路由维护机制，以及d s d v 中的逐跳路 华束师范大学硕士学位论文 由、序列号、定期广播。 2 5 4t o r a 路由协议 t o r a ( t e m p o r a l l yo r d e r e dr o 血n g 灿g o 删 】m ) 1 8 是基于链路逆转( 1 i n k r e v c r s a l l 算法的高度自适应的、分布式、按需路由算法，能提供到目的节点的多 条路由，主要特点为控制信息位于发生拓扑改变链路附近的小的节点集合中。每 个节点维护有关相邻节点的路由信息，协议具有路由产生、路由维护和路由删除 三个基本功能。 t o r a 的行为可以描述为：分组通过由管道组成的网络往下流到目的节点。 每个节点相对于目的节点有一个由路由协议计算出的高度。如果节点a 流向外的 最后一条管道被阻塞，以致其中的分组不能流动，则a 的高度被设置成高于任何 相邻节点的高度，使分组流出a ，流向周围节点。节点之间“高度”度量与链路 失效的逻辑时间有关，同步问题在t o r a 中非常重要。t o r a 假设各节点具有 同步时钟，如通过同步时钟使各节点获得同步。t o r a 的路由删除采用洪泛， 在整个网络广播删除分组来删除无效路由。 t o r a 中可能发生潜在的振荡，这种振荡类似于距离向量路由协议中计数 到无穷问题( c o u n t t 0 i n f i n i 动，但它是临时的，路由最终是收敛的。 2 6 各类路由协议性能比较 上面介绍了a dh o c 网络中路由协议的分类及几种代表性的路由协，下面 就对其性能指标做一个比较。 2 ，6 1 按需路由协议与表驱动路由协议的比较 主要从路由信息的可行性、路由结构、周期路由更新、处理