TY - GEN

T1 - Cardinality Estimation Algorithm in Large-Scale Anonymous Wireless Sensor Networks

AU - Douik, Ahmed S.

AU - Aly, Salah A.

AU - Al-Naffouri, Tareq Y.

AU - Alouini, Mohamed-Slim

N1 - KAUST Repository Item: Exported on 2020-10-01

PY - 2017/8/31

Y1 - 2017/8/31

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

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

UR - http://hdl.handle.net/10754/625750

UR - https://link.springer.com/chapter/10.1007%2F978-3-319-64861-3_53

UR - http://www.scopus.com/inward/record.url?scp=85029476969&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-64861-3_53

DO - 10.1007/978-3-319-64861-3_53

M3 - Conference contribution

SN - 9783319648606

SP - 569

EP - 578

BT - Proceedings of the International Conference on Advanced Intelligent Systems and Informatics 2017

PB - Springer Nature

ER -