2011 | OriginalPaper | Buchkapitel
Parsimonious Flooding in Geometric Random-Walks
(Extended Abstract)
verfasst von : Andrea E. F. Clementi, Riccardo Silvestri
Erschienen in: Distributed Computing
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We study the information spreading yielded by the
(Parsimonious) k-Flooding Protocol
in geometric Mobile Ad-Hoc Networks. We consider
n
agents on a square of side length
L
performing independent random walks with move radius
ρ
. At any time step, every active agent
v
informs every non-informed agent which is within distance
R
from
v
(
R
> 0 is the transmission radius). An agent is only active for the next
k
time steps following the one in which has been informed and, after that, she is removed. At the initial time step, a source agent is informed and we look at the
completion time
of the protocol, i.e., the first time step (if any) in which all agents are informed.
The presence of removed agents makes this process much more complex than the (standard) flooding and no analytical results are available over any explicit mobility model.
We prove optimal bounds on the completion time depending on the parameters
n
,
L
,
R
, and
ρ
. The obtained bounds hold with high probability. Our method of analysis provides a clear picture of the dynamic shape of the information spreading (or infection wave) over the time.