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

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

中圖分類號： TP393 文獻標識碼：A

1 引言（Introduction）

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

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

2 問題描述（Problem description）

SVC技術將視頻編碼成基本層和增強層，基本層具有低比特率、獨立解碼、獨立傳輸。增強層用來增強基本層的視頻質量，不能獨立解碼，在傳輸中增強層可任意截斷傳輸，其截斷的粒度可達到比特層面，解碼器接收的增強層信息越多，解碼質量就越好。因視頻增強層的碼流可被截斷傳輸并解碼，對于同一個編碼流，低解碼質量的碼流總是高解碼質量碼流的前綴。

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

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

（1）

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

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

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

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

（2）

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

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

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

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

輸入：。

輸出：。

（1）取；

（2）從小到大排序表；

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

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

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

a.輸出；

b.重置和；

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

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

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

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

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

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

4 實驗與分析（Experiment and analysis）

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

融合網(wǎng)絡下，在分布式流媒體服務體系中，發(fā)送者們具有頻繁進出和輸出帶寬不穩(wěn)定的特點[7]，所以發(fā)送者選擇算法主要應考慮用盡可能小的發(fā)送者數(shù)去滿足需求者的最大質量需求，保持系統(tǒng)地穩(wěn)定性，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流媒體穩(wěn)態(tài)傳輸模型分析[J].通信

學報，2012，33（2）：132-140.

作者簡介：

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

字媒體傳輸.