《電子技術應用》
您所在的位置：首頁 > 通信與網(wǎng)絡 > 設計應用 > 基于流行度的P2P流媒體復制算法
基于流行度的P2P流媒體復制算法
2018年電子技術應用第10期
楊 戈1,，2,，高 兵1,，2,，黃 靜1，賀 輝1
1.北京師范大學珠海分校 信息技術學院,，廣東 珠海519087,； 2.北京大學深圳研究生院 深圳物聯(lián)網(wǎng)智能感知技術工程實驗室，廣東 深圳518055
摘要： 通過把赤字帶寬引入到流媒體文件流行度中,，定義了一種新的流媒體文件的流行度, 以該流行度為依據(jù),，確定需要復制的流媒體文件，將節(jié)點按綜合性能指標進行排序,，把副本放置在綜合性能高的節(jié)點上,。在副本放置空間不足時需要進行副本替換，替換掉副本實際數(shù)量與期望數(shù)量之比中比值最大的文件,，以復制新的文件,。實驗表明，和比例復制算法相比，本算法的工作負載更早進入穩(wěn)態(tài),，平均提前了總仿真時間的13%,。穩(wěn)態(tài)時,，工作負載更小, 工作負載是比例復制算法的33.3% ,；達到流媒體文件請求速率的節(jié)點數(shù)量比比例復制算法的節(jié)點數(shù)量平均多1‰左右；同時在暫態(tài)時,，本算法的波動更加平穩(wěn),。
中圖分類號： TN919.85；TP393
文獻標識碼： A
DOI：10.16157/j.issn.0258-7998.180559
中文引用格式： 楊戈,，高兵,，黃靜，等. 基于流行度的P2P流媒體復制算法[J].電子技術應用,，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)絡的動態(tài)性和異構性是影響流媒體的應用實施的兩個重要因素[1],。文獻[2]研究了一個分布式副本近似放置算法，給定流媒體文件的請求速率和存儲容量,，在請求節(jié)點的最鄰近位置放置副本,，從而達到最大化縮短訪問時間的目的,。文獻[3]研究最佳復制算法的要求：內(nèi)容放置在不同節(jié)點，滿足存儲和約束條件,，期望有最小的服務負載和均衡的帶寬,。文獻[4]研究指出在P2P點播系統(tǒng)中，上傳速率和流媒體文件流行度都是影響復制策略的因素,。

1 流媒體復制算法

1.1 流媒體副本建立算法

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

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

tx4-gs1-5.gif

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

    當節(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,，對它們進行復制,。其中B是正整數(shù)，B在0～100范圍內(nèi),。

1.1.4 綜合性能比較高的非服務節(jié)點的選擇標準

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

tx4-gs10.gif

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

1.2 流媒體副本更新算法

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

tx4-gs11-12.gif

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

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

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

2 實驗結果及分析

2.1 實驗參數(shù)

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

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

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

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

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

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

tx4-b1.gif

tx4-b2.gif

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

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

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

2.2 實驗結果以及分析

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

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

tx4-t1.gif

tx4-t2.gif

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

3 結論

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

參考文獻

[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.北京師范大學珠海分校 信息技術學院，廣東 珠海519087,；

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

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