Exploration of dynamic tori by mobile agents

摘要

Mobile agents (agents) are entities which can move autonomously in a networked system and execute actions at nodes they are visiting. One of the most fundamental problems of agents is exploration, which requires that each node should be visited by at least one agent. So far, researchers focus mainly on exploration of static networks. However, exploration of dynamic networks comes to be studied recently. In this paper, we consider exploration of a dynamic torus under some constraints on the dynamics (or topology changes). An n × n torus is considered as a collection of n row rings and n column rings. The constraints on the dynamics is that each the ring should be 1-interval connected, which allows at most one link is missing at any time in each the ring. On this n × n dynamic torus, we propose exploration algorithms with and without the link presence detection. With the link presence detection, an agent can detect which incident links are missing (if exist) before determining its next move. On the other hand, without the link presence detection, an agent has to determine its next move without knowing which incident links are missing, which makes the agent stay on the same node when the link necessary to the move is missing. We prove for exploration of the n × n dynamic torus that, without the link presence detection, n + 1 agents are necessary and sufficient, and, with the link presence detection, n/2 + 1 agents are necessary and sufficient.