Estimation of a Population Size in Large-Scale Wireless Sensor Networks

Efficient estimation of population size is a common requirement for many wireless sensor network applications. Examples include counting the number of nodes alive in the network and measuring the scale and shape of physically correlated events. These tasks must be accomplished at extremely low overhead due to the severe resource limitation of sensor nodes, which poses a challenge for large-scale sensor networks. In this article we design a novel measurement technique, FLAKE based on sparse sampling that is generic, in that it is applicable to arbitrary wireless sensor networks (WSN). It can be used to efficiently evaluate system size, scale of event, and other global aggregating or summation information of individual nodes over the whole network in low communication cost. This functionality is useful in many applications, but hard to achieve when each node has only a limited, local knowledge of the network. Therefore, FLAKE is composed of two main components to solve this problem. One is the Injected Random Data Dissemination (Sampling) method, the other is sparse sampling algorithm based on Inverse Sampling, upon which it improves by achieving a target variance with small error and low communication cost. FLAKE uses approximately uniform random data dissemination and sparse sampling in sensor networks, which is an unstructured and localized method. At last we provide experimental results demonstrating the effectiveness of our algorithm on both small-scale and large-scale WSNs. Our measurement technique appears to be the practical and appropriate choice.