（通信与信息系统专业论文）基于带宽探测的ad+hoc多径qos路由协议研究.pdf

摘要 摘要 无线a dh o e 网络以其组网灵活 快捷等特点 在军事 应急等组网通信中具 有广泛的应用前景 广受业界青睐 然而 a dh o e 网络共享无线信道 无线资源 十分有限 如何合理 高效使用紧缺的无线资源 提高网络传输性能 为高层业 务提供0 0 s 保障 一直是人们研究的热点 实时 准确探测网络中当前无线链路 的状况是高效使用无线资源的前提 本文针对这一问题 对现有典型的a dh o c 网 络无线链路带宽探测算法进行了分析 在此基础上提出了一种较为准确的a dh o c 网络无线链路带宽的探测算法 并结合a d h o e 网络多路径策略 提出了一种基于 无线链路带宽探测的a dh o c 多路径q o s 路由协议 具体研究内容如下 1 分析了影响a dh o c 网络无线链路质量的因素 探讨了无线链路带宽的表 示方法 对当前a dh o e 无线链路带宽探测算法做了深入研究 分别从主动探测和 被动探测两种角度 提出了基于捎带传输的p b b e 链路带宽探测算法 以及基于 信道空闲时间的l b e 链路带宽探测算法 通过数学推导和仿真验证了p b b e 算法 和l b e 算法都比基础算法有较大改进 同时 l b e 算法比p b b e 进一步提高了链 路带宽探测的准确性 2 分析了无线a dh o c 网络多路径的特点 以多路径路由协议a o d v m 为基 础 着重比较分析了多路并行使用和备份路由的两种多路径使用策略 通过仿真 分析得出了多路并行使用策略在a dh o c 中没有优势的结论 从而选择实现相对简 单的备份路由方式作为多路径的使用策略 为多径q o s 路由协议的设计奠定基础 3 结合本文提出的无线链路带宽探测算法以及使用备份方式的多路径策略 以a o d v m 为基础进行改进 提出了一种新的基于链路探测的多路径q o s 路由协 议q b a o d v m 并通过仿真分析 验证了q b a o d v m 协议具有良好的q o s 性 能 本文的主要贡献在于提出了两种较准确a dh o e 无线链路带宽探测算法 并将 其中一种算法结合多路径路由协议应用于a dh o c 网络q o s 保障中 保证有带宽需 求业务的q o s 为a dh o c 网络q o s 路由的研究提供了一种思路 并奠定了一定 的研究基础 关键词 a dh o c 网络 链路带宽探测 多路径路由 q o s 路由 a b s t r a c t a bs t r a c t w i r e l e s sa dh o cn e t w o r kh a sab r o a da p p l i c a t i o np r o s p e c ti nt h em i l i t a r ya n d e m e r g e n c yn e t w o r kc o m m u n i c a t i o nb e c a u s eo fi t sf l e x i b l ea n de a s yt oc o n s t r u c t i o n c h a r a c t e r i s t i c h o w e v e r a dh o en e t w o r k su s es h a r e dw i r e l e s sc h a n n e l t h er e s o u r c e s a r el i m i t e d h o wt ou s et h es c a r c ew i r e l e s sr e s o u r c e sm o r ee f f e c t i v e l yt o i m p r o v e n e t w o r kp e r f o r m a n c e a n dh o wt o p r o v i d eq o sf o rl l i 曲 1 e v e ls e r v i c e s h a sb e e na r e s e a r c hh o t s p o t t h ep r e m i s eo fe f f i c i e n tu s eo fw i r e l e s sr e s o u r c e si st oe s t i m a t et h e w i r e l e s sl i n ks t a t u si nt i m ea n d a c c u r a t e l y t h i sp a p e ra n a l y z e dt h ee x i s t i n ga dh o c n e t w o r k sb a n d w i d t he s t i m a t i o na l g o r i t h m p r o p o s e daa c c u r a t ee s t i m a t i o n a l g o r i t h m c o m b i n e dw i t ha dh o cn e t w o r km u l t i p a t h r o u t i n gs t r a t e g y p r o p o s e daw i r e l e s s b a n d w i d t he s t i m a t i o nb a s e da dh o c m u l t i p a t hq o sr o u t i n gp r o t o c 0 1 s p e c i f i cs t u d i e s a r ea sf o l l o w s 1 t h i sp a p e ra n a l y z e dt h ef a c t o rt h a ti m p a c tt h eq u a l i t y o fa dh o cn e t w o r kl i n k a n dt h ep r e s e n t a t i o no fa dh o cn e t w o r kb a n d w i d t h s t u d i e dt h ee x i s t i n ga c t i v ea n d p a s s i v ee s t i m a t i o nm e t h o da sab a s i sf o ri m p r o v e m e n t p r o p o s e dap i g g y b a c kb a s e d p b b eb a n d w i d t he s t i m a t i o na l g o r i t h m t h i sp a p e ra l s op r o p o s e dai d l et i m eb a s e dl b e a l g o r i t h ma si m p r o v e m e n t t h r o u g hm a t h e m a t i c a ld e r i v a t i o na n ds i m u l a t i o np r o v e dt h a t t h i sa l g o r i t h mf u a 仙e ri m p r o v e dt h ee s t i m a t i o na c c u r a c yc o m p a r e dw i t hp b b e 2 a f t e rt h ea n a l y s i so ft h ec h a r a c t e r i s t i c so fa dh o e m u l t i p a t hr o u t i n gp r o t o c o l s t h i sp a p e rf o c u s e do nt h ec o m p a r i n go fp a r a l l e lt r a n s m i ts t r a t e g ya n db a c k u ps t r a t e g y b a s e do na o d v m a n do b t a i n e dt h ec o n c l u s i o nt h a tt h e r ei sn oa d v a n t a g ew i t hp a r a l l e l s t r a t e g yi na dh o cn e t w o r k s t h i sc o n c l u s i o ni st h ef o u n d a t i o nf o rm u l t i p a t hq o s r o u t i n g p r o t o c o ld e s i g n 3 t h i sp a p e ra l s oc o m b i n e dt h ew i r e l e s sl i n kb a n d w i d t he s t i m a t i o na n dt h e b a c k u pm u l t i p a t hr o u t i n gs t r a t e g y p r o p o s e db a n d w i d t he s t i m a t i o nb a s e dm u l t i p a t h q o sr o u t i n gp r o t o c o lq b a o d v mb a s e do na o d v m s i m u l a t i o na n a l y s i sp r o v e dt h a t q b a o d v m h a sg o o dq o s p e r f o r m a n c e t h em a i nc o n t r i b u t i o no ft h i sp a p e ri st op r o p o s et w oa dh o cw i r e l e s sb a n d w i d t h e s t i m a t i o na l g o r i t h m c o m b i n e dw i t hm u l t i p a t hr o u t i n gp r o t o c o la n du s e df o ra dh o c i i a b s t r a c t n e t w o r kq o sg u a r a n t e et oe n s u r et h eb a n d w i d t hr e q u i r e m e n t t h i sp a p e rp r o v i d e da i d e ai na dh o cn e t w o r kq o s r o u t i n g a l s ol a i daf o u n d a t i o no fr e s e a r c h k e y w o r d s a dh o en e t w o r k s l i n kb a n d w i d t he s t i m a t i o n m u l t i p a t hr o u t i n g q o s r o u t i n g l i i 图目录 图目录 图3 1 无线节点之间的距离关系 8 图3 2 隐藏终端 1 0 图3 3 暴露终端 1 1 图3 42 个发送节点向不同的接收节点发送 1 1 图3 5 一种链式拓扑结构 1 2 图3 6 常见的拓扑结构 1 4 图3 7p b b e 算法不准确的场景 1 6 图3 8i e e e 8 0 2 1 1 d c f 1 7 图3 9 空闲时间收集与计算 1 9 图3 1 0p b b e 算法实现模块图 2 0 图3 1 1 收集邻居带宽信息流程图 2 1 图3 1 2l b e 算法实现模块图 2 1 图3 1 3 收集空闲时间算法状态机 2 2 图3 1 4 仿真场景1 2 3 图3 1 5 即时估算的可用带宽1 2 3 图3 1 6 网络丢包随着负载增大的变化情况1 2 4 图3 1 7 仿真场景3 2 4 图3 1 8 即时估算的可用带宽2 2 5 图3 1 9 网络丢包随着发送速率增大的变化情况2 2 5 图3 2 0 带宽探测的开销比较 2 6 图4 1 两种多路径路由 2 9 图4 2e t 随着多路径数量增多的变化趋势 3 0 图4 3 相干度因子为0 的两条路径 3 1 图4 4 备份模式的两条路径 3 2 图4 5r r e q 表 3 4 图4 6 路由表结构 3 5 图4 7a o d v m 协议实现模块图 3 7 图4 8 相干度为2 的两条路径 3 9 v 图目录 图4 9 网络瞬时吞吐量的变化情况 3 9 图4 1 0 相干度为o 的两条路径 4 0 图4 1 1 相干度o 的瞬时吞吐量变化情况 4 0 图4 1 2 移动性场景 4 1 图4 1 3 备份模式对网络性能的影响 4 1 图4 1 4 路由开销对比 4 2 图5 1 单跳拓扑 4 6 图5 2 多跳拓扑 4 6 图5 3 多跳拓扑2 4 7 图5 4e h p c c 算法举例 4 9 图5 5 主 次路径计算c c c c d 值举例 5 3 图5 6 主路径切换 5 4 图5 7q b a o d v m 协议实现模块图 5 6 图5 8 节点r r e q 和r r e p 接收流程 5 6 图5 9 仿真场景1 5 7 图5 1 0 节点1 和节点4 的可用带宽变化情况 5 8 图5 113 条数据流的静态拓扑 5 9 图5 1 2 网络总吞吐量的变化情况 6 0 图5 1 3a o d v 协议c b r l 和c b r 2 的吞吐量情况 6 0 图5 1 4q b a o d v m 协议c b r l 和c b r 2 的吞吐量情况 6 1 图5 1 5 动态仿真场景 6 2 图5 1 6 节点3 平均吞吐量随时间的变化情况 6 2 图5 1 7 网络丢包随负载增大的变化情况 6 3 图5 1 8 路由开销比较 6 4 图5 1 9 时延保证仿真场景 6 5 图5 2 0 带宽保证的时延情况 6 5 图5 2 1 时延保证的时延情况 6 6 v i i i 表目录 表目录 表3 1n s 2 主要仿真参数设定 2 2 表4 1r r e q 报文格式 3 4 表4 2r r e p 报文格式 3 5 表4 3n s 2 主要仿真参数设定 3 8 表5 1r r e q 报文格式 5 0 表5 2r r e p 报文格式 5 0 表5 3n s 2 主要仿真参数设定 5 7 i x 缩略语 m a c a o d v q o s p b b e l b e b a o d v m r r e q r r e p r r e r r d e r r c o m e h p c c 缩略语 m e d i aa c c e s sc o n t r o l a d h o co n d e m a n dd i s t a n c ev e c t o r q u a l i t yo fs e r v i c e p i g g y b a c kb a s e db a n d w i d t he s t i m a t i o n l i s t e nb a n d w i d t he s t i m a t i o n b a c k u pb a s e da d h o co n d e m a n d d i s t a n c ev e c t o rm u l t i p a t h r o u t er e q u e s t r o u t er e p l y r o u t ee r r o r r o u t ed i s c o v e r ye r r o r r o u t ec o m f o r i l l e n h a n c e dh i g hp o w e rc o n t e n dc o u n t x 介质访问控制 按需的自组网距离矢量路由协 议 服务质量 基于捎带的带宽探测 基于侦听的带宽探测 基于备份的自组网按需距离矢 量多路径路由协议 路由请求报文 路由应答报文 路由出错报文 路由寻找出错报文 路由确认报文 增强的高功率冲突值计算算法 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作 及取得的研究成果 据我所知 除了文中特别加以标注和致谢的地方 外 论文中不包含其他人已经发表或撰写过的研究成果 也不包含为 获得电子科技大学或其它教育机构的学位或证书而使用过的材料 与 我一同工作的同志对本研究所做的任何贡献均己在论文中作了明确的 说明并表示谢意 签名 虚翌日期 劢哆年j 月彦日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留 使用学位论文 的规定 有权保留并向国家有关部门或机构送交论文的复印件和磁盘 允许论文被查阅和借阅 本人授权电子科技大学可以将学位论文的全 部或部分内容编入有关数据库进行检索 可以采用影印 缩印或扫描 等复制手段保存 汇编学位论文 保密的学位论文在解密后应遵守此规定 签名 虚盐 导师签名 建童螽 眺砷铘帅 第一章引言 1 1研究背景 第一章引言弟一早与i西 无线a dh o c 网络又称为自组织网络 是一组带有无线收发器的移动网络节点 组成的一个多跳的临时性的自治系统 这些移动节点包括计算机 便携式笔记本 嵌入式系统 个人数字助理 p d a 等 无线a dh o c 网络由于其自由 灵活 方 便等特点 在军事 应急等组网通信中具有广泛的应用前景 广受业界青睐 a dh o c 网络为一种无线分布式移动多跳网络 与其它通信网络相比 a dh o c 网络主要有以下特点 多跳性 由于a dh o e 网络中没有基础设施的支持 节点间的通信往往需 要其他节点的中继转发来实现 网络拓扑的动态性 a dh o e 网络中的节点可以较随意的移动 节点间通 过无线信道形成的网络拓扑结构可能随时发生变化 并且这种变化是难以 预测的 无线信道的广播性 a dh o e 网络的无线信道是多跳共享的多点信道 即 一个节点发送信息 邻居节点都可以收到 无中心和自组织性 a dh o c 网络中所有节点地位平等 各节点通过网络 协议和分布式算法调节彼此的行为 由于a dh o e 网络采用无线传输技术作为基本通信手段 与有线传输相比 面 临很多的困难 无线传输信号损伤很大 传输环境的变化起伏不定 无线频谱资 源宝贵 传输带宽狭窄等 源于对不受约束的固执追求 人们 直在努力 试图 最大化的利用网络资源 发掘a dh o c 网络的潜力 其中包含许多关键的技术问题 如m a c 协议 2 1 路由问题 网络安全 q o s 保证以及功率控制与管理等 1 2研究内容与目标 本文以提供带宽q o s 保证作为切入点 重点研究以下几个问题 1 分析影响a dh o e 网络无线链路质量的因素 探讨无线链路带宽的表示方 电子科技大学硕士学位论文 法 对当前a dh o c 无线链路带宽探测算法做了深入研究 分别从主动探测和被动 探测两种角度 提出基于捎带传输的p b b e 链路带宽探测算法 以及基于信道空 闲时间的l b e 链路带宽探测算法 包括理论分析以及仿真模块的实现与验证 希 望p b b e 算法和l b e 算法都比基础算法有较大改进 2 分析无线a dh o c 网络多路径路由的特点 以多路径路由协议a o d v m 为 基础 着重比较分析多路并行使用和备份路由的两种多路径使用策略 通过仿真 模块的实现与验证 分析得出多路并行使用策略在a dh o c 中没有优势的结论 从 而选择实现相对简单的备份路由方式作为多路径的使用策略 希望为多径q o s 路 由协议的设计奠定基础 3 结合本文提出的无线链路带宽探测算法以及使用备份方式的多路径策略 以a o d v m 为基础进行改进 提出一种新的基于链路探测的多路径q o s 路由协议 q b a o d v m 并通过仿真模块的实现与验证分析 验证q b a o d v m 协议的q o s 性能 希望其在带宽0 0 s 业务的保证上有良好的性能 1 3论文章节安排 论文后续章节内容安排如下 第二章对a dh o c 网络的路由协议进行介绍 对当前国内外的a dh o c 网络的 q o s 保证问题 链路带宽探测问题 多路径路由问题的研究现状作了简单的介绍 第三章分析了无线共享信道的特点以及物理层与之相关的因素 在当前的主 动探测和被动探测两种思路的基础上 提出了两种无线链路探测算法 并分别作 了理论分析以及仿真验证 第四章分析了a dh o c 网络多路径路由寻路以及使用模式的相关问题 分析 了a o d v m 多路径路由协议 通过理论分析以及仿真验证 证明a dh o c 网络中并 行传输模式没有优势 从而选择实现相对简单的备份路由方式作为多路径的使用 策略 第五章结合第三章的链路带宽探测算法以及第四章的多路径路由算法 从 单路径q o s 协议受网络动态拓扑的影响入手 提出了一种基于带宽探测的多径q o s 路由协议 并作了仿真验证 第六章总结论文的工作并指出需要进一步研究的方向 2 第二章研究基础与现状 第二章研究基础与现状 本章重点介绍a dh o c 网络路由协议的基础概念 以及当前国内外对其q o s 保证问题 链路带宽探测问题 多路径路由问题的研究现状 为论文的后续章节 做好铺垫 2 1a dh o c 网络路由协议简介 路由协议是无线a dh o c 网络研究热点之一 由于a dh o c 网络中没有像有线 网络的路由器那样的专门的路由设备 并且没有如基站等基础设施的支持 网络 中的每一个节点都必须承担路由的功能 节点既是主机 又是路由器 由于无线 信号的限制 无线网络的通信距离一般较小 当节点与自己通信覆盖范围外的节 点通信时 必须借助多个中间节点来转发 因此 路由协议是实现多跳路由的关 键 a dh o c 网络的路由协议可以分为表驱动 t a b l e d r i v e n 路由协议 按需 o n d e m a n d 路由协议和混合式 h y b r i d 路由协议三类 首先是表驱动路由协议 当使用这类路由协议时 网络中的每个节点都需要 主动维护路由表 该路由表可以准确的反映到其他节点的路由信息 路由表的维 护一般时通过路由信息的定时交互完成的 当源节点要发送数据时 查找路由表 可以立即获得到达目的节点的路径 因此其时延较小 但是 维护每个节点的路 由表需要大量的控制报文 并且控制报文必须定期发送以保证路由信息的及时性 协议的开销较大 典型的表驱动路由协议是d s d v l 3 j 其次是按需路由协议 在这类路由协议中 不需要网络中的每个节点主动维 护路由表 而是采用一种 按需 的维护方式 即当源节点需要知道某个目的节 点的路由时 才发起路由请求过程来寻找路径 由于路由查找是临时的 因此其 端到端时延相比表驱动路由协议来说较大 但由于其不需要定期维护全网的路由 信息 协议的开销大大减少 典型的按需路由协议有a o d v t 4 d s r i s 等 最后是混合式路由协议 该协议结合了表驱动协议时延小的优点以及按需路 由开销小的优点 设定一个局部范围 如2 跳内 节点定期维护该范围内的邻居 节点的路由信息 若数据报文的目的地址是该范围内的某一个邻居 源节点可直 接将报文传递 减少了端到端时延 并且也限制了路由信息的交互 当目的节点 电子科技大学硕士学位论文 在该范围外时 再采用按需路由的方式临时进行路由查找 因此 混合式路由协 议即减少了路由开销 又改善了时延特性 典型的协议是z r p t 6 1 2 2a dh o c 网络q o s 研究现状 在a dh o c 网络发展的初期 人们主要将其用于传输数据信息 因此即使a d h o c 网络资源较为匮乏 仍能满足人们的需求 提供尽力而为的保障 随着网络应用 的不断发展以及a dh o c 网络便利性的逐步体现 人们试图将其应用在更多的场合 比如传输语音 视频等多媒体信息 这类信息往往对网络的带宽 时延等有较高 的要求 如何合理 有效地利用a d h o e 较为匮乏的网络资源 以获得更好的传输 性能 进而为多媒体业务的服务质量提供保障 就成为了一个十分突出的问题 而a dh o c 网络q o s 支持的研究正是试图解决这一问题 由于a d h o e 网络的特点 实现q o s 相比有线网络具有更大的难度 主要包括 以下几个方面 1 1 由于a dh o e 网络的动态性 网络拓扑结构可能频繁的变化 2 无线信道带宽较窄 负载较重时保证带宽需求难度较大 3 无线节点共享信道 邻居节点的传输状况同样会影响到本节点的传输质 量 当前对a dh o c 网络q o s 的研究主要有以下两种策略 1 q o s 路由 即根据应用的q o s 需求 在当前的网络中寻找并建立一条满 足q o s 参数 如带宽 延迟等 的传输路径 从而提高网络的传输性能 q o s 路由策略从现有的路由协议出发加以扩展 易于实现 是当前q o s 研究的热点 目前国内外研究者已经提出一些q o s 路由协议 但这些协 议往往都只是单路径的 并且在区分业务方面考虑不多 2 q o s 信令 该策略借鉴目前i n t e m e t 上支持q o s 的方法 根据a dh o c 网 络的特点加以适当改造 这种研究策略与具体的路由协议无关 是从一个 系统的层面来研究支持q o s 的机制 由于q o s 信令要考虑整个q o s 机制 的建立以及可扩展性 维护性 在资源受限的a dh o c 网络中实现较为复 杂 本文主要从q o s 路由的策略出发 来研究a dh o c 网络的q o s 由于当前a d h o c 网络常用的路由协议大多以跳数作为路由的度量依据 可以保证源节点与目的 4 第二章研究基础与现状 节点之间的路径最短 时延最短 然而 最短的路径不一定保证带宽能满足应用 的需求 而且网络中的一些关键路径往往由于同时被很多条路由同时使用 造成 可用带宽降低 满足不了应用的需求 并且会由于节点的拥塞造成时延的增加 当前对于a dh o c 网络q o s 路由协议的研究根据其基础协议的不同大致可分为 单径和多径两类 其中 典型的单径q o s 路由协议有a q o r 7 1 c e d a r t 8 等 a q o r 是基于带宽保证的q o s 路由协议 在按需路由协议的基础上增加了q o s 寻路 资 源预留等机制 其缺点在于带宽探测 路由接入的不准确 以及无法应对网络的 动态性 c e d a r 采用核心节点作为基础设施来进行路由计算 其缺点在于核心节 点的维护较为复杂 且核心节点的任务较重 多径q o s 路由协议由于其复杂性 当前研究较少 典型的有q o s m s r 协议 等 q o s m s r 协议使用m s r 协议的路由发现机制来搜集q o s 信息 并采用多带 宽分裂预留的方式将带宽需求分裂成多个多条路径上的小的带宽需求 其缺点在 于采用源路由机制 带来较大的路由开销 以及采用多路径传输的相关问题 2 3链路带宽探测算法研究现状 a dh o c 网络通常共享信道资源 如何高效利用紧缺的无线链路资源 一直是 人们研究的热点 而实时 准确的掌握无线链路状态是前提 目前人们对于链路 带宽探测算法的研究 主要是基于i e e e 8 0 2 1 1 的无线链路 其思想大致可分为二 个方面 一种是主动式 一种是被动式 主动式主要是节点主动发出探测报文 并通过节点间的交互计算可用带宽 而被动式是节点本地查看自己的可用带宽情 况 不需要节点间的交互 文献 7 1 0 出了一种主动式的算法 算法的主要思想是各个节点通过h e l l o 报文通告自己以及邻居节点的使用带宽信息 使各个节点得到自己2 跳范围内邻 居节点的带宽情况 分布式地计算出自己的可用带宽 这种算法的主要问题在于 邻居信息的准确性以及定期探测带来的额外开销 一种比较热门的被动式算法由文献 1 1 1 2 1 1 3 所述 其基本思想是根据 i e e e 8 0 2 1 l 的d c f 特性 节点通过本地查看一段时间内的空闲时间来估算可用带 宽 该算法采用节点本地监控 不必与其它节点交互 同时利用8 0 2 1 1 的n a v 考 虑了相邻节点的干扰问题 这种算法的主要问题在于如何将空闲时间同节点的可 用带宽联系起来 5 电子科技大学硕士学位论文 2 4多路径路由协议研究现状 多径路由是指当源节点向目的节点发送数据时 可采用多条路径来进行传输 a d h o e 网络中的带宽等资源相对匮乏 当使用单径路由协议时 目的节点相同的 数据包全部都在一条路径上发送 当某条链路拥塞或者断开时 通过该链路发送 的所有数据就都必须重新由新的路径发送 造成了网络的不稳定 同时也增加了 时延 随着网络性能的提高 单径协议也无法满足路由可靠性和q o s 等方面的要 求 多径路由相比单径路由 其优势主要有以下几点 可靠性 由于a dh o c 网络的动态性 网络中的节点可以任意移动 因此网络拓扑结构 可能会经常发生变化 而网络中链路断开等情况也会经常发生 如果能建立一条 或多条备份路径 当链路出错时立刻使用备份路径 提高网络的可靠性和容错性 带宽利用 由于a dh o c 网络带宽较窄 若使用多条相对独立的路径同时传输 那么传输 的实际带宽就等于各条路径的带宽总和 各条路径相互协同 并行传输 提高网 络资源的利用率 负载均衡 在多路径路由协议中 数据报文可以按一定比例分配到多条路径中 避免了 单径路由协议将数据报文的转发全部放在一条路径上导致路径上的节点过载而拥 塞 实现负载均衡 目前的多路路由一般都是在单路路由协议的基础上进行扩展 大致可分为两 类 基于d s r 和基于a o d v 由于d s r 寻找路径的先天优势 基于d s r 的多路 径扩展比较多 如m s r 14 1 s m r t l5 1 a o m r 1 6 等 m s r m u l t i p a t hs o u r c er o u t i n ga l g o r i t h m 是一种基于d s r 扩展的多路径路 由协议 它采用与d s r 相同的路由发现过程 使用源路由的方式找到多条路径 m s r 按照一定得权重将负载分配到多条路径上 其目的是使减少网络的平均时延 其局限在于它是按照多条路径完全独立的前提来进行负载分配 然而它通过路由 发现找到的多条路径并不一定是完全独立的 s m r s p l i tm u l t i p a t hr o u t i n g 协议改进了m s r 的这一局限 试图在路由发 现时找到最大程度不相交的路径 其缺点在于由目的节点来决定使用哪些路径 6 第二章研究基础与现状 因此对于源节点来说控制权较低 a o m r a dh o co n d e m a n dm u l t i p a t hr o u t i n g 也是d s r 协议的一个扩展 协议的主要思想是采用备份路由的策略 在源节点和中间节点之间提供多条备份 路径 且备份路径同主路径是独立的 当主路径由于断路或其他原因失效时 源 节点立即使用备份路径来继续传输 基于a o d v 的多路径扩展 相关文献比较少 只有a o m d v 1 7 1 和a o d v m t l 8 等 a o m d v a dh o co n d e m a n dm u l t i p a t hd i s t a n c ev e c t o r 协议的目的是在路 径发现过程中找到多条无环的链路不相交路径 而a o d v m a dh o co n d e m a n d d i s t a n c ev e c t o rm u l t i p a t h 协议以使用r r e q 表取代a o d v 中的先驱表为主要思 想 其优点在于尽可能地利用一次路由请求过程找到多条路径 并且路径之间是 节点不相关的 2 5本章小结 本章主要介绍了a dh o c 网络的基本概念 以及当前国内外学者对a dh o c 网 络q o s 保证 链路带宽探测算法以及多路径路由协议的研究现状 为论文后面的 章节作好铺垫 打下基础 7 电子科技大学硕士学位论文 第三章无线链路带宽探测算法研究 高效使用网络资源对于a dh o e 网络q o s 保证非常重要 而高效使用资源的前 提 在于链路状态的准确探测 带宽是链路状态的重要反映之一 本章主要研究 无线链路带宽探测算法 由于带宽探测的准确性同物理层密切相关 因此本章首 先分析了无线共享信道的特点以及物理层与之相关的影响因素 并结合当前已有 的探测算法 分别从主动探测和被动探测两种思路 提出了基于捎带传输的p b b e 链路带宽探测算法 以及基于信道空闲时间的l b e 链路带宽探测算法 为基于带 宽的q o s 保证打下基础 3 1 无线共享信道物理层分析 由于节点的无线信道带宽同物理层紧密相关 因此本文先对无线共享信道的 特点以及物理层与之相关的影响因素进行分析 分析的前提条件为 所有节点的 传输特性都一致 节点是半双工的 天线为全向天线 3 1 1无线共享信道干扰距离分析 一 一 二 二 一 图3 1 无线节点之间的距离关系 a dh o e 网络的无线信道主要具有以下两个特点 共享性 节点发出的无线信号 周围的节点都能接收到 因此在一定 8 第三章无线链路带宽探测算法研究 范围内若同时有两个节点发送数据 数据包就会产生冲突 衰减性 无线信号会随着节点间距离的增大而逐渐衰减 为了深入分析这些特点对信号传输造成的影响 本文做了如下的数学模型分 析 如图3 1 所示 其中 a b c 分别是三个网络节点 每个节点都由一些距 离参数来表示它们的无线传输特性 1 9 分别是 1 传输距离 t r a n s m i s s i o nr a n g e r 节点可以正常收发数据的最大距离 这个 距离是由节点的传输功率以及电磁波的传播特性决定的 以r 为半径作出的 圆表示了节点的传输范围 如图3 1 中的实线圈 2 载波侦听距离 c a r r i e rs e n s i n gr a n g e r s 节点进行物理载波侦听能检测到的 最大距离 根据i e e e 8 0 2 1 1 协议 节点只有在侦听到信道为空闲状态时才能 够发送数据 这个距离可以通过设置接收机的载波侦听灵敏度来调节 图3 一l 中的虚线圈表示了节点的载波侦听范围 3 干扰距离 i n t e r f e r e n c er a n g e r i 节点传输能被其他节点干扰的最大距离 假设图3 1 中节点c 处于b 的干扰范围内 当节点b 正在接收a 传来的数据 时 若节点c 也在进行传输 节点b 就不能正确接收a 的数据 一般来说 这三个距离之间的关系是i kr i r s 在物理层 主要是通过接收 机收到的信号强度 以及接收机的接收阈值来体现这三个距离 其中 p r 为接收 机收到的信号强度 c s t h r e s h 为载波侦听信号阈值 c p t h r e s h 为接收信号阈值 1 若p r c s t h r e s h 则无线物理层将这个信号作为噪声而丢弃 因此 m a c 层不能检测到这个载波 或者说 对于m a c 层而言 这个信号是不存在 的 2 若c s t h r e s h p r c p t h r e s h 则物理层直接将该信号上传给m a c 层 此时 m a c 层可以对该信号进行正确地接收并进行相应地处理 接收机收到的信号强度p r 取决于发送功率以及信号的衰减状况 为了方便计 算 本文的衰减模型选取了t w o r a yg r o u n d 该模型考虑了路径长度对信号的衰减 以及地面反射的影响 适合户外 开阔的地形 在该模型中 信号的衰减与节点 间的距离相关 有如下公式 9 电子科技大学硕士学位论文 cg f g 鱼莩公式 3 1 其中 p 是发送功率 p 是接收功率 g f 和g 分别是发射机和接收机天线增 益 魄和h 分别是发射机和接收机的天线高度 d 是发送节点和接收节点之间的 距离 要使信号能够正确地被接收而不受噪声干扰 必须保证接收机处的信噪比大 于接收阈值 即 p 1 冬 二j 皇 c p t h 坨s h 公式 3 2 只p 上 一 1d 一 对于一般的接收机来说 c p t h r e s h 为1 0 d b 可以得到 d 1 7 7 8 d 公式 3 3 即节点的干扰距离应为发送 接收节点间距离的1 7 7 8 倍 这是因为干扰所需 的信号强度要比正确接收所需的信号强度小 3 1 2 载波侦听范围的取值分析 由于载波侦听范围的取值受隐藏终端 暴露终端以及网络空间复用的影响 因此本文从以下三个方面来分析 1 隐藏终端问题 隐藏终端是指在接收节点覆盖范围内而在发送节点覆盖范围外的节点 不同 的发送节点有可能向同一接收节点发送信息 造成冲突 如图3 2 中 节点a 正 向节点b 发送数据 节点c 也要向节点b 发送数据 c 发送前要监听信道状态 由于c 在a 的有效范围覆盖之外 因此 c 监听到信道为空闲 开始向b 发送数 据 这样节点a 和c 发送的数据在b 处发生碰撞 导致传输失败 此时 c 被称 为隐藏终端 图3 2 隐藏终端 1 0 第三章无线链路带宽探测算法研究 2 暴露终端问题 暴露终端是指在发送节点覆盖范围之内 而在接收节点覆盖范围之外的节点 该节点因听到发送节点的发送而延迟发送报文 但因它在接收节点通信范围之外 它的发送实际上并不会冲突 引入了不必要的延迟o 如图3 3 中 节点b 正向节 点a 发送数据 此时 节点c 也要向节点d 发送数据 c 先监听信道 听到b 正 发送数据 c 判断信道忙 延迟发送 但实际上c 向d 的发送并不会影响b 向a 发送 因此这种情况降低了信道利用率 图3 3 暴露终端 根据3 1 1 节对于干扰距离的分析 要使网络中同时有2 个发送节点向不同的 接收节点发送数据 节点之间必须隔开一定的距离来避免冲突 当两个发送节点 之间的距离大于d 足时 可以保证在所有可能的网络场景下 两个发送节点在不 同的接收节点不会发生冲突 由于接收节点在发送a c k 时不会进行载波侦听 因 此 要保证完全没有冲突 接收节点之间的距离也必须要大于r 在这种情况下 要保证同时传输而不发生冲突 发送节点之间的距离应该大于2 d r t 如图3 4 所示 7 一一 一 7 一 图3 42 个发送节点向不同的接收节点发送 电子科技大学硕士学位论文 在i e e e 8 0 2 1 1 协议中 并没有明确指出载波侦听距离的取值 在很多网络仿 真软件如n s 2 中 载波侦听距离是节点最大传输距离的2 2 倍 物理载波侦听范 围其实是可以通过修改载波侦听信号阈值来改变的 修改这个值的大小可以很明 显的影响到节点的网络性能 3 空间复用问题 当物理载波侦听范围设定得足够大时 如上面提到的2 d 足 可以完全解决 节点间的冲突问题 然而 载波侦听范围并不是设置得越大越好 因为这里又牵 涉到信道的空间复用 s p a t i a lr e u s e 的问题 由于无线信道的共享性 一定范围 内的节点是不同同时占用信道发送数据的 节点的物理载波侦听范围增大 该范 围也会随之增大而导致信道的空间复用度太低 如图3 5 所示 a 卜 呻 b 一 一 c b 一 d h 一 图3 5 一种链式拓扑结构 在这种多跳拓扑下 假设节点间距离为最大传输距离 有2 条数据流 分别 是从节点1 到2 以及从3 到4 若节点1 的载波侦听距离为传输距离的2 2 倍 节 点1 和节点3 是无法同时传输的 因为节点1 会侦听到3 的传输而退避 这一点 对于多路径路由算法是很重要的 因为如果多路径在协同传输时相互干扰 会对 性能产生很大的影响 因此 为了使多路径协同传输达到最大的效果 m a c 层空 间复用度应该做到越大越好 这又要求节点的物理载波侦听距离尽量小 因此 无线节点物理载波侦听距离的选取 是一个值得研究的问题 必须根 据网络的需求来进行折中 3 2p b b e 算法设计 3 2 1基本思想 本文的研究是以文献 7 和文献 1 0 提出的主动式的探测思路为基础 算法的主 要思想是各个节点通过h e l l o 报文通告自己以及邻居节点的使用带宽信息 使各 1 2 第三章无线链路带宽探测算法研究 个节点得到自己2 跳范围内邻居节点的带宽情况 分布式地计算出自己的可用带 宽 这种算法能够较为准确的估算可用带宽 当网络状态发生变化时能够较为实 时的反应变化 但是 其中有如下问题值得讨论 带宽表示 在具体实现中 总带宽可以用信道的最大传输速率来表示 而节点的使用带 宽用什么来表示 文献 7 并没有明确说明 而文献 1 0 单纯通过节点的发送速率来 表示使用带宽 是不准确的 探测开销 由于文献 1 0 采用的是主动式的估算机制 定时发送的h e l l o 报文与网络变 化后触发更新发送的h e l l o 报文增加很多网络负担 特别是在网络负荷较重以及 网络变化较快的时候 相对于被动式的估算机制 探测开销会很大 直接影响a d h o c 网络数据传输的效率 针对上述问题 本文借鉴了文献 1 0 中算法的部分思想 提出了一种主动式的 链路带宽探测算法p b b e p i g g y b a c kb a s e db a n d w i d t he s t i m a t i o n p b b e 算法的前 提同b e q r 一样 节点物理载波侦听范围为默认值 节点最大传输距离的2 2 倍 p b b e 算法的主要思想是各个节点查看自己本地的发送速率 并周期 1 秒 更新 自己的 使用带宽寄存器 通过h e l l o 报文广播自己的带宽占用情况 各个节 点维护自己2 跳内的邻居表 通过原始带宽减去所有2 跳邻居的使用带宽来估算 可用带宽 p b b e 算法的前提条件基本与文献 1 0 相同 即 无线信道采用半双工方式 所有节点都具有相同的传输半径和数据率 无线网络必须满足组合稳定性 c o m b i n a t o r i a ls t a b i l i t y t l o l 所谓组合稳定性 是指在给定时间段内 拓扑变化发生 的频率不能太高 必须能够使拓扑变化信息传遍整个网络 3 2 2 具体实现与分析 p b b e 算法主要涉及链路带宽的表示 链路带宽信息的收集 信息的交互以及 各节点对可用带宽的计算 由于无线网络的动态性 节点的链路状态信息随时可 能改变 带宽信息必须及时更新 再加上a dh o c 网络的无中心特