網(wǎng)絡編碼P2P流媒體中的動態(tài)段粒度研究*

李　姍，袁　遠，彭宇行1.長沙師范學院 電子與信息工程系，長沙 410100.國防科學技術大學 計算機學院，長沙 410073

網(wǎng)絡編碼P2P流媒體中的動態(tài)段粒度研究*

李姍1+，袁遠2，彭宇行2
1.長沙師范學院 電子與信息工程系，長沙 410100
2.國防科學技術大學 計算機學院，長沙 410073

網(wǎng)絡編碼技術已證明能夠提高P2P流媒體系統(tǒng)的整體性能，但是現(xiàn)有系統(tǒng)采用固定段粒度編碼方式存在諸多局限性，為了克服固定段粒度的缺點，且適應實際網(wǎng)絡的隨機特性，提出了動態(tài)段粒度的新概念，即源節(jié)點在編碼時能夠動態(tài)調(diào)節(jié)編碼塊的段粒度。從編碼方式、取值范圍及輸出能力三方面回答了升階和降階編碼實現(xiàn)動態(tài)段粒度所面臨的問題。最后設計了一種動態(tài)段粒度調(diào)節(jié)策略，該策略中源節(jié)點能夠根據(jù)播放緩沖量和源節(jié)點服務能力來動態(tài)調(diào)節(jié)編碼塊的段粒度。實驗表明該策略能夠有效提高網(wǎng)絡抖動和節(jié)點攪動時的服務質(zhì)量。

網(wǎng)絡編碼；P2P流媒體；動態(tài)段粒度

1　引言

2005年后，網(wǎng)絡編碼技術[1]相繼應用于P2P數(shù)據(jù)分發(fā)系統(tǒng)[2]和P2P流媒體系統(tǒng)[3]中，并逐步成為研究的熱點[4-5]。較傳統(tǒng)的P2P流媒體[6]而言，網(wǎng)絡編碼技術具有傳輸協(xié)議更簡單，動態(tài)網(wǎng)絡適應性更強，系統(tǒng)擴展性更好等優(yōu)勢[7]。在基于網(wǎng)絡編碼的P2P流媒體系統(tǒng)中，媒體文件被劃分成等大小且具有時序的原始數(shù)據(jù)塊（original block），多個原始數(shù)據(jù)塊組成數(shù)據(jù)段（segment），隨機線性網(wǎng)絡編碼（randomized linear network coding）就作用在每個數(shù)據(jù)段內(nèi)原始數(shù)據(jù)塊上?！岸瘟６取保╯egment granularity）指每個數(shù)據(jù)段所包含的原始數(shù)據(jù)塊數(shù)目。對于每個數(shù)據(jù)段，多個源節(jié)點同時向一個請求節(jié)點分發(fā)該段的編碼塊（coded block）；請求節(jié)點在未解碼編碼塊時，通過再編碼為更多節(jié)點提供服務。當請求節(jié)點收到數(shù)目等于段粒度的線性無關編碼塊后，則通過高斯約旦消去法解碼，得到原始數(shù)據(jù)塊用于播放[8]。

段粒度作為編碼范圍，是P2P流媒體系統(tǒng)中的關鍵參數(shù)。研究表明[9]，段粒度取值會影響系統(tǒng)各方面的性能：段粒度設定較大時，每次編碼的數(shù)據(jù)量增加，計算開銷明顯增大，造成較大編解碼延遲；另外，段粒度增大也會導致編碼塊上附加系數(shù)開銷增大，降低傳輸效率；再次，原始數(shù)據(jù)只有在一個數(shù)據(jù)段全部解碼后才能得到，段粒度過大將帶來較大的播放啟動延遲，且降低抗網(wǎng)絡抖動能力，影響服務質(zhì)量。段粒度設定較小時，由于數(shù)據(jù)段切換次數(shù)增多，請求節(jié)點向源節(jié)點發(fā)送“剎車消息”也越多，將導致更多的段間線性相關冗余，影響傳輸效率；此外，已證明段粒度太小還會使得數(shù)據(jù)塊在對等網(wǎng)絡的節(jié)點中分布不均勻，導致魯棒性下降[10]。

目前，基于網(wǎng)絡編碼的P2P流媒體系統(tǒng)的相關研究中都是將媒體文件的段粒度設定為固定值[9,11-12]，即段粒度取值在整個媒體數(shù)據(jù)分發(fā)過程中保持不變，因此稱為固定段粒度（fixed segment granularity）。大部分固定段粒度取值研究通過模擬實驗和海量數(shù)據(jù)實測來獲取一個較優(yōu)的固定值，不但開銷大，而且不能夠適應于動態(tài)變化網(wǎng)絡環(huán)境，影響了服務質(zhì)量[12]；少部分段粒度通過數(shù)學模型分析計算得到最優(yōu)值，由于模型本身不能完全刻畫實際網(wǎng)絡的隨機特性，從而對應用的指導意義有限[13]。

針對固定段粒度存在的上述局限性，本文提出了動態(tài)段粒度的概念及其實際應用的策略，即在基于網(wǎng)絡編碼的P2P流媒體系統(tǒng)中，源節(jié)點可根據(jù)請求節(jié)點需求動態(tài)調(diào)節(jié)編碼塊的段粒度，能夠有效克服由于P2P系統(tǒng)的自發(fā)性和網(wǎng)絡隨機特性導致固定段粒度過大或者過小的問題，進一步提高系統(tǒng)的服務質(zhì)量。本文的主要貢獻如下：

（1）提出了動態(tài)段粒度概念與基本原理。與固定段粒度的傳統(tǒng)思路不同，為進一步提高P2P流媒體系統(tǒng)的服務質(zhì)量提供了新的突破方向。

（2）解決了實現(xiàn)動態(tài)段粒度面臨的3個難點，即編碼方式問題、取值范圍問題和輸出能力問題，證明了源節(jié)點可以在不解碼的情況下通過升階編碼和降階編碼方式動態(tài)調(diào)整編碼塊的段粒度，為動態(tài)段粒度策略的設計提供了理論支持。

（3）設計了一種高效動態(tài)段粒度調(diào)節(jié)策略。請求節(jié)點根據(jù)緩沖狀況和源節(jié)點的服務能力周期性地計算動態(tài)段粒度，源節(jié)點則根據(jù)請求節(jié)點的反饋來調(diào)節(jié)編碼塊的段粒度，提高了系統(tǒng)在網(wǎng)絡抖動和節(jié)點攪動時的服務質(zhì)量。

2　基本概念和原理

動態(tài)段粒度指的是在基于隨機線性網(wǎng)絡編碼的P2P流媒體系統(tǒng)中，每個媒體文件在分發(fā)過程中段粒度不再是一個固定值，而允許源節(jié)點在生成編碼塊時進行動態(tài)調(diào)節(jié)，以適應P2P系統(tǒng)自發(fā)性及實際網(wǎng)絡隨機特性，有效提高系統(tǒng)的服務質(zhì)量。

動態(tài)段粒度的優(yōu)勢在于：在請求節(jié)點協(xié)同配合下，當網(wǎng)絡狀況良好，且請求節(jié)點播放緩沖中的有效原始數(shù)據(jù)量富余時，源節(jié)點動態(tài)增加編碼塊的段粒度，這樣可減小段間切換開銷，提高帶寬資源利用率；當請求節(jié)點播放緩沖的有效原始數(shù)據(jù)量較小，且有節(jié)點退出或者網(wǎng)絡狀況不佳時，源節(jié)點動態(tài)減小編碼塊的段粒度，幫助請求節(jié)點快速完成解碼，保證播放質(zhì)量。

下面用一個例子，從請求節(jié)點的角度說明動態(tài)段粒度較固定段粒度的優(yōu)勢。

如圖1所示，黑色曲線表示源節(jié)點收到編碼塊的數(shù)據(jù)量；灰色曲線表示解碼得到的原始數(shù)據(jù)；藍色曲線表示已播放的數(shù)據(jù)量。這3條曲線均為累積曲線，即所代表的數(shù)據(jù)量都隨著時間不斷累積增加。其中編碼塊曲線由于受到實際隨機因素的影響，曲線不光滑，也沒有固定的斜率，數(shù)據(jù)量增長時快時慢；原始數(shù)據(jù)曲線按照隨機線性網(wǎng)絡編碼的方式，只有在請求節(jié)點收到等于段粒度數(shù)目的線性無關編碼塊時才能解碼，因此是階梯狀的；播放曲線在理想的情況下應該是一條以媒體播放碼率R為固定斜率的直線。如圖1（a）所示，假設系統(tǒng)采用固定段粒度方式，段粒度為m，則請求節(jié)點只有在收到m個線性無關編碼塊時才能完成該段數(shù)據(jù)的解碼，因此固定段粒度下的有效原始數(shù)據(jù)曲線的階梯高度都為固定值m。這樣當編碼塊曲線增長變慢時，則有可能導致原始數(shù)據(jù)播放完時，接收到的下一段編碼塊沒有達到m（紅叉的位置），不能解碼成原始數(shù)據(jù)，從而影響播放的連續(xù)性。如圖1（b）所示，系統(tǒng)采用動態(tài)段粒度，請求節(jié)點在編碼塊曲線增長變緩時也能夠及時完成解碼，即原始數(shù)據(jù)曲線的階梯高度是動態(tài)變化的，使得緩沖區(qū)中有效原始數(shù)據(jù)不會被清空，保證播放的流暢性。

Fig.1　Request node buffer data diagram圖1　請求節(jié)點緩沖數(shù)據(jù)量示意圖

本文稱增加段粒度的編碼方式為升階編碼，降低段粒度的編碼方式為降階編碼。升階編碼和降階編碼是實現(xiàn)動態(tài)段粒度的兩種基本編碼方式。雖然動態(tài)段粒度的基本原理容易理解，但是如何升階和降階編碼，能否應用到實際系統(tǒng)中，還需要先解答三方面問題：

（1）編碼方式問題。在基于網(wǎng)絡編碼的P2P數(shù)據(jù)分發(fā)系統(tǒng)中，源節(jié)點通常在收到編碼塊但不能解碼的情況下要求通過“再編碼”為請求節(jié)點提供服務[14]。因此首先需要討論如何在再編碼過程中完成升階或者降階編碼，這是實現(xiàn)動態(tài)段粒度的基本手段。

（2）取值范圍問題。再編碼過程中，源節(jié)點將受限于自身已獲取的編碼塊段粒度情況，并不能升階或者降階編碼出任意動態(tài)段粒度的編碼塊，如動態(tài)段粒度為1的編碼塊只有源節(jié)點能夠解碼出該段數(shù)據(jù)才能提供。因此還需要確定源節(jié)點能夠提供的動態(tài)段粒度的取值范圍。

（3）輸出能力問題。請求節(jié)點在新收到的編碼塊與已緩沖的編碼塊線性相關時，考慮到對解碼出整段原始數(shù)據(jù)沒有幫助，將丟棄這些新編碼塊。因此最后還需要討論在某一特定動態(tài)段粒度下，源節(jié)點能夠提供的線性無關編碼塊的數(shù)目，即動態(tài)段粒度下的輸出能力。

3　降階與升階編碼

P2P系統(tǒng)中的內(nèi)容服務器具有所有的原始數(shù)據(jù)塊，因此可以直接進行降階和升階編碼。本節(jié)主要討論源節(jié)點在不解碼編碼塊的情況下如何完成降階編碼和升階編碼，并分別從降階編碼和升階編碼兩個方面來回答上述3個問題，對動態(tài)段粒度可行性進行分析。

3.1降階編碼

源節(jié)點上降階編碼方式是在不解碼的情況下，將編碼塊中時序靠后的部分原始數(shù)據(jù)信息剔除，即通過再編碼處理，將編碼塊中時序靠后的隨機系數(shù)通過線性運算調(diào)整為0，得到降階編碼塊。

例1設基于網(wǎng)絡編碼的P2P流媒體系統(tǒng)的有限域為GF(28)，初始段粒度為5，某源節(jié)點已收到3個段粒度為5的編碼塊，編碼系數(shù)分別為E1=[234,10,123, 146,85|C1]，E2=[13,254,34,76,123|C2]，E3=[222,134, 34,90,165|C3]，其中C1、C2、C3表示每個編碼塊中編碼數(shù)據(jù)。每個假設要求降階到段粒度為3的編碼塊，

則源節(jié)點可以采用高斯消去法，降階編碼過程如下：

上述矩陣的第三行由于后兩個系數(shù)已變換為0，即為產(chǎn)生的段粒度為3的新編碼塊，將被發(fā)往請求節(jié)點。

在此基本編碼方式下，得到取值范圍定理。

定理1（取值范圍定理）假設源節(jié)點已收到段粒度為m的線性無關編碼塊數(shù)量為k(k≤m)，則源節(jié)點能夠提供降階編碼塊的段粒度d滿足d∈{m,m-1,…,m-k+1}。

證明 采用第一數(shù)學歸納法進行證明。

（1）當k=1時，接收到的任意編碼塊都可以看作是包含該段m個原始塊信息的編碼塊，因此d∈{m}。

（2）當k=2時，假設兩個編碼塊系數(shù)矩陣如式（1）所示，如果e1m和e2m中至少有一個為0，則d∈{m, m-1}結(jié)論成立；如果e1m和e2m都不為0，則總可以通過線性行變換將其中第一個編碼塊的參數(shù)e1m變成0，即段粒度為m-1，如下所示，因此d∈{m,m-1}，結(jié)論也成立：

定理1證明了這種降階編碼方式的可行性，同時也可以看出，降階編碼不能任意降低段粒度，而是收到的編碼塊越多，則能夠得到的段粒度越小。假設源節(jié)點收到k個段粒度為m的編碼塊，則最多能夠提供段粒度為m-k+1的降階編碼塊；特別的，當收到k=m時，則源節(jié)點已經(jīng)可以解碼出段粒度為m的所有編碼塊，因此能夠提供任意段粒度不大于m的降階編碼塊。

源節(jié)點上采用降階編碼方式，等價于為請求節(jié)點分攤了解碼計算開銷，因此請求節(jié)點能夠在收到小于m個編碼塊時，提前解碼出部分原始數(shù)據(jù)，保證播放緩沖不被清空，如例2所示。

例2設源節(jié)點收到編碼塊段粒度m=5，采用段粒度為3的降階編碼為請求節(jié)點提供服務。如果請求節(jié)點收到3個降階編碼塊，系數(shù)向量分別為E1=[5, 10,12,0,0]，E2=[43,13,0,0,0]，E3=[73,54,2,0,0]，組成的系數(shù)矩陣形如：

則通過高斯約旦消去法，此時已經(jīng)可以解碼得到時序靠前的3個原始塊。

定理2（輸出能力定理）假設源節(jié)點已收到段粒度為m的線性無關編碼塊數(shù)量為k(k≤m)，且源節(jié)點目前提供的降階編碼塊的段粒度為d，則系數(shù)矩陣所組成的線性空間的秩為

證明 采用第一數(shù)學歸納法進行證明。

（1）當k=1，d=m時，由于只有一個編碼塊，此時線性空間的秩為結(jié)論成立。

（2）當k=2，d∈{m,m-1}時，有：

從定理2中可以看出，針對動態(tài)段粒度為d，源節(jié)點在不接收新的編碼塊的情況下，最多能夠編碼出個線性無關的編碼塊。

3.2升階編碼

源節(jié)點上的升階編碼的基本編碼方式是在不解碼的情況下，將時序連續(xù)數(shù)據(jù)段的編碼塊通過線性組合的方式編碼在一起，提高段粒度，得到升階編碼塊。在此基本思想下，結(jié)合定理1，得到了以下推論。

推論1（取值范圍推論）假設段i的段粒度為m1，段i+1的段粒度為m2，且源節(jié)點已收到段i的線性無關編碼塊數(shù)量為k1(k1≤m1)，收到段i+1的線性無關編碼數(shù)量為k2(k2≤m2)，則源節(jié)點能夠提供變階編碼塊的段粒度d滿足

證明 由于源節(jié)點同樣可以利用高斯約旦消去法將時序靠前的編碼塊的系數(shù)變?yōu)?，從而可以將段i編碼塊靠前的系數(shù)變?yōu)?，而將段i+1編碼塊靠后的系數(shù)變?yōu)?，然后再求這兩個變階編碼塊線性組合，從而將這兩個編碼塊中所包含的原始數(shù)據(jù)的時序連接起來。根據(jù)定理1，源節(jié)點能夠提供段i的降階編碼塊的段粒度d1滿足1}，能夠提供段i+1的降階編碼塊的段粒度d2滿足，則源節(jié)點能夠提供變階編碼塊的段粒度d滿足

考慮到為升階編碼，因此一般情況下對段i的編碼塊不作降階處理，而將段i+1的編碼進行降階，因此從推論1可以得到，源節(jié)點能夠提供的升階編碼塊的段粒度d滿足

推論2（輸出能力推論）假設段i的段粒度為m1，段i+1的段粒度為m2，且源節(jié)點已收到段i的線性無關編碼塊數(shù)量為k1(k1≤m1)，收到段i+1的線性無關編碼數(shù)量為k2(k2≤m2)，則源節(jié)點能夠提供段粒度為d的線性無關升階編碼塊的數(shù)目為

證明 升階編碼塊的段粒度為d，則段i+1的降階編碼塊的段粒度為d-m1，根據(jù)定理2，則一定有段i+1的降階編碼系數(shù)空間秩為，即可以降階編碼出個線性無關的段粒度為d-m1的編碼塊，這其中每個編碼塊都與段i的任意一個編碼塊進行線性組合，則能夠得到段粒度為d的升階編碼塊，因此命題得證。

推論2說明兩個段的編碼塊融合成一個段，將有更多的線性無關編碼塊產(chǎn)生。

4　動態(tài)段粒度調(diào)節(jié)策略

在解決了3個動態(tài)段粒度可行性相關問題后，將結(jié)合現(xiàn)有的基于網(wǎng)絡編碼的P2P流媒體系統(tǒng)的數(shù)據(jù)分發(fā)策略，設計配套的動態(tài)段粒度調(diào)節(jié)策略。

4.1系統(tǒng)模型

系統(tǒng)模型如圖2所示，請求節(jié)點接收上游n個源節(jié)點的編碼塊服務，同時又為下游l個請求節(jié)點提供再編碼塊服務。請求節(jié)點將上游n個源節(jié)點傳輸?shù)木幋a塊存儲到接收緩沖區(qū)中，編碼塊解碼后被移交到播放緩沖區(qū)中等待播放，另外也可以再編碼成編碼塊繼續(xù)為下游l個請求節(jié)點服務。動態(tài)段粒度策略在合適的時機被觸發(fā)，可根據(jù)當前的源節(jié)點服務能力和緩沖區(qū)數(shù)據(jù)量計算出每個源節(jié)點的動態(tài)段粒度取值，并通知上游源節(jié)點進行升階或者降階編碼，保證請求節(jié)點的播放質(zhì)量。

為了降低策略的復雜度，保證策略的收斂性，假設P2P流媒體系統(tǒng)中針對特定媒體文件A的最大動態(tài)段粒度為mmax，即升階編碼與降階編碼的范圍都限定在mmax內(nèi)，不存在跨mmax的情況。mmax可以在系統(tǒng)初始化時設定任意值。任何源節(jié)點通過降階編碼或者升階編碼得到編碼塊中包含的原始塊信息嚴格按照時序排列。例如，編碼塊b1的段粒度為m1，編碼塊b2的段粒度為m2，則一定有m1≤mmax且m2≤mmax，b1包含mmax個原始塊中的第1個到第m1個原始塊的信息，不包含最后mmax-m1個原始塊信息；如果有m1

在動態(tài)段粒度調(diào)節(jié)策略中，請求節(jié)點需要根據(jù)自身數(shù)據(jù)緩沖情況和源節(jié)點的服務能力計算出最佳的動態(tài)段粒度。

（1）數(shù)據(jù)緩沖情況

接收緩沖區(qū)中編碼塊的分布情況用p維向量B來表示，稱作編碼塊分布向量。假設有B={b1,b2,…, bp}，其中p表示將最大段粒度mmax劃分成 p個階段，每個階段 j(1≤j≤p)表示動態(tài)段粒度取值為((j-1) mmax/p,jmmax/p]，第j個分量bj表示接收緩沖中動態(tài)段粒度取值在((j-1)mmax/p,kmmax/p]范圍內(nèi)的編碼塊數(shù)量。

根據(jù)上面的假設，不難得到編碼塊分布向量B具有以下性質(zhì)：

Fig.2　System model圖2　系統(tǒng)模型示意圖

②時序性。p個階段的編碼塊，只有第j個階段的編碼塊完成解碼，其后繼第 j+1個階段的編碼塊才能完成解碼，或者第j個階段與第 j+1個階段同時解碼。

（2）源節(jié)點服務能力

源節(jié)點服務能力通常可用請求節(jié)點接收到該源節(jié)點編碼塊的速率表示。請求節(jié)點利用指數(shù)加權平均法（exponential weighted moving average，EWMA）來周期性地計算每個源節(jié)點編碼塊的到達速率[15]。假設周期長度設定為T個時間單位，令-λi[t]表示源節(jié)點i在周期t內(nèi)的編碼塊到達EWMA速率，作為對周期t+1的源節(jié)點服務能力的一種估計。在周期t結(jié)束時，可以計算為：

其中，α表示加權因子；λi[t]表示請求節(jié)點在周期t內(nèi)檢測到源節(jié)點i的平均編碼塊到達速率。α較大時，歷史數(shù)據(jù)在EWMA平均值中所占的比重將迅速減小。EWMA平均法的優(yōu)點在于，統(tǒng)計出來的編碼塊到達速率能夠?qū)⒃垂?jié)點服務能力和網(wǎng)絡環(huán)境的隨機抖動弱化，確保統(tǒng)計值與實際情況接近。

4.2調(diào)節(jié)算法

請求節(jié)點在每個周期結(jié)束時首先檢測源節(jié)點服務能力和數(shù)據(jù)緩沖情況，然后根據(jù)當前播放緩沖區(qū)的數(shù)據(jù)量來確定動態(tài)段粒度，即當數(shù)據(jù)量低于下限值β時，立即采用盡可能小的動態(tài)段粒度，保證能夠盡快解碼出原始數(shù)據(jù)；而當數(shù)據(jù)量高于上限值δ時，立即采用盡可能大的動態(tài)段粒度，保證減小段間切換的開銷；而當數(shù)據(jù)量在上下限之間時，則根據(jù)統(tǒng)計得到編碼塊到達速率，估計下一周期播放緩沖不會被清空到下限值以下所需要的動態(tài)段粒度取值。假設當前周期為t，令]表示周期t結(jié)束時所有源節(jié)點的聚合EWMA編碼塊到達速率，有令Bp[t]表示周期t結(jié)束時請求節(jié)點上播放緩沖區(qū)中還未播放的原始塊數(shù)目；令B[t]和bj[t]分別表示周期t結(jié)束時接收緩沖編碼塊分布向量和第j個階段對應的分量；假設R表示媒體文件的播放速率，用原始塊/秒（b/s）表示；M[t]和mi[t]分別表示周期t中各個源節(jié)點為請求節(jié)點提供的段粒度取值。動態(tài)段粒度調(diào)節(jié)策略的算法偽代碼如下所示。

請求節(jié)點在計算得到m[t+1]后，如果與當前的值不同，則通知各個源節(jié)點，源節(jié)點拿到新的動態(tài)段粒度后，將會調(diào)整編碼方式，通過升階或者降階編碼提供具有新的段粒度的編碼塊給請求節(jié)點。

5　性能評價

本文通過與固定段粒度機制進行比較，驗證動態(tài)段粒度機制的有效性。仿真實驗通過Matlab來實現(xiàn)，由于本文研究對象為應用層上的隨機線性網(wǎng)絡編碼，仿真過程將忽略下層細節(jié)。

將基于網(wǎng)絡編碼的P2P流媒體系統(tǒng)的典型參數(shù)帶入到仿真實驗中，具體包括：有限域采用GF（28），文件大小Sf設定為400 MB，原始數(shù)據(jù)塊的小大So設定為1 KB，則原始塊數(shù)目為409 600。假設該文件的播放碼率R為480 Kb/s，則播放碼率R也可以表示為每秒60個原始塊。該媒體文件最大動態(tài)段粒度mmax為160，接收緩沖區(qū)中編碼塊的分布情況用8維向量B來表示，即p為8；播放緩沖區(qū)上下限β和δ分別設置為20和350。每個請求節(jié)點共有4個源節(jié)點為其提供服務，平均服務能力為每秒15個編碼塊，服從指數(shù)分布。

如圖3所示，綠色曲線表示請求節(jié)點收到的編碼塊的累積數(shù)量，藍色折線表示請求節(jié)點解碼出的原始數(shù)據(jù)塊的累積數(shù)量，紅色折線表示請求節(jié)點播放了原始數(shù)據(jù)塊的累積數(shù)量。從圖3（a）中可以看到采用固定段粒度在3.2 s、6.5 s和8.3 s左右時，紅色折線沒有連續(xù)，即播放緩沖被清空，而沒有新的原始數(shù)據(jù)到達，因此出現(xiàn)了播放停滯現(xiàn)象，影響了服務質(zhì)量；從圖3（b）中可以看到采用動態(tài)段粒度，播放連續(xù)，藍色折線始終與紅色折線沒有交點，即緩沖始終沒有被清空，播放質(zhì)量得到了保證。

如圖4所示，在2 s后1號源節(jié)點退出，而在4 s后請求節(jié)點找到新的源節(jié)點，服務能力也是每秒15個編碼塊；在5 s開始模擬1號源節(jié)點的上行服務能力提高到每秒60個編碼塊，而在7 s時下降到每秒15個編碼塊。發(fā)現(xiàn)動態(tài)段粒度策略能夠很好地適應源節(jié)點服務能力的抖動，隨著服務能力的降低而減小段粒度，而隨著服務能力的提高而增加段粒度，保證服務質(zhì)量。

Fig.3　Request node buffer data when source node service ability stability圖3　源節(jié)點服務能力穩(wěn)定時請求節(jié)點緩沖數(shù)據(jù)量

Fig.4　Request node buffer data when source node service ability shaking圖4　源節(jié)點服務能力抖動時請求節(jié)點緩沖數(shù)據(jù)量

6　結(jié)束語

針對固定段粒度存在的局限性，本文首先提出了動態(tài)段粒度的概念，然后針對升階和降階編碼實現(xiàn)動態(tài)段粒度時存在的問題，從編碼方式、取值范圍和輸出能力三方面給出了答案，最后在現(xiàn)有P2P流媒體系統(tǒng)的分發(fā)機制上，設計了一種動態(tài)段粒度調(diào)節(jié)策略。實驗表明該策略能夠進一步提高請求節(jié)點在網(wǎng)絡抖動和節(jié)點攪動下的播放質(zhì)量。動態(tài)段粒度思想為基于網(wǎng)絡編碼的P2P流媒體系統(tǒng)提供了新思路，能夠進一步提高系統(tǒng)的服務質(zhì)量。下一步將從宏觀上繼續(xù)開展動態(tài)段粒度相關研究，分析動態(tài)段粒度調(diào)節(jié)策略下的段粒度在全系統(tǒng)中的分布及變化情況，思考動態(tài)段粒度對整個數(shù)據(jù)分發(fā)過程的影響，找出其中內(nèi)在規(guī)律，為動態(tài)段粒度概念應用到實際系統(tǒng)中提供更堅實的技術支持。

References:

[1]Ahlswede R,Cai Ning,Li S R,et al.Network information flow[J].IEEE Transactions on Information Theory,2000, 46(4):1204-1216.

[2]Gkantsidis C,Rodriguez P R.Network coding for large scale content distribution[C]//Proceedings of the 24th IEEE International Conference on Computer Communications,Miami, USA,Mar 13-17,2005.Piscataway,USA:IEEE,2005:2235-2245.

[3]Wang M,Li Baochun.LAVA:a reality check of network coding in peer-to-peer live streaming[C]//Proceedings of the 26th IEEE International Conference on Computer Communications,Anchorage,USA,May 6-12,2007.Piscataway, USA:IEEE,2007:1082-1090.

[4]Zhang Xinyu,Li Baochun.On the market power of network coding in P2P content distribution systems[J].IEEE Transactions on Parallel and Distributed Systems,2011,22 (12):2063-2070.

[5]Halloush M,Radha H.Network coding with multigeneration mixing:a generalized framework for practical network coding [J].IEEE Transactions on Wireless Communications,2011,10 (2):466-473.

[6]Zhang Xinyan,Liu Jiangchuan,Li Bo,et al.CoolStreaming/ DONet:a data-driven overlay network for live media streaming [C]//Proceedings of the 24th Annual Joint Conference of the IEEE Computer and Communications Societies,Miami,USA, Mar 13-17,2005.Piscataway,USA:IEEE,2005:2102-2111.

[7]Xu Jin,Li Xiaofeng,Fu Zhizhong,et al.Recent advances in P2P streaming with network coding[J].Computer Science, 2012,39(3):1-8.

[8]Wang M,Li Baochun.R2:random push with random network coding in live peer-to-peer streaming[J].IEEE Journal on Selected Areas in Communications,2007,25(9): 1655-1666.

[9]Yuan Yuan.The research on performance evaluation and optimization techniques for network coding based data transmission[D].Changsha:National University of Defense Technology,2011.

[10]Niu Di,Li Baochun.On the resilience-complexity tradeoff of network coding in dynamic P2P networks[C]//Proceedings of the 15th IEEE International Workshop on Quality of Service.Piscataway,USA:IEEE,2007:38-46.

[11]Sheikh A M,Fiandrotti A,Magli E,et al.Distributed mediaaware scheduling for P2P streaming with network coding [C]//Proceedings of the 2013 IEEE International Conference on Acoustics,Speech and Signal Processing,Vancouver,Canada,May 26-31,2013.Piscataway,USA:IEEE,2013: 3597-3601.

[12]Liu Zimu,Wu Chuan,Li Baochun,et al.UUSee:largescale operational on-demand streaming with random net coding[C]//Proceedings of the 29th IEEE International Conference on Computer Communication,San Diego,USA, Mar 14-19,2010.Piscataway,USA:IEEE,2010:1-9.

[13]Feng Chen,Li Baochun.On large-scale peer-to-peer streaming systems with network coding[C]//Proceedings of the 16th ACM International Conference on Multimedia,Vancouver, Canada,Oct 26-31,2008.NewYork:ACM,2008:269-278.

[14]Liu Yajie,Dou Wenhua.The P2P streaming media based on network coding[J].Computer Engineering and Science, 2006,28(9):33-34.

[15]Floyd S,Jacobson V.Random early detection gateways forcongestion avoidance[J].IEEE/ACM Transactions on Networking,1993,1(4):397-413.

附中文參考文獻：

[7]徐進,李曉峰,傅志中,等.應用網(wǎng)絡編碼的P2P流媒體技術研究進展[J].計算機科學,2012,39(3):1-8.

[9]袁遠.基于網(wǎng)絡編碼的數(shù)據(jù)傳輸性能分析與優(yōu)化技術研究[D].長沙:國防科學技術大學,2011.

[14]劉亞杰,竇文華.基于網(wǎng)絡編碼的P2P流媒體[J].計算機工程與科學,2006,28(9):33-34.

LI Shan was born in 1981.She received the M.S.degree from Hunan University in 2011.Now she is a lecturer at Changsha Normal College.Her research interests include network coding,P2P streaming media and data mining,etc.

李姍（1981—），女，湖南長沙人，2011年于湖南大學獲得碩士學位，現(xiàn)為長沙師范學院講師，主要研究領域為網(wǎng)絡編碼，P2P流媒體，數(shù)據(jù)挖掘等。主持湖南省教育科學研究優(yōu)秀青年項目。

YUAN Yuan was born in 1980.He received the Ph.D.degree from National University of Defense Technology in 2011.Now he is an assistant researcher at National University of Defense Technology.His research interests include network coding and high performance computing,etc.

袁遠（1980—），男，湖南長沙人，2011年于國防科學技術大學獲得博士學位，現(xiàn)為國防科學技術大學計算機學院助理研究員，主要研究領域為網(wǎng)絡編碼，高性能計算等。主持國家自然科學基金項目。

PENG Yuxing was born in 1963.He is a professor at National University of Defense Technology.His research interest is parallel and distributed processing.

彭宇行（1963—），男，湖南長沙人，國防科技大學計算機學院研究員，主要研究領域為并行與分布式處理。

Exploring Dynamic Segment Granularity in Network Coding Based P2PStreaming*

LI Shan1+,YUAN Yuan2,PENG Yuxing2
1.Department of Electronic and Information Engineering,Changsha Normal College,Changsha 410100,China
2.College of Computer Science,National University of Defense Technology,Changsha 410073,China
+Corresponding author:E-mail:Anglaia@163.com

LI Shan,YUAN Yuan,PENG Yuxing.Exploring dynamic segment granularity in network coding based P2P streaming.Journal of Frontiers of Computer Science and Technology,2016,10(9)：1262-1271.

It has been proved that network coding technology can improve the overall performance of P2P streaming systems.However,the existing systems all use fixed segment granularity coding scheme for data dissemination.To overcome the limitations of fixed segment granularity coding scheme,and fit for the stochastic characteristic of real networks,this paper proposes the new concept of dynamic segment granularity,with which the peers can tune the segment granularity dynamically while encoding.Then this paper answers three questions about how to implement dynamic segment granularity,which are the coding modes,segment granularity range and output performance.Finally this paper designs a new coding scheme with dynamic segment granularity.According to the playing buffer states and the service capabilities of source peers,this scheme can tune the segment granularity of coded blocks dynamically.The experiments illustrate that this scheme can offer better QoS with network jitters or peer churns.It is believed that dynamic segment granularity shares a new idea of further improving the QoS of coding-based P2P streaming systems. Key words:network coding;P2P streaming;dynamic segment granularity

2016-02,Accepted 2016-05.

*The National Natural Science Foundation of China under Grant No.61402514(國家自然科學基金);the Scientific Research Program of Hunan Provincial Education Department under Grant No.12B012(湖南省教育科學研究優(yōu)秀青年項目).

CNKI網(wǎng)絡優(yōu)先出版:2016-05-19,http://www.cnki.net/kcms/detail/11.5602.TP.20160519.1513.002.html

A

TP393