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

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

注：本文系浙江傳媒學院校級課題“基于P2P對等網(wǎng)絡(luò)的視頻點播系統(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ì)量要求也日益突出，通過實驗表明，PPlive的播放啟動延遲在10—120 S 之間，播放時間甚至延遲到140 S，遠遜于電視直播服務(wù)［2］。如何提高P2P 系統(tǒng)的服務(wù)質(zhì)量是當前研究的一個重點。

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

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

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

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

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

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

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

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

2.1 Canopy思想及算法

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

2.2 Canopy算法

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

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

(1) 將要劃分的數(shù)據(jù)都放進一個集合中，作為中心點備選；

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

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

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

Fig 2-1 Canopy created based of steps

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

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

算法1：CreateCluster(Canopy)

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

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

實現(xiàn)過程：

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

(2)n=0

(3)while ClusterCenterSet!={}

{ 從ClusterCenterSet中隨機選取一點 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é)點集有兩種結(jié)果，一種是各個劃分間沒有交叉節(jié)點，是非重疊劃分; 相反則說明兩者是重疊劃分。根據(jù)是否重疊總結(jié)提出K-n 和K-n-t兩種劃分模型。

2. 3 K-n 模型

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

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

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

4.總結(jié)

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

參考文獻：

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

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

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

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