论文标题
网格上的近视发光机器人的异步最大独立集算法
An Asynchronous Maximum Independent Set Algorithm by Myopic Luminous Robots on Grids
论文作者
论文摘要
我们考虑在网格网络上使用移动近视发光机器人构建最大独立设置的问题，该网络的大小是有限但对机器人未知的。在此设置中，机器人从网格的一个角度从一个角度进入网格网络，最终必须在网格节点上传播它们，以使占用位置形成网络的最大独立集。我们假设机器人是异步，匿名，沉默的，并且它们执行相同的分布式算法。在本文中，我们提出了两种算法：第一个算法假定每个机器人的浅色数量为三个，可见范围为两个，但对每个节点使用额外的强端口假设。为了删除这一假设，第二个假设每个机器人的浅色数量为7，可见范围为三个。在这两种算法中，动作的数量为$ o（n（l+l））$步骤，其中$ n $是节点的数量，$ l $和$ l $是网格尺寸。
We consider the problem of constructing a maximum independent set with mobile myopic luminous robots on a grid network whose size is finite but unknown to the robots. In this setting, the robots enter the grid network one-by-one from a corner of the grid, and they eventually have to be disseminated on the grid nodes so that the occupied positions form a maximum independent set of the network. We assume that robots are asynchronous, anonymous, silent, and they execute the same distributed algorithm. In this paper, we propose two algorithms: The first one assumes the number of light colors of each robot is three and the visible range is two, but uses additional strong assumptions of port-numbering for each node. To delete this assumption, the second one assumes the number of light colors of each robot is seven and the visible range is three. In both algorithms, the number of movements is $O(n(L+l))$ steps where $n$ is the number of nodes and $L$ and $l$ are the grid dimensions.
