延迟容忍网络中路由与缓存管理算法

摘要

延迟容忍网络(delay tolerant networks，DTN)是一种新型的网络体系结构。在这种类型的网络中，节点具有存储空间小、计算能力低的特点。由于节点频繁的移动、稀疏的分布或者节省能量等原因，经常造成链路中断、网络分割的现象。因此，源节点和目的节点之间长期不存在端到端的路径，从而导致消息在节点之间传输的延时非常大。消息传递的方式发生了重大的改变，传统的路由方式已经不能适应这样的网络。延迟容忍网络中如何将消息成功地发送到目的地是一个挑战性的问题。因此，路由是延迟容忍网络中最主要的问题。本文针对各种不同环境的延迟容忍网络的路由技术以及对路由性能影响很大的缓存管理技术进行了深入的研究，本文的主要研究工作包括以下几个方面的内容。
　　 (1)掌握节点的移动特征，有利于设计高效的路由算法。在网络状态未知的情况下，提出了一种基于节点运动移动范围感知的路由算法MSAR。不需要地理位置定位等硬件的支持，根据节点的历史相遇记录来比较消息携带节点和相遇节点的移动范围的相似性，以及消息携带节点和相遇节点两者与目的节点的移动相似性，并以此作为消息复制转发的依据。实验结果表明，MSAR路由算法能够有效的提高节点的交付比率并降低网络的开销。
　　 (2)通过实际的行踪数据分析发现，采用中心性作为路由度量尺度具有幂律分布的特点。如果采用中心性较大的节点作为中继节点，会使这些节点成为热区节点，造成网络的拥塞，导致消息大量的丢弃和重传而浪费网络资源。在中心性作为路由度量的基础上提出了一种负载感知的路由算法，该算法使用介数中心性和相似性以及节点的负载状况作为中继节点选择的依据，避免了消息传播能力强的节点产生严重的拥塞，均衡网络流量。仿真结果表明，该算法在容忍消息延时的情况下能够提高网络的交付比率，减小网络的开销。
　　 (3)针对基于固定消息副本数量的喷射与等待这类算法在节点密度较大的情况下会过早地将消息副本分发完毕，使消息局限于一个局部区域，会造成较大的延时并降低交付比率的问题，提出了一种基于节点密度自适应的喷射与转发路由算法DASF。DASF通过估计当前节点所在位置的节点密度，控制每次用于分配的消息副本数量，然后根据节点活跃程度按比例分配消息副本数量。仿真结果表明，该算法能够在提高交付比率的基础上，明显地减小消息传递的平均延时。
　　 (4)延迟容忍网络中节点采用“存储-携带-转发”的方式传递消息。在缓存空间有限时，不同的缓存管理策略对路由算法的性能有很大的影响。从整个网络的角度来看，一个消息过分地复制转发会耗尽节点的缓存，减少了其他消息对缓存使用的概率，从而导致了交付比率的下降。受微观经济学边际效用递减法则的启示，提出了一种分布式的基于消息传播状态的缓存管理方法。当缓存不够时，节点将消息复制数量多和传递速率快的消息丢弃，而在转发时则优先发送消息复制数量少和传递速率慢的消息，保证了副本数量较少的消息获得更多的传输机会。仿真实验结果表明，该方法能够提高消息的交付比率并且具有相对较小的开销比率。
　　 本文对延迟容忍网络中的路由和相关技术进行了深入的研究，这些研究工作能够较好地解决不同延迟容忍网络环境下的路由问题，为延迟容忍网络路由技术的发展提供有价值的参考。

目录

声明

摘要

第一章 绪论

1．1 研究背景与意义

1．1．1 DTN概述

1．1．2 DTN的体系结构和特点

1．1．3 DTN路由及相关技术的研究意义

1．2 DTN路由研究现状与分析

1．2．1 DTN路由的目标

1．2．2 DTN路由分类

1．3 研究目标与主要研究内容

1．4 论文的组织结构

第二章 移动范围自感知路由算法

2．1 节点移动特征研究概述

2．2 网络模型与假设

2．3 MSAR路由算法

2．3．1 路由转发度量定义

2．3．2 MSAR算法描述

2．4 仿真实验

2．4．1 仿真环境设置

2．4．2 性能分析与评价

2．5 小结

第三章 基于节点社会属性的负载感知路由算法

3．1 移动社会网络概述

3．2 中心性特征分析

3．3 SBLAR路由算法

3．3．1 路由度量尺度

3．3．2 路由算法SBLAR实现

3．4 仿真实验

3．4．1 实验场景设置

3．4．2 实验结果与分析

3．5 小结

第四章 节点密度自适应的喷射与转发路由算法

4．1 副本数量受限路由概述

4．2 消息副本数量分配过程分析

4．3 DASF路由算法

4．4 仿真实验

4．4．1 仿真环境设置

4．4．2 实验结果与分析

4．5 小结

第五章 基于消息传播状态的缓存管理方法

5．1 DTN缓存管理概述

5．2 系统模型与分析

5．2．1 系统模型与假设

5．2．2 系统分析

5．3 缓存管理策略

5．3．1 缓存替换策略

5．3．2 缓存调度策略

5．4 仿真实验

5．4．1 仿真环境设置

5．4．2 性能分析与评价

5．4．3 缓存管理策略对路由算法的影响比较

5．5 小结

第六章 总结与展望

6．1 工作总结

6．2 进一步的研究方向

参考文献

致谢

攻读博士学位期间参加的科研项目及研究成果