P2P网络多视点立体视频传输的数据块调度策略

刘晓辉，金志刚，卫津津，赵西满

天津大学 电子信息工程学院，天津 300072

1 引言

立体视频利用人类双目视差原理，使人眼获得同一场景具有轻微视角差异的两个视图，从而在大脑中形成立体感。多视点立体视频支持裸眼观看，具有独特的表现力和强大的震撼力，必将成为互联网新的应用和业务增长点。但是多视点立体视频具有很高的码流速率，同时立体视频对数据丢失特别敏感，需要高效、高质量的网络传输。

P2P（Peer-to-Peer）网络模式在流媒体传输上获得了巨大成功，其非中心化和负载均衡等特点同样适用于多视点立体视频的传输。

P2P的非中心化特点要求每个对等体在获取数据的同时也作为数据提供者，因此对等体之间的数据块调度对视频的传输和播放质量至关重要[1]。为了提高传输效率，研究人员针对不同的影响因素提出许多有效的P2P数据块调度算法[2-6]。文献[2]提出随机获取算法（RAND）；文献[3]提出数据驱动的概念，并提出采用局部最少优先算法（Local Rarest First，LRF）改善性能；文献[4]通过分析贪婪策略和最少优先策略提出一种混合调度策略（Mixed Rarest First and Greedy，Mixed-RF-G）。该策略将节点缓冲区分成两部分，第一部分用最少优先策略调度数据块，剩下的用贪婪策略，以此来平衡数据的稀有性和紧急性。

上述P2P数据调度算法可以改善节点吞吐量、带宽利用率和启动速度等方面发挥作用。但分析表明：P2P节点吞吐量的最大化并不能保证视频的播放质量，因为一些关键数据块的丢失会造成视频的严重失真[7]。尤其是多视点立体视频，其编码形式复杂、同时包含运动和深度信息、对数据丢失敏感度高，因此关键数据块的缺失对多视点立体视频的影响更大。文献[8-10]从率失真的角度提出重要性优先（Importance First，IF）的传输模型，这种方法对多视点立体视频的P2P传输具有指导意义。但是，采用重要性优先模型进行数据调度往往会导致P2P网络陷入内容瓶颈问题[11]。本文首先分析多视点立体视频的编码特点，然后结合节点数据的重要性、稀有性以及紧急程度提出面向多视点立体视频的P2P数据块调度方案。

2 多视点立体视频和P2P视频传输系统

为了提高立体视频播放质量和传输效率，P2P传输调度算法需要紧密结合立体视频的编码结构。因此，本章首先介绍多视点立体视频的编码结构，然后对P2P视频传输系统和其中的数据块调度问题进行分析。

2.1 多视点立体视频编码

在单视点视频编码中，去除视频序列时间冗余的有效方法是帧间预测[12]。对于多视点立体视频而言，去除视点间冗余最直接的方式是在编码当前视点图像时使用其他视点中的图像作为参考图像进行位移估值和帧间预测，这种方法称为视点间预测[13]。

多视点视频编码（MVC）在H.264编码的基础上增加了视点间预测，目前已经成为H.264编码标准的扩展集之一。本文的立体视频编码方式就是采用MVC编码，图1是一个全视点图片组（GOGOP）的MVC编码结构。水平坐标轴为时间轴，垂直坐标轴为视点轴，T0表示第0帧视频，V0表示第0号视点。多视点立体视频采用分层的B帧构造可分级的预测结构，每帧字母下标的数字表示级别，0级优先级最高。V0的第0帧是I帧，V2，V4，V6，V7的第0帧采用视点间P帧预测，V1，V3，V5的第0帧采用视点间的B帧预测。其余都是基于时域和视点间的B帧预测。显而易见，V0视点的I0最为重要，整个GOGOP中的所有帧图像都对它有依赖关系，I0的数据丢失将影响整个GOGOP的图像质量。其次是P0帧，P0帧不仅是本视点的参考帧，同时影响对应的B帧预测视点。多视点立体视频中所有帧类型的重要性顺序为I0>P0>B1>B2>B3>b4，在一个GOP中其数目分别为1，4，8，13，26，12。

图1 八视点立体视频MVC编码结构图

2.2 P2P视频传输系统

P2P系统由流媒体服务器、Tracker服务器以及若干个节点组成（Peer）[14]。流媒体服务器将预先编码好的视频流分组打包，以直播的方式分发到P2P网络中；Tracker服务器用于维护在线节点列表，并为请求节点提供具有媒体发布能力的邻居节点列表；节点不仅是媒体内容的下载者，而且将媒体内容下载并转发给其他请求节点。

当一个节点加入P2P网络系统中，它首先向Tracker服务器请求邻居节点列表。获得邻居节点列表后，随机选择节点建立连接。每个节点维护一个缓存图（BufferMap，BM），用于说明该节点的数据块中哪些是已经缓存并且可用的。在传输过程中，节点周期性地与其他的邻居节点交换BM，从而得到更多的节点的缓存信息。当节点收到对方的数据缓存图BM后，就会采用一定的数据块调度策略去请求感兴趣的块。媒体内容被分成大小相同的块，每个数据块被指定一个编号，用以表示其播放顺序。节点缓存一定量的数据块以后，就开始进行视频播放。

为了维持视频播放和流媒体数据块请求动作，每个节点维护两个滑动窗口：播放窗口和请求窗口。节点的播放窗口和请求窗口结构如图2所示。播放窗口中的是正在参与解码和播放的数据块，包括已经缓存的数据块和少量的丢失数据块。播放窗口中的最后一个数据块被称为截止期，晚于这个截止期到达的数据块将会被认为是数据丢失，并会对视频的播放质量产生影响。请求窗口为视频播放缓存数据，内容包含已经缓存的数据块、向邻居节点请求但尚未收到的数据块、邻居节点拥有但尚未请求的数据块，以及邻居节点没有的数据块。

图2 节点的播放窗口和请求窗口

当Peer节点开始接收和播放数据时，播放窗口和请求窗口同时向后滑动。正常情况下，播放窗口的滑动速率与视频的正常的码流速率相同。而请求窗口的滑动速率只与Peer节点的数据接收速率有关，当数据块的接收速率高于播放速率时，播放窗口的截止期与请求窗口的距离会拉大。当网络出现阻塞或者P2P网络出现传输瓶颈时，请求窗口的滑动速率会迅速降低或者停止，此时截止期与请求窗口的距离会越来越小，直至为0。当截止期和请求窗口距离为0时，播放窗口无法正常向后滑动，视频播放也会出现卡顿或停止。

3 数据块调度模型及算法

3.1 数据块调度的主要考虑因素

数据块调度的主要目的包括两点：（1）保证P2P网络的高效数据传输；（2）提高单个Peer的视频接收和播放质量。

在P2P网络系统的角度上，为了提高数据的传输效率，就必须提高Peer之间的单位时间数据交换量。假设N个Peer节点之间进行数据交互，而没有外部新鲜数据进入的情况下，它们会随着因缓存数据的同步，传输效率会越来越低，最终陷入传输瓶颈。因此P2P网络中数据块内容的多样性和可用性对保证P2P系统的传输效率至关重要。

对于Peer节点而言，要保证数据接收和视频播放质量，必须满足紧急数据块的优先性。Peer的紧急数据块是指请求窗口中靠近播放窗口截止期但尚未接收到的数据块，随着这类数据块逐步接近播放窗口，其紧急程度越来越高。如果进入播放窗口，仍未接收，将会影响视频的播放质量。

另一方面，由于本文面向的是多视点立体视频的P2P传输，数据块的丢失对立体视频播放质量影响更为复杂，关键数据块的丢失会对视频的正常播放产生更大的影响。例如：图1中I0帧所在的数据块具有最高的重要性，I0帧的数据块丢失会影响整个GOGOP中其他所有视点、所有后续帧的解码。因此，必须考虑数据块在编码中的重要程度。

因此，P2P网络多视点立体视频传输数据块调度的主要考虑因素包括：

（1）数据块在视频编码结构中的重要程度。

（2）数据块对视频播放的紧急程度。

（3）新鲜数据和数据的局部稀缺性。

3.2 面向立体视频数据块调度算法

MVC采用分级的B帧预测结构，其中，B3帧和b4帧在预测结构中数目较多，但它们重要性相对较低，其数据丢失对立体视频质量的影响相对较小。而I0P0B1B2帧的数目和比例虽然较低，但其数据丢失对立体视频影响较大。有鉴于此，本文将两类分开处理。

本文算法中将请求窗口内的数据块分为Priority_Chunks和Rand_Chunks两个集合，Priority_Chunks主要包含I0P0B1B2四种帧类型对应的数据块（也可称为I0P0B1B2集），这些数据块需要优先传输。而Rand_Chunks主要包含B3b4两种帧类型的数据块（可称为B3b4集）。

确定数据块的请求优先级，是提高传输效率和播放质量的一种有效手段。本文引入重要性、紧急性和稀缺性三种影响因素，确立数据块的请求优先级。本文对每个数据块c定义一个立体视频经验效用函数 P(l,t,λ)，P(l,t,λ)值越小，数据块的优先级越高。

为了提高传输效率，提高立体视频质量，本文提出一种联合优先级传输和随机传输的数据块调度方法PR-RAND。具体算法如下：

初始化传输以后，Peer节点i以时间T为间隔进行如下操作：

（1）对请求窗口中的 N个数据块计算其效用函数Pi(l,t,λ),1≤i≤N 。

（2）将待请求的数据块分为两个集合：Priority_Chunks和Rand_Chunks。

I0P0B1B2对应的数据块属于Priority_Chunks；B3b4对应的数据块属于Rand_Chunks。

（3）对于 Priority_Chunks中的数据块，按照 P(l,t,λ)越小，优先级越高的方式进行请求。

（4）使用邻居节点的传输率估计Peer节点i的可用数据带宽：

其中，设节点 Nij(j=1～Neighbors)是节点i的邻居节点；oj是节点Nij的上载带宽；mj是节点Nij的邻居总数。

若BWi大于多视点立体视频的平均码流速率，使用RAND[2]算法传输Rand_Chunks中的数据块，否则，对Rand_Chunks集合中的数据块不做请求。

注 Rand_Chunks中数据块的效用函数P(l,t,λ)并未实际使用，在算法实现中可以省去此部分计算。

Priority_Chunks按照 P(l,t,λ)越小，优先级越高的方式进行传输；Rand_Chunks中的数据块优先级相对较低，对立体视频质量影响较小，采用RAND[2]算法进行传输。RAND[2]算法是一种简单的数据块请求方法，它是指peer节点根据维护的数据块请求列表和邻居节点的可用数据块列表，随机地挑选数据块向邻居节点发送请求获取信息，而不考虑任何优先级信息。其优点在于算法简单，并能够增加节点数据块的多样性。

使用PR-RAND方法，在保证立体视频播放质量的基础上，可以充分利用空余网络带宽传输随机数据块，增加Peer节点之间数据块的多样性，能够一定程度地避免P2P内容瓶颈问题。

4 实验结果和性能评价

4.1 性能评价指标

流媒体块调度算法和Peer邻居节点选择算法是影响视频播放质量和网络传输效率的两大关键因素，本文在固定Peer邻居节点的情况下对本文所提出的PR-RAND算法做出评估，主要的性能评价指标包括：

立体视频回放质量：立体视频的回放质量直接关系到用户的体验效果，是判定数据块调度效果的最直接的指标。本文采用峰值信噪比（Peek Signal-to-Noise Ratio，PSNR）作为立体视频传输失真的质量评价标准。

数据到达率：立体视频回放时，节点实际获得的有效立体视频数据占应获得数据的比例。由于数据块重要性的区别，数据到达率并不完全与视频回放质量成正比。

启动延迟：数据包从源节点发出直到在接收节点的缓冲区被回放的时间，具体指用户决定观看到实际播放的等待时间，是衡量用户体验效果良好与否的关键。

网络吞吐量：网络吞吐量是指Peer节点平均每秒接收到的数据量，网络吞吐量能够直观地反映P2P系统的网络传输效率，因此也是衡量P2P数据块调度策略有效性的重要指标。

4.2 实验结果

实验环境为：2.13 GHz 4核CPU（Intel Xeon E5606），内存4 GB DDR3，操作系统为Suse linux 11。实验采用Transit-Stub拓扑中的GT-ITM模型建立网络层的拓扑结构，生成2 000个路由节点；采用General Peer-to-Peer Simulator[15]（General p2p simulator:www.cs.binghamton.Edu/～wyang/gps/）作为仿真工具，模拟对等体个数分别为1 000、3 000、5 000。具体的实验参数如表1所示。

表1 实验参数设置

除上述参数以外，算法中的优先级效用函数P(l,t,λ)包含3个权重因子ω1,ω2,ω3，它们是一种比例关系。为了比较简单地获取系统性能较好的权重因子，假设三种因子彼此独立。首先通过分析节点吞吐量和启动延迟的变化，确定ω2,ω3之间比例关系。然后以ω2,ω3为基准，从0开始增加ω1的比重，通过PSNR的变化判断不同权重的作用效果。具体方法如下：设ω3=1，在不考虑ω1的情况下（即ω1=0），调节ω2的数值。由图3可知，ω2在0.5附近时，节点的吞吐量较高，同时启动延迟较低。进一步引入重要性因子ω1，设ω2=0.5,ω3=1,，通过增加ω1的权重进行比较实验，立体视频的平均PSNR随着权重因子ω1增大先增加后减少，在取值为2.5附近出现峰值。因此，本文在以下实验中，将权重因子等比变换为整数，分别设置为ω1=5,ω2=1,ω3=2。

图3 ω3=1时，不同ω2对节点吞吐量和启动延迟的影响

实验内容包括：平均PSNR；启动延迟；平均数据到达率；节点平均吞吐量。由于节点数量庞大，实验数据的获得方式是通过随机抽样的方式，将所有Peer节点分为5组，每组抽取10个节点，由5组总计50个节点数据获取平均值作为整体的实验结果。为了分析和评价所提出的PR-RAND方法的有效性，本文使用三种典型的调度算法PR-RAND方法与 LRF[3]、Mixed-RF-G[4]、IF-IBP[6]进行比较。

（1）平均PSNR：如图4所示，1 000个Peer节点的仿真实验中，不同算法立体视频播放的平均PSNR。由实验结果可以看出，采用本文提出的PR-RAND方法，立体视频的平均PSNR高于其他3种方法。LRF和Mixed-RF-G方法不考虑数据块的重要性，因此视频回放时不能保证关键数据的完整性，造成立体视频平均PSNR偏低。IF-IBP以重要性为优先的原则传输立体视频数据块，但是在200～250 s内出现了明显的内容传输瓶颈，由于大量缺失数据，造成视频质量的下降。

图4 不同算法产生的视频PSNR

（2）启动延迟：本文设计的立体视频播放窗口大小为20，因此，启动延迟是指接收到前20个数据块的时间。从表2中可以看出，由于本文算法考虑了数据块的紧急性，启动延迟低于LRF和IF-IBP，比Mixed-RF-G算法略高。同时，受节点传播时延影响，四者的启动延时随着节点规模增大略有增加。

表2 启动延迟 s

（3）节点平均吞吐量和数据到达率：节点的平均吞吐量和平均数据到达率如图5所示。从图5（a）可以看出，LRF方法具有最高的节点平均吞吐量，其次是PR-RAND和Mixed-RF-G，IF-IBP的吞吐量最低。平均数据到达率如图5（b）所示，由于考虑了数据块的紧急性，并采用联合优先级和随机传输方法，本文提出的PR-RAND方法的数据到达率高于其他三种方法。

图5 算法的平均节点吞吐量和数据到达率对比

5 结束语

面向多视点立体视频P2P网络传输，本文综合考虑了数据块在视频编码中的重要性、播放的紧急程度以及网络内容的稀有性，提出了一种联合优先级和随机传输的数据块调度方案。通过仿真实验，证明了本文提出的PR-RAND方法能够提供更优越的立体视频质量和较小的启动延迟，同时克服了IF方法的缺点，能够避免内容传输瓶颈问题，保证较高的网络吞吐率。

本文仅仅研究立体视频P2P数据块请求的调度问题，与P2P Tracker服务器节点调度相结合，建立一套完整高效的立体视频P2P传输系统是下一步的工作方向。

[1]Zhang M，Xiong Y Q，Zhang Q，et al.On the optimal scheduling for media streaming in data-driven overlay networks[C]//Proc of IEEE GLOBECOM，2006.

[2]Pai V，Kumar K.Chainsaw：eliminating trees from overlay multicast[C]//Proc of IEEE INFOCOM，2005.

[3]Zhang X，Liu J，Li B，et al.CoolStreaming/DONet：a data-driven overlay network for efficient media streaming[C]//Proc of IEEE INFOCOM，2005：2102-2111.

[4]Zhou Y，Chiu D M，Lui J C.A simple model for analyzing P2P streaming protocols[C]//Proc of IEEE ICNP，2007.

[5]任浩，王劲林，尤佳莉.一种分阶段的P2P流媒体数据调度算法[J].计算机工程与应用，2011，47（23）：1-4.

[6]徐家燕，陆建德，武广柱.rlncBT：随机线性网络编码的P2P内容分发系统[J].计算机工程与应用，2009，45（12）：110-113.

[7]Chakareski J，Apostolopoulos J，Wee S，et al.Rate-distortion hint tracks for adaptive video streaming[J].IEEE Transactions on Circuits and Systems for Video Technology，2005，15（10）：1257-1269.

[8]Chou P A，Miao Z.Rate-distortion optimized streaming of packetized media[J].IEEE Transactions on Multimedia，2006，8（2）：390-404.

[9]Miao Z，Ortega A.Expected run-time distortion based scheduling for delivery of scalable media[C]//Proc of Int Packet Video Workshop，2002：829-832.

[10]Chakareski J，Apostolopoulos J.Rate-distortion optimized distributed schediling of multiple video streams over shared communication resources[J].IEEE Transactions on Multimedia，2006，8（2）：207-218.

[11]Chang C Y，Chou C F，Chen M H.Striking the balance between content diversity and content importance in swarm-based P2P streaming system[C]//Proc of IEEE HPCC，2002：653-660.

[12]欧阳合.H.264和MPEG-4视频压缩[M].北京：国防科技大学出版社，2004.

[13]MPEG video subgroup.Introduction to multi-view video coding[C]//83rd MPEG Meeting，2008.

[14]谢勇均.P2P视频直播传输系统的研究与实现[D].北京：中国科学院计算技术研究所，2006.

[15]Yang W，Abu-Ghazaleh N.GPS：a general peer-to-peer simulator and its use for modeling BitTorrent[J].Mascots，2005：425-434.