0 引言

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

1 流媒體復制算法

1.1 流媒體副本建立算法

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

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

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

    當節點調度策略滿足順序性和貪婪性時，赤字帶寬^[4]如式（6）所示：

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

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

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

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

1.1.3 流媒體文件流行度定義

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

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

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

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

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

1.2 流媒體副本更新算法

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

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

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

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

2 實驗結果及分析

2.1 實驗參數

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

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

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

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

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

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

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

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

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

2.2 實驗結果以及分析

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

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

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

3 結論

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

參考文獻

[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，FU 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.北京大學深圳研究生院 深圳物聯網智能感知技術工程實驗室，廣東 深圳518055)