Minimalist counting in sensor networks (Noise helps)

Y. M. Baryshnikov, E. G. Coffman, K. J. Kwak, Bill Moran

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish
Pages (from-to)987-997
Number of pages11
JournalAd Hoc Networks
Issue number6
Publication statusPublished - Aug 1 2011
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications


Dive into the research topics of 'Minimalist counting in sensor networks (Noise helps)'. Together they form a unique fingerprint.

Cite this