Submitted: April 2022
Abstract
Delay Tolerant Networks (DTNs) offer the option to store-carry-and-forward bundles in space networks, which are often challenged by link disruptions and high propagation delays. As a result, DTNs are characterized by episodic communication opportunities, also known as contacts.
To optimize routing in DTNs, the Contact Graph Routing (CGR) algorithm aims at reducing the overall end-to-end delivery delay in perfectly predictable (scheduled) topologies. More recently, Routing under Uncertain Contact Plan (RUCoP) has been proposed to deal with uncertain topologies leveraging a multi-copy MDP formulation. The goal of RUCoP is to optimize the delivery ratio of bundles over future episodic links with a well-known probability of failure. Single-replica computations based on RUCoP were then ported to CGR (CGR-UCoP) to support practical applications where DTN nodes are limited to local observations. On the other hand, the state-of-the-art in DTN routing also includes opportunistic topologies. In these cases, newly discovered communication opportunities that were completely unknown before and therefore not included in a priori available structures such as the probabilistic MDP model. To embrace opportunistic contacts, Opportunistic CGR (OCGR) was introduced as an extension to CGR, which keeps a scheduled source topology as the starting knowledge base. Although these advances, to the best of our knowledge, uncertain and opportunistic routing remain separated.
In this thesis, we merge uncertain and opportunistic routing approaches in a single routing framework. Specifically, we propose OL-RUCoP and OCGR-UCoP, both opportunistic variants of the existing RUCoP routines based on local observability. To evaluate the schemes, we implemented them in the DTN simulator DTNSim, which was first prepared to support opportunistic behaviour and then extended with an OCGR implementation adapted from the Unibo-CGR library. OL-RUCoP and OCGR-UCoP algorithms are then evaluated in their performance in terms of delivery ratio, delivery time and energy efficiency. They are finally compared against the performances of existing uncertain and opportunistic schemes in an appealing benchmark set. The results show, that the proposed algorithms perform up to 6 times better than their uncombined variants, but slightly worse than oracle versions, that use contact plans, where all opportunistic contacts are already known.