Fast flooding over Manhattan

We consider a Mobile Ad-hoc NETwork (MANET) formed by n agents that move at speed v according to the Manhattan Random-Waypoint model over a square region of side length L. This model has stationary properties that strongly depart from the well-studied Random-Walk model and that are typical in scenarios of vehicular traffic in urban zones. For instance, the resulting stationary (agent) spatial probability distribution is far to be uniform: the average density over the "central zone" is asymptotically higher than that over the "Suburb". Agents exchange data if and only if they are at (Euclidean) distance at most R within each other. We study the flooding time of this MANET: the number of time steps required to broadcast a message from one source agent to all agents of the network in the stationary phase. We prove the first asymptotical upper bound on the flooding time. This bound holds with high probability, it is a decreasing function of R and v, and it is tight for a wide and relevant range of the network parameters (i.e. L, R and v). A consequence of our result is that flooding over the sparse and highly-disconnected Suburb can be as fast as flooding over the dense and connected central zone. This property holds even when R is exponentially below the connectivity threshold of the MANET and the speed v is very low. © 2012 Springer-Verlag Berlin Heidelberg.