Communication Problems for Mobile Agents Exchanging Energy
Communication Problems for Mobile Agents Exchanging Energy
复制标题
移动代理交换能量的通信问题
DOI：
10.1007/978-3-319-48314-6_18
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
W. Rytter
中科院分区：
文献类型：
--
作者：
J. Czyzowicz;K. Diks;J. Moussi;W. Rytter
一组移动代理部署在边缘加权网络的节点中。特工最初拥有大量能量，所有特工可能都不同。代理在网络中移动时消耗的能量与所经过的距离成正比。网络的某些节点可以保存访问它们的代理获取的信息。会议代理可以交换当前拥有的信息以及任意数量的能量。当某些网络节点最初持有的信息必须传递给其他一些节点和/或代理时，我们会考虑通信问题。本文讨论了两个通信问题：数据传输和聚合广播。这些问题是针对完全了解实例的集中式调度程序提出的。众所周知，在没有能量交换的情况下，即使网络是一条线，这两个问题也是NP完全问题。在本文中，我们证明，如果允许代理交换能量，这两个问题在树上都有线性时间解。另一方面，对于一般的无向图和有向图，我们表明这些问题是 NP 完全的。
A set of mobile agents is deployed in the nodes of an edge-weighted network. Agents originally possess amounts of energy, possibly different for all agents. The agents travel in the network spending energy proportional to the distance traversed. Some nodes of the network may keep information which is acquired by the agents visiting them. The meeting agents may exchange currently possessed information, as well as any amount of energy. We consider communication problems when the information initially held by some network nodes have to be communicated to some other nodes and/or agents. The paper deals with two communication problems: data delivery and convergecast. These problems are posed for a centralized scheduler which has full knowledge of the instance. It is already known that, without energy exchange, both problems are NP-complete even if the network is a line. In this paper we show that, if the agents are allowed to exchange energy, both problems have linear-time solutions on trees. On the other hand for general undirected and directed graphs we show that these problems are NP-complete.