Coloring unstructured wireless multi-hop networks
作者： Johannes Schneider , Roger Wattenhofer
关键词: Parallel algorithm 、 Collision detection 、 Binary logarithm 、 Time complexity 、 Geometric networks 、 Asymptotically optimal algorithm 、 Wireless ad hoc network 、 Combinatorics 、 Distributed algorithm 、 Mathematics
摘要: We present a randomized coloring algorithm for the unstructured radio network model, model comprising autonomous nodes, asynchronous wake-up, no collision detection and an unknown but geometric topology. The current state-of-the-art needs with high probability O(Δ ∙ log n) time uses O(Δ) colors, where n Δ are number of nodes in maximum degree, respectively; this requires knowledge linear bound on Δ. improve result three ways: Firstly, we complexity, instead logarithmic factor just need polylogarithmic additive term; more specifically, our complexity is + given estimate Δ, log2n) without Secondly, vertex 1 colors only. Thirdly, manages to do distance-d asymptotically optimal constant d.
core.ac.uk
acm.org
sci-hub.se 参考文章(18)
Michael Elkin, Leonid Barenboim, Distributed (delta+1)-coloring in linear (in delta) time. symposium on the theory of computing. pp. 111- 120 ,(2009)
Tomasz Jurdziński, Grzegorz Stachowiak, Probabilistic Algorithms for the Wakeup Problem in Single-Hop Radio Networks Algorithms and Computation. pp. 535- 549 ,(2002) , 10.1007/3-540-36136-7_47
Ted Herman, Sébastien Tixeuil, A Distributed TDMA Slot Assignment Algorithm for Wireless Sensor Networks Algorithmic Aspects of Wireless Sensor Networks. pp. 45- 58 ,(2004) , 10.1007/978-3-540-27820-7_6
Johannes Schneider, Roger Wattenhofer, A log-star distributed maximal independent set algorithm for growth-bounded graphs principles of distributed computing. pp. 35- 44 ,(2008) , 10.1145/1400751.1400758
Eyal Kushilevitz, Yishay Mansour, An Ω(D log(N/D)) lower bound for broadcast in radio networks Proceedings of the twelfth annual ACM symposium on Principles of distributed computing - PODC '93. pp. 65- 74 ,(1993) , 10.1145/164051.164059
Alessandro Panconesi, Romeo Rizzi, Some simple distributed algorithms for sparse networks Distributed Computing. ,vol. 14, pp. 97- 100 ,(2001) , 10.1007/PL00008932
Barenboim Leonid, Elkin Michael, Kuhn Fabian, Distributed (δ+1)-coloring in linear (in δ) time Proceedings of the 41st annual ACM symposium on Symposium on theory of computing - STOC '09. pp. 111- 120 ,(2009) , 10.1145/1536414.1536432
Reuven Bar-Yehuda, Oded Goldreich, Alon Itai, On the time-complexity of broadcast in radio networks: an exponential gap between determinism randomization Proceedings of the sixth annual ACM Symposium on Principles of distributed computing - PODC '87. pp. 98- 108 ,(1987) , 10.1145/41840.41849
Noga Alon, Amotz Bar-Noy, Nathan Linial, David Peleg, A lower bound for radio broadcast Journal of Computer and System Sciences. ,vol. 43, pp. 290- 298 ,(1991) , 10.1016/0022-0000(91)90015-W
A. Czumaj, W. Rytter, Broadcasting algorithms in radio networks with unknown topology foundations of computer science. pp. 492- 501 ,(2003) , 10.1109/SFCS.2003.1238222