Abstract
In wireless ad hoc networks, distributed node coloring is a fundamental problem closely related to establishing efficient communication through TDMA schedules. For networks with maximum degree Δ, a Δ + 1 coloring is the ultimate goal in the distributed setting as this is always possible. In this work we propose a very simple 4Δ coloring along with a color reduction technique to achieve Δ + 1 colors. All algorithms have a runtime of \(\mathcal{O}(\Delta \log n)\) time slots. This improves on previous algorithms for the SINR model either in terms of the number of required colors or the runtime, and matches the runtime of local broadcasting in the SINR model (which can be seen as an asymptotical lower bound).
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Bardwell, J.: Converting signal strength percentage to dbm values. WildPackets’ White Paper (2002)
Barenboim, L., Elkin, M.: Distributed Graph Coloring: Fundamentals and Recent Developments. Synthesis Lectures on Distributed Computing Theory. Morgan & Claypool Publishers (2013)
Derbel, B., Talbi, E.G.: Distributed Node Coloring in the SINR Model. In: Proc. 30th Internat. Conf. on Distributed Computing Systems (ICDCS 2010). pp. 708–717. IEEE (2010)
Distributed Computing Group, ETH Zurich: Sinalgo - simulator for network algorithms (2008), http://sourceforge.net/projects/sinalgo/ , version 0.75.3
Fuchs, F.: On asynchronous node coloring in the SINR model (2015), http://i11www.iti.kit.edu/f-oancs-15.pdf (unpublished manuscript)
Fuchs, F., Prutkin, R.: Simple distributed delta + 1 coloring in the SINR model. CoRR abs/1502.02426 (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 Internat. Workshop on Algorithmic Aspects of WSN (ALGOSENSORS 2013). pp. 170–184. Springer (2013)
Fuchs, F., Wagner, D.: Local broadcasting with arbitrary transmission power in the SINR model. In: Proc. 21st Internat. Colloq. Structural Inform. and Comm. Complexity (SIROCCO 2014), pp. 180–193. Springer (2014)
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co. (1979)
Goussevskaia, O., Moscibroda, T., Wattenhofer, R.: Local Broadcasting in the Physical Interference Model. In: Proc. 5th ACM Internat. Workshop on Foundations of Mobile Computing (DialM-POMC 2008), pp. 35–44. ACM (2008)
Goussevskaia, O., Pignolet, Y.A., Wattenhofer, R.: Efficiency of wireless networks: Approximation algorithms for the physical interference model. Foundations and Trends in Networking 4(3) (November 2010)
Gupta, P., Kumar, P.R.: The capacity of wireless networks. IEEE Trans. on Inform. Theory 46(2), 388–404 (2000)
Halldórsson, M.M., Mitra, P.: Towards Tight Bounds for Local Broadcasting. In: Proc. 8th ACM Internat. Workshop on Foundations of Mobile Computing (FOMC 2012). ACM (2012)
Moscibroda, T., Wattenhofer, M.: Coloring Unstructured Radio Networks. J. Distr. Comp. 21(4), 271–284 (2008)
Moscibroda, T., Wattenhofer, R., Weber, Y.: Protocol design beyond graph-based models. In: Proc. of the ACM Workshop on Hot Topics in Networks (HotNets-V), pp. 25–30 (2006)
Roberts, L.G.: Aloha packet system with and without slots and capture. SIGCOMM Comput. Commun. Rev. 5(2), 28–42 (1975)
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. ACM (2009)
Yu, D., Hua, Q.S., Wang, Y., Lau, F.C.M.: An O(logn) Distributed Approximation Algorithm for Local Broadcasting in Unstructured Wireless Networks. In: Proc. 8th Internat. Conf. on Distributed Computing in Sensor Systems (DCOSS 2012), pp. 132–139. IEEE (2012)
Yu, D., Wang, Y., Hua, Q.S., Lau, F.C.M.: Distributed (Δ + 1) Coloring in the Physical Model. Theoret. Comput. Sci. 553, 37–56 (2014)
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
Fuchs, F., Prutkin, R. (2015). Simple Distributed Δ + 1 Coloring in the SINR Model. 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_11
Download citation
DOI: https://doi.org/10.1007/978-3-319-25258-2_11
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)