Advanced

Deterministic radio broadcasting at low cost

Dessmark, Anders LU and Pelc, A (2002) In Networks 39(2). p.88-97
Abstract
We consider distributed deterministic broadcasting in synchronous radio networks. A node receives a message in a given round if and only if exactly one of its neighbors transmits. The source message has to reach all nodes. We assume that nodes do not know the network topology or even their immediate neighborhood. (Such networks are called ad hoc.) We are concerned with two efficiency measures of broadcasting algorithms: their execution time (number of rounds) and their cost (number of transmissions). We focus our study on the execution time of algorithms which have cost close to minimum. We consider two scenarios depending on whether nodes know or do not know global parameters of the network: the number n of nodes and the eccentricity D of... (More)
We consider distributed deterministic broadcasting in synchronous radio networks. A node receives a message in a given round if and only if exactly one of its neighbors transmits. The source message has to reach all nodes. We assume that nodes do not know the network topology or even their immediate neighborhood. (Such networks are called ad hoc.) We are concerned with two efficiency measures of broadcasting algorithms: their execution time (number of rounds) and their cost (number of transmissions). We focus our study on the execution time of algorithms which have cost close to minimum. We consider two scenarios depending on whether nodes know or do not know global parameters of the network: the number n of nodes and the eccentricity D of the source. Our main contribution Is proving tight lower bounds on the time of low-cost broadcasting which show sharp differences between these scenarios. In each case, we also give broadcasting algorithms whose performance matches these lower bounds. (C) 2002 Wiley Periodicals, Inc. (Less)
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Contribution to journal
publication status
published
subject
keywords
time, radio network, distributed, broadcasting, cost
in
Networks
volume
39
issue
2
pages
88 - 97
publisher
John Wiley & Sons
external identifiers
  • wos:000174342200005
  • scopus:0141540718
ISSN
1097-0037
DOI
10.1002/net.10016
language
English
LU publication?
yes
id
cb66a167-6110-497c-b5d8-db42917ca937 (old id 341969)
date added to LUP
2007-08-16 08:48:17
date last changed
2017-01-01 06:44:59
@article{cb66a167-6110-497c-b5d8-db42917ca937,
  abstract     = {We consider distributed deterministic broadcasting in synchronous radio networks. A node receives a message in a given round if and only if exactly one of its neighbors transmits. The source message has to reach all nodes. We assume that nodes do not know the network topology or even their immediate neighborhood. (Such networks are called ad hoc.) We are concerned with two efficiency measures of broadcasting algorithms: their execution time (number of rounds) and their cost (number of transmissions). We focus our study on the execution time of algorithms which have cost close to minimum. We consider two scenarios depending on whether nodes know or do not know global parameters of the network: the number n of nodes and the eccentricity D of the source. Our main contribution Is proving tight lower bounds on the time of low-cost broadcasting which show sharp differences between these scenarios. In each case, we also give broadcasting algorithms whose performance matches these lower bounds. (C) 2002 Wiley Periodicals, Inc.},
  author       = {Dessmark, Anders and Pelc, A},
  issn         = {1097-0037},
  keyword      = {time,radio network,distributed,broadcasting,cost},
  language     = {eng},
  number       = {2},
  pages        = {88--97},
  publisher    = {John Wiley & Sons},
  series       = {Networks},
  title        = {Deterministic radio broadcasting at low cost},
  url          = {http://dx.doi.org/10.1002/net.10016},
  volume       = {39},
  year         = {2002},
}