Top

Published in:

2018 | OriginalPaper | Chapter

Broadcast with Energy-Exchanging Mobile Agents Distributed on a Tree

Authors : Jurek Czyzowicz, Krzysztof Diks, Jean Moussi, Wojciech Rytter

Published in: Structural Information and Communication Complexity

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Mobile agents are deployed at selected nodes of an edge-weighted tree network. Each agent originally possesses an amount of energy, possibly different for all agents. Initially, in a given source node of the network is placed a piece of information (data packet) that must be broadcast to all other nodes. Such transfer of the packet needs to be achieved with aid of collaborating mobile agents, which may transport copies of the packet to all nodes.

Agents travel in the network spending energy proportionally to the distance traversed. They can stop only at network nodes. If two agents are present at a node at the same time, they can exchange any amount of currently possessed energy. Our goal is to verify if there exists a sequence of agents’ movements (a schedule) and energy exchanges between meeting agents, which results in the packet reaching all nodes of the tree network.

Our algorithm produces an optimal centralized scheduler as we assume that the central authority knows everything about the network and controls the movement of the agents, which do not need to possess any knowledge. In this sense it is a semi-distributed algorithm.

The important part of our algorithm uses dynamic programming in order to compute an optimal agents migration flow of every edge of the network, i.e. the number of agents traversing every edge in each direction. The approach is far from being straightforward, as its correctness is based on multiple complex interactions between the subtrees obtained by removal of any given edge.

It is known that, if energy exchange is not allowed, the broadcasting problem for trees (even for lines) is NP-complete.

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now

previous chapter Deterministic Distributed Ruling Sets of Line Graphs

next chapter A Deterministic Distributed 2-Approximation for Weighted Vertex Cover in Rounds

Anaya, J., Chalopin, J., Czyzowicz, J., Labourel, A., Pelc, A., Vaxès, Y.: Collecting information by power-aware mobile agents. In: Aguilera, M.K. (ed.) DISC 2012. LNCS, vol. 7611, pp. 46–60. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-33651-5_4CrossRef

Albers, S., Henzinger, M.R.: Exploring unknown environments. SIAM J. Comput. 29(4), 1164–1188 (2000)MathSciNetCrossRef

Awerbuch, B., Goldreich, O., Peleg, D., Vainish, R.: A trade-off between information and communication in broadcast protocols. J. ACM 37(2), 238–256 (1990)MathSciNetCrossRef

Annamalai, V., Gupta, S.K.S., Schwiebert, L.: On tree-based convergecasting in wireless sensor networks. IEEE Wirel. Commun. Netw. 3, 1942–1947 (2003)

Averbakh, I., Berman, O.: A heuristic with worst-case analysis for minimax routing of two traveling salesmen on a tree. Discr. Appl. Math. 68, 17–32 (1996)CrossRef

Bärtschi, A., Chalopin, J., Das, S., Disser, Y., Geissmann, B., Graf, D., Labourel, A., Mihalák, M.: Collaborative delivery with energy-constrained mobile robots. In: Suomela, J. (ed.) SIROCCO 2016. LNCS, vol. 9988, pp. 258–274. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-48314-6_17CrossRef

Bärtschi, A., Chalopin, J., Das, S., Disser, Y., Graf, D., Hackfeld, J., Penna, P.: Energy-efficient delivery by heterogeneous mobile agents. In: STACS , pp. 10:1–10:14 (2017)

Bärtschi, A.: Efficient Delivery with Mobile Agents (Ph.D. thesis), ETH Zurich (2017)

Baeza-Yates, R.A., Schott, R.: Parallel searching in the plane. Comput. Geom. 5, 143–154 (1995)MathSciNetCrossRef

10.

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. J. Comput. Syst. Sci. 45(1), 104–126 (1992)MathSciNetCrossRef

11.

Chalopin, J., Jacob, R., Mihalák, M., Widmayer, P.: Data delivery by energy-constrained mobile agents on a line. In: Esparza, J., Fraigniaud, P., Husfeldt, T., Koutsoupias, E. (eds.) ICALP 2014. LNCS, vol. 8573, pp. 423–434. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-43951-7_36CrossRef

12.

Czyzowicz, J., Diks, K., Moussi, J., Rytter, W.: Energy-optimal broadcast in a tree with mobile agents. In: Fernández Anta, A., Jurdzinski, T., Mosteiro, M.A., Zhang, Y. (eds.) ALGOSENSORS 2017. LNCS, vol. 10718, pp. 98–113. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-72751-6_8CrossRef

13.

Czyzowicz, J., Diks, K., Moussi, J., Rytter, W.: Communication problems for mobile agents exchanging energy. In: Suomela, J. (ed.) SIROCCO 2016. LNCS, vol. 9988, pp. 275–288. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-48314-6_18CrossRefMATH

14.

Das, S., Dereniowski, D., Karousatou, C.: Collaborative exploration by energy-constrained mobile robots. In: Scheideler, C. (ed.) Structural Information and Communication Complexity. LNCS, vol. 9439, pp. 357–369. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-25258-2_25CrossRef

15.

Dynia, M., Korzeniowski, M., Schindelhauer, C.: Power-aware collective tree exploration. In: Grass, W., Sick, B., Waldschmidt, K. (eds.) ARCS 2006. LNCS, vol. 3894, pp. 341–351. Springer, Heidelberg (2006). https://doi.org/10.1007/11682127_24CrossRef

16.

Fraigniaud, P., Gasieniec, L., Kowalski, D.R., Pelc, A.: Collective tree exploration. In: Farach-Colton, M. (ed.) LATIN 2004. LNCS, vol. 2976, pp. 141–151. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-24698-5_18CrossRef

17.

Frederickson, G., Hecht, M., Kim, C.: Approximation algorithms for some routing problems. SIAM J. Comput. 7, 178–193 (1978)MathSciNetCrossRef

18.

Toth, P., Vigo, D.: Vehicle Routing. Problems, Methods and Applications. MOS-SIAM series on Optimization, 2nd edn. (2014)

Title: Broadcast with Energy-Exchanging Mobile Agents Distributed on a Tree
Authors: Jurek Czyzowicz
Krzysztof Diks
Jean Moussi
Wojciech Rytter
Publisher: Springer International Publishing
Book: Structural Information and Communication Complexity
Print ISBN: 978-3-030-01324-0

Electronic ISBN: 978-3-030-01325-7

Copyright Year: 2018
DOI: https://doi.org/10.1007/978-3-030-01325-7_20

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner