《電子技術(shù)應(yīng)用》
您所在的位置：首頁 > 通信與網(wǎng)絡(luò) > 設(shè)計應(yīng)用 > 基于流行度的P2P流媒體復(fù)制算法
基于流行度的P2P流媒體復(fù)制算法
2018年電子技術(shù)應(yīng)用第10期
楊 戈1，2，高 兵1，2，黃 靜1，賀 輝1
1.北京師范大學(xué)珠海分校 信息技術(shù)學(xué)院，廣東 珠海519087； 2.北京大學(xué)深圳研究生院 深圳物聯(lián)網(wǎng)智能感知技術(shù)工程實驗室，廣東 深圳518055
摘要： 通過把赤字帶寬引入到流媒體文件流行度中，定義了一種新的流媒體文件的流行度, 以該流行度為依據(jù)，確定需要復(fù)制的流媒體文件，將節(jié)點按綜合性能指標(biāo)進行排序，把副本放置在綜合性能高的節(jié)點上。在副本放置空間不足時需要進行副本替換，替換掉副本實際數(shù)量與期望數(shù)量之比中比值最大的文件，以復(fù)制新的文件。實驗表明，和比例復(fù)制算法相比，本算法的工作負(fù)載更早進入穩(wěn)態(tài)，平均提前了總仿真時間的13%。穩(wěn)態(tài)時，工作負(fù)載更小, 工作負(fù)載是比例復(fù)制算法的33.3% ；達到流媒體文件請求速率的節(jié)點數(shù)量比比例復(fù)制算法的節(jié)點數(shù)量平均多1‰左右；同時在暫態(tài)時，本算法的波動更加平穩(wěn)。
中圖分類號： TN919.85；TP393
文獻標(biāo)識碼： A
DOI：10.16157/j.issn.0258-7998.180559
中文引用格式： 楊戈，高兵，黃靜，等. 基于流行度的P2P流媒體復(fù)制算法[J].電子技術(shù)應(yīng)用，2018，44(10)：122-126.
英文引用格式： Yang Ge，Gao Bing，Huang Jing，et al. A replica algorithm based on popularity for P2P streaming media[J]. Application of Electronic Technique，2018，44(10)：122-126.
A replica algorithm based on popularity for P2P streaming media
Yang Ge1，2，Gao Bing1，2，Huang Jing1，He Hui1
1.College of Information Technology，Beijing Normal University(Zhuhai Campus)，Zhuhai 519087，China； 2.Engineering Lab on Intelligent Perception for Internet of Things(ELIP)，Shenzhen Graduate School， Peking University，Shenzhen 518055，China
Abstract： In this paper，a new formula of popularity was proposed. It included the term deficit bandwidth and was based on the new popularity. Those streaming media files which need to be replicated were determined. A concept named comprehensive performance indicators was proposed. Peers were sorted by their comprehensive performance indicators and those peers with high comprehensive performance indicators had priority to place these popular files. Replacement algorithm would be carried out if there was no enough space to cache the new file, and the file which had largest ratio of its duplicates to the desired duplicates would be replaced by the new file. Experimental results show that the workload of the proposed algorithm, compared with proportional replication algorithm, is in steady conditions earlier about 13% in advance and is smaller. Its workload in steady-state condition is about 33.3% of the workload of the proportional replication algorithm. Meanwhile, more of one in a thousand peers has the desired requested rates in steady-state. Besides, the proposed algorithm has more stationary transient process.
Key words : P2P network；deficit bandwidth；popularity；replication algorithm；replacement algorithm

0 引言

    P2P網(wǎng)絡(luò)的動態(tài)性和異構(gòu)性是影響流媒體的應(yīng)用實施的兩個重要因素[1]。文獻[2]研究了一個分布式副本近似放置算法，給定流媒體文件的請求速率和存儲容量，在請求節(jié)點的最鄰近位置放置副本，從而達到最大化縮短訪問時間的目的。文獻[3]研究最佳復(fù)制算法的要求：內(nèi)容放置在不同節(jié)點，滿足存儲和約束條件，期望有最小的服務(wù)負(fù)載和均衡的帶寬。文獻[4]研究指出在P2P點播系統(tǒng)中，上傳速率和流媒體文件流行度都是影響復(fù)制策略的因素。

1 流媒體復(fù)制算法

1.1 流媒體副本建立算法

    對于流媒體文件x而言，正在觀看流媒體文件y (x≠y)的當(dāng)前節(jié)點和緩存流媒體文件y(x≠y)的復(fù)制節(jié)點統(tǒng)稱為流媒體文件x的活躍節(jié)點。而服務(wù)節(jié)點是存儲源流媒體文件的節(jié)點，不能從別的節(jié)點那里下載數(shù)據(jù)。本文假設(shè)所有流媒體文件的觀看順序都是從頭到尾的[4]。

1.1.1 流媒體文件k的期望的赤字帶寬Dk(nk)

tx4-gs1-5.gif

    式(5)就是當(dāng)前節(jié)點的赤字帶寬和服務(wù)節(jié)點的上傳帶寬消耗之間的關(guān)系。根據(jù)這個關(guān)系，本文的目的就是找到一個復(fù)制算法確定Rk，使得U最小。

    當(dāng)節(jié)點調(diào)度策略滿足順序性和貪婪性時，赤字帶寬[4]如式（6）所示：

    tx4-gs6.gif

tx4-gs7.gif

1.1.2 流媒體文件i期望的存儲空間

    流媒體文件i期望的存儲空間[4]為：

tx4-gs8.gif

其中，E(Di(ni)表示流媒體文件i的期望的赤字帶寬，l(s)為流媒體文件的播放時間長度。

    每個流媒體文件i的期望的赤字帶寬乘以每個流媒體文件i的時間長度，就可以得到每個流媒體文件i的大小，再把所有將要流行的流媒體文件的大小求和，即為將要流行流媒體文件總期望的存儲空間大小。

1.1.3 流媒體文件流行度定義

    本文定義的流媒體文件的流行度為式(9)：

tx4-gs9.gif

    先計算流媒體文件的流行度，按照從大到小順序進行排列，選擇流行度高的前B%的流媒體看作是將要流行的流媒體，即選擇將要流行的流媒體文件i，對它們進行復(fù)制。其中B是正整數(shù)，B在0～100范圍內(nèi)。

1.1.4 綜合性能比較高的非服務(wù)節(jié)點的選擇標(biāo)準(zhǔn)

    綜合性能比較高的非服務(wù)節(jié)點的選擇標(biāo)準(zhǔn)：在最大上傳速率、最大下載速率、存儲容量以及當(dāng)前節(jié)點與除當(dāng)前節(jié)點外的非服務(wù)節(jié)點之間的跳數(shù)這4個指標(biāo)之間找到一個合適的比例。首先，要計算P2P流媒體系統(tǒng)中節(jié)點的存儲容量值，并進行歸一化處理；其次，計算該節(jié)點的最大上傳速率、最大下載速率，并進行歸一化處理；再次，計算當(dāng)前節(jié)點與系統(tǒng)中除當(dāng)前節(jié)點外的非服務(wù)節(jié)點之間的跳數(shù)，并進行歸一化處理；最后，將該節(jié)點的存儲容量、最大上傳速率、最大下載速率以及當(dāng)前節(jié)點與除當(dāng)前節(jié)點外的非服務(wù)節(jié)點之間的跳數(shù)進行加權(quán)求和，得到該節(jié)點的綜合性能指標(biāo)值，根據(jù)節(jié)點的綜合性能指標(biāo)值選取出所要的候選節(jié)點。根據(jù)其比重的不同，可以使本算法具有較好的健壯性。定義節(jié)點的綜合性能指標(biāo)為：

tx4-gs10.gif

    W的值越大說明節(jié)點的綜合性能越好，如果W出現(xiàn)負(fù)值，說明這樣的節(jié)點是個單純的消耗節(jié)點，不能提供很好的上傳服務(wù)，因而不利于作為復(fù)制候選節(jié)點。如果所有節(jié)點的綜合性能指標(biāo)都是負(fù)值，就放棄此次排序，再更新綜合性能指標(biāo)中的各個權(quán)值，重新計算綜合性能指標(biāo)，如果得到的綜合性能指標(biāo)是非負(fù)數(shù)，則進行排序，選取綜合性能指標(biāo)高的前n個節(jié)點，這里n為流媒體文件需要存放的副本數(shù)量。否則放棄排序，以此類推。對前n個節(jié)點，判斷其可利用的存儲空間是否可以放置整個該流媒體文件。如果可以放下，更新流媒體文件需要存放的個數(shù)以及相應(yīng)的活躍節(jié)點的剩余的可利用存儲空間。否則，更新綜合性能指標(biāo)公式中的權(quán)值系數(shù)：最大上傳速率的權(quán)值tx4-t2-x1.gif每次減少0.05，節(jié)點最大下載速率的權(quán)值β每次減少0.05，節(jié)點存儲空間的權(quán)值η每次增加0.2，當(dāng)前節(jié)點與系統(tǒng)中除當(dāng)前節(jié)點外非服務(wù)節(jié)點之間的跳數(shù)的權(quán)值ξ每次減少0.1。直到權(quán)值系數(shù)到達到設(shè)定閾值或者需要存放流媒體文件個數(shù)都已經(jīng)緩存到節(jié)點中，結(jié)束本次復(fù)制。

1.2 流媒體副本更新算法

    當(dāng)一個節(jié)點請求觀看一個新的流媒體文件時，先檢查這個流媒體文件是否存在于本地節(jié)點的緩存中，如果存在就不做替換，如果沒在本地緩存中存儲，則計算存在緩存中的每個流媒體文件的期望的副本個數(shù)，然后再計算存在緩存中的每個流媒體文件的當(dāng)前副本個數(shù)，得出當(dāng)前副本個數(shù)與期望的副本個數(shù)之比，此比值稱為滿意度指標(biāo)SIi。替換滿意度指標(biāo)SIi值最大的流媒體文件，這就是替換算法。這個算法的主要思想就是保持副本與赤字帶寬合理的比例，因為赤字帶寬之比接近最優(yōu)復(fù)制比例[4]。當(dāng)SIi大于1時，表示當(dāng)前時刻該流媒體文件的副本個數(shù)多于期望的副本個數(shù)；若SIi小于1，表示當(dāng)前時刻該流媒體文件的副本個數(shù)低于期望的副本個數(shù)；SIi等于1，表示當(dāng)前時刻該流媒體文件的副本個數(shù)和期望的副本個數(shù)相符合。因此，在本算法的每一次循環(huán)中，就要從本地緩存的流媒體文件中替換掉SIi值最大的流媒體文件。計算已存在于當(dāng)前節(jié)點緩存中的每個流媒體文件的期望的副本個數(shù)tx4-gs11-s1.gif如式(11)所示：

tx4-gs11-12.gif

    流媒體副本更新算法描述：

    (1)當(dāng)節(jié)點請求流媒體文件時，首先判斷節(jié)點的緩存空間中是否存放有該流媒體文件。如果有，則直接觀看該流媒體文件；如果沒有，就判斷該節(jié)點的緩存空間是否可以放下整個流媒體文件。如果能放下，直接從其他節(jié)點處請求數(shù)據(jù)；如果放不下，就需要調(diào)用流媒體替換算法，見步驟(2)。

    (2)對各個流媒體文件的滿意度指標(biāo)進行從大到小排序。將本地緩存中滿意度指標(biāo)最大的流媒體文件替換掉。此時本地緩存釋放出空間，以放置待請求的流媒體文件。

2 實驗結(jié)果及分析

2.1 實驗參數(shù)

    利用MATLAB R2012搭建仿真平臺，參數(shù)設(shè)置如下：

    (1)假設(shè)路由器包含的非服務(wù)節(jié)點和服務(wù)節(jié)點為peerset=[10，1；20，2；10，2；15，3；10，1]，其中每一行代表一個路由器覆蓋的非服務(wù)節(jié)點數(shù)和服務(wù)節(jié)點數(shù)。服務(wù)節(jié)點個數(shù)為9個，非服務(wù)節(jié)點個數(shù)為65個。

    (2)假設(shè)系統(tǒng)共有20個流媒體文件，每個流媒體文件時長均為90 min，播放速率R=500 kb/s。

    (3)節(jié)點的請求速率[5]。為了流媒體文件能流暢播放，請求節(jié)點從其他節(jié)點處期望獲得的請求速率r′等于流媒體文件的播放速率R，因此r′=500 kb/s。

    (4)每個節(jié)點（包括服務(wù)節(jié)點和非服務(wù)節(jié)點）緩存的流媒體文件數(shù)和可利用存儲空間。通過在[0，1]區(qū)間上服從均勻分布的隨機數(shù)rand命令，確定初始時刻各個服務(wù)節(jié)點上存儲了哪些流媒體文件。具體地，對每個流媒體文件，利用rand命令生成一個隨機數(shù)。規(guī)定如果rand<0.8，不存儲該流媒體文件；否則，存儲該流媒體文件。原因就是服務(wù)節(jié)點上只是隨機地存儲了部分的流媒體文件。初始時刻非服務(wù)節(jié)點沒有緩存任何流媒體文件，且非服務(wù)節(jié)點的可利用存儲空間為600 MB～700 MB，其大小在[600 MB，700 MB]上服從均勻分布[4]。

    (5)本實驗通過不同的非服務(wù)節(jié)點和服務(wù)節(jié)點的最大上傳速率分布情況[4]，來比較本文提出的復(fù)制算法和比例復(fù)制算法的性能。數(shù)據(jù)分別如表1、表2所示。仿真兩種算法復(fù)制流行度高的前20%的流媒體文件，即B=20。

tx4-b1.gif

tx4-b2.gif

    (6)每次迭代對應(yīng)的實際時間長度和迭代步數(shù)[4]。假設(shè)一次迭代對應(yīng)3 h，總步數(shù)為15次迭代。

    (7)流媒體文件的流行度和期望赤字帶寬。初始時刻，各流媒體文件的流行度相同，因此，將初始時刻各流媒體文件的流行度賦值為零。由于流媒體文件的期望赤字帶寬與訪問它的用戶數(shù)量有關(guān)，初始時刻還沒有請求節(jié)點觀看流媒體文件，因此將初始時刻各流媒體文件的期望赤字帶寬賦值為零。

    (8)綜合性能指標(biāo)公式中權(quán)值的選取。綜合性能指標(biāo)公式中，初始權(quán)值取0.1、0.2、0.5、0.2，后續(xù)進行復(fù)制算法執(zhí)行時，如果按照此權(quán)值得到的綜合性能指標(biāo)高的節(jié)點仍然不能完成復(fù)制算法，就更新權(quán)值。更新規(guī)律為：節(jié)點最大上傳速率的權(quán)值tx4-t2-x1.gif每次減少0.05，節(jié)點最大下載速率的權(quán)值β每次減少0.05，節(jié)點存儲空間的權(quán)值η每次增加0.2，當(dāng)前節(jié)與P2P網(wǎng)絡(luò)中除當(dāng)前節(jié)點外的非服務(wù)節(jié)點之間的跳數(shù)的權(quán)值ξ每次減少0.1，直到能放下為止，如果更新5次還放不下，就跳出循環(huán)，5次是更新的次數(shù)閾值，是預(yù)先設(shè)定好的。

2.2 實驗結(jié)果以及分析

    服務(wù)節(jié)點的工作負(fù)載：指的是每次迭代過程中，當(dāng)請求節(jié)點從當(dāng)前節(jié)點和復(fù)制節(jié)點處請求得到的速率不能滿足流暢播放的期望速率時，需要從所有的服務(wù)節(jié)點獲得的總的速率，單位為Mb/s。滿意節(jié)點的比例：所謂滿意節(jié)點，指的是請求節(jié)點從其他節(jié)點處請求到的速率等于流暢播放的期望速率。滿意節(jié)點的比例指的是滿意節(jié)點占所有請求節(jié)點總數(shù)的比例。

    實驗仿真結(jié)果如圖1、圖2所示，本組實驗（B=20，非服務(wù)節(jié)點和服務(wù)節(jié)點的上傳速率服從表1、表2分布）結(jié)果表明，采用本文提出的流媒體復(fù)制算法，服務(wù)節(jié)點的工作負(fù)載在第4次迭代時降低到0.1 Mb/s，明顯低于比例復(fù)制算法，滿意節(jié)點的比例從第3次迭代開始，較比例復(fù)制算法高約1‰。而且在大約6次迭代后，兩種算法服務(wù)節(jié)點的工作負(fù)載和滿意節(jié)點的比例變得差別不大，但是，本文提出的流媒體復(fù)制算法無論在服務(wù)節(jié)點的工作負(fù)載還是在滿意節(jié)點的比例上都比比例復(fù)制算法[5]好。

tx4-t1.gif

tx4-t2.gif

    算法開始迭代時，因為本文提出的算法本身就是通過期望的副本數(shù)和實際副本數(shù)的不斷逼近來確定副本數(shù)目的，所以到達穩(wěn)態(tài)需要一個過程，因此初始幾個迭代過程中，本文的復(fù)制算法可能沒有比例復(fù)制算法好，服務(wù)節(jié)點的工作負(fù)載也可能會高于比例復(fù)制算法的服務(wù)節(jié)點的工作負(fù)載。這是因為一個流媒體文件剛開始流行時，流行度會急劇增長，比例復(fù)制算法按照此流媒體文件的流行度占所有的流媒體文件的流行度總和的比例進行復(fù)制，隨著迭代次數(shù)的增多，本文提出的流媒體復(fù)制算法就有了明顯的優(yōu)勢，更早進入穩(wěn)態(tài)。其中穩(wěn)態(tài)是指系統(tǒng)的狀態(tài)變化很小，在仿真結(jié)果上就是曲線始終保持小幅變化。穩(wěn)態(tài)時，工作負(fù)載更小, 工作負(fù)載平均是比例復(fù)制算法的33.3%；達到流媒體文件請求速率的節(jié)點數(shù)量較比例復(fù)制算法的節(jié)點數(shù)量平均多1‰左右。

3 結(jié)論

    本文提出了基于P2P網(wǎng)絡(luò)的流媒體副本建立算法和副本更新算法。通過實際副本數(shù)與期望副本數(shù)的不斷逼近來實現(xiàn)網(wǎng)絡(luò)中副本數(shù)量的最佳，按照最佳復(fù)制比例來復(fù)制副本，不僅可以避免網(wǎng)絡(luò)赤字帶寬瓶頸，提高系統(tǒng)性能，還可以防止網(wǎng)絡(luò)中的副本數(shù)量過多，造成副本冗余。如何有效地在動態(tài)加入或離開的節(jié)點上復(fù)制流媒體文件，是下一步需要考慮的一個問題。

參考文獻

[1] Zhao Can，Lin Xiaojun，Wu Chuan.The streaming capacity of sparsely connected P2P systems with distributed control[J].IEEE/ACM Transactions on Networking，2016，24(1)：58-71.

[2] ZAMAN S，GROSU D.A distributed algorithm for the replica placement problem[J].IEEE Transactions on Parallel and Distributed Systems，2011，22(9)：1455-1468.

[3] ZHOU Y，F(xiàn)U T Z J，CHIU D M.A unifying model and analysis of P2P VoD replication and scheduling[C].IEEE INFOCOM 2012，Orlando，USA，2012.

[4] Wu Weijie，RICHARD T B M，JOHN C S L.Distributed caching via rewarding: an incentive scheme design in P2P-VoD systems[J].IEEE Transactions on Parallel and Distributed Systems，2014，25(3)：612-621.

[5] TEWARI S，KLEINROCK L.Optimal search performance in unstructured peer-to-peer networks with clustered demands[J].IEEE Journal on Selected Areas in Communications，2007，25(1)：84-95.



作者信息:

楊  戈1，2，高  兵1，2，黃  靜1，賀  輝1

(1.北京師范大學(xué)珠海分校 信息技術(shù)學(xué)院，廣東 珠海519087；

2.北京大學(xué)深圳研究生院 深圳物聯(lián)網(wǎng)智能感知技術(shù)工程實驗室，廣東 深圳518055)

此內(nèi)容為AET網(wǎng)站原創(chuàng)，未經(jīng)授權(quán)禁止轉(zhuǎn)載。