基于地理位置信息的无线自组织网络贪婪路由算法研究

摘要

传统的基于拓扑结构的无线自组织网络的网络协议被大量的研究与应用,但是传统网络协议需要全局的网络拓扑信息以及并没有利用节点的地理位置这个物理信息。现实中的网络节点通过GPS等方式可以方便地获得自己的地理位置,并且全局拓扑信息的需求使得传统路由协议的可扩容性较差。所以对于不需要全局网络信息的利用节点的地理位置信息的路由算法的研究有着重要的意义。
　　本文首先阐述了基于网络拓扑结构的传统路由协议算法,并通过实验仿真分析了传统路由协议算法在数据分组成功投递率和路由数据分组开销上的性能;然后阐述了方向最近、前向最近和距离最近贪婪算法进行路由决策的方式,并从理论上证明了方向最近判据的贪婪路由算法无法避免路由回路的产生,而前向最近和距离最近判据的贪婪路由算法能够避免通信网络中路由回路的产生,通过实验仿真得到,方向最近判据的贪婪路由算法在数据分组成功投递率和平均路径跳数上比其他两种判据的贪婪路由算法性能差,距离最近判据贪婪路由算法在性能上比前向最近判据的算法性能略好;最后,阐述了路由空洞问题,并分析了完全遍历和单侧遍历面路由方式的性能,得出路由转发方式能够保证数据分组的有效交付,数据分组成功投递率都接近于百分之百,但是平均路径长度比较大,同时单侧遍历要比完全遍历的平均路径长度要短,性能更有优势。
　　本文将贪婪路由算法与面路由转发方式相结合,提出了保证交付的贪婪路由算法,能够克服贪婪路由算法所产生的本地最大问题。能够保证数据分组交付的贪婪路由算法在数据分组成功投递率方面有了明显的提升,但是由于面路由转发方式的加入,平均路径长度变长。并基于本地链路质量对保证交付的贪婪路由算法进行优化,优化过程完全在本地进行,并没有破坏贪婪路由算法协议分布式本地运行的性质,不会影响贪婪路由算法协议的网络可扩容性。相比于传统路由协议,保证交付的贪婪路由算法协议有着更高的数据分组成功投递率与更少的路由数据分组开销,并且当网络的规模变大的时候,贪婪路由算法协议所受到的影响并没有传统路由协议那么剧烈。基于链路质量优化后的贪婪路由算法协议在数据分组成功投递率这个指标上相比于优化前有着明显的提高,尤其是当网络中节点运动剧烈的情况下,性能提升更明显。

目录

U.D.C: 621.396

Dissertation for the Master’s Degree in Engineering

摘 要

Abstract

第1章 绪论

1.1 课题背景与意义

1.2 本文主要研究内容和结构

第2章 基于拓扑结构的传统路由算法

2.1 先应式路由算法

2.1.1 DSDV路由协议算法

2.2 后应式路由算法

2.2.1 DSR路由协议算法

2.2.2 AODV路由协议算法

2.3 基于拓扑结构的传统路由协议算法性能分析

2.3.1 场景模型参数设置与网络性能评价指标

2.3.2 路由协议仿真结果

2.4 本章小结

第3章 利用贪婪算法的路由决策

3.1 贪婪算法概念

3.2 贪婪路由选择算法

3.2.1 方向最近判据的贪婪路由算法

3.2.2 前向最近判据的贪婪路由算法

3.2.3 距离最近判据的贪婪路由算法

3.2.4 其他的贪婪路由算法

3.3 路由空洞问题

3.4 不同判据贪婪路由算法性能

3.5 本章小结

第4章 贪婪路由算法的路由空洞处理

4.1 路由空洞问题解决思想

4.2 通信网络图的平面子图

4.2.1 RNG平面化

4.2.2 GG平面化

4.2.3 平面子图的连通性

4.3 面路由转发方式

4.3.1 完全遍历的面路由方式

4.3.2 单侧遍历的面路由方式

4.4 面路由转发方式用来保证交付的性能分析

4.5 本章小结

第5章 保证交付的贪婪路由算法协议

5.1 利用面路由方式保证交付的贪婪路由算法协议

5.2 基于本地链路质量的贪婪路由算法协议优化

5.2.1 信号传播模型

5.2.2 基于链路质量的优化

5.3 贪婪路由算法协议的性能分析

5.3.1 分组成功投递率

5.3.2 路由协议开销

5.3.3 数据转发路径长度

5.3.4 网络直径的影响

5.4 本章小结

结 论

参考文献

攻读学位期间发表的学术论文

哈尔滨工业大学学位论文原创声明及使用授权说明

致 谢