Anzeige
Erschienen in:
2017 | OriginalPaper | Buchkapitel
Energy-Optimal Broadcast in a Tree with Mobile Agents
verfasst von : Jerzy Czyzowicz, Krzysztof Diks, Jean Moussi, Wojciech Rytter
Erschienen in: Algorithms for Sensor Systems
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
A set of k mobile agents is deployed at the root r of a weighted, n-node tree T. The weight of each tree edge represents the distance between the corresponding nodes along the edge. One node of the tree, the source s, possesses a piece of information which has to be communicated (broadcasted) to all other nodes using mobile agents. An agent visiting a node, which already possesses the information, automatically acquires it and communicates it to all nodes subsequently visited by this agent. The process finishes when the information is transferred to all nodes of the tree.
The agents spend energy proportionally to the distance traversed. The problem considered in this paper consists in finding the minimal total energy, used by all agents, needed to complete the broadcasting. We give an \(O(n \log n)\) time algorithm solving the problem. If the number of agents is sufficiently large (at least equal to the number of leaves of T), then our approach results in an O(n) time algorithm.
When the source of information s is initially at the root r, our algorithm solves the problem of searching the tree (exploring it) by a set of agents using minimal energy. It is known that, even if the tree is a line, the broadcasting problem and the search problem are NP-complete when the agents may be initially placed at possibly many distinct arbitrary positions.