P2P網絡多視點立體視頻傳輸的數據塊調度策略

劉曉輝，金志剛，衛津津，趙西滿

天津大學 電子信息工程學院，天津 300072

1 引言

立體視頻利用人類雙目視差原理，使人眼獲得同一場景具有輕微視角差異的兩個視圖，從而在大腦中形成立體感。多視點立體視頻支持裸眼觀看，具有獨特的表現力和強大的震撼力，必將成為互聯網新的應用和業務增長點。但是多視點立體視頻具有很高的碼流速率，同時立體視頻對數據丟失特別敏感，需要高效、高質量的網絡傳輸。

P2P（Peer-to-Peer）網絡模式在流媒體傳輸上獲得了巨大成功，其非中心化和負載均衡等特點同樣適用于多視點立體視頻的傳輸。

P2P的非中心化特點要求每個對等體在獲取數據的同時也作為數據提供者，因此對等體之間的數據塊調度對視頻的傳輸和播放質量至關重要[1]。為了提高傳輸效率，研究人員針對不同的影響因素提出許多有效的P2P數據塊調度算法[2-6]。文獻[2]提出隨機獲取算法（RAND）；文獻[3]提出數據驅動的概念，并提出采用局部最少優先算法（Local Rarest First，LRF）改善性能；文獻[4]通過分析貪婪策略和最少優先策略提出一種混合調度策略（Mixed Rarest First and Greedy，Mixed-RF-G）。該策略將節點緩沖區分成兩部分，第一部分用最少優先策略調度數據塊，剩下的用貪婪策略，以此來平衡數據的稀有性和緊急性。

上述P2P數據調度算法可以改善節點吞吐量、帶寬利用率和啟動速度等方面發揮作用。但分析表明：P2P節點吞吐量的最大化并不能保證視頻的播放質量，因為一些關鍵數據塊的丟失會造成視頻的嚴重失真[7]。尤其是多視點立體視頻，其編碼形式復雜、同時包含運動和深度信息、對數據丟失敏感度高，因此關鍵數據塊的缺失對多視點立體視頻的影響更大。文獻[8-10]從率失真的角度提出重要性優先（Importance First，IF）的傳輸模型，這種方法對多視點立體視頻的P2P傳輸具有指導意義。但是，采用重要性優先模型進行數據調度往往會導致P2P網絡陷入內容瓶頸問題[11]。本文首先分析多視點立體視頻的編碼特點，然后結合節點數據的重要性、稀有性以及緊急程度提出面向多視點立體視頻的P2P數據塊調度方案。

2 多視點立體視頻和P2P視頻傳輸系統

為了提高立體視頻播放質量和傳輸效率，P2P傳輸調度算法需要緊密結合立體視頻的編碼結構。因此，本章首先介紹多視點立體視頻的編碼結構，然后對P2P視頻傳輸系統和其中的數據塊調度問題進行分析。

2.1 多視點立體視頻編碼

在單視點視頻編碼中，去除視頻序列時間冗余的有效方法是幀間預測[12]。對于多視點立體視頻而言，去除視點間冗余最直接的方式是在編碼當前視點圖像時使用其他視點中的圖像作為參考圖像進行位移估值和幀間預測，這種方法稱為視點間預測[13]。

多視點視頻編碼（MVC）在H.264編碼的基礎上增加了視點間預測，目前已經成為H.264編碼標準的擴展集之一。本文的立體視頻編碼方式就是采用MVC編碼，圖1是一個全視點圖片組（GOGOP）的MVC編碼結構。水平坐標軸為時間軸，垂直坐標軸為視點軸，T0表示第0幀視頻，V0表示第0號視點。多視點立體視頻采用分層的B幀構造可分級的預測結構，每幀字母下標的數字表示級別，0級優先級最高。V0的第0幀是I幀，V2，V4，V6，V7的第0幀采用視點間P幀預測，V1，V3，V5的第0幀采用視點間的B幀預測。其余都是基于時域和視點間的B幀預測。顯而易見，V0視點的I0最為重要，整個GOGOP中的所有幀圖像都對它有依賴關系，I0的數據丟失將影響整個GOGOP的圖像質量。其次是P0幀，P0幀不僅是本視點的參考幀，同時影響對應的B幀預測視點。多視點立體視頻中所有幀類型的重要性順序為I0>P0>B1>B2>B3>b4，在一個GOP中其數目分別為1，4，8，13，26，12。

圖1 八視點立體視頻MVC編碼結構圖

2.2 P2P視頻傳輸系統

P2P系統由流媒體服務器、Tracker服務器以及若干個節點組成（Peer）[14]。流媒體服務器將預先編碼好的視頻流分組打包，以直播的方式分發到P2P網絡中；Tracker服務器用于維護在線節點列表，并為請求節點提供具有媒體發布能力的鄰居節點列表；節點不僅是媒體內容的下載者，而且將媒體內容下載并轉發給其他請求節點。

當一個節點加入P2P網絡系統中，它首先向Tracker服務器請求鄰居節點列表。獲得鄰居節點列表后，隨機選擇節點建立連接。每個節點維護一個緩存圖（BufferMap，BM），用于說明該節點的數據塊中哪些是已經緩存并且可用的。在傳輸過程中，節點周期性地與其他的鄰居節點交換BM，從而得到更多的節點的緩存信息。當節點收到對方的數據緩存圖BM后，就會采用一定的數據塊調度策略去請求感興趣的塊。媒體內容被分成大小相同的塊，每個數據塊被指定一個編號，用以表示其播放順序。節點緩存一定量的數據塊以后，就開始進行視頻播放。

為了維持視頻播放和流媒體數據塊請求動作，每個節點維護兩個滑動窗口：播放窗口和請求窗口。節點的播放窗口和請求窗口結構如圖2所示。播放窗口中的是正在參與解碼和播放的數據塊，包括已經緩存的數據塊和少量的丟失數據塊。播放窗口中的最后一個數據塊被稱為截止期，晚于這個截止期到達的數據塊將會被認為是數據丟失，并會對視頻的播放質量產生影響。請求窗口為視頻播放緩存數據，內容包含已經緩存的數據塊、向鄰居節點請求但尚未收到的數據塊、鄰居節點擁有但尚未請求的數據塊，以及鄰居節點沒有的數據塊。

圖2 節點的播放窗口和請求窗口

當Peer節點開始接收和播放數據時，播放窗口和請求窗口同時向后滑動。正常情況下，播放窗口的滑動速率與視頻的正常的碼流速率相同。而請求窗口的滑動速率只與Peer節點的數據接收速率有關，當數據塊的接收速率高于播放速率時，播放窗口的截止期與請求窗口的距離會拉大。當網絡出現阻塞或者P2P網絡出現傳輸瓶頸時，請求窗口的滑動速率會迅速降低或者停止，此時截止期與請求窗口的距離會越來越小，直至為0。當截止期和請求窗口距離為0時，播放窗口無法正常向后滑動，視頻播放也會出現卡頓或停止。

3 數據塊調度模型及算法

3.1 數據塊調度的主要考慮因素

數據塊調度的主要目的包括兩點：（1）保證P2P網絡的高效數據傳輸；（2）提高單個Peer的視頻接收和播放質量。

在P2P網絡系統的角度上，為了提高數據的傳輸效率，就必須提高Peer之間的單位時間數據交換量。假設N個Peer節點之間進行數據交互，而沒有外部新鮮數據進入的情況下，它們會隨著因緩存數據的同步，傳輸效率會越來越低，最終陷入傳輸瓶頸。因此P2P網絡中數據塊內容的多樣性和可用性對保證P2P系統的傳輸效率至關重要。

對于Peer節點而言，要保證數據接收和視頻播放質量，必須滿足緊急數據塊的優先性。Peer的緊急數據塊是指請求窗口中靠近播放窗口截止期但尚未接收到的數據塊，隨著這類數據塊逐步接近播放窗口，其緊急程度越來越高。如果進入播放窗口，仍未接收，將會影響視頻的播放質量。

另一方面，由于本文面向的是多視點立體視頻的P2P傳輸，數據塊的丟失對立體視頻播放質量影響更為復雜，關鍵數據塊的丟失會對視頻的正常播放產生更大的影響。例如：圖1中I0幀所在的數據塊具有最高的重要性，I0幀的數據塊丟失會影響整個GOGOP中其他所有視點、所有后續幀的解碼。因此，必須考慮數據塊在編碼中的重要程度。

因此，P2P網絡多視點立體視頻傳輸數據塊調度的主要考慮因素包括：

（1）數據塊在視頻編碼結構中的重要程度。

（2）數據塊對視頻播放的緊急程度。

（3）新鮮數據和數據的局部稀缺性。

3.2 面向立體視頻數據塊調度算法

MVC采用分級的B幀預測結構，其中，B3幀和b4幀在預測結構中數目較多，但它們重要性相對較低，其數據丟失對立體視頻質量的影響相對較小。而I0P0B1B2幀的數目和比例雖然較低，但其數據丟失對立體視頻影響較大。有鑒于此，本文將兩類分開處理。

本文算法中將請求窗口內的數據塊分為Priority_Chunks和Rand_Chunks兩個集合，Priority_Chunks主要包含I0P0B1B2四種幀類型對應的數據塊（也可稱為I0P0B1B2集），這些數據塊需要優先傳輸。而Rand_Chunks主要包含B3b4兩種幀類型的數據塊（可稱為B3b4集）。

確定數據塊的請求優先級，是提高傳輸效率和播放質量的一種有效手段。本文引入重要性、緊急性和稀缺性三種影響因素，確立數據塊的請求優先級。本文對每個數據塊c定義一個立體視頻經驗效用函數 P(l,t,λ)，P(l,t,λ)值越小，數據塊的優先級越高。

為了提高傳輸效率，提高立體視頻質量，本文提出一種聯合優先級傳輸和隨機傳輸的數據塊調度方法PR-RAND。具體算法如下：

初始化傳輸以后，Peer節點i以時間T為間隔進行如下操作：

（1）對請求窗口中的 N個數據塊計算其效用函數Pi(l,t,λ),1≤i≤N 。

（2）將待請求的數據塊分為兩個集合：Priority_Chunks和Rand_Chunks。

I0P0B1B2對應的數據塊屬于Priority_Chunks；B3b4對應的數據塊屬于Rand_Chunks。

（3）對于 Priority_Chunks中的數據塊，按照 P(l,t,λ)越小，優先級越高的方式進行請求。

（4）使用鄰居節點的傳輸率估計Peer節點i的可用數據帶寬：

其中，設節點 Nij(j=1～Neighbors)是節點i的鄰居節點；oj是節點Nij的上載帶寬；mj是節點Nij的鄰居總數。

若BWi大于多視點立體視頻的平均碼流速率，使用RAND[2]算法傳輸Rand_Chunks中的數據塊，否則，對Rand_Chunks集合中的數據塊不做請求。

注 Rand_Chunks中數據塊的效用函數P(l,t,λ)并未實際使用，在算法實現中可以省去此部分計算。

Priority_Chunks按照 P(l,t,λ)越小，優先級越高的方式進行傳輸；Rand_Chunks中的數據塊優先級相對較低，對立體視頻質量影響較小，采用RAND[2]算法進行傳輸。RAND[2]算法是一種簡單的數據塊請求方法，它是指peer節點根據維護的數據塊請求列表和鄰居節點的可用數據塊列表，隨機地挑選數據塊向鄰居節點發送請求獲取信息，而不考慮任何優先級信息。其優點在于算法簡單，并能夠增加節點數據塊的多樣性。

使用PR-RAND方法，在保證立體視頻播放質量的基礎上，可以充分利用空余網絡帶寬傳輸隨機數據塊，增加Peer節點之間數據塊的多樣性，能夠一定程度地避免P2P內容瓶頸問題。

4 實驗結果和性能評價

4.1 性能評價指標

流媒體塊調度算法和Peer鄰居節點選擇算法是影響視頻播放質量和網絡傳輸效率的兩大關鍵因素，本文在固定Peer鄰居節點的情況下對本文所提出的PR-RAND算法做出評估，主要的性能評價指標包括：

立體視頻回放質量：立體視頻的回放質量直接關系到用戶的體驗效果，是判定數據塊調度效果的最直接的指標。本文采用峰值信噪比（Peek Signal-to-Noise Ratio，PSNR）作為立體視頻傳輸失真的質量評價標準。

數據到達率：立體視頻回放時，節點實際獲得的有效立體視頻數據占應獲得數據的比例。由于數據塊重要性的區別，數據到達率并不完全與視頻回放質量成正比。

啟動延遲：數據包從源節點發出直到在接收節點的緩沖區被回放的時間，具體指用戶決定觀看到實際播放的等待時間，是衡量用戶體驗效果良好與否的關鍵。

網絡吞吐量：網絡吞吐量是指Peer節點平均每秒接收到的數據量，網絡吞吐量能夠直觀地反映P2P系統的網絡傳輸效率，因此也是衡量P2P數據塊調度策略有效性的重要指標。

4.2 實驗結果

實驗環境為：2.13 GHz 4核CPU（Intel Xeon E5606），內存4 GB DDR3，操作系統為Suse linux 11。實驗采用Transit-Stub拓撲中的GT-ITM模型建立網絡層的拓撲結構，生成2 000個路由節點；采用General Peer-to-Peer Simulator[15]（General p2p simulator:www.cs.binghamton.Edu/～wyang/gps/）作為仿真工具，模擬對等體個數分別為1 000、3 000、5 000。具體的實驗參數如表1所示。

表1 實驗參數設置

除上述參數以外，算法中的優先級效用函數P(l,t,λ)包含3個權重因子ω1,ω2,ω3，它們是一種比例關系。為了比較簡單地獲取系統性能較好的權重因子，假設三種因子彼此獨立。首先通過分析節點吞吐量和啟動延遲的變化，確定ω2,ω3之間比例關系。然后以ω2,ω3為基準，從0開始增加ω1的比重，通過PSNR的變化判斷不同權重的作用效果。具體方法如下：設ω3=1，在不考慮ω1的情況下（即ω1=0），調節ω2的數值。由圖3可知，ω2在0.5附近時，節點的吞吐量較高，同時啟動延遲較低。進一步引入重要性因子ω1，設ω2=0.5,ω3=1,，通過增加ω1的權重進行比較實驗，立體視頻的平均PSNR隨著權重因子ω1增大先增加后減少，在取值為2.5附近出現峰值。因此，本文在以下實驗中，將權重因子等比變換為整數，分別設置為ω1=5,ω2=1,ω3=2。

圖3 ω3=1時，不同ω2對節點吞吐量和啟動延遲的影響

實驗內容包括：平均PSNR；啟動延遲；平均數據到達率；節點平均吞吐量。由于節點數量龐大，實驗數據的獲得方式是通過隨機抽樣的方式，將所有Peer節點分為5組，每組抽取10個節點，由5組總計50個節點數據獲取平均值作為整體的實驗結果。為了分析和評價所提出的PR-RAND方法的有效性，本文使用三種典型的調度算法PR-RAND方法與 LRF[3]、Mixed-RF-G[4]、IF-IBP[6]進行比較。

（1）平均PSNR：如圖4所示，1 000個Peer節點的仿真實驗中，不同算法立體視頻播放的平均PSNR。由實驗結果可以看出，采用本文提出的PR-RAND方法，立體視頻的平均PSNR高于其他3種方法。LRF和Mixed-RF-G方法不考慮數據塊的重要性，因此視頻回放時不能保證關鍵數據的完整性，造成立體視頻平均PSNR偏低。IF-IBP以重要性為優先的原則傳輸立體視頻數據塊，但是在200～250 s內出現了明顯的內容傳輸瓶頸，由于大量缺失數據，造成視頻質量的下降。

圖4 不同算法產生的視頻PSNR

（2）啟動延遲：本文設計的立體視頻播放窗口大小為20，因此，啟動延遲是指接收到前20個數據塊的時間。從表2中可以看出，由于本文算法考慮了數據塊的緊急性，啟動延遲低于LRF和IF-IBP，比Mixed-RF-G算法略高。同時，受節點傳播時延影響，四者的啟動延時隨著節點規模增大略有增加。

表2 啟動延遲 s

（3）節點平均吞吐量和數據到達率：節點的平均吞吐量和平均數據到達率如圖5所示。從圖5（a）可以看出，LRF方法具有最高的節點平均吞吐量，其次是PR-RAND和Mixed-RF-G，IF-IBP的吞吐量最低。平均數據到達率如圖5（b）所示，由于考慮了數據塊的緊急性，并采用聯合優先級和隨機傳輸方法，本文提出的PR-RAND方法的數據到達率高于其他三種方法。

圖5 算法的平均節點吞吐量和數據到達率對比

5 結束語

面向多視點立體視頻P2P網絡傳輸，本文綜合考慮了數據塊在視頻編碼中的重要性、播放的緊急程度以及網絡內容的稀有性，提出了一種聯合優先級和隨機傳輸的數據塊調度方案。通過仿真實驗，證明了本文提出的PR-RAND方法能夠提供更優越的立體視頻質量和較小的啟動延遲，同時克服了IF方法的缺點，能夠避免內容傳輸瓶頸問題，保證較高的網絡吞吐率。

本文僅僅研究立體視頻P2P數據塊請求的調度問題，與P2P Tracker服務器節點調度相結合，建立一套完整高效的立體視頻P2P傳輸系統是下一步的工作方向。

[1]Zhang M，Xiong Y Q，Zhang Q，et al.On the optimal scheduling for media streaming in data-driven overlay networks[C]//Proc of IEEE GLOBECOM，2006.

[2]Pai V，Kumar K.Chainsaw：eliminating trees from overlay multicast[C]//Proc of IEEE INFOCOM，2005.

[3]Zhang X，Liu J，Li B，et al.CoolStreaming/DONet：a data-driven overlay network for efficient media streaming[C]//Proc of IEEE INFOCOM，2005：2102-2111.

[4]Zhou Y，Chiu D M，Lui J C.A simple model for analyzing P2P streaming protocols[C]//Proc of IEEE ICNP，2007.

[5]任浩，王勁林，尤佳莉.一種分階段的P2P流媒體數據調度算法[J].計算機工程與應用，2011，47（23）：1-4.

[6]徐家燕，陸建德，武廣柱.rlncBT：隨機線性網絡編碼的P2P內容分發系統[J].計算機工程與應用，2009，45（12）：110-113.

[7]Chakareski J，Apostolopoulos J，Wee S，et al.Rate-distortion hint tracks for adaptive video streaming[J].IEEE Transactions on Circuits and Systems for Video Technology，2005，15（10）：1257-1269.

[8]Chou P A，Miao Z.Rate-distortion optimized streaming of packetized media[J].IEEE Transactions on Multimedia，2006，8（2）：390-404.

[9]Miao Z，Ortega A.Expected run-time distortion based scheduling for delivery of scalable media[C]//Proc of Int Packet Video Workshop，2002：829-832.

[10]Chakareski J，Apostolopoulos J.Rate-distortion optimized distributed schediling of multiple video streams over shared communication resources[J].IEEE Transactions on Multimedia，2006，8（2）：207-218.

[11]Chang C Y，Chou C F，Chen M H.Striking the balance between content diversity and content importance in swarm-based P2P streaming system[C]//Proc of IEEE HPCC，2002：653-660.

[12]歐陽合.H.264和MPEG-4視頻壓縮[M].北京：國防科技大學出版社，2004.

[13]MPEG video subgroup.Introduction to multi-view video coding[C]//83rd MPEG Meeting，2008.

[14]謝勇均.P2P視頻直播傳輸系統的研究與實現[D].北京：中國科學院計算技術研究所，2006.

[15]Yang W，Abu-Ghazaleh N.GPS：a general peer-to-peer simulator and its use for modeling BitTorrent[J].Mascots，2005：425-434.