一种用户码率偏好敏感的网络编码视频分发算法

吕小星， 张百海

(1.北京理工大学 自动化学院， 北京 100081; 2.北京开放大学 计算机系， 北京 100081)



一种用户码率偏好敏感的网络编码视频分发算法

吕小星1，2， 张百海1

(1.北京理工大学 自动化学院， 北京 100081; 2.北京开放大学 计算机系， 北京 100081)

无线网络用户拥有差异化的网络与视频接收设备，通过单一优化用户获得的下载速率，无法最终确保用户获得良好的视频质量. 多码率视频流编码基于一种多描述编码(MDC)，在MDC视频流中，由于各层数据以数据分片的形式传输，网络编码成为一种有效的视频分片传输机制. 从网络、用户兴趣、内容属性等角度分析用户对视频流码率的偏好，提出了一种用户码率敏感的流媒体数据传输算法. 实验表明该算法在用户偏好满足与降低网络消耗率上，优于已有研究. 在用户可以获得偏好码率的同时，保证了流媒体的连续性.

网络编码；用户偏好；多码率视频分发

多码率视频服务已经成为今天主要的视频服务模式[1]，为了提高用户视频观看质量，在多码率视频服务中，传统优化策略通常考虑提高用户的接收速率，从而提高服务质量[2]. 在用户拥有足够带宽和计算资源的情况下，这一优化目标可以有效指导流媒体传输算法设计. 然而，如今互联网无线用户拥有差异化的网络与视频接收设备：如2G、3G、WiFi用户及使用PC、PAD、手机等设备接收视频服务. 通过单一优化用户获得的下载速率，无法最终确保用户获得良好的视频质量. 例如，当用户使用的移动设备计算能力弱时，接收到高码率视频无法实时解码造成视频无法正常播放，此时向用户传输低码率视频，反而可以获得更好的服务质量. 影响视频的因素是多方面的，如图1所示. 由于用户设备、网络环境、偏好、视频使用上下文不同，用户对不同码率拥有完全不同的偏好. 为了解决以上问题，本文提出一个用户对码率的偏好模型. 这一模型集合了影响用户视频体验的因素，这些因素将对视频质量、视频播放延迟以及用户计算资源等产生影响.

本文使用的多码率视频流编码基于一种多描述编码(multiple description coding，MDC). MDC提供了一种有效的多码率视频编码方式[3]，通过将源数据分成同等重要的数据流以保证通过解码任一子数据流的译码质量可被接受，视频质量会随着接收到的描述数量增加而提高. 在多描述编码中，可以将分层编码和优先编码传输系统的不等错误保护结合起来[4]，达到优化数据传输的目标；同时，利用多分辨率编码(multi-resolution codes，MRC)，将数据编码成一个基础层和若干细化层[5]，接收节点可以逐渐请求各层，随着接收节点接收到层数的增加逐渐细化，更高层的解码通常是建立在包括基础层在内所有更低层正确接收的基础之上. 多码率编码为多码率视频流服务提供了保证，根据视频服务应用场景，可以对不同编码策略进行选择，有效服务特定用户群. 在本文中，使用了基于MDC的视频编码方式.

在MDC视频流中，由于各层数据以数据分片的形式传输，网络编码[6]成为一种有效的视频分片传输机制. 许多实时应用，都需要从一个源节点到多个接收节点的组播. 对于MDC方法，文献[7-8]中修改了源节点的PET以使之满足网络编码系统. 这种方法可以保证一些层能在所有线性无关层收到前被恢复出来，并且能够达到更低的码率开销. Wu等[9]研究了彩虹网络编码问题，即将线性网络编码引入到多描述编码组播中. 对于MRC方法，Sundaram等[10]在研究多分辨率流媒体时，提出一种针对异构接收节点的多项式复杂度算法. Zhao等[11]将多码率组播引入覆盖网络中.

然而，传统方法仅仅以速率为优化目标，无法解决前文中提到的满足用户偏好问题. 本文提出一种将用户偏好进行服务器反馈的方法，有效地解决用户获得速率与偏好不一致的问题.

1 算法基础

1.1 用户对码率的偏好主要决定因素

缓冲率：在视频流服务中，用户对缓冲率非常敏感. 为了获得低的缓冲率，虽然用户可能会趋向于使用低一些的码率，但得到无缓冲或缓冲率极低的视频流；

设备限制：受用户本身设备限制，用户的最小割下载速率可能会远远高于用户设备允许的码率；

视频属性：对于可以进行高码率选择的用户，他们会关心视频的码率高低，通常更高的码率可以带来更好的视频体验；

内容：对于以上条件相同的情况下，由于用户观看的内容不同，很可能会要求不同的码率，如观看体育类视频时，会要求更高的码率.

由上面的分析可以看出，用户对视频码率的偏好是一个复杂的模型，与非常具体的应用场景相关，不失一般性，定义用户的码率偏好为，并且，假设这个码率偏好与用户可达到的下载速率不相关. 在多码率视频中，应该根据这一定义进行流媒体策略设计.

本文的思路如图2所示，在无线环境中，用户可以通过反向传输，将偏好告知上一级节点，而节点在发送数据时，会综合考虑下一级节点的速度要求与偏好要求. 下面将给出详细的建模方法与算法设计.

1.2 组播流媒体模型

假设有向无圈图为

2 基于用户码率偏好的网络编码流媒体算法

本节给出一种基于用户码率偏好的网络编码流媒体分发算法. 算法对文献[2]进行了改进，充分利用了用户的码率偏好信息. 算法由拓扑与偏好收集、码字分配和编码调整3个部分组成.

2.1 拓扑及偏好收集

在拓扑收集阶段，网络中的节点获得与子节点之间的拓扑信息，包括连接的容量. 如图3所示，对于一个节点ν，P(ν)是它的父亲节点集合；而对于一个节点w，C(w)是该节点的子节点集合. 因为图是无环的，所以P(ν)和C(ν)是互不连通的. 在拓扑收集阶段，消息最初由接收节点产生并向上逐级推给源节点，在此过程中，上游节点收集它们子节点的需求信息，消息从子节点传送给它们的父亲节点.

接收节点处理：首先，每个接收节点ri∈R请求一定的视频质量层，最大层数为q(r)，即该节点希望收到视频层X1，X2，…，X′. 其中X′的定义为

式中Θ(ri)为接收节点ri偏好的码率. 这个定义的原理在于接收节点一方面根据自身码率偏好，另一方面根据网络拓扑下能接收到的最高速率，决定目前需要的码率大小，并将该码率告诉父节点.

中间节点处理：中间节点ν∈V根据自身的ψ(ν)以及其孩子节点的请求计算出一个上传消息传递给自己的父亲节点，告知它们自己需要的编码层数. 将节点从它一个孩子节点u∈C(v)处所收到的消息标记为q(u)，节点ν从它所有孩子节点收到消息的集合为q(C(ν))={q(u)，u∈C(ν)}. 消息q(u)代表着u请求它的父亲节点将1～q(u)层的数据进行编码. 一旦ν收到所有来自它孩子节点的请求，计算出它自己的q(u)并把它发送给所有父亲节点.

于是，q(ν)是q(C(ν))和ψ(ν)的函数，

式中f()的选择决定着算法的性能，文献[5]主要讨论两种f()的定义：最小割标准和最小需求标准. 在用户码率敏感的流媒体应用中有以下问题：最小需求标准保证基础层的可译码性仅仅满足接收节点的最小请求；最小割标准无法满足节点请求多于ψ(ν)层的请求. 为了解决该问题，引入用户码率偏好定义f()为

(1)

在文献[2]中，这一定义可以有效地被实现到两种节点码率选择策略，即最小割和最小需求标准中. 在本文中，对f()进行的改进，可以使其满足用户码率偏好，当一个节点为接收节点时，它的码率偏好与原先允许码率作为一个组合消息，发送给父节点，从而在码字分配中满足用户的偏好需求.

结合接收节点处理方法，q(ν)的定义如下

(2)

2.2 码字分配

码字分配阶段，由源节点开始，根据上一阶段收到的消息，随机线性网络编码按照自上而下的方式产生. 源节点S根据其孩子节点的消息产生码字：S将所请求的数据层编码在一起并将编码后的数据传输给相应的孩子节点，充分满足来自它孩子节点的所有请求. 接收节点尝试译码最多的连续数据层. 中间节点根据回溯阶段的消息进行包的编解码.

c(e，m)表示从节点传输到其孩子节点u∈C(ν)的随机线性网络编码，其中e=(ν，u)表示该数据编码了1～m层. 对于一个接入网络中的中间节点，p(ν)≠φ，ν收集所有来自它父亲节点的码字c(ei，mi)，并由此决定其所能译码的最大层数m*. 存在这样的情况，节点ν不能译码任何的层并导致m*=0. 当时，节点ν可以被看作是一个通过译码而成为可以编码1，2，…，层的次源节点. 当q(u)≤m*，u∈C(u))时，节点可以通过编码层1～q(u)就可以满足孩子节点的请求. 但当q(u)>m*时，节点ν不能译码u所请求的所有层，其不能满足其孩子节点的请求. 此时，节点ν采取最大努力策略. 节点ν将继续传递编码包含mmax层的数据包，其中mmax是在不违反孩子节点u请求的情况下，节点ν可以提供的最接近q(u)的层数，所以此时q(u)≤mmax. 码字分配阶段要求每个节点通过检查各自的译码能力来决定m*.

2.3 编码调整

编码调整阶段，使那些在第一次回溯算法结束后，需求仍未被满足的接收节点向它们的父亲节点反馈它们更多的需求. 在很多情况下，接收节点的请求并不能在一次反馈中满足. 特别是在网络带宽有限和接收节点对画面质量要求比较高的情况下，因此，进一步设计一个编码调整阶段，在产生新的网络编码的时候，父亲节点必须在保证每个不参与反馈阶段接收节点可译码性的同时，需要考虑新反馈的需求. 完成一次回溯算法后，如果存在接收节点c可译码k层，没有达到它的X′时，该节点ν向父亲节点发送q(ν)←ψ(ν)-k为新的需求，而其他所有满足需求的接收节点都发送需求为0. 更新各级需求后，进行下一次回溯算法，直到所有接收节点的需求都被满足. 当存在接收节点ν没有达到它的q(ν)中任一条件时，其他已经满足的接收节点处于等待状态. 当所有的接收节点都满足后，源节点进入下一组数据的组播.

综上所述，基于用户偏好敏感的网络编码多码率视频分发算法步骤如下：

① 接收节点发出请求，希望收到视频数据层X1，X2，┄，X′；

② 中间节点收集所有其孩子节点的请求，并将请求集合q(C(ν))发送给父亲节点；

③ 父亲(源)节点将所有请求数据层随机线性网络编码c(e，m)，发给所有它的孩子节点；

④ 中间节点根据收到的编码，计算可译码的最大层数m*. 若m*=0，不译码；若m*≠0，编码1，2，…，m*层，根据q(u)将不同编码层发送给接收节点.q(u)≤m*，编码层1～q(u)层；q(u)>m*，继续传递编码包含mmax层的数据包；

⑤ 需求没有满足的接收节点，发送新的请求q(ν)，进入回溯算法，直到所有接收节点的需求被满足，本次数据组播结束.

3 性能分析

通过基于Matlab的仿真实验，对本文提出的用户偏好敏感的网络编码流媒体算法进行性能评测.

3.1 实验设置

① 仿真环境设置：在实验中，仿真了多种无线网络场景，包括以下主要特性.

网络规模：网络中节点数量从10～30，节点分布在一个10 m×10 m的区域中，根据距离大小，节点与相近节点拥有连接；连接的容量为单位1.

节点偏好：为了验证算法在不同应用下的适应性，在实验中，对接收节点的偏好进行了随机生成，例如，某一场景中，拥有小屏幕设备更多，则低码率偏好的节点比例更大. 实验统计多次随机配备的平均结果.

② 实验指标定义：在实验中，定义了以下两个目标进行性能验证.

NSatisified表示满足偏好的接收节点比例. 该值越高，则说明算法越有效，因为更多的节点可以获得想要的码率.

UNetwork度量了网络消耗率. 网络消耗率越高，网络可能的资源情况就越低，无线网络无法再满足其他业务的需求.

③ 对比方法：在实验中，对比了传统方法[2]. 在传统方法中，没有考虑节点由于自身因素对码率的偏好，也没有考虑网络本身对其他业务的支持.

3.2 实验结果

① 节点偏好满意度Nsatisfied：图4中对比了在不同的节点数量下，接收节点偏好的满足情况. 可以看到，与传统方法对比，本文算法可以有效保证用户偏好的满足. 而在传统方法下，节点接收到的码率，可以高于或低于用户偏好，造成设备无法正常播放视频，或者无法满足用户质量需求. 这一性能提升的原因在于设计了在网络拓扑收集和偏好反馈时，建立了用户偏好与网络容量的知识.

② 网络消耗率Unetwork：图5中对比了在不同的接收节点数量下，本文提出的算法对网络消耗情况. 在传统方法下，节点趋向于用尽网络资源，使得网络无法满足用户的其他请求. 而在本文算法下，网络可以有效根据用户的真实偏好，传输对用户有用的视频码流，从而有效地在满足用户视频质量的同时，降低对网络的开销.

4 结 论

本文从网络、用户兴趣、内容属性等角度分析了用户对视频流媒体中码率的偏好，给出一种用户码率偏好的模型. 基于该模型与网络编码视频服务最新工作，给出了一种用户码率敏感的流媒体数据传输算法. 通过性能分析和仿真实验对本文提出的算法进行了验证，实验表明该算法在用户偏好满足与降低网络消耗率上，优于已有研究. 如何在实际应用中(如iOS，Android设备)，对算法进行有效部署是下一步的研究工作.

[1] Li Bo， Liu Jiangchuan. Multiratevideo multicast over the internet: anoverview[J]. IEEE Network， 2003，17(1):24-29.

[2] Kim Minji， Lucani D， Shi Xiaomeng， et al. Networkcoding for multi-resolution multicast[C]∥Proceedings of INFOCOM.[S.l.]: IEEE， 2010:1810-1818.

[3] Wang Y， Reibman A R， Lin S. Multiple description coding for video delivery[J]. Proceedings of the IEEE， 2005，93(1):57-70.

[4] Albanese A， Blomer J， Edmonds J， et al. Priority encoding transmission[J]. IEEE Transactions on Information Theory， 1996，42(6):1737-1744.

[5] Effros M. Universal multire solution source codes[J]. IEEE Transactions on Information Theory， 2001，47(6):2113-2129.

[6] Yeung R W. Information theory and network coding[M]. Berlin: Springer， 2008.

[7] Silva D， Kschischang F R. Rank-metric codes for priority encoding transmission with network coding[C]∥Proceedings of IEEE Canadian Workshop on Information Theory. [S.l.]: IEEE， 2007:375706.

[8] Walsh J M， Weber S. A concatenated network codingscheme for multimedia transmission[C]∥Proceedings of IEEE NetCod. [S.l.]: IEEE， 2008.

[9] Wu Xiaolin， Ma Bin， Sarshar N. Rainbow network flow of multiple description coding[J]. IEEE Transactions on Information Theory， 2008，54(10):4565-4574.

[10] Sundaram N， Ramanathan P， Banerjee S. Multiratemedia streaming using network coding[C]∥Proceedings of Allerton Conference on Communication， Control， and Computing. [S.l.]: IEEE，2005.

[11] Zhao Jin， Yang Fan， Zhang Qian， et al. Lion: layered overlay multicast with network coding[J]. IEEE Transactions on Multimedia， 2006，8(5):1021-1032.

(责任编辑：李兵)

A User Bitrate Preference-Aware Streaming Algorithm Based on Network Coding

LÜ Xiao-xing1，2， ZHANG Bai-hai1

(1.School of Automation， Beijing Institute of Technology， Beijing 100081， China;2.Department of Computer， Beijing Open University， Beijing 100081， China)

The difference among the heterogeneous user bitrate preference has greatly limited the quality-of-experience (QoE) due to the heterogeneous network environment and devices， and the homogeneous download schedule in wireless video streaming. Multi-resolution code network coding has emerged as a promising approach to delivering videos in multiple description coding (MDC) streaming， where chunks of different layers are delivered to users. In this paper， a bitrate-aware streaming algorithm was proposed based on network coding to satisfy users bitrate preference， considering the network condition， user interests， and content property that together characterize the user preference. Experimental results show that the proposal algorithm outperforms traditional approach in user p

atisfaction and higher network utilization， such that users can enjoy both improved bitrate and streaming continuity.

network coding；user preference；multi-rate streaming

2013-10-16

吕小星(1966—)，女，博士生，教授，E-mail:lvxx@mail.btvu.org；张百海(1966—)，男，教授，博士生导师，E-mail:smczhang@bit.edu.cn.

TP 37

A

1001-0645(2016)08-0827-05

10.15918/j.tbit1001-0645.2016.08.010