Sensor Network Gossiping or How to Break the Broadcast Lower Bound
Pages 232 - 243
Abstract
Gossiping is an important problem in Radio Networks that has been well studied, leading to many important results. Due to strong resouce limitations of sensor nodes, previous solutions are frequently not feasible in Sensor Networks. In this paper, we study the gossiping problem in the restrictive context of Sensor Networks. By exploiting the geometry of sensor node distributions, we present reduced, optimal running time of O(D + Δ) for an algorithm that completes gossiping with high probability in a Sensor Network of unknown topology and adversarial wake-up, where D is the diameter and Δ the maximum degree of the network. Given that an algorithm for gossiping also solves the broadcast problem, our result proves that the classic lower bound of [16] can be broken if nodes are allowed to do preprocessing.
References
[1]
Bar-Yehuda R., Goldreich O., and Itai A. On the time-complexity of broadcast in multi-hop radio networks: An exponential gap between determinism and randomization Journal of Computer and System Sciences 1992 45 104-126
[2]
Bar-Yehuda R., Israeli A., and Itai A. Multiple communication in multihop radio networks SIAM Journal on Computing 1993 22 875-887
[3]
Bruschi D. and Pinto M.D. Lower bounds for the broadcast problem in mobile radio networks Distributed Computing 1997 10 3 129-135
[4]
Chlamtac, I., Weinstein, O.: The wave expansion approach to broadcasting in multihop networks. In: Proc. of INFOCOM (1987)
[5]
Chlebus, B., Ga̧sieniec, L., Lingas, A., Pagourtzis, A.: Oblivious gossiping in ad-hoc radio networks. In: Proc. of 5th International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications, pp. 44–51 (2001)
[6]
Chrobak, M., Ga̧sieniec, L., Rytter, W.: Fast broadcasting and gossiping in radio networks. In: Proc. of the 41st IEEE Annual Symp. on Foundation of Computer Science (2000)
[7]
Chrobak M., Ga̧sieniec L., and Rytter W. A randomized algorithm for gossiping in radio networks Networks 2004 43 2 119-124
[8]
Clementi, A., Monti, A., Silvestri, R.: Selective families, superimposed codes, and broadcasting on unknown radio networks. In: Proc. of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms (2001)
[9]
Czumaj, A., Rytter, W.: Broadcasting algorithms in radio networks with unknown topology. In: Proc. of the 44th IEEE Annual Symp. on Foundation of Computer Science (2003)
[10]
Farach-Colton M., Fernandes R.J., and Mosteiro M.A. Brodal G.S. and Leonardi S. Bootstrapping a hop-optimal network in the weak sensor model Algorithms – ESA 2005 2005 Heidelberg Springer 827-838
[11]
Fejes-Tóth L. über einen geometrischen satz Mathematische Zeitschrift 1940 46 1 83-85
[12]
Ga̧sieniec, L., Potapov, I.: Gossiping with unit messages in known radio networks. In: Proc. of 17th IFIP World Computer Congress / 2nd IFIP International Conference on Theoretical Computer Science (2002)
[13]
Geréb-Graus, M., Tsantiles, T.: Efficient optical communication in parallel computers. In: 4th Annual ACM Symposium on Parallel Algorithms and Architectures pp. 41–48 (1992)
[14]
Kowalski, D.R.: On selection problem in radio networks. In: Proceedings 24th Annual ACM Symposium on Principles of Distributed Computing, pp. 158–166 (2005)
[15]
Kowalski D.R. and Pelc A. Time of deterministic broadcasting in radio networks with local knowledge SIAM Journal on Computing 2004 33 4 870-891
[16]
Kushilevitz E. and Mansour Y. An Ω(Dlog(N/D)) lower bound for broadcast in radio networks SIAM Journal on Computing 1998 27 3 702-712
[17]
Liu D. and Prabhakaran M. Ibarra O.H. and Zhang L. On randomized broadcasting and gossiping in radio networks Computing and Combinatorics 2002 Heidelberg Springer 340-349
[18]
Mitzenmacher M. and Upfal E. Probability and Computing: Randomized Algorithms and Probabilistic Analysis 2005 Cambridge Cambridge University Press
[19]
Moscibroda, T., Wattenhofer, R.: Maximal independent sets in radio networks. Technical Report TR-478, Computer Engineering and Networks Laboratory, ETH Zurich, 8092 Zurich, Switzerland (December 2004)
[20]
Ravelomanana V. Optimal initialization and gossiping algorithms for random radio networks IEEE Trans. Parallel Distr. Syst. 2007 18 1 17-28
Index Terms
- Sensor Network Gossiping or How to Break the Broadcast Lower Bound
Index terms have been assigned to the content through auto-classification.
Recommendations
Deterministic Communication in the Weak Sensor Model
Principles of Distributed SystemsAbstractIn Sensor Networks, the lack of topology information and the availability of only one communication channel has led research work to the use of randomization to deal with collision of transmissions. However, the scarcest resource in this setting ...
Optimal memory-aware Sensor Network Gossiping (or how to break the Broadcast lower bound)
Gossiping is a well-studied problem in Radio Networks. However, due to the strong resource limitations of sensor nodes, previous solutions are frequently not feasible in Sensor Networks. In this paper, we study the Gossiping problem in the restrictive ...
Sensor network gossiping or how to break the broadcast lower bound
ISAAC'07: Proceedings of the 18th international conference on Algorithms and computationGossiping is an important problem in Radio Networks that has been well studied, leading to many important results. Due to strong resouce limitations of sensor nodes, previous solutions are frequently not feasible in Sensor Networks. In this paper, we ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
© Springer-Verlag Berlin Heidelberg 2007.
Publisher
Springer-Verlag
Berlin, Heidelberg
Publication History
Published: 17 December 2007
Author Tags
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 18 Feb 2025