Opportunistic shortest path forwarding in disruption tolerant network

Abstract

In this thesis, we focus on estimating a metric to adjust optimal forwarding framework with delay minimizing objective in delay/diruption tolerant network(DTN) which is regarded as an opportunistic network. Using inter-contact time, a consideration of the multi-hop contacts path finds better path than considering only one hop contact path. In opportunistic network, since every node has intelligence to decide forwarding and scheduling and rate control, the multi-hop contacts path is not pre-determined by source node. One thing we did here is that we present a novel metric estimation algorithm called opportunistic transitivity (OTR) which can be well-adapted to opportunistic network property. Using the opportunism, we show the 12.5 percents delay gain compared to the transitivity algorithm and we call that gain a multi-contact diversity gain. Secondly, we propose more practical algorithm exploiting multi-contact diversity gain. While OTR needs to regard any topology as a complete graph including opportunistic links, Approach First Inter-Contact(AFIC) algorithm which we propose here reduces hop counts from undetermined to 2 hop and the candidate set from all nodes to one hop contact nodes. Using the property of vehicles` locality which we found on real trace, we reduce the complexity as well as keeping the OTR`s performance level. Geographic correlation of each vehicle mitigates the high complexity of OTR. In Chapter 2, we consider regularity in urban city environment using real trace 4000 taxies. In contrast to well-known [1,2] inter-contact regularity, inter-visit regularity and inter-visit time distribution is not studied well. In order to find new circumstance in urban city environment, we first plot the correlation between everyday visiting spots to know temporal regularity. We show that the visiting pattern of all vehicles is repeated daily. Second, we show spatial regularity which means that the regularly visiting spots of each vehicle are spatially div...