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

　　摘要:数据驱动型覆盖网络中的数据调度算法是影响P2P流媒体系统性能的重要因素，为了解决当前算法未能有效利用数据块和节点的特性导致流媒体服务质量差的问题，提出了一种基于数据块优先级和节点能力度的数据调度算法。该算法能够根据数据块的稀缺性、紧迫性得到块的优先级大小，根据节点的上行带宽、在线时间、相对距离得到节点能力度的大小，使优先级高的数据块和能力度大的节点优先被请求，减少了数据块的播放等待时间。在OPNET网络仿真实验表明该算法能够有效降低流媒体播放系统的启动延时和服务器的负载。
　　
　　关键词:对等网络；流媒体；数据调度；启动延迟；服务器负载
　　中图分类号:
　　TP393文献标志码:A
　　
　　Data scheduling algorithm of P2P streaming media
　　GUO Yuan.wei, XU Xue.mei*, ZHANG Jian.yang, HUANG Zheng.yu, NI Lan
　　School of Physics Science and Technology, Central South University, Changsha Hunan 410083， ChinaAbstract:
　　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 low-quality streaming media services, a novel 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 nodes 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. Network simulating experiments in the OPNET indicate that the algorithm can efficiently reduce start-up delay of streaming media playing system and the server 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 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 nodes 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 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 load
　　
　　0引言
　　基于数据驱动型覆盖网络（Data.Driven Overlay Network，DON）的P2P流媒体［1］技术的广泛使用，使P2P流媒体技术成为当前研究的热点，各种应用如BT［2］、Thunder、PPLive、PPStream等都拥有广大的用户。在DON网络中每个节点独立地选择它的伙伴形成一个无结构的覆盖网，然后通知它的伙伴它所拥有的数据，每一个节点从它的邻居节点请求缺失的数据块，同时也传递可用的数据块到它的邻居节点。
　　在DON网络中，当前一些数据调度算法主要从单一的因素去优化调度策略，忽略了其他关键因素对系统性能的影响，少数研究考虑了多因素，但也只能局部优化系统某方面的性能。例如:文献［3］中的数据调度算法主要考虑了数据的稀缺性，没有考虑到数据块的播放时间顺序，可能导致急需播放的数据块并不能优先请求，播放连续性降低；文献［4］中算法选择最近的节点提供服务来减少延迟的算法，但是算法的复杂度较高，需要对每一个节点调用算法，系统开销较大；文献［5］中提出了一种基于移动代理和节点信任度的调度算法，主要从节点的角度优化算法来降低骨干网的流量，但是没有考虑到数据块的请求顺序，导致数据块的利用率较低；文献［6］中只考虑了数据的稀缺性，没有考虑数据的紧迫性；文献［7］中只考虑了节点的因素，忽略了数据块的请求顺序。针对这些问题，本文提出了一种基于数据块优先级和节点能力度（Data.Block Priority and Node Capacity, DPNC）的数据调度算法，该算法充分考虑影响系统性能的多因素，将有效提高P2P网络中流媒体的播放连续性和服务质量。
　　1DPNC算法模型
　　1.1算法描述与前提条件1）设流媒体文件被分割为大小相等的数据块，块的大小为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算法将根据数据块优先级策略决定优先请求哪个数据块，同时某个数据块（如块8）有多个伙伴节点可以提供，将由算法中的节点能力度大小决定从哪个节点请求数据。
　　图片图1数据块调度策略
　　1.2模型参数
　　为了研究DPNC算法模型，现定义以下参数，如表1所示。在DPNC算法中，数据块的优先级由数据块的稀缺性和紧迫性这两个因素决定，根据以上的参数模型可以给出数据块优先级如式（1）所示：
　　Pki=∑k∈Di,j∈NPibkij+∑k∈Di(Tki－Ti) （1）其中：∑k∈Di,j∈NPibkij越大，表示数据块越稀少；∑k∈Di(Tki－Ti)越大，数据块越紧迫；数据块的优先级Pki由稀缺性和紧迫性同时决定。在DPNC算法中同时考虑了这两个因素，比传统算法只考虑稀缺性更加合理。表格(有表名)
　　
　　Cjik=Tji×(UBWji)2Dji （2）
　　max∑j∈NPi,bkij=1Cjik取值最大的j为节点i所请求数据块k的节点提供者。Tji节点在线时间利用当前时间减去节点最近一次加入的时间得到，UBWji为节点的上行带宽，Dji为节点之间的相对距离。第4期
　　郭远威等：P2P流媒体的数据调度算法计算机应用 第32卷
　　
　　Dji通过IP地址地域感知查表得到，由于每一个外部IP地址都会有一个确定的地域信息和运营商信息，地域信息可以用经纬度表示，根据墨卡托投影算法［9］每一个地域信息都可以映射到平面坐标系中的一定(x,y)，这里建立一个字典表Dictionary(ip,(x,y))来快速计算节点间的相对距离，其中ip为字典表的键，(x,y)为其对应的值，因此知道了节点ip，就可以查表快速地找到对应的坐标信息(x,y)，计算两个节点的相对距离如式（3）所示。
　　Dji=(xi－xj)2+(yi－yj)2（3）
　　为了减少算法的计算量Dji可以由式（4）近似得到:
　　Dji=max{|xi－yi|,|xj－yj|} （4）
　　将式（4）代入式（2）中得式（5）:
　　 Cjik=Tji×(UBWji)2max{|xi－xj|,|yi－yj|}（5）
　　分子中(UBWji)2表示在计算节点能力度的过程中占较大的比重。
　　
　　2算法伪代码与分析
　　在书写算法伪代码的过程中“缩进”表示程序中分程序结构，代码中定义了两个局部变量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)两步是通过字典表数据结构来查找，时间复杂度均为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］中提到的数据调度算法进行对比。
　　实验通过OPNET［12］网络仿真器进行，主要软硬件环境为：一台AMD双核处理器2.7GHz主频，2GB内存，XP操作系统。网络拓扑层由10个核心路由器和100个区域路由器组成，每10个区域路由器连在一个核心路由器上，核心路由器之间以及核心路由器与区域路由器之间网络带宽为10Gbps，区域路由器间的带宽为100Mbps，数据源服务器连接在一个固定的核心路由器上，终端节点随机连接在某个区域路由器上。
　　节点的上行带宽服从均值为100Kbps的指数（泊松）分布，节点的平面坐标(x,y)，其中x、y均服从均值为10km的指数（泊松）分布，流媒体的码率为300Kbps，数据块的大小为1Kb，每个节点滑动窗口的大小为120个数据块，节点初始总数为2000。
　　
　　3.1启动延迟实验与分析
　　每个节点的按播放顺序请求的数据块数量达到20时就开始播放，播放启动延迟为节点加入系统到开始播放的时间，新节点以固定频率随机加入并连接在某个区域路由器上。图2给出了仿真运行7小时，不同算法下节点的平均启动延迟时间变化。可以看到系统开始运行时延迟都比较大，随着时间的推移，启动延迟逐渐降低，到达一定的时间后，延迟趋于稳定。其中DPNC算法启动延迟平衡值约为15.59858619s，DoNet为16.98575192s，AnySee为18.63836027s，MATPS为20.08844481s，由于在DPNC算法中充分考虑了邻居节点的带宽、在线时间以及节点间的相对距离，系统能更快速获取播放所必须的数据块，从而更能降低系统的播放启动延迟。
　　为了研究网络波动性对不同算法启动延迟的影响，在OPNET中的使初始节点以加入节点频率的1/2随机离开，仿真运行，结果如图3所示。比较图2和图3可知受节点离开网络波动的影响，延迟达到平衡的时间增加。
　　
　　图片图2平均启动延迟
　　
　　图片图3网络波动对平均启动延迟的影响
　　3.2服务器负载实验与分析
　　利用服务器单位时间内输出流量值［13］的大小来衡量服务器的负载大小，单位时间内输出流量值越小，负载就越小。
　　从图4中可以看出，服务器的负载逐渐增加，到达一定时间后达到平衡。由OPNET仿真后统计数据可知，DPNC算法中平衡值约为3891.02Kbps，DoNet算法为4287.37Kbps，AnySee算法为4150.66Kbps，MATPS算法为4396.78Kbps。由于DPNC算法在请求数据块时充分考虑了节点的上行带宽、在线时间、相对距离，使系统中节点的相互作用性提高，对服务器的请求次数减少，因此有利于降低服务器的负载。
　　图片图4服务器平均负载
　　
　　4结语
　　本文主要研究P2P流媒体传输过程中的数据调度问题，为了更好地提高流媒体的服务质量，本文提出了一种基于数据块优先级和节点能力度的数据调度算法DPNC,充分考虑了数据块的稀缺性和紧迫性、节点的上行带宽、在线时间、相对距离这些影响系统的关键因素，建立了数据调度算法模型，并给出了算法的伪代码，最后通过仿真实验表明DPNC算法能有效降低服务器的负载和节点的播放启动延迟。在下一步的工作中，将对DPNC算法部署在实际系统中运行测试，进一步降低算法的复杂度，进一步加强对节点管理的研究以提高系统的稳定性。

推荐访问:流媒体 调度 算法 姓名