新颖的实时视频流传输模式

王 田

（华侨大学 计算机科学与技术学院，福建 厦门361021）

0 引 言

视频传输是一种极为消耗网络带宽的应用，而传统的视频传输模式却不能很好地支持这种应用。一般来说，现在的视频传输有两种基本的模式，其一是客户机－服务器模型 （C／S），视频流从源端产生后，先送到服务器，用户再从服务器取得该视频流［1，2］。这种模式实现比较简单，但是却会给服务器端带来很重的负担［3］，特别是当视频用户的数量增多的时候。与之相比，点对点的传输模式［4－6］（P2P）可以减轻服务器端的负担，因为每一个视频源端充当了服务器的功能，因此具有去中心化、可扩展性强、健壮性及负载均衡等优点。然而这种模式对源端机器的计算能力有较高的要求，这无疑会增加源端的成本，比如IP摄像头就需要自带CPU。一般来说，源端产生的视频流还需要保存起来，已备后续的查询，源端也没有这么大的存储空间。此外，这两种传统模式的另外一个问题是，网络传输的不稳定性会导致当前的视频传输质量不稳定甚至中断。

为了解决上述问题，本文提出一种新颖的视频传输模式。基本思想是，多个视频服务器组成一个组来协同提供视频传输服务。多个服务器不但能互相减轻负担来支持大量的视频用户，更重要的是，当某个传输信道由于拥塞或者其他因素而不可用的时候，多个服务器可以提供更多的传输通道供选择，从而具有更好的健壮性［7，8］。这将会提高视频传输系统的吞度量从而使更多的用户得到服务。在本文所提的框架中，任何一个服务器都可以给一对源－目标对（如IP摄像头和远程用户之间）提供服务。甚至当一个服务器不能为之服务时，还可以请求另外一个服务器来帮助转发视频流。本文的目的是协调多个服务器来支持尽可能多的视频流 （视频源－－用户对）。

1 相关工作

近年来，成千上万个摄像头几乎遍布城市的每一个角落，普通居民能像以前的警察一样看到许多地方的实时视频，比如实时视频监控系统［9－11］。视频流应用或者为用户提供高质量的现场视频或者为用户提供按需点播服务。一般来说，视频应用服务包含有视频服务器、客户端还有连接二者的网络。客户端是用户，他们选择需要播放的网络视频，而服务器端存储着这些视频并且当收到请求的时候将视频流推送至客户端。

传统的客户机－服务器模型会导致服务器端巨大的带宽消耗，并且单个服务器也不利于应用规模的扩大。另一方面，点对点的视频流传输模型虽可以减轻服务器端的负担［12］，因为每一个视频源端充当了服务器的功能，然而这种模式对源端机器的计算能力有较高的要求，这无疑会增加源端的成本，比如IP摄像头。一般来说，源端产生的视频流还需要存储起来，已备后续的查询，点对点模式下的源端也没有这么大的存储空间。本文提出的多服务器群组传输模式将解决这一问题。

另外，本文的多服务器群组传输模式还充分利用了“服务器多样性”。Cui和Frossard在文［13，14］中也利用了该特性在来不稳定的网络中由多个服务器来共同为一个客户端服务。单个视频流可能被分成许多子流，分别从不同的服务器向客户端推送，客户端收到多个子流后再重组还原成原始数据流。本文的不同之处在于，为了保证传输的实时性和降低设备处理的复杂性，一个视频数据流不允许被分成多个子流。重点考虑的问题是如何协调多个服务器来服务尽可能多的视频数据流。

2 视频传输框架

本文所提的视频传输模式如图1所示，包含视频源端、服务器端和用户端三个方面。视频源端是产生视频流的设备而用户端是请求得到相应的视频流的用户。中间端是多个服务器，由网络所连接并协同地为视频流服务。在本文中，我们也称服务器为NVS （network video server），因为NVS具有较强的视频处理能力和较大的存储空间［15］。视频流由源端产生后先送到服务器组，用户再从服务器组取得数据流。多个服务器之间相互交流带宽等信息，从而为用户提供最好的服务。这既可以为视频流选择最好的服务器，也可以在服务器之间存储多个原始视频流的备份。

用户端ui向源端si请求视频流fi，视频流经某个NVS处理后再转发至用户。我们的目的是在此模式下最大化同时传送的视频流的数目。假设对被用户ui请求的视频流，链路的最小可用带宽不应低于fi，比如，为了保证MPEG－1视频流的连续传输，网络的可用带宽不能低于1.5Mbps。为了表示的方便，文本用fi既表示流的大小也表示该流本身。另外一个假设是NVS可以测量到数据源端和用户端的带宽大小，比如借助已有的带宽测量工具［16］。

图1 视频流传输模式

3 最大流传输问题

3.1 问题定义

在介绍本文提出的问题之前，先介绍一个关于流完整性限制的定义：

定义 流完整性 （flow integrality，FI）限制－－一个流从源端发送到目的端的过程中仅仅通过一条路径，即该流不能再分。

最大流问题 （maximum streaming flows，MSF）：系统中有一组源节点S＝ ｛s1，s2，…，sm｝，一组服务器NVSs＝ ｛NVS1，NVS2，…，NVSh｝和一组目标用户U＝ ｛u1，u2，…，um｝。源节点和用户节点都通过有线或者无线网络连接到NVSs上。源节点推送数据流到服务器上而用户节点则从服务器取回数据流。每条连接NVS的链路 （u，v）（包括NVS之间的链路）都具有一个链路容量c（u，v）。每个源节点si都将产生一个fi大小的视频流。用户节点ui期望得到源节点si产生的视频流。流在传输的过程中必须满足流完整性限制，且最多可以被服务器群组转发一跳。目标是在链路带宽的允许下，最大化网络中成功传输的数据流数目。

之所以最多只让服务器群组转发一跳，一方面是可以满足实时性的需求因为转发多跳会导致更大的延迟，另外从我们后面的实验结果可以看出，转发一跳和多跳的结果差别不大，而且一跳转发比较简单容易实现。

图2给出了一个基于该框架传输视频流的例子。s1和s2产生的数据流大小分别为7和6，链路带宽均附在图中链路旁。对于f1来说，最优的路径是s1－NVS1－u1，而对于f2来 说， 最 优 的 传 输 路 径 则 是s2－NVS2－NVS1－u2， 因 为NVS2至u2的链路带宽不足以传输f2，所以要借助服务器NVS1来帮助转发，这就是服务器多样性特性的体现，多个服务器可以共同协作，提高视频流的吞吐量。

图2 MSF问题示例

3.2 复杂度分析

通过该问题的复杂性分析，我们可以得出如下结论：

定理 MSF问题是NP－难问题。

证明：如图3所示，在构造的场景中，假设只有3个NVSs，且所有源端视频流只能连接NVS1，NVS1连接到NVS2和NVS3，它们之间的链路带宽分别表示为C12和C13。数据源和用户连接到NVSs的带宽均为无穷大 （如果存在连接的话）。如此以来，带宽瓶颈只在NVSs之间。可以将C12和C13分别看作是2个箱子的容量，而将数据流f1，f2，…，fk看作是待装入箱子的货物，显然，这就是著名的装箱问题，目的是要如何将待选的货物f1，f2，…，fk装入这两个箱子中，使得箱子能装下尽可能多的货物量。而装箱问题本身就是一个已知的NP－难问题，因此MSF问题肯定是一个NP－难问题。

图3 MSF问题的一个特例

3.3 启发式算法

由于MSF问题是NP－难问题，多项式时间内最优算法不易找到 （严格来说，除非NP＝P）。本文设计了一种快速的启发式算法。该算法的基本思想是先将所有的流按照大小排序，尽量先服务最小的流，如果该流能直接被某服务器服务，则直接分配该流，这类似于操作系统中处理器调度的小作业优先原理。若不能，则需要借助另外一个服务器来转发。为了表示某条链路li是否还有剩余带宽，设置一个变量fi＊，初始状态为NULL，表示还有剩余带宽。对于一个流si来说，NVS之间可供选择的链路可能有很多，先任意分配给一条链路的＝NULL的，如果该链路不再有剩余带宽，则该链路的＝fi。如果所有可选的链路的f＊都不为空，则尝试将这些链路已经分配的流分配给其他f＊＝NULL的链路，即还有剩余空间的链路。若某条链路在移出某些流后重新具有了剩余带宽，则将流fi分配给该链路，否则该流最终将不能被服务。

具体算法如图4所示，NU表示要最优化的视频流数目。初始时刻，将视频流按照流的大小自小到大排序，先选择当前最小的流 （假设是fi），如果此流能被某条链路服务，则直接分配该流。否则，寻找某条仍有带宽剩余但不足以服务该流的链路，并分配之，然后修改该链路的f＊，使之不为空。若找不到这样一条链路，则寻找一条该流的候选链路，将候选链路中的已分配的流移动至其它链路，若移动完后该链路f＊的状态变为空，则可将fi分配至该链路，处理方法同上述过程。若最后fi都不能分配到任何一条链路，则fi将被剩下，继续考虑下一条流fi＋1。

图4 MSF算法

如此反复，最后不能分配的流则是不能成功发送的，此外，成为某条链路里的f＊的流也是不能成功发送的，因为链路带宽不足以支持该流的大小。所以最后NU要去掉这两部分的数目。

4 实验结果

本节对提出的视频传输模式进行模拟实验，工具用的是MATLAB。本文以两种传统的视频传输模式为参考进行对比，其一是P2P模式，其二是单个服务器的C／S模式。为了模拟网络带宽的动态性，本文假设网络带宽服从lognormal分布，基于Kun－chan等人的研究［17］，本文假设视频流也服从log－normal分布。如果没有特别指出，文本设置网络点到点的带宽期望为1000Kbps（接近文［18］的结论1.06Mbps），设置视频流大小的期望值为600Kbps。为了模拟出网络带宽的动态性，我们设置网络带宽的标准偏差为50000，设置视频流大小的标准方差为10000。模拟场景中有2000个用户分别请求2000个视频流。

图5是发送失败的视频流 （总数2000）的示例，网络带宽期望值从800Mbps逐渐增加到1000Mbps。在这组实验中，我们一共设置了3个NVS服务器。如图所示，随着网络带宽的逐渐增大，所有模式所实现的失败视频流均呈下降趋势，这是因为随着带宽的增大可以支持更多的视频流。但是MSF模式一直表现出更好的性能，大概能超出C／S和P2P模式235%－1400%，这充分体现了本文所提框架和算法的优越性。

图5 连接失败的视频流与带宽大小的关系

图6展示了当服务器的数目从1增加到5时，发送失败的视频流数。显然，当只有一个服务器时，MSF的性能接近于C／S模式，甚至可能还不如P2P模式，但随着服务器数目的增加，失败的视频流数目呈现出指数级下降趋势，最终性能要远胜于其它两组传输模式。这是由于更多的服务器意味着更多的可选网络链路，从而有更多的协调合作，可以支持更多的视频流。

图6 连接失败的视频流与服务器数目的关系

图7模拟了网络动态性情况下各种模式的表现情况。众所周知，网络带宽是随时改变的，尤其是在无线或者移动环境下。本实验让网络带宽的标准方差从10000逐渐增大到50000。显然，方差越大，网络动态性越强，网络状态越不稳定。如图所示，随着标准方差的增大，这3种模式表现出来的性能都随之下降 （失败视频流数目增多），但较之P2P和C／S模式，MSF模式下失败视频流的数目增长相对缓慢得多，这说明MSF模式更适合于网络不稳定的环境中，多个服务器的模式使得系统更具健壮性和稳定性。

图7 连接失败的视频流与网络动态性的关系

5 结束语

本文研究了实时传输视频流的问题，提出了一种新颖的传输框架，利用多个服务器的相互协作以共同支持更多的视频流服务。在此框架下提出了MSF问题，目的是最大化同时传输的视频流数目。同时设计了有效的启发式算法，以支持尽可能多的视频流。通过模拟实验，与传统的P2P模式和C／S模式比较，MSF模式及其相应的算法能同时支持更多的视频流，并更能容忍网络动态性对传输的影响，多个服务器之间的相互配合也有利于服务器之间的负载均衡和系统的健壮性。

［1］WANG Jianyue，JIN Lei.The substation video monitoring system based on C／S model［J］.Electric Age，2009 （3）：1－2 （in Chinese）.［王建跃，靳雷.基于C／S模式的变电站视频监控系统，［J］电气时代，2009 （3）：1－2.］

［2］CHEN Jianfeng，XU Haojie，DAI Songshi，et al.MRI equipment remote monitor and control system based on multilayer structure of C／S，［J］Journal of Computer Applications，2011，31 （12）：3429－3433 （in Chinese）.［陈建峰，许 豪 杰，戴松世，等.基于C／S多层结构的核磁共振成像设备远程监控系统［J］.计算机应用，2011，31 （12）：3429－3433.］

［3］Zhu X，Deng H，Chen Z，et al.Design of large－scale video surveillance system based on P2Pstreaming ［C］／／3rd International Workshop on Intelligent Systems and Applications，2011：1－4.

［4］KANG Hao，HE Su，JIANG Zhihong，et al.Research on audio／video data recovery and online detection method of P2P－TV for content monitoring ［J］.Application Research of Computers，2009，29 （1）：187－196 （in Chinese）.［康浩，何速，姜志宏，等.面向内容监管的P2P－TV音视频数据还原与在线检测方法研究 ［J］.计算机应用研究，2012，29 （1）：187－196.］

［5］SHEN Shijun，LI Sanli.P2P－based video－on－demand systems：A survey ［J］.Chinese Journal of Computers，2010，33 （4）：613－624 （in Chinese）.［沈时军，李三立.基于P2P的视频点播系统综述 ［J］.计算机学报，2010，33 （4）：613－624.］

［6］LI Zhenzhen，ZHANG Zhibin，DU Yuejin.Survey on P2Pvideo streaming systems［J］.Application Research of Computers，2009，26 （8）：2801－2806 （in Chinese）.［李真真，张志斌，杜跃进.P2P在线视频研究综述 ［J］.计算机应用研究，2009，26（8）：2801－2806.］

［7］WU Qingxiang，SHUAI Jianmei.A multi－server collaborative parallel downloading mechanism with file dynamic adjustment［J］.Electronic Technology，2011 （8）：10－11 （in Chinese）.［吴庆响，帅建梅.一种多服务器协作文件动态调整并行下载机制 ［J］.电子技术，2011 （8）：10－11.］

［8］Karic M，Martinovic G，Hocenski Z.Implementation and simulation results of multipletotal bandwidth server mechanism［C］／／The 8th International Symposium on Intelligent Systems and Informatics，2010：423－427.

［9］Bloisi D，Iocchi L.Argos－a video surveillance system for boat traffic monitoring in venice ［J］.International Journal of Pattern Recognition and Artificial Intelligence，2009，23 （7）：1477－1502.

［10］Moon H M，Pan S B.A new human identification method for intelligent video surveillance system ［C］／／Proceedings of 19th International Conference on Computer Communications and Networks，2010：1－6.

［11］ZHAO Chunyuan，LI Meng，HAN Huishan，et al.Design and implementation of wireless video monitor system based on ARM9 ［J］.Computer Engineering and Design，2012，33（2）：529－534 （in Chinese）.［赵春媛，李萌，韩会山，等.基于ARM9的无线视频监控系统设计与实现 ［J］.计算机工程与设计，2012，33 （2）：529－534.］

［12］Wu C，Li B，Zhao S.Diagnosing network－wide P2Plive streaming inefficiencies ［C］／／Infocom，2009：2731－2735.

［13］Cui Huali，Qian Depei，Zhang Xingjun，et al.Video streaming over wireless mesh networks with multi－gateway support［C］／／IEEE／IFIP 8th International Conference on Embedded and Ubiquitous Computing，2010：268－272.

［14］Frossard P，De Martin J C，Reha Civanlar M.Media streaming with network diversity ［C］／／Proceedings of the IEEE，2008：39－53.

［15］Girgensohn A，Kimber D，Vaughan J，et al.Dots：Support for effective video surveillance ［C］／／Proceedings of the 15th International Conference on Multimedia，2007：423－432.

［16］Koitani K，Hasegawa G，Murata M.Measuring available bandwidth of multiple parts on end－to－end network path［C］／／IEEE International Workshop Technical Committee on Communications Quality and Reliability，2012：1－6.

［17］Chan Lan K，Heidemann J.A measurement study of correlation of Internet flow characteristics ［J］.Computer Networks，2006，50 （1）：46－62.

［18］Yoshihisa T.An interruption time reduction scheme with prefetch for hybrid video broadcasting environments ［C］／／Ibaraki，Japan：IEEE Wireless Communications and Networking Conference，2011：2071－2076.