Research On Social Delay Tolerant Networks Based On Graph Mining Methods

Delay-Tolerant Network(DTN)is a special network model which is frequently used in the scenes of reconstruction after disasters and space communications,where the end-to-end delay is tolerable because of the absence of the communication infrastructure,the unpredictable movement of the nodes in the network,and the unreliability of the communication links between each two nodes.Therefore,Traditional Ad hoc Network routing protocols cannot apply to Delay-Tolerant Network.To improve the efficiency of transmissions,nodes exploit the store-carry-forward scheme to deliver messages.Social Delay-Tolerant Network is a subset of DTN where the nodes in the network are carried by human beings.As a result,most existing Social DTN routing protocols are proposed based on the characteristics of human being society.Bubblerap is a classic Social DTN routing scheme,which proposes its routing strategy based on separating the communities in the society.In the process of delivering messages,the node carrying the message deliver the message to nodes with higher global social metric it encountered.Intuitively,this scheme can accelerate the delivering and the destination community would receive the message quicker.We found and verified that there are two different reasons that will lead to a high global social metric:(1)the node is active(i.e.,keep a number of links with other nodes)within its community,and(2)the node is active among multiple communities.In the first case,when using Bubblerap protocol,the message would be wrongly forwarded within its community,thus it cannot be effectively forwarded to its destination community.We found the second case can contribute the delivery.To address this problem,first,we propose the singularity metric to indicate the active level of a node among different communities,i.e.,the probability of successfully forwarding messages to any other community.Nodes with high singularity metric have more opportunities to forward messages to their destination communities.Therefore,the node carrying a message can opportunistically forward it to the nodes it encounters by selecting the ones with higher singularity metric.Thus,forwarding efficiency can be improved.Secondly,we estimate the probability that a node will forward a message to another node in the next period of time.This is important to avoid the situation that the node holding the message cannot forward it to its next hop for a long time.We propose the routing protocol SBTP for Social DTN based on the above two contributions.Finally,we evaluate the effectiveness of the our proposed routing protocol utilizing the singularity metric and the prediction scheme,by comparing it with other Social DTN routing protocols.The simulation results show that our protocol can effectively reduce the transmission cost and delay,thus accelerate the delivery speed in Social DTN.