Communication and location discovery in geometric ring networks

作     者：Gasieniec, Leszek Jurdzinski, Tomasz Martin, Russell Stachowiak, Grzegorz 

作者机构：Univ Liverpool Dept Comp Sci Ashton BldgAshton St Liverpool L69 3BX Merseyside England Univ Wroclaw Inst Comp Sci Przesmyckiego 20 PL-50383 Wroclaw Poland 

出 版 物：《INFORMATION AND COMPUTATION》 (信息与计算)

年 卷 期：2019年第266卷

页      面：19-48页

核心收录：

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 08[工学] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：Polish National Science Centre [DEC-2012/06/M/ST6/00459, 2017/25/B/ST6/02010] Networks Sciences and Technology (NeST) Initiative in the School of Electrical Engineering, Electronics and Computer Science at the University of Liverpool 

主　　题：Mobile robots Distributed algorithms Location discovery Boundary patrolling Combinatorial structures 

摘      要：We study a distributed coordination mechanism for uniform agents located on a circle. The agents perform their actions in synchronized rounds. At the beginning of each round an agent chooses the direction of its movement from clockwise, anticlockwise, or idle, and moves at unit speed during this round. Agents are not allowed to overpass, i.e., when an agent collides with another it instantly starts moving with the same speed in the opposite direction (without exchanging any information with the other agent). However, at the end of each round each agent has access to limited information regarding its trajectory of movement during this round. We assume that n mobile agents are initially located on a circle unit circumference at arbitrary but distinct positions unknown to other agents. The agents are equipped with unique identifiers from a fixed range. The location discovery task to be performed by each agent is to determine the initial position of every other agent. Our main result states that, if the only available information about movement in a round is limited to distance between the initial and the final position, then there is a superlinear lower bound on time needed to solve the location discovery problem. Interestingly, this result corresponds to a combinatorial symmetry breaking problem, which might be of independent interest. If, on the other hand, an agent has access to the distance to its first collision with another agent in a round, we design an asymptotically efficient and close to optimal solution for the location discovery problem. Assuming that agents are anonymous (there are no IDs distinguishing them), our solution applied to randomly chosen IDs from appropriately chosen range gives an (almost) optimal algorithm, improving upon the complexity of previous randomized results. (C) 2018 Published by Elsevier Inc.