Deterministic Communication in the Weak Sensor Model
Pages 119 - 131
Abstract
In 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 is the energy supply, and radio communication dominates the sensor node energy consumption. Hence, redundant trials of transmission as used in randomized protocols may be counter-effective. Additionally, most of the research work in Sensor Networks is either heuristic or includes unreallistic assumptions. Hence, provable results for many basic problems still remain to be given. In this paper, we study upper and lower bounds for deterministic communication primitives under the harsh constraints of sensor nodes.
References
[1]
Alon N., Bar-Noy A., Linial N., and Peleg D. Single round simulation in radio networks Journal of Algorithms 1992 13 188-210
[2]
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
[3]
Bonis, A.D., Ga̧sieniec, L., Vaccaro, U.: Generalized framework for selectors with applications in optimal group testing. In: Proc. of 30th International Colloquium on Automata Languages and Programming (2003)
[4]
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 (2001)
[5]
Chlebus B.S., Ga̧sieniec L., Gibbons A., Pelc A., and Rytter W. Deterministic broadcasting in unknown radio networks Distributed Computing 2002 15 27-38
[6]
Chlebus, B.S., Ga̧sieniec, L., Östlin, A., Robson, J.M.: Deterministic radio broadcasting. In: Proc. of 27th International Colloquium on Automata Languages and Programming (2000)
[7]
Chrobak, M., Ga̧sieniec, L., Kowalski, D.: The wake-up problem in multi-hop radio networks. In: Proc. of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (2004)
[8]
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)
[9]
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)
[10]
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)
[11]
Dyachkov, A., Rykov, V.: A survey of superimposed code theory. Problems Control and Inform. Theory 12 (1983)
[12]
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
[13]
Farach-Colton, M., Mosteiro, M.A.: Initializing sensor networks of non-uniform density in the weak sensor model. In: Proc. of 10th International Workshop on Algorithms and Data Structures (to appear, 2007)
[14]
Farach-Colton, M., Mosteiro, M.A.: Sensor network gossiping or how to break the broadcast lower bound. Manuscript (2007)
[15]
Fejes-Tóth L. Über einen geometrischen Satz Mathematische Zeitschrift 1940 46 83-85
[16]
Hardy G.H. and Wright E.M. An introduction to the theory of numbers 1979 Oxford Oxford University Press
[17]
Indyk, P.: Explicit constructions of selectors and related combinatorial structures, with applications. In: Proc. of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms (2002)
[18]
Komlòs J. and Greenberg A. An asymptotically nonadaptive algorithm for conflict resolution in multiple-access channels IEEE Trans. Inf. Theory 1985 31 303-306
[19]
Kowalski, D.R.: On selection problem in radio networks. In: Proceedings 24th Annual ACM Symposium on Principles of Distributed Computing (2005)
[20]
Kushilevitz E. and Mansour Y. An Ω(Dlog(N/D)) lower bound for broadcast in radio networks SIAM Journal on Computing 1998 27 702-712
[21]
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
Recommendations
Sensor Network Gossiping or How to Break the Broadcast Lower Bound
Algorithms and ComputationAbstractGossiping 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, ...
Bootstrapping a hop-optimal network in the weak sensor model
Sensor nodes are very weak computers that get distributed at random on a surface. Once deployed, they must wake up and form a radio network. Sensor network bootstrapping research thus has three parts: One must model the restrictions on sensor nodes; one ...
Green content communications in 6LoWPAN
As a low‐rate and low‐power network, IPv6 over low‐power wireless personal area network (6LoWPAN) wireless sensor network (WSN) suffers from considerable data communication latency and rapid energy depletion which data transmission mainly accounts for. ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Dec 2007
314 pages
ISBN:978-3-540-77095-4
DOI:10.1007/978-3-540-77096-1
- Editors:
- Eduardo Tovar,
- Philippas Tsigas,
- Hacène Fouchal
© 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