Abstract
We present the discrete beeping communication model, which assumes nodes have minimal knowledge about their environment and severely limited communication capabilities. Specifically, nodes have no information regarding the local or global structure of the network, do not have access to synchronized clocks and are woken up by an adversary. Moreover, instead on communicating through messages they rely solely on carrier sensing to exchange information. This model is interesting from a practical point of view, because it is possible to implement it (or emulate it) even in extremely restricted radio network environments. From a theory point of view, it shows that complex problems (such as vertex coloring) can be solved efficiently even without strong assumptions on properties of the communication model.
We study the problem of interval coloring, a variant of vertex coloring specially suited for the studied beeping model. Given a set of resources, the goal of interval coloring is to assign every node a large contiguous fraction of the resources, such that neighboring nodes have disjoint resources. A k-interval coloring is one where every node gets at least a 1/k fraction of the resources.
To highlight the importance of the discreteness of the model, we contrast it against a continuous variant described in [17]. We present an \({\mathcal O}(1)\) time algorithm that with probability 1 produces a \({\mathcal O}(\Delta)\)-interval coloring. This improves an \({\mathcal O}(\log n)\) time algorithm with the same guarantees presented in [17], and accentuates the unrealistic assumptions of the continuous model. Under the more realistic discrete model, we present a Las Vegas algorithm that solves \({\mathcal O}(\Delta)\)-interval coloring in \({\mathcal O}(\log n)\) time with high probability and describe how to adapt the algorithm for dynamic networks where nodes may join or leave. For constant degree graphs we prove a lower bound of Ω(logn) on the time required to solve interval coloring for this model against randomized algorithms. This lower bound implies that our algorithm is asymptotically optimal for constant degree graphs.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Awerbuch, B., Goldberg, A.V., Luby, M., Plotkin, S.A.: Network decomposition and locality in distributed computation. In: Proc. of 30th Symposium on Foundations of Computer Science (FOCS), pp. 364–369 (1989)
Balasundaram, B., Butenko, S.: Graph domination, coloring and cliques in telecommunications. In: Resende, M.G.C., Pardalos, P.M. (eds.) Handbook of Optimization in Telecommunications, pp. 865–890. Springer, Heidelberg (2006)
Barenboim, L., Elkin, M.: Distributed (Δ + 1)-coloring in linear (in Δ) time. In: Proc. of the 41st ACM Symposium on Theory of Computing, STOC (2009)
Barenboim, L., Elkin, M.: Deterministic distributed vertex coloring in polylogarithmic time. In: Proc. 29th ACM Symposium on Principles of Distributed Computing, PODC (2010)
Degesys, J., Nagpal, R.: Towards desynchronization of multi-hop topologies. In: Proc. 2nd IEEE Conference Self-Adaptive and Self-Organizing Systems (SASO), pp. 129–138 (2008)
Degesys, J., Rose, I., Patel, A., Nagpal, R.: Desync: self-organizing desynchronization and TDMA on wireless sensor networks. In: Proc. 6th Conference on Information Processing in Sensor Networks (IPSN), p. 20 (2007)
Flury, R., Wattenhofer, R.: Slotted programming for sensor networks. In: Proc. 9th Conference on Information Processing in Sensor Networks, IPSN (2010)
Gandham, S., Dawande, M., Prakash, R.: Link scheduling in sensor networks: Distributed edge coloring revisited. In: Proc. of 24th IEEE Conference on Computer Communications (INFOCOM), pp. 2492–2501 (2005)
Goldberg, A.V., Plotkin, S.A., Shannon, G.E.: Parallel symmetry-breaking in sparse graphs. SIAM Journal on Discrete Mathematics 1(4), 434–446 (1988)
Herman, T., Tixeuil, S.: A distributed TDMA slot assignment algorithm for wireless sensor networks. In: Nikoletseas, S.E., Rolim, J.D.P. (eds.) ALGOSENSORS 2004. LNCS, vol. 3121, pp. 45–58. Springer, Heidelberg (2004)
Kothapalli, K., Onus, M., Scheideler, C., Schindelhauer, C.: Distributed coloring in \(o(\sqrt{\log n})\) bit rounds. In: Proc. of 20th IEEE Parallel and Distributed Processing Symposium, IPDPS (2006)
Kuhn, F.: Local multicoloring algorithms: Computing a nearly-optimal TDMA schedule in constant time. In: Proc. of 26th Symp. on Theoretical Aspects of Computer Science, STACS (2009)
Kuhn, F.: Weak Graph Coloring: Distributed Algorithms and Applications. In: Proc. of 21st ACM Symposium on Parallelism in Algorithms and Architectures, SPAA (2009b)
Linial, N.: Locality in distributed graph algorithms. SIAM Journal on Computing, 193–201 (1992)
Mecke, S.: MAC layer and coloring. In: Wagner, D., Wattenhofer, R. (eds.) Algorithms for Sensor and Ad Hoc Networks, pp. 63–80 (2007)
Moscibroda, T., Wattenhofer, R.: Coloring unstructured radio networks. In: Proc. 17th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 39–48 (2005)
Motskin, A., Roughgarden, T., Skraba, P., Guibas, L.: Lightweight coloring and desynchronization for networks. In: Proc. 28th IEEE Conference on Computer Communications, INFOCOM (2009)
Panconesi, A., Srinivasan, A.: On the complexity of distributed network decomposition. Journal of Algorithms 20(2), 581–592 (1995)
Ramanathan, S.: A unified framework and algorithm for channel assignment in wireless networks. Wireless Networks 5, 81–94 (1999)
Rhee, I., Warrier, A., Min, J., Xu, L.: DRAND: Distributed randomized TDMA scheduling for wireless ad-hoc networks. In: 7th ACM Symp. on Mobile Ad Hoc Networking and Computing (MOBIHOC), pp. 190–201 (2006)
Scheideler, C., Richa, A., Santi, P.: An o(log n) dominating set protocol for wireless ad-hoc networks under the physical interference model. In: Proc. 9th ACM Symposium on Mobile Ad Hoc Networking and Computing (MOBIHOC), pp. 91–100 (2008)
Schmid, S., Wattenhofer, R.: Algorithmic models for sensor networks. In: Proc. 14th Workshop on Parallel and Distributed Real-Time Systems, WPDRTS (2006)
Schneider, J., Wattenhofer, R.: A log-star distributed maximal independent set algorithm for growth-bounded graphs. In: Proc. of 27th ACM Symposium on Principles of Distributed Computing, PODC (2008)
Schneider, J., Wattenhofer, R.: Coloring unstructured wireless multi-hop networks. In: Proc. 28th ACM Symposium on Principles of Distributed Computing (PODC), pp. 210–219 (2009)
Schneider, J., Wattenhofer, R.: A new technique for distributed symmetry breaking. In: Proc. 29th ACM Symposium on Principles of Distributed Computing, PODC (2010)
USC/ISI. Network Simulator 2 (NS2), http://www.isi.edu/nsnam/ns/
Zhang, X., Hong, J., Zhang, L., Shan, X., Li, V.O.K.: CP-TDMA: Coloring- and probability-based TDMA scheduling for wireless ad hoc networks. IEICE Transactions on Communication E91-B(1), 322–326 (2008)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Cornejo, A., Kuhn, F. (2010). Deploying Wireless Networks with Beeps. In: Lynch, N.A., Shvartsman, A.A. (eds) Distributed Computing. DISC 2010. Lecture Notes in Computer Science, vol 6343. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-15763-9_15
Download citation
DOI: https://doi.org/10.1007/978-3-642-15763-9_15
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-15762-2
Online ISBN: 978-3-642-15763-9
eBook Packages: Computer ScienceComputer Science (R0)