Fast size approximation of a radio network in beeping model

摘要

In a single-hop radio network, nodes can communicate with each other by broadcasting to a shared wireless channel. In each time slot, all nodes receive feedback from the channel depending on the number of transmitters. In the Beeping Model, each node learns whether zero or at least one node have transmitted. In such a model, a procedure estimating the size of the network can be used for efficiently solving the problems of leader election or conflict resolution. We introduce a time-efficient uniform algorithm for size estimation of single-hop networks. With probability at least 1 - 1/f our solution returns (1 + epsilon)-approximation of the network size n within O (loglogn + log f/epsilon(2)) time slots. We prove that the algorithm is asymptotically time-optimal in a class of uniform algorithms. (C) 2017 Elsevier B.V. All rights reserved.