Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

On adaptive deterministic gossiping in ad hoc radio networks

Gasieniec, Leszek and Lingas, Andrzej LU (2002) Symposium on Discrete Algorithms, 2002 p.689-690
Abstract
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... (More)
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]. (Less)
Please use this url to cite or link to this publication:
author
and
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
host publication
Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms
pages
689 - 690
publisher
Society for Industrial and Applied Mathematics
conference name
Symposium on Discrete Algorithms, 2002
conference location
San Francisco, California, United States
conference dates
2002-01-06 - 2002-01-08
external identifiers
  • scopus:0037205804
ISBN
0-89871-513-X
language
English
LU publication?
yes
id
44dedb69-7d3f-4dee-86b4-ee1870b89fe7 (old id 631639)
alternative location
http://portal.acm.org/citation.cfm?id=545473&coll=GUIDE&dl=GUIDE&CFID=44876763&CFTOKEN=37550423
date added to LUP
2016-04-04 10:12:50
date last changed
2022-01-29 19:59:05
@inproceedings{44dedb69-7d3f-4dee-86b4-ee1870b89fe7,
  abstract     = {{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 α &lt; 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].}},
  author       = {{Gasieniec, Leszek and Lingas, Andrzej}},
  booktitle    = {{Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms}},
  isbn         = {{0-89871-513-X}},
  language     = {{eng}},
  pages        = {{689--690}},
  publisher    = {{Society for Industrial and Applied Mathematics}},
  title        = {{On adaptive deterministic gossiping in ad hoc radio networks}},
  url          = {{http://portal.acm.org/citation.cfm?id=545473&coll=GUIDE&dl=GUIDE&CFID=44876763&CFTOKEN=37550423}},
  year         = {{2002}},
}