Delay-Tolerant Networking is a promising approach to address technical issues in networks that are subject to frequent partitioning (termed intermittently-connected networks). In particular, the Delay-Tolerant Network (DTN) architecture was designed to ensure interoperability, performances, and security in heterogeneous networks where end-to-end paths may never exist. In this paper, we focus on the problem of routing in DTNs. The common approach is to use a store-carry-forward mechanism, i.e. data are sent from one node to another, depending on the communication opportunities that occur, and stored throughout the network in hope that messages will reach their destinations. We assume reliable predictions can be made about node mobility, and thus study the problem of making use of this knowledge when data need to be routed from one subset of nodes to another within a given time horizon. To ensure robustness, we search for solutions that remain valid even if some transfers fail. Applications include satellite and interplanetary networks (where the trajectory of nodes depends on straightforward physics), fleets of drones, and public transportation systems.
Mots clés : operational research, combinatorial optimization, robust optimization, constraint programming, routing, delay-tolerant networks