Article

Coloring unstructured radio networks

Authors:

Thomas Moscibroda,

Rogert WattenhoferAuthors Info & Claims

SPAA '05: Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures

Pages 39 - 48

https://doi.org/10.1145/1073970.1073977

Published: 18 July 2005 Publication History

Abstract

During and immediately after their deployment, ad hoc and sensor networks lack an efficient communication scheme rendering even the most basic network coordination problems difficult. Before any reasonable communication can take place, nodes must come up with an initial structure that can serve as a foundation for more sophisticated algorithms. In this paper, we consider the problem of obtaining a vertex coloring as such an initial structure. We propose an algorithm that works under the unstructured radio network model. This model captures the characteristics of newly deployed ad hoc and sensor networks, i.e. asynchronous wake-up, no collision-detection, and scarce knowledge about the network topology. Our algorithm produces a correct coloring with O(Δ) colors in time O(Δ log n) with high probability in a unit disk graph, where n and Δ are the number of nodes in the network and the maximum degree, respectively. Furthermore, the number of locally used colors depends only on the local node density.

References

[1]

I. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci. Wireless Sensor Networks: A Survey. Computer Networks Journal, 38(4):393--422, 2002.

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 Proceedings 6th ACM Symposium on Principles of Distributed Computing (PODC), pages 98--108, 1987.

Digital Library

[3]

R. Cole and U. Vishkin. Deterministic Coin Tossing with Applications to Optimal Parallel List Ranking. Inf. Control, 70(1):32--53, 1986.

Digital Library

[4]

I. Finocchi, A. Panconesi, and R. Silvestri. Experimental Analysis of Simple, Distributed Vertex Coloring Algorithms. In Proceedings of the 13th ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 606--615, 2002.

Digital Library

[5]

L. Gasieniec, A. Pelc, and D. Peleg. The Wakeup Problem in Synchronous Broadcast Systems (Extended Abstract). In Proceedings of the 19th ACM Symposium on Principles of Distributed Computing (PODC), pages 113--121, 2000.

Digital Library

[6]

A. Goldberg, S. Plotkin, and G. Shannon. Parallel symmetry-breaking in sparse graphs. In Proceedings of the 19th Annual ACM Conference on Theory of Computing (STOC), pages 315--324, 1987.

Digital Library

[7]

A. V. Goldberg and S. A. Plotkin. Parallel (Δ + 1)-Coloring of Constant-degree Graphs. Information Processing Letters, 25:241--245, 1987.

Digital Library

[8]

D. A. Grable and A. Panconesi. Fast Distributed Algorithms for Brooks-Vizing Colourings. In Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 473--480. Society for Industrial and Applied Mathematics, 1998.

Digital Library

[9]

W. R. Heinzelman, A. Chandrakasan, and H. Balakrishnan. Energy-Efficient Communication Protocol for Wireless Microsensor Networks. In Proceedings of the 33rd Hawaii International Conference on System Sciences (HICSS), page 8020. IEEE Computer Society, 2000.

Digital Library

[10]

T. Jurdzinski, M. Kutylowski, and J. Zatopianski. Energy-Efficient Size Approximation of Radio Networks with No Collision Detection. In Proceedings of the 8th Annual International Conference on Computing and Combinatorics (COCOON), pages 279--289, 2002.

Digital Library

[11]

T. Jurdzinski, M. Kutylowski, and J. Zatopianski. Weak Communication in Radio Networks. In Proceedings of Euro-Par, pages 397--408, 2002.

Digital Library

[12]

T. Jurdzinski and G. Stachowiak. Probabilistic Algorithms for the Wakeup Problem in Single-Hop Radio Networks. In Proceedings of 13th Annual International Symposium on Algorithms and Computation (ISAAC), pages 535--549, 2002.

Digital Library

[13]

S. O. Krumke, M. V. Marathe, and S. S. Ravi. Models and Approximation Algorithms for Channel Assignment in Radio Networks. Wireless Networks, 7(6):575--584, 2001.

Digital Library

[14]

F. Kuhn, T. Moscibroda, and R. Wattenhofer. Radio Network Clustering from Scratch. In Proceedings of 12th Annual European Symposium on Algorithms (ESA), pages 460--472.

[15]

F. Kuhn, T. Moscibroda, and R. Wattenhofer. Initializing Newly Deployed Ad Hoc and Sensor Networks. In Proceedings of 10th Annual International Conference on Mobile Computing and Networking (MOBICOM), pages 260--274, 2004.

Digital Library

[16]

N. Linial. Locality in Distributed Graph Algorithms. SIAM Journal on Computing, 21(1):193--201, 1992.

Digital Library

[17]

M. V. Marathe, H. Breu, H. B. Hunt III, S. S. Ravi, and D. J. Rosenkrantz. Simple Heuristics for Unit Disk Graphs. Networks, 25:59--68, 1995.

[18]

G. D. Marco and A. Pelc. Fast Distributed Graph Coloring with O(Δ) Colors. In Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 630--635, 2001.

Digital Library

[19]

M. J. McGlynn and S. A. Borbash. Birthday Protocols for Low Energy Deployment and Flexible Neighbor Discovery in Ad Hoc Wireless Networks. In Proceedings of the 2nd ACM International Symposium on Mobile Ad Hoc Networking and Computing (MOBIHOC), pages 137--145. ACM Press, 2001.

Digital Library

[20]

T. Moscibroda and R. Wattenhofer. Efficient Computation of Maximal Independent Sets in Unstructured Multi-Hop Radio Networks. In Proceedings of 1st IEEE International Conference on Mobile Ad-Hoc and Sensor Systems (MASS), 2004.

[21]

T. Moscibroda and R. Wattenhofer. Maximal Independent Sets in Radio Networks. In Proceedings of the 23rd ACM Symp. on Principles of Distributed Computing (PODC), 2005.

Digital Library

[22]

K. Nakano and S. Olariu. Energy-Efficient Initialization Protocols for Single-Hop Radio Networks with No Collision Detection. IEEE Trans. Parallel Distributed Systems, 11(8):851--863, 2000.

Digital Library

[23]

K. Nakano and S. Olariu. Randomized Initialization Protocols for Radio Networks. pages 195--218, 2002.

Digital Library

[24]

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

Digital Library

[25]

D. Peleg. Distributed Computing: A Locality-Sensitive Approach. SIAM Monographs on Discrete Mathematics and Applications, 2000.

Digital Library

[26]

S. Ramanathan and E. L. Lloyd. Scheduling Algorithms for Multi-Hop Radio Networks. In Conference proceedings on Communications architectures & protocols (SIGCOMM), pages 211--222. ACM Press, 1992.

Digital Library

[27]

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. COM-23(12):1417--1433, 1975.

[28]

A. Woo and D. E. Culler. A Transmission Control Scheme for Media Access in Sensor Networks. In Proceedings of the 7th International Conference on Mobile Computing and Networking (MOBICOM), pages 221--235. ACM Press, 2001.

Digital Library

Cited By

Moscibroda T(2016)Local Computation in Unstructured Radio NetworksEncyclopedia of Algorithms10.1007/978-1-4939-2864-4_210(1133-1136)Online publication date: 22-Apr-2016
https://doi.org/10.1007/978-1-4939-2864-4_210
Feuilloley LFraigniaud PBlelloch GAgrawal K(2015)Randomized Local Network ComputingProceedings of the 27th ACM symposium on Parallelism in Algorithms and Architectures10.1145/2755573.2755596(340-349)Online publication date: 13-Jun-2015
https://dl.acm.org/doi/10.1145/2755573.2755596
Bhatia AHansdah R(2015)DSLRProceedings of the 2015 IEEE International Parallel and Distributed Processing Symposium10.1109/IPDPS.2015.60(365-374)Online publication date: 25-May-2015
https://dl.acm.org/doi/10.1109/IPDPS.2015.60
Show More Cited By

Index Terms

Coloring unstructured radio networks
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Graph algorithms
      2. Network flows
2. Theory of computation
  1. Design and analysis of algorithms
    1. Graph algorithms analysis
      1. Network flows
  2. Randomness, geometry and discrete structures

Recommendations

Maximal independent sets in radio networks
PODC '05: Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing

We study the distributed complexity of computing a maximal independent set (MIS) in radio networks with completely unknown topology, asynchronous wake-up, and no collision detection mechanism available. Specifically, we propose a novel randomized ...
Initializing newly deployed ad hoc and sensor networks
MobiCom '04: Proceedings of the 10th annual international conference on Mobile computing and networking

A newly deployed multi-hop radio network is unstructured and lacks a reliable and efficient communication scheme. In this paper, we take a step towards analyzing the problems existing during the initialization phase of ad hoc and sensor networks. ...
Coloring unstructured wireless multi-hop networks
PODC '09: Proceedings of the 28th ACM symposium on Principles of distributed computing

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

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

SPAA '05: Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures

July 2005

346 pages

ISBN:1581139861

DOI:10.1145/1073970

General Chair:
Phil Gibbons
Intel Research
,
Program Chair:
Paul Spirakis
Research and Academic Computer Technology Institute, Greece

Copyright © 2005 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: 18 July 2005

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

SPAA05

Sponsor:

SPAA05: 17th ACM Symposium on Parallelism in Algorithms and Architectures 2005

July 18 - 20, 2005

Nevada, Las Vegas, USA

Acceptance Rates

Overall Acceptance Rate 447 of 1,461 submissions, 31%

Upcoming Conference

SPAA '25

Sponsor:
sigact
sigact

37th ACM Symposium on Parallelism in Algorithms and Architectures

July 28 - August 1, 2025

Portland , OR , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

57
Total Citations
View Citations
473
Total Downloads

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

Reflects downloads up to 18 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Moscibroda T(2016)Local Computation in Unstructured Radio NetworksEncyclopedia of Algorithms10.1007/978-1-4939-2864-4_210(1133-1136)Online publication date: 22-Apr-2016
https://doi.org/10.1007/978-1-4939-2864-4_210
Feuilloley LFraigniaud PBlelloch GAgrawal K(2015)Randomized Local Network ComputingProceedings of the 27th ACM symposium on Parallelism in Algorithms and Architectures10.1145/2755573.2755596(340-349)Online publication date: 13-Jun-2015
https://dl.acm.org/doi/10.1145/2755573.2755596
Bhatia AHansdah R(2015)DSLRProceedings of the 2015 IEEE International Parallel and Distributed Processing Symposium10.1109/IPDPS.2015.60(365-374)Online publication date: 25-May-2015
https://dl.acm.org/doi/10.1109/IPDPS.2015.60
Yu DWang YHua QLau F(2014)Distributed ( Δ + 1 ) -coloring in the physical modelTheoretical Computer Science10.1016/j.tcs.2014.05.016553:C(37-56)Online publication date: 1-Dec-2014
https://dl.acm.org/doi/10.1016/j.tcs.2014.05.016
Fuchs FWagner D(2014)Local Broadcasting with Arbitrary Transmission Power in the SINR ModelStructural Information and Communication Complexity10.1007/978-3-319-09620-9_15(180-193)Online publication date: 2014
https://doi.org/10.1007/978-3-319-09620-9_15
Marden JWierman A(2013)Distributed Welfare GamesOperations Research10.1287/opre.1120.113761:1(155-168)Online publication date: 1-Jan-2013
https://dl.acm.org/doi/10.1287/opre.1120.1137
Ribeiro CAnastácio ICosta ABaptista M(2013)A Framework for Robust Address Assignment in WSNs Whispering to Avoid IntrudersInternational Journal of Distributed Sensor Networks10.1155/2013/6935199:9(693519)Online publication date: Jan-2013
https://doi.org/10.1155/2013/693519
Muldoon COhare GOgrady MTynan RTrigoni N(2013)Distributed constraint optimisation for resource limited sensor networksScience of Computer Programming10.1016/j.scico.2012.10.00578:5(583-593)Online publication date: 1-May-2013
https://dl.acm.org/doi/10.1016/j.scico.2012.10.005
Cappanera PLenzini LLori AStea GVaglini G(2013)Optimal joint routing and link scheduling for real-time traffic in TDMA Wireless Mesh NetworksComputer Networks: The International Journal of Computer and Telecommunications Networking10.1016/j.comnet.2012.11.02157:11(2301-2312)Online publication date: 1-Aug-2013
https://dl.acm.org/doi/10.1016/j.comnet.2012.11.021
Halldórsson MMitra PKuhn FNewport C(2012)Towards tight bounds for local broadcastingProceedings of the 8th International Workshop on Foundations of Mobile Computing10.1145/2335470.2335472(1-9)Online publication date: 19-Jul-2012
https://dl.acm.org/doi/10.1145/2335470.2335472
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