TY - GEN
T1 - Opportunistic information dissemination in mobile Ad-hoc networks
T2 - 10th Latin American Symposiumon Theoretical Informatics, LATIN 2012
AU - Farach-Colton, Martín
AU - Fernández Anta, Antonio
AU - Milani, Alessia
AU - Mosteiro, Miguel A.
AU - Zaks, Shmuel
N1 - Funding Information:
This research was supported in part by the National Science Foundation (CCF-0937829, CCF-1114930), Comunidad de Madrid grant S2009TIC-1692, Spanish MICINN grant TIN2008–06735-C02-01.
PY - 2012
Y1 - 2012
N2 - In this paper 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. 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 the assumptions in previous papers. 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 show upper and lower bounds for different types of randomized protocols, parameterized by α and β. This problem has been extensively studied in static networks and for deterministic 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 by a logarithmic or linear factor, depending on the class of randomized protocol considered.
AB - In this paper 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. 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 the assumptions in previous papers. 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 show upper and lower bounds for different types of randomized protocols, parameterized by α and β. This problem has been extensively studied in static networks and for deterministic 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 by a logarithmic or linear factor, depending on the class of randomized protocol considered.
UR - http://www.scopus.com/inward/record.url?scp=84860806977&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84860806977&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-29344-3_26
DO - 10.1007/978-3-642-29344-3_26
M3 - Conference contribution
AN - SCOPUS:84860806977
SN - 9783642293436
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 303
EP - 314
BT - LATIN 2012
Y2 - 16 April 2012 through 20 April 2012
ER -