Title: Worst-case latency of broadcast in intermittently connected networks

Authors: Mikael Asplund; Simin Nadjm-Tehrani

Addresses: Linköping University, SE-581 83 Linköping, Sweden. ' Linköping University, SE-581 83 Linköping, Sweden

Abstract: Worst-case latency is an important characteristic of information dissemination protocols. However, in sparse mobile ad hoc networks where end-to-end connectivity cannot be achieved and store-carry-forward algorithms are needed, such worst-case analyses have not been possible to perform on real mobility traces due to lack of suitable models. We propose a new metric called delay expansion that reflects connectivity and reachability properties of intermittently connected networks. Using the delay expansion, we show how bounds on worst-case latency can be derived for a general class of broadcast protocols and a wide range of real mobility patterns. The paper includes theoretical results that show how worst-case latency can be related with delay expansion for a given mobility scenario, as well as simulations to validate the theoretical model.

Keywords: worst-case latency; connectivity; reachability; partitioned networks; graph expansion; dynamic networks; real time; delay tolerant networks; DTN; analysis; intermittently connected networks; information dissemination protocols; sparse MANETs; mobile ad hoc networks; mobile networks; delay expansion; broadcast protocols; mobility patterns.

DOI: 10.1504/IJAHUC.2012.050281

International Journal of Ad Hoc and Ubiquitous Computing, 2012 Vol.11 No.2/3, pp.125 - 138

Received: 01 Dec 2011
Accepted: 09 Jul 2012
Published online: 13 Nov 2012 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article