LIPIcs.ISAAC.2020.60.pdf
- Filesize: 0.54 MB
- 15 pages
Document
The Online Broadcast Range-Assignment Problem
Authors
Mark de Berg 
,
Seeun William Umboh
-
Part of:
Volume:
31st International Symposium on Algorithms and Computation (ISAAC 2020)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Symposium on Algorithms and Computation (ISAAC) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2020-12-04
File
Document Identifiers
Author Details
Acknowledgements
We thank two anonymous referees for their comments on a previous version of this paper. In particular, we thank them for suggesting to consider 2-NN (in our previous version we analyzed 3-NN) and for the proof of Lemma 3.5.
Cite As Get BibTex
Mark de Berg, Aleksandar Markovic, and Seeun William Umboh. The Online Broadcast Range-Assignment Problem. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 60:1-60:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ISAAC.2020.60
Abstract
Let P = {p₀,…,p_{n-1}} be a set of points in ℝ^d, modeling devices in a wireless network. A range assignment assigns a range r(p_i) to each point p_i ∈ P, thus inducing a directed communication graph 𝒢_r in which there is a directed edge (p_i,p_j) iff dist(p_i, p_j) ⩽ r(p_i), where dist(p_i,p_j) denotes the distance between p_i and p_j. The range-assignment problem is to assign the transmission ranges such that 𝒢_r has a certain desirable property, while minimizing the cost of the assignment; here the cost is given by ∑_{p_i ∈ P} r(p_i)^α, for some constant α > 1 called the distance-power gradient.
We introduce the online version of the range-assignment problem, where the points p_j arrive one by one, and the range assignment has to be updated at each arrival. Following the standard in online algorithms, resources given out cannot be taken away - in our case this means that the transmission ranges will never decrease. The property we want to maintain is that 𝒢_r has a broadcast tree rooted at the first point p₀. Our results include the following.
- We prove that already in ℝ¹, a 1-competitive algorithm does not exist. In particular, for distance-power gradient α = 2 any online algorithm has competitive ratio at least 1.57.
- For points in ℝ¹ and ℝ², we analyze two natural strategies for updating the range assignment upon the arrival of a new point p_j. The strategies do not change the assignment if p_j is already within range of an existing point, otherwise they increase the range of a single point, as follows: Nearest-Neighbor (NN) increases the range of NN(p_j), the nearest neighbor of p_j, to dist(p_j, NN(p_j)), and Cheapest Increase (CI) increases the range of the point p_i for which the resulting cost increase to be able to reach the new point p_j is minimal. We give lower and upper bounds on the competitive ratio of these strategies as a function of the distance-power gradient α. We also analyze the following variant of NN in ℝ² for α = 2: 2-Nearest-Neighbor (2-NN) increases the range of NN(p_j) to 2⋅ dist(p_j,NN(p_j)),
- We generalize the problem to points in arbitrary metric spaces, where we present an O(log n)-competitive algorithm.
Subject Classification
ACM Subject Classification
- Theory of computation → Design and analysis of algorithms
Keywords
- Computational geometry
- online algorithms
- range assignment
- broadcast
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Noga Alon, Baruch Awerbuch, Yossi Azar, Niv Buchbinder, and Joseph Naor. The online set cover problem. SIAM J. Comput., 39(2):361-370, 2009. URL: https://doi.org/10.1137/060661946.
- Christoph Ambühl, Andrea E. F. Clementi, Miriam Di Ianni, Nissan Lev-Tov, Angelo Monti, David Peleg, Gianluca Rossi, and Riccardo Silvestri. Efficient algorithms for low-energy bounded-hop broadcast in ad-hoc wireless networks. In Proc. 21st Annual Symposium on Theoretical Aspects of Computer Science (STACS 2004), volume 2996 of Lecture Notes in Computer Science, pages 418-427. Springer, 2004. URL: https://doi.org/10.1007/978-3-540-24749-4_37.
- Joan Boyar, Stephan J. Eidenbenz, Lene M. Favrholdt, Michal Kotrbcík, and Kim S. Larsen. Online dominating set. Algorithmica, 81(5):1938-1964, 2019. URL: https://doi.org/10.1007/s00453-018-0519-1.
- Gruia Călinescu. Approximate min-power strong connectivity. SIAM J. Discret. Math., 27(3):1527-1543, 2013. URL: https://doi.org/10.1137/100819540.
- Andrea E. F. Clementi, Pierluigi Crescenzi, Paolo Penna, Gianluca Rossi, and Paola Vocca. On the complexity of computing minimum energy consumption broadcast subgraphs. In Proc. 18th Annual Symposium on Theoretical Aspects of Computer Science (STACS 2001), volume 2010 of Lecture Notes in Computer Science, pages 121-131. Springer, 2001. URL: https://doi.org/10.1007/3-540-44693-1_11.
-
Andrea E. F. Clementi, Gurvan Huiban, Paolo Penna, Gianluca Rossi, and Yann C. Verhoeven. Some ecent theoretical advances and open questions on energy consumption in ad-hoc wireless networks. In Proc. 3rd Workshop on Approximation and Randomization Algorithms in Communication Networks (ARACNE 2002), 2002.
- Andrea E. F. Clementi, Miriam Di Ianni, and Riccardo Silvestri. The minimum broadcast range assignment problem on linear multi-hop wireless networks. Theor. Comput. Sci., 299(1-3):751-761, 2003. URL: https://doi.org/10.1016/S0304-3975(02)00538-8.
- Andrea E. F. Clementi, Paolo Penna, Afonso Ferreira, Stephane Perennes, and Riccardo Silvestri. The minimum range assignment problem on linear radio networks. Algorithmica, 35(2):95-110, 2003. URL: https://doi.org/10.1007/s00453-002-0985-2.
- Andrea E. F. Clementi, Paolo Penna, and Riccardo Silvestri. Hardness results for the power range assignmet problem in packet radio networks. In Proc. 3rd International Workshop on Randomization and Approximation Techniques in Computer Science, and 2nd International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (RANDOM-APPROX'99), volume 1671 of Lecture Notes in Computer Science, pages 197-208. Springer, 1999. URL: https://doi.org/10.1007/978-3-540-48413-4_21.
- Andrea E. F. Clementi, Paolo Penna, and Riccardo Silvestri. On the power assignment problem in radio networks. Mob. Networks Appl., 9(2):125-140, 2004. URL: https://doi.org/10.1023/B:MONE.0000013624.32948.87.
- Bernhard Fuchs. On the hardness of range assignment problems. Networks, 52(4):183-195, 2008. URL: https://doi.org/10.1002/net.20227.
- Fabrizio Grandoni. On min-power steiner tree. In Proc. 20th Annual European Symposium on Algorithms (ESA 2012), volume 7501 of Lecture Notes in Computer Science, pages 527-538. Springer, 2012. URL: https://doi.org/10.1007/978-3-642-33090-2_46.
- Sudipto Guha and Samir Khuller. Improved methods for approximating node weighted steiner trees and connected dominating sets. Inf. Comput., 150(1):57-74, 1999. URL: https://doi.org/10.1006/inco.1998.2754.
- Lefteris M. Kirousis, Evangelos Kranakis, Danny Krizanc, and Andrzej Pelc. Power consumption in packet radio networks. Theor. Comput. Sci., 243(1-2):289-305, 2000. URL: https://doi.org/10.1016/S0304-3975(98)00223-0.
-
Kaveh Pahlavan and Allen H. Levesque. Wireless information networks, Second Edition. Wiley series in telecommunications and signal processing. Wiley-VCH, 2005.
- Daniel Dominic Sleator and Robert Endre Tarjan. Amortized efficiency of list update and paging rules. Commun. ACM, 28(2):202-208, 1985. URL: https://doi.org/10.1145/2786.2793.
- Peng-Jun Wan, Gruia Călinescu, Xiang-Yang Li, and Ophir Frieder. Minimum-energy broadcasting in static ad hoc wireless networks. Wirel. Networks, 8(6):607-617, 2002. URL: https://doi.org/10.1023/A:1020381720601.