【作者】 刘耀；

【导师】 王建新；

【作者基本信息】 中南大学 ， 计算机应用技术， 2012， 博士

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

【Abstract】 Delay tolerant networks (DTN) are an emerging network architecture. In such type of networks, nodes have small storage capacity and limited processing capability. Network partition and link disconnection often occurs for the sake of nodes frequently moving, sparsely distributed, and energy saving. An end-to-end path from a source to a destination may not always exist. Traditional routing schemes do not accommandate such conditions, and they would not work efficiently. The message transfer paradigm is changed greatly. Routing is the main issues in DTN. This dissertation investigates routing schemes in different type of delay tolerant networks and buffer management schemes that have great impact on routing. The main contributions of this dissertation are concluded as follows.(1) Characteristics of node mobility are in favor of designing efficient routing algorithms in DTN. A routing algorithm based on mobility scope aware (MSAR) is proposed with uncertainty of network status. It does not need the support of geographical position location devices. It uses encounter histories as utility to analyze node mobility scope, and decide whether the node are chose to forward messages. It compares the mobility similarity between message carrier node and encounter node. It also compares mobility similarity between message carrier node and destination node with mobility similarity between encounter node and destination node. Simulation results show that MSAR may guarantee higher message delivery ratio and relative lower delays. It can greatly decrease the number of message copies distributed in the network and overhead ratio. It can be easily implemented with low overhead of control.(2) Through analyzing trace data in real world, we can observe that centrality has the characteristics of approximate distribution of power law. Centrality is used as routing metric in delay tolerant networks. The nodes that have higher centrality value will suffer great traffic loads and become hot spots. It will result in congestion in these nodes. A lot of messages are discarded and retransmitted, and then network resources are wasted. A social-based load aware routing algorithm is proposed to resolve this problem. The proposed routing algorithm uses two social metrics, i.e. betweenness centrality and social similarity, and node’s load status to select relay nodes. It could avoid serious congestion in the nodes that have stronger ability of disseminate messages, and also balance traffic load. Simulation results show that the proposed routing algorithm could increase message delivery ratio and reduce network overhead.(3) When using quota-based routing algorithms, such as spray and wait, message copies would be premature to distribute in the case of higher node density. Message copies are limited to a local area that will cause a larger delay and decrease delivery ratio. A node density adaptive spray and focus (DASF) routing algorithm is proposed to address this problem. By estimating the node density of the current node location, DASF could control the available distributed number of message copies. And then it allocates message copies between encountered nodes according to the level of activity. Simulation results show that the proposed routing algorithm can reduce message transmission average delay significantly and improve delivery ratio.(4) As the storage-carry-forward paradigm is adopted to transfer messages in DTN, buffer management schemes greatly influence the performance of routing algorithms when nodes have limited buffer space. From a network-wide viewpoint, the excessive increase of a single message’s copies will exhaust nodes’buffer space, thus reduces the probability of other messages to be buffered and forwarded and leads substantial decrease in their delivery ratio. Inspired by the law of diminishing marginal utility in economics, we propose a buffer management scheme based on estimated status of messages, e.g. the total number of copies in the network and the dissemination speed of a message. When performing buffer replacement and scheduling, nodes use encounter histories to estimate status of messages and act accordingly:when buffer overflow occurs, messages that have larger estimated number of copies and faster dissemination speed are replaced prior to and forwarded posterior to other messages. Simulation results show that our buffer management scheme can improve delivery ratio and has relative lower overhead ratio compared with other buffer management schemes.This dissertation focuses on the routing issues and related technologies in delay tolerant networks. These works could solve some routing problems in different DTN environments. It also provides valuable references for the development of routing technologies.更多还原