Computer Science – Distributed – Parallel – and Cluster Computing
Scientific paper
2011-08-30
Computer Science
Distributed, Parallel, and Cluster Computing
19 pages
Scientific paper
We consider the problems of deterministic broadcasting and gossiping in completely unknown ad-hoc radio networks. We assume that nothing is known to the nodes about the topology or even the size of the network, $n$, except that $n > 1$. Protocols for vanilla model, when $n$ is known, may be run for increasingly larger estimates $2^i$ on the size of the network, but one cannot determine when such a protocol should terminate. Thus, to carry this design paradigm, successful completion or in-completion of the process should be detected, and this knowledge circulated in the network. We consider the problem of deterministic Acknowledged Broadcasting and Gossiping when nodes can take polynomially large labels. For the above setting, we present the following results for strongly connected networks: (a) A deterministic protocol for acknowledged broadcasting which takes $NRG(n,n^c)$ rounds, where $NRG(n,n^c)$ is the round complexity of deterministic gossiping for vanilla model. (b) A deterministic protocol for acknowledged gossiping, which takes $O(n^2 \lg n)$ rounds when collision detection mechanism is available. The structure of the transmissions of nodes in the network, to enable them to infer collisions, and discover existence of unknown in-neighborhood as a result, is abstracted as a family of integral sets called Selecting-Colliding family. We prove the existence of Selecting-Colliding families using the probabilistic method and employ them to design protocol for acknowledged gossiping when no collision detection mechanism is available. Finally, we present a deterministic protocol for acknowledged broadcasting for bidirectional networks, with a round complexity of $O(n \lg n)$ rounds.
No associations
LandOfFree
Information Dissemination in Unknown Radio networks with Large Labels does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Information Dissemination in Unknown Radio networks with Large Labels, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Information Dissemination in Unknown Radio networks with Large Labels will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-728899