Year

2014

Degree Name

Doctor of Philosophy

Department

School of Electrical, Computer and Telecommunications Engineering

Abstract

Delay Tolerant Networks (DTNs) are characterized by the lack of contemporaneous paths between any source and destination node. In these networks, nodes act as relays, whereby they cooperatively help forward data bundles from a source to a destination node. As a basic forwarding strategy, nodes may flood bundles to every encountered node. However, flooding results in congestion and unnecessarily consume precious resources such as buffer space and bandwidth. To this end, many routing protocols select a next hop node based on metrics such as delivery probability and encounter rates. Another strategy is one adopted by quota based protocols in order to reduce resource usage. Namely, for each bundle, only a limited number of copies or replicas are disseminated throughout the network. However, they suffer from low delivery ratios as their dissemination rate is low. Hence, bundles need to be efficiently managed in order to achieve high delivery ratios, low delays and low overheads. Another key challenge is considering both routing and buffer management simultaneously when network resources such as bandwidth and buffer are limited and the number of replicas for each bundle is finite. Under such conditions, sender nodes need to select a next hop node that results in a high delivery ratio. In addition, as nodes may need to send a large number of bundles in each contact, their communication bandwidth may not be sufficient to transmit all buffered bundles. In addition, due to limited buffer size, when replicas are dropped by nodes when their buffer overflows, the delivery probability of the corresponding bundles reduces. This is because no provisions are provided to replace a dropped replica in order to maintain a high delivery ratio.

This thesis proposes a quota-based protocol that is based on weighting nodes that have encountered the final destination higher than any other nodes. This fact is based on the idea that regardless of how small an encounter rate with the destination is, given a highly correlated movement model, e.g., human, we will end up with a high delivery ratio. This idea is then studied analytically using a time homogeneous semi- Markov process (THSMP). Analysis shows that a targeted forwarding strategy based on contact history with a destination improves bundle delivery when there are finite replicas. A destination-based routing protocol (DBRP) is then proposed to specifically target nodes that have a history with a bundle's destination. Simulation studies over three scenarios show that in terms of a composite metric comprising of delivery, delay and overhead, DBRP achieves up to 57% improvement over three well-known routing protocols, namely PROPHET, EBR and Spray and Wait. Moreover, DBRP results in nodes experiencing at least 28% lower buffer consumption.

The second proposed method investigated in this thesis is an efficient scheduling and drop policy called QM-EBRP for use under quota based protocols. In particular, QM-EBRP makes use of the encounter rate of vehicles and context information such as time to live, number of available replicas and maximum number of forwarded bundle replicas to derive a bundle's priority. Simulation results, over a service quality metric comprising of delivery, delay and overhead, show that the proposed policy achieves up to 80% improvement when vehicles have infinite buffer space and up to 35% when vehicles have finite buffer space over six popular queuing policies: Drop Oldest (DO), Last Input First Output (LIFO), First Input First Output (FIFO), Most FOrwarded first (MOFO), LEast PRobable first (LEPR), and drop bundles with greatest hop count (HOP-COUNT).

Lastly, this thesis considers a Mobility-Based Routing Protocol (MBRP) that constructs a space-time graph at every node by recording the mobility pattern of nodes upon each contact. In particular, nodes do not have full knowledge of the network topology. Also, the space-time graph is dynamic, meaning the trajectory of nodes may only be valid for a given period of time. As the space-time graph may be incomplete, MBRP presents a heuristic that evaluates encountered nodes based on their recorded mobility patterns in order to disseminate a finite number of replicas. MBRP has been evaluated over a realistic environment comprising of vehicles with both periodic and dynamic mobility patterns. The simulation results, over a service quality metric comprising of delivery, delay and overhead, show that MBRP achieves up to 105% improvement as compared to four well-known routing protocols namely, EBR, EPIDEMIC, MAXPROP, and PROPHET. Finally, MBRP is capable of achieving 50% of the performance attained by the optimal algorithm, whereby all nodes are preloaded with the space-time graph.

Download

Share

COinS
 

Unless otherwise indicated, the views expressed in this thesis are those of the author and do not necessarily represent the views of the University of Wollongong.