A Lower Bound for Broadcasting in Mobile Ad Hoc Networks
We give a lower time complexity bound of $\Omega(n)$ for broadcasting in a mobile ad hoc network, where $n$ is the number of nodes in the network. This is a tighter lower bound over the $\Omega(D \log n)$ bound by Bruschi and Del Pinto in 1997, for a network of diameter $D$. We show that when node mobility is considered, the dominating factor in the complexity of an algorithm is the number of nodes in the network and not its diameter. We consider a synchronous model, in which time is divided into rounds. In each round a node receives messages, performs some computation, sends messages, and possibly moves to a new location.