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. Journal articles
  4. The impact of mobility on the time complexity for deterministic broadcasting in radio networks
 
research article

The impact of mobility on the time complexity for deterministic broadcasting in radio networks

Prakash, Ravi
•
Sasson, Yoav  
•
Mohsin, Mansoor
Show more
2011
International Journal Of Ad Hoc And Ubiquitous Computing

We study the time complexity for deterministic broadcasting algorithms in mobile radio networks. The broadcast operation consists of a source node successfully communicating its message to every other node. In multi-hop radio networks such as MANETs, the message may traverse multiple other nodes. Nodes have no prior knowledge besides the number n of nodes in the network and its diameter D. The problem we address has been extensively studied for static networks. Our work quantifies the impact of mobility. We consider three families of graphs: undirected graphs of constant contention degree, undirected graphs of non-constant contention degree and directed graphs of non-constant contention degree. We prove the lower bounds of Omega(n log n) time slots for the first family, Omega(n(2)/D-2 log D + D) time slots for the second and Omega(n(2)/D-2 log D + n log D) for the third. At the time of writing, the corresponding tightest lower bounds derived in the static case are, respectively, Omega(D log n), Omega(n log n log n/D) and Omega(n log D).

  • Details
  • Metrics
Type
research article
DOI
10.1504/IJAHUC.2011.042351
Web of Science ID

WOS:000296279200004

Author(s)
Prakash, Ravi
Sasson, Yoav  
Mohsin, Mansoor
Cavin, David  
Schiper, Andre  
Date Issued

2011

Published in
International Journal Of Ad Hoc And Ubiquitous Computing
Volume

8

Start page

174

End page

188

Subjects

MANETs

•

mobile ad hoc networks

•

broadcasting

•

lower bound

•

Randomization

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
LSR-IC  
Available on Infoscience
December 16, 2011
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/73398
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