On size estimation protocols for Sensor Networks

In this paper we discuss a two-phase algorithm for estimating the size of a wireless network consisting of weak devices, such as Wireless Sensor Networks (WSN). The main idea is based on employing randomly generated identifiers. In the first phase of the algorithm we use the properties of order statistics and calculate an approximate estimator of the number of nodes. In the second phase we use this estimator and a series of Bernoulli independent trials in order to get a more precise estimator. We discuss the precision of the algorithm and we show that using a little more than 100 bytes of memory ensures 20% precision for networks consisting of up to 10⁹ nodes. We also prove some lower bounds for memory requirements. We compare our algorithm with HyperLogLog and Extrema Propagation algorithms. Finally, we show that the communication complexity of our algorithm is of order O(log n) where n is the network size.