Broadcast with Energy-Exchanging Mobile Agents Distributed on a Tree

obile 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.