[ACM Press the 28th ACM symposium - Calgary, AB, Canada (2009.08.10-2009.08.12)] Proceedings of the 28th ACM symposium on Principles of distributed computing - PODC '09 - Coloring unstructured wireless multi-hop networks

✍ Scribed by Schneider, Johannes; Wattenhofer, Roger

• Book ID: 121749221
• Publisher: ACM Press
• Year: 2009
• Tongue: English
• Weight: 508 KB
• Category: Article
• ISBN: 1605583960
• DOI: 10.1145/1582716.1582751

✦ Synopsis

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(∆ + log 2 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.