Target counting using binary proximity sensors via cluster identification

This paper proposes an algorithm for counting the number of distinct targets using binary proximity sensors randomly deployed for target detection. This paper focuses on the fact that sensors simultaneously detecting a target should be in close proximity to each other. Thus, if multiple targets exist in a region of watch, sensors detecting them at a specific time are divided into several clusters, and each cluster represents one target. Based on such consideration, this paper uses the number of clusters of target-detecting sensors as an estimator of the number of distinct targets. To find clusters of sensors, the notion of mutual nearest neighbor (MNN) is employed. The MNN is a set of target-detecting sensors, where the largest distance within the set is smaller than the distance to any target-detecting sensor outside the set. The notion of the MNN yields a polynomial-time algorithm for partitioning a set of target-detecting sensors into several clusters. Simulation experiments verify that the proposed algorithm gives very precise estimates of the number of distinct targets if sensors are densely deployed.