Efficient broadcasting in known toplogy radio networks with longrange interference
(2009) In PODC '09 proceedings of the 28th ACM symposium on principles of distributed computing p.230239 Abstract
 We study broadcasting (onetoall communication) in known topology radio networks modeled by graphs, where the interference range of a node is likely to exceed 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 their transmissions disable recipience of one another. For a network G, we term the smallest integer d, s.t., for any interference edge e there exists a simple path formed of at most d transmission edges connecting the endpoints of e as its interference distance dI. In this model the schedule of transmissions is precomputed in advance based on full knowledge about the size and the topology... (More)
 We study broadcasting (onetoall communication) in known topology radio networks modeled by graphs, where the interference range of a node is likely to exceed 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 their transmissions disable recipience of one another. For a network G, we term the smallest integer d, s.t., for any interference edge e there exists a simple path formed of at most d transmission edges connecting the endpoints of e as its interference distance dI. In this model the schedule of transmissions is precomputed in advance based on full knowledge about 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 limited number of transmissions at each node.
In what follows we assume that n stands for the number of nodes, DT 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 even for networks with the interference distance dI = 2 any broadcasting schedule requires at least DT + Ω(Δ ∙ log n/log Δ) rounds.
(2) We also provide for networks modeled by bipartite graphs an algorithm that computes 1shot (each node is allowed to transmit at most once) broadcasting schedules of length O(Δ ∙ log n).
Note that in this case the length of the broadcasting schedule is independent of the interference distance of the network.
(3) The main result of the paper is an algorithm that computes a 1shot broadcasting schedule of length at most 4 ∙ DT + O(Δ ∙ dI ∙ log4 n) for networks with arbitrary topology.
Note that in view of the lower bound from (1) the broadcast schedule is almost optimal for dI polylogarithmic in n. Note also that by applying our algorithm to radio networks with no interference edges the time of the broadcasting schedule from [10] is improved in graphs with Δ = o(√n/log4 n).
The 1shot broadcasting algorithm proposed in [10] relies heavily on the concept of internal ranks that impose currently an Ω(√n)time bottleneck in the broadcasting schedule. (Less)
Please use this url to cite or link to this publication:
http://lup.lub.lu.se/record/1670319
 author
 Galcík, Frantisek; Gasieniec, Leszek and Lingas, Andrzej ^{LU}
 organization
 publishing date
 2009
 type
 Chapter in Book/Report/Conference proceeding
 publication status
 published
 subject
 in
 PODC '09 proceedings of the 28th ACM symposium on principles of distributed computing
 pages
 230  239
 external identifiers

 scopus:70350655923
 ISBN
 9781605583969
 DOI
 10.1145/1582716.1582754
 project
 VR 20084649
 language
 English
 LU publication?
 yes
 id
 c2ad4a2743834662870b2107bc2caf4e (old id 1670319)
 date added to LUP
 20100913 13:41:27
 date last changed
 20170101 08:15:58
@inproceedings{c2ad4a2743834662870b2107bc2caf4e, abstract = {We study broadcasting (onetoall communication) in known topology radio networks modeled by graphs, where the interference range of a node is likely to exceed 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 their transmissions disable recipience of one another. For a network G, we term the smallest integer d, s.t., for any interference edge e there exists a simple path formed of at most d transmission edges connecting the endpoints of e as its interference distance dI. In this model the schedule of transmissions is precomputed in advance based on full knowledge about 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 limited number of transmissions at each node.<br/><br> <br/><br> In what follows we assume that n stands for the number of nodes, DT 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:<br/><br> <br/><br> (1) We prove that even for networks with the interference distance dI = 2 any broadcasting schedule requires at least DT + Ω(Δ ∙ log n/log Δ) rounds.<br/><br> <br/><br> (2) We also provide for networks modeled by bipartite graphs an algorithm that computes 1shot (each node is allowed to transmit at most once) broadcasting schedules of length O(Δ ∙ log n).<br/><br> <br/><br> Note that in this case the length of the broadcasting schedule is independent of the interference distance of the network.<br/><br> <br/><br> (3) The main result of the paper is an algorithm that computes a 1shot broadcasting schedule of length at most 4 ∙ DT + O(Δ ∙ dI ∙ log4 n) for networks with arbitrary topology.<br/><br> <br/><br> Note that in view of the lower bound from (1) the broadcast schedule is almost optimal for dI polylogarithmic in n. Note also that by applying our algorithm to radio networks with no interference edges the time of the broadcasting schedule from [10] is improved in graphs with Δ = o(√n/log4 n).<br/><br> <br/><br> The 1shot broadcasting algorithm proposed in [10] relies heavily on the concept of internal ranks that impose currently an Ω(√n)time bottleneck in the broadcasting schedule.}, author = {Galcík, Frantisek and Gasieniec, Leszek and Lingas, Andrzej}, booktitle = {PODC '09 proceedings of the 28th ACM symposium on principles of distributed computing}, isbn = {9781605583969}, language = {eng}, pages = {230239}, title = {Efficient broadcasting in known toplogy radio networks with longrange interference}, url = {http://dx.doi.org/10.1145/1582716.1582754}, year = {2009}, }