Almost uniform deployment of mobile agents in dynamic rings
Almost uniform deployment of mobile agents in dynamic rings
复制标题
动态环中移动代理的部署几乎统一
DOI：
10.1016/j.ic.2022.104949
复制
发表时间：
2022
影响因子：
1
通讯作者：
Yonghwan Kim
中科院分区：
文献类型：
--
作者：
Masahiro Shibata; Yuichi Sudo;Junya Nakamura;Yonghwan Kim
本文考虑动态环中移动的代理的几乎均匀部署问题，该问题要求除一个代理外的所有代理在环中均匀分布。在本文中，我们考虑这个问题的1-区间连通环，即其中一个环节可能会失去在每个时间步。集中在全局知识给代理，我们澄清问题的可解性和算法性能。首先，我们考虑知道节点数量n的代理。然后，我们证明了这个问题可以解决的O（k log n）每个代理的内存空间，O（n log k）轮，和总数量的O（k n）移动，其中k是代理的数量。接下来，我们考虑具有k知识的代理。然后，我们证明了这个问题可以解决每个代理的O（k log n）内存空间，O（n 2）轮，和O（n 2）移动的总数。
In this paper, we consider the almost uniform deployment problem of mobile agents in dynamic rings, which requires all agents other than one agent to spread uniformly in the ring. In this paper, we consider this problem in 1-interval connected rings, that is, one of the links may be missing at each time step. Focusing on global knowledge given to agents, we clarify the problem solvability and the algorithm performance. First, we consider agents with knowledge of the number n of nodes. Then, we show that the problem can be solved with O (k log n) memory space per agent, O (n log k) rounds, and a total number of O (k n) moves, where k is the number of agents. Next, we consider agents with knowledge of k. Then, we show that the problem can be solved with O (k log n) memory space per agent, O (n 2) rounds, and a total number of O (n 2) moves.