Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Buchtitelbild

2017 | OriginalPaper | Buchkapitel

Multi-message Broadcast in Dynamic Radio Networks

verfasst von : Mohamad Ahmadi, Fabian Kuhn

Erschienen in: Algorithms for Sensor Systems

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

We continue the recent line of research studying information dissemination problems in adversarial dynamic radio networks. We give two generic algorithms which allow to transform generalized version of single-message broadcast algorithms into multi-message broadcast algorithms. Based on these generic algorithms, we obtain multi-message broadcast algorithms for dynamic radio networks for a number of different dynamic network settings. For one of the modeling assumptions, our algorithms are complemented by a lower bound which shows that the upper bound is close to optimal.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Nächstes Kapitel Global Synchronization and Consensus Using Beeps in a Fault-Prone MAC
Fußnoten
1
Note that this assumption is reasonable as long as the number of broadcast messages which are combined with each other is at most the length of a single broadcast message (in bits).
 
2
We note that many other, similar dynamic network models have appeared in the literature (cf. Sect. 1).
 
Literatur
1.
Ahmadi, M., Ghodselahi, A., Kuhn, F., Molla, A.R.: The cost of global broadcast in dynamic radio networks. In: Proceedings of the 19th International Conference on Principles of Distributed Systems (OPODIS) (2015)
2.
Ahmadi, M., Kuhn, F.: Multi-message broadcast in dynamic radio networks. CoRR, abs/1610.02931 (2016)
3.
Anta, A.F., Milani, A., Mosteiro, M.A., Zaks, S.: Opportunistic information dissemination in mobile ad-hoc networks: the profit of global synchrony. Distrib. Comput. 25(4), 279–296 (2012)CrossRefMATH
4.
Avin, C., Koucký, M., Lotker, Z.: How to explore a fast-changing world (cover time of a simple random walk on evolving graphs). In: Proceedings of the 5th Colloquium on Automata, Languages and Programming (ICALP) (2008)
5.
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. Distrib. Comput. 5(2), 67–71 (1991)CrossRefMATH
6.
Bar-Yehuda, R., Goldreich, O., Itai, A.: On the time-complexity of broadcast in multi-hop radio networks: an exponential gap between determinism and randomization. Comput. Syst. Sci. 45(1), 104–126 (1992)MathSciNetCrossRefMATH
7.
Baumann, H., Crescenzi, P., Fraigniaud, P.: Parsimonious flooding in dynamic graphs. In: Proceedings of the 28th ACM Symposium on Principles of Distributed Computing (PODC) (2009)
8.
Casteigts, A., Flocchini, P., Quattrociocchi, W., Santoro, N.: Time-varying graphs and dynamic networks. In: Proceedings of the 10th International Conference on Ad-hoc, Mobile, and Wireless Networks (2011)
9.
Censor-Hillel, K., Gilbert, S., Kuhn, F., Lynch, N., Newport, C.: Structuring unreliable radio networks. Distrib. Comput. 27(1), 1–19 (2014)MathSciNetCrossRefMATH
10.
Chlamtac, I., Kutten, S.: On broadcasting in radio networks-problem analysis and protocol design. IEEE Trans. Commun. 33(12), 1240–1246 (1985)CrossRefMATH
11.
Chlebus, B.S., Gasieniec, L., Ostlin, A., Robson, J.M.: Deterministic radio broadcasting. In: Proceedings of the 27th International Colloquium on Automata, Languages, and Programming (ICALP) (2000)
12.
Chlebus, B.S., Kowalski, D.R., Radzik, T.: Many-to-many communication in radio networks. Algorithmica 54(1), 118–139 (2009)MathSciNetCrossRefMATH
13.
Christersson, M., Gasieniec, L., Lingas, A.: Gossiping with bounded size messages in ad hoc radio networks. In: Proceedings of the 29th International Colloquium on Automata, Languages and Programming (ICALP) (2002)
14.
Chrobak, M., Gasieniec, L., Rytter, W.: A randomized algorithm for gossiping in radio networks. Networks 43(2), 119–124 (2004)MathSciNetCrossRefMATH
15.
Clementi, A., Monti, A., Pasquale, F., Silvestri, R.: Broadcasting in dynamic radio networks. Comput. Syst. Sci. 75(4), 213–230 (2009)MathSciNetCrossRefMATH
16.
Clementi, A., Monti, A., Silvestri, R.: Selective families, superimposed codes, and broadcasting on unknown radio networks. In: Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA) (2001)
17.
Clementi, A., Monti, A., Silvestri, R.: Round robin is optimal for fault-tolerant broadcasting on wireless networks. Parallel Distrib. Comput. 64(1), 89–96 (2004)CrossRefMATH
18.
Deb, S., Médard, M., Choute, C.: Algebraic gossip: a network coding approach to optimal multiple rumor mongering. IEEE/ACM Trans. Inf. Theory 52(6), 2486–2507 (2006)MathSciNetCrossRefMATH
19.
Gasieniec, L., Kranakis, E., Pelc, A., Xin, Q.: Deterministic m2m multicast in radio networks. Theor. Comput. Sci. 362(1–3), 196–206 (2006)MathSciNetCrossRefMATH
20.
Ghaffari, M., Kantor, E., Lynch, N., Newport, C.: Multi-message broadcast with abstract mac layers and unreliable links. In: Proceedings of the 2014 ACM Symposium on Principles of Distributed Computing (PODC) (2014)
21.
Ghaffari, M., Lynch, N., Newport, C.: The cost of radio network broadcast for different models of unreliable links. In: Proceedings of the 32nd Symposium on Principles of Distributed Computing (PODC) (2013)
22.
Ghaffari, M., Newport, C.: Leader election in unreliable radio networks. In: Proceedings of the 43rd International Colloquium on Automata, Languages and Programming (ICALP) (2016)
23.
24.
Khabbazian, M., Kowalski, D.R.: Time-efficient randomized multiple-message broadcast in radio networks. In: Proceedings of the 30th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC)
25.
Kim, K.-H., Shin, K.G.: On accurate measurement of link quality in multi-hop wireless mesh networks. In: Proceedings of the 12th International Conference on Mobile Computing and Networking (MOBICOM) (2006)
26.
Kowalski, D.R., Mosteiro, M.A., Rouse, T.: Dynamic multiple-message broadcast: bounding throughput in the affectance model. In: Proceedings of the 10th ACM International Workshop on Foundations of Mobile Computing (2014)
27.
28.
Kuhn, F., Lynch, N., Newport, C.: The abstract mac layer. Distrib. Comput. 24(3), 187–206 (2011)CrossRefMATH
29.
Kuhn, F., Lynch, N., Newport, C., Oshman, R., Richa, A.W.: Broadcasting in unreliable radio networks. In: Proceedings of the 29th Symposium on Principles of Distributed Computing (PODC) (2010)
30.
Kuhn, F., Lynch, N., Oshman, R.: Distributed computation in dynamic networks. In: Proceeedings of the 42nd Symposium on Theory of Computing (STOC) (2010)
31.
Kuhn, F., Oshman, R.: Dynamic networks: models and algorithms. ACM SIGACT News 42(1), 82–96 (2011)CrossRef
32.
Lynch, N., Newport, C.: A (truly) local broadcast layer for unreliable radio networks. In: Proceedings of the 34th Symposium on Principles of Distributed Computing (PODC) (2015)
33.
Moscibroda, T., Wattenhofer, R.: The complexity of connectivity in wireless networks. In: Proceedings of the 25th Conference on Computer Communications (INFOCOM) (2006)
34.
Newport, C.: Radio network lower bounds made easy. In: Proceedings of the 28th International Symposium on Distributed Computing (DISC) (2014)
35.
Newport, C., Kotz, D., Yuan, Y., Gray, R.S., Liu, J., Elliott, C.: Experimental evaluation of wireless simulation assumptions. Simulation (2007)
36.
O’Dell, R., Wattenhofer, R.: Information dissemination in highly dynamic graphs. In: Proceedings of Workshop on Foundations of Mobile Computing (DIALM-POMC) (2005)
37.
Ramachandran, K., Sheriff, I., Belding, E., Almeroth, K.: Routing stability in static wireless mesh networks. In: Proceedings of the 8th International Conference on Passive and Active Network Measurement (2007)
38.
Srinivasan, K., Kazandjieva, M.A., Agarwal, S., Levis, P.: The \(\beta \)-factor: measuring wireless link burstiness. In: Proceedings of the 6th Conference on Embedded Networked Sensor System (2008)
39.
Yarvis, M.D., Conner, S.W., Krishnamurthy, L., Chhabra, J., Elliott, B., Mainwaring, A.: Real-world experiences with an interactive ad hoc sensor network. In: Proceedings of the Conference on Parallel Processing (2002)
Metadaten
Titel
Multi-message Broadcast in Dynamic Radio Networks
verfasst von
Mohamad Ahmadi
Fabian Kuhn
Copyright-Jahr
2017
Buch
Algorithms for Sensor Systems

Print ISBN: 978-3-319-53057-4

Electronic ISBN: 978-3-319-53058-1

Copyright-Jahr: 2017

DOI
https://doi.org/10.1007/978-3-319-53058-1_1