Abstract
Wireless networks often experience a significant amount of churn, the arrival and departure of nodes. In this paper we propose a distributed algorithm for single-hop networks that detects churn and is resilient to a worst-case adversary. The nodes of the network are notified about changes quickly, in asymptotically optimal time up to an additive logarithmic overhead. We establish a trade-off between saving energy and minimizing the delay until notification for single- and multi-channel networks.
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
Bakshi, A., Prasanna, V.K.: Energy-Efficient Communication in Multi-Channel Single-Hop Sensor Networks. In: Conference on Parallel and Distributed Systems, p. 403. IEEE, Los Alamitos (2004)
Bar-Yehuda, R., Goldreich, O., Itai, A.: Efficient Emulation of Single-Hop Radio Network with Collision Detection on Multi-Hop Radio Network with No Collision Detection. Distributed Computing 5(2), 67–71 (1991)
Caragiannis, I., Galdi, C., Kaklamanis, C.: Basic computations in wireless networks. In: Deng, X., Du, D.-Z. (eds.) ISAAC 2005. LNCS, vol. 3827, pp. 533–542. Springer, Heidelberg (2005)
Chlebus, B.S., Kowalski, D.R., Lingas, A.: Performing work in broadcast networks. Distributed Computing 18(6), 435–451 (2006)
Chlebus, B.S., Kowalski, D.R., Rokicki, M.A.: Maximum throughput of multiple access channels in adversarial environments. Distributed Computing 22(2), 93–116 (2009)
Chockler, G.V., Keidar, I., Vitenberg, R.: Group communication specifications: a comprehensive study. ACM Computing Surveys (CSUR) 33(4), 427–469 (2001)
Kowalski, D.R., Georgiou, C., Gilbert, S.: Meeting the deadline: On the complexity of fault-tolerant continuous gossip. In: PODC (2010)
Holzer, S., Pignolet, Y.A., Smula, J., Wattenhofer, R.: Monitoring Churn in Wireless Networks. Technical report, Computer Engineering and Networks Laboratory (TIK), ETH Zurich, Switzerland (2010), ftp://ftp.tik.ee.ethz.ch/pub/publications/TIK-Report-328.pdf
Kabarowski, J., Kutylowski, M., Rutkowski, W.: Adversary immune size approximation of single-hop radio networks. In: Cai, J.-Y., Cooper, S.B., Li, A. (eds.) TAMC 2006. LNCS, vol. 3959, p. 148. Springer, Heidelberg (2006)
Kik, M.: Merging and Merge-Sort in a Single Hop Radio Network. In: Wiedermann, J., Tel, G., Pokorný, J., Bieliková, M., Štuller, J. (eds.) SOFSEM 2006. LNCS, vol. 3831, p. 341. Springer, Heidelberg (2006)
Klonowski, M., Kutyłowski, M., Zatopianski, J.: Energy Efficient Alert in Single-Hop Networks of Extremely Weak Devices. In: Dolev, S. (ed.) ALGOSENSORS 2009. LNCS, vol. 5804, pp. 139–150. Springer, Heidelberg (2009)
Kowalski, D.R., Pelc, A.: Leader Election in Ad Hoc Radio Networks: A Keen Ear Helps. In: 36th International Colloquium on Automata, Languages and Programming, p. 533 (2009)
Kutyłowski, M., Letkiewicz, D.: Computing Average Value in Ad Hoc Networks. In: Rovan, B., Vojtáš, P. (eds.) MFCS 2003. LNCS, vol. 2747, pp. 511–520. Springer, Heidelberg (2003)
Kutyłowski, M., Rutkowski, W.: Adversary Immune Leader Election in Ad Hoc Radio Networks. In: Di Battista, G., Zwick, U. (eds.) ESA 2003. LNCS, vol. 2832, pp. 397–408. Springer, Heidelberg (2003)
Lavault, C., Marckert, J.F., Ravelomanana, V.: Quasi-optimal energy-efficient leader election algorithms in radio networks. Information and Computation 205(5), 679–693 (2007)
Singh, M., Prasanna, V.K.: Optimal energy-balanced algorithm for selection in a single hop sensor network. In: IEEE Workshop on Sensor Network Protocols and Applications (SNPA) (2003)
Singh, M., Prasanna, V.K.: Energy-optimal and energy-balanced sorting in a single-hop wireless sensor network. In: Pervasive Computing and Communications (PERCOM) (2003)
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
Holzer, S., Pignolet, Y.A., Smula, J., Wattenhofer, R. (2010). Monitoring Churn in Wireless Networks. In: Scheideler, C. (eds) Algorithms for Sensor Systems. ALGOSENSORS 2010. Lecture Notes in Computer Science, vol 6451. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-16988-5_11
Download citation
DOI: https://doi.org/10.1007/978-3-642-16988-5_11
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-16987-8
Online ISBN: 978-3-642-16988-5
eBook Packages: Computer ScienceComputer Science (R0)
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.