Coloring unstructured wireless multi-hop networks

Abstract

We present a randomized coloring algorithm for the unstructured radio network model, a model comprising autonomous nodes, asynchronous wake-up, no collision detection and an unknown but geometric network topology. The current state-of-the-art coloring algorithm needs with high probability O(Δ ∙ log n) time and uses O(Δ) colors, where n and Δ are the number of nodes in the network and the maximum degree, respectively; this algorithm requires knowledge of a linear bound on n and Δ. We improve this result in three ways: Firstly, we improve the time complexity, instead of the logarithmic factor we just need a polylogarithmic additive term; more specifically, our time complexity is O(Δ + log Δ ∙ log n) given an estimate of n and Δ, and O(Δ + log2 n) without knowledge of Δ. Secondly, our vertex coloring algorithm needs Δ + 1 colors only. Thirdly, our algorithm manages to do a distance-d coloring with asymptotically optimal O(Δ) colors for a constant d.