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(Δ + log² 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.

REFERENCES

• 1: Noga Alon , Amotz Bar-Noy , Nathan Linial , David Peleg, A lower bound for radio broadcast, Journal of Computer and System Sciences, v.43 n.2, p.290-298, Oct. 1991 [doi>10.1016/0022-0000(91)90015-W]
• 2: 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, p.98-108, August 10-12, 1987, Vancouver, British Columbia, Canada [doi>10.1145/41840.41849]
• 3: Leonid Barenboim , Michael Elkin, Distributed (δ+1)-coloring in linear (in δ) time, Proceedings of the 41st annual ACM symposium on Theory of computing, May 31-June 02, 2009, Bethesda, MD, USA [doi>10.1145/1536414.1536432]
• 4: Artur Czumaj , Wojciech Rytter, Broadcasting Algorithms in Radio Networks with Unknown Topology, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.492, October 11-14, 2003
• 5: T. Herman and S. Tixeuil. A Distributed TDMA Slot Assignment Algorithm for Wireless Sensor Networks. In Lecture Notes in Computer Science, volume 3121/2004, 2004.
• 6: Tomasz Jurdzinski , Grzegorz Stachowiak, Probabilistic Algorithms for the Wakeup Problem in Single-Hop Radio Networks, Proceedings of the 13th International Symposium on Algorithms and Computation, p.535-549, November 21-23, 2002
• 7: S. Khot, Improved Inapproximability Results for MaxClique, Chromatic Number and Approximate Graph Coloring, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.600, October 14-17, 2001
• 8: Dariusz R. Kowalski , Andrzej Pelc, Broadcasting in undirected ad hoc radio networks, Distributed Computing, v.18 n.1, p.43-57, July 2005 [doi>10.1007/s00446-005-0126-7]
• 9: Fabian Kuhn , Tim Nieberg , Thomas Moscibroda , Roger Wattenhofer, Local approximation schemes for ad hoc and sensor networks, Proceedings of the 2005 joint workshop on Foundations of mobile computing, September 02-02, 2005, Cologne, Germany [doi>10.1145/1080810.1080827]
• 10: Fabian Kuhn , Thomas Moscibroda , Roger Wattenhofer, Initializing newly deployed ad hoc and sensor networks, Proceedings of the 10th annual international conference on Mobile computing and networking, September 26-October 01, 2004, Philadelphia, PA, USA [doi>10.1145/1023720.1023746]
• 11: 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, p.65-74, August 15-18, 1993, Ithaca, New York, United States [doi>10.1145/164051.164059]
• 12: Michael Luby, A simple parallel algorithm for the maximal independent set problem, SIAM Journal on Computing, v.15 n.4, p.1036-1055, Nov. 1986 [doi>10.1137/0215074]
• 13: Thomas Moscibroda , Roger Wattenhofer, Coloring unstructured radio networks, Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures, July 18-20, 2005, Las Vegas, Nevada, USA [doi>10.1145/1073970.1073977]
• 14: Thomas Moscibroda , Roger Wattenhofer, Maximal independent sets in radio networks, Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, July 17-20, 2005, Las Vegas, NV, USA [doi>10.1145/1073814.1073842]
• 15: Alessandro Panconesi , Romeo Rizzi, Some simple distributed algorithms for sparse networks, Distributed Computing, v.14 n.2, p.97-100, April 2001 [doi>10.1007/PL00008932]
• 16: Johannes Schneider , Roger Wattenhofer, A log-star distributed maximal independent set algorithm for growth-bounded graphs, Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing, August 18-21, 2008, Toronto, Canada [doi>10.1145/1400751.1400758]
• 17: F. A. Tobagi and L. Kleinrock. Packet Switching in Radio Channels: Part II--The Hidden Terminal Problem in Carrier Sense Multiple Access and the Busy Tone Solution. In COM-23(12), 1975.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

General Terms:
Algorithms, Theory

Keywords:
ad hoc networks, bounded independence graphs, coloring, distributed algorithms, growth bounded graphs, local algorithms, parallel algorithms, sensor networks, unit disk graphs, unstructured radio networks