基于双曲空间的网络贪婪路由研究

摘要

当今的Internet面临核心路由表持续膨胀的问题。为了缓解这一问题以及适应更多的网络应用情景，研究者们提出了很多路由改进方案和新的路由策略。其中基于图嵌入的贪婪路由方案由于转发策略简单且不依赖于路由表，在移动传感器网络和下一代互联网中开始受到越来越多的关注。
　　传统的图嵌入方案将网络拓扑嵌入到欧几里得空间。由于受到维度的限制，无法实现完全贪婪嵌入，路由存在空洞问题。Kleinberg开创性地证明了有限节点的网络都可以被完全贪婪嵌入到双曲平面之中，使得端到端的贪婪路由100％成功成为可能。
　　首先，本文对双曲几何的基本理论进行了分析，着重分析了双曲平面在欧几里得平面的映射模型。为双曲嵌入理论作出铺垫，随后研究了贪婪路由的双曲嵌入理论，基于双曲平面模型，对现有的几种网络双曲嵌入方案进行了研究。
　　接下来本文对复杂网络的特征量和经典模型进行了介绍，并基于双曲平面模型，实现了一种双曲嵌入无标度网络的拓扑生成器。通过该拓扑生成器，生成了具有双曲坐标的无标度网络拓扑。本文对生成拓扑的复杂网络特性进行了仿真和研究，并对在生成网络中进行贪婪路由的结果进行了分析。证明了双曲嵌入网络具有极好的贪婪路由性能。
　　最后，本文对双曲嵌入网络中的贪婪路由策略进行了深入的研究，对现有的多种贪婪路由策略进行了性能仿真，对比分析了不同策略的路由成功率，网络延伸系数等性能指标。创新性地提出了降低贪婪转发过程中的选路复杂度的快速贪婪路由策略。依据实验结果证明了快速贪婪路由策略具有良好的路由性能，可以大幅度降低选路计算复杂度，并能和现有的贪婪路由策略相结合。本文还对基于贪婪嵌入特性，在双曲嵌入网络中进行有限洪泛路由进行了研究，实验表明，限洪泛路由可以提高整体路由成功率。

目录

封面

声明

中文摘要

英文摘要

目录

第一章 绪论

1.1 Internet路由现状

1.2 传统路由方案面临的挑战

1.3 新型路由方案的研究

1.4 本文的结构安排与主要工作

第二章 双曲几何与双曲嵌入

2.1 双曲几何概述

2.2 双曲平面的贪婪嵌入

2.3 双曲空间下的贪婪嵌入方案

第三章 双曲嵌入无标度网络拓扑生成器实现

3.1 复杂网络的拓扑结构

3.2 拓扑生成器的实现

3.3 拓扑生成器的实现与仿真分析

第四章 双曲嵌入网络贪婪路由策略的改进

4.1 双曲嵌入贪婪路由的优势

4.2 局部最小问题

4.3 贪婪路由策略

4.4 快速贪婪策略

4.5 有限洪泛贪婪路由策略

第五章 总结

致谢

参考文献