网络流媒体系统中多发送者选择算法

摘 要：于SVC视频服务的融合网络流媒体系统中，存在传输网络异构、终端上行带宽受限和参与者持有相同SVC视频编码源的不同比例。基于这样的流媒体系统往往需要多个发送者才能服务一个接收者。上行带宽、持有编码流的比例等是选择候选发送者的主要参数，多参数优化下的多发送者选择算法是一个NP问题。对于一群候选发送者，文章提出一个以尽可能少的发送者数去满足接收者最大需求的选择算法-MSSA，性能分析显示本文算法比同类算法有更好的网络系统稳定性。

关键词：SVC视频；融合网络；流媒体

中图分类号： TP393 文献标识码：A

1 引言（Introduction）

流媒体服务是融合网络最能见实效的也是目前最广泛的主流应用之一[1]。融合网络具有传输网络异构、终端多样性、上下行带宽不对称等特点。在融合网络中为多样性终端提供统一解码质量的视频服务是不现实的，也是不必要的。SVC（Scalability Video Coding）可伸缩视频或分层视频编码技术（包括H.264中FGS标准）为异构网络的多样化流媒体服务提供了可行性。

基于融合网络的分布式流媒体服务，由于视频提供者的上行带宽限制，可能不能为接收者提供足够的视频数据，需要多个发送者为单一接收者共同提供所需视频数据[2-4]。基于SVC或FGS（Fine Granularity Scalability）视频编码源，如何选择多发送者为单一接收者服务，文献[4]做出了一些实效性的工作。所谓多发送者，它们的上行带宽可能不同，可能持相同视频编码源中的不同比例。基于文献[4]的工作基础，文章提出一个新的多发送者选择算法，算法可以取得用尽可能少的发送者为单一接收者提供极大化的视频传送服务。

2 问题描述（Problem description）

SVC技术将视频编码成基本层和增强层，基本层具有低比特率、独立解码、独立传输。增强层用来增强基本层的视频质量，不能独立解码，在传输中增强层可任意截断传输，其截断的粒度可达到比特层面，解码器接收的增强层信息越多，解码质量就越好。因视频增强层的码流可被截断传输并解码，对于同一个编码流，低解码质量的码流总是高解码质量码流的前缀。

在分布式服务的流媒体系统中，各终端既是视频的接收者，同时也是视频的提供者。作为提供者的终端或因网络异构其出口带宽受限、或因仅持有部分增强层编码，它们不足以为某一接收者提供全部所需要的视频，所以这类流媒体传输中需要多对一的传输策略。这种传输策略在提供个性化服务的同时，复杂了多发送者的选择问题。一个合格的候选发送者需要定义三个参数：数据传输时间、上行带宽和持有的编码流前缀。一个接收者需要定义两个参数：下行带宽和视频质量的需求等级（即增强层编码流前缀）。表1汇总了这些参数的定义和描述。

视频传输服务通常以一个自然编码帧作为发送单元，考虑到分层编码视频的解码原理和复杂性，基本层编码数据需要单独传送，增强层编码数据可根据不同情况进行可伸缩截断传送，基本层数据的传输可使用早期的一些优化算法[5]来实施，文章在这里只讨论传输增强层编码帧的多发送者选择问题。让代表一个自然编码帧的播放时间，表示候选发送者的个数，对于接收者的某一传输帧要求满足公式（1）。

（1）

视频解码质量通常用率失真参数来衡量以及评价传输算法，如优化的率失真传输算法。对于SVG编码视频来说，解码器得到的增强层编码前缀越长，其率失真越小[4]。因此，可以将极小化率失真传输策略简化为极大化编码前缀获取策略。

为求解问题方便，分两步走，第一步寻找一组有效的候选发送者。先通过一些网络技术，来获得“意愿发送者”的网络响应和传输时间，如RTT，根据它们的响应时间，预设定一组意愿发送者，这些发送者可能持有相同视频增强层编码数据的不同比例，它们被称之为一组候选发送者。

对于一组候选发送者，每一个发送者贡献自己持有的一部分视频编码数据，如图1中持有编码数据的发送者贡献，即自己的全部数据，持有编码数据的发送者贡献部分，所以接收者能获得的编码数据为。

若某一接收者视频需求为，文章讨论在发送者中寻求一组传送分配方案，来极大地满足接收者的视频质量需求，这样的一组传送分配方案应满足公式（2）。

（2）

其中，中的数据应互不重叠且顺序相连，构成一个完整的编码前缀。求解满足公式（2）的传送方案属于整数线性规划求解问题，即NP难问题[6]。

3 发送者选择算法（Algorithm for selection senders）

算法的主要思想是从候选发送者中选一组尽可能少的实际发送者个数，来满足接收端的最大质量（最长编码前缀）需求。先把所有候选发送者的从小到大排序，即形成，根据目标需求逐个扫描，寻求最大匹配，若满足要求算法完成，否则对余下的部分继续本算法。详细算法描述如下。为书写简明，用表代替。

最小发送集选择算法MSSA（Minimum Senders Set Algorithm）：

输入：。

输出：。

（1）取；

（2）从小到大排序表；

（3）如果表中每一项都或而，则停止算法；

（4）先从头扫描表，若遇有，则输出，停止算法；

（5）否则，从表尾开始扫描，若遇到有或者已到达表头，则停止循环，并记下循环变量为，并做如下工作。

a.输出；

b.重置和；

c.重置表（其中，若，则让），回到（3）步继续。

算法最后按（4）和（5）第a步的输出顺序形成一个最终多发送者的分配方案。第一个发送者贡献的是增强层视频编码的首部分，其余发送者相继贡献增强层视频编码的后续部分，它们连接起来形成一个完整的编码前缀。算法若最后终止于（4）步则说明能完全满足接收者的最大需求，否则终止于（3）步的话，则说明尽可能极大地满足接收者的需求。

MSSA算法的时间复杂性主要在排序上，算法有两个优化性能：最大分配和尽可能小的发送者个数，下面给出最大分配的分析证明，发送者数目的分析由实验给出。

结论：算法输出的结果满足，即各发送者贡献的编码段是无缝连接的。

引论：给定一组持不全相同编码长度和相应上行带宽的发送者，以及单个接收者条件，经MSSA算法，可以最大分配来满足接收者视频质量的需要。

证明：分两种情况来证明，不管算法循环多少轮，只要是算法结束于步骤（4），很明显输出的结果能完全满足接收者的最大需求。现在来证明算法结束于步骤（3）的情况。理论上在（3）步骤结束算法，说明候选发送者们已经用尽自己的资源，做到了尽最大努力，同时结论中的数据连续性可保证其输出是极大的。

4 实验与分析（Experiment and analysis）

实验和文献[4]的算法进行比较，试验设计一个统计模型，根据SVC编码的特性，编码流由基本层和可伸缩的增强层组成，增强层按位平面编码（一般在几个位平面以内）。试验模型只考虑增强层截断传输问题。考虑到位平面编码技术，对于发送者持有的编码流和接受者需求的编码流，虽然可以说是任意长度的，但实际上是限于几个质量等级的，所以发送者的持有量和接收者的需求量按编码的位平面数分级分类，但发送者的有效上行带宽具有统计特性，实验中可以随机生成。所以对于一组候选发送者，其持有的增强层长度从固定的几个等级中随机选取，其输出带宽则随机生成。根据一段The firm编码源，如图2所示，按单帧，算法运行1000帧次，MSSA算法有85%集中在一两个发送者，只有当候选发送者们的输出带宽均细小时，才出现多个发送者的情况，而文献[4]算法，98%以上是多发送者结果（4个以上），如图3所示。

融合网络下，在分布式流媒体服务体系中，发送者们具有频繁进出和输出带宽不稳定的特点[7]，所以发送者选择算法主要应考虑用尽可能小的发送者数去满足需求者的最大质量需求，保持系统地稳定性，MSSA算法具有这方面的特点。

参考文献（References）

[1] Chris Develder，et al.Delivering scalable video with QoS to the

home[J]. Telecommunication Systems，2012，49（1）：129-148.

[2] Magharei，N.and Rejaie，R..Adaptive receiver-driven streaming

from multiple senders.ACM/Springer Multimedia System

J.2006，11（6）：1-18.

[3] Shabnam Mirshokraie，Mohamed Hefeeda.Live peer-to-peer

streaming with scalable video coding and networking coding[J].

Feb.2010 Proceedings of the first annual ACM SIGMM

conference on Multimedia systems，102-107.

[4] Hefeeda，M.and Hsu，C.-H.Rate-distortion optimized streaming

of fine-grained scalable video sequences[J].ACM Trans.

Multimedia Comput. Commun.Appl.4，2008：32-37.

[5] 谢建国，姜灵敏，陈松乔.VBR流式视频的最短路径率平滑传

输算法[J].计算机学报，2004，27（3）：357-364.

[6] Cormen，T.，et al.Introduction to Algorithms[M].MIT Press（2nd

ed），Cambridge，MA.2001.

[7] 万成威，邬江兴，兰巨龙.P2P流媒体稳态传输模型分析[J].通信

学报，2012，33（2）：132-140.

作者简介：

谢建国（1964-），男，博士，教授.研究领域：计算机网络，数

字媒体传输.