The impact of mobility on the time complexity for deterministic broadcasting in radio networks
by Ravi Prakash, Yoav Sasson, Mansoor Mohsin, David Cavin, Andre Schiper
International Journal of Ad Hoc and Ubiquitous Computing (IJAHUC), Vol. 8, No. 3, 2011

Abstract: 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 Ω(n log n) time slots for the first family, Ω(n²/D² log D + D) time slots for the second and Ω(n²/D² 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, Ω(D log n), Ω(n log/log n / D) and Ω(n log D).

Online publication date: Mon, 05-Sep-2011

The full text of this article is only available to individual subscribers or to users at subscribing institutions.

 
Existing subscribers:
Go to Inderscience Online Journals to access the Full Text of this article.

Pay per view:
If you are not a subscriber and you just want to read the full contents of this article, buy online access here.

Complimentary Subscribers, Editors or Members of the Editorial Board of the International Journal of Ad Hoc and Ubiquitous Computing (IJAHUC):
Login with your Inderscience username and password:

Username:        Password:          Forgotten your password?

Want to subscribe?
A subscription gives you complete access to all articles in the current issue, as well as to all articles in the previous three years (where applicable). See our Orders page to subscribe.

If you still need assistance, please email subs@inderscience.com