Distributed Cardinality Estimation in Anonymous Networks
2013 (English)In: IEEE Transactions on Automatic Control, ISSN 0018-9286, E-ISSN 1558-2523, Vol. 59, no 3, 645-659 p.Article in journal (Refereed) Published
We consider estimation of network cardinality by distributed anonymous strategies relying on statistical inference methods. In particular, we focus on the relative Mean Square Error (MSE) of Maximum Likelihood (ML) estimators based on either the maximum or the average of M-dimensional vectors randomly generated at each node. In the case of continuous probability distributions, we show that the relative MSE achieved by the max-based strategy decreases as, independently of the used distribution, while that of the average-based estimator scales approximately as. We then introduce a novel strategy based on the average of M-dimensional vectors locally generated from Bernoulli random variables. In this case, the ML estimator, which is the Least Common Multiple (LCM) of the denominators of the irreducible fractions corresponding to the elements of the average vector, leads to an MSE which goes exponentially to zero as increases. We then discuss the effects of finite-precision arithmetics in practical dynamic implementations. Numerical experiments reveal that the MSE of the strategy based on Bernoulli trials is two order of magnitude smaller than that based on continuous random variables, at a price of one order of magnitude slower convergence time.
Place, publisher, year, edition, pages
2013. Vol. 59, no 3, 645-659 p.
anonymous networks, consensus, distributed estimation, number of agents, number of nodes, privacy-preservation, sensor networks, size estimation
Electrical Engineering, Electronic Engineering, Information Engineering
IdentifiersURN: urn:nbn:se:kth:diva-138334DOI: 10.1109/TAC.2013.2287113ISI: 000332037800007ScopusID: 2-s2.0-84897690932OAI: oai:DiVA.org:kth-138334DiVA: diva2:680902
FunderEU, FP7, Seventh Framework Programme, 257462 HYCON2Swedish Research CouncilKnut and Alice Wallenberg Foundation
QC 201402282013-12-182013-12-182014-03-28Bibliographically approved