王 田

（華僑大學 計算機科學與技術學院，福建 廈門361021）

0 引 言

視頻傳輸是一種極為消耗網絡帶寬的應用，而傳統(tǒng)的視頻傳輸模式卻不能很好地支持這種應用。一般來說，現在的視頻傳輸有兩種基本的模式，其一是客戶機－服務器模型 （C／S），視頻流從源端產生后，先送到服務器，用戶再從服務器取得該視頻流［1，2］。這種模式實現比較簡單，但是卻會給服務器端帶來很重的負擔［3］，特別是當視頻用戶的數量增多的時候。與之相比，點對點的傳輸模式［4－6］（P2P）可以減輕服務器端的負擔，因為每一個視頻源端充當了服務器的功能，因此具有去中心化、可擴展性強、健壯性及負載均衡等優(yōu)點。然而這種模式對源端機器的計算能力有較高的要求，這無疑會增加源端的成本，比如IP攝像頭就需要自帶CPU。一般來說，源端產生的視頻流還需要保存起來，已備后續(xù)的查詢，源端也沒有這么大的存儲空間。此外，這兩種傳統(tǒng)模式的另外一個問題是，網絡傳輸的不穩(wěn)定性會導致當前的視頻傳輸質量不穩(wěn)定甚至中斷。

為了解決上述問題，本文提出一種新穎的視頻傳輸模式?；舅枷胧?，多個視頻服務器組成一個組來協(xié)同提供視頻傳輸服務。多個服務器不但能互相減輕負擔來支持大量的視頻用戶，更重要的是，當某個傳輸信道由于擁塞或者其他因素而不可用的時候，多個服務器可以提供更多的傳輸通道供選擇，從而具有更好的健壯性［7，8］。這將會提高視頻傳輸系統(tǒng)的吞度量從而使更多的用戶得到服務。在本文所提的框架中，任何一個服務器都可以給一對源－目標對（如IP攝像頭和遠程用戶之間）提供服務。甚至當一個服務器不能為之服務時，還可以請求另外一個服務器來幫助轉發(fā)視頻流。本文的目的是協(xié)調多個服務器來支持盡可能多的視頻流 （視頻源－－用戶對）。

1 相關工作

近年來，成千上萬個攝像頭幾乎遍布城市的每一個角落，普通居民能像以前的警察一樣看到許多地方的實時視頻，比如實時視頻監(jiān)控系統(tǒng)［9－11］。視頻流應用或者為用戶提供高質量的現場視頻或者為用戶提供按需點播服務。一般來說，視頻應用服務包含有視頻服務器、客戶端還有連接二者的網絡?？蛻舳耸怯脩簦麄冞x擇需要播放的網絡視頻，而服務器端存儲著這些視頻并且當收到請求的時候將視頻流推送至客戶端。

傳統(tǒng)的客戶機－服務器模型會導致服務器端巨大的帶寬消耗，并且單個服務器也不利于應用規(guī)模的擴大。另一方面，點對點的視頻流傳輸模型雖可以減輕服務器端的負擔［12］，因為每一個視頻源端充當了服務器的功能，然而這種模式對源端機器的計算能力有較高的要求，這無疑會增加源端的成本，比如IP攝像頭。一般來說，源端產生的視頻流還需要存儲起來，已備后續(xù)的查詢，點對點模式下的源端也沒有這么大的存儲空間。本文提出的多服務器群組傳輸模式將解決這一問題。

另外，本文的多服務器群組傳輸模式還充分利用了“服務器多樣性”。Cui和Frossard在文［13，14］中也利用了該特性在來不穩(wěn)定的網絡中由多個服務器來共同為一個客戶端服務。單個視頻流可能被分成許多子流，分別從不同的服務器向客戶端推送，客戶端收到多個子流后再重組還原成原始數據流。本文的不同之處在于，為了保證傳輸的實時性和降低設備處理的復雜性，一個視頻數據流不允許被分成多個子流。重點考慮的問題是如何協(xié)調多個服務器來服務盡可能多的視頻數據流。

2 視頻傳輸框架

本文所提的視頻傳輸模式如圖1所示，包含視頻源端、服務器端和用戶端三個方面。視頻源端是產生視頻流的設備而用戶端是請求得到相應的視頻流的用戶。中間端是多個服務器，由網絡所連接并協(xié)同地為視頻流服務。在本文中，我們也稱服務器為NVS （network video server），因為NVS具有較強的視頻處理能力和較大的存儲空間［15］。視頻流由源端產生后先送到服務器組，用戶再從服務器組取得數據流。多個服務器之間相互交流帶寬等信息，從而為用戶提供最好的服務。這既可以為視頻流選擇最好的服務器，也可以在服務器之間存儲多個原始視頻流的備份。

用戶端ui向源端si請求視頻流fi，視頻流經某個NVS處理后再轉發(fā)至用戶。我們的目的是在此模式下最大化同時傳送的視頻流的數目。假設對被用戶ui請求的視頻流，鏈路的最小可用帶寬不應低于fi，比如，為了保證MPEG－1視頻流的連續(xù)傳輸，網絡的可用帶寬不能低于1.5Mbps。為了表示的方便，文本用fi既表示流的大小也表示該流本身。另外一個假設是NVS可以測量到數據源端和用戶端的帶寬大小，比如借助已有的帶寬測量工具［16］。

圖1 視頻流傳輸模式

3 最大流傳輸問題

3.1 問題定義

在介紹本文提出的問題之前，先介紹一個關于流完整性限制的定義：

定義 流完整性 （flow integrality，FI）限制－－一個流從源端發(fā)送到目的端的過程中僅僅通過一條路徑，即該流不能再分。

最大流問題 （maximum streaming flows，MSF）：系統(tǒng)中有一組源節(jié)點S＝ ｛s1，s2，…，sm｝，一組服務器NVSs＝ ｛NVS1，NVS2，…，NVSh｝和一組目標用戶U＝ ｛u1，u2，…，um｝。源節(jié)點和用戶節(jié)點都通過有線或者無線網絡連接到NVSs上。源節(jié)點推送數據流到服務器上而用戶節(jié)點則從服務器取回數據流。每條連接NVS的鏈路 （u，v）（包括NVS之間的鏈路）都具有一個鏈路容量c（u，v）。每個源節(jié)點si都將產生一個fi大小的視頻流。用戶節(jié)點ui期望得到源節(jié)點si產生的視頻流。流在傳輸的過程中必須滿足流完整性限制，且最多可以被服務器群組轉發(fā)一跳。目標是在鏈路帶寬的允許下，最大化網絡中成功傳輸的數據流數目。

之所以最多只讓服務器群組轉發(fā)一跳，一方面是可以滿足實時性的需求因為轉發(fā)多跳會導致更大的延遲，另外從我們后面的實驗結果可以看出，轉發(fā)一跳和多跳的結果差別不大，而且一跳轉發(fā)比較簡單容易實現。

圖2給出了一個基于該框架傳輸視頻流的例子。s1和s2產生的數據流大小分別為7和6，鏈路帶寬均附在圖中鏈路旁。對于f1來說，最優(yōu)的路徑是s1－NVS1－u1，而對于f2來 說， 最 優(yōu) 的 傳 輸 路 徑 則 是s2－NVS2－NVS1－u2， 因 為NVS2至u2的鏈路帶寬不足以傳輸f2，所以要借助服務器NVS1來幫助轉發(fā)，這就是服務器多樣性特性的體現，多個服務器可以共同協(xié)作，提高視頻流的吞吐量。

圖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 啟發(fā)式算法

由于MSF問題是NP－難問題，多項式時間內最優(yōu)算法不易找到 （嚴格來說，除非NP＝P）。本文設計了一種快速的啟發(fā)式算法。該算法的基本思想是先將所有的流按照大小排序，盡量先服務最小的流，如果該流能直接被某服務器服務，則直接分配該流，這類似于操作系統(tǒng)中處理器調度的小作業(yè)優(yōu)先原理。若不能，則需要借助另外一個服務器來轉發(fā)。為了表示某條鏈路li是否還有剩余帶寬，設置一個變量fi＊，初始狀態(tài)為NULL，表示還有剩余帶寬。對于一個流si來說，NVS之間可供選擇的鏈路可能有很多，先任意分配給一條鏈路的＝NULL的，如果該鏈路不再有剩余帶寬，則該鏈路的＝fi。如果所有可選的鏈路的f＊都不為空，則嘗試將這些鏈路已經分配的流分配給其他f＊＝NULL的鏈路，即還有剩余空間的鏈路。若某條鏈路在移出某些流后重新具有了剩余帶寬，則將流fi分配給該鏈路，否則該流最終將不能被服務。

具體算法如圖4所示，NU表示要最優(yōu)化的視頻流數目。初始時刻，將視頻流按照流的大小自小到大排序，先選擇當前最小的流 （假設是fi），如果此流能被某條鏈路服務，則直接分配該流。否則，尋找某條仍有帶寬剩余但不足以服務該流的鏈路，并分配之，然后修改該鏈路的f＊，使之不為空。若找不到這樣一條鏈路，則尋找一條該流的候選鏈路，將候選鏈路中的已分配的流移動至其它鏈路，若移動完后該鏈路f＊的狀態(tài)變?yōu)榭?，則可將fi分配至該鏈路，處理方法同上述過程。若最后fi都不能分配到任何一條鏈路，則fi將被剩下，繼續(xù)考慮下一條流fi＋1。

圖4 MSF算法

如此反復，最后不能分配的流則是不能成功發(fā)送的，此外，成為某條鏈路里的f＊的流也是不能成功發(fā)送的，因為鏈路帶寬不足以支持該流的大小。所以最后NU要去掉這兩部分的數目。

4 實驗結果

本節(jié)對提出的視頻傳輸模式進行模擬實驗，工具用的是MATLAB。本文以兩種傳統(tǒng)的視頻傳輸模式為參考進行對比，其一是P2P模式，其二是單個服務器的C／S模式。為了模擬網絡帶寬的動態(tài)性，本文假設網絡帶寬服從lognormal分布，基于Kun－chan等人的研究［17］，本文假設視頻流也服從log－normal分布。如果沒有特別指出，文本設置網絡點到點的帶寬期望為1000Kbps（接近文［18］的結論1.06Mbps），設置視頻流大小的期望值為600Kbps。為了模擬出網絡帶寬的動態(tài)性，我們設置網絡帶寬的標準偏差為50000，設置視頻流大小的標準方差為10000。模擬場景中有2000個用戶分別請求2000個視頻流。

圖5是發(fā)送失敗的視頻流 （總數2000）的示例，網絡帶寬期望值從800Mbps逐漸增加到1000Mbps。在這組實驗中，我們一共設置了3個NVS服務器。如圖所示，隨著網絡帶寬的逐漸增大，所有模式所實現的失敗視頻流均呈下降趨勢，這是因為隨著帶寬的增大可以支持更多的視頻流。但是MSF模式一直表現出更好的性能，大概能超出C／S和P2P模式235%－1400%，這充分體現了本文所提框架和算法的優(yōu)越性。

圖5 連接失敗的視頻流與帶寬大小的關系

圖6展示了當服務器的數目從1增加到5時，發(fā)送失敗的視頻流數。顯然，當只有一個服務器時，MSF的性能接近于C／S模式，甚至可能還不如P2P模式，但隨著服務器數目的增加，失敗的視頻流數目呈現出指數級下降趨勢，最終性能要遠勝于其它兩組傳輸模式。這是由于更多的服務器意味著更多的可選網絡鏈路，從而有更多的協(xié)調合作，可以支持更多的視頻流。

圖6 連接失敗的視頻流與服務器數目的關系

圖7模擬了網絡動態(tài)性情況下各種模式的表現情況。眾所周知，網絡帶寬是隨時改變的，尤其是在無線或者移動環(huán)境下。本實驗讓網絡帶寬的標準方差從10000逐漸增大到50000。顯然，方差越大，網絡動態(tài)性越強，網絡狀態(tài)越不穩(wěn)定。如圖所示，隨著標準方差的增大，這3種模式表現出來的性能都隨之下降 （失敗視頻流數目增多），但較之P2P和C／S模式，MSF模式下失敗視頻流的數目增長相對緩慢得多，這說明MSF模式更適合于網絡不穩(wěn)定的環(huán)境中，多個服務器的模式使得系統(tǒng)更具健壯性和穩(wěn)定性。

圖7 連接失敗的視頻流與網絡動態(tài)性的關系

5 結束語

本文研究了實時傳輸視頻流的問題，提出了一種新穎的傳輸框架，利用多個服務器的相互協(xié)作以共同支持更多的視頻流服務。在此框架下提出了MSF問題，目的是最大化同時傳輸的視頻流數目。同時設計了有效的啟發(fā)式算法，以支持盡可能多的視頻流。通過模擬實驗，與傳統(tǒng)的P2P模式和C／S模式比較，MSF模式及其相應的算法能同時支持更多的視頻流，并更能容忍網絡動態(tài)性對傳輸的影響，多個服務器之間的相互配合也有利于服務器之間的負載均衡和系統(tǒng)的健壯性。

［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模式的變電站視頻監(jiān)控系統(tǒng)，［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多層結構的核磁共振成像設備遠程監(jiān)控系統(tǒng)［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）.［康浩，何速，姜志宏，等.面向內容監(jiān)管的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的視頻點播系統(tǒng)綜述 ［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）.［吳慶響，帥建梅.一種多服務器協(xié)作文件動態(tài)調整并行下載機制 ［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的無線視頻監(jiān)控系統(tǒng)設計與實現 ［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.