Download files
Abstract
This thesis concentrates on the message forwarding issues of real-world people-centric Delay Tolerant Networks (DTN), such as Pocket Switched Networks (PSN) and Vehicular Ad-hoc Networks (VANET), which are omnipresent, and hence pertinent to examine. These people-centric DTN often exhibit discernible network properties, which can be leveraged to develop efficient message forwarding schemes. In this thesis, we analyse the mobility traces of a large-scale public transport network. This type of network is an illustrative example of people-centric DTN. Our extensive analysis of its spatio-temporal communication graph identifies a power-law behaviour and periodicity in the mobility patterns. It also reveals the existence of \emph{hubs} (a group of highly connected nodes) in these networks.
Based on our observations of these networks, we propose three classes of functional message forwarding schemes for people-centric DTN. In particular, we propose a network coding based forwarding strategy, called the \emph{HubCode}, which seeks to exploit the hubs as message relays in an efficient manner. We formulate a mathematical model for estimating the message delivery delay and present a closed-form expression for the same. The large-scale simulation results show that under pragmatic assumptions, which account for short contact durations between nodes, our schemes outperform comparable strategies by more than 20%. Next, by utilizing the clustering property of people-centric networks, we propose a cluster-based forwarding scheme and a generic cluster formation method based on encounter frequencies between nodes, which uses the dynamic programming paradigm to reduce the complexity by an order, compared to traditional graph-theoretic approach. Our cluster-based forwarding approach outperforms the Spray and Wait scheme by about 12% in terms of delivery ratio. Finally, when the history of mobility patterns about the underlying network is available, we propose a statistical forwarding scheme which leverages this information in predicting the next best forwarder. In particular, we have proposed a Bayesian classifier based DTN message forwarding framework, that adopts a systematic approach for computing the forwarding metrics by utilizing the network parameters (e.g. spatial and temporal information at the time of message forwarding), which capture the periodic behaviour of DTN nodes. Simulation results show that even a naive instantiation of our Bayesian forwarding framework outperforms comparable gradient-based schemes by 25%, in terms of delivery ratio.
It is worth mentioning that our proposed forwarding schemes, which are based on the key characteristics of a real-world public transport network, are generic enough to be applicable for a wide range of people-centric DTN. This is due to the fact that the other real-world people centric DTN (e.g. pocket switched network) also share similar properties (e.g. existence of hubs) with the aforementioned network.