Cardinality Estimation Algorithm in Large-Scale Anonymous Wireless Sensor Networks

Ahmed S. Douik, Salah A. Aly, Tareq Y. Al-Naffouri, Mohamed-Slim Alouini

Research output: Chapter in Book/Report/Conference proceedingConference contribution


Consider a large-scale anonymous wireless sensor network with unknown cardinality. In such graphs, each node has no information about the network topology and only possesses a unique identifier. This paper introduces a novel distributed algorithm for cardinality estimation and topology discovery, i.e., estimating the number of node and structure of the graph, by querying a small number of nodes and performing statistical inference methods. While the cardinality estimation allows the design of more efficient coding schemes for the network, the topology discovery provides a reliable way for routing packets. The proposed algorithm is shown to produce a cardinality estimate proportional to the best linear unbiased estimator for dense graphs and specific running times. Simulation results attest the theoretical results and reveal that, for a reasonable running time, querying a small group of nodes is sufficient to perform an estimation of 95% of the whole network. Applications of this work include estimating the number of Internet of Things (IoT) sensor devices, online social users, active protein cells, etc.
Original languageEnglish (US)
Title of host publicationProceedings of the International Conference on Advanced Intelligent Systems and Informatics 2017
PublisherSpringer Nature
Number of pages10
ISBN (Print)9783319648606
StatePublished - Aug 31 2017

Bibliographical note

KAUST Repository Item: Exported on 2020-10-01


Dive into the research topics of 'Cardinality Estimation Algorithm in Large-Scale Anonymous Wireless Sensor Networks'. Together they form a unique fingerprint.

Cite this