Approximate Cardinality Estimation (ACE) in large-scale Internet of Things deployments

IoT (Internet of Things) deployments have been used in many diverse applications in increasingly large numbers, usually composed of embedded sensors, computational units, and actuators. One central problem with IoT applications is that we frequently need to query the number of nodes according to certain requirements, or filters. For example, a user may want to query the number of nodes that are currently actively sensing data, or having data above a threshold. Conventional methods typically require each active node to report their status, leading to a total communication overhead that is at least proportional to the network size. In this paper, we study the problem of deployment size estimation by investigating probabilistic methods for processing queries, where we only try to obtain approximate estimates within desired confidence intervals. Our methods are different with other probabilistic methods, such as sampling, in that our approach is based on the well-known birthday paradox in statistics. Hence, our methods provide a different solution that can be combined or used to enhance existing methods. We demonstrate through extensive simulations that their overhead is considerably lower than conventional methods, usually by an order of magnitude.