P2P流媒体的数据调度算法作者姓名

1、 P2P流媒体的数据调度算法作者姓名摘要:数据驱动型覆盖网络中的数据调度算法是影响p2p流媒体系统性能的重要因素，为了解决当前算法未能有效利用数据块和节点的特性导致流媒体服务质量差的问题，提出了一种基于数据块优先级和节点能力度的数据调度算法。该算法能够根据数据块的稀缺性、紧迫性得到块的优先级大小，根据节点的上行带宽、在线时间、相对距离得到节点能力度的大小，使优先级高的数据块和能力度大的节点优先被请求，减少了数据块的播放等待时间。在opnet网络仿真实验表明该算法能够有效降低流媒体播放系统的启动延时和服务器的负载。关键词:对等网络；流媒体；数据调度；启动延迟；服务器负载中图分类号:tp393文献

2、标志码:adata scheduling algorithm of p2p streaming mediaguo yuan.wei, xu xue.mei*, zhang jian.yang, huang zheng.yu, ni lanschool of physics science and technology, central south university, changsha hunan 410083， chinaabstract:the data scheduling algorithm in data-driven overlay network is identified a

3、s one of the most influential factors affecting system performance of p2p streaming media. considering the fact that the current algorithm fails to make use of the data blocks and nodes efficiently, which leads to low-quality streaming media services, a novel method for data scheduling algorithm was

4、 proposed in this study based on both priority of data blocks and capacity of nodes. this algorithm could get priority value according to the scarcity and urgency of blocks. it also could get the capacity of the nodes according to uplink-bandwidths, time-online and relative distance of the nodes. wi

5、th the utilization of this algorithm, higher priority blocks and higher capacity nodes were requested, and the waiting time to play was decreased. network simulating experiments in the opnet indicate that the algorithm can efficiently reduce start-up delay of streaming media playing system and the s

6、erver load.the data scheduling algorithm in data.driven overlay network is identified as one of the most influential factors affecting system performance of p2p streaming media. considering the fact that the current algorithm fails to make use of the data blocks and nodes efficiently, which leads to

7、 low.quality streaming media services, a new method for data scheduling algorithm was proposed in this study based on both priority of data blocks and capacity of nodes. this algorithm could get priority value according to the scarcity and urgency of blocks. it also could get the capacity of the nod

8、es according to uplink.bandwidths, time.online and relative distance of the nodes. with the utilization of this algorithm, higher priority blocks and higher capacity nodes were requested, and the waiting time to play was decreased. the simulations in the opnet network indicate that the algorithm can

9、 efficiently reduce start.up delay of streaming media playing system and the server load.key words:peer.to.peer (p2p); streaming media; data scheduling; start.up delay; server load0引言基于数据驱动型覆盖网络（data.driven overlay network，don）的p2p流媒体1技术的广泛使用，使p2p流媒体技术成为当前研究的热点，各种应用如bt2、thunder、pplive、ppstream等都拥有广大

10、的用户。在don网络中每个节点独立地选择它的伙伴形成一个无结构的覆盖网，然后通知它的伙伴它所拥有的数据，每一个节点从它的邻居节点请求缺失的数据块，同时也传递可用的数据块到它的邻居节点。在don网络中，当前一些数据调度算法主要从单一的因素去优化调度策略，忽略了其他关键因素对系统性能的影响，少数研究考虑了多因素，但也只能局部优化系统某方面的性能。例如:文献3中的数据调度算法主要考虑了数据的稀缺性，没有考虑到数据块的播放时间顺序，可能导致急需播放的数据块并不能优先请求，播放连续性降低；文献4中算法选择最近的节点提供服务来减少延迟的算法，但是算法的复杂度较高，需要对每一个节点调用算法，系统开销较大；文

11、献5中提出了一种基于移动代理和节点信任度的调度算法，主要从节点的角度优化算法来降低骨干网的流量，但是没有考虑到数据块的请求顺序，导致数据块的利用率较低；文献6中只考虑了数据的稀缺性，没有考虑数据的紧迫性；文献7中只考虑了节点的因素，忽略了数据块的请求顺序。针对这些问题，本文提出了一种基于数据块优先级和节点能力度（data.block priority and node capacity, dpnc）的数据调度算法，该算法充分考虑影响系统性能的多因素，将有效提高p2p网络中流媒体的播放连续性和服务质量。1dpnc算法模型1.1算法描述与前提条件1）设流媒体文件被分割为大小相等的数据块，块的大小为

12、k个字节，按照数据块的播放顺序，将块编号为1,2,3,m，其中fm表示流媒体文件的第m个数据块。2）设滑动窗口8的大小为l个字节，是数据块大小的整数倍即l=nk，滑动窗口以外的数据块不在节点请求的考虑范围之内，所有节点的滑动窗口以相同速度移动。3）节点滑动窗口中的数据块缓存情况可以用一个l位的向量表示，如果其中某位为1，表示该位对应的数据块已经在节点的缓存中；否则表示对应的数据块不存在，等待请求。4）如图1所示，有节点a、b、c、d，阴影部分表示滑动窗口中缺失的数据块，节点c向a、b、d请求缺失的数据块。节点c的缓存中数据块5、6、7已存在，8、9、10、11、12等待请求。本文提出的dpnc

13、算法将根据数据块优先级策略决定优先请求哪个数据块，同时某个数据块（如块8）有多个伙伴节点可以提供，将由算法中的节点能力度大小决定从哪个节点请求数据。图片图1数据块调度策略1.2模型参数为了研究dpnc算法模型，现定义以下参数，如表1所示。在dpnc算法中，数据块的优先级由数据块的稀缺性和紧迫性这两个因素决定，根据以上的参数模型可以给出数据块优先级如式（1）所示：pki=kdi,jnpibkij+kdi(tkiti) （1）其中：kdi,jnpibkij越大，表示数据块越稀少；kdi(tkiti)越大，数据块越紧迫；数据块的优先级pki由稀缺性和紧迫性同时决定。在dpnc算法中同时考虑了这两个因

14、素，比传统算法只考虑稀缺性更加合理。表格(有表名)cjik=tji×(ubwji)2dji （2）maxjnpi,bkij=1cjik取值最大的j为节点i所请求数据块k的节点提供者。tji节点在线时间利用当前时间减去节点最近一次加入的时间得到，ubwji为节点的上行带宽，dji为节点之间的相对距离。第4期郭远威等：p2p流媒体的数据调度算法计算机应用 第32卷dji通过ip地址地域感知查表得到，由于每一个外部ip地址都会有一个确定的地域信息和运营商信息，地域信息可以用经纬度表示，根据墨卡托投影算法9每一个地域信息都可以映射到平面坐标系中的一定(x,y)，这里建立一个字典表dictio

15、nary(ip,(x,y)来快速计算节点间的相对距离，其中ip为字典表的键，(x,y)为其对应的值，因此知道了节点ip，就可以查表快速地找到对应的坐标信息(x,y)，计算两个节点的相对距离如式（3）所示。dji=(xixj)2+(yiyj)2（3）为了减少算法的计算量dji可以由式（4）近似得到:dji=max|xiyi|,|xjyj| （4）将式（4）代入式（2）中得式（5）:cjik=tji×(ubwji)2max|xixj|,|yiyj|（5）分子中(ubwji)2表示在计算节点能力度的过程中占较大的比重。2算法伪代码与分析在书写算法伪代码的过程中“缩进”表示程序中分程序结构，

16、代码中定义了两个局部变量skj、t，分别表示数据块的稀缺性和紧迫性。算法的输入di为节点i在一个调度周期内需要请求的数据块集合，npi为节点i的邻居节点集合；算法的输出l(k,pki)为根据块的优先级大小排序的集合，输出cjik为节点i的邻居节点中拥有所请求的数据块k的节点j的能力度大小，代码如下所示。程序前1)程序后由滑动窗口的大小为l=nk，设邻居节点个数为m，则算法3）、4）两步的时间复杂度为o(m)，算法5）7）步时间复杂度为o(3)，所以2）7）步时间复杂度为o(n×(m+3)；第8)步采用快速排序算法10来排序，时间复杂度为o(n×lg n)，第10)、11)两

17、步是通过字典表数据结构来查找，时间复杂度均为o(1)；第9)13)步时间复杂度为o(m×4)。dpnc算法总的时间复杂度如式（6）所示:t=o(n×lg n)+o(n×(m+3)+o(m×4) （6）根据算法分析的渐进原则，略去低阶项和常数项，整理式（6）可得:t=o(n×(m+lg n) （7）从式（7）可知算法的时间复杂度主要由滑动窗口的大小和邻居节点的个数决定。3实验仿真与分析实验将从影响p2p流媒体播放系统的启动延迟、服务器负载11两个主要方面进行仿真与分析，并与文献3-5中提到的数据调度算法进行对比。实验通过opnet12网络仿真器进

18、行，主要软硬件环境为：一台amd双核处理器2.7ghz主频，2gb内存，xp操作系统。网络拓扑层由10个核心路由器和100个区域路由器组成，每10个区域路由器连在一个核心路由器上，核心路由器之间以及核心路由器与区域路由器之间网络带宽为10gbps，区域路由器间的带宽为100mbps，数据源服务器连接在一个固定的核心路由器上，终端节点随机连接在某个区域路由器上。节点的上行带宽服从均值为100kbps的指数（泊松）分布，节点的平面坐标(x,y)，其中x、y均服从均值为10km的指数（泊松）分布，流媒体的码率为300kbps，数据块的大小为1kb，每个节点滑动窗口的大小为120个数据块，节点初始总数

19、为2000。3.1启动延迟实验与分析每个节点的按播放顺序请求的数据块数量达到20时就开始播放，播放启动延迟为节点加入系统到开始播放的时间，新节点以固定频率随机加入并连接在某个区域路由器上。图2给出了仿真运行7小时，不同算法下节点的平均启动延迟时间变化。可以看到系统开始运行时延迟都比较大，随着时间的推移，启动延迟逐渐降低，到达一定的时间后，延迟趋于稳定。其中dpnc算法启动延迟平衡值约为15.59858619s，donet为16.98575192s，anysee为18.63836027s，matps为20.08844481s，由于在dpnc算法中充分考虑了邻居节点的带宽、在线时间以及节点间的相对距离，系统能更快速获取播放所必须的数据块，从而更能降低系统的播放启动延迟。为了研究网络波动性对不同算法启动延迟的影响，在