Antonio Fernandez Anta, IMDEA, Spain

Title: Opportunistic Information Dissemination in Mobile Ad-hoc Networks. Adaptiveness vs. Obliviousness and Randomization vs. Determinism

Abstract:
In this talk the problem of Information Dissemination in Mobile Ad-hoc Networks (MANETs) is studied. The problem is to disseminate a piece of information, initially held by a distinguished source node, to all nodes in a target set. In MANETs, nodes are embedded in the plane and can move with bounded speed. Communication between nodes occurs over a collision-prone single channel. We assume a weak set of restrictions on the mobility of nodes, parameterized by α, the disconnection time, and β, the link stability time, such that the MANETs considered are connected enough for dissemination. Such a connectivity model generalizes previous models in that we assume much less connectivity, or make explicit their assumptions.

We start by studying the solution of the problem by means of deterministic protocols. The protocols studied are classified into three classes: oblivious (the transmission schedule of a node is only a function of its ID), quasi-oblivious (the transmission schedule may also depend on a global time), and adaptive. The main contributions concern negative results. Contrasting the lower and upper bounds derived, interesting complexity gaps among protocol-classes are observed. These results show that the gap in time complexity between oblivious and quasi-oblivious (hence, adaptive) protocols is almost linear. This gap is what we call the profit of global synchrony, since it represents the gain the network obtains from global synchrony with respect to not having it. We note that the global synchrony required by the efficient quasi-oblivious protocol proposed is simply achieved by piggybacking in the messages sent the time at the source node, as a global reference.

We then move to study randomized protocols. We show tight bounds on the randomized complexity of information dissemination in MANETs, for reasonable choices of α and β. We show that randomization reduces the time complexity of the problem (with respect to deterministic solutions) by a logarithmic or linear factor, depending on the class of randomized protocol considered.

Joint work with Martin Farach-Colton, Alessia Milani, Miguel A. Mosteiro, and Shmuel Zaks.