摘要: 计算机网络呈现出动态、大规模和自主组织的特征,使用分布式方法估计具有某种特征的节点数量是网络领域的重要问题。该文研究了基于抽样理论的规模估计方法,该方法具有良好的可扩展性,可以较好地应用在非结构网络环境中。分析基于采样冲突和基于二项式分布的2个算法,实验结果表明基于采样冲突算法的开销小、精度高。当总采样量不变时,基于分布的估算方法采用大样本比小样本策略的估计精度要高。
关键词:
规模估计,
抽样方法,
非结构网络
Abstract: Network nowadays displays dynamic, scale and self-organizing characteristics. How to estimate the number of certain kind of nodes of the network in distributed manner is important. This paper studies sampling-based size estimation methods which are robust and scalable. The methods are suitable to be used in unstructured network environment. Two algorithms are researched, which are based on sample-collision and binomial-distribution. The experiments show that sample-collision based algorithm has lower cost and higher veracious. When sampling few large-sample, distribution based algorithm is better.
Key words:
size estimation,
sampling method,
unstructured network
中图分类号:
曹 佳. 基于多次采样的规模估计算法[J]. 计算机工程, 2009, 35(1): 98-100.
CAO Jia. Size Estimation Algorithms Based on Multiple Sampling[J]. Computer Engineering, 2009, 35(1): 98-100.