基于四叉树的路由技术研究

发布时间：2017-08-28 22:23

  本文关键词：基于四叉树的路由技术研究

  更多相关文章： 路由机制 信息论 四叉树 最优化 地理位置信息

【摘要】：在网络互连中,路由发挥了重要的作用。利用它一方面能够找到最优的路径；另一方面能够尽可能减小由路由引起的开销,从而提高路由协议的性能。迄今为止,大量的路由方案已被广泛研究。根据不同的需求,路由方案可以被分成多种类型。根据路由中利用信息的多少,现存的方案主要可以被分成两类,即基于图拓扑的路由和基于地理位置的路由。 对于基于图拓扑的路由,它总能保证找到最优路径,但路由表中包含了大量的表项。与基于图拓扑路由中路由表的大小相比,基于地理位置路由的路由表相当的小。然而,后者一般找不到全局最优的路径。本论文旨在现有的路由机制上改进,结合了上述两种路由机制的优点,同时回避了二者的缺点。论文主要贡献如下： 提出了一种基于四叉树的最优路径路由机制QOPR-一利用图拓扑路由的思想,它能够保证最优路径。此外,通过使用地理位置信息和四叉树结构,路由表的大小可以被压缩至其信息论的下界。为了保证最优路径且能将路由表尽可能的压缩,文献中已提出了大量的方案。通过利用地理位置信息,我们的理论结果比现存文献中的最好的结果(基于IP的方案)还要好。与其它方案相比,QOPR路由机制有两大优势。一方面,它的编码方案比IP地址更加直观。路由表中的目的节点由四叉树编码,它可以直观的划分、编码节点。另一方面,我们得到的路由表大小优于现存文献中的结果。仿真实验表明,一般情况下,本方案无论在路由表大小还是路由表的构建、查找性能上均优于基于IP的方案。 提出了一种QOPR+路由机制——针对QOPR路由机制中,当插入新节点时引起的路由更新的不足,在QOPR路由机制的基础上,提出QOPR+路由机制。通过采用一种新型的proper四叉树-位图混合结构(proper quadtree bitmap hybrid structure,简称pqbh(T))作为路由表,它能够进一步降低更新复杂度,兼顾查找速度和更新性能。此外,本文从理论上证明pqbh(T)也是一个很省空间的数据结构。与QOPR路由机制中路由表的大小只相差了一个很小的常数因子。仿真实验表明,一般情况下,QOPR+路由机制的路由表构建、查找、更新性能均优于QOPR路由机制中的性能,但这是通过牺牲部分路由表大小实现的。
【关键词】：路由机制 信息论 四叉树 最优化 地理位置信息
【学位授予单位】：中国科学技术大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：TP393.02;O157.5
【目录】：

• 摘要5-6
• ABSTRACT6-8
• 目录8-11
• 插图索引11-13
• 表格索引13-14
• 第1章 绪论14-20
• 1.1 研究背景与意义14-15
• 1.2 研究现状15-17
• 1.2.1 现有路由机制的研究现状15-16
• 1.2.2 路由表的压缩16-17
• 1.2.3 现有研究的不足17
• 1.3 研究内容与创新点17-18
• 1.4 结构安排18-20
• 第2章 相关路由技术及其应用20-30
• 2.1 基于图拓扑的路由方案20-23
• 2.1.1 先验式路由20-21
• 2.1.2 反应式路由21-22
• 2.1.3 混合式路由22-23
• 2.2 基于地理位置路由方案23-28
• 2.2.1 贪婪转发路由23-26
• 2.2.2 有限制的方向性洪泛路由26-27
• 2.2.3 分层路由27-28
• 2.3 利用四叉树解决路由问题28
• 2.4 本章小结28-30
• 第3章 基于四叉树的路由机制30-60
• 3.1 基于四叉树的路由机制30-37
• 3.1.1 四叉树对二维平面的编码方案30-31
• 3.1.2 网络拓扑31
• 3.1.3 QOPR 算法31-33
• 3.1.4 路由表的形式33-35
• 3.1.5 路由表的构建和查找35-37
• 3.2 性能分析37-42
• 3.2.1 路由表大小37-41
• 3.2.2 QCCT的性能41
• 3.2.3 路由表查找操作的性能41-42
• 3.3 仿真实验42-59
• 3.3.1 数据预处理42-43
• 3.3.2 性能验证43-59
• 3.4 本章小结59-60
• 第4章 QOPR+路由机制60-86
• 4.1 qcct(T)的更新60-62
• 4.2 QOPR+机制62-67
• 4.2.1 路由表的形式62-64
• 4.2.2 路由表的构建及查找64-66
• 4.2.3 路由表的更新66-67
• 4.3 性能分析67-71
• 4.3.1 路由表的构建性能67
• 4.3.2 路由表查找操作的性能67-68
• 4.3.3 路由表的更新68-69
• 4.3.4 路由表的大小69-71
• 4.4 仿真实验71-84
• 4.4.1 路由表的构建性能71-73
• 4.4.2 路由表查找操作的性能73-77
• 4.4.3 路由表的更新77-79
• 4.4.4 路由表的大小79-84
• 4.5 本章小结84-86
• 第5章 总结与展望86-88
• 5.1 论文总结86
• 5.2 未来工作展望86-88
• 参考文献88-94
• 致谢94-96
• 在读期间发表的学术论文与取得的其他研究成果96

【参考文献】

中国期刊全文数据库 前3条

1 魏子卿;;2000中国大地坐标系[J];大地测量与地球动力学;2008年06期

2 黄谟涛,翟国君,管铮,欧阳永忠;空间直角坐标和大地坐标的转换[J];解放军测绘学院学报;1998年03期

3 杨望;;CAIDA提供互联网数据共享服务[J];中国教育网络;2008年05期

，

本文编号：749812