Research On Routing Protocols For Delay Tolerant Networks

Delay Tolerant Networks (DTNs) are a class of networks in which nodes areintermittently connected. In DTNs, due to node mobility, power management,scheduling, etc., network topology changes dynamically. And a continuous end-to-endpath between a source and a destination may not ever exist. Furthermore, it ischallenging for nodes to obtain priori knowledge about network topology. Therefore,traditional routing protocols cannot be directly applied to DTNs.The routing protocol is closely related to the network performance. In recent years,the subject of DTN routing has almost become an independent and open research area.Because of the dynamic nature of DTNs, it is necessary to study routing protocols toreliably delivery data in extreme environments. By means of analyzing existing routingprotocols and mobility pattern of nodes, the main research results and innovations ofthis dissertation can be summarized as follows:(1) Adaptive SprayingIn the networks which are characterized with intermittent connectivity, replicationbased routing protocols can improve the probability of message delivery. One issue ofreplication-based routing protocols is how many replicas of a message should bedistributed in the network. In this dissertation, we propose a DTN routing protocolcalled Adaptive Spraying. Adaptive Spraying exploits mobility pattern and encounterhistory to predict the number of nodes with no copy a node will encounter within theexpected delivery delay. The number of nodes with no copy encountered can be viewedas the number of message copies disseminated. Every node with copies dynamicallychooses the right number of copies by itself. We also set the spraying depth. Simulationresults demonstrate that Adaptive Spraying keeps good performance while maintaininglow overhead in various sparse scenarios.(2) Adaptive Spraying Based on the Inter-contact TimeDue to dynamical changes of DTNs, a fixed number of message copies determinedby sources may not be appropriate to respond to the current conditions of the network.Changes in the network may not be ignored during the routing of a message. In this dissertation, we present a DTN routing scheme called ASBIT (Adaptive Spraying Basedon the Inter-contact Time). Based on the inter-contact time, each node independentlyselects the right number of message copies disseminated in a dynamic manner. Whentwo nodes encounter, message copies are forwarded to the nodes with higher degreecentrality. When dividing the replication number between two nodes, ASBIT takes intoaccount a representative set of attributes, including degree centrality, node speed andfree buffer. Simulation results show that ASBIT can delivery data efficiently with boththe Random Waypoint mobility model (RWP) and real traces.(3) Location-Aware Social RoutingSince social relationships tend to be relatively stable over time, social networkanalysis becomes an appealing technique to improve the routing performance. In thisdissertation, we propose a routing scheme for DTNs, called Location-Aware SocialRouting (LASR). LASR introduces location information to reflect the node relations.Two nodes, staying closer to each other most of the time, tend to belong to the samecommunity even if they have not been in the transmission range of each other before.Messages are forwarded to the nodes having higher global centrality, or nodes havinghigher local centrality in the destination's community. Simulation results show thatLASR can utilize location information to improve the accuracy of community detection.Consequently, messages can be more quickly and exactly forwarded to destinations.(4) Immunization-Based Redundancy EliminationReplication-based routing protocols distribute duplicate copies per message in thenetwork to improve the delivery ratio. However, after a successful delivery, the sourceand relays would continue carrying and forwarding the message copy. This results innetwork resources wasting. It is a critical issue for replication-based DTN routingprotocols. We formulate the redundancy elimination issues of flushing already deliveredmessage copies firstly. Inspired by the enhanced acquaintance immunization, we alsopropose an Immunization-Based Redundancy Elimination scheme (IBRE). Eachdestination dynamically selects the right number of ACKs disseminated. Each nodereceiving an ACK forwards it only once to the first encountered node with higherdegree centrality. Simulation results show that IBRE eliminates redundant copiesefficiently through a small number of ACKs disseminated in the network. Meanwhile itmaintains a comparable delivery ratio.