Online Routing and Scheduling in Bandwidth-Limited Delay Tolerant Networks.

When delivering messages in bandwidth-limited Delay Tolerant Networks (DTNs), which are always intermittently-connected and frequently-partitioned, one of the most important challenging problems is how to route messages and schedule transmissions. Namely, an efficient routing and scheduling strategy in bandwidth-limited DTNs should arrange messages properly for each limited transfer opportunity to achieve a high performance. This paper investigates how to make such decisions to minimize average delivery delay of messages. To obtain an optimal average delivery delay, a node should consider not only current contact opportunities but also future ones. In this paper, we firstly formulate the problem of message delivery in bandwidth-limited DTNs into a minimum cost maximum flow (MCMF) problem, and then propose an Online Routing and Scheduling (ORS) algorithm based on corresponding MCMF results. Furthermore, we also propose an extended distributed algorithm with partial information based on ego network used in social networks. Our ORS is finally evaluated on publicly available data sets Infocom and Roller traces against MED, SimBet and PRoPHET. The results show that the delivery delay of ORS is at least 49% shorter than that of existing works. At the meantime, the delivery ratio of ORS is also the highest. [ABSTRACT FROM AUTHOR]