Comparison of Policies for Epidemic Broadcast in DTNs under Different Mobility Models

Introduction

The mobile nodes of a delay tolerant network, or DTN (DTN Research Group, 2008), experiment intermittent connectivity and network partitions. So far, in such a critical scenario, the research mainly focused on the problem of providing unicast communications (e.g. (Burgess, Gallagher, Jensen, & Levine, 2006; Davis, Fagg, & Levine, 2001; Jones, Li, & Ward, 2005; Juang, Oki, Wang, Martonosi, Peh, & Rubenstein, 2002; Spyropoulos, Psounis, & Raghavendra, 2004)). By contrast, the one-to-all communication scheme has not received the same attention despite the fact that its service is strategic to support protocols at both application and routing levels. For instance, a broadcast service is required to diffuse scoped advertisements—e.g. about available services or events—and summaries (Lee, Magistretti, Zhou, Gerla, Bellavista, & Corradi, 2006), to support podcasting (Lenders, Karlsson, & May, 2007), or to diffuse acknowledgments, or cure, packets (Harras, Almeroth, & Belding-Royer, 2005). In a DTN, broadcast can be designed by adopting one of the gossip-based mechanisms that have been proposed in the literature in a few slightly different alternatives by starting from the following PUSH-based scheme: when a node has a message m, it forwards m to one or more (possibly all) neighbors it happens to encounter while moving. The forwarding, elsewhere called infection or epidemic, can be either performed periodically (Montresor, Jelasity, & Babaoglu, 2005) or whenever a contact occurs (Vahdat, & Becker, 2000). Infection can continue up to either the message lifetime or a given number of transmissions. The PUSH-based algorithm is effective in achieving a node coverage arbitrarily close to 1 with low latency, but fails in doing this efficiently. Indeed, nodes perform epidemic forwarding with no knowledge about the state of the encountered nodes and, as a consequence, they often happen to forward a message to already infected nodes.

The primary focus in the design of a—both efficient and effective—broadcast protocol is to increase the node likelihood of delivering a message only to uninfected nodes. There are several, growing levels of knowledge a node could achieve about the neighbors state and to approximate the global system state. Whatever is the followed approach to achieve efficiency, the performance of the algorithms is greatly influenced by the mobility patterns that nodes follow (Camp, Boleng, & Davies, 2002). The comparative analysis of the effects of mobility on protocols deserves more attention and, as far as we know, has never been applied to broadcast. This paper moves into this research track and provides some interesting contributions to understand broadcast delivery over DTNs under different mobility conditions. Firstly, the paper defines a family of broadcast protocols, obtained from the PUSH-based approach through the introduction of adaptive mechanisms whose purpose is the improvement of the node awareness about the level of infection in the neighborhood. Secondly, the performances of the different mechanisms are analyzed in three basic mobility model: the classical random waypoint, the swarm mobility, and the aggregation model where nodes move throughout aggregation points. The main contribution of the paper is twofold: (i) it identifies and characterizes the winning mechanisms to diffuse messages in DTNs under different conditions, and (ii) it is a first attempt to move toward the design of an autonomic and situational algorithm able of autonomously adapting its parameters according to the mobility context the node is moving through, in order to optimize performances.