论文部分内容阅读
P2P(peer-to-peer)技术是未来重构分布式体系结构的关键技术,拥有广阔的应用前景。同时,随着P2P应用的广泛化与复杂化,将会有越来越多的应用所产生数据是随时间变化的。对于这些数据进行统计,将有助于用户分析这些数据的变化趋势并做出相应的决策。而聚集操作是统计方法中一个最为基本的操作,故在本文中将对P2P网络中时变数据的聚集方法进行研究。由于P2P网络具有大规模性、动态性、分散性等特点,使得在P2P网络中进行时变数据的聚集运算颇具挑战。本文针对这些挑战问题,主要进行如下几方面的研究:首先,由于P2P的大规模性,通过遍历每个节点来获取样本数据会出现处理时间过长、资源浪费较大等缺点。所以在本文中将利用随机采样的方式获取少量的样本数据,并利用这些样本数据来估计总体的聚集值。考虑到P2P网路的动态性等因素,本文利用全概率公式、Markov过程的收敛特性及Metropolis-Hastings等数学手段对动态网络中的均衡采样问题进行了深入研究,并首次提出了适应动态P2P网络的均衡采样算法——USTPF算法(Uniformly Sampling based on Total Probability Formula),同时我们利用理论与实验证明了该算法的正确性及有效性。其次,由于P2P网络中的数据是时变的,从而需要保证聚集运算中使用的所有样本数据均在时间上是有效的,这就要求时变数据的聚集算法能够在较短的时间区间内完成数据收集工作。为了达到上述目的,本文在均衡采样算法(USTPF算法)的基础上,利用中心极限定理、Chebyshev不等式等数学方法,首次构造出能够获得某一较短时间段内,P2P网络时变数据的近似聚集值的算法——AUS(Aggregation based on Uniformly Sampling)算法,同时本文利用理论与实验证明该算法在统计学中及实际应用中的意义。最后,由于P2P网络时变数据聚集值的历史信息同样十分重要,所以须解决如何在网络中存储时变数据聚集值的问题。针对该问题,本文提出了通过在网络中选取一部分节点构成档案节点集合,利用这些档案节点来存储时变数据聚集值的历史信息的方案,并给出了档案节点集合的选取算法——LCDS近似算法,通过理论证明与实验验证了该算法的正确性及有效性。