research-article

Coloring unstructured wireless multi-hop networks

Authors:

Johannes Schneider,

Roger WattenhoferAuthors Info & Claims

PODC '09: Proceedings of the 28th ACM symposium on Principles of distributed computing

Pages 210 - 219

https://doi.org/10.1145/1582716.1582751

Published: 10 August 2009 Publication History

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]

N. Alon, A. Bar-Noy, N. Linial, and D. Peleg. A lower bound for radio broadcast. In Journal of Computer and System Sciences, pages 290--298, 1991.

Digital Library

[2]

R. Bar-Yehuda, O. Goldreich, and A. Itai. On the Time-Complexity of Broadcast in Radio Networks: an Exponential Gap between Determinism and Randomization. In 6th Symp. on PODC, 1987.

Digital Library

[3]

L. Barenboim and M. Elkin. Distributed (delta+1)-coloring in linear (in delta) time. In 41st STOC, 2009.

Digital Library

[4]

A. Czumaj and W. Rytter. Broadcasting algorithms in radio networks with unknown topology. In 44th Symp. on FOCS, 2003.

Digital Library

[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]

T. Jurdzi&#324;ski and G. Stachowiak. Probabilistic Algorithms for the Wakeup Problem in Single-Hop Radio Networks. In 13th ISAAC, 2002.

Digital Library

[7]

S. Khot. Improved Inapproximability Results for MaxClique, Chromatic Number and Approximate Graph Coloring. In 42nd Symp. on FOCS, 2001.

Digital Library

[8]

D. R. Kowalski and A. Pelc. Broadcasting in undirected ad hoc radio networks. In Distributed Computing, volume 18, pages 43--57, 2005.

Digital Library

[9]

F. Kuhn, T. Moscibroda, T. Nieberg, and R. Wattenhofer. Local Approximation Schemes for Ad Hoc and Sensor Networks. In 3rd Workshop DIALM-POMC, 2005.

Digital Library

[10]

F. Kuhn, T. Moscibroda, and R. Wattenhofer. Initializing newly deployed ad hoc and sensor networks. In 10th Conf. on MOBICOM, 2004.

Digital Library

[11]

E. Kushilevitz and Y. Mansour. An &#937;(D &#8729; log(N/D)) lower bound for broadcast in radio networks. In 12th Symp. on PODC, 1993.

Digital Library

[12]

M. Luby. A Simple Parallel Algorithm for the Maximal Independent Set Problem. SIAM Journal on Computing, 15, 1986.

Digital Library

[13]

T. Moscibroda and R. Wattenhofer. Coloring Unstructured Radio Networks. In 17th SPAA, 2005.

Digital Library

[14]

T. Moscibroda and R. Wattenhofer. Maximal Independent Sets in Radio Networks. In 24th Symp. on PODC, 2005.

Digital Library

[15]

A. Panconesi and R. Rizzi. Some Simple Distributed Algorithms for Sparse Networks. In Distributed Computing, 14(2), pages 97--100, 2001.

Digital Library

[16]

J. Schneider and R. Wattenhofer. A Log-Star Distributed Maximal Independent Set Algorithm for Growth-Bounded Graphs. In 27th Symp. on PODC, 2008.

Digital Library

[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.

Cited By

Yang LZou YYu DYu J(2023)Distributed Age-of-Information optimization in edge computing for Internet of VehiclesJournal of Systems Architecture10.1016/j.sysarc.2023.103000144(103000)Online publication date: Nov-2023
https://doi.org/10.1016/j.sysarc.2023.103000
Barenboim LOren G(2022)Distributed backup placementDistributed Computing10.1007/s00446-022-00423-z35:5(455-473)Online publication date: 24-Mar-2022
https://doi.org/10.1007/s00446-022-00423-z
Yu DZou YWang YYu JCheng XLau F(2021)Implementing the Abstract MAC Layer via Inductive Coloring Under the Rayleigh-Fading ModelIEEE Transactions on Wireless Communications10.1109/TWC.2021.307223620:9(6167-6178)Online publication date: Sep-2021
https://doi.org/10.1109/TWC.2021.3072236
Show More Cited By

Index Terms

Coloring unstructured wireless multi-hop networks
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Graph algorithms
2. Theory of computation
  1. Randomness, geometry and discrete structures

Recommendations

A log-star distributed maximal independent set algorithm for growth-bounded graphs
PODC '08: Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing

We present a novel distributed algorithm for the maximal independent set (MIS) problem. On growth-bounded graphs (GBG) our deterministic algorithm finishes in O(log* n) time, n being the number of nodes. In light of Linial's Ω(log* n) lower bound our ...
Distributed (δ+1)-coloring in linear (in δ) time
STOC '09: Proceedings of the forty-first annual ACM symposium on Theory of computing

The distributed (Δ + 1)-coloring problem is one of most fundamental and well-studied problems in Distributed Algorithms. Starting with the work of Cole and Vishkin in 86, there was a long line of gradually improving algorithms published. The current ...
A new technique for distributed symmetry breaking
PODC '10: Proceedings of the 29th ACM SIGACT-SIGOPS symposium on Principles of distributed computing

We introduce Multi-Trials, a new technique for symmetry breaking for distributed algorithms and apply it to various problems in general graphs. For instance, we present three randomized algorithms for distributed (vertex or edge) coloring improving on ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

PODC '09: Proceedings of the 28th ACM symposium on Principles of distributed computing

August 2009

356 pages

ISBN:9781605583969

DOI:10.1145/1582716

General Chair:
Srikanta Tirthapura
Iowa State University, USA
,
Program Chair:
Lorenzo Alvisi
The University of Texas at Austin, USA

Copyright © 2009 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 10 August 2009

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

PODC '09

Sponsor:

PODC '09: ACM Symposium on Principles of Distributed Computing

August 10 - 12, 2009

AB, Calgary, Canada

Acceptance Rates

PODC '09 Paper Acceptance Rate 27 of 110 submissions, 25%;

Overall Acceptance Rate 740 of 2,477 submissions, 30%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

45
Total Citations
View Citations
264
Total Downloads

Downloads (Last 12 months)6
Downloads (Last 6 weeks)0

Reflects downloads up to 18 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Yang LZou YYu DYu J(2023)Distributed Age-of-Information optimization in edge computing for Internet of VehiclesJournal of Systems Architecture10.1016/j.sysarc.2023.103000144(103000)Online publication date: Nov-2023
https://doi.org/10.1016/j.sysarc.2023.103000
Barenboim LOren G(2022)Distributed backup placementDistributed Computing10.1007/s00446-022-00423-z35:5(455-473)Online publication date: 24-Mar-2022
https://doi.org/10.1007/s00446-022-00423-z
Yu DZou YWang YYu JCheng XLau F(2021)Implementing the Abstract MAC Layer via Inductive Coloring Under the Rayleigh-Fading ModelIEEE Transactions on Wireless Communications10.1109/TWC.2021.307223620:9(6167-6178)Online publication date: Sep-2021
https://doi.org/10.1109/TWC.2021.3072236
Yu DZou YYu JWu YLv WCheng XDressler FLau F(2021)Distributed Broadcasting in Dynamic NetworksIEEE/ACM Transactions on Networking10.1109/TNET.2021.308781829:5(2142-2155)Online publication date: Oct-2021
https://doi.org/10.1109/TNET.2021.3087818
Yu DZou YZhang YSheng HLv WCheng X(2021)An Exact Implementation of the Abstract MAC Layer via Carrier Sensing in Dynamic NetworksIEEE/ACM Transactions on Networking10.1109/TNET.2021.305789029:3(994-1007)Online publication date: Jun-2021
https://doi.org/10.1109/TNET.2021.3057890
Yu DZou YXu MXu YZhang YGong BXing X(2021)Competitive Age of Information in Dynamic IoT NetworksIEEE Internet of Things Journal10.1109/JIOT.2020.30385958:20(15160-15169)Online publication date: 15-Oct-2021
https://doi.org/10.1109/JIOT.2020.3038595
Zou YXu MXu YZhang YGong BXing X(2020)Distributed Data Aggregation in Dynamic Sensor NetworksWireless Algorithms, Systems, and Applications10.1007/978-3-030-59016-1_67(822-833)Online publication date: 10-Sep-2020
https://doi.org/10.1007/978-3-030-59016-1_67
Yu DZou YZhang YLi FYu JWu YCheng XLau F(2019)Distributed Dominating Set and Connected Dominating Set Construction Under the Dynamic SINR Model2019 IEEE International Parallel and Distributed Processing Symposium (IPDPS)10.1109/IPDPS.2019.00092(835-844)Online publication date: May-2019
https://doi.org/10.1109/IPDPS.2019.00092
Halldórsson MWang YYu D(2019)Leveraging multiple channels in ad hoc networksDistributed Computing10.1007/s00446-018-0329-332:2(159-172)Online publication date: 1-Apr-2019
https://dl.acm.org/doi/10.1007/s00446-018-0329-3
Yu DWang YTonoyan THalldorsson M(2017)Dynamic Adaptation in Wireless Networks Under Comprehensive Interference via Carrier Sense2017 IEEE International Parallel and Distributed Processing Symposium (IPDPS)10.1109/IPDPS.2017.78(337-346)Online publication date: May-2017
https://doi.org/10.1109/IPDPS.2017.78
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten