Shortest path routing with reliability requirement in delay tolerant networks

Huai En Lian*, Chien Chen, Je Wei Chang, Chien Chung Shen, Rong Hong Jan

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

6 Scopus citations

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 spacetime 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.

Original languageEnglish
Title of host publication2009 1st International Conference on Future Information Networks, ICFIN 2009
Pages292-297
Number of pages6
DOIs
StatePublished - 21 Dec 2009
Event2009 1st International Conference on Future Information Networks, ICFIN 2009 - Beijing, China
Duration: 14 Oct 200917 Oct 2009

Publication series

Name2009 1st International Conference on Future Information Networks, ICFIN 2009

Conference

Conference2009 1st International Conference on Future Information Networks, ICFIN 2009
CountryChina
CityBeijing
Period14/10/0917/10/09

Keywords

  • Delay tolerant network
  • Reliable routing
  • Space-time graph

Fingerprint Dive into the research topics of 'Shortest path routing with reliability requirement in delay tolerant networks'. Together they form a unique fingerprint.

Cite this