Routing And Buffer Management Algorithms In Delay Tolerant Networks

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.