Efficient broadcasting in radio networks with long-range interference
(2013) In Distributed Computing 26(1). p.59-74- Abstract
- We study broadcasting, also known as one-to-all communication, in synchronous radio networks with known topology modeled by undirected (symmetric) graphs, where the interference range of a node is likely exceeding its transmission range. In this model, if two nodes are connected by a transmission edge they can communicate directly. On the other hand, if two nodes are connected by an interference edge they cannot communicate directly and transmission of one node disables recipience of any message at the other node. For a network we term the smallest integer , s.t., for any interference edge there exists a simple path formed of at most transmission edges connecting the endpoints of as its interference distance . In this model the schedule of... (More)
- We study broadcasting, also known as one-to-all communication, in synchronous radio networks with known topology modeled by undirected (symmetric) graphs, where the interference range of a node is likely exceeding its transmission range. In this model, if two nodes are connected by a transmission edge they can communicate directly. On the other hand, if two nodes are connected by an interference edge they cannot communicate directly and transmission of one node disables recipience of any message at the other node. For a network we term the smallest integer , s.t., for any interference edge there exists a simple path formed of at most transmission edges connecting the endpoints of as its interference distance . In this model the schedule of transmissions is precomputed in advance. It is based on the full knowledge of the size and the topology (including location of transmission and interference edges) of the network. We are interested in the design of fast broadcasting schedules that are energy efficient, i.e., based on a bounded number of transmissions executed at each node. We adopt as the number of nodes, is the diameter of the subnetwork induced by the transmission edges, and refers to the maximum combined degree (formed of transmission and interference edges) of the network. We contribute the following new results: (1) We prove that for networks with the interference distance any broadcasting schedule requires at least rounds. (2) We provide for networks modeled by bipartite graphs an algorithm that computes -shot (each node transmits at most once) broadcasting schedules of length . (3) The main result of the paper is an algorithm that computes a -shot broadcasting schedule of length at most for networks with arbitrary topology. Note that in view of the lower bound from (1) if is poly-logarithmic in this broadcast schedule is a poly-logarithmic factor away from the optimal solution. (Less)
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/3589911
- author
- Galcik, Frantisek ; Gasieniec, Leszek and Lingas, Andrzej LU
- organization
- publishing date
- 2013
- type
- Contribution to journal
- publication status
- published
- subject
- keywords
- Radio networks, Broadcasting, Long-range interference, 1-shot protocols
- in
- Distributed Computing
- volume
- 26
- issue
- 1
- pages
- 59 - 74
- publisher
- Springer
- external identifiers
-
- wos:000314532300004
- scopus:84873477459
- ISSN
- 0178-2770
- DOI
- 10.1007/s00446-012-0176-6
- language
- English
- LU publication?
- yes
- id
- 2980e469-345e-4afa-b94a-86ec22206015 (old id 3589911)
- date added to LUP
- 2016-04-01 10:50:24
- date last changed
- 2022-01-26 02:55:24
@article{2980e469-345e-4afa-b94a-86ec22206015,
abstract = {{We study broadcasting, also known as one-to-all communication, in synchronous radio networks with known topology modeled by undirected (symmetric) graphs, where the interference range of a node is likely exceeding its transmission range. In this model, if two nodes are connected by a transmission edge they can communicate directly. On the other hand, if two nodes are connected by an interference edge they cannot communicate directly and transmission of one node disables recipience of any message at the other node. For a network we term the smallest integer , s.t., for any interference edge there exists a simple path formed of at most transmission edges connecting the endpoints of as its interference distance . In this model the schedule of transmissions is precomputed in advance. It is based on the full knowledge of the size and the topology (including location of transmission and interference edges) of the network. We are interested in the design of fast broadcasting schedules that are energy efficient, i.e., based on a bounded number of transmissions executed at each node. We adopt as the number of nodes, is the diameter of the subnetwork induced by the transmission edges, and refers to the maximum combined degree (formed of transmission and interference edges) of the network. We contribute the following new results: (1) We prove that for networks with the interference distance any broadcasting schedule requires at least rounds. (2) We provide for networks modeled by bipartite graphs an algorithm that computes -shot (each node transmits at most once) broadcasting schedules of length . (3) The main result of the paper is an algorithm that computes a -shot broadcasting schedule of length at most for networks with arbitrary topology. Note that in view of the lower bound from (1) if is poly-logarithmic in this broadcast schedule is a poly-logarithmic factor away from the optimal solution.}},
author = {{Galcik, Frantisek and Gasieniec, Leszek and Lingas, Andrzej}},
issn = {{0178-2770}},
keywords = {{Radio networks; Broadcasting; Long-range interference; 1-shot protocols}},
language = {{eng}},
number = {{1}},
pages = {{59--74}},
publisher = {{Springer}},
series = {{Distributed Computing}},
title = {{Efficient broadcasting in radio networks with long-range interference}},
url = {{http://dx.doi.org/10.1007/s00446-012-0176-6}},
doi = {{10.1007/s00446-012-0176-6}},
volume = {{26}},
year = {{2013}},
}