On Flooding in the Presence of Random Faults

• Autorzy: Cichoń J. , Klonowski M.
• Języki publikacji: EN

Abstrakty

EN

In this paper we study the efficiency of information flooding protocols in various communication networks, and in the presence of random faults. We show big differences between the flooding performance of networks with a seemingly similar structure. Since real-life systems usually consist of a moderate number of devices, the analysis presented in this paper is not limited to the asymptotic behavior of the flooding protocol. Instead, exact formulas are provided whenever possible. The presented results can be useful building blocks for the analysis of other, more sophisticated protocols. In particular, they may be used for planning and analyzing sensors network deployed in an environment subject to communication failures.

Słowa kluczowe

EN

flooding protocol; communication networks with failures; geometric distribution; Markov chain

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2013
• Tom: Vol. 123, nr 3
• Strony: 273--287
• Opis fizyczny: Bibliogr. 15 poz., tab., wykr.

Twórcy

autor

Cichoń J.

• Institute of Mathematics and Computer Science Wrocław University of Technology, Poland

autor

Klonowski M.

• Institute of Mathematics and Computer Science Wrocław University of Technology, Poland

Bibliografia

• [1] Bollobás, B., Riordan, O.: Percolation, Cambridge University Press, 2006, ISBN 9780521872324.
• [2] Chatzigiannakis, I., Dimitriou, T., Nikoletseas, S. E., Spirakis, P. G.: A probabilistic algorithm for efficient and robust data propagation in wireless sensor networks, Ad Hoc Networks, 4(5), 2006, 621–635.
• [3] Chatzigiannakis, I., Kirousis, L. M., Stratiotis, T.: Probabilistic Protocols for Fair Communication inWireless Sensor Networks, ALGOSENSORS (S. P. Fekete, Ed.), 5389, Springer, 2008, ISBN 978-3-540-92861-4.
• [4] Cichoń, J., Lemiesz, J., Zawada, M.: On Message Complexity of Extrema Propagation Techniques, ADHOCNOW (X.-Y. Li, S. Papavassiliou, S. Rührup, Eds.), 7363, Springer, 2012, ISBN 978-3-642-31637-1.
• [5] Flajolet, P., Sedgewick, R.: Analytic Combinatorics, Cambridge University Press, 2009, ISBN 978-0-521-89806-5.
• [6] Gomulkiewicz, M., Klonowski, M., Kutylowski, M.: Provable Unlinkability Against Traffic Analysis Already After O(log(n)) Steps!, ISC (K. Zhang, Y. Zheng, Eds.), 3225, Springer, 2004, ISBN 3-540-23208-7.
• [7] Grabner, P. J., Prodinger, H.: Maximum Statistics of N Random Variables Distributed by the Negative Binomial Distribution, Combinatorics, Probability & Computing, 6(2), 1997, 179–183.
• [8] Gumbel, E.: Statistics of Extremes, Dover books on mathematics, Dover Publications, 2004, ISBN 9780486436043.
• [9] Iwanik, J., Klonowski, M., Kutylowski, M.: DUO–Onions and Hydra–Onions – Failure and Adversary Resistant Onion Protocols, Proceedings of the IFIP TC-6 TC-11 Conference on Communications and Multimedia Security 2004, September 2004.
• [10] Knuth, D. E.: The Art of Computer Programming, Volume I: Fundamental Algorithms, Addison-Wesley, 1968.
• [11] Rackoff, C., Simon, D. R.: Cryptographic defense against traffic analysis, STOC (S. R. Kosaraju, D. S. Johnson, A. Aggarwal, Eds.), ACM, 1993, ISBN 0-89791-591-7.
• [12] Szpankowski, W., Rego, V.: Yet another application of a binomial recurrence. Order statistics, Computing, 43(4), February 1990, 401–410, ISSN 0010-485X.
• [13] Valiant, L. G.: A Scheme for Fast Parallel Communication, SIAM J. Comput., 1982, 350–361.
• [14] Wu, D., Bao, L., Li, R.: A holistic approach to wireless sensor network routing in underground tunnel environments, Comput. Commun., 33(13), August 2010, 1566–1573, ISSN 0140-3664.
• [15] YOUNG, D. H.: The order statistics of the negative binomial distribution, Biometrika, 57(1), 1970, 181–186.