DIMACS Theoretical Computer Science Seminar


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

Speaker: Miguel Mosteiro, Rutgers University

Date: Wednesday, April 4, 2012 11:00-12:00pm

Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ


Abstract:

In this talk, we overview recent results on Information Dissemination in Mobile Ad-hoc Networks (MANETs). In MANETs, nodes are embedded in the plane, they can move with bounded speed, and communication among nodes occurs over a collision-prone single channel. The problem is to disseminate a piece of information, initially held by a source node, to all nodes in a target set. We assume a weak set of restrictions on the mobility of nodes, parameterized by the disconnection time (alpha) and the link-stability time (beta), 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 the assumptions in previous papers.

We will overview upper and lower bounds for different types of protocols, parameterized by alpha and beta. Most notably, we will show: (i) an almost linear complexity gap between oblivious and adaptive deterministic protocols that only use global time; (ii) tight bounds on the randomized complexity (for reasonable choices of alpha and beta); and (iii) that randomization reduces the time complexity by a logarithmic or linear factor, depending on the class of protocol.

Joint work with Martin Farach-Colton, Antonio Fernandez-Anta, Alessia Milani, and Shmuel Zaks.

See: http://paul.rutgers.edu/~yixinxu/theory-spring12.html