Blind online optimal forwarding in heterogeneous delay tolerant networks

International audience—In this paper we consider a heterogeneous DTN formed by different classes of nodes. A core problem in DTNs literature is to optimize forwarding control such in a way to deliver messages from source to destination under a given energy budget. In this context, we model the presence of different classes and describe the structure of the optimal solution. The closed form of an optimal policy is found in the family of the multi-dimensional dynamic strategies. These policies assign a specific threshold to each class of mobiles. We also show that in the multi-class case there exists an order of the classes that depends on the system parameters in a very simple form. In particular, we exploit the ordering induced by the optimal control with the goal of designing a new class of multi-dimensional stochastic approximation algorithms that apply to the heterogeneous DTNs. These algorithms are blind because they drive online the source node to the optimal operating point without requiring explicit estimation of network parameters (intermeeting intensities and the number of nodes for each class). Index Terms—Delay tolerant networks, multi-dimensional optimal control, ordering, stochastic approximation I. INTRODUCTION Delay Tolerant Networks (DTNs) are designed to sustain communications in networked systems where persistent end-to-end connectivity cannot be granted [1], [2], [3]. In DTNs, messages are carried from source to destination via relay nodes adopting the so-called " store and carry " forwarding, which leverages on nodes' mobility pattern. The core problem in DTNs is thus to efficiently route messages towards the intended destination. It is worth observing that due to frequent disruptions, traditional routing techniques would fail in this context. Furthermore, mobile nodes rarely possess information on the upcoming encounters they are going to experience [4]. Disseminating multiple copies of the message in the network is the straightforward routing solution. This ensures that at least some of them will reach the destination within some deadline [5], [6] with high probability. This is called epidemic forwarding [7], in analogy to spread of infectious diseases. We confine our analysis to the two hop routing protocol because of two major advantages: first, compared to epidemic routing it performs natively a better trade-off between the number of released copies and the delivery probability [6]. Second, forwarding control can be implemented on board of the source node. Under two hop routing, the source transmit