Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Reports, Documentation, and Standards
  4. A Lower Bound for Broadcasting in Mobile Ad Hoc Networks
 
report

A Lower Bound for Broadcasting in Mobile Ad Hoc Networks

Prakash, Ravi
•
Schiper, André  
•
Mohsin, Mansoor
Show more
2004

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.

  • Files
  • Details
  • Metrics
Loading...
Thumbnail Image
Name

IC_TECH_REPORT_200437.pdf

Access type

openaccess

Size

142.3 KB

Format

Adobe PDF

Checksum (MD5)

03c94c1e88895f0ca0e2e9efea9d9b53

Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés