Efficient Broadcasting in Known Geometric Radio Networks with Non-uniform Ranges
Författare
Redaktör
- Gadi Taubenfeld
Summary, in English
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 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(hlogψ) rounds in the conflict-embodied 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.
Avdelning/ar
- Computer Science
Publiceringsår
2008
Språk
Engelska
Sidor
274-288
Publikation/Tidskrift/Serie
Lecture Notes in Computer Science/Proceedings of the 22nd International Symposium on Distributed Computing
Volym
5218
Dokumenttyp
Konferensbidrag
Förlag
Springer
Ämne
- Computer Science
Conference name
International Symposium on Distributed Computing (DISC)
Conference date
2008-09-22 - 2008-09-24
Conference place
Arcachon, France
Status
Published
Projekt
- VR 2005-4085
ISBN/ISSN/Övrigt
- ISSN: 0302-9743
- ISSN: 1611-3349
- ISBN: 978-3-540-87778-3