Premium
Deterministic radio broadcasting at low cost
Author(s) -
Dessmark Anders,
Pelc Andrzej
Publication year - 2002
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.10016
Subject(s) - broadcasting (networking) , computer science , node (physics) , computer network , focus (optics) , wireless ad hoc network , network topology , radio networks , upper and lower bounds , distributed computing , topology (electrical circuits) , wireless network , telecommunications , wireless , mathematics , combinatorics , mathematical analysis , physics , structural engineering , optics , engineering
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. © 2002 Wiley Periodicals, Inc.