In this article, we investigate the convergence behavior of two classes of gathering protocols with fixed circulant topologies using tools from dynamical systems. Given a fixed number of mobile entities moving in the Euclidean plane, we model a gathering protocol as a system of (linear) ordinary differential equations whose equilibria are exactly all possible gathering points. For a circulant topology, we derive a decomposition of the state space into stable invariant subspaces with different convergence rates. This decomposition is identical for every linear circulant gathering protocol. Only the convergence rates depend on the weights in the interaction graph. In the second part, we consider a normalized nonlinear version of the equation of motion that is obtained by scaling the speed of each entity. Again, we find a similar decomposition of the state space that is based on our findings in the linear case. In both situations, we also consider visibility preservation properties.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

On the Dynamical Hierarchy in Gathering Protocols with Circulant Topologies

  • Raphael Gerlach,
  • Sören von der Gracht,
  • Michael Dellnitz

摘要

In this article, we investigate the convergence behavior of two classes of gathering protocols with fixed circulant topologies using tools from dynamical systems. Given a fixed number of mobile entities moving in the Euclidean plane, we model a gathering protocol as a system of (linear) ordinary differential equations whose equilibria are exactly all possible gathering points. For a circulant topology, we derive a decomposition of the state space into stable invariant subspaces with different convergence rates. This decomposition is identical for every linear circulant gathering protocol. Only the convergence rates depend on the weights in the interaction graph. In the second part, we consider a normalized nonlinear version of the equation of motion that is obtained by scaling the speed of each entity. Again, we find a similar decomposition of the state space that is based on our findings in the linear case. In both situations, we also consider visibility preservation properties.