Shortest Path Routing with Reliability Requirement in Delay Tolerant Networks

Abstract

The topology of a delay tolerant network (DTN) over time has been modeled by a space-time graph. However, the mobility of nodes, such as buses, may not be completely predictable due to factors such as traffic load, road condition, the number of passengers getting on and off the buses, and the operations of traffic lights. In this paper, we adapt the space-time graph by augmenting each horizontal edge with a direct contact probability to model the uncertainty of connectivity. With such an augmented space-time graph, our goal is to compute a shortest routing path satisfying a given end-to-end delivery reliability in a DTN. To facilitate such computation, we adapt the Floyd-Warshall algorithm to compute the maximum contact probability matrix at each time interval. By using an iterative matrix multiplication scheme on a maximum contact matrix, we can compute the shortest path satisfying the reliability constraint. Simulation results validate the performance of our solution which achieves a good balance between delay and reliability.