Optimal Forwarding in Delay Tolerant Networks with Multiple Destinations

Thursday, November 01, 2012

We study the trade-off between delivery delay and energy consumption in a delay tolerant network in which a message (or a file) has to be delivered to each of several destinations by epidemic relaying. In addition to the destinations, there are several other nodes in the network that can assist in relaying the message. We first assume that, at every instant, all the nodes know the number of relays carrying the packet and the number of destinations that have received the packet. We formulate the problem as a controlled continuous time Markov chain and derive the optimal closed loop control (i.e., forwarding policy). The intermittent connectivity in the network implies that the nodes may not have the required perfect knowledge of the system state. To address this issue, we obtain an ODE (i.e., fluid) approximation for the optimally controlled Markov chain. This fluid approximation also yields an asymptotically optimal open loop policy. Towards the end I will also discuss a few other contexts where similar control problems arise and our methodology is applicable.


Chandramani Singh received ME and PhD degrees from the Electrical Communication Engineering Department at the Indian Institute of Science, Bangalore in 2005 and 2012 respectively. He worked as a member of technical staff at ESQUBE Communication Solutions Pvt. Ltd. from 2005 to 2006. Currently, he is a postdoctoral researcher at TREC Paris, a joint research team between INRIA and ENS de Paris. He was one of the recipients of the Microsoft Research India Rising Star Awards for the academic year 2010–2011.