基于流行度的P2P流媒体复制算法-AET

P2P网络的动态性和异构性是影响流媒体的应用实施的两个重要因素^[1]。文献[2]研究了一个分布式副本近似放置算法，给定流媒体文件的请求速率和存储容量，在请求节点的最邻近位置放置副本，从而达到最大化缩短访问时间的目的。文献[3]研究最佳复制算法的要求：内容放置在不同节点，满足存储和约束条件，期望有最小的服务负载和均衡的带宽。文献[4]研究指出在P2P点播系统中，上传速率和流媒体文件流行度都是影响复制策略的因素。

1 流媒体复制算法

1.1 流媒体副本建立算法

对于流媒体文件x而言，正在观看流媒体文件y (x≠y)的当前节点和缓存流媒体文件y(x≠y)的复制节点统称为流媒体文件x的活跃节点。而服务节点是存储源流媒体文件的节点，不能从别的节点那里下载数据。本文假设所有流媒体文件的观看顺序都是从头到尾的^[4]。

1.1.1 流媒体文件k的期望的赤字带宽D_k(n_k)

式(5)就是当前节点的赤字带宽和服务节点的上传带宽消耗之间的关系。根据这个关系，本文的目的就是找到一个复制算法确定R_k，使得U最小。

当节点调度策略满足顺序性和贪婪性时，赤字带宽^[4]如式（6）所示：

1.1.2 流媒体文件i期望的存储空间

流媒体文件i期望的存储空间^[4]为：

其中，E(D_i(n_i)表示流媒体文件i的期望的赤字带宽，l(s)为流媒体文件的播放时间长度。

每个流媒体文件i的期望的赤字带宽乘以每个流媒体文件i的时间长度，就可以得到每个流媒体文件i的大小，再把所有将要流行的流媒体文件的大小求和，即为将要流行流媒体文件总期望的存储空间大小。

1.1.3 流媒体文件流行度定义

本文定义的流媒体文件的流行度为式(9)：

先计算流媒体文件的流行度，按照从大到小顺序进行排列，选择流行度高的前B%的流媒体看作是将要流行的流媒体，即选择将要流行的流媒体文件i，对它们进行复制。其中B是正整数，B在0～100范围内。

1.1.4 综合性能比较高的非服务节点的选择标准

综合性能比较高的非服务节点的选择标准：在最大上传速率、最大下载速率、存储容量以及当前节点与除当前节点外的非服务节点之间的跳数这4个指标之间找到一个合适的比例。首先，要计算P2P流媒体系统中节点的存储容量值，并进行归一化处理；其次，计算该节点的最大上传速率、最大下载速率，并进行归一化处理；再次，计算当前节点与系统中除当前节点外的非服务节点之间的跳数，并进行归一化处理；最后，将该节点的存储容量、最大上传速率、最大下载速率以及当前节点与除当前节点外的非服务节点之间的跳数进行加权求和，得到该节点的综合性能指标值，根据节点的综合性能指标值选取出所要的候选节点。根据其比重的不同，可以使本算法具有较好的健壮性。定义节点的综合性能指标为：

W的值越大说明节点的综合性能越好，如果W出现负值，说明这样的节点是个单纯的消耗节点，不能提供很好的上传服务，因而不利于作为复制候选节点。如果所有节点的综合性能指标都是负值，就放弃此次排序，再更新综合性能指标中的各个权值，重新计算综合性能指标，如果得到的综合性能指标是非负数，则进行排序，选取综合性能指标高的前n个节点，这里n为流媒体文件需要存放的副本数量。否则放弃排序，以此类推。对前n个节点，判断其可利用的存储空间是否可以放置整个该流媒体文件。如果可以放下，更新流媒体文件需要存放的个数以及相应的活跃节点的剩余的可利用存储空间。否则，更新综合性能指标公式中的权值系数：最大上传速率的权值 每次减少0.05，节点最大下载速率的权值β每次减少0.05，节点存储空间的权值η每次增加0.2，当前节点与系统中除当前节点外非服务节点之间的跳数的权值ξ每次减少0.1。直到权值系数到达到设定阈值或者需要存放流媒体文件个数都已经缓存到节点中，结束本次复制。

1.2 流媒体副本更新算法

当一个节点请求观看一个新的流媒体文件时，先检查这个流媒体文件是否存在于本地节点的缓存中，如果存在就不做替换，如果没在本地缓存中存储，则计算存在缓存中的每个流媒体文件的期望的副本个数，然后再计算存在缓存中的每个流媒体文件的当前副本个数，得出当前副本个数与期望的副本个数之比，此比值称为满意度指标SI_i。替换满意度指标SI_i值最大的流媒体文件，这就是替换算法。这个算法的主要思想就是保持副本与赤字带宽合理的比例，因为赤字带宽之比接近最优复制比例^[4]。当SI_i大于1时，表示当前时刻该流媒体文件的副本个数多于期望的副本个数；若SI_i小于1，表示当前时刻该流媒体文件的副本个数低于期望的副本个数；SI_i等于1，表示当前时刻该流媒体文件的副本个数和期望的副本个数相符合。因此，在本算法的每一次循环中，就要从本地缓存的流媒体文件中替换掉SI_i值最大的流媒体文件。计算已存在于当前节点缓存中的每个流媒体文件的期望的副本个数如式(11)所示：

流媒体副本更新算法描述：

(1)当节点请求流媒体文件时，首先判断节点的缓存空间中是否存放有该流媒体文件。如果有，则直接观看该流媒体文件；如果没有，就判断该节点的缓存空间是否可以放下整个流媒体文件。如果能放下，直接从其他节点处请求数据；如果放不下，就需要调用流媒体替换算法，见步骤(2)。

(2)对各个流媒体文件的满意度指标进行从大到小排序。将本地缓存中满意度指标最大的流媒体文件替换掉。此时本地缓存释放出空间，以放置待请求的流媒体文件。

2 实验结果及分析

2.1 实验参数

利用MATLAB R2012搭建仿真平台，参数设置如下：

(1)假设路由器包含的非服务节点和服务节点为peerset=[10，1；20，2；10，2；15，3；10，1]，其中每一行代表一个路由器覆盖的非服务节点数和服务节点数。服务节点个数为9个，非服务节点个数为65个。

(2)假设系统共有20个流媒体文件，每个流媒体文件时长均为90 min，播放速率R=500 kb/s。

(3)节点的请求速率^[5]。为了流媒体文件能流畅播放，请求节点从其他节点处期望获得的请求速率r′等于流媒体文件的播放速率R，因此r′=500 kb/s。

(4)每个节点（包括服务节点和非服务节点）缓存的流媒体文件数和可利用存储空间。通过在[0，1]区间上服从均匀分布的随机数rand命令，确定初始时刻各个服务节点上存储了哪些流媒体文件。具体地，对每个流媒体文件，利用rand命令生成一个随机数。规定如果rand<0.8，不存储该流媒体文件；否则，存储该流媒体文件。原因就是服务节点上只是随机地存储了部分的流媒体文件。初始时刻非服务节点没有缓存任何流媒体文件，且非服务节点的可利用存储空间为600 MB～700 MB，其大小在[600 MB，700 MB]上服从均匀分布^[4]。

(5)本实验通过不同的非服务节点和服务节点的最大上传速率分布情况^[4]，来比较本文提出的复制算法和比例复制算法的性能。数据分别如表1、表2所示。仿真两种算法复制流行度高的前20%的流媒体文件，即B=20。

(6)每次迭代对应的实际时间长度和迭代步数^[4]。假设一次迭代对应3 h，总步数为15次迭代。

(7)流媒体文件的流行度和期望赤字带宽。初始时刻，各流媒体文件的流行度相同，因此，将初始时刻各流媒体文件的流行度赋值为零。由于流媒体文件的期望赤字带宽与访问它的用户数量有关，初始时刻还没有请求节点观看流媒体文件，因此将初始时刻各流媒体文件的期望赤字带宽赋值为零。

(8)综合性能指标公式中权值的选取。综合性能指标公式中，初始权值取0.1、0.2、0.5、0.2，后续进行复制算法执行时，如果按照此权值得到的综合性能指标高的节点仍然不能完成复制算法，就更新权值。更新规律为：节点最大上传速率的权值 每次减少0.05，节点最大下载速率的权值β每次减少0.05，节点存储空间的权值η每次增加0.2，当前节与P2P网络中除当前节点外的非服务节点之间的跳数的权值ξ每次减少0.1，直到能放下为止，如果更新5次还放不下，就跳出循环，5次是更新的次数阈值，是预先设定好的。

2.2 实验结果以及分析

服务节点的工作负载：指的是每次迭代过程中，当请求节点从当前节点和复制节点处请求得到的速率不能满足流畅播放的期望速率时，需要从所有的服务节点获得的总的速率，单位为Mb/s。满意节点的比例：所谓满意节点，指的是请求节点从其他节点处请求到的速率等于流畅播放的期望速率。满意节点的比例指的是满意节点占所有请求节点总数的比例。

实验仿真结果如图1、图2所示，本组实验（B=20，非服务节点和服务节点的上传速率服从表1、表2分布）结果表明，采用本文提出的流媒体复制算法，服务节点的工作负载在第4次迭代时降低到0.1 Mb/s，明显低于比例复制算法，满意节点的比例从第3次迭代开始，较比例复制算法高约1‰。而且在大约6次迭代后，两种算法服务节点的工作负载和满意节点的比例变得差别不大，但是，本文提出的流媒体复制算法无论在服务节点的工作负载还是在满意节点的比例上都比比例复制算法^[5]好。

算法开始迭代时，因为本文提出的算法本身就是通过期望的副本数和实际副本数的不断逼近来确定副本数目的，所以到达稳态需要一个过程，因此初始几个迭代过程中，本文的复制算法可能没有比例复制算法好，服务节点的工作负载也可能会高于比例复制算法的服务节点的工作负载。这是因为一个流媒体文件刚开始流行时，流行度会急剧增长，比例复制算法按照此流媒体文件的流行度占所有的流媒体文件的流行度总和的比例进行复制，随着迭代次数的增多，本文提出的流媒体复制算法就有了明显的优势，更早进入稳态。其中稳态是指系统的状态变化很小，在仿真结果上就是曲线始终保持小幅变化。稳态时，工作负载更小, 工作负载平均是比例复制算法的33.3%；达到流媒体文件请求速率的节点数量较比例复制算法的节点数量平均多1‰左右。

3 结论

本文提出了基于P2P网络的流媒体副本建立算法和副本更新算法。通过实际副本数与期望副本数的不断逼近来实现网络中副本数量的最佳，按照最佳复制比例来复制副本，不仅可以避免网络赤字带宽瓶颈，提高系统性能，还可以防止网络中的副本数量过多，造成副本冗余。如何有效地在动态加入或离开的节点上复制流媒体文件，是下一步需要考虑的一个问题。

参考文献

[1] Zhao Can，Lin Xiaojun，Wu Chuan.The streaming capacity of sparsely connected P2P systems with distributed control[J].IEEE/ACM Transactions on Networking，2016，24(1)：58-71.

[2] ZAMAN S，GROSU D.A distributed algorithm for the replica placement problem[J].IEEE Transactions on Parallel and Distributed Systems，2011，22(9)：1455-1468.

[3] ZHOU Y，FU T Z J，CHIU D M.A unifying model and analysis of P2P VoD replication and scheduling[C].IEEE INFOCOM 2012，Orlando，USA，2012.

[4] Wu Weijie，RICHARD T B M，JOHN C S L.Distributed caching via rewarding: an incentive scheme design in P2P-VoD systems[J].IEEE Transactions on Parallel and Distributed Systems，2014，25(3)：612-621.

[5] TEWARI S，KLEINROCK L.Optimal search performance in unstructured peer-to-peer networks with clustered demands[J].IEEE Journal on Selected Areas in Communications，2007，25(1)：84-95.

作者信息:

杨 戈1，2，高 兵1，2，黄 静1，贺 辉1

(1.北京师范大学珠海分校 信息技术学院，广东 珠海519087；

2.北京大学深圳研究生院 深圳物联网智能感知技术工程实验室，广东 深圳518055)