基于带宽预测的流媒体超级节点选择算法

魏　赟　韩少恒

(上海理工大学光电信息与计算机工程学院　上海 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