Social-Based Data Routing Strategies in Delay Tolerant Networks
by Konglin Zhu
Date of Examination:2014-02-25
Date of issue:2014-04-03
Advisor:Prof. Dr. Xiaoming Fu
Referee:Prof. Dr. Xiaoming Fu
Referee:Prof. Dr. Mario Gerla
Referee:Prof. Dr. Dieter Hogrefe
Referee:Prof. Dr. Jens Grabowski
Referee:Prof. Dr. Carsten Damm
Referee:Prof. Dr. Stephan Waack
Files in this item
Name:zhu_thesis1.pdf
Size:1.85Mb
Format:PDF
Abstract
English
Delay Tolerant networks (DTNs) are intermittently connected mobile networks in which the end-to-end paths do not exist. Data delivery in such networks relies upon the contacts that use "store-carry-and-forward" paradigm to forward message from one node to another. However, such intuitive methodology encounters low message delivery ratio and high data transmission delay when applying to different data routing strategies. The design of effective and efficient data routing strategies based on limited knowledge of mobile nodes in DTNs is challenging. In this dissertation, we explore several aspects of social information that can be applied for data routing in DTNs. We discuss the problems of data routing in DTNs and study the using of different social information and network features to facilitate data routing in DTNs. Specifically, we propose three different data routing strategies relying on different types of social information obtained from mobile nodes: (a) a location-based social routing strategy applying different aspects of location-based social information; (b) an encounter-based social routing strategy relying on several encounter-based social factors of mobile nodes in the network; (c) a community-based routing strategy combining social and mobile factors as well as community structure. The proposed location-based social routing strategy is motivated by the fact that location information can provide the geographic distance and the direction of information propagation, which can guide the data to the destination effectively. The proposed location-based social strategy considers both geographic distance and user mobility pattern as factors and combines them into one utility function for data forwarding. We propose the encounter-based social routing strategy based on the fact that users in DTNs are interactively connected by encountering events. The design of encounter-based social strategy involves social centrality and social similarity. Compared to location-based social strategy, the usage of encounter-based social information is much less sensitive than location-based social information. By convoluting two social factors into utility function, the proposed algorithm can achieve competitive performance with location-based routing strategy. The design of the community-based strategy is motivated by the observation that the mobility of people concentrates on a local area and the communication occurs in the form of communities. To apply such characteristics for elevating data routing performance in DTNs, we propose a Social and Mobile Aware Routing sTrategy (SMART). It exploits a distributed community partitioning algorithm to divide the DTN into communities regarding user locations and interaction routines. For intra-community communication, a decayed routing metric convoluting social similarity and social centrality is calculated, which is used to decide forwarding node efficiently while avoiding the newly identified blind spot and dead end problems. Meanwhile, to enable efficient inter-community communication, we choose the fringe nodes which travel remotely as relays, and propose the node-to-community utilities for routing decision across communities. The major contribution of the thesis is to compose comprehensive routing metric to overcome the situation that is not addressed by using single routing metric, and then identify and tackle the blind spot and dead end problem, which are severe but not noticed in the existing studies. The proposed location-based strategy and encounter-based strategy are to construct comprehensively routing metric in geographic and encountering perspectives, and the proposed SMART is to tackle the blind spot and dead end problems. Among all three strategies, the objective is to enhance the data delivery ratio, reduce the average delay and meanwhile maintain the low cost for data delivery. We present the simulation results regarding to the performance of the proposed routing strategies with the state-of-the-art data routing strategies in DTNs. By comprehensively consider multiple aspects of routing metrics, the proposed location-based and encounter-based routing strategies outperforms the previous studies around 10% in terms of different evaluation metrics. Through identifying and solve blind spot and dead end problems, the proposed SMART resolves both of them and thus outperforms previous studies over 20%.
Keywords: Social-based Data Routing; Delay Tolerant Network; Location-based Routing; Encounter-based Routing; Social and Mobile Aware Routing