Delay (or disruption) tolerant sensor networks may be modeled as Markovian evolving graphs [1]. We present experimental evidence showing that considering multiple (possibly not shortest) paths instead of one fixed (greedy) path can decrease the expected time to deliver a packet on such a network by as much as 65 per cent depending on the probability that an edge exists in a given time interval. We provide theoretical justification for this result by studying a special case of the Markovian evolving grid graph. We analyze a natural algorithm for routing on such networks and show that it is possible to improve the expected time of delivery by up to a factor of two depending upon the probability of an edge being up during a time step and the relative positions of the source and destination. Furthermore we show that this is optimal, i.e., no other algorithm can achieve a better expected running time. As an aside, our results give high probability bounds for Knuth's toilet paper problem [11].

Additional Metadata
Keywords Ad hoc networks, Delay tolerant, Disruption tolerant, Evolving graphs, Routing, Sensors
Persistent URL
Keane, M. (Michael), Kranakis, E, Krizanc, D. (Danny), & Narayanan, L. (Lata). (2009). Routing on delay tolerant sensor networks. doi:10.1007/978-3-642-05434-1_17