Minimalist counting in sensor networks (Noise helps)

Abstract

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-e..