網(wǎng)絡(luò)流媒體系統(tǒng)中多發(fā)送者選擇算法

摘 要：于SVC視頻服務(wù)的融合網(wǎng)絡(luò)流媒體系統(tǒng)中，存在傳輸網(wǎng)絡(luò)異構(gòu)、終端上行帶寬受限和參與者持有相同SVC視頻編碼源的不同比例?；谶@樣的流媒體系統(tǒng)往往需要多個(gè)發(fā)送者才能服務(wù)一個(gè)接收者。上行帶寬、持有編碼流的比例等是選擇候選發(fā)送者的主要參數(shù)，多參數(shù)優(yōu)化下的多發(fā)送者選擇算法是一個(gè)NP問題。對(duì)于一群候選發(fā)送者，文章提出一個(gè)以盡可能少的發(fā)送者數(shù)去滿足接收者最大需求的選擇算法-MSSA，性能分析顯示本文算法比同類算法有更好的網(wǎng)絡(luò)系統(tǒng)穩(wěn)定性。

關(guān)鍵詞：SVC視頻；融合網(wǎng)絡(luò)；流媒體

中圖分類號(hào)： TP393 文獻(xiàn)標(biāo)識(shí)碼：A

1 引言（Introduction）

流媒體服務(wù)是融合網(wǎng)絡(luò)最能見實(shí)效的也是目前最廣泛的主流應(yīng)用之一[1]。融合網(wǎng)絡(luò)具有傳輸網(wǎng)絡(luò)異構(gòu)、終端多樣性、上下行帶寬不對(duì)稱等特點(diǎn)。在融合網(wǎng)絡(luò)中為多樣性終端提供統(tǒng)一解碼質(zhì)量的視頻服務(wù)是不現(xiàn)實(shí)的，也是不必要的。SVC（Scalability Video Coding）可伸縮視頻或分層視頻編碼技術(shù)（包括H.264中FGS標(biāo)準(zhǔn)）為異構(gòu)網(wǎng)絡(luò)的多樣化流媒體服務(wù)提供了可行性。

基于融合網(wǎng)絡(luò)的分布式流媒體服務(wù)，由于視頻提供者的上行帶寬限制，可能不能為接收者提供足夠的視頻數(shù)據(jù)，需要多個(gè)發(fā)送者為單一接收者共同提供所需視頻數(shù)據(jù)[2-4]?；赟VC或FGS（Fine Granularity Scalability）視頻編碼源，如何選擇多發(fā)送者為單一接收者服務(wù)，文獻(xiàn)[4]做出了一些實(shí)效性的工作。所謂多發(fā)送者，它們的上行帶寬可能不同，可能持相同視頻編碼源中的不同比例?；谖墨I(xiàn)[4]的工作基礎(chǔ)，文章提出一個(gè)新的多發(fā)送者選擇算法，算法可以取得用盡可能少的發(fā)送者為單一接收者提供極大化的視頻傳送服務(wù)。

2 問題描述（Problem description）

SVC技術(shù)將視頻編碼成基本層和增強(qiáng)層，基本層具有低比特率、獨(dú)立解碼、獨(dú)立傳輸。增強(qiáng)層用來增強(qiáng)基本層的視頻質(zhì)量，不能獨(dú)立解碼，在傳輸中增強(qiáng)層可任意截?cái)鄠鬏?，其截?cái)嗟牧６瓤蛇_(dá)到比特層面，解碼器接收的增強(qiáng)層信息越多，解碼質(zhì)量就越好。因視頻增強(qiáng)層的碼流可被截?cái)鄠鬏敳⒔獯a，對(duì)于同一個(gè)編碼流，低解碼質(zhì)量的碼流總是高解碼質(zhì)量碼流的前綴。

在分布式服務(wù)的流媒體系統(tǒng)中，各終端既是視頻的接收者，同時(shí)也是視頻的提供者。作為提供者的終端或因網(wǎng)絡(luò)異構(gòu)其出口帶寬受限、或因僅持有部分增強(qiáng)層編碼，它們不足以為某一接收者提供全部所需要的視頻，所以這類流媒體傳輸中需要多對(duì)一的傳輸策略。這種傳輸策略在提供個(gè)性化服務(wù)的同時(shí)，復(fù)雜了多發(fā)送者的選擇問題。一個(gè)合格的候選發(fā)送者需要定義三個(gè)參數(shù)：數(shù)據(jù)傳輸時(shí)間、上行帶寬和持有的編碼流前綴。一個(gè)接收者需要定義兩個(gè)參數(shù)：下行帶寬和視頻質(zhì)量的需求等級(jí)（即增強(qiáng)層編碼流前綴）。表1匯總了這些參數(shù)的定義和描述。

視頻傳輸服務(wù)通常以一個(gè)自然編碼幀作為發(fā)送單元，考慮到分層編碼視頻的解碼原理和復(fù)雜性，基本層編碼數(shù)據(jù)需要單獨(dú)傳送，增強(qiáng)層編碼數(shù)據(jù)可根據(jù)不同情況進(jìn)行可伸縮截?cái)鄠魉?，基本層?shù)據(jù)的傳輸可使用早期的一些優(yōu)化算法[5]來實(shí)施，文章在這里只討論傳輸增強(qiáng)層編碼幀的多發(fā)送者選擇問題。讓代表一個(gè)自然編碼幀的播放時(shí)間，表示候選發(fā)送者的個(gè)數(shù)，對(duì)于接收者的某一傳輸幀要求滿足公式（1）。

（1）

視頻解碼質(zhì)量通常用率失真參數(shù)來衡量以及評(píng)價(jià)傳輸算法，如優(yōu)化的率失真?zhèn)鬏斔惴ā?duì)于SVG編碼視頻來說，解碼器得到的增強(qiáng)層編碼前綴越長(zhǎng)，其率失真越小[4]。因此，可以將極小化率失真?zhèn)鬏敳呗院?jiǎn)化為極大化編碼前綴獲取策略。

為求解問題方便，分兩步走，第一步尋找一組有效的候選發(fā)送者。先通過一些網(wǎng)絡(luò)技術(shù)，來獲得“意愿發(fā)送者”的網(wǎng)絡(luò)響應(yīng)和傳輸時(shí)間，如RTT，根據(jù)它們的響應(yīng)時(shí)間，預(yù)設(shè)定一組意愿發(fā)送者，這些發(fā)送者可能持有相同視頻增強(qiáng)層編碼數(shù)據(jù)的不同比例，它們被稱之為一組候選發(fā)送者。

對(duì)于一組候選發(fā)送者，每一個(gè)發(fā)送者貢獻(xiàn)自己持有的一部分視頻編碼數(shù)據(jù)，如圖1中持有編碼數(shù)據(jù)的發(fā)送者貢獻(xiàn)，即自己的全部數(shù)據(jù)，持有編碼數(shù)據(jù)的發(fā)送者貢獻(xiàn)部分，所以接收者能獲得的編碼數(shù)據(jù)為。

若某一接收者視頻需求為，文章討論在發(fā)送者中尋求一組傳送分配方案，來極大地滿足接收者的視頻質(zhì)量需求，這樣的一組傳送分配方案應(yīng)滿足公式（2）。

（2）

其中，中的數(shù)據(jù)應(yīng)互不重疊且順序相連，構(gòu)成一個(gè)完整的編碼前綴。求解滿足公式（2）的傳送方案屬于整數(shù)線性規(guī)劃求解問題，即NP難問題[6]。

3 發(fā)送者選擇算法（Algorithm for selection senders）

算法的主要思想是從候選發(fā)送者中選一組盡可能少的實(shí)際發(fā)送者個(gè)數(shù)，來滿足接收端的最大質(zhì)量（最長(zhǎng)編碼前綴）需求。先把所有候選發(fā)送者的從小到大排序，即形成，根據(jù)目標(biāo)需求逐個(gè)掃描，尋求最大匹配，若滿足要求算法完成，否則對(duì)余下的部分繼續(xù)本算法。詳細(xì)算法描述如下。為書寫簡(jiǎn)明，用表代替。

最小發(fā)送集選擇算法MSSA（Minimum Senders Set Algorithm）：

輸入：。

輸出：。

（1）?。?/p>

（2）從小到大排序表；

（3）如果表中每一項(xiàng)都或而，則停止算法；

（4）先從頭掃描表，若遇有，則輸出，停止算法；

（5）否則，從表尾開始掃描，若遇到有或者已到達(dá)表頭，則停止循環(huán)，并記下循環(huán)變量為，并做如下工作。

a.輸出；

b.重置和；

c.重置表（其中，若，則讓），回到（3）步繼續(xù)。

算法最后按（4）和（5）第a步的輸出順序形成一個(gè)最終多發(fā)送者的分配方案。第一個(gè)發(fā)送者貢獻(xiàn)的是增強(qiáng)層視頻編碼的首部分，其余發(fā)送者相繼貢獻(xiàn)增強(qiáng)層視頻編碼的后續(xù)部分，它們連接起來形成一個(gè)完整的編碼前綴。算法若最后終止于（4）步則說明能完全滿足接收者的最大需求，否則終止于（3）步的話，則說明盡可能極大地滿足接收者的需求。

MSSA算法的時(shí)間復(fù)雜性主要在排序上，算法有兩個(gè)優(yōu)化性能：最大分配和盡可能小的發(fā)送者個(gè)數(shù)，下面給出最大分配的分析證明，發(fā)送者數(shù)目的分析由實(shí)驗(yàn)給出。

結(jié)論：算法輸出的結(jié)果滿足，即各發(fā)送者貢獻(xiàn)的編碼段是無縫連接的。

引論：給定一組持不全相同編碼長(zhǎng)度和相應(yīng)上行帶寬的發(fā)送者，以及單個(gè)接收者條件，經(jīng)MSSA算法，可以最大分配來滿足接收者視頻質(zhì)量的需要。

證明：分兩種情況來證明，不管算法循環(huán)多少輪，只要是算法結(jié)束于步驟（4），很明顯輸出的結(jié)果能完全滿足接收者的最大需求?，F(xiàn)在來證明算法結(jié)束于步驟（3）的情況。理論上在（3）步驟結(jié)束算法，說明候選發(fā)送者們已經(jīng)用盡自己的資源，做到了盡最大努力，同時(shí)結(jié)論中的數(shù)據(jù)連續(xù)性可保證其輸出是極大的。

4 實(shí)驗(yàn)與分析（Experiment and analysis）

實(shí)驗(yàn)和文獻(xiàn)[4]的算法進(jìn)行比較，試驗(yàn)設(shè)計(jì)一個(gè)統(tǒng)計(jì)模型，根據(jù)SVC編碼的特性，編碼流由基本層和可伸縮的增強(qiáng)層組成，增強(qiáng)層按位平面編碼（一般在幾個(gè)位平面以內(nèi)）。試驗(yàn)?zāi)Ｐ椭豢紤]增強(qiáng)層截?cái)鄠鬏攩栴}?？紤]到位平面編碼技術(shù)，對(duì)于發(fā)送者持有的編碼流和接受者需求的編碼流，雖然可以說是任意長(zhǎng)度的，但實(shí)際上是限于幾個(gè)質(zhì)量等級(jí)的，所以發(fā)送者的持有量和接收者的需求量按編碼的位平面數(shù)分級(jí)分類，但發(fā)送者的有效上行帶寬具有統(tǒng)計(jì)特性，實(shí)驗(yàn)中可以隨機(jī)生成。所以對(duì)于一組候選發(fā)送者，其持有的增強(qiáng)層長(zhǎng)度從固定的幾個(gè)等級(jí)中隨機(jī)選取，其輸出帶寬則隨機(jī)生成。根據(jù)一段The firm編碼源，如圖2所示，按單幀，算法運(yùn)行1000幀次，MSSA算法有85%集中在一兩個(gè)發(fā)送者，只有當(dāng)候選發(fā)送者們的輸出帶寬均細(xì)小時(shí)，才出現(xiàn)多個(gè)發(fā)送者的情況，而文獻(xiàn)[4]算法，98%以上是多發(fā)送者結(jié)果（4個(gè)以上），如圖3所示。

融合網(wǎng)絡(luò)下，在分布式流媒體服務(wù)體系中，發(fā)送者們具有頻繁進(jìn)出和輸出帶寬不穩(wěn)定的特點(diǎn)[7]，所以發(fā)送者選擇算法主要應(yīng)考慮用盡可能小的發(fā)送者數(shù)去滿足需求者的最大質(zhì)量需求，保持系統(tǒng)地穩(wěn)定性，MSSA算法具有這方面的特點(diǎn)。

參考文獻(xiàn)（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].計(jì)算機(jī)學(xué)報(bào)，2004，27（3）：357-364.

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

ed），Cambridge，MA.2001.

[7] 萬成威，鄔江興，蘭巨龍.P2P流媒體穩(wěn)態(tài)傳輸模型分析[J].通信

學(xué)報(bào)，2012，33（2）：132-140.

作者簡(jiǎn)介：

謝建國（1964-），男，博士，教授.研究領(lǐng)域：計(jì)算機(jī)網(wǎng)絡(luò)，數(shù)

字媒體傳輸.