基于自适应随机行走的可扩展无偏抽样方法

摘要：

针对非结构化P2P系统中可扩展的快速无偏抽样问题,提出了一种基于多个peer自适应随机行走的抽样方法SMARW.在该方法中,基于代理随机行走选择一组临时的peer执行抽样过程,一次产生一组可调数目的抽样节点,提高了抽样速度,选择每次产生的抽样节点作为临时peer进行新的抽样过程,这种简单的方法可以保证系统具有近似最优的系统负载均衡程度.同时,SMARW利用自适应的分布式随机行走修正过程提高抽样过程的收敛速度.理论分析和模拟测试表明,SMARW方法具有较高的无偏抽样能力以及近似最优的系统负载均衡程度.

关键词：无偏抽样、非结构化P2P系统、随机算法、可扩展性

所属期刊栏目：20

分类号：TP393(计算技术、计算机技术)

资助基金：the National Natural Science Foundation of China under Grant Nos.60873215, 60621003;the National Basic Research Program of China under Grant No.2005CB321801 国家重点基础研究发展计划973;the Specialized Research Fund for the Doctoral Program of Higher Education of China No.200899980003;the Foundation for the Author of National Excellent Doctoral Dissertation of China under Grant No.200141;the Graduate Research Innovation Fund of NUDT of China under Grant No.B080602

在线出版日期：2009-05-06（万方平台首次上网日期，不代表论文的发表时间）

页数：共14页

页码：630-643