Space-efficient self-stabilizing counting population protocols on mobile sensor networks
Space-efficient self-stabilizing counting population protocols on mobile sensor networks
复制标题
DOI：
10.1016/j.tcs.2014.07.028
复制
发表时间：
2014-10-02
影响因子：
1.1
通讯作者：
Wada, Koichi
中科院分区：
文献类型：
--
作者：
Izumi, Tomoko;Kinpara, Keigo;Wada, Koichi
在这项研究中，我们考虑了一个被动移动传感器网络的自稳定计数问题，该网络最初由Beauquier等人提出[13]，其中基站必须对网络中的传感器数量进行计数。自稳定计数意味着基站最终从每个传感器具有任意初始状态的配置中计数系统中传感器的确切数量。在本文中，我们专注于传感器状态的数量的自稳定计数问题的空间复杂性。我们提出了两个自稳定计数协议。给定传感器数量的已知上限P，第一协议使用2P个传感器状态执行计数，并且在公平执行中其收敛时间为O（logn），其中n是传感器的实际数量。第二个协议只使用3。[P/2]传感器状态，但假设全局公平性，这是比标准公平性更强的假设。最好的协议需要4P个状态，而相应的下限是P，所以我们的结果减少了P和4P之间的可行性差距差距。(C)2014爱思唯尔有限公司版权所有。
In this study, we consider a self-stabilizing counting problem for a passively-mobile sensor network with a base station originally proposed by Beauquier et al. [13], where the base station must count the number of sensors in the network. Self-stabilizing counting means that the base station eventually counts the exact number of sensors in the system from the configuration where each sensor has an arbitrary initial state. In this paper, we focus on the space complexity of the self-stabilizing counting problem in terms of the number of sensor states. We propose two self-stabilizing counting protocols. Given a known upper bound P on the number of sensors, the first protocol performs counting using 2P sensor states and its convergence time is O (logn) in fair executions, where n is the actual number of sensors. The second protocol uses only 3. [P/2] sensor states but assumes the global fairness, which is an assumption stronger than the standard fairness. The best known protocol requires 4P states while the corresponding lower bound is P, so our result reduces the gap of the feasibility between P and 4P. (C) 2014 Elsevier B.V. All rights reserved.