混合流媒體分發(fā)系統(tǒng)中多指標用戶群分組算法

萬明剛，李澤平，張 軍

(貴州大學 計算機科學與技術學院，貴州 貴陽 550025)

混合流媒體分發(fā)系統(tǒng)中多指標用戶群分組算法

萬明剛，李澤平，張 軍

(貴州大學 計算機科學與技術學院，貴州 貴陽 550025)

針對混合流媒體分發(fā)系統(tǒng)中服務節(jié)點提供服務時出現(xiàn)額外的跨地域、跨網(wǎng)絡開銷以及搜索服務節(jié)點效率低下的問題，提出一種基于多指標的用戶群分組算法，并應用于服務節(jié)點選擇。依次分別利用節(jié)點位置和網(wǎng)絡類型對用戶群進行分組，將候選服務節(jié)點限制在同地域、同ISP范圍內(nèi)，以減少不必要的跨地域、跨網(wǎng)絡開銷；然后結合節(jié)點興趣對用戶群作進一步劃分，將搜索服務節(jié)點的范圍限制在興趣組內(nèi)，以減小搜索流量、提高搜索效率。仿真實驗表明：提出的算法能有效將用戶群分組，提高分發(fā)系統(tǒng)服務效率。

混合流媒體分發(fā)系統(tǒng);節(jié)點位置;網(wǎng)絡類型;節(jié)點興趣;分組;服務節(jié)點選擇

1 概 述

在CDN-P2P混合流媒體分發(fā)系統(tǒng)中，用戶節(jié)點可以通過兩種方式獲取流媒體資源：一是由邊緣服務器提供，二是由peer節(jié)點之間共享。在以peer節(jié)點之間共享的方式獲取資源時，請求節(jié)點搜索擁有所請求的流媒體資源的peer節(jié)點，并從中選擇一個或多個節(jié)點作為服務節(jié)點。而這些節(jié)點可能分布于不同的地域、接入不同的ISP。如果請求節(jié)點忽略位置較近的節(jié)點而選擇位置較遠的節(jié)點作為服務節(jié)點，提供服務時流媒體資源需要經(jīng)過較多的物理鏈路才能到達請求節(jié)點，增加了網(wǎng)絡負載、引起了不必要的跨地域開銷；如果請求節(jié)點忽略自己所在ISP內(nèi)部的節(jié)點，而選擇不同ISP的節(jié)點作為服務節(jié)點，提供服務時流媒體資源需要跨過網(wǎng)絡邊界才能到達請求節(jié)點，引起了不必要的跨網(wǎng)絡開銷。另外，在搜索服務節(jié)點時如果不對搜索范圍加以限制而采用全局洪泛搜索的方式，將會導致搜索效率低下，并大幅增加骨干網(wǎng)的通信負載，導致網(wǎng)絡運營商有更強烈的愿望來限制P2P網(wǎng)絡流量。

針對上述問題，國內(nèi)外眾多研究機構、專家學者都積極展開了研究。

文獻[1]基于節(jié)點之間的網(wǎng)絡延遲提出一種分箱策略，測量網(wǎng)絡節(jié)點到地標節(jié)點集中各地標節(jié)點的網(wǎng)絡延遲，據(jù)此將網(wǎng)絡節(jié)點分到不同的箱中。文獻[2]基于網(wǎng)絡坐標計算節(jié)點之間的歐氏距離，結合遺傳聚類算法和K-means算法提出一種混合聚類算法對節(jié)點進行有效聚類。文獻[3-4]對計算機網(wǎng)絡上的距離預測技術進行了研究。文獻[5]提出一種基于興趣相關度的P2P網(wǎng)絡搜索優(yōu)化算法，介紹了興趣向量及興趣相關度的描述方法。文獻[6]描述了節(jié)點興趣以及興趣相關度的表示方法，借助層次聚類法和K-means聚類法探討P2P社區(qū)的形成過程。文獻[7]提出一種基于網(wǎng)絡拓撲和節(jié)點興趣偏好的P2P搜索機制。文獻[8-10]對近年來提出的較有代表性的聚類算法進行分析概括，介紹了聚類分析的研究熱點、難點、不足和有待解決的一些問題。

現(xiàn)有這些對分組方法的研究多是基于節(jié)點位置或者節(jié)點興趣某一個指標，設計出的算法對用戶群體劃分不夠細致，不能兼顧搜索效率以及網(wǎng)絡開銷的問題，分組結果具有明顯的缺陷。文中提出一種基于多指標的用戶群分組算法，結合基于節(jié)點位置分組與基于節(jié)點興趣分組各自的優(yōu)勢，引入網(wǎng)絡類型這一指標，利用這三個指標對用戶群進行層次劃分，盡可能將候選服務節(jié)點限制在同地域、同網(wǎng)絡類型以及興趣相似的節(jié)點小組內(nèi)，以減少不必要的跨地域、跨網(wǎng)絡開銷，提高搜索效率。

2 體系結構

目前主流的流媒體分發(fā)結構有基于CDN[11-13]、基于P2P[14-15]和CDN-P2P[16]混合結構。文中研究的分組算法是基于CDN-P2P混合結構。將CDN的思想引入P2P網(wǎng)絡，在骨干網(wǎng)部署CDN系統(tǒng)，在接入網(wǎng)構建P2P區(qū)域化網(wǎng)絡，融合了CDN高可靠性和P2P低成本、高可擴展性的優(yōu)勢，應用前景廣泛。

混合流媒體分發(fā)系統(tǒng)體系結構如圖1所示。

圖1 混合流媒體分發(fā)系統(tǒng)體系結構

3 分組算法

3.1 分組指標

文中選取節(jié)點位置、網(wǎng)絡類型和節(jié)點興趣三個指標設計混合流媒體分發(fā)系統(tǒng)中的用戶群分組算法，盡可能將位置鄰近、網(wǎng)絡類型相同、興趣近似的用戶節(jié)點劃分到同一個小組。

基于節(jié)點位置分組的基本思想是根據(jù)節(jié)點在網(wǎng)絡中所處的位置直接計算節(jié)點間的網(wǎng)絡距離或者估計節(jié)點間的網(wǎng)絡鄰近度，將網(wǎng)絡距離較小或者相對鄰近的節(jié)點劃分到同一個位置組中,將候選服務節(jié)點限制在位置組內(nèi)，以減少不必要的跨地域開銷。其中，網(wǎng)絡距離是一種抽象概念，通常用網(wǎng)絡延遲來衡量，以RTT表示[8]。

文中采用基于參考點的網(wǎng)絡鄰近度估計技術，選取混合流媒體分發(fā)系統(tǒng)中的邊緣服務器節(jié)點作為地標節(jié)點(Landmark)，用節(jié)點到地標節(jié)點的網(wǎng)絡延遲來定義它們之間的距離，根據(jù)每個節(jié)點到各地標節(jié)點的距離預估節(jié)點之間的鄰近度，進而根據(jù)鄰近度進行第一次基于節(jié)點位置的分組。

定義1：節(jié)點位置。

算法 1：基于節(jié)點位置分組算法。

對每個節(jié)點ni，測量它到地標節(jié)點集L中所有地標節(jié)點的RTT，并按升序排列，得到節(jié)點ni到各個地標節(jié)點的RTT序列。將RTT序列相同的節(jié)點歸到同一個位置組。

由于同一網(wǎng)絡類型內(nèi)的節(jié)點之間網(wǎng)絡連接狀況、通信質量比較有保證，而跨網(wǎng)絡之間的通信質量比較差，因此選擇服務節(jié)點時應盡量選擇同一網(wǎng)絡類型的節(jié)點?；诰W(wǎng)絡類型分組的思想便是基于這一點。

定義2：網(wǎng)絡類型。

根據(jù)網(wǎng)絡運營商，文中將網(wǎng)絡類型分為電信、移動、聯(lián)通三類。

算法2：基于網(wǎng)絡類型分組算法。

將基于節(jié)點位置分組的結果按網(wǎng)絡類型繼續(xù)劃分，將每個位置組的用戶群節(jié)點按其所接入的網(wǎng)絡類型進一步劃分為更小的網(wǎng)絡類型組。

在流媒體分發(fā)系統(tǒng)中，節(jié)點請求流媒體資源表現(xiàn)出一定的興趣，興趣之間也表現(xiàn)出一定的相似程度。興趣相似的節(jié)點之間共享資源的概率明顯大于興趣不相關的節(jié)點之間共享資源的概率。為此，文中試圖找出一種描述節(jié)點興趣、度量興趣相似程度的方法，并據(jù)此將基于網(wǎng)絡類型分組的結果按節(jié)點興趣繼續(xù)劃分，將候選服務節(jié)點限制在興趣組內(nèi)，有效減小搜索流量、提高搜索效率。

定義3：節(jié)點興趣。

節(jié)點請求流媒體資源時表現(xiàn)出一定的興趣偏好，可以用興趣向量和興趣相似度來度量。

定義4：興趣向量。

定義5：興趣相似度。

算法3：基于節(jié)點興趣分組算法。

1)層次聚類：給定目標聚類數(shù)k，用層次聚類法確定k個初始聚類中心。

(1)給定節(jié)點集合N={ni,i=1,2,…,m}，將集合N中每個節(jié)點看作一個具有單獨成員的類。即：

N=C={Ci,i=1,2,…,m}

其中，Ci={ni},i=1,2,…,m。

(2)計算C中每兩個類之間的興趣相似度Sim(Ci,Cj),i=1,2,…,m,j=1,2,…,m。當Sim(Ci,Cj)=Sim(ni,nj)≥θ時，有：

這樣得到一組新的Ci,i=1,2,…,m。將Ci按模降序排列，取前k個Ci對應的節(jié)點ni作為初始聚類中心，記為s={nj,j=1,2,…,k}。

2)K-means聚類。

依次計算N中每個節(jié)點ni與每個種子節(jié)點sj的興趣相似度Sim(ni,sj)，找出與節(jié)點ni興趣相似度最大的種子節(jié)點sj，將ni歸入以sj為聚類中心的類。

3)重復計算聚類中心s并重新聚類，直至聚類結果穩(wěn)定。

3.2 初始分組形成

算法4:初始分組形成算法。

Step2：依次對每一個位置組Cr根據(jù)節(jié)點ni所屬網(wǎng)絡類型(電信、移動、聯(lián)通)進一步劃分為{Cr1,Cr2,Cr3}，將節(jié)點ni歸入相應的分組Crs,s=1,2,3。

3.3 分組更新

考慮到網(wǎng)絡環(huán)境的動態(tài)性，節(jié)點之間的網(wǎng)絡延遲、節(jié)點位置等都不是固定不變的，因此設計的算法應該能隨網(wǎng)絡狀況的變化而動態(tài)更新。

算法5：分組更新算法。

每經(jīng)過一個固定的時間間隔t，根據(jù)當前網(wǎng)絡狀況重新計算分組。

4 服務節(jié)點選擇

文中算法將對用戶群分組的結果存儲在追蹤服務器TR上并建立索引，RS是重定向服務器。

當一個節(jié)點需要獲得某個流媒體資源時，首先將服務請求同時發(fā)送給RS和TR。RS在查詢了索引表之后，根據(jù)某種重定向策略返回一個離請求節(jié)點距離較近且負載較輕的邊緣服務器的地址信息。TR在查詢了索引表之后，返回與請求節(jié)點同屬于一個興趣組的其他節(jié)點的地址信息。請求節(jié)點在收到返回的邊緣服務器和同興趣組節(jié)點的地址信息后，同時向該興趣組內(nèi)其他節(jié)點發(fā)出流媒體服務請求，在興趣組內(nèi)搜索擁有所請求資源的peer節(jié)點作為候選服務節(jié)點。如果搜索到有節(jié)點存儲有所請求的流媒體資源，則在其中選取一個或幾個節(jié)點作為服務節(jié)點為請求節(jié)點提供服務；如果搜索到?jīng)]有節(jié)點存儲有所請求的流媒體資源，則將服務請求重定向到邊緣服務器，由邊緣服務器為其提供服務。

服務節(jié)點選擇過程如圖2所示。

圖2 服務節(jié)點選擇過程

5 仿真及結果分析

實驗在一臺PC機上完成，模擬具有1 000個節(jié)點的對等網(wǎng)絡。每個節(jié)點用一個數(shù)據(jù)結構模擬，數(shù)據(jù)結構中定義了該節(jié)點到各地標節(jié)點的網(wǎng)絡延遲、所屬網(wǎng)絡類型以及節(jié)點興趣。實驗數(shù)據(jù)采用人工模擬的方式獲得，在設定的各個參數(shù)取值范圍內(nèi)隨機賦值。為簡化模型，假設：地標節(jié)點數(shù)為3，每個節(jié)點到各地標節(jié)點的網(wǎng)絡延遲在[0,100]區(qū)間內(nèi)隨機取整數(shù)值；節(jié)點網(wǎng)絡類型取值為0,1,2，分別對應電信、移動、聯(lián)通；網(wǎng)絡中流媒體資源分為5類，每個節(jié)點擁有每類資源的數(shù)量在[0,10]區(qū)間內(nèi)隨機取整數(shù)值。分組算法用Java語言編程實現(xiàn)，取K-means算法中k=3，這樣最終將1 000個節(jié)點分為54組。每次實驗隨機選取一個節(jié)點作為請求節(jié)點，對其最感興趣的一類資源發(fā)出搜索請求。

在實驗中對比分析了全局洪泛法、基于節(jié)點位置分組算法、基于網(wǎng)絡類型分組算法、基于節(jié)點興趣分組算法和文中算法五種服務節(jié)點選擇方案的性能差異。為方便比較，定義了四個主要性能指標：

跨地域服務節(jié)點占比=搜索到的節(jié)點中屬于不同地域的節(jié)點數(shù)/搜索到的節(jié)點總數(shù)

跨網(wǎng)絡類型服務節(jié)點占比=搜索到的節(jié)點中屬于不同網(wǎng)絡類型的節(jié)點數(shù)/搜索到的節(jié)點總數(shù)

搜索到的資源占比=搜索到的某類資源數(shù)/網(wǎng)絡中該類資源總數(shù)

搜索范圍占比=搜索范圍內(nèi)所有節(jié)點數(shù)/網(wǎng)絡中總節(jié)點數(shù)

采用多次重復實驗的方式，每次實驗記錄下各個性能指標的值，用Excel和Matlab對實驗數(shù)據(jù)進行處理，結果如圖3～6所示。

圖3 跨地域服務節(jié)點占比

圖4 跨網(wǎng)絡類型服務節(jié)點占比

圖3、圖4表明：相比較全局洪泛法選擇服務節(jié)點而言，文中所提用戶群分組算法集合了基于節(jié)點位置分組與基于網(wǎng)絡類型分組的優(yōu)點，能有效將服務節(jié)點選擇范圍限制在同地域、同網(wǎng)絡類型范圍內(nèi)，從而達到減少不必要的跨地域、跨網(wǎng)絡開銷的目的。

圖5 搜索到的資源占比

圖5、圖6表明：文中所提用戶群分組算法較其他幾種常見分組算法而言，選擇服務節(jié)點時搜索范圍明顯更小，能有效降低搜索流量，同時也能保證一定的資源搜索量。

圖6 搜索范圍占比

6 結束語

文中提出一種混合流媒體分發(fā)系統(tǒng)中的多指標用戶群分組算法，并通過仿真實驗驗證了該算法的有效性，但對于其在真實網(wǎng)絡環(huán)境中的應用價值尚有待驗證。下一步的研究將集中于此，將該算法部署到流媒體分發(fā)系統(tǒng)中加以論證。

[1]RatnasamyS,HandleyM,KarpR,etal.Topologically-awareoverlayconstructionandserverselection[C]//ProcofINFOCOM2002.[s.l.]:IEEE,2002:1190-1199.

[2] 周振朝,費耀平,李 敏.基于網(wǎng)絡坐標的無結構P2P節(jié)點聚類算法[J].計算機工程,2010,36(11):98-100.

[3] 邢長友,陳 鳴.網(wǎng)絡距離預測技術[J].軟件學報,2009,20(9):2470-2482.

[4] 王意潔,李小勇.網(wǎng)絡距離預測技術研究[J].軟件學報,2009,20(6):1574-1590.

[5] 吳 思,歐陽松.基于興趣相關度的P2P網(wǎng)絡搜索優(yōu)化算法[J].計算機工程,2008,34(11):102-104.

[6] 趙捧未,馬 琳,秦春秀.P2P用戶興趣社區(qū)形成研究[J].現(xiàn)代圖書情報技術,2013(10):53-58.

[7] 梁衛(wèi)芳,黃建華.基于網(wǎng)絡拓撲和節(jié)點興趣的P2P搜索機制[J].計算機工程與設計,2008,29(6):1316-1318.

[8] 鄭力明,李曉冬,李小勇,等.P2P覆蓋網(wǎng)中的聚類研究綜述[J].計算機應用研究,2010,27(3):806-810.

[9] 楊 博,劉大有,LIUJiming,等.復雜網(wǎng)絡聚類方法[J].軟件學報,2009,20(1):54-66.

[10] 孫吉貴,劉 杰,趙連宇.聚類算法研究[J].軟件學報,2008,19(1):48-61.

[11]AdhikariVK,JainS,ChenY,etal.VivisectingYouTube:anactivemeasurementstudy[C]//ProcofINFOCOM.Orlando,FL:IEEE,2012:2521-2525.

[12]AdhikariVK,GuoY,HaoF,etal.Unreelingnetflix:understandingandimprovingmulti-CDNmoviedelivery[C]//ProcofINFOCOM.Orlando,FL:IEEE,2012:1620-1628.

[13]AdhikariVK,GuoY,HaoF,etal.AtaleofthreeCDNs:anactivemeasurementstudyofHuluanditsCDNs[C]//ProcofIEEEconferenceoncomputercommunicationsworkshops.Orlando,FL:IEEE,2012:7-12.

[14]HuangYan,FuTZJ,ChiuDah-Ming,etal.Challenges,designandanalysisofalarge-scalep2p-vodsystem[C]//ProcofSIGCOMM.[s.l.]:ACM,2008:375-388.

[15]LeiJ,ShiL,FuX.AnexperimentalanalysisofJoostpeer-to-peerVoDservice[J].Peer-to-PeerNetw.Appl.,2010,3(4):351-362.

[16]ZhangG,LiuW,HeiX,etal.UnreelingXunleiKankan:understandinghybridCDN-P2Pvideo-on-demandstreaming[J].IEEETransactionsonMultimedia,2015,17(2):229-242.

A User-group Grouping Algorithm Based on Multiple Indicators in Hybrid Streaming System

WAN Ming-gang,LI Ze-ping,ZHANG Jun

(College of Computer Science & Technology,Guizhou University,Guiyang 550025,China)

To address the problem of additional cross-regional and cross-network cost that appears when the service node provides streaming media services,and the problem of inefficiency in searching service node,a grouping algorithm based on multiple indicators is proposed and used in server selection.As the algorithm goes,the user-group would be grouped by the node location and network type successively,limited the candidate server nodes in the same area and the same ISP,consequently reduced additional cross-regional and cross-network cost.Then the user-group would be divided further based on nodes’ interest,limited the search scope within an interest group,consequently reduced searching traffic and improved searching efficiency.Simulation demonstrates that the proposed algorithm can effectively divide the user-group,improving service efficiency.

hybrid streaming system;node location;Internet type;node interest;grouping;server node selection

2015-08-05

2015-12-16

時間：2016-09-18

國家自然科學基金資助項目(61462014)

萬明剛(1989-)，男，碩士研究生，研究方向為計算機網(wǎng)絡與流媒體技術；李澤平，通訊作者，博士，教授，碩士研究生導師，研究方向為計算機網(wǎng)絡與流媒體技術。

http://www.cnki.net/kcms/detail/61.1450.TP.20160918.1707.010.html

TP301.6

A

1673-629X(2016)10-0036-05

10.3969/j.issn.1673-629X.2016.10.008