新穎的實(shí)時(shí)視頻流傳輸模式

王 田

（華僑大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，福建 廈門361021）

0 引 言

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

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

1 相關(guān)工作

近年來，成千上萬個(gè)攝像頭幾乎遍布城市的每一個(gè)角落，普通居民能像以前的警察一樣看到許多地方的實(shí)時(shí)視頻，比如實(shí)時(shí)視頻監(jiān)控系統(tǒng)［9－11］。視頻流應(yīng)用或者為用戶提供高質(zhì)量的現(xiàn)場視頻或者為用戶提供按需點(diǎn)播服務(wù)。一般來說，視頻應(yīng)用服務(wù)包含有視頻服務(wù)器、客戶端還有連接二者的網(wǎng)絡(luò)。客戶端是用戶，他們選擇需要播放的網(wǎng)絡(luò)視頻，而服務(wù)器端存儲著這些視頻并且當(dāng)收到請求的時(shí)候?qū)⒁曨l流推送至客戶端。

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

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

2 視頻傳輸框架

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

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

圖1 視頻流傳輸模式

3 最大流傳輸問題

3.1 問題定義

在介紹本文提出的問題之前，先介紹一個(gè)關(guān)于流完整性限制的定義：

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

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

之所以最多只讓服務(wù)器群組轉(zhuǎn)發(fā)一跳，一方面是可以滿足實(shí)時(shí)性的需求因?yàn)檗D(zhuǎn)發(fā)多跳會(huì)導(dǎo)致更大的延遲，另外從我們后面的實(shí)驗(yàn)結(jié)果可以看出，轉(zhuǎn)發(fā)一跳和多跳的結(jié)果差別不大，而且一跳轉(zhuǎn)發(fā)比較簡單容易實(shí)現(xiàn)。

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

圖2 MSF問題示例

3.2 復(fù)雜度分析

通過該問題的復(fù)雜性分析，我們可以得出如下結(jié)論：

定理 MSF問題是NP－難問題。

證明：如圖3所示，在構(gòu)造的場景中，假設(shè)只有3個(gè)NVSs，且所有源端視頻流只能連接NVS1，NVS1連接到NVS2和NVS3，它們之間的鏈路帶寬分別表示為C12和C13。數(shù)據(jù)源和用戶連接到NVSs的帶寬均為無窮大 （如果存在連接的話）。如此以來，帶寬瓶頸只在NVSs之間?？梢詫12和C13分別看作是2個(gè)箱子的容量，而將數(shù)據(jù)流f1，f2，…，fk看作是待裝入箱子的貨物，顯然，這就是著名的裝箱問題，目的是要如何將待選的貨物f1，f2，…，fk裝入這兩個(gè)箱子中，使得箱子能裝下盡可能多的貨物量。而裝箱問題本身就是一個(gè)已知的NP－難問題，因此MSF問題肯定是一個(gè)NP－難問題。

圖3 MSF問題的一個(gè)特例

3.3 啟發(fā)式算法

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

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

圖4 MSF算法

如此反復(fù)，最后不能分配的流則是不能成功發(fā)送的，此外，成為某條鏈路里的f＊的流也是不能成功發(fā)送的，因?yàn)殒溌穾挷蛔阋灾С衷摿鞯拇笮?。所以最后NU要去掉這兩部分的數(shù)目。

4 實(shí)驗(yàn)結(jié)果

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

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

圖5 連接失敗的視頻流與帶寬大小的關(guān)系

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

圖6 連接失敗的視頻流與服務(wù)器數(shù)目的關(guān)系

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

圖7 連接失敗的視頻流與網(wǎng)絡(luò)動(dòng)態(tài)性的關(guān)系

5 結(jié)束語

本文研究了實(shí)時(shí)傳輸視頻流的問題，提出了一種新穎的傳輸框架，利用多個(gè)服務(wù)器的相互協(xié)作以共同支持更多的視頻流服務(wù)。在此框架下提出了MSF問題，目的是最大化同時(shí)傳輸?shù)囊曨l流數(shù)目。同時(shí)設(shè)計(jì)了有效的啟發(fā)式算法，以支持盡可能多的視頻流。通過模擬實(shí)驗(yàn)，與傳統(tǒng)的P2P模式和C／S模式比較，MSF模式及其相應(yīng)的算法能同時(shí)支持更多的視頻流，并更能容忍網(wǎng)絡(luò)動(dòng)態(tài)性對傳輸?shù)挠绊?，多個(gè)服務(wù)器之間的相互配合也有利于服務(wù)器之間的負(fù)載均衡和系統(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］電氣時(shí)代，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é)構(gòu)的核磁共振成像設(shè)備遠(yuǎn)程監(jiān)控系統(tǒng)［J］.計(jì)算機(jī)應(yīng)用，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）.［康浩，何速，姜志宏，等.面向內(nèi)容監(jiān)管的P2P－TV音視頻數(shù)據(jù)還原與在線檢測方法研究 ［J］.計(jì)算機(jī)應(yīng)用研究，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）.［沈時(shí)軍，李三立.基于P2P的視頻點(diǎn)播系統(tǒng)綜述 ［J］.計(jì)算機(jī)學(xué)報(bào)，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）.［李真真，張志斌，杜躍進(jìn).P2P在線視頻研究綜述 ［J］.計(jì)算機(jī)應(yīng)用研究，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）.［吳慶響，帥建梅.一種多服務(wù)器協(xié)作文件動(dòng)態(tài)調(diào)整并行下載機(jī)制 ［J］.電子技術(shù)，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）.［趙春媛，李萌，韓會(huì)山，等.基于ARM9的無線視頻監(jiān)控系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn) ［J］.計(jì)算機(jī)工程與設(shè)計(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.