李　姍，袁　遠(yuǎn)，彭宇行1.長沙師范學(xué)院 電子與信息工程系，長沙 410100.國防科學(xué)技術(shù)大學(xué) 計(jì)算機(jī)學(xué)院，長沙 410073

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

李?yuàn)?+，袁遠(yuǎn)2，彭宇行2
1.長沙師范學(xué)院 電子與信息工程系，長沙 410100
2.國防科學(xué)技術(shù)大學(xué) 計(jì)算機(jī)學(xué)院，長沙 410073

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

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

1　引言

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

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

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

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

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

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

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

2　基本概念和原理

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

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

下面用一個(gè)例子，從請(qǐng)求節(jié)點(diǎn)的角度說明動(dòng)態(tài)段粒度較固定段粒度的優(yōu)勢(shì)。

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

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

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

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

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

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

3　降階與升階編碼

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

3.1降階編碼

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

例1設(shè)基于網(wǎng)絡(luò)編碼的P2P流媒體系統(tǒng)的有限域?yàn)镚F(28)，初始段粒度為5，某源節(jié)點(diǎn)已收到3個(gè)段粒度為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表示每個(gè)編碼塊中編碼數(shù)據(jù)。每個(gè)假設(shè)要求降階到段粒度為3的編碼塊，

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

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

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

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

證明 采用第一數(shù)學(xué)歸納法進(jìn)行證明。

（1）當(dāng)k=1時(shí)，接收到的任意編碼塊都可以看作是包含該段m個(gè)原始?jí)K信息的編碼塊，因此d∈{m}。

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

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

源節(jié)點(diǎn)上采用降階編碼方式，等價(jià)于為請(qǐng)求節(jié)點(diǎn)分?jǐn)偭私獯a計(jì)算開銷，因此請(qǐng)求節(jié)點(diǎn)能夠在收到小于m個(gè)編碼塊時(shí)，提前解碼出部分原始數(shù)據(jù)，保證播放緩沖不被清空，如例2所示。

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

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

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

證明 采用第一數(shù)學(xué)歸納法進(jìn)行證明。

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

（2）當(dāng)k=2，d∈{m,m-1}時(shí)，有：

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

3.2升階編碼

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

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

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

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

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

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

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

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

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

4.1系統(tǒng)模型

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

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

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

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

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

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

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

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

（2）源節(jié)點(diǎn)服務(wù)能力

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

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

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

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

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

5　性能評(píng)價(jià)

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

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

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

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

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

Fig.4　Request node buffer data when source node service ability shaking圖4　源節(jié)點(diǎn)服務(wù)能力抖動(dòng)時(shí)請(qǐng)求節(jié)點(diǎn)緩沖數(shù)據(jù)量

6　結(jié)束語

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

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.

附中文參考文獻(xiàn)：

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

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

[14]劉亞杰,竇文華.基于網(wǎng)絡(luò)編碼的P2P流媒體[J].計(jì)算機(jī)工程與科學(xué),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.

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

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.

袁遠(yuǎn)（1980—），男，湖南長沙人，2011年于國防科學(xué)技術(shù)大學(xué)獲得博士學(xué)位，現(xiàn)為國防科學(xué)技術(shù)大學(xué)計(jì)算機(jī)學(xué)院助理研究員，主要研究領(lǐng)域?yàn)榫W(wǎng)絡(luò)編碼，高性能計(jì)算等。主持國家自然科學(xué)基金項(xià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—），男，湖南長沙人，國防科技大學(xué)計(jì)算機(jī)學(xué)院研究員，主要研究領(lǐng)域?yàn)椴⑿信c分布式處理。

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(國家自然科學(xué)基金);the Scientific Research Program of Hunan Provincial Education Department under Grant No.12B012(湖南省教育科學(xué)研究優(yōu)秀青年項(xiàng)目).

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

A

TP393