（计算机软件与理论专业论文）ad+hoc网络中基于负载平衡的自适应多径路由协议.pdf

摘要 a dh 网络是一种自组织的无线网络，它具有无线传输、高度的动态拓扑、 无中心、多跳路由等特点。这使得它在某些应用场合具有独特优势的同时也提出 了不少技术上的难题，其中路由闯题是目前a d h 阏络中的研究热点之一。 本文提出了一种基于负载平衡的自适应多径路由( u l a m r ) 协议，该协议中 用阻塞率表示节点的负载情况u l m r 协议与其他的多径路由协议最大的不同之 处就在于利用一种全新的负载平衡计算策略作为路由选择标准，并且建立一组无 相交节点路径。在发送数据瓣，将动态选择负载最小的路由作为主路由。 为了验证ib a h 瞻协议豹性能，本文使用无线网络仿真工具g l 丽幻s i m 对 u l a m r 与a i v 膏唾矬敷进行了仿真，然后分析了数据流；网络拓扑变化及节点 个数对u l 聪稠艮街影响并给出了其适用的a di l 网络场景。 鬟键词潮飘魄月终i j 硝m 阻协议负载平衡多径路由自适应 a b s h a c t a b s t r a c t a dh d cn e t w 叫i ki saw i r c l e s sn c 押，o r k ，w h i c hc a no r g a n i z ei t s c l f i t 丘g u r c sw i r c l c s s t t 髓谢锚i o n ，h i g l i l yd y n a m i ct o p o l o g y m u n i p l eh 叩s a n dw i t h i tc e n t e r t h e 鳊 c h a r a c t e r sm a k ei th a v cl l n i q u ca d v 锄t a g ci ns 吣ea p p l i c a t i o n s ，b u ta tt l l es a m et i m e ，i t g i v e su sm 蛆yt c c h i c a ld i m c i l n i e s r 咖t i n gb c l o n g st ot h e p r o b l e m s 柚di sa l s oo n c o ft l l eh o t s p o to f a dh o cn e 撕o f k sr e s e 删n g a ma d a p t i v cm u m p a t h 咖t i n gp r o t o o o lb 弱e do nl o a d b a l 蛆c e d ( u 弧m r ) i s p r e s e n t e d ，i w h i c ht h eb l o c km t ed e n o t 髓t h el o a do fan o d e 1 1 i el b a m rp m t o c o l t a k 骼an o v c ll o a dc 0 恤p u t j l l gs t r a t e g yt ob u i l das e to fn o d e d i s j o i tp a t l l s 柚d d y n a m i c a l l ys e l c c t st h ep a t l lw i t ht l l em i n i m a ll o a d 雒t h em a i np a t h ，w l l i c hi st h em o s t i m p o n a td i d i c r c n c cb 婀e n rw o r ka n do t h c rw o r ko nm 1 j l t i p a l hp r o t o 1 t bv a l i d a t eo i l ru j a m rp r o 咖l w eu t h cw i r c l 龉sn c t w o r ks i m u l a t i o nt 0 0 l g l o m o s i ml os i m u l a t ct h ep r o 咖l so f 洲r ，a o d v 柚dd s r ，a n da n a l y z et l l e c 肌c tt 0i b a m ro fn e 柳o r kt m 蚯cl o a d ，c h 髓g e so fm t w o r kt o p o l o g y 卸dt h cn 啪b c r o fn o d c s 胁a l l y ，w eg i v ct h e 印p l i b l cd 岫a i n so fo u ru a l r k e y w o r d ：a dl 五m l w o r k s m 讪籼 i j k 气m rp 玎叽o li 棚db 曩b n c e a d 印廿v e 创新性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或 其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做 的任何贡献均已在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名； 硅：主亟墨 日期羔即舌 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕 业离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学： 学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全 部或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。( 保密的论文 摘解密后遵守此规定) 本学位论文属于保密，在一年解密后适用本授权书。 本人签名 导师签名 蓝：查强 重：垒鱼 日期f f 1y 日期2 ，。f 7 i r 第一章绪论 第一章绪论 1 1 引言 近几年，无线网络在支持移动性方面的发展非常迅速，但一般来说，移动无 线通信网络通常以蜂窝移动通信网络或无线局域网方式出现，使移动网络仍然需 要以通信基站或接入点为基础。在蜂窝通信网络中，移动终端和固定基站互相通 信，移动终端不具备路由功能。在无线局域网中，配备有无线局域网网卡的移动 节点通过无线接入访问点连接到现有的固定网络。蜂窝移动通信网络和无线局域 网都属于现有网络基础设施范畴，但在战场、科学考察、探险、发生地震或火灾 后不便预先铺设网络设备的场合，蜂窝移动通信网络或无线局域网并不适用。在 这种情况下，一种无基础设旌的移动网络一一a dh o c 网络而被提出。 移动a d h o c 无线网络又称移动自组网、多跳网络，是一种特殊的在不借助任 何固定基础网络设施的情况下，在有限的范围内实现多个移动终端或主机( 统称 为节点) 的临时互联，它为局域网内的移动通信网络提供了一种灵活的互联方式。 与传统的无线网络相比较，a dh 0 c 网络可以更好的体现移动节点随意、灵活、自 治的特点。 a dh o c 网络具有无线传输、高度的动态拓扑、无中心、多跳路由等特点，这 使得其中许多问题变得十分复杂而且难以实现。直到现在，a dh 0 c 网络中仍然存 在着许多棘手难以解决的问题【1 】【2 】。在a dh 0 c 网络中，每一个节点既是接收器也 是发射器，它们具有报文转发能力，节点间的通信可能要经过多个中间节点的转 发，即经过多跳到达f 3 j 。a dh 0 c 网络中的节点是可以移动的，并且节点也可以随 时加入或退出，网络中的一些链路就会随着节点的变化而变化。因此，a dh 0 c 网 络的拓扑结构是随时变化的，这种变化具有不可预知性。考虑到a dh 0 c 的动态拓 扑结构，传统的用于因特网的路由协议无法适应a d 1 0 c 网络的实际需要。因此， 路由协议成为移动a dh 0 c 网络研究中关键的问题之一。 1 2a dh o c 网络中路由协议的研究现状 根据a d i 无线网络路由协议的特殊性，近年来提出了多种a dh o c 网络路 由协议以及解决方案。根据路由触发原理，目前的路由协议大致可以分为袁驱动 的预先路由协议、源起始的按需路由协议两种： 1 ) 表驱动的预先路由协议：每个节点维护一张包含到达节点的路由信息的路由 表，并根据网络拓扑的变化随时更新路由表，所以路由表可以准确地反映网络 的拓扑结构；源节点一旦要发送报文，可以立即获得到达目的节点的路由，这 类的路由协议通常是通过修改现有的有线路由协议来适应a dh 0 c 无线网络要 求。因此这种路由协议的时延较小，但是协议需要大量豹路由控制报文路由， 2 a dh o c 网络中基于负载平衡的自适应多径路由协议 协议的开销较大。常用的表驱动的预先路由协议有d s d v ( d e s t i 舱t i s e q u e n c e d d i s t 锄c e 、k t o f ) 【4 1 ，w r p ( w 确c 鹞r ( m 咖g p m l o c 0 1 ) 【5 1 等。 d s d v 协议通过给每个路由设定序列号来避免路由环路的产生，采用时间 驱动和事件驱动技术控制路由表的传送，即每个移动节点在本地都保留一 张路由表，其中包括所有有效信宿点、路由跳数、信宿路由序列号等信息， 信宿路由序列号用于区别新旧路由以避免环路的产生。每个节点周期性地 将本地路由表传送给邻近节点，或者当其路由表发生变化时，也会将其路 由信息传给邻近点，当无节点移动时使用问隔较长的大数据包( 包括多个 数据单元) 进行路由更新；邻近节点收到包含修改的路由表信息后，先比 较信源k 信宿路由序列号的大小，信宿路由序列号大的路由将被采用，而 信宿路由序列号小的路由则被淘汰，若相同，则采用最佳制式的路由( 如 最短路径) 。 无线路由协议w r p 是一种矢量路由协议，每个节点都维持一个距离表、 路由表、链路开销表和报文重传表，通过其邻近节点的最短路径生成数s s t ( s h o np a t hs p a 舳i g 讯c ) 。生成自己的s s t 后，再向邻节点传递更新信 息。当网络路由表没有任何变化时，接收节点需回传一个空闲报文以示连 接，否则，修改距离表，寻找更优路径。这种算法的特点是当检测到任意 相邻节点变化时，则检查所有相邻节点的坚固性以消除回路，具有较快的 收敛性。 2 ) 源起始的按需路由协议：是一种当需要时才查找路由的路由选择方式。节点不 需要维护及时准确的路由信息，当需要发送数据时才发起路由查找过程。与表 驱动的预先路由协议相比，源起始的按需路由协议的开销小，但是数据报传送 的时延较大，不适合予实时性的应用。常用的源起始的按需路由协议有a 1 ) d v ( a dl 五o c0 n d 锄锄dd i s t 蛐o cv b d o r ) 【6 j ，d s r ( d y 眦i cs 伽i r o u t i n g ) 【7 】 和t o r a ( t c m 删y - 0 i d 阿r o u t i n ga 1 9 0 r i t h m ) 1 8 】都属于此类协议。 a o d v 协议：源节点发送数据前先广播一个路由请求消息，附近节点收到 后再次广播，宣到请求消息到达目的节点或到达知道目的节点路由的中间 节点，目的节点或中间节点沿原来路径返回响应消息，源节点收到响应后 就知道到达目的节点的路由。 d s r 协议称为动态源路由协议，是一种源路由协议，每个分组的分组头中 包含了源节点到目的节点的整条路由信息。它采用路由缓存技术，用于存 储源路由信息，当学习到新的路由时则修改路由缓存内容，该协议包含两 个方面：路由发现和路由维护。 t o r a 协议称为临时预定路由算法，是一种源初始化按需路由选择协议， 它采用链路反转的分布式算法，具有高度自适应、商效事和较好的扩充性， 第一章绪论 比较适合高度动态移动、多跳的无线网络，其主要特点是控制报文定位在 最靠近拓扑变化的一小部分节点处，因此节点只保留邻近点的路由信息。 该算法中路由不一定是最优的，常常使用次优路由以减少发现路由的开销。 t o r a 协议包括3 个基本模块：路由的创建、路由的维护和路由的删除。 上面的表驱动的预先路由协议和源起始的按需路由协议的最大共同点就是在 源节点和目的节点问只存在一条路由。但是，无线连接的不可靠特性和无线节点 不停移动导致的网络拓扑结构的持续变化，使单一路径的a d i o c 网络路由性能一 直不能获得太大的突破。由于多路径所具有的稳定和提高网络资源利用率的特性， 它比原来的单一路径更适合于o o s 路由的要求。因此，a d 1 0 c 网络希望能够打破 单一路径路由的局限，采用多路径进行路由。采用多路径的网络路由协议也相继 被提出。其中，对a o d v 进行扩展盼协议有a o d v - b r ( a dl 眦o n d e m 姐dd i s t a n c e v e c t o r - 日妇c k l l pr t i n g ) 【9 】，a o m d 、，( a dh o co n d c m 强dm u l t i p a t hd i s t 锄c ev e c t o r r o 嘶n g ) 【1 0 】等；对d s r 进行扩展的协议有 口d s r 0 订u m 胆t hd y l i 锄i cs o u r o c r 血1 1 】和m s r ( m u l t 蛔t hs o l l r c cr 伽t i n g ) 1 1 2 l 【1 3 】等。 a o d v - b r 是对a o d v 的扩展，多径路由是在目的节点向源节点发送响应消息 的过程中建立的，它利用无线通信的特点，一个未被选中的节点侦听副并不是 直接发送到自己的r 鄹巳p 包，它就将这个r r e p 包的直接目的节点作为自己发 往目的节点的下一跳，利用这种方法，它就能接收到大量的对于同一路由的 r r e p 包，它将挑选一个最佳路由记录到自己的路由表中。当r i t e p 包最终到 达源节点时，一条从源节点到目的节点主路由将建立起来，其他的一部分节点 也能建立起到目的节点的备用路由。 a o m d 、，也是对a o d v 的扩展，它利用公告跳数机制( a d v c r t i s c dh o p c o u n t m e c h a n i s m ) 建立一个无环、无公共链路的多径路由，在路由建立过程中，中 间节点不会立刻丢弃路由请求包的副本，而是判断这个包是否提供了一条到源 节点的无环、无公共链路的路由。 m p d s r 是对d s r 扩展的一个满足q o s 的多径路由协议，它利用一个新的q o s 衡量标准一一端到端的可靠性，来创建和选择路由。这个协议尝试寻找满足端 到端可靠性的一组无相交节点的路由。 m s r 是对按需路由d s r 的扩展，协议中，每个节点对到目的节点的每一个路 由都维护着个多径表( m u n i p l e - p a 也t a b l e ) ，这个表包含了路径编号、目的节点 i d 、延迟和计算出的路由传输量。目的是为了均衡每条路由的传输负载。 1 3 研究内容 本文的工作重点主要侧重予a dh 0 c 网络多径路由协议的研究。在以上传统的 路由协议中，多采用最短路径作为节点间通信豹路由，此路由选择机制存在着很 4 a dh o c 网络中基于负载平衡的自适应多径路由协议 多不足之处，例如，无法很好的解决拥塞问题，公平性很差，不能节约节点能量 等等。这些问题可能会导致某些节点因能量损耗过快而过早断开链接，将会降低 整个网络的寿命。虽然有些路由协议也采用了多条路由传输数据，表面上能起到 一定的负载平衡作用，但是每条路由并不是负载最优的，无法达到负载平衡的最 优效果。因此，本文提出了一种基于负载平衡的自适应多径路由( u i a m r ，b 鹤e d l 舶d b a l a n c e d a d a p t j v cm u l t i p a _ 也r o u t i n g ) 协议，该协议中用阻塞率表示节点的 负载情况，解决传统路由选择机制的不足之处，进一步提高整个a d 1 0 c 网络的性 能。该协议与其他的多径路由协议最大的不同之处就在于利用一种全新的负载平 衡计算策略，作为建立和选择路由的标准，然后建立一组无相交节点路径 ( n o d e d i s j o i n tp a 也s ) 。在传输数据的过程中，采用自适应机制，动态选择发送数 据的生路由，以求达到负载平衡的最优效果。h i a m 鼠协议是在按需路由思想上结 合m a c 8 0 2 1 1 设计出来的，主要工作集中在以下几个方面： 1 1 传统的按需路由协议是一个尽力而为的路由协议，其选择路由的标准是跳数最 小，而i b a m r 选择路由的标准是路由的负载，因此，在本文中给出了路由 负载的一种全新计算方法。 动根据负载的定义，如何在协议分组中记录路由的负载以及如何根据这些负载信 息选择路由是本文的一个工作重点。 3 1 在路由建立过程中，源节点将会建立一组无环、无相交节点路径：发送数据时， 将动态选择负载小的路由作为主路由。 为了评价u t a 厦r 的性能，本文最后还使用无线网络仿真工具g 1 0 m o s i m 对 l 蝴r 协议与a o d 、，协议和d s r 协议进行了仿真，主要对比了三者的端到 端分组传递率、端到端平均延迟、端到端平均吞吐事，以及分析了数据流、网 络拓扑变化及节点个数对u k 蝴r 协议的影响并给出了一个该协议所适用的 a d h 0 c 网络场景。 1 4 论文各章节的安捧 本文各章节的安排如下： 第二章首先介绍了a d 1 0 c 网络的定义、特点及其应用，另外还对路由协议做 了一个介绍。接着分析了a dh o h c 网络中传统的单径路由、多径路由协议及其主要 存在的问题。 第三章首先介绍了u a m r 协议的重要基础：路由负载的计算方法。接着详 细介绍了u l a m r 的设计：协议分组中增加的负载信息、无环路由和不相交路由 的建立，选择路由的自适应性等。 第四章首先介绍了无线网络仿真工具g l o m o s i m ，然后利用它对i b a m r 及 a i 如、d s r 进行仿真比较，最后着重分析了仿真结果。 第二章a d h o c 网络及其路由协议 第二章a dh o c 网络及其路由协议 本章主要介绍a dh 0 c 网络以及路由协议的一些相关知识。首先介绍了a dh 0 c 网络产生的背景、发展历史、定义、特点、应用和网络协议栈。然后介绍了路由 协议面l 临的问题，最后介绍了典型的单径、多径路由协议。 2 1 a d h o c 网络介绍 2 1 1a dh 0 c 网络的产生背景 随着信息技术的发展，人们对移动通信的需求越来越强。近年来，移动通信 技术得到了飞速发展和普及。蜂窝移动通信系统、无线局域网、蓝牙技术 ( b l u e t 0 0 也) 、家庭无线网( h o m e r f ) 等移动通信新技术纷纷涌现。这些技术的 出现，极大方便了人们的生活，同时也推动了无线通信技术的发展。 无线通信网络按照其组网方式分为两类：一类是集中式控制，无线网络的运 行要依赖预先部署的网络基础设施。典型的例子有：蜂窝移动通信系统，依靠基站 和移动交换中心等基础设施的支持；基于接入点( a o 鼹p 0 m ) 和有线骨干网模 式工作的无线局域网。另一类是能够临时快速自动组网的移动通信技术，也就是 a dh o c 网络通信技术，能够应用于战场上部队的快速展开和推进、发生地震或水 灾后的营救、野外科学考察、临时会议等场合。 “a d 融”一词来源于拉丁语，意思是“专用的、特定的”。a dh 0 c 网络通 常也可以称为“移动专用网络”( d a n e t ，m 0 b i l ea dh 0 cn c t 啪瓜s ) ，“无固定设 施网”、“自组织网”、“对等网络”或“移动分布式多跳无线网络”等等。在本论 文中，用“a d 融”来描述这种移动分组式网络。由于组网快速、灵活，使用方 便，目前得到越来越广泛的应用，已经成为移动通信技术发展的一个重要方向， 在未来的通信技术中占有重要地位。 a dh d c 网络的前身是分组无线阿( p a c k c tr a d i on e 咐o r k ) 1 1 q 唧。早在1 9 7 2 年， 是由美国国防部远景研究规划局( d a r p a ) 启动了分组无线网项目p 鼢吧一1 4 1 ，研 究在战场环境下利用分组无线网进行数据通信。在1 9 8 3 年n a r p a 启动了高残存 性自适应网络s u r a n ( 哪v i v a m ea d a p t j v cn c t 咖r k ) 项目，研究如何将p 姗的 研究成果加以扩展，以支持更大规模的网络。在1 9 9 4 年。d a _ r l ，a 又启动了全球 移动信息系统g i o m o ( g i o b a l 脚b n ci n f b 咖a t i 0 s y s t c m s ) 项目，旨在对能够满足 军事应用需要的、高抗毁性的移动信息系统进行全面深入的研究。成立于1 9 9 1 年 的m 髓8 0 2 1 1 标准委员会采用了“a dh o c 网络”一词来描述这种特殊的自组织对 等式多跳移动通信网络。另外个具有影响力的研究分支是因特网工程任务组 ( 趼) ，成立了专门的m n e r 工作组【1 6 l 。a dh 0 c 的设计思路也由传统的单一 技术体系过渡到基予臻的多技术体系，从而使a dl i d c 具有开放性、适应性和灵 6 a dh o c 网络中基于负载平衡的自适应多径路由协议 活性，提高了开发的速度。 2 1 2 a dh o c 网络 1 a d h o c 网络的定义 移动a dh 0 c 无线网络又称移动自组网、多跳网络，是一种特殊的在不借助任 何固定基础网络设施的情况下，在有限的范围内实现多个移动终端或主机( 统称 为节点) 的临时互联，它为局域网内的移动通信网络提供了一种灵活的互联方式。 与传统的无线网络相比较，a dh o h c 网络可以更好的体现移动节点随意、灵活、自 治的特点。它不仅能够充分调动节点自身的通信和计算能力，而且还可以为用户 提供更为复合多元的服务，完全符合末端网络发展的趋势。a dh o c 网络的应用早 已不仅仅限于灾难救助、紧急会议等特殊情况，而逐渐开始拓展到家庭网络、个 人网络等许多新的领域当中。 l 砖￥硅， 弋i b ， i “ ，叠d 口 恳ox ， 便攮机 车鼗考 e - ) 物建网络结构 图2 1 典型的a d t o c 网络物理结构和逻辑结构 a d1 1 0 c 网络是由一组带有无线收发装置的移动终靖组成的一个多跳犒时性自 治系统，移动终端具有路由功能，可以通过无线连接构成任意的网络拓于卜，这种 网络可以独立工作，也可以与h t 锄e t 或蜂窝无线网络连接。在后一种情况中，a d h o c 网络通常是一末端子网的形式接入现有网络。考虑到带宽和功率的限制，a d h 0 c 网络一般不适于作为中间承载网络，它只允许源节点或目的节点是网络内部节 点的信息进出，而不让其他信息穿越本网络，从而大大减少了与现存i n t c m c t 互操 作的路由开销，而且节点是可以移动的，并且节点也可以随时加入或退出，网络 中的一些链路就会随着节点的变化而变化，因此，a dh 0 c 网络的拓扑结构是随时 变化的，这种变化具有不可预知性。a dl l 0 c 网络中，所有节点的地位平等。无需 第二章a d l t 瞬络及其路由协议 7 设置任何的中心控制节点，每个移动终端兼备路由器和主机两种功能：作为主机， 终端需要运行面向用户的应用程序；作为路由器，终端需要运行相应的路由协议， 根据路由策略和路由表参与分组转发和路由维护工作。在a d h 0 c 网络中，节点闻 的路由通常由多跳组成，由于终端的无线传输范围有限，两个无法直接通信的终 端节点往往通过多个中间节点的转发来实现通信。所有它又被称为多跳无线网、 自组织网络、无固定设施的网络或对等网络。a dh 0 c 网络同时具备移动通信和计 算机网络的特点，可以看作是一类特殊的移动计算机通信网络。图2 1 ( a ) 给出了 a dh o c 网络的一种典型的物理网络结构，图2 1 ( b ) 是其逻辑结构，图中终端a 和 i 无法直接通信，但是a 和i 可以通过a _ b g i 进行通信。 2 a d h o c 网络的特点 与其他传统网络相比，a dh 0 c 网络具有如下显著特点【1 _ 7 】f 1 8 l 。 1 1 动态变化的网络拓扑 a dh o c 网络中，移动终端能够以任意可能的速度和移动模式移动，并且可以 随时关闭电台，加上无线发送装置的天线类型多种多样、发送功率变化、无线信 道间的互相干扰、地形和天气等综合因素的影响，移动终端问通过无线信道形成 的网络拓扑随时可能发生变化，而且变化的方式和速度难以预测。在网络拓扑图 中，这些变化的特点主要体现在节点和链路的数量及分布的变化。而对于传统有 线网络，网络的拓扑较为稳定。 2 ) 无中心和自组织性 a dh o h c 网络采用无中心结构，网络中没有绝对的控制中心。所有节点的地位 平等，即是一个对等式网络，各节点通过分层的网络协议和分布式算法协调彼此 的行为。节点可以随时加入和离开网络。任意节点的故障不会影响整个网络的正 常运行，与有中心的网络相比，具有很强的抗毁性。无中心和自组织特点使得a d h o c 网络可以实现快速自动组网。 3 ) 多跳路由 由于节点发送功率的限制，节点的覆盖范围是有限的。当要与其覆盖范围以 外的节点通信时，需要中问节点的转发。即要经过多跳。与普通网络中的多跳不 同，a dh 0 c 网络中的多跳路由是由普通节点共同完成的，而不是由专用的路由设 备( 如路由器) 完成的。反过来，如果可以使用多跳路由，节点的发送功率可以 很低，从而可以达到节省电能延长电池工作时间的目的。 移动终端的便携性 移动终端具有携带方便、轻便灵巧等优点，但也存在固有缺陷，如能源有限、 内存较少、c p u 处理能力较低和成本较高等，从而给应用的设计开发和推广带来 一定难度，同时显示屏等外设的功能和尺寸受限，不利于开展功能较复杂的业务。 8 a dh o c 网络中基于负载平衡的自适应多径路由协议 考虑到成本和易于携带，移动终端不能配各太多数量的发送接收器，并且节点 般依靠电池供电。因此，如何高效地使用节点的电能和延长节点的工作时间是一 个十分突出的问题。 5 1 无线传输 a dh 0 c 网络采用无线传输技术，由于无线信道本身的特性，它所能提供的网 络带宽相对于有线网络要低得多，并且无线信道的质量较差。考虑到竞争共享无 线信道产生的冲突、带宽、并且会随时间动态变化。传统的共享广播式信道是一 跳共享的，而a dh o c 网络中节点的发送功率受限，广播信道是多跳芡享的：个 节点的发送，只有其一跳相邻节点可以听到，而此范围之外的其他节点察觉不到。 这一特性一方面提高了信道的空间重用度，另一方面使得分组的冲突与节点所处 的地理位置相关。此外，地形和发射功率等因素使得a di l o c 网络中可能存在单向 无线信道。例如，车载终端的发射功率大于手持终端，手持终端可以收到来自车 载终端的信号，而车载终端无法收到来自手持终端的信号，即存在从车载终端到 手持终端的单向信道( 如图2 1 ( b ) ) 中节点b 到节点e 的无线链路。 6 ) 安全性差 a dh 0 c 网络是一种特殊的无线网络，由于采用无线债道、有限电源、分布式 控制等技术，它更加容易受到被动切听、主动入侵、拒绝服务、剥夺“睡眠”等 网络攻击。另外，a dh o c 网络由节点自身充当路由器，不存在命名服务器和目录 服务器等网络设施，也不存在网络边界的概念。这就使得a dh 0 c 网络中的安全性 非常复杂，传统网络中的许多安全策略和机制将不再使用。因此，信道加密、抗 干扰、用户认证、密钥管理、访问控制和其他安全措藏都需要特别考虑。 3 a d h o c 网络的应用 a dh 0 c 网络的许多优良特性使它在民用和军事通信领域占据一席之地提供了 有利的依据。首先，网络的自组织性提供了廉价并且快速部署网络的可能。其次， 多跳和中间节点转发的特性可以在不降低网络覆盖范围的条件下减少每个终端节 点的发送功率，从而降低了天线和相关发射，接收部件的设计难度和成本，从而为 移动终端的小型化、低功耗提供了可能。从共享无线信道的角度来看，a d1 1 0 c 网 络降低了信号冲突的几率，提高了信道利用率。从用户的角度看，低功率的无线 电波产生的电磁辐射较少，对用户身体健康影响较小。另外，网络的鲁棒性、抗 毁性满足了某些特定应用的需求。总的来说，它的应用可以归纳为以下几类。 1 ) 军事应用 军事应用是a dh o c 网络技术的主要应用领域。因其特有的无需架设网络设施、 可以快速展开、抗毁性强等特点，它是数字化战场通信的首选技术，并已经成为 战术互联网的核心技术。为了满足信息战和数字化战场的需要，美军研制了大量 第二章a dh 网络及其路由协议 9 无线自组织网络设备，用于单兵、车载、指挥所等不同的场合。美军的近期数字 电台m 【d r 和无线互联网控制器等通信装备都使用了a dh 0 c 网络技术。 2 ) 传感网络 传感网络是a dh 网络技术应用的另一个领域。传感器的发射功率较小，大 量地理分散的传感器通过a dh o c 网络技术组成网络，可以实现传感器之间以及控 制中心之间的通信。传感网络中，节点不仅能协作转发来实现通信，还可以检测 本地环境的变化，收集和处理相关的传感信息，这种网络具有非常广阔的应用前 景。 3 ) 紧急和突发场合 在发生了地震、洪水、火灾或遭受其他灾难后，固定的通信网络设施很可能 会无法正常工作。而a d 1 0 c 网络能够在这些恶劣和特殊的环境下提供通信支持， 对抢险和救灾工作具有重要意义。此外当警察和消防队员执行任务，而常规网络 无法保障时，可以通过a dh o c 网络来保障通信指挥的顺利进行。 钔偏远野外地区 偏远或野外地区的通信通常无法依赖固定或预设的网络设施进行。a dh o c 网 络具有单独组网能力和自组织性，是这些场合实现通信的最佳选择。 5 ) 临时场合 6 1a dh o c 网络的快速、倚单组网能力使得它使用于临时场合的通信，比如会议、 庆典、展览会等，并可以免去布线和部署网络设备的工作。 们个人通信 a dh 0 c 鼹络可以用于个人域网络来实现p n a 、手机、掌上电脑等个人 通信设备之间的通信，并可以构建虚拟教室和讨论组等崭新的移动对等应用 ( m p 2 p ) 。考虑到电磁波的辐射问题，个人域网络通信设备的无线发射功率应尽量 小，这种情况下a di l 网络的多跳通信特点将再次展现它的独特有时。 8 ) 商业应用 、 使用a dh 0 c 网络技术来组建家庭无线网络、无线数据网络、移动医疗监护系 统和无线设备网络，开展移动和便携式计算等。 外其他应用 a dh 0 c 网络具有很多优良特性，它的应用领域还有很多，这需要我们进一步 去挖掘。比如它可以用来扩展线有蜂窝移动通信系统的通信模式和覆盖范围，实 现地铁和隧道的无线覆盖，实现汽车和飞机等交通工具之间的通信，用于辅助教 学和构建未来的移动无线城域网和自组织广域网等。 2 1 3 a dh o c 网络协议栈 根据a d 1 0 c 网络的特征，参照0 s l 的经典7 层协议棱模型和t ( 驯i p 的体系 1 0 a dh 0 c 网络中基于负载平衡的自适应多径路由协议 结构，可以将a d 1 0 c 网络的协议栈划分为5 层：物理层、链路层、网络层、传输 层、应用层。 物理层：功能包括信道的区分和选择、无线信号的检测、调制解调等。由于 多径传播带来的多径衰落、码问传绕，以及无线传输的空间广播特征带来的节点 间的相互干扰，使得a dl i o c 网络传输链路的带宽容量变低，因此物理层的设计目 标是以相对低的能量消耗，克服无线媒体的传输损伤，获得较大的链路容量。为 达到上述目的，必须采用某些技术，比如调制解调、信道编码、多天线、自适应 功率控制、自适应干扰抵消、自适应速率控制等。 数据链路层：m a c 子层控制移动节点对共享无线信道的访问，它包括两个部 分，一是信道的划分，即如何把频谱划分不同的信道；二是信遒分配，如何把信 道分配给不同的用户。可以采用随机竞争机制( c s m a 、髓e 踟2 1 1 或m a c a ) 、 基于信道划分的接入机制( t d m a 、f i m a 、c d m a 或s d m a ) 、轮转机制( 轮询 或令牌环) 或动态调度机制。在a dh 0 c 网络中，必须克服暴露终端和隐藏终端问 题。逻辑链路控制子层负责向网络提供同一的服务，屏蔽底层不同的m a c 方法。 具体包括数据流的复用、数据帧的检测、分组的转发，确认、优先级排队、差错 控制和流量控制等。 网络层：需要完成邻居发现、分组路由、拥塞控制和网络互联功能。邻居发 现用于收集网络拓扑信息。路由协议的作用是发现和维护去往目的节点的路由， 将网络层分组从源节点发送到目的节点以实现节点之间的通信。路由协议包括单 搔路由和多播路由协议，此外还可以采用虚电路方式来支持实时分组的传输。 传输层：向应用层提供可靠的端到端服务，使上层与通信子网( 下三层的细 节) 相隔离，并根据网络层的特性来高效地利用网络资源，特别是当a dh 0 c 网络 需要接入h t e m e t 等外部网络时尤其需要传输层协议的支持。目前a dh o c 舟络的 传输层还是基于传统有线网络中的传输层协议，包括传输控制协议( t c p ) 和用户 数据报协议( u d p ) 以及适用于无线环境的其他特定的传输层协议。 应用层：提供面向用户的各种应用服务，包括具有严格时延和丢失率限制的 实时应用( 紧急控制信息) 、基于r t p ，r ：h 了的自适应应用( 音频和视频) 和没 有任何服务质量保障的数据报业务，此外还可以采用各种应用层协议和标准，如 w a p ( w i r e l e s sa p p l i c a t i 曲p m t o 1 ) 。 可选功能：包括功率控制机制、分簇算法、信令协议、移动管理和位置定位、 服务发现、地址自动配置和安全策略等。这些可选功能模块在协议栈中的具体的 位置取决于各功能模块的作用以及与上下层协议的关系。例如功率控制机制可以 工作在物理层之上为链路层提供服务；信令协议一般在网络层之上工作为传输层 提供服务：而分簇算法可以工作在链路层之上为网络层提供服务。 此外，为了优化系统性能，应采用跨层的协议栈设计方法考虑到a d1 1 0 c 网 第二章a dh o c 网络及其路由协议 络中的能量极其宝贵，各个层也应采用相应的能量保护机制。需要注意的是该协 议栈是一个通用a dh 0 c 网络协议栈，对于具体的应用场合，该协议栈可以简化， 去掉不必要的功能模块或添加新的模块，并根据系统和应用要求作进步的细化。 2 2 a dh 0 c 网络路由协议的设计要求 1 面临的问题 常规的路由协议主要有两种，一种是基于距离矢量的路由协议，一种是基于 链路状态的路由协议，这两类协议都是针对有线固定网络而设计的，它们的拓扑 结构是固定的，不会出现大的网络结构变化。a dh 0 c 网络中由于节点的任意移动 性导致拓扑结构动态、随机且较快速的变化，这样常规路由在拓扑结构变化时， 就会花很大的代价重新路由，而且协议状态将始终处于不收敛状态，占用大量的 网络资源，致使信息的传输无法实现。 另外，a dh 0 c 网络不能采用常规路由协议主要由于以下几种因素f 1 9 】： a dh 0 c 网络中无线传输设备功率的差异以及无线信道中的大量干扰导致 单向信道的存在。 无线信道的广播特性使得常规路由的网络选路由过程中产生许多冗余链 路。 常规路由的周期性广播路由更新分组会消耗大量的网络带宽。 常规路由协议周期性的路由更新分组会消耗大量的节点能源。此外，某些 常规路由协议需要的复杂计算使得c p u 始终处于很高的负载下，这也同 样消耗了大量的能源，并将对有限的节点能源带来更多的压力。因此需要 适用于a dh 0 c 网络自身的路由协议。 a dh 0 c 网络是一个多跳的移动计算机网络，多跳是研究a dh o c 网络路由协 议的前提基础，路由协议的设计会遇到以下几个问题1 1 9 j ： 网络的自缎性 动态变化的网络拓扑结构 有限的无线传输带宽 无线移动终端的局限性 单向信道的存在 分布式的控制网络 有限的网络安全 生存时间较短 2 对路由协议的要求 a dh 网络路由协议的任务是实现路由。具体主要有以下几个方面：监控网 a dh o c 网络中基于负载平衡的白适应多径路由协议 络拓扑结构的变化；交换路由信息：确定目的节点的位置；产生、维护以及取消 路由；选择路由并转发数据。由于a dh o c 网络具有动态拓扑、有限带宽、终端受 限、存在单向信道等特点，对在其上运行的路由协议提出许多具体而严格的要求。 相对于有线网络，有些要求是a dh 0 c 网络特有的，这些要求主要有1 1 9 j ： 收敛迅速：a dh o c 网络的拓扑结构是动态的，随时处于变化之中，这就 要求路由协议必须对拓扑的变化具有快速反应能力，在计算路由时能够迅 速收敛，及时获得有效的路由，避免出现目的节点不可到达的情况。 提供无环路由：无论在有线网络还是无线网络，提供无环路由是对路由协 议的一项基本要求。但在a dh 0 c 网络中，由于拓扑结构动态变化会导致 大量已有路由信息在短时间内作废，从而更容易产生路由环路因此，在 a d 1 0 c 网络中提供无环路由就显得尤为重要。 避免无穷计算：经典的距离矢量算法在某些链路失效时，有可能出现无穷 计算的情况。在a dh o c 网络中，链路失效是经常发生的事情，这就要求 在a d 脓网络中运行的路由协议必须能够避免无穷计算，不采用会出现 无穷计算的算法。 控制管理开销小：a dh o c 网络中无线传输带宽有限，传送控制管理分组 不可避免的会消耗掉一部分带宽资源。为了更有效的利用宝贵的带宽资 源，需要尽可能的减小控制管理的开销。 对终端性能无过高要求：无线移动终端使用可耗尽能源，c p u 性能、内 存大小、外部存储容量等都低于固定的有线终端，因此，在a dh 0 c 网络 中不能对终端性能要求过高。有线网络中用计算的复杂度来换取路由协议 性能的做法，在a dh o c 网络中并不适用。 支持单向信道：在a dh 0 c 网络中，经常有可能出现单向信道。支持单向 信道，也是对路由协议的要求之一。 尽量简单实用：简单有助于提高可靠性，减少各种开销。在实现路由功能 的前提下力求简单，应是设计a d1 1 0 c 网络路由协议的原则之一。 但目前提出的路由协议都尚未达到以上所有要求。提出一种适应性较强的路 由协议本文研究的一个重点。 3 路由协议的设计 a dh 0 c 网络中节点一方面要运行面向用户的应用程序，另一方面又要运行相 应的路由协议，根据路由策略和路由表完成数据的转发和路由维护的任务。然而， 由于节点的计算能力和存储容量较低，尤其是在电源提供上深受限制，因此要求 路由协议尽量简单实用，这在一定程度上增加了a d h o c 网络路由协议设计的难度。 基于以上因素并考虑到a dh o c 网络拓扑结构动态交化，国内外许多研究人员 第二章a dh o c 网络及其路由协议 从不同角度提出了a d1 1 0 c 网络路由协议，主要有3 种思路【1 9 j ： 第一种思路是通过修改现有的常规路由协议以适应在a dh 0 c 网络环境下 工作，例如d s d v l 4 l 协议就是在r 口( r o u t i n gl n f o 珊a t i p m t o c 0 1 ) 协议 的基础上，通过引入序列号机制解决了距离矢量类型协议固有的路由环路 和计数到无穷的问题( 即收敛时间过长的问题) ；通过采用“时间驱动” 和“事件驱动”机制更新路由信息，尽量减少路由等控制信息对无线信道 的占用，以提高系统效率。 第二种思路是基于按需路由发现的路由原则。按需路由是指节点不再通过 周期性的广播路由信息分组，而是在发现没有去往目的节点的路由的时候 按需发起路由请求。 第三种思路是基于q o s ( q u a l i t vo f s e r v i c c ) 路由。a d h 0 c 网络环境下的 c 1 0 s 路由是指节点收集网络的资源情况，选择一条最有可能满足用户q o s 的路由，而不再仅仅是采用跳数作为路由度量尺度产生的最短路由。 2 3 a dh 0 c 网络中典型的路由协议 在2 2 节已经介绍了路由协议设计的三种基本思想，其中思想一的优点是当节 点需要发送一个去往其他节点的数据分组时，只要路由存在，发送分组的延时就 很小，但也存在着一些比较明显的缺点，比如花费开销大，动态变化的拓扑结构 可能使得花费较高代价得到的路由表中的内容变成无效信息，路由协议始终处于 不收敛状态。思想二的优点是不需要周期性的路由信息广播，节省了一定的网络 资源，缺点是如果发送数据分组时，没有去往目的节点的路由，数据分组需要等 待一定时间的延时。综合考虑，思想二在网络的可扩展性、资源开销等方面具有 一定的优势，如果再在此基础上考虑到路由的q o s ，那么a d h 0 c 网络性能就会有 很大的提升。所以，本文在以下的内容里，只讨论基于按需机制的路由协议。 在前面，我们只介绍了根据发现路由的策略来对路由协议进行分类，而且仅 仅考虑了单一路径，但是，无线连接的不可靠特性和无线节点不停移动导致的网 络拓扑结构的持续变化，使单一路径的a d k i c 网络路由性能一直不能获得太大的 突破。由于多路径所具有的稳定和提高网络资源利用率的特性，它比原来的单一路 径更适合于q o s 路由的要求