Minimalist counting in sensor networks (Noise helps)

• Published in: Ad hoc networks 2011-08, Vol.9 (6), p.987-997
• Main Authors: Baryshnikov, Y.M., Coffman, E.G., Kwak, K.J., Moran, Bill
• Format: Article
• Language: English
• Subjects: Algorithms; Counting; Cumulants; Estimates; Inclusion–exclusion formula; Intersections; Mathematical models; Minimalist counting; Networks; Noise; Sensing noise; Sensor networks; Sensors; Target counting
• ISSN: 1570-8705; 1570-8713
• DOI: 10.1016/j.adhoc.2010.08.010

We propose a novel algorithm for counting N indistinguishable objects, called targets, by a collection of sensors. We adopt a minimalist scenario where sensors are unaware of the (non-empty) intersections of sensing regions, and so simple addition of all sensor counts inflates estimates of the total number of targets. The multiple counting in intersections must be accounted for, but with nothing more than the sensor counts, this is clearly impossible. However, noise is typically present in the target counting of many, if not most, applications. We make the key observation that if there is a (target-dependent) noise source affecting all sensors simultaneously, then it couples those with non-empty intersections. Exploitation of this coupling allows us to extract multiple-counting statistics from stochastic correlation patterns, and hence to compute accurate estimates of N via the classical inclusion–exclusion formula. Cumulants are the correlation measures of choice. Our analysis brings out and resolves certain technicalities that arise in our statistical counting algorithm. Examples are worked out to show the potential of the new algorithm. The paper concludes with a discussion of alternative models and open problems.