基于P2P的短视频点播相似度分享系统

李 彦，张 华

(重庆理工大学计算机科学与工程学院，重庆 400054)

近年来，以UGC(user generated content)为特点的视频分享方式已成为网络视频的重要应用之一。目前，视频网站不仅仅能给用户提供视频，也允许用户上传一定长度的视频(时长一般不超过10 min)，以供其他用户分享。当用户在观看视频时，就是一个“消费者”，而当用户上传视频供其他用户分享时，又是一个“生产者”。传统的短视频采用客户/服务器(C/S)方式向用户提供视频。C/S的优点是用户的点播响应快，但是，当用户规模较大时，不仅增加了缓存时间，更增加了服务器带宽压力，直接影响了点播用户的QoE。

随着网络规模的不断扩张，使得P2P共享系统得到广泛的应用和可持续的发展［1］。P2P系统用户在分享其他用户节点视频流的同时，也贡献自己的带宽给其他用户节点。已有的视频直播系统 Coolstreaming［2］和点播系统 PPS、PPLive［3］等都是采用P2P方式实现。这类系统具备良好的可扩展性能，与传统的C/S系统相比，其服务器带宽消耗有所降低［3］。因此，本文构建的SShare系统也引入P2P思想。

文献［4］通过tracking方式对YouTube进行研究，提出了一种“视频服务器+P2P”的在线视频分享系统NetTube。仿真实验表明，引入P2P技术后可以降低服务器带宽消耗约70%。本文通过把用户的点播相似度和短视频之间具有的社会特性相结合，提出一种基于P2P的在线短视频分享系统——SShare。

1 SShare重叠网的构建

文献［5－6］分别基于小世界网络和兴趣来构建视频之间的单层overlay，而SShare是多层overlay。SShare重叠网是将视频之间的社会特性和点播相似性相结合的一个重叠网。SShare中每一个用户节点同时属于基于社会特性网(social based overlay)和基于点播相似度网(similarity based overlay)，整个结构仍是一个Mesh结构。

1.1 基于点播相似度及社会特性的重叠网

SShare的重叠网结构把用户的点播相似度和点播视频之间形成的社会特性相结合，其目的是使点播用户节点以更小的开销查找到所有的视频资源。图1说明了一个用户节点是如何加入这基于社会特性网和基于点播相似度网的。

NetTube研究结果表明，点播节点与点播视频之间形成一种具备社会特性的网结构。另外，根据点播节点的偏好，将视频分为不同的簇。如图1所示，就有T1簇、T2簇和T3簇等。当点播节点P1新加入系统，由P9和P3向其提供视频V1，又由于P2和P5向节点P3提供了视频V2，则当P1点播视频V2时，P2和P5有更大的概率向P1提供视频V2，这样 P1、P2、P3、P5和 P9就构建了基于社会特性网的结构。

视频网站往往将视频分成不同的类，如体育类、新闻类和军事类等。不同的点播节点(也就是点播用户)会喜欢不同类别的视频。假如当前点播是体育类，而将要点播的下一个视频可能就是新闻类。如图1所示，当点播节点P1点播视频V4时，T3簇的P4有更大的概率向其提供视频V4;同理，T2簇中的P7有更大概率缓存了P1所需求的视频V7，这样P1、P4和P7就构成了基于点播相似性的网结构。P1这种不断点播不同类视频的结构，既属于社会特性网结构，也属于点播相似性特性网结构。随着新节点的不断加入及它们点播不同类的视频，便构成了SShare的重叠网。

图1 SShare重叠网结构

2 基于P2P的在线短视频分享策略

2.1 UGC网站视频特性及点播相似度

由于UGC视频分享网站将视频进行整理分类，当用户点播某一视频时，网站会自动提供相关的视频供用户选择播放，即以相关视频列表(relation vide list)列举出。在UGC视频网站中，在同一时间点播同一视频的用户较少，即使在Flash Crowd情况下大约也只有5个用户［7］。有些用户虽然不再点播视频了，但其内存中仍保留有点播过的视频，这样利用点播用户的空闲带宽仍可以上传视频，以供其他用户分享。像PPVA［8］、百度视频、优酷、飞速土豆等都是采用这种 P2P加速的。

依据以上方式，对用户点播视频文件的特点进行分析。用户点播视频时是按类进行的，且每类视频中又有多个不同的视频。假设视频节目分为n类，每类又分为m个视频，则每个用户节点(如节点i)包含1个点播向量:

其中:1≤i≤n;1≤mj≤m(1≤j≤n);wi，Tmj表示第 i类中的mj视频。若wi，Tmj=1表示节点i已点播过该视频，wi，Tmj=0表示未点播过该视频。

当节点i访问SShare的跟踪服务器时，跟踪服务器会通过对比i节点与其他各节点的点播相似度，并将与节点i的点播相似度最近似的节点返回给节点i，作为节点i的候选邻居节点向节点i提供所需要的视频资源。通过euclidean distance或consine distance来计算两向量之间的距离能产生比较理想的分簇效果［9］。依据本文对点播向量的表示方法计算点播节点之间的点播相似度，这里采用consine distance方法。例如节点i和节点j的点播向量分别记为:

则计算节点i和节点j的点播相似度为

其中:

di，j越小表示二者的点播相似度越接近。

2.2 资源查找策略

本文已讨论了在UGC视频系统中引入P2P技术，当用户点播视频后，可以利用自己的空闲带宽上传自己已点播的视频资源，供其他点播用户分享，以减少服务器带宽的消耗。而同一时间观看同一视频的用户最多大约只有5个，所以，对于UGC视频，有一个高效的查找策略很重要。笔者认为UGC视频查找策略有以下几个难点:①视频应用有较强的时间紧迫性，这一特点使得用户要在较短的时间内查找到所需要的视频资源;② 视频资源的查找范围太小，不能有效查找到视频资源，若查找范围太大，则必定增大视频资源的查找开销，因此，在查找开销和查找到资源的个数之间要有一个权衡［10］;③当在一定查找范围内仍未能查找到所需视频资源时，应及时向服务器请求资源，以保证点播用户的点播感受度QoE。

2.3 资源查找策略描述

SShare重叠网是建立在基于社会特性和点播相似度基础之上的一种重叠网。在UGC视频网站中，网站将视频进行整理归类。当点播节点点播某一视频时，网站会将同类视频以相关视频列表的形式列出，供用户选择。因此，将SShare系统中点播行为分为2类:一类是有关联关系的相关行为，即从相关列表中选择视频做为下一个将要点播的视频;另一类是没有关联关系的无关行为，即点播节点将点播的下一个视频不在关联列表中，比如:当前点播的是T类视频，而下一个将要点播的视频是非T类的。SShare系统中所有点播行为均属于这2种之一。

SShare的查找策略是一种具有视频关联关系的查找策略。UGC视频系统中视频文件之间存在的社会网络特性使得用户的点播行为也呈现一定的关联关系，即点播用户往往会从那些和当前播放的视频存在一定关联关系的列表中选择下一个将要点播的视频［4］。SShare主要利用这一特性，有偏向地发送查找请求给那些和查找视频具有点播关联关系的节点，而不是像NetTube那样采用简单的Flooding查找方法。文献［12］中采用Random Walker，减少了查询开销，但增加了查询跳数。文献［13］中采用 K_Radnom Walker，与前2种方法相比，不仅减少了查询开销，也减少了查询跳数，使得查找开销和查找范围得到的平衡。本文也采用K_Random walker查询方法。这种有偏向的查询方法能显著地提高查找命中率(hit ratio)。

基于点播视频之间社会特性，SShare中将点播用户的邻居节点也按视频类进行分类记录。如点播节点P点播i类视频时，与候选节点Vi1、Vi2、…、ViN等建立邻居关系后，则将 Vi1、Vi2、…、ViN这些节点记录在节点P的第i类邻居列表中。当节点P 即将点播i类视频时，Vi1、Vi2、…、ViN这些邻居节点比其他邻居节点有更大概率缓存P所需要的视频。在这N个邻居节点中选择n(n＜N)个节点Vi1、Vi2、…、Vin以及节点 V 作为候选节点，向其发出资源请求，其中V是由跟踪服务器提供的与节点P具有点播相似度最高的节点。若未能查找节点P所需视频资源，则从 Vi1、Vi2、…、Vin以及节点V中选择K个与P具有较高的点播相似度的节点作为下一跳的候选节点，向其发出资源请求。若仍未能查找到所需视频资源，则应及时向服务器发出请求。算法伪码如下:

2.4 资源查找性能分析

假设系统中有 n个节点{P1、P2、…、Pi、…、Pn}，其中 Sv={P1、P2、…、Pj、…、Pm}(m ＜ n)个用户节点缓存有视频V，则当用户节点i访问任一邻居节点缓存有视频V的概率为

在资源查找过程中，可能需要多跳才能查找到所需要的视频资源。从第l跳到第l+1跳依据社会特性进行查找，查找到的概率为Pv。若按照点播相似度进行查找时，第l+1跳的查找概率不仅和Pv相关，也和第l跳邻居节点所缓存的与V相关联的视频个数有关。假设第l跳节点i缓存有λ个与V相关联的视频，第l+1跳节点j缓存有K个与V相关联的视频，则节点i从节点j查找到视频V的概率为

其中 λi＜K，(i=1、2、…、θ)。可推出，节点 i从这θ个节点中查找到视频V的概率为

当节点i向t个节点发送查找消息时，若采用社会特性随机选择θ个节点，查找成功的概率为

而

从式(6)可以看出，采用基于点播相似度关系进行选择节点进行查找资源成功概率大于采用基于社会特性关系查找资源的成功概率。

3 仿真分析

对基于点播视频之间的社会特性与基于点播相似度特性形结合的SShare系统的仿真结果如图2～4所示。

由图2可以看出，无论采用基于社会特性还是采用基于点播相似度方法，对服务器带宽消耗均小于C/S方法。当仿真进行到4 h后，采用点播相似度方法就优于采用社会特性的方法和C/S方法，明显降低了对服务器带宽的消耗。

图3是对系统加入2 000个节点的过程中查询包的统计对比结果，即基于社会特性和点播相似度2种方法的查询包对比。由图3可以看出，当系统点播节点小于1 200时，二者查询包相差很小。虽然，当系统点播节点大于1 200之后，基于点播相似度方法查询包明显增加，但是降低了服务器带宽消耗，这些开销还是值得的。

图4显示了在系统中加入2 000节点的过程中，采用基于社会特性和点播相似度2种方法查询失败次数的对比情况。当系统点播节点小于1 500个时，基于社会特性的查询成功次数远高于基于点播相似度查询成功次数;当系统点播节点超过1 500个后，基于点播相似度方法的查询成功次数远高于基于社会特性查询成功次数。所以说，当系统规模越大时，采用点播相似度查询方法能获得更高的查询成功率。

在NetTube中利用点播视频之间的社会特性，使服务器带宽消耗降低了70%。通过对图2～4的分析可知，本文构建的SShare系统与采用基于社会特性的方法和传统的C/S方法相比，随着系统规模的不断增加，能明显降低服务器带宽消耗，而且查询成功率还远高于采用基于社会特性方法的查询成功率。

图2 服务器带宽消耗对比

图3 资源查询包对比

图4 访问失效次数对比

4 结束语

本文设计的SShare系统，通过组建基于社会特性和点播相似度的重叠网，可以有偏向地对资源进行查找。仿真实验表明，SShare系统能明显降低服务器带宽的消耗，而且也有效降低了查询失败次数。在SShare系统中，对内存管理方面还需要进一步研究。

［1］王淑玲.P2P资源共享系统中的资源定位研究［D］.合肥:中国科学技术大学，2012.

［2］Zhang X，Liu J，Li B，et al.Cool Streaming/DONet:A Data-Driven Overlay Network for Peer-to-Peer Live Media Streaming［Z］.［S.l.］:IEEE，2005.

［3］Xu K，Li H，Liu J.PPVA:A Universal and Transparent Peer-to-Peer Accelerator for Interactive Online Video Sharing［Z］.［S.l.］:IEEE，2010.

［4］Cheng X，Liu J.NetTube:Exploring social networks for peer-to-peershortvideo sharing ［Z］.［S.l.］:IEEE，2009.

［5］Hao Liao，Kuo-Chan Huang，Hung-Chang Hsiao.Small-World Social Relationship Awareness in Unstructured Peer-to-Peer Networks［Z］.［S.l.］:IEEE，2010.

［6］Kunwadee，Sripanidkulchai，Bruce Maggs.Efficient Content Location Using Interest-Based，Locality in Peer-to-Peer Systems［Z］.［S.l.］:IEEE，2003.

［7］Pawel Garbacki，Dick Epema，Johan Pouwelse，et al.Offloading Servers with Collaborative Video on Demand［C］//Proceeding of the 7th International Workshop on Peer-to-Peer Systems(IPTPS＇08).［S.l.］:IEEE，2008.

［8］Xu K，Li H，Liu J.PPVA:A Universal and Transparent Peer-to-Peer Accelerator for Interactive Online Video Sharing［Z］.［S.l.］:IEEE，2010.

［9］Sean Owen，Robin Anil，Ted Dunning.Mahout in action［M］.［S.l.］:Manning Publications，2010.

［10］Xueyan Tang，JianliangXu，Wang-Chien Lee.Analysis of TTL-Based Consistency in Unstructured Peer-to-Peer Networks［Z］.［S.l.］:IEEE，2008:1683 －1694.

［11］Ming Zhong，Kai Shen，Joel Seiferas.The Convergence-Guaranteed Random Walk and Its Applications in Peerto-Peer Networks［Z］.［S.l.］:IEEE，2008.

［12］Ming Zhong，Kai Shen.PopularityBiased Random Walks for PeertoPeer Search under the Square Root Principle［Z］.

［13］A Biased k-Random Walk to Find Useful Files in Unstructed P2P Networks，International Conference on Parallel and Distributed Computing，Applications and Technologies［Z］.2009.