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.

    Keywords: NCCR-MICS ; NCCR-MICS/CL4


    EPFL Technical Report IC/2004/37


    • LSR-REPORT-2004-033

    Record created on 2005-05-20, modified on 2017-05-12


  • There is no available fulltext. Please contact the lab or the authors.

Related material