0 引言

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

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

1.1 流媒體副本建立算法

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

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

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

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

1.1.2 流媒體文件i期望的存儲(chǔ)空間

    流媒體文件i期望的存儲(chǔ)空間^[4]為：

其中，E(D_i(n_i)表示流媒體文件i的期望的赤字帶寬，l(s)為流媒體文件的播放時(shí)間長(zhǎng)度。

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

1.1.3 流媒體文件流行度定義

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

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

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

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

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

1.2 流媒體副本更新算法

    當(dāng)一個(gè)節(jié)點(diǎn)請(qǐng)求觀看一個(gè)新的流媒體文件時(shí)，先檢查這個(gè)流媒體文件是否存在于本地節(jié)點(diǎn)的緩存中，如果存在就不做替換，如果沒(méi)在本地緩存中存儲(chǔ)，則計(jì)算存在緩存中的每個(gè)流媒體文件的期望的副本個(gè)數(shù)，然后再計(jì)算存在緩存中的每個(gè)流媒體文件的當(dāng)前副本個(gè)數(shù)，得出當(dāng)前副本個(gè)數(shù)與期望的副本個(gè)數(shù)之比，此比值稱(chēng)為滿(mǎn)意度指標(biāo)SI_i。替換滿(mǎn)意度指標(biāo)SI_i值最大的流媒體文件，這就是替換算法。這個(gè)算法的主要思想就是保持副本與赤字帶寬合理的比例，因?yàn)槌嘧謳捴冉咏顑?yōu)復(fù)制比例^[4]。當(dāng)SI_i大于1時(shí)，表示當(dāng)前時(shí)刻該流媒體文件的副本個(gè)數(shù)多于期望的副本個(gè)數(shù)；若SI_i小于1，表示當(dāng)前時(shí)刻該流媒體文件的副本個(gè)數(shù)低于期望的副本個(gè)數(shù)；SI_i等于1，表示當(dāng)前時(shí)刻該流媒體文件的副本個(gè)數(shù)和期望的副本個(gè)數(shù)相符合。因此，在本算法的每一次循環(huán)中，就要從本地緩存的流媒體文件中替換掉SI_i值最大的流媒體文件。計(jì)算已存在于當(dāng)前節(jié)點(diǎn)緩存中的每個(gè)流媒體文件的期望的副本個(gè)數(shù)如式(11)所示：

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

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

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

2 實(shí)驗(yàn)結(jié)果及分析

2.1 實(shí)驗(yàn)參數(shù)

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

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

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

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

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

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

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

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

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

2.2 實(shí)驗(yàn)結(jié)果以及分析

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

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

    算法開(kāi)始迭代時(shí)，因?yàn)楸疚奶岢龅乃惴ū旧砭褪峭ㄟ^(guò)期望的副本數(shù)和實(shí)際副本數(shù)的不斷逼近來(lái)確定副本數(shù)目的，所以到達(dá)穩(wěn)態(tài)需要一個(gè)過(guò)程，因此初始幾個(gè)迭代過(guò)程中，本文的復(fù)制算法可能沒(méi)有比例復(fù)制算法好，服務(wù)節(jié)點(diǎn)的工作負(fù)載也可能會(huì)高于比例復(fù)制算法的服務(wù)節(jié)點(diǎn)的工作負(fù)載。這是因?yàn)橐粋€(gè)流媒體文件剛開(kāi)始流行時(shí)，流行度會(huì)急劇增長(zhǎng)，比例復(fù)制算法按照此流媒體文件的流行度占所有的流媒體文件的流行度總和的比例進(jìn)行復(fù)制，隨著迭代次數(shù)的增多，本文提出的流媒體復(fù)制算法就有了明顯的優(yōu)勢(shì)，更早進(jìn)入穩(wěn)態(tài)。其中穩(wěn)態(tài)是指系統(tǒng)的狀態(tài)變化很小，在仿真結(jié)果上就是曲線(xiàn)始終保持小幅變化。穩(wěn)態(tài)時(shí)，工作負(fù)載更小, 工作負(fù)載平均是比例復(fù)制算法的33.3%；達(dá)到流媒體文件請(qǐng)求速率的節(jié)點(diǎn)數(shù)量較比例復(fù)制算法的節(jié)點(diǎn)數(shù)量平均多1‰左右。

3 結(jié)論

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

參考文獻(xiàn)

[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ù)工程實(shí)驗(yàn)室，廣東 深圳518055)