Distributed Size Estimation of Dynamic Anonymous Networks

Abstract — We consider the problem of estimating the size of dynamic anonymous networks, motivated by network main-tenance. The proposed algorithm is based on max-consensus information exchange protocols, and extends a previous algo-rithm for static anonymous networks. A regularization term is accounting for a-priori assumptions on the smoothness of the estimate, and we specifically consider quadratic regularization terms since they lead to closed-form solutions and intuitive design laws. We derive an explicit estimation scheme for a particular peer-to-peer service network, starting from its statistical model. To validate the accuracy of the algorithm, we perform numerical experiments and show how the algorithm can be implemented using finite precision arithmetics as well as small communication burdens. Index Terms — anonymous networks, dynamic networks, size estimation, sensor networks, distributed estimation. I