TITLE: Opportunistic Information Dissemination in Mobile Ad-hoc Networks:
The Profit of Global Synchrony
SPEAKER: Alessia Milani
Laboratoire Bordelaise de recherche en informatique (LABRI) University of Bordeaux 1
The talk will be about information dissemination in mobile ad-hoc networksusing deterministic protocols. A mobile ad-hoc network is a set of mobile nodes which communicate over a multihop radio network, without relying on a stable infrastructure. Current trends in networking-architecture developments aim to deal with the disconnections that naturally and frequently arise in wireless environments. Thus, multi-hop communication is provided through opportunistic communication, in which the online route of a message is followed one link at a time, as links in the route become available.
We formally define a class of slotted mobile ad-hoc networks suited for opportunistic communication, in which there are bounds on certain connectivity parameters resulting from movement, from failures, and from the fact that nodes may join the computation at different times. In this context, we studied three classes of protocols: oblivious (the transmission schedule of a node is only a function of its ID and its local time), adaptive (a node can also use any information from the communication history to decide its schedule), and quasi-oblivious (the transmission schedule can depend on very limited information from the communication history, namely, the number of slots since the dissemination slotted). 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 (and, 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 being able to synchronize.