Abstract
We consider the SINR wireless model with uniform power. In this model the success of a transmission is determined by the ratio between the strength of the transmission signal and the noise produced by other transmitting processors plus ambient noise. The local broadcasting problem is a fundamental problem in this setting. Its goal is producing a schedule in which each processor successfully transmits a message to all its neighbors. This problem has been studied in various variants of the setting, where the best currently-known algorithm has running time \(O(\bar{\Delta} + \log^2 n)\) in n-node networks with feedback, where \(\bar{\Delta}\) is the maximum neighborhood size [9]. In the latter setting processors receive free feedback on a successful transmission. We improve this result by devising a local broadcasting algorithm with time \(O(\bar{\Delta} + \log n \log \log n)\) in networks with feedback. Our result is nearly tight in view of the lower bounds \(\Omega(\bar{\Delta})\) and Ω(logn) [13]. Our results also show that the conjecture that \(\Omega(\bar{\Delta} + \log^2 n)\) time is required for local broadcasting [9] is not true in some settings.
We also consider a closely related problem of distant-k coloring. This problem requires each pair of vertices at geometrical distance of at most k transmission ranges to obtain distinct colors. Although this problem cannot be always solved in the SINR setting, we are able to compute a solution using an optimal number of Steiner points (up to constant factors). We employ this result to devise a local broadcasting algorithm that after a preprocessing stage of \(O(\log^* n \cdot (\bar{\Delta} + \log n \log \log n))\) time obtains a local-broadcasting schedule of an optimal (up to constant factors) length \(O(\bar{\Delta})\). This improves upon previous local-broadcasting algorithms in various settings whose preprocessing time was at least \(O(\bar{\Delta} \log n\)) [3,10,5,]. Finally, we prove a surprising phenomenon regarding the influence of the path-loss exponent α on performance of algorithms. Specifically, we show that in vacuum (α = 2) any local broadcasting algorithm requires \(\Omega(\bar{\Delta} \log n)\) time, while on earth (α > 2) better results are possible as illustrated by our \(O(\bar{\Delta} + \log n \log \log n)\)-time algorithm.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Barenboim, L., Elkin, M.: Distributed Graph Coloring: Fundamentals and Recent Developments. Morgan & Claypool Synthesis Lectures on Distributed Computing Theory (2013)
Barenboim, L., Elkin, M., Pettie, S., Schneider, J.: The locality of distributed symmetry breaking. In: Proc. 53rd Symp. on Foundations of Computer Science (FOCS 2012), pp. 321–330 (2012)
Derbel, B., Talbi, E.: Distributed Node Coloring in the SINR Model. In: Proc. 30th IEEE Int. Conf. on Distributed Computing Systems (ICDCS 2010), pp. 708–717 (2010)
Fuchs, F., Prutkin, R.: Simple Distributed (Δ + 1)-coloring in the SINR model (2015), http://arxiv.org/abs/1502.02426
Fuchs, F., Wagner, D.: On Local Broadcasting Schedules and CONGEST Algorithms in the SINR Model. In: Proc. 9th Int. Workshop on Algorithmic Aspects of Wireless Sensor Networks (ALGOSENSORS 2013), pp. 170–184 (2013)
Fuchs, F., Wagner, D.: Local broadcasting with arbitrary transmission power in the SINR model. In: Halldórsson, M.M. (ed.) SIROCCO 2014. LNCS, vol. 8576, pp. 180–193. Springer, Heidelberg (2014)
Goussevskaia, O., Moscibroda, T., Wattenhofer, R.: Local Broadcasting in the Physical Interference Model. In: Proc. 5th ACM Int. Workshop on Foundations of Mobile Computing (DialM-POMC 2008), pp. 35–44 (2008)
Goussevskaia, O., Pignolet, Y., Wattenhofer, R.: Efficiency of wireless networks: Approximation algorithms for the physical interference model. Foundations and Trends in Networking 4(3), 313–420 (2010)
Halldórsson, M., Mitra, P.: Towards Tight Bounds for Local Broadcasting. In: Proc. 8th ACM Int. Workshop on Foundations of Mobile Computing (FOMC 2012), Article No 2 (2012)
Jurdzinski, T., Kowalski, D.: Distributed Backbone Structure for Algorithms in the SINR Model of Wireless Networks. In: Proc. 26th Int. Symp. on Distributed Computing (DISC 2012), pp. 106–120 (2012)
Schneider, J., Wattenhofer, R.: A Log-Star Distributed Maximal Independent Set Algorithm For Growth Bounded Graphs. In: Proc. 27th ACM Symp. on Principles of Distributed Computing (PODC 2008), pp. 35–44 (2008)
Schneider, J., Wattenhofer, R.: Coloring unstructured wireless multi-hop networks. In: Proc. 28th ACM Symp. on Principles of Distributed Computing (PODC 2009), pp. 210–219 (2009)
Yu, D., Hua, Q., Wang, Y., Lau, F.: An O(logn) Distributed Approximation Algorithm for Local Broadcasting in Unstructured Wireless Networks. In: Proc. 8th Int. Conf. on Distributed Computing in Sensor Systems (DCOSS 2012), pp. 132–139 (2012)
Yu, D., Wang, Y., Hua, Q., Lau, F.: Distributed Local Broadcasting Algorithms in the Physical Interference Model. In: Proc. 2011 Int. Conf. on Distributed Computing in Sensor Systems (DCOSS 2011), pp. 1–8 (2011)
Yu, D., Wang, Y., Hua, Q.-S., Lau, F.C.M.: Distributed (Δ + 1)-Coloring in the Physical Model. In: Erlebach, T., Nikoletseas, S., Orponen, P. (eds.) ALGOSENSORS 2011. LNCS, vol. 7111, pp. 145–160. Springer, Heidelberg (2012)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Barenboim, L., Peleg, D. (2015). Nearly Optimal Local Broadcasting in the SINR Model with Feedback. In: Scheideler, C. (eds) Structural Information and Communication Complexity. SIROCCO 2015. Lecture Notes in Computer Science(), vol 9439. Springer, Cham. https://doi.org/10.1007/978-3-319-25258-2_12
Download citation
DOI: https://doi.org/10.1007/978-3-319-25258-2_12
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-25257-5
Online ISBN: 978-3-319-25258-2
eBook Packages: Computer ScienceComputer Science (R0)