Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Distributed Cardinality Estimation in Anonymous Networks
KTH, School of Electrical Engineering (EES), Automatic Control. KTH, School of Electrical Engineering (EES), Centres, ACCESS Linnaeus Centre.
Univ Padua, Dept Informat Engn, I-35131 Padua, Italy.
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
Abstract [en]

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.
Keyword [en]
anonymous networks, consensus, distributed estimation, number of agents, number of nodes, privacy-preservation, sensor networks, size estimation
National Category
Electrical Engineering, Electronic Engineering, Information Engineering
Identifiers
URN: urn:nbn:se:kth:diva-138334DOI: 10.1109/TAC.2013.2287113ISI: 000332037800007Scopus ID: 2-s2.0-84897690932OAI: oai:DiVA.org:kth-138334DiVA: diva2:680902
Funder
EU, FP7, Seventh Framework Programme, 257462 HYCON2Swedish Research CouncilKnut and Alice Wallenberg Foundation
Note

QC 20140228

Available from: 2013-12-18 Created: 2013-12-18 Last updated: 2017-12-06Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Varagnolo, DamianoSchenato, Luca
By organisation
Automatic ControlACCESS Linnaeus Centre
In the same journal
IEEE Transactions on Automatic Control
Electrical Engineering, Electronic Engineering, Information Engineering

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 57 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf