Parsimonious Flooding in Geometric Random-Walks

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.