基于聚類劃分的P2P 流媒體系統(tǒng)構(gòu)建

摘要：對(duì)常見的P2P 流媒體系統(tǒng)進(jìn)行分析研究，提出了基于聚類劃分的P2P 流媒體系統(tǒng)，并根據(jù)Canopy聚類情況得出K-n 模型和K-n-t模型，對(duì)這兩種模型的網(wǎng)絡(luò)特征作了理論分析和比較并指出適應(yīng)范圍。

關(guān)鍵詞：對(duì)等網(wǎng)絡(luò) 流媒體 聚類

注：本文系浙江傳媒學(xué)院校級(jí)課題“基于P2P對(duì)等網(wǎng)絡(luò)的視頻點(diǎn)播系統(tǒng)”的研究成果。

Modeling of cluster structure based on P2P streaming systems

Qiu Rongtai Yang Xi

Abstract: A research of normal structure based on P2P streaming systems． Two types of models，named k- n model and k-n-t model，were announced，and then compared and analyzed the network characteristics theoretically. Present its fitable situations.

Key words: peer-to-peer network; media streaming; clustering

隨著P2P流媒體PPStream、SopCast、PPlive 的廣泛使用，其服務(wù)質(zhì)量要求也日益突出，通過實(shí)驗(yàn)表明，PPlive的播放啟動(dòng)延遲在10—120 S 之間，播放時(shí)間甚至延遲到140 S，遠(yuǎn)遜于電視直播服務(wù)［2］。如何提高P2P 系統(tǒng)的服務(wù)質(zhì)量是當(dāng)前研究的一個(gè)重點(diǎn)。

1.常見的P2P流媒體系統(tǒng)

為提高系統(tǒng)的服務(wù)質(zhì)量，現(xiàn)流行的P2P 流媒體系統(tǒng)，如NICE、PPLive、NetTube 等，大多依據(jù)節(jié)點(diǎn)的能力、網(wǎng)絡(luò)距離等將節(jié)點(diǎn)進(jìn)行歸類劃分。例如，PPLive 根據(jù)節(jié)點(diǎn)能力來選代理網(wǎng)關(guān)節(jié)點(diǎn)，并構(gòu)建由代理網(wǎng)關(guān)為中心節(jié)點(diǎn)的“域”所組成的雙層覆蓋網(wǎng)絡(luò)結(jié)構(gòu)。NICE 使用層和簇的概念，將節(jié)點(diǎn)歸類到不同層次的“簇”中，由“簇頭”節(jié)點(diǎn)負(fù)責(zé)數(shù)據(jù)的傳輸。NetTube 則根據(jù)用戶節(jié)目興趣度將節(jié)點(diǎn)加入到不同的“群集”中，通過高效的視頻索引和檢索策略顯著地提高了視頻播放質(zhì)量。因此，本文在歸納和比較現(xiàn)有的P2P 流媒體系統(tǒng)結(jié)構(gòu)的基礎(chǔ)上，提出基于聚類劃分的P2P 流媒體系統(tǒng)并進(jìn)行建模研究。根據(jù)聚類結(jié)果是否重疊劃分，分別提出了K-n 模型和K-n-t 模型兩種結(jié)構(gòu)模型。對(duì)這兩種結(jié)構(gòu)模型作了理論分析比較，指出了各自的應(yīng)用場(chǎng)景，對(duì)設(shè)計(jì)和實(shí)現(xiàn)P2P 流媒體系統(tǒng)的具有重要的參考意義。

2.基于聚類劃分的P2P 流媒體系統(tǒng)

P2P 流媒體系統(tǒng)主要包括以下三方面:

中心節(jié)點(diǎn)master的選擇: 中心節(jié)點(diǎn)對(duì)應(yīng)于P2P流媒體系統(tǒng)結(jié)構(gòu)劃分中的頭節(jié)點(diǎn)，起到管理與調(diào)試的作用。

2) 區(qū)域劃分選擇: 即普通節(jié)點(diǎn)如何從已知的中心節(jié)點(diǎn)集合中選擇某個(gè)中心節(jié)點(diǎn)，并加入到其所在的劃分中。

3) 重疊劃分: 即根據(jù)節(jié)點(diǎn)是否同時(shí)存在于多個(gè)劃分區(qū)域中，形成非重疊或重疊分區(qū)結(jié)構(gòu)。

設(shè)P2P 流媒體系統(tǒng)中所有節(jié)點(diǎn)的集合表示為A = { a0，a1，…aN － 1} ，N 是節(jié)點(diǎn)總數(shù)。中心節(jié)點(diǎn)集合表示為CN = { c0，c1，…，c k － 1} ，k 是中心節(jié)點(diǎn)總數(shù)，也是系統(tǒng)中社區(qū)的數(shù)量。將ci所在社區(qū)Ci中所有節(jié)點(diǎn)的集合表示為Ci = { ci，b0，b1，…，b ni － 1} i∈{ 0，1，…，k － 1} ，bni是社區(qū)Ci中的普通節(jié)點(diǎn)，ni是該社區(qū)中普通節(jié)點(diǎn)的數(shù)量，根據(jù)以上定義可得A = C0∪C1∪…∪Ck － 1。普通節(jié)點(diǎn)bni依據(jù)Canopy聚類方法選擇加入到社區(qū)Ci中。

2.1 Canopy思想及算法

Canopy聚類分兩個(gè)階段執(zhí)：第一步就是粗糙地、快速和近似地把數(shù)據(jù)分成一些重疊的子集，稱之為罩蓋（Canopy）；然后對(duì)Canopy內(nèi)的點(diǎn)用精確的計(jì)算方法再聚類。

2.2 Canopy算法

創(chuàng)建Canopy是以某一數(shù)據(jù)點(diǎn)為初始中心，用一種相似度計(jì)算方法找出在一個(gè)閾值范圍內(nèi)的數(shù)據(jù)點(diǎn)集合。在創(chuàng)建Canopy的過程中，所有的數(shù)據(jù)點(diǎn)都必須出現(xiàn)在至少一個(gè)Canopy中，對(duì)于每一個(gè)聚類，存在至少一個(gè)Canopy能夠包含這個(gè)聚類的所有元素。當(dāng)創(chuàng)建Canopy的條件都滿足時(shí)，任何兩個(gè)不處于同一個(gè)Canopy的點(diǎn)將不可能屬于同一聚類，所以在第二階段時(shí)不需要計(jì)算不處于同一個(gè)Canopy的點(diǎn)之間的距離，從而大大減少了計(jì)算量。

第一階段由于數(shù)據(jù)量非常大，首先隨機(jī)設(shè)置一個(gè)中心點(diǎn)，采用一種比較簡(jiǎn)單的計(jì)算方法找到中心點(diǎn)周圍區(qū)域的所有數(shù)據(jù)點(diǎn)構(gòu)成一個(gè)“Canopy”，然后再尋找下一個(gè)中心點(diǎn)周圍的區(qū)域，同樣也形成一個(gè)“Canopy”，一直到找遍中心點(diǎn)集合中所有數(shù)據(jù)點(diǎn)的聚類為止。為了保證所有的點(diǎn)都存在于相應(yīng)的Canopy中，設(shè)置的中心點(diǎn)范圍應(yīng)該盡可能的廣，范圍的確定影響聚類的精確度，可以采用了兩個(gè)距離閾值T1，T2（T1≥T2）。創(chuàng)建Canopy的步驟為：

(1) 將要?jiǎng)澐值臄?shù)據(jù)都放進(jìn)一個(gè)集合中，作為中心點(diǎn)備選；

(2) 隨機(jī)選取集合中一個(gè)點(diǎn)作為中心點(diǎn)，把與中心點(diǎn)距離小于等于T1的點(diǎn)放進(jìn)Canopy，從中心點(diǎn)集合中刪除與中心點(diǎn)距離小于等于T2的點(diǎn)（包括原來的中心點(diǎn)）；

(3) 檢查中心點(diǎn)集合是否已是空集，如果是則終止操作；如果不是空集，重復(fù)執(zhí)行步驟(2)。

圖2-1 基于以上的步驟創(chuàng)建的一些Canopy

Fig 2-1 Canopy created based of steps

圖2-1是根據(jù)以上步驟創(chuàng)建的一些Canopy。圖中的圈代表罩蓋，首先點(diǎn)A是隨機(jī)選擇的中心點(diǎn)，選擇一種花費(fèi)少的，近似的距離計(jì)算方法計(jì)算點(diǎn)之間的距離，把與A點(diǎn)距離小于等于T1的點(diǎn)放進(jìn)Canopy，圖中共有7個(gè)點(diǎn)放入第一個(gè)Canopy中，然后從中心點(diǎn)集合中刪除與中心點(diǎn)距離小于等于T2的點(diǎn)（包括原來的中心點(diǎn)）；圖中所示為A附近的6個(gè)點(diǎn)，依次類推，創(chuàng)建“Canopy”B，C，D，E的過程與A一樣。依據(jù)圖可以得出，如果數(shù)據(jù)點(diǎn)比較密集，則創(chuàng)建出的Canopy可能是重疊的，圖中共分為5個(gè)聚類，對(duì)于每一個(gè)聚類，至少存在一個(gè)Canopy能夠完全包括這個(gè)聚類，而精確的距離計(jì)算方法只用于同一個(gè)Canopy的數(shù)據(jù)點(diǎn)，因?yàn)镃anopy中的點(diǎn)遠(yuǎn)遠(yuǎn)少于整個(gè)數(shù)據(jù)集的點(diǎn)，相比之下其計(jì)算量是非常小的。除了用一種花費(fèi)較少的距離計(jì)算方法聚類以外，仍然用精確的方法聚類Canopy中的數(shù)據(jù)，這個(gè)方法在降低計(jì)算成本的情況下仍然保證了計(jì)算結(jié)果的準(zhǔn)確性。

根據(jù)以上的分析，創(chuàng)建Canopy的算法如下：

算法1：CreateCluster(Canopy)

輸入：數(shù)據(jù)集D，距離閾值T1，T2（T1≥T2）

輸出：創(chuàng)建的Canopy類

實(shí)現(xiàn)過程：

(1)備選中心點(diǎn)集合 ClusterCenterSet=D

(2)n=0

(3)while ClusterCenterSet!={}

{ 從ClusterCenterSet中隨機(jī)選取一點(diǎn) k;

Canopyn (k)={(k，k’):k’∈D ∩ approxDist(k，k’)≤T1};

n=n+1;

ClusterCenterSet= ClusterCenterSet － {k’| approxDist(k，k’)≤T2};

Return Canopyn (k);}

經(jīng)過Canopy聚類后節(jié)點(diǎn)集有兩種結(jié)果，一種是各個(gè)劃分間沒有交叉節(jié)點(diǎn)，是非重疊劃分; 相反則說明兩者是重疊劃分。根據(jù)是否重疊總結(jié)提出K-n 和K-n-t兩種劃分模型。

2. 3 K-n 模型

每個(gè)劃分均具有相同的節(jié)點(diǎn)數(shù)量，即ni = n，K-n 模型表示該系統(tǒng)包含k 個(gè)社區(qū)，每個(gè)社區(qū)由1 個(gè)中心節(jié)點(diǎn)和n個(gè)普通節(jié)點(diǎn)組成，而且普通節(jié)點(diǎn)只存在于一個(gè)社區(qū)中，即| CN | = k，|Ci | = n + 1，且Cov( Ci，Cj) = 0。如圖2-2所示

實(shí)際當(dāng)中經(jīng)常存在的是重疊結(jié)構(gòu)，例如，P2P 流媒體系統(tǒng)中的節(jié)點(diǎn)同時(shí)存在于多個(gè)劃分中。因此，k- n - t 模型表示系統(tǒng)包含k 個(gè)社區(qū)，每個(gè)社區(qū)由1 個(gè)中心節(jié)點(diǎn)和n 個(gè)普通節(jié)點(diǎn)組成，而且每個(gè)普通節(jié)點(diǎn)同時(shí)存在于t( 1≤t≤k) 個(gè)社區(qū)中，即| CN | = k，|Ci | = n + 1，可以得出K-n 模型是K-n － t模型的一個(gè)特例。如圖2-3 所示

經(jīng)實(shí)驗(yàn)證明，隨著k 的增加，K-n 模型和K-n-t模型結(jié)構(gòu)的平均路徑也隨之增加，并且K-n 模型社區(qū)結(jié)構(gòu)的平均路徑要顯著高于K-n-t模型和隨機(jī)網(wǎng)絡(luò)，因此，K-n 模型的高聚集系數(shù)是以平均路徑為前提; 而K-n-t模型社區(qū)結(jié)構(gòu)的平均路徑具有與隨機(jī)網(wǎng)絡(luò)基本一樣，且t 越大越接近，由于K-n-t模型社區(qū)結(jié)構(gòu)中節(jié)點(diǎn)同時(shí)存在于多個(gè)劃分中，增加了網(wǎng)絡(luò)中節(jié)點(diǎn)之間“長(zhǎng)邊”連接的機(jī)會(huì)，從而降低了平均路徑。可見，相比K-n 模型社區(qū)結(jié)構(gòu)，K-n-t模型社區(qū)結(jié)構(gòu)在聚集系數(shù)和平均路徑兩方面達(dá)到了更好的折衷，因此，K-n-t模型更適用于用戶離散型的P2P 流媒體應(yīng)用場(chǎng)景，如面向互聯(lián)網(wǎng)的網(wǎng)絡(luò)電視直播等。

4.總結(jié)

基于聚類劃分的設(shè)計(jì)顯著地提高了P2P 流媒體系統(tǒng)的服務(wù)質(zhì)量。本文提出了針對(duì)K-n 模型和K-n-t模型的適用范圍，并作了分析和比較。結(jié)果表明，K-n 模型的聚集程度要遠(yuǎn)高于K-n-t模型，但K-n-t模型可以在聚集程度和平均路徑均衡，對(duì)實(shí)際P2P 流媒體系統(tǒng)的設(shè)計(jì)和實(shí)現(xiàn)具有重要的參考意義。

參考文獻(xiàn)：

［1］秦豐林，劉琚.P2P 網(wǎng)絡(luò)流媒體關(guān)鍵技術(shù)［J］.電子學(xué)報(bào)，2011， 39( 4) : 919-927．

［2］劉琪，葛連升，秦豐林.基于社區(qū)結(jié)構(gòu)的P2P 流媒體系統(tǒng)建模研究[J].山東大學(xué)學(xué)報(bào)，2012，5:3-4

［3］戴磊，王源，劉科科.一種主動(dòng)學(xué)習(xí)式P2 P 流識(shí)別方法[J].計(jì)算機(jī)應(yīng)用研究，2012，2:2-3

［4］于敬敬，王子磊，奚宏生，基于FGS 的P2P 流媒體網(wǎng)絡(luò)編碼及調(diào)度[J].計(jì)算機(jī)工程，2012，2:2