无线Ad Hoc网络路由算法研究

论文摘要

随着Internet技术的飞速发展，网络技术日新月异，有线网络已不能满足人们对随时随地自由通信的需求，从而这也促进了无线网络技术的发展。无线Ad Hoc网络就是一种新型的无线网络。它是在没有任何基础设施的情况下由无线节点组建而成的网络，节点间通过无线接口传递数据，网络中的节点既是网络的终端也是路由器。与其他无线网络不同的是，Ad Hoc网络具有不依赖固定基础设施的通信、自组织、自管理等特点。路由算法是Ad Hoc网络的重要组成部分，是建立Ad Hoc网络的首要问题。然而，与传统网络相比，Ad Hoc网络路由算法的研发更具挑战性，因此成为一直以来研究的热点。如今虽然有一些初步的研究成果，但是还没有完善的解决方案，这就为Ad Hoc网络技术的深入研究留下了非常广阔的空间。Ad Hoc网络中的节点既可以是静止也可以是移动的，静止的无线传感器网络（WSN）和移动的车载自组织网络（VANET）就是其典型的代表，也是当今研究的热点。本文在对无线Ad Hoc网络中的传感器网络和车载网络进行了系统、全面地分析和总结的基础上，深入细致地研究了传感器网络中的能量洞问题和车载网络中拓扑结构变化频繁等特点对路由算法的影响，取得了若干创新和成果。本文的主要贡献包括：1．针对节点传输距离可调的传感器网络的特点，改进现有的模型，提出了分级的环模型分析这种网络中的能量洞问题。在这种模型里，节点的传输距离被分成了若干等级，同一环内的节点的传输距离是相同的，而不同环的节点的传输距离可以不相同。将所有环的传输距离组成一组传输距离序列，网络中的节点基于传输距离序列路由传递数据。本文证明了这种传输距离序列是影响网络寿命的本质因素，并证明了搜索最优传输距离序列的问题是多目标优化问题，也是NP难问题。2．为不同的节点分布情况提出搜索近似最优的传输距离序列的三种算法。提出了一种集中式的贪婪算法—CETT，根据能量洞的特点从内环向外环逐步搜索近似最优的序列。在均匀节点分布的情况下，CETT在节点部署前根据部署信息（例如区域范围、节点密度等等）计算传输距离序列。在非均匀节点分布的情况下，提出了一种分布式的优化算法—DETL，在节点部署后优化从CETT算法获得的传输距离序列，算法中为了能够尽可能平衡各环的能量消耗，各环自适应地调整它们发送和接收数据的策略。仿真实验证明这两种算法有效的延长了网络寿命，而且在降低了搜索复杂度的同时其性能也接近最优解。还提出了一种基于蚁群优化搜索近似最优传输距离序列的算法—AASTRL，不同区域的节点根据当前的节点分布情况，自适应地调节其数据传输距离，从而延长网络寿命。这种算法不仅适合于均匀节点分布的情况，而且适合于非均匀节点分布的网络。仿真实验显示AASTRL与现有算法相比，有效地延长了网络寿命，并接近理想最优解。3．分析了车载网络路由问题的特点，在对现有路由算法分类的基础上，总结出一种宏-微模型（Macro-Micro Model），分别从宏观和微观的角度分析了VANET的路由问题。这种模型既能够分析现有的路由算法，又能够帮助设计适合VANET的路由算法。在宏-微模型中，宏观层（Macro）拥有稳定的状态能够为创建路由提供依据，微观层（Micro）则是保证各路段数据的传递。4．基于宏-微模型，在宏观层的信息收集和扩散协议方面提出了基于网络延时估计的算法（DRDE和E-DRDE），与现有的方法相比，获得的信息更加准确可靠，而且能够有效避免网络拥塞，信息评估采用加权平均结合递归的方式，既能够保证评估的有效性又能减少节点存储的代价。在宏-微模型微观层的数据传递协议方面，本文首先提出了一种简单的基于位置的贪婪协议—DEAGF，保证数据沿期望路由路径传递。为了提高数据在路口处传递的性能，又提出了一种沿路由路径流行性传递的协议—RAEP，结合TTL（time-to-live）方式，将资源利用集中在最有价值的路段上，既保证了数据传递的高效性（特别是在路口处），又减少了冗余数据对资源的浪费。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 研究背景
• 1.2 无线传感器网络
• 1.2.1 无线传感器网络体系结构
• 1.2.2 无线传感器网络应用
• 1.2.3 无线传感器网络的特点
• 1.2.4 无线传感器网络中的能量洞问题
• 1.3 无线传感器网络研究现状
• 1.3.1 无线传感器网络的路由
• 1.3.2 无线传感器网络的能量问题
• 1.4 车载自组织网络
• 1.4.1 车载自组织网络应用
• 1.4.2 车载自组织网络特点
• 1.4.3 车载自组织网络中的路由问题
• 1.5 车载自组织网络研究现状
• 1.5.1 车载自组织网络中的路由算法
• 1.5.2 移动模型
• 1.5.3 车载自组织网络中的数据收集和扩散协议
• 1.6 当前研究存在的问题
• 1.7 本文的主要内容和贡献
• 1.8 本文结构
• 第二章 无线传感器网络能量洞问题的分析研究
• 2.1 引言
• 2.2 网络模型与问题分析
• 2.2.1 基本假设
• 2.2.2 能量模型
• 2.2.3 分级环模型
• 2.2.4 问题分析
• 2.3 传输生成树
• 2.4 搜索高能效传输树的集中式算法 CETT
• 2.5 搜索高能效传输距离序列的分布式算法 DETL
• 2.6 节点部署
• 2.7 算法性能评估（仿真）
• 2.7.1 仿真环境
• 2.7.2 与其他算法比较
• 2.7.3 算法在不同参数下的网络寿命
• 2.8 小结
• 第三章 基于蚁群优化解决传感器网络中的能量洞问题
• 3.1 引言
• 3.2 搜索传输距离序列的算法
• 3.3 构建图
• 3.4 基于蚁群优化的算法搜索传输距离序列AASTRL
• 3.5 算法性能评估（仿真）
• 3.5.1 仿真环境
• 3.5.2 边概率变化
• 3.5.3 与其他算法比较
• 3.5.4 算法参数对性能的影响
• 3.6 小结
• 第四章 基于分布式实时信息的车载自组织网络路由协议
• 4.1 引言
• 4.2 宏-微模型
• 4.2.1 假设
• 4.2.2 车载网络中的路由问题
• 4.2.3 宏-微模型
• 4.2.4 基于宏-微分析现有的协议
• 4.3 分布式实时延时估计 DRDE
• 4.3.1 获取延时记录
• 4.3.2 扩散延时记录
• 4.3.3 更新估计延时
• 4.4 基于延时估计的贪婪转发协议DEAGF
• 4.4.1 直路模式
• 4.4.2 路口模式
• 4.4.3 路由错误恢复策略
• 4.5 算法性能评估（仿真）
• 4.5.1 实时性
• 4.5.2 资源不受限制
• 4.5.3 资源受限制
• 4.5.4 数据包大小的影响
• 4.5.5 缓冲容量的影响
• 4.6 小结
• 第五章 路段受限的流行性车载自组织网络路由协议
• 5.1 引言
• 5.2 流行性扩散的分布式实时延时估计 E-DRDE
• 5.3 路段受限的流行性路由算法 RAEP
• 5.3.1 入口模式
• 5.3.2 直路模式
• 5.3.3 出口模式
• 5.4 算法性能评估（仿真）
• 5.4.1 无限资源
• 5.4.2 有限资源
• 5.4.3 数据包大小对性能的影响
• 5.4.4 缓存对性能的影响
• 5.5 小结
• 第六章 全文总结
• 6.1 本文工作总结
• 6.2 下一步研究工作
• 致谢
• 参考文献
• 攻博期间取得的研究成果