李 彥，張 華

(重慶理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，重慶 400054)

近年來，以UGC(user generated content)為特點(diǎn)的視頻分享方式已成為網(wǎng)絡(luò)視頻的重要應(yīng)用之一。目前，視頻網(wǎng)站不僅僅能給用戶提供視頻，也允許用戶上傳一定長(zhǎng)度的視頻(時(shí)長(zhǎng)一般不超過10 min)，以供其他用戶分享。當(dāng)用戶在觀看視頻時(shí)，就是一個(gè)“消費(fèi)者”，而當(dāng)用戶上傳視頻供其他用戶分享時(shí)，又是一個(gè)“生產(chǎn)者”。傳統(tǒng)的短視頻采用客戶/服務(wù)器(C/S)方式向用戶提供視頻。C/S的優(yōu)點(diǎn)是用戶的點(diǎn)播響應(yīng)快，但是，當(dāng)用戶規(guī)模較大時(shí)，不僅增加了緩存時(shí)間，更增加了服務(wù)器帶寬壓力，直接影響了點(diǎn)播用戶的QoE。

隨著網(wǎng)絡(luò)規(guī)模的不斷擴(kuò)張，使得P2P共享系統(tǒng)得到廣泛的應(yīng)用和可持續(xù)的發(fā)展［1］。P2P系統(tǒng)用戶在分享其他用戶節(jié)點(diǎn)視頻流的同時(shí)，也貢獻(xiàn)自己的帶寬給其他用戶節(jié)點(diǎn)。已有的視頻直播系統(tǒng) Coolstreaming［2］和點(diǎn)播系統(tǒng) PPS、PPLive［3］等都是采用P2P方式實(shí)現(xiàn)。這類系統(tǒng)具備良好的可擴(kuò)展性能，與傳統(tǒng)的C/S系統(tǒng)相比，其服務(wù)器帶寬消耗有所降低［3］。因此，本文構(gòu)建的SShare系統(tǒng)也引入P2P思想。

文獻(xiàn)［4］通過tracking方式對(duì)YouTube進(jìn)行研究，提出了一種“視頻服務(wù)器+P2P”的在線視頻分享系統(tǒng)NetTube。仿真實(shí)驗(yàn)表明，引入P2P技術(shù)后可以降低服務(wù)器帶寬消耗約70%。本文通過把用戶的點(diǎn)播相似度和短視頻之間具有的社會(huì)特性相結(jié)合，提出一種基于P2P的在線短視頻分享系統(tǒng)——SShare。

1 SShare重疊網(wǎng)的構(gòu)建

文獻(xiàn)［5－6］分別基于小世界網(wǎng)絡(luò)和興趣來構(gòu)建視頻之間的單層overlay，而SShare是多層overlay。SShare重疊網(wǎng)是將視頻之間的社會(huì)特性和點(diǎn)播相似性相結(jié)合的一個(gè)重疊網(wǎng)。SShare中每一個(gè)用戶節(jié)點(diǎn)同時(shí)屬于基于社會(huì)特性網(wǎng)(social based overlay)和基于點(diǎn)播相似度網(wǎng)(similarity based overlay)，整個(gè)結(jié)構(gòu)仍是一個(gè)Mesh結(jié)構(gòu)。

1.1 基于點(diǎn)播相似度及社會(huì)特性的重疊網(wǎng)

SShare的重疊網(wǎng)結(jié)構(gòu)把用戶的點(diǎn)播相似度和點(diǎn)播視頻之間形成的社會(huì)特性相結(jié)合，其目的是使點(diǎn)播用戶節(jié)點(diǎn)以更小的開銷查找到所有的視頻資源。圖1說明了一個(gè)用戶節(jié)點(diǎn)是如何加入這基于社會(huì)特性網(wǎng)和基于點(diǎn)播相似度網(wǎng)的。

NetTube研究結(jié)果表明，點(diǎn)播節(jié)點(diǎn)與點(diǎn)播視頻之間形成一種具備社會(huì)特性的網(wǎng)結(jié)構(gòu)。另外，根據(jù)點(diǎn)播節(jié)點(diǎn)的偏好，將視頻分為不同的簇。如圖1所示，就有T1簇、T2簇和T3簇等。當(dāng)點(diǎn)播節(jié)點(diǎn)P1新加入系統(tǒng)，由P9和P3向其提供視頻V1，又由于P2和P5向節(jié)點(diǎn)P3提供了視頻V2，則當(dāng)P1點(diǎn)播視頻V2時(shí)，P2和P5有更大的概率向P1提供視頻V2，這樣 P1、P2、P3、P5和 P9就構(gòu)建了基于社會(huì)特性網(wǎng)的結(jié)構(gòu)。

視頻網(wǎng)站往往將視頻分成不同的類，如體育類、新聞?lì)惡蛙娛骂惖?。不同的點(diǎn)播節(jié)點(diǎn)(也就是點(diǎn)播用戶)會(huì)喜歡不同類別的視頻。假如當(dāng)前點(diǎn)播是體育類，而將要點(diǎn)播的下一個(gè)視頻可能就是新聞?lì)悺Ｈ鐖D1所示，當(dāng)點(diǎn)播節(jié)點(diǎn)P1點(diǎn)播視頻V4時(shí)，T3簇的P4有更大的概率向其提供視頻V4;同理，T2簇中的P7有更大概率緩存了P1所需求的視頻V7，這樣P1、P4和P7就構(gòu)成了基于點(diǎn)播相似性的網(wǎng)結(jié)構(gòu)。P1這種不斷點(diǎn)播不同類視頻的結(jié)構(gòu)，既屬于社會(huì)特性網(wǎng)結(jié)構(gòu)，也屬于點(diǎn)播相似性特性網(wǎng)結(jié)構(gòu)。隨著新節(jié)點(diǎn)的不斷加入及它們點(diǎn)播不同類的視頻，便構(gòu)成了SShare的重疊網(wǎng)。

圖1 SShare重疊網(wǎng)結(jié)構(gòu)

2 基于P2P的在線短視頻分享策略

2.1 UGC網(wǎng)站視頻特性及點(diǎn)播相似度

由于UGC視頻分享網(wǎng)站將視頻進(jìn)行整理分類，當(dāng)用戶點(diǎn)播某一視頻時(shí)，網(wǎng)站會(huì)自動(dòng)提供相關(guān)的視頻供用戶選擇播放，即以相關(guān)視頻列表(relation vide list)列舉出。在UGC視頻網(wǎng)站中，在同一時(shí)間點(diǎn)播同一視頻的用戶較少，即使在Flash Crowd情況下大約也只有5個(gè)用戶［7］。有些用戶雖然不再點(diǎn)播視頻了，但其內(nèi)存中仍保留有點(diǎn)播過的視頻，這樣利用點(diǎn)播用戶的空閑帶寬仍可以上傳視頻，以供其他用戶分享。像PPVA［8］、百度視頻、優(yōu)酷、飛速土豆等都是采用這種 P2P加速的。

依據(jù)以上方式，對(duì)用戶點(diǎn)播視頻文件的特點(diǎn)進(jìn)行分析。用戶點(diǎn)播視頻時(shí)是按類進(jìn)行的，且每類視頻中又有多個(gè)不同的視頻。假設(shè)視頻節(jié)目分為n類，每類又分為m個(gè)視頻，則每個(gè)用戶節(jié)點(diǎn)(如節(jié)點(diǎn)i)包含1個(gè)點(diǎn)播向量:

其中:1≤i≤n;1≤mj≤m(1≤j≤n);wi，Tmj表示第 i類中的mj視頻。若wi，Tmj=1表示節(jié)點(diǎn)i已點(diǎn)播過該視頻，wi，Tmj=0表示未點(diǎn)播過該視頻。

當(dāng)節(jié)點(diǎn)i訪問SShare的跟蹤服務(wù)器時(shí)，跟蹤服務(wù)器會(huì)通過對(duì)比i節(jié)點(diǎn)與其他各節(jié)點(diǎn)的點(diǎn)播相似度，并將與節(jié)點(diǎn)i的點(diǎn)播相似度最近似的節(jié)點(diǎn)返回給節(jié)點(diǎn)i，作為節(jié)點(diǎn)i的候選鄰居節(jié)點(diǎn)向節(jié)點(diǎn)i提供所需要的視頻資源。通過euclidean distance或consine distance來計(jì)算兩向量之間的距離能產(chǎn)生比較理想的分簇效果［9］。依據(jù)本文對(duì)點(diǎn)播向量的表示方法計(jì)算點(diǎn)播節(jié)點(diǎn)之間的點(diǎn)播相似度，這里采用consine distance方法。例如節(jié)點(diǎn)i和節(jié)點(diǎn)j的點(diǎn)播向量分別記為:

則計(jì)算節(jié)點(diǎn)i和節(jié)點(diǎn)j的點(diǎn)播相似度為

其中:

di，j越小表示二者的點(diǎn)播相似度越接近。

2.2 資源查找策略

本文已討論了在UGC視頻系統(tǒng)中引入P2P技術(shù)，當(dāng)用戶點(diǎn)播視頻后，可以利用自己的空閑帶寬上傳自己已點(diǎn)播的視頻資源，供其他點(diǎn)播用戶分享，以減少服務(wù)器帶寬的消耗。而同一時(shí)間觀看同一視頻的用戶最多大約只有5個(gè)，所以，對(duì)于UGC視頻，有一個(gè)高效的查找策略很重要。筆者認(rèn)為UGC視頻查找策略有以下幾個(gè)難點(diǎn):①視頻應(yīng)用有較強(qiáng)的時(shí)間緊迫性，這一特點(diǎn)使得用戶要在較短的時(shí)間內(nèi)查找到所需要的視頻資源;② 視頻資源的查找范圍太小，不能有效查找到視頻資源，若查找范圍太大，則必定增大視頻資源的查找開銷，因此，在查找開銷和查找到資源的個(gè)數(shù)之間要有一個(gè)權(quán)衡［10］;③當(dāng)在一定查找范圍內(nèi)仍未能查找到所需視頻資源時(shí)，應(yīng)及時(shí)向服務(wù)器請(qǐng)求資源，以保證點(diǎn)播用戶的點(diǎn)播感受度QoE。

2.3 資源查找策略描述

SShare重疊網(wǎng)是建立在基于社會(huì)特性和點(diǎn)播相似度基礎(chǔ)之上的一種重疊網(wǎng)。在UGC視頻網(wǎng)站中，網(wǎng)站將視頻進(jìn)行整理歸類。當(dāng)點(diǎn)播節(jié)點(diǎn)點(diǎn)播某一視頻時(shí)，網(wǎng)站會(huì)將同類視頻以相關(guān)視頻列表的形式列出，供用戶選擇。因此，將SShare系統(tǒng)中點(diǎn)播行為分為2類:一類是有關(guān)聯(lián)關(guān)系的相關(guān)行為，即從相關(guān)列表中選擇視頻做為下一個(gè)將要點(diǎn)播的視頻;另一類是沒有關(guān)聯(lián)關(guān)系的無關(guān)行為，即點(diǎn)播節(jié)點(diǎn)將點(diǎn)播的下一個(gè)視頻不在關(guān)聯(lián)列表中，比如:當(dāng)前點(diǎn)播的是T類視頻，而下一個(gè)將要點(diǎn)播的視頻是非T類的。SShare系統(tǒng)中所有點(diǎn)播行為均屬于這2種之一。

SShare的查找策略是一種具有視頻關(guān)聯(lián)關(guān)系的查找策略。UGC視頻系統(tǒng)中視頻文件之間存在的社會(huì)網(wǎng)絡(luò)特性使得用戶的點(diǎn)播行為也呈現(xiàn)一定的關(guān)聯(lián)關(guān)系，即點(diǎn)播用戶往往會(huì)從那些和當(dāng)前播放的視頻存在一定關(guān)聯(lián)關(guān)系的列表中選擇下一個(gè)將要點(diǎn)播的視頻［4］。SShare主要利用這一特性，有偏向地發(fā)送查找請(qǐng)求給那些和查找視頻具有點(diǎn)播關(guān)聯(lián)關(guān)系的節(jié)點(diǎn)，而不是像NetTube那樣采用簡(jiǎn)單的Flooding查找方法。文獻(xiàn)［12］中采用Random Walker，減少了查詢開銷，但增加了查詢跳數(shù)。文獻(xiàn)［13］中采用 K_Radnom Walker，與前2種方法相比，不僅減少了查詢開銷，也減少了查詢跳數(shù)，使得查找開銷和查找范圍得到的平衡。本文也采用K_Random walker查詢方法。這種有偏向的查詢方法能顯著地提高查找命中率(hit ratio)。

基于點(diǎn)播視頻之間社會(huì)特性，SShare中將點(diǎn)播用戶的鄰居節(jié)點(diǎn)也按視頻類進(jìn)行分類記錄。如點(diǎn)播節(jié)點(diǎn)P點(diǎn)播i類視頻時(shí)，與候選節(jié)點(diǎn)Vi1、Vi2、…、ViN等建立鄰居關(guān)系后，則將 Vi1、Vi2、…、ViN這些節(jié)點(diǎn)記錄在節(jié)點(diǎn)P的第i類鄰居列表中。當(dāng)節(jié)點(diǎn)P 即將點(diǎn)播i類視頻時(shí)，Vi1、Vi2、…、ViN這些鄰居節(jié)點(diǎn)比其他鄰居節(jié)點(diǎn)有更大概率緩存P所需要的視頻。在這N個(gè)鄰居節(jié)點(diǎn)中選擇n(n＜N)個(gè)節(jié)點(diǎn)Vi1、Vi2、…、Vin以及節(jié)點(diǎn) V 作為候選節(jié)點(diǎn)，向其發(fā)出資源請(qǐng)求，其中V是由跟蹤服務(wù)器提供的與節(jié)點(diǎn)P具有點(diǎn)播相似度最高的節(jié)點(diǎn)。若未能查找節(jié)點(diǎn)P所需視頻資源，則從 Vi1、Vi2、…、Vin以及節(jié)點(diǎn)V中選擇K個(gè)與P具有較高的點(diǎn)播相似度的節(jié)點(diǎn)作為下一跳的候選節(jié)點(diǎn)，向其發(fā)出資源請(qǐng)求。若仍未能查找到所需視頻資源，則應(yīng)及時(shí)向服務(wù)器發(fā)出請(qǐng)求。算法偽碼如下:

2.4 資源查找性能分析

假設(shè)系統(tǒng)中有 n個(gè)節(jié)點(diǎn){P1、P2、…、Pi、…、Pn}，其中 Sv={P1、P2、…、Pj、…、Pm}(m ＜ n)個(gè)用戶節(jié)點(diǎn)緩存有視頻V，則當(dāng)用戶節(jié)點(diǎn)i訪問任一鄰居節(jié)點(diǎn)緩存有視頻V的概率為

在資源查找過程中，可能需要多跳才能查找到所需要的視頻資源。從第l跳到第l+1跳依據(jù)社會(huì)特性進(jìn)行查找，查找到的概率為Pv。若按照點(diǎn)播相似度進(jìn)行查找時(shí)，第l+1跳的查找概率不僅和Pv相關(guān)，也和第l跳鄰居節(jié)點(diǎn)所緩存的與V相關(guān)聯(lián)的視頻個(gè)數(shù)有關(guān)。假設(shè)第l跳節(jié)點(diǎn)i緩存有λ個(gè)與V相關(guān)聯(lián)的視頻，第l+1跳節(jié)點(diǎn)j緩存有K個(gè)與V相關(guān)聯(lián)的視頻，則節(jié)點(diǎn)i從節(jié)點(diǎn)j查找到視頻V的概率為

其中 λi＜K，(i=1、2、…、θ)。可推出，節(jié)點(diǎn) i從這θ個(gè)節(jié)點(diǎn)中查找到視頻V的概率為

當(dāng)節(jié)點(diǎn)i向t個(gè)節(jié)點(diǎn)發(fā)送查找消息時(shí)，若采用社會(huì)特性隨機(jī)選擇θ個(gè)節(jié)點(diǎn)，查找成功的概率為

而

從式(6)可以看出，采用基于點(diǎn)播相似度關(guān)系進(jìn)行選擇節(jié)點(diǎn)進(jìn)行查找資源成功概率大于采用基于社會(huì)特性關(guān)系查找資源的成功概率。

3 仿真分析

對(duì)基于點(diǎn)播視頻之間的社會(huì)特性與基于點(diǎn)播相似度特性形結(jié)合的SShare系統(tǒng)的仿真結(jié)果如圖2～4所示。

由圖2可以看出，無論采用基于社會(huì)特性還是采用基于點(diǎn)播相似度方法，對(duì)服務(wù)器帶寬消耗均小于C/S方法。當(dāng)仿真進(jìn)行到4 h后，采用點(diǎn)播相似度方法就優(yōu)于采用社會(huì)特性的方法和C/S方法，明顯降低了對(duì)服務(wù)器帶寬的消耗。

圖3是對(duì)系統(tǒng)加入2 000個(gè)節(jié)點(diǎn)的過程中查詢包的統(tǒng)計(jì)對(duì)比結(jié)果，即基于社會(huì)特性和點(diǎn)播相似度2種方法的查詢包對(duì)比。由圖3可以看出，當(dāng)系統(tǒng)點(diǎn)播節(jié)點(diǎn)小于1 200時(shí)，二者查詢包相差很小。雖然，當(dāng)系統(tǒng)點(diǎn)播節(jié)點(diǎn)大于1 200之后，基于點(diǎn)播相似度方法查詢包明顯增加，但是降低了服務(wù)器帶寬消耗，這些開銷還是值得的。

圖4顯示了在系統(tǒng)中加入2 000節(jié)點(diǎn)的過程中，采用基于社會(huì)特性和點(diǎn)播相似度2種方法查詢失敗次數(shù)的對(duì)比情況。當(dāng)系統(tǒng)點(diǎn)播節(jié)點(diǎn)小于1 500個(gè)時(shí)，基于社會(huì)特性的查詢成功次數(shù)遠(yuǎn)高于基于點(diǎn)播相似度查詢成功次數(shù);當(dāng)系統(tǒng)點(diǎn)播節(jié)點(diǎn)超過1 500個(gè)后，基于點(diǎn)播相似度方法的查詢成功次數(shù)遠(yuǎn)高于基于社會(huì)特性查詢成功次數(shù)。所以說，當(dāng)系統(tǒng)規(guī)模越大時(shí)，采用點(diǎn)播相似度查詢方法能獲得更高的查詢成功率。

在NetTube中利用點(diǎn)播視頻之間的社會(huì)特性，使服務(wù)器帶寬消耗降低了70%。通過對(duì)圖2～4的分析可知，本文構(gòu)建的SShare系統(tǒng)與采用基于社會(huì)特性的方法和傳統(tǒng)的C/S方法相比，隨著系統(tǒng)規(guī)模的不斷增加，能明顯降低服務(wù)器帶寬消耗，而且查詢成功率還遠(yuǎn)高于采用基于社會(huì)特性方法的查詢成功率。

圖2 服務(wù)器帶寬消耗對(duì)比

圖3 資源查詢包對(duì)比

圖4 訪問失效次數(shù)對(duì)比

4 結(jié)束語(yǔ)

本文設(shè)計(jì)的SShare系統(tǒng)，通過組建基于社會(huì)特性和點(diǎn)播相似度的重疊網(wǎng)，可以有偏向地對(duì)資源進(jìn)行查找。仿真實(shí)驗(yàn)表明，SShare系統(tǒng)能明顯降低服務(wù)器帶寬的消耗，而且也有效降低了查詢失敗次數(shù)。在SShare系統(tǒng)中，對(duì)內(nèi)存管理方面還需要進(jìn)一步研究。

［1］王淑玲.P2P資源共享系統(tǒng)中的資源定位研究［D］.合肥:中國(guó)科學(xué)技術(shù)大學(xué)，2012.

［2］Zhang X，Liu J，Li B，et al.Cool Streaming/DONet:A Data-Driven Overlay Network for Peer-to-Peer Live Media Streaming［Z］.［S.l.］:IEEE，2005.

［3］Xu K，Li H，Liu J.PPVA:A Universal and Transparent Peer-to-Peer Accelerator for Interactive Online Video Sharing［Z］.［S.l.］:IEEE，2010.

［4］Cheng X，Liu J.NetTube:Exploring social networks for peer-to-peershortvideo sharing ［Z］.［S.l.］:IEEE，2009.

［5］Hao Liao，Kuo-Chan Huang，Hung-Chang Hsiao.Small-World Social Relationship Awareness in Unstructured Peer-to-Peer Networks［Z］.［S.l.］:IEEE，2010.

［6］Kunwadee，Sripanidkulchai，Bruce Maggs.Efficient Content Location Using Interest-Based，Locality in Peer-to-Peer Systems［Z］.［S.l.］:IEEE，2003.

［7］Pawel Garbacki，Dick Epema，Johan Pouwelse，et al.Offloading Servers with Collaborative Video on Demand［C］//Proceeding of the 7th International Workshop on Peer-to-Peer Systems(IPTPS＇08).［S.l.］:IEEE，2008.

［8］Xu K，Li H，Liu J.PPVA:A Universal and Transparent Peer-to-Peer Accelerator for Interactive Online Video Sharing［Z］.［S.l.］:IEEE，2010.

［9］Sean Owen，Robin Anil，Ted Dunning.Mahout in action［M］.［S.l.］:Manning Publications，2010.

［10］Xueyan Tang，JianliangXu，Wang-Chien Lee.Analysis of TTL-Based Consistency in Unstructured Peer-to-Peer Networks［Z］.［S.l.］:IEEE，2008:1683 －1694.

［11］Ming Zhong，Kai Shen，Joel Seiferas.The Convergence-Guaranteed Random Walk and Its Applications in Peerto-Peer Networks［Z］.［S.l.］:IEEE，2008.

［12］Ming Zhong，Kai Shen.PopularityBiased Random Walks for PeertoPeer Search under the Square Root Principle［Z］.

［13］A Biased k-Random Walk to Find Useful Files in Unstructed P2P Networks，International Conference on Parallel and Distributed Computing，Applications and Technologies［Z］.2009.