The browser you are using is not supported by this website. All versions of Internet Explorer are no longer supported, either by us or Microsoft (read more here: https://www.microsoft.com/en-us/microsoft-365/windows/end-of-ie-support).

Please use a modern browser to fully experience our website, such as the newest versions of Edge, Chrome, Firefox or Safari etc.

On adaptive deterministic gossiping in ad hoc radio networks

På svenska

Author

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].

Department/s

  • Computer Science

Publishing year

2002

Language

English

Pages

689-690

Publication/Series

Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms

Document type

Conference paper

Publisher

Society for Industrial and Applied Mathematics

Topic

  • 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/Other

  • ISBN: 0-89871-513-X