A Lower Bound for Broadcasting in Mobile Ad Hoc Networks

Abstract

We give a lower bound of $\\Omega(n)$ rounds for broadcasting in a mobile ad hoc network, where $n$ is the number of nodes in the network. A round is the time taken by a node to successfully transmit a message to all its neighbors. It has been shown by Bruschi et al. and Chlebus et al. that a minimum of $\\Omega(\\log n)$ time-slots are required in a round to propagate the broadcast message by one hop. In static networks, this gives us the lower bound for network-wide broadcast to be $\\Omega(D \\log n)$ time-slots, where $D$ is its diameter. Although this lower bound is valid for a mobile network, we obtain a tighter lower bound of $\\Omega(n \\log n)$ time-slots by considering explicit node mobility. This result is valid even when $D \\ll n$ and the network diameter never exceeds $D$. This shows that the dominating factor in the complexity of broadcasting in a mobile network is the number of nodes in the network and not its diameter.