2012 年 2 月 February 2012
计 算 机 工 程
Computer Engineering
第 38 卷 第 3 期 V ol.38 No.3 ·开发研究与设计技术·
文献标识码：A
文章编号：1000—3428(2012)03—0273—03
中图分类号：TP393.03
P2P 陈 一种基于 的短视频分享系统
卓 1,2，李 彦
1 (1. 重庆理工大学计算机科学与工程学院，重庆 400054；2. 电子科技大学通信抗干扰技术国家重点实验室，成都 611731)
摘 要：现有在线短视频分享策略通常采用 C/S 架构，给视频服务器带来较大的带宽压力。为此，提出一种采用点对点方式的在线短视频
分享系统 ISh a re ，该系统结合用户点播偏好和视频文件之间的社会网络特性实现视频分享。ISh a re 主要包括基于点播兴趣的节点分簇和视 频数据源节点的查 2 个核心技术。实验结果表明，IS ha re 具备较好的视频数据源节点查能力，可降低视频服务器带宽资源消耗。 关键词：点对点；查算法；社会网络；重叠网；视频点播；兴趣簇
P2P-based Short Video Sharing System
CHEN Zhuo 1,2, LI Y an 1
(1. College of Compu ter Science and Engineering, Chongqing University o f Technology, C hongqing 400054, China; 2. National Key Laboratory of
Science and Technology o n C ommu nications, University o f Electronic Science and Technology of C hina, Chengdu 611731, China)
【Abstract 】Online short video sharing is reshaping the way people watching videos, so this paper presents sharing policies mainly adopts the Client/Server architecture, which can result huge bandwidt
h pressure at streaming server. A P2P based online short video sharing System IShare is proposed, which combines viewing interests of users and social network characteristic of short videos, which can share short videos between users. IShare mainly includes interest based peers clustering and streaming source peers searching. Experimental results show IShare has a high efficient streaming source peers searching ability and can greatly reduce the bandwith consumption o f streaming server.
【Key words 】Pe er-to -P e er(P2P); searching alg orithm; social network; overlay network; Video -on -De ma nd(Vo D); interest cluster
DO I: 10.3969/j.issn.1000-3428.2012.03.090
和簇 1 中的多个节点 P 4、P 5、P 6 建立了邻居关系，这里 P 4、 P 5、P 6 不一定缓存了 V 1，但由于和 P 1 的点播兴趣最相似，因此 P 1 观看完 V 1 后 P 4、P 5、P 6 具有很大的概率缓存了 P 1即将点播的视频。
1 概述
近年来，在线网络视频分享成为新的 Internet 重要应用。 大量在线视频分享网站如 YouTube 、优酷、土豆网每天吸引 上百万的点播量[1]。大多数短视频分享网站采用的是客户机/ 服务器(C /S )的架构实现，以这种架构带来的问题是视频服务 器的带宽消耗巨大。基于点对点(P eer-to-P eer, P2P)的视频类 应用越来越多[2-4]，这类系统中的用户在从其他节点获取视频
流的同时也贡献自己的上行带宽，提供缓存的视频流给其他 节点。但由于在线视频分享自身的特点使得直接应用已有的 P2P 视频播放技术存在诸多挑战。主要的技术难点在于： (1)视频分享网站中的视频节目通常较小，在同一时刻观看同 一个视频节目的节点通常不多，这使得节点之间共享视频流 的难度增
大；(2)如何在较短时间内高效地查到视频源节点 也成为必须研究的问题。为此，本文提出一种采用点对点方 式的在线短视频分享系统 IShare 。
2 基于 P2P 的在线短视频分享系统 IShare
IShare 的主要设计思想是结合节点的点播兴趣偏好和视
频文件之间所具有的社会网络特性，并建立混合结构重叠 网，该重叠网结构如图 1 所示。该图中的 P 1 为一个新访问 IShare 视频分享网站的节点，P 1 点播了视频 V 1。由于 P 2 和 P 3 都曾经点播了 V 1，因此 P 2 和 P 3 可以向 P 1 提供 V 1。这 时 P 1、P 2、P 3 同属于基于社会特性的重叠网，P 2 和 P 3 具 有较大的概率缓存了 P 1 即将点播的另一个视频节目。另外， 根据对用户点播兴趣偏好，IS hare 把节点组织成多个兴趣簇， 每个簇中的节点对同一类视频有同样的点播偏好，P 1 根据和 自己点播兴趣的相似程度和多个节点建立了邻居关系，如 P 1
基于兴趣T 3的分簇
图 1 IShare 的重叠网结构
基金项目：国家科技基金资助重大项目(2008ZX03004)；重庆市教委
科技基金资助项目(KJ110831)
作者简介：陈 卓(1980－)，男，讲师、博士研究生，主研方向：分 布式网络，网络通信协议；李 彦，副教授 收稿日期：2011-07-27
E-mail ：uestccz@g mail
274 计 算 机 工 程
2012 年 2 月 5 日
2.1 混合重叠网结构的建立
IShare 的重叠网结构把用户的点播偏好和视频文件之间 形成的社会特性进行结合，主要目的是为了让点播节点在选 择点播新的视频文件时，能够以较小的开销到更多的视频 数据源节点。这里首先介绍在一段时间内用户的点播兴趣计 算方法。
设视频节目共有 n 种分类，分别为 T 1 ,T 2 ,…,T n 。另外假设 endif
if T(v)!=T fa v(Ni) then
if can find We ak Nbri which T fa v(Weak Nbri ) = T(v) t hen
SPv = Search S P(We ak Nbri ); endif
SPv = SPv + Search SP (Soci al Nbri, v); endif
if SPv = Ф then
SPv = SendReqtoServer(v); endif
2.2.2 查跳数 TTL 的确定 查策略需要重点考虑的一
个问题是如何确定查跳数
TT L (hop )。文献[4]通过大量实验数据得出在线视频分享中视
频的点播次数和流行度排名基本满足 Z ipf 分布。假设节点单 播的视频 v 的流行度排名为 k ，而 IShare 中所有视频文件数 量为 M ，Zipf 分布是指数特性参数为 S 。则根据 Z ipf 分布的 性质，节点点播流行度排名为 k 的视频
v 的概率可表示为： 点播节点 i 对应于一个兴趣向量 V = (w , w ,…, w ) ，该向
i i ,T i ,T
i ,T
量中的元素 w i ,T 对应于节点 i 对 T i 类视频节目的偏好，而 i
Num i ,T
n
, Num i = N um i ,T 。
其中，Num i ,T 表示点播节点 i 曾 w i ,T =
Num
j =1
i
经点播过 T j 类视频节目的次数， Num i 表示节点 i 曾经点播 IShare 网站的视频总次数。节点 i 在访问 IShare 时，首先计 算得到自己的兴趣向量并把向量信息发送给 IShare 。IShare 的 Tracker 服务器会计算出节点 i 最感兴趣的视频分类 ， T fav 即 T fav 满足：
1/ k s
1
f (k ; s , M ) =
=
k s
H
(2) N um i ,T
M
s
(1/ n ) M ,s w i ,T = max( ≤ j ≤ n
N um n =1 M 1
i
1 = k 1 = k
其中， 为谐参数，H M ,S = k =1 s
；设 S = 1 时，H k
M H
M , S
并且向节点 i 提供分类 上的部分在线节点的信息作为节 点 i 的候选邻居节点。在这些候选节点中，节点 i 会进一步通 过比较点播相似度选择其中和自己点播相似度最高的节点建 立邻居关系。在 IShare 中，通过计算 i 和 j 的兴趣向量T fav = M ,1 ln M + © ；© 是 Euler-M ascheroni 系数，值为 0.577 215 664
9。 另外，设在线的点播节点数为 N ，那么在线节点中点播并缓 存视频 v 的节点数 可粗略估计为：
N k 氏距离得到 i 和 j 的点播相似度。如：V = (w , w ,…, w ) ，
N
i i ,T i ,T
i ,T
V j = (w j ,T , w j ,T ,…, w j ,T
) ，则 i 和 j 的点播相似度 S i , j 计算方法为：
N = N ⊕
f (k ; s , M ) =
(3)
k k (ln M + © ) 因此，节点 i 要查到视频
v 需要访问的节点数量为： =
(1)
S , j ϒ N /
(4 )
N v = ' ∞ = ϒ' k (ln M +
© ) /
S i , j 越小表示 i 和 j 的点播相似程度越高。i 通过计算和
候选邻居节点的点播相似度，和相似度最大的 m 个节点建立
起实际的邻居关系，称节点在 T fav 分类中建立起的邻居关系 称为强关联邻居关系。节点 i 可能还点播过其他几种类型的
视频。因此，IS hare 中的每个点播用户还会和自己曾经点播 过的视频类建立弱关联，具体的方式是通过 Tracker 服务器， 根据 V i ，提供少量属于其他类型的节点。
另外，文献[4]通过 Tra cking 实验说明在线视频分享网站 的视频文件之间具有社会网络特点。N etTube
基于这个特点 实现了一个具有社会特点的重叠网络。IS hare 实现的具有社 会网络特性的重叠网类似于 NetTube 。因此，IS hare 的重叠网 络结构是一个混合结 构，更好地结合了点播兴趣和社会网络 属性。
2.2 视频数据源节点查算法
2.2.1 算法的基本描述
IS hare 的资源查算法的伪码描述如下。
输入
v : 被 Ni 选择用来观察下一节点的短视频 T (v ): 短视频 v 的类型 StrongNbri : 强邻居列表 Ni W eakNbri : 弱邻居列表 Ni
SocialNbri : 基于社会关系的邻居列表 Ni 输出
能提供 v 给 Ni 的流资源节点 SPv if T(v)=Tfav (Ni) then
SPv = Search S P(Stro ng Nb ri, v); SPv = SPv + Search SP (Soci al Nbri, v);
' N k ∞
另外，还需要考虑的是类型为 T (v )的簇的紧密程度，这 里采用文献[5]中的方法，对一个属于类型为 T (v )兴趣簇的节 点 j 其局部簇系数可表示为：
j CC =
j C 2 N b
其中，℘ j 为节点 j 的邻居集合；℘ 为节点 j 的邻居的总数；
j E (℘ ) 表示 ℘ j
集合中实际的连接总数； 表示
℘ j 集合中可 2 C N b
j 能产生的连接总数；
C C j 越大表示簇的紧密程度越大。再假 设 IS hare 中一个节点的强邻居节点个数为 x ，那么在 TTL 跳
T TL ' t
内可以访问到的 T (v )类型簇的节点个数为 1 (x ) ，其中，
x '
= x ⊕ (1 CC ) 。所以
有： j TTL ( x )t ≥ N
(5)
(6)
t =1
v
(x ' 1)N TT L ≥log ( x
v
+1) x '
IShare 通过式(3)~式(6)的计算得到一个流行度排名为 k 的视频 v 的查跳数 TTL 。
3 实验仿真与分析
本文采用 OverS im [6]系统对 IShare 进行仿真，比较前后
2 次点播的视频节目无强关联性时的查效率，如图 2 所示。
通过图 2 的对比可以看到 IShare 的查效率显著优于 NetTube ，在这种情况下 IShare 的平均查效率基本达到了
60%，而部分情况下 NetTube 却基本无法直接通过 P2P 的方 式到源节点而必须借助于服务器的帮助，而这显然又增加
E (℘ )
50
第
38 卷 第 3 期 陈 卓，李 彦：一种基于 P2P 的短视频分享系统
275
80 70 60 50 4 结束语
本文提出了一种基于 P2P 的在线视频分享策略，通过实
验仿真表明了 IShare 比现有系统的性能优势，下一步将继续 通过现实系统的部署完善和验证 IShare 。
40 30
20 10 0
参考文献
Gill P, Arlitt M, Li Zongpeng, et al. Y ou Tube Traffic Characteri-
zation: A V iew from the Edge[C]//Proc. of the 7th ACM
Conference on Internet Measurement. San Diego, USA: ACM
Press, 2007.
短视频分享网站源码苏少炜, 王劲林, 尤佳莉. 一种带宽自适应 P2P 视频点播数据
调度策略[J]. 计算机工程, 2011, 37(1): 13-15.
Yan Huang, Fu T Z J, C hiu Dah-Ming. Challenges, Design and
Analysis of a Large-scale P2P-V oD System[C ]//Proc. of ACM
Conference on Data Communication. Seattle, USA: ACM Press, 2008.
Xu Cheng, Liu Jiangchuan. Net Tube: Exploring Social Networks
for Peer-to-Peer Short V ideo Sharing[C]//Proc. of IEEE
INFOCOM’09. [S. l.]: IEEE Press, 2009: 1152-1160.
Hui K Y K, Lui J C S, Yau D K Y. Small-world Overlay P2P
Networks: Construction and Handling Dynamic Flash Crowd[J].
Compu ter Networks, 2006, 50(15): 2727-2746.
Baumgart I, Heep B, Krause S, et al. OverSim: A Scalable and
Flexible Overlay Framework for Simulation and Real Network
Applications[C]//Proc. of the 9th International C onference on Peer-to-Peer Compu ting. Berlin, Germany: [s. n.], 2009: 87-88.
编辑 顾逸斐
[1]
仿真时间/min
图 2 视频关联度较小时查视频源节点的效率
实验对服务器的带宽消耗也进行了比较，对比了 IShare 、 NetTube 和 C/S 架构时视频服务器的带宽消耗。从图 3 可以 看到，C/S 架构的带宽消耗最大，在同样数量的用户点播请 求下接近 4 Gb/s 。IS hare 比 NetTube 有了更好的改善，能够 节约 75%的带宽消耗，这是通过进一步增加节点间的数据共 享实现的。
[2] [3] [4] 4.54.01.0[5] [6] 仿真时间/min
图 3 视频服务器的带宽对比
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ (上接第 272 页)
从图 4 可以看出，在信号数量不同的情况下，OKC PA 算 法的迭代次数仍然明显少于 S AKM 算法。由此可知，无论是 信号方差变化还是信号数量变化的情况下，OKC PA 算法都比 S AKM 算法有更少的迭代次数。
4 结束语
本文提出一种新的变参数在线核聚类算法，并将其应用 于雷达辐射源信号分选中。该算法基于支持向量机的思想， 采用核映射技术将数据映射到高维线性空间，因此，可以用 线性方式处理任何复杂分布形状的数据，并利用随机梯度下 降法更新类的边界函数，使雷达辐射源信号可以实现在线地 分选，同时更新步长和惩罚项参数可以随着信号的到来而动 态地调整，加快聚类分选的速度。仿真实验结果证明，该算 法无论在分选准确率还是在处理速度上，都达到了较好的 水平。
参考文献
Pulses[C]//Proc. of International Conference on Information Acquisition. Weihai, China: IEEE Press, 2006: 742-747.
陈 彬, 骆鲁秦, 赵贵喜. 基于核模糊聚类的雷达信号分选算
法[J]. 舰船电子对抗, 2009, 32(4): 76-79.
普运伟, 朱 明, 金炜东, 等. 核聚类算法最佳聚类数的自适 应确定方法[J]. 计算机工程, 2007, 33(4): 11-13.
Amad ou-Boubacar H, Lecoeuche S. SAKM: A Kernel-based Algorithm for Online Clustering[J]. Neural Networks, 2008, 21(9):
1287-1301.
Kivinen J, Smola A, Williamson R. Online Learning with Ker- nels[J]. IEEE Trans. on Signal Processing, 2004, 52(8): 2165-
2176.
Scholkopf B , Platt J, Taylor J S, et al. Estimating the Support of a
High-dimensional Distribu tion[J]. Neural C ompu tation, 2001,
13(7): 1443-1471.
Vapnik V. An Overview of Statistical Learning Theory[J]. IEEE Trans. on Neural Networks, 1999, 10(5): 988-999.
[4] [5] [6] [7] [8] [9] [1] 郭 杰, 陈军文. 一种处理未知雷达信号的聚类分选方法[J].
系统工程与电子技术, 2006, 28(6): 853-856.
张万军, 樊甫华, 谭 营. 聚类方法在雷达信号分选中的应 用[J]. 雷达科学与技术, 2004, 2(4): 219-223.
Guo Qiang, Zhang Xingzhou, Li Zheng. SVC & K-Means and Type-entropy Based DeInterleaving/Recog nition System of Radar
[10] Vishwanathan S V N, Schraudolph N N, Smola A J. Step Size
Adaptation in Reproducing Kernel Hilbert Space[J]. Journal of
Machine Learning Research, 2006, 7: 1107-1133.
编辑 陆燕菲
[2]
[3]
视频服务器带宽/(G b ·s 1
)
查效率/(%)
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论