On adaptive deterministic gossiping in ad hoc radio networks
Författare
Summary, in English
We study deterministic algorithms for gossiping problem in ad hoc radio networks. The gossiping problem is a communication task in which each node of the network possesses a unique single message that is to be communicated to all other nodes in the network. The efficiency of a communication algorithm in radio networks is very often expressed in terms of: max-eccentricity D, max-indegree Δ, and size (number of nodes) n of underlying graph of connections. The max-eccentricity D of a network is the maximum of the lengths of shortest directed paths from a node u to a node v, taken over all ordered pairs (u, v) of nodes in the network. The max-indegree Δ of a network is the maximum of indegrees of its nodes.We propose a new method that leads to several improvements in deterministic gossiping. It combines communication techniques designed for both known as well as unknown ad hoc radio networks. First we show how to subsume the O(Dn)-time bound yield by the Round-Robin procedure proposing a new Õ(√Dn)-time gossiping algorithm. Our algorithm is more efficient than the known Õ(n3/2)-time gossiping algorithms [3, 6], whenever D = O(nα) and α < 1. For large values of max-eccentricity D, we give another gossiping algorithm that works in time O(DΔ3/2 log3 n) which subsumes the O(DΔ2 log3 n) upper bound presented in [4].
Avdelning/ar
- Computer Science
Publiceringsår
2002
Språk
Engelska
Sidor
689-690
Publikation/Tidskrift/Serie
Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms
Länkar
Dokumenttyp
Konferensbidrag
Förlag
Society for Industrial and Applied Mathematics
Ämne
- Computer Science
Conference name
Symposium on Discrete Algorithms, 2002
Conference date
2002-01-06 - 2002-01-08
Conference place
San Francisco, California, United States
Status
Published
ISBN/ISSN/Övrigt
- ISBN: 0-89871-513-X