基于帶寬預測的流媒體超級節點選擇算法

魏　赟　韓少恒

(上海理工大學光電信息與計算機工程學院　上海 200093)

?

基于帶寬預測的流媒體超級節點選擇算法

魏赟韓少恒

(上海理工大學光電信息與計算機工程學院上海 200093)

超級節點SGP的選擇是影響P2P流媒體系統流暢性和播放質量的重要因素。針對P2P系統的特點，對傳統隨機選擇算法進行改進，提出運用ELM極限學習機的節點選擇算法ELM-SGP。通過對下一時刻節點帶寬和CPU實時負載度進行預估，評定超級節點的綜合可用性。普通節點根據SGP的綜合可用性強弱進行選擇，有效避免隨機選擇算法的盲目性和隨機性，使系統能夠穩定地為用戶提供高質量的可靠服務。實驗證明，相對于傳統隨機選擇算法，ELM-SGP在系統的吞吐量上提高了7.74%、播放延時降低了44.4%、播放質量方面穩定保持在90%以上。

ELM超級節點P2P流媒體帶寬

0　引　言

隨著網絡覆蓋范圍的擴大以及寬帶業務的普及，基于網絡流媒體的在線視頻、音頻、遠程課堂、視頻會議等應用，如pptv，pps等取得了快速發展。據文獻[1]報告顯示，2013年網絡視頻用戶與2012年相比增幅超過15%，在整個網民中的比率接近70%。流媒體網絡應用已成為互聯網中的重要業務。

流媒體服務質量嚴格依賴于帶寬、丟包率、時延等指標，而現有網絡體系設計初衷是用于數據傳輸業務，并非針對流媒體業務。傳統集中式服務，是基于網絡的不可靠交付，容錯性差，不適合部署支撐大規模用戶訪問的流媒體系統。P2P模式的負載分擔、自組織、資源分布式存儲等特點很好地解決了傳統中心模式的可擴展性、容錯性差和帶寬瓶頸問題。本文是基于混合式P2P模式進行分析研究，在此基礎上進行算法改進。

對于混合式P2P流媒體系統[2]而言，超級節點具有更強的處理能力、更大帶寬，它為網絡子節點提供流媒體源數據，同時還要對普通節點的路由選擇進行管理。隨機節點選擇算法和洪泛法選擇算法是當前超級節點的一般選擇算法，早期隨機節點選擇算法存在著許多缺陷，如該算法容錯性和可擴展性差，網絡動態適應能力弱，面對大規模數據流量容易造成系統癱瘓。采用洪泛法會造成非常多的冗余信息，消耗了大量的網絡帶寬資源。

除此之外，帶寬和節點負載度是影響節點服務質量的關鍵因素。面對以上問題，本文提出了利用ELM神經網絡預估節點帶寬和負載度的節點選擇算法ELM-SGP。該算法能夠根據網絡的實時動態變化，及時調整選擇能力強、帶寬高的超級節點。經過驗證分析，ELM-SGP有效地解決了P2P流媒體的QoS問題。

1　相關工作

文獻[3]提出通過分析節點離線規律，預測節點無效時刻，安排后備節點。該算法減少了控制信息的流量，造成信息的同步性較差，然而流媒體應用更強調對帶寬、CPU處理能力的要求。文獻[4]提出根據區域劃分實現超級節點的選取，該方法根據節點在物理網絡中的實際距離進行區域劃分，保證物理位置最近的節點在同一區域。文獻[5]提出一種算法，該算法通過超級節點在網絡中的區域，計算出一條最短路徑選取超級節點。H2O[6](Hierarchical 2-level overlay)是基于P2P重疊網絡的節點選擇算法。該算法向所有節點廣播自己的資源信息，這種以廣告形式進行的信息交互將產生大量通信消息，增加網絡負載。文獻[7]基于距離對節點進行聚類然后進行節點選擇，優先選擇上傳、下載能力強的節點作為鄰居節點，這種方法顯著提高了系統吞吐量。但是對節點的聚類方法僅考慮距離，不能很好地反映節點間實時可用帶寬等，不適用于流媒體系統。文獻[8]引入了信譽的概念，用節點的貢獻度、在線時長等指標衡量節點的信譽等級，選擇較好信譽的節點。文獻[9]引入了模糊集理論，將節點選擇轉化為多屬性決策問題，從理論上給出了節點選擇算法。文獻[10]根據節點到達目標節點的相似度，判斷節點是否為同一自治域(AS)，同時結合節點的能力和綜合流速率，優先選擇最優同域節點作為資源提供節點。通過以上分析，本文在傳統隨機算法基礎上進行改進，使用ELM算法對節點可用帶寬和負載度進行預估，以下部分將詳細介紹ELM-SGP算法及其驗證分析過程。

2　基于ELM動態可用帶寬的超級節點選擇

神經網絡模型是一種基于生物神經科學，模擬人腦構造和功能的數學模型。1943年W.McCulloch和W.Pits提出了形式神經元抽象數學模型。這項技術經過70多年的發展，相關研究和模型已經發展成融合了數學、生物學、計算機科學、物理學等的交叉學科。它被廣泛應用于各種領域，如：圖形處理、經濟預測、組合優化、航空技術、通信網絡等，ELM則是其中性能較優的一種。它對于隨機性、非線性變化的數據的收斂性很好。

2.1系統描述

在混合式P2P網絡中，超級節點(sp)除了作為服務器為子節點提供源數據外，還負責管理子節點的行為、與臨近層節點進行交互。包括：資源查詢、路徑選擇、信息交互等。每個超級節點都是其管轄范圍的代表，子節點可以自由選擇加入或離開，超級節點則是長時間在線、能力強的節點。一般為了保證網絡的可靠性都會有備份的超級節點，如圖1所示。

圖1　混合P2P網絡結構

2.2ELM神經網絡

極限學習ELM[11]是一種快速學習的前饋神經網絡(SLFN)算法，是由Huang G.B.等人提出，該算法在訓練過程中隱層節點參數(內權和偏置值)可以隨機生成，不需要調節，它的輸出權值依據MP廣義矩陣得到。使得它具有學習速度更快、結構更簡單、收斂性能好等優點。該網絡在這些年在各個領域得到了廣泛的應用，SLFN結構如圖2所示。

圖2　前饋神經網絡

對于一個SLFN包含L個隱含節點和m個輸出，假設有任意N個訓練樣本(xi，ti)，其中xi∈Rn，ti∈Rm則標準的單隱層神經網絡數學建模為:

(1)

其中，Wi=[wi,1,wi,2,…,wi,L]T為SLFN的輸入權重，βi為其輸出權重，bi表示的是第i個隱層單元的偏置，SLFN的激活函數為g(x)，Wi·Xj表示Wi和Xj的內積。單隱層神經網絡學習的目標是使得輸出目標可以零誤差逼近訓練樣本，即：

(2)

存在βi、Wi和bi，使得：

(3)

上式可以矩陣表示為：

Hβ=T

(4)

其中，H表示隱層節點的輸出，β為輸出權，T是期望輸出。

H(W1,…,WL,b1,…,bL,X1,…,XN)

(5)

(6)

(7)

根據文獻[12]在ELM算法中，只要隨機確定了輸入權重Wi和隱層的偏置bi，則隱層的輸出矩陣H就被唯一確定。訓練單隱層神經網絡可以轉化為求解一個線性系統Hβ=T。同時輸出權重β可以被等式β=H+·T確定，H+是矩陣H的Moore-Penrose廣義逆。

為了避免數據差異過大，統一量綱ELM要對輸入數據進行歸一化處理，將原始數據歸一到[0,1]區間，將可用帶寬時間序列進行歸一化處理，具體處理公式為：

(8)

2.3算法描述

節點Si的可用帶寬：

(9)

節點的CPU剩余負載率：

(10)

節點Si的綜合可用性：

(11)

基于ELM-SGP的算法具體步驟如下(如圖3所示)：

Step1初始化ELM算法的控制參數，設置激活函數g(x)與隱含層節點個數L，隨機生成隱含層節點參數(ai,bi)，計算輸出矩陣H，設置慣性因子的范圍[wmin,wmax]，使用式(8)歸一化帶寬時間序列X={x1,x2,…,xn}，歸一化CPU動態負載時間序列C={c1,c2,…,cn}，并根據ELM算法求出最優輸出權值βi，將X和C代入式(3)計算出每個xi對應的輸出目標oj。

圖3　算法流程圖

Step3超級節點代理根據預測結果，如圖3所示利用式(11)計算每個節點的綜合可用價值，并向鄰居超級節點代理發送該消息。

Step4超級節點代理對步驟3消息進行分析后，根據每個節點的g(i)值劃分為3個等級，當普通節點(op)請求連接超級節點Si時，鄰近Si代理將綜合可用性優良的Si列表NodeList發送給op。

Step5普通節點得到反饋信息后，再綜合考慮節點信譽、區域等進行選擇，如算法流程圖3所示。

具體ELM-SGP算法偽代碼實現如下：

Joining Node P;

P Sending join message to super agent;

while(true)

{

1. Creating a list of candidate super nodes S={s1,s2,…,sm};

2. if 1

3. then consider the m nodes reputation, distance cost,

4. content similanity;

5. choosing the super node;

6. break;

7. else

8. goto step 9;

9. Creating a estimate Vector E=[(Bi,Ci)];

10. for(i=1;i≤m;i++)

11. By using the ELM prediction of super nodes available dynamic bandwidth Biand CPU dynamic load Ci;

12. g(si)=α·Bi+(1-α)·Ci;

13. endfor

14. g order by descend,then return the top k nodes as candidate super nodes;

15. goto step 3;

}

3　仿真實驗及結果分析

本文通過Matlab評測實驗比較傳統隨機選擇算法Random-SGP與基于帶寬和CPU動態負載預測算法ELM-SGP，系統模擬真實網絡環境，模擬環境的建立如下：op數量范圍[100，1000]，sp數量范圍[20，100]，自由op為20個，sp代理數量為20個。可用參數α設置為0.4。為了能夠仿真現實網絡中節點的異構性，將普通節點聚類為三類：A、B、C，設置它們的下載帶寬分別為：4 Mbps、1.8 Mbps、750 Kbps，上傳帶寬分別為：900、465、125 Kbps。它們在系統中所占比例分別為：A:56%、B:32%、C:12%。為了驗證ELM-SGP預測算法效果，通過與傳統Random-SGP算法在平均吞吐量、平均播放延時、平均播放質量三個指標進行比較評價該方法。實驗結果如圖4-圖6所示。

圖4　Random-SGP與ELM-SGP吞吐量的比較

圖5　ELM-SGP與Random-SGP方法平均播放延時比較

圖6　ELM-SGP與Random-SGP平均播放質量比較

實驗1比較了ELM-SGP與傳統Random-SGP方法在吞吐量上的差異。節點的吞吐量是指接收報文的速率，包括流媒體數據包和控制報文。獲得越高的吞吐量，一個節點才能獲得更好的播放質量。如圖4所示ELM-SGP算法的吞吐量相對于Random-SGP算法提高了7.74%，這主要是因為本文提出的ELM-SGP方法更加全面的衡量了超級節點的網絡性能來做出選擇。

實驗2對ELM-SGP算法的播放延遲進行評估，播放延遲是指服務器發送數據時刻到此數據被節點接收時刻的延遲。這個性能參數直接影響用戶的觀看體驗，特別是對于直播系統而言。本文提出的算法相對于Random-SGP優化了選擇指標，使播放延時降低了44.4%，這將明顯改善用戶的體驗。

實驗3比較了ELM-SGP方法與傳統Random-SGP方法的播放質量。在仿真實驗中，間隔30秒，用節點在這段時間所收到的有效數據包與流媒體服務器發送數據包的比值作為該節點的播放質量。該參數直接反映了用戶觀看視頻的質量，圖6反映了ELM-SGP算法的播放質量明顯優于Random-SGP，相對提高了8.7%。ELM-SGP的播放質量雖然沒有達到100%，但隨著吞吐量的提高，平均播放質量基本穩定在90%以上，為用戶提供了流暢穩定的高質量服務。

4　結　語

本文通過對超級節點選擇算法的分析研究，結合ELM對超級節點可用帶寬和CPU的實時負載能力的進行預估。使普通節點在選擇帶寬較高的超級節點的同時兼顧超級節點的CPU實時負載能力。有效解決了傳統隨機算法的信息不同步、節點選擇質量低、可適應性差等問題。并通過仿真驗證了ELM-SGP算法相對于Random-SGP在系統吞吐量、播放延時、播放質量方面有所改善，優化了節點選擇策略。但是對于系統的自適應性和魯棒性方面仍存在著考慮因素不足以及系統抖動等問題，在下一步工作中將針對以上問題進行深入研究。

[1] 中國互聯網絡信息中心(CNNIC). 2013年中國網民網絡視頻應用研究報告[ER/OI]. [2014-06-09].http://www.cnnic.net.cn/hlwfzyj/hlwxzbg /spbg/201406/P020140609392906022556.pdf.

[2] 廖丹，孫罡，曾帥,等. P2P流媒體系統關鍵技術[M]. 北京：國防工業出版社，2014：18-20.

[3] 何欽，劉丹，周明. 基于行為特征的超級節點節流算法研究[J]. 計算機工程與應用，2013，49(11)：61-65.

[4] 郭良敏，楊壽保，郭磊濤. P2P網絡中的超級節點選取算法研究[J]. 小型微型計算機系統，2008，38(3)：385-388.

[5] Merz P，Priebe M，Wolf S．Super-Peer Selection in Peer-to-Peer Networks Using Network Coordinates[C]//International Conference on Internet and Web Applications and Services．IEEE，2008:385-390.

[6] Lo V，Zhou D，Liu Y，et al．Scalable supernode selection in peer-to-peer overlay networks[C]//International Workshop on Hot Topics in Peer-to-peer Systems．IEEE，2005:18-25.

[7] 李英壯，陳志彬，李先毅. 基于統計學習的P2P節點選擇算法[J]. 計算機應用，2013，33(1)：8-10.

[8] 劉玉枚，楊壽保，陳萬明. P2P 系統中基于信譽感知的超級節點選擇算法研究[J]. 中國科學院研究生院學報，2008，25(2)：198-202.

[9] 李彥，王麗娜. P2P流媒體系統中基于直覺模糊集的節點選擇策略[J]. 計算機科學，2013，40(6)：280-282.

[10] 韋建楠，莊雷. P2P流媒體中未知覆蓋網拓撲信息的節點選擇策略[J]. 計算機應用研究，2012，29(4)：1536-1539.

[11] Huang G，Zhu Q，Siew C．Extreme learning machine:Theory and applications[J]．Neurocomputing，2006，70:489-501.

[12] Huang G B，Zhou H M，Ding X J，et al．Extreme learning machine for regression and multiclass classification[J]．IEEE Transactions on Systems，Man，and Cybernetics，Part B:Cybernetics，2012，42( 2) : 513 -529.

[13] 周品. MATLAB神經網絡設計與應用[M]. 北京：清華大學出版社，2013.

[14] Chen S，Cowan C F N，Grant P M．Orthogonal least squareslearning algorithm for radial basis function networks[J]．IEEE Transactions on Neural Networks，1991，2(2)：302-309.

STREAMING MEDIA SUPER NODES SELECTION ALGORITHM BASED ON BANDWIDTH PREDICTION

Wei YunHan Shaoheng

(SchoolofOptical-ElectricalandComputerEngineering,UniversityofShanghaiforScienceandTechnology,Shanghai200093,China)

The selection of super group peer (SGP) is an important factor affecting the system fluency and playing quality of P2P streaming media. According to the characteristics of P2P system, we improved the traditional random selection algorithm, and proposed the nodes selection algorithm, namely ELM-SGP, which uses ELM extreme learning machine. Through estimating the node bandwidth and the CPU real-time loading at the next time moment, the comprehensive availability of super nodes can be assessed. The ordinary nodes select SGP according to its comprehensive strength of availability, this effectively avoids the blindness and randomness in random selection algorithm, and also enables the system to provide users with a stable and reliable high-quality service. It is proved by the experiment that relative to traditional random selection algorithm, ELM-SGP algorithm’s system throughput is increased by 7.74%, and its playback delay is reduced by 44.4%, the broadcast quality remains stable at 90% or higher.

ELMSuper nodeP2P streaming mediaBandwidth

2015-04-12。國家自然科學基金項目(61170277)；上海市教委科研創新基金項目(12YZ094)。魏赟，副教授，主研領域：對等網絡，分布式系統。韓少恒，碩士生。

TP393

A

10.3969/j.issn.1000-386x.2016.08.040