Efficient Broadcasting in Known Geometric Radio Networks with Nonuniform Ranges
(2008) International Symposium on Distributed Computing (DISC) In Lecture Notes in Computer Science/Proceedings of the 22nd International Symposium on Distributed Computing 5218. p.274288 Abstract
 We study here deterministic broadcasting in geometric radio networks (GRN) whose nodes have complete knowledge of the network. Nodes of a GRN are deployed in the Euclidean plane (R 2) and each of them can transmit within some range r assigned to it. We adopt model in which ranges of nodes are nonuniform and they are drawn from the predefined interval 0 ≤ r min ≤ r max . All our results are in the conflictembodied model where a receiving node must be in the range of exactly one transmitting node in order to receive the message.
We derive several lower and upper bounds on the time of deterministic broadcasting in GRNs in terms of the number of nodes n, a distribution of nodes ranges, and the eccentricity D of the source node... (More)  We study here deterministic broadcasting in geometric radio networks (GRN) whose nodes have complete knowledge of the network. Nodes of a GRN are deployed in the Euclidean plane (R 2) and each of them can transmit within some range r assigned to it. We adopt model in which ranges of nodes are nonuniform and they are drawn from the predefined interval 0 ≤ r min ≤ r max . All our results are in the conflictembodied model where a receiving node must be in the range of exactly one transmitting node in order to receive the message.
We derive several lower and upper bounds on the time of deterministic broadcasting in GRNs in terms of the number of nodes n, a distribution of nodes ranges, and the eccentricity D of the source node (i.e., the maximum length of a shortest directed path from the source node to another node in the network). In particular:
(1) We show that D + Ω(log(n − D)) rounds are required to accomplish broadcasting in some GRN where each node has the transmission range set either to 1 or to 0. We also prove that the bound D + Ω(log(n − D)) is almost tight providing a broadcasting procedure that works in this type of GRN in time D + O(logn).
(2) In GRNs with a wider choice of positive node ranges from r min , ...,r max , we show that broadcasting requires rounds and that it can be accomplished in rounds subsuming the best currently known upper bound provided in [15].
(3) We also study the problem of simulation of minimum energy broadcasting in arbitrary GRNs. We show that energy optimal broadcasting that can be completed in h rounds in a conflictfree model may require up to h/2 additional rounds in the conflictembodied model. This lower bound should be seen as a separation result between conflictfree and conflictembodied geometric radio networks. Finally, we also prove that any hhop broadcasting algorithm with the energy consumption in a GRN can be simulated within O(hlogψ) rounds in the conflictembodied model using energy O(cal E), where ψ is the ratio between the largest and the shortest Euclidean distance between a pair of nodes in the network. (Less)
Please use this url to cite or link to this publication:
http://lup.lub.lu.se/record/1288735
 author
 Gasieniec, Leszek; Kowalski, Dariusz; Lingas, Andrzej ^{LU} and Wahlén, Martin ^{LU}
 organization
 publishing date
 2008
 type
 Chapter in Book/Report/Conference proceeding
 publication status
 published
 subject
 in
 Lecture Notes in Computer Science/Proceedings of the 22nd International Symposium on Distributed Computing
 editor
 Taubenfeld, Gadi and
 volume
 5218
 pages
 274  288
 publisher
 Springer
 conference name
 International Symposium on Distributed Computing (DISC)
 external identifiers

 scopus:56449096257
 ISSN
 16113349
 03029743
 ISBN
 9783540877783
 DOI
 10.1007/9783540877790_19
 project
 VR 20054085
 language
 English
 LU publication?
 yes
 id
 fe01d91f4025427785484eba5f9fb40e (old id 1288735)
 date added to LUP
 20090203 10:17:17
 date last changed
 20170305 03:39:19
@inproceedings{fe01d91f4025427785484eba5f9fb40e, abstract = {We study here deterministic broadcasting in geometric radio networks (GRN) whose nodes have complete knowledge of the network. Nodes of a GRN are deployed in the Euclidean plane (R 2) and each of them can transmit within some range r assigned to it. We adopt model in which ranges of nodes are nonuniform and they are drawn from the predefined interval 0 ≤ r min ≤ r max . All our results are in the conflictembodied model where a receiving node must be in the range of exactly one transmitting node in order to receive the message.<br/><br> We derive several lower and upper bounds on the time of deterministic broadcasting in GRNs in terms of the number of nodes n, a distribution of nodes ranges, and the eccentricity D of the source node (i.e., the maximum length of a shortest directed path from the source node to another node in the network). In particular:<br/><br> (1) We show that D + Ω(log(n − D)) rounds are required to accomplish broadcasting in some GRN where each node has the transmission range set either to 1 or to 0. We also prove that the bound D + Ω(log(n − D)) is almost tight providing a broadcasting procedure that works in this type of GRN in time D + O(logn).<br/><br> (2) In GRNs with a wider choice of positive node ranges from r min , ...,r max , we show that broadcasting requires rounds and that it can be accomplished in rounds subsuming the best currently known upper bound provided in [15].<br/><br> (3) We also study the problem of simulation of minimum energy broadcasting in arbitrary GRNs. We show that energy optimal broadcasting that can be completed in h rounds in a conflictfree model may require up to h/2 additional rounds in the conflictembodied model. This lower bound should be seen as a separation result between conflictfree and conflictembodied geometric radio networks. Finally, we also prove that any hhop broadcasting algorithm with the energy consumption in a GRN can be simulated within O(hlogψ) rounds in the conflictembodied model using energy O(cal E), where ψ is the ratio between the largest and the shortest Euclidean distance between a pair of nodes in the network.}, author = {Gasieniec, Leszek and Kowalski, Dariusz and Lingas, Andrzej and Wahlén, Martin}, booktitle = {Lecture Notes in Computer Science/Proceedings of the 22nd International Symposium on Distributed Computing}, editor = {Taubenfeld, Gadi}, isbn = {9783540877783}, issn = {16113349}, language = {eng}, pages = {274288}, publisher = {Springer}, title = {Efficient Broadcasting in Known Geometric Radio Networks with Nonuniform Ranges}, url = {http://dx.doi.org/10.1007/9783540877790_19}, volume = {5218}, year = {2008}, }