基于聚类划分的P2P,,流媒体系统构建_P2P流媒体广告
摘要：对常见的P2P 流媒体系统进行分析研究，提出了基于聚类划分的P2P 流媒体系统，并根据Canopy聚类情况得出K-n 模型和K-n-t模型，对这两种模型的网络特征作了理论分析和比较并指出适应范围。
关键词：对等网络 流媒体 聚类
注：本文系浙江传媒学院校级课题“基于P2P对等网络的视频点播系统”的研究成果。
Modeling of cluster structure based on P2P streaming systems
Qiu Rongtai Yang Xi
Abstract: A research of normal structure based on P2P streaming systems． Two types of models，named k- n model and k-n-t model，were announced，and then compared and analyzed the network characteristics theoretically. Present its fitable situations.
Key words: peer-to-peer network; media streaming; clustering
随着P2P流媒体PPStream、SopCast、PPlive 的广泛使用，其服务质量要求也日益突出，通过实验表明，PPlive的播放启动延迟在10—120 S 之间，播放时间甚至延迟到140 S，远逊于电视直播服务［2］。如何提高P2P 系统的服务质量是当前研究的一个重点。
1.常见的P2P流媒体系统
为提高系统的服务质量，现流行的P2P 流媒体系统，如NICE、PPLive、NetTube 等，大多依据节点的能力、网络距离等将节点进行归类划分。例如，PPLive 根据节点能力来选代理网关节点，并构建由代理网关为中心节点的“域”所组成的双层覆盖网络结构。NICE 使用层和簇的概念，将节点归类到不同层次的“簇”中，由“簇头”节点负责数据的传输。NetTube 则根据用户节目兴趣度将节点加入到不同的“群集”中，通过高效的视频索引和检索策略显著地提高了视频播放质量。因此，本文在归纳和比较现有的P2P 流媒体系统结构的基础上，提出基于聚类划分的P2P 流媒体系统并进行建模研究。根据聚类结果是否重叠划分，分别提出了K-n 模型和K-n-t 模型两种结构模型。对这两种结构模型作了理论分析比较，指出了各自的应用场景，对设计和实现P2P 流媒体系统的具有重要的参考意义。
2.基于聚类划分的P2P 流媒体系统
P2P 流媒体系统主要包括以下三方面:
中心节点master的选择: 中心节点对应于P2P流媒体系统结构划分中的头节点，起到管理与调试的作用。
2) 区域划分选择: 即普通节点如何从已知的中心节点集合中选择某个中心节点，并加入到其所在的划分中。
3) 重叠划分: 即根据节点是否同时存在于多个划分区域中，形成非重叠或重叠分区结构。
设P2P 流媒体系统中所有节点的集合表示为A = { a0，a1，…aN － 1} ，N 是节点总数。中心节点集合表示为CN = { c0，c1，…，c k － 1} ，k 是中心节点总数，也是系统中社区的数量。将ci所在社区Ci中所有节点的集合表示为Ci = { ci，b0，b1，…，b ni － 1} i∈{ 0，1，…，k － 1} ，bni是社区Ci中的普通节点，ni是该社区中普通节点的数量，根据以上定义可得A = C0∪C1∪…∪Ck － 1。普通节点bni依据Canopy聚类方法选择加入到社区Ci中。
2.1 Canopy思想及算法
Canopy聚类分两个阶段执：第一步就是粗糙地、快速和近似地把数据分成一些重叠的子集，称之为罩盖（Canopy）；然后对Canopy内的点用精确的计算方法再聚类。
2.2 Canopy算法
创建Canopy是以某一数据点为初始中心，用一种相似度计算方法找出在一个阈值范围内的数据点集合。在创建Canopy的过程中，所有的数据点都必须出现在至少一个Canopy中，对于每一个聚类，存在至少一个Canopy能够包含这个聚类的所有元素。当创建Canopy的条件都满足时，任何两个不处于同一个Canopy的点将不可能属于同一聚类，所以在第二阶段时不需要计算不处于同一个Canopy的点之间的距离，从而大大减少了计算量。
第一阶段由于数据量非常大，首先随机设置一个中心点，采用一种比较简单的计算方法找到中心点周围区域的所有数据点构成一个“Canopy”，然后再寻找下一个中心点周围的区域，同样也形成一个“Canopy”，一直到找遍中心点集合中所有数据点的聚类为止。为了保证所有的点都存在于相应的Canopy中，设置的中心点范围应该尽可能的广，范围的确定影响聚类的精确度，可以采用了两个距离阈值T1，T2（T1≥T2）。创建Canopy的步骤为：
(1) 将要划分的数据都放进一个集合中，作为中心点备选；
(2) 随机选取集合中一个点作为中心点，把与中心点距离小于等于T1的点放进Canopy，从中心点集合中删除与中心点距离小于等于T2的点（包括原来的中心点）；
(3) 检查中心点集合是否已是空集，如果是则终止操作；如果不是空集，重复执行步骤(2)。
图2-1 基于以上的步骤创建的一些Canopy
Fig 2-1 Canopy created based of steps
图2-1是根据以上步骤创建的一些Canopy。图中的圈代表罩盖，首先点A是随机选择的中心点，选择一种花费少的，近似的距离计算方法计算点之间的距离，把与A点距离小于等于T1的点放进Canopy，图中共有7个点放入第一个Canopy中，然后从中心点集合中删除与中心点距离小于等于T2的点（包括原来的中心点）；图中所示为A附近的6个点，依次类推，创建“Canopy”B，C，D，E的过程与A一样。依据图可以得出，如果数据点比较密集，则创建出的Canopy可能是重叠的，图中共分为5个聚类，对于每一个聚类，至少存在一个Canopy能够完全包括这个聚类，而精确的距离计算方法只用于同一个Canopy的数据点，因为Canopy中的点远远少于整个数据集的点，相比之下其计算量是非常小的。除了用一种花费较少的距离计算方法聚类以外，仍然用精确的方法聚类Canopy中的数据，这个方法在降低计算成本的情况下仍然保证了计算结果的准确性。