基于帶寬預(yù)測的流媒體超級節(jié)點選擇算法

魏　赟　韓少恒

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

?

基于帶寬預(yù)測的流媒體超級節(jié)點選擇算法

魏赟韓少恒

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

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

ELM超級節(jié)點P2P流媒體帶寬

0　引　言

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

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

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

除此之外，帶寬和節(jié)點負載度是影響節(jié)點服務(wù)質(zhì)量的關(guān)鍵因素。面對以上問題，本文提出了利用ELM神經(jīng)網(wǎng)絡(luò)預(yù)估節(jié)點帶寬和負載度的節(jié)點選擇算法ELM-SGP。該算法能夠根據(jù)網(wǎng)絡(luò)的實時動態(tài)變化，及時調(diào)整選擇能力強、帶寬高的超級節(jié)點。經(jīng)過驗證分析，ELM-SGP有效地解決了P2P流媒體的QoS問題。

1　相關(guān)工作

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

2　基于ELM動態(tài)可用帶寬的超級節(jié)點選擇

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

2.1系統(tǒng)描述

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

圖1　混合P2P網(wǎng)絡(luò)結(jié)構(gòu)

2.2ELM神經(jīng)網(wǎng)絡(luò)

極限學(xué)習(xí)ELM[11]是一種快速學(xué)習(xí)的前饋神經(jīng)網(wǎng)絡(luò)(SLFN)算法，是由Huang G.B.等人提出，該算法在訓(xùn)練過程中隱層節(jié)點參數(shù)(內(nèi)權(quán)和偏置值)可以隨機生成，不需要調(diào)節(jié)，它的輸出權(quán)值依據(jù)MP廣義矩陣得到。使得它具有學(xué)習(xí)速度更快、結(jié)構(gòu)更簡單、收斂性能好等優(yōu)點。該網(wǎng)絡(luò)在這些年在各個領(lǐng)域得到了廣泛的應(yīng)用，SLFN結(jié)構(gòu)如圖2所示。

圖2　前饋神經(jīng)網(wǎng)絡(luò)

對于一個SLFN包含L個隱含節(jié)點和m個輸出，假設(shè)有任意N個訓(xùn)練樣本(xi，ti)，其中xi∈Rn，ti∈Rm則標準的單隱層神經(jīng)網(wǎng)絡(luò)數(shù)學(xué)建模為:

(1)

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

(2)

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

(3)

上式可以矩陣表示為：

Hβ=T

(4)

其中，H表示隱層節(jié)點的輸出，β為輸出權(quán)，T是期望輸出。

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

(5)

(6)

(7)

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

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

(8)

2.3算法描述

節(jié)點Si的可用帶寬：

(9)

節(jié)點的CPU剩余負載率：

(10)

節(jié)點Si的綜合可用性：

(11)

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

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

圖3　算法流程圖

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

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

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

具體ELM-SGP算法偽代碼實現(xiàn)如下：

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　仿真實驗及結(jié)果分析

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

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

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

圖6　ELM-SGP與Random-SGP平均播放質(zhì)量比較

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

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

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

4　結(jié)　語

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

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

[2] 廖丹，孫罡，曾帥,等. P2P流媒體系統(tǒng)關(guān)鍵技術(shù)[M]. 北京：國防工業(yè)出版社，2014：18-20.

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

[4] 郭良敏，楊壽保，郭磊濤. P2P網(wǎng)絡(luò)中的超級節(jié)點選取算法研究[J]. 小型微型計算機系統(tǒng)，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] 李英壯，陳志彬，李先毅. 基于統(tǒng)計學(xué)習(xí)的P2P節(jié)點選擇算法[J]. 計算機應(yīng)用，2013，33(1)：8-10.

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

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

[10] 韋建楠，莊雷. P2P流媒體中未知覆蓋網(wǎng)拓撲信息的節(jié)點選擇策略[J]. 計算機應(yīng)用研究，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神經(jīng)網(wǎng)絡(luò)設(shè)計與應(yīng)用[M]. 北京：清華大學(xué)出版社，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。國家自然科學(xué)基金項目(61170277)；上海市教委科研創(chuàng)新基金項目(12YZ094)。魏赟，副教授，主研領(lǐng)域：對等網(wǎng)絡(luò)，分布式系統(tǒng)。韓少恒，碩士生。

TP393

A

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