170803
20180913060917.0
10.1504/IJAHUC.2011.042351
doi
000296279200004
ISI
ARTICLE
The impact of mobility on the time complexity for deterministic broadcasting in radio networks
2011
2011
Journal Articles
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).
MANETs
mobile ad hoc networks
broadcasting
lower bound
Randomization
Prakash, Ravi
Sasson, Yoav
103545
241626
Mohsin, Mansoor
Cavin, David
111415
241625
Schiper, Andre
106377
241767
174-188
International Journal Of Ad Hoc And Ubiquitous Computing
8
LSR
252206
U10411
oai:infoscience.tind.io:170803
article
IC
106377
EPFL-ARTICLE-170803
EPFL
PUBLISHED
REVIEWED
ARTICLE