Deterministic radio broadcasting at low cost
(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:
https://lup.lub.lu.se/record/341969
- author
- Dessmark, Anders LU and Pelc, A
- organization
- publishing date
- 2002
- 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 Inc.
- 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
- 2016-04-01 15:42:17
- date last changed
- 2022-01-28 06:38:33
@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}},
keywords = {{time; radio network; distributed; broadcasting; cost}},
language = {{eng}},
number = {{2}},
pages = {{88--97}},
publisher = {{John Wiley & Sons Inc.}},
series = {{Networks}},
title = {{Deterministic radio broadcasting at low cost}},
url = {{http://dx.doi.org/10.1002/net.10016}},
doi = {{10.1002/net.10016}},
volume = {{39}},
year = {{2002}},
}