TY - GEN
T1 - Efficient broadcasting in known geometric radio networks with non-uniform ranges
AU - Ga̧sieniec, Leszek
AU - Kowalski, Dariusz R.
AU - Lingas, Andrzej
AU - Wahlen, Martin
N1 - Funding Information:
Research supported in part by VR grant 621-2005-4085 and The Royal Society International Joint Project, IJP - 2006/R2.
PY - 2008
Y1 - 2008
N2 - 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 (R2) and each of them can transmit within some range r assigned to it. We adopt model in which ranges of nodes are non-uniform and they are drawn from the predefined interval 0 ≤ rmin ≤rmax. All our results are in the conflict-embodied 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 rmin , ..., rmax, we show that broadcasting requires D + Ω(min{log rmax/rmin, log (n -D)}) rounds and that it can be accomplished in O(D log2 rmax/rmin rounds subsuming the best currently known upper bound O(D(rmax/rmin)4) 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 conflict-free model may require up to h/2 additional rounds in the conflict-embodied model. This lower bound should be seen as a separation result between conflict-free and conflict-embodied geometric radio networks. Finally, we also prove that any h-hop broadcasting algorithm with the energy consumption ε in a GRN can be simulated within O(h log ψ) rounds in the conflict-embodied model using energy O(ε), where ψ is the ratio between the largest and the shortest Euclidean distance between a pair of nodes in the network.
AB - 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 (R2) and each of them can transmit within some range r assigned to it. We adopt model in which ranges of nodes are non-uniform and they are drawn from the predefined interval 0 ≤ rmin ≤rmax. All our results are in the conflict-embodied 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 rmin , ..., rmax, we show that broadcasting requires D + Ω(min{log rmax/rmin, log (n -D)}) rounds and that it can be accomplished in O(D log2 rmax/rmin rounds subsuming the best currently known upper bound O(D(rmax/rmin)4) 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 conflict-free model may require up to h/2 additional rounds in the conflict-embodied model. This lower bound should be seen as a separation result between conflict-free and conflict-embodied geometric radio networks. Finally, we also prove that any h-hop broadcasting algorithm with the energy consumption ε in a GRN can be simulated within O(h log ψ) rounds in the conflict-embodied model using energy O(ε), where ψ is the ratio between the largest and the shortest Euclidean distance between a pair of nodes in the network.
UR - http://www.scopus.com/inward/record.url?scp=56449096257&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=56449096257&partnerID=8YFLogxK
U2 - 10.1007/978-3-540-87779-0_19
DO - 10.1007/978-3-540-87779-0_19
M3 - Conference contribution
AN - SCOPUS:56449096257
SN - 3540877789
SN - 9783540877783
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 274
EP - 288
BT - Distributed Computing - 22nd International Symposium, DISC 2008, Proceedings
T2 - 22nd International Symposium on Distributed Computing, DISC 2008
Y2 - 22 September 2008 through 24 September 2008
ER -