Research Of Social-based Forwarding Algorithm In Mobile Delay-Tolerant Networks

Mobile delay-tolerant networks which originated in Interplanetary Internetarchitecture research is a more general and representative form of challenged networkmodel. Intermittent connectivity, resource-constrained network nodes and highpropagation delay are some of the main characteristics of mobile delay-tolerantnetworks. Unlike traditional communication network model, there is no long-term orreliable end-to-end link existed in mobile delay-tolerant networks, which indicatesthat former network protocols based on the assumption of end-to-end connectivity areno longer applicable. Based on the store-carry-forward paradigm, each node in mobiledelay-tolerant networks makes use of the communication opportunities introduced bymovement to exchange messages. As the application scenarios increasingly emerge,such as rural Internet service, wildlife tracking system and environmental monitoringsystem, mobile delay-tolerant networks has become one of the hot research fields ofwireless sensor networks.Data forwarding algorithm is an important research aspect in mobiledelay-tolerant networks. Compared to traditional routing algorithm in wireless sensornetwork, data forwarding algorithm in mobile delay-tolerant network concerns notonly the nodes’ energy efficiency and the network lifetime, but also the messagedelivery rate, delivery delay and delivery cost. Generally, existing data forwardingalgorithms in mobile delay-tolerant network can be divided into the followingcategories: Replication-based forwarding algorithm, History-based forwardingalgorithm, Knowledge-based forwarding algorithm, Infrastructure-assisted forwardingalgorithm and Social-based forwarding algorithm. With the development ofmicroelectronics and communication technology, portable mobile devices (e.g.,smartphones and tablets) equipped with advanced processing, storage and communication capacities have been widely applied in people’s daily life. Networkingwith a huge number of portable mobile devices has become a typical scenario inmobile delay-tolerant network. In this scenario, considering that portable mobiledevices are usually carried by people while the mobility of people is difficult topredict, people’s social information which is relatively stable compared to rapidlychanged network topology is more suitable to be exploited to make forwardingdecisions. Therefore, social-based data forwarding algorithm is more applicable inthis scenario.With regard to the characteristics of this scenario, this thesis researches on howto improve the delivery efficiency. Based on the statistical analysis of contact patternsbetween human-carried mobile devices as well as the distributed community detectionalgorithm, this thesis presents efficient social-based data forwarding algorithms inmobile delay netowrks. The main contributions of this thesis are as follows:1) Based on empirical connectivity trace data, the aggregated distribution ofinter-contact time between each pair of nodes in the network, the individualdistribution of inter-contact time between each single node and any other encounterednodes, as well as the individual distribution of contact times between each single nodeand any other encountered nodes are investigated. This thesis presents empiricalevidence that power-law with exponential cutoff characterizes all three distributionsof interest better than other possible long-tail distributions. This thesis also makes therecommendation to use the average number of contacts within a time window as athreshold to detect the Familiar Set which is a precondition for some distributedcommunity detection algorithms.2) On the basis of the statistical analysis of contact patterns betweenhuman-carried mobile devices, this thesis proposes dynamic distributed communitydetection algorithm, in which the average value of accumulated contact duration andthe average value of contact times within a time window are exploited as two dynamicthresholds to detect the Familiar Set of each node. The Familiar Set information is exchanged and updated in each contact so that a local social graph is built up, onwhich overlapping community detection algorithm can be exploited to detect differentcommunities of each node. Compared to those algorithms capable to detect only onecommunity of each node, this method helps to reduce unnecessary delivery cost in theprocess of data forwarding.3) In order to improve the delivery efficiency for those algorithms rely on node’scentrality, this thesis investigates the distribution of the node’s centrality. Based on theobservation, this thesis presents BiBubble forwarding algorithm which comparesnodes’ centrality as well as Social Relation Level (SRL) to make use of morecommunication opportunities thus archieves higher delivery efficiency.4) In order to reduce the delivery cost of content sharing from those multi-copyforwarding algorithms which rely on comparison of node’s centrality, this thesispresents social-based source routing (SSR) algorithm. SSR logically devides thecontent sharing process into3phases: advertising phase, interest forwarding phaseand data forwarding phase. Different from traditional hop-based source routingalgorithm in wireless sensor networks, SSR constructs community-based paths duringadvertising phase to make a logical connection between content source and contentconsumer. Such community paths can be referenced afterwards in the process ofinterest/data forwarding. The results from trace-driven simulations show that undercertain conditions, SSR achieves comparable delivery rate and delivery delaycompared to multi-copy forwarding algorithm, while significantly reduces thedelivery cost due to single-copy forwarding mechanism.