基于贡献度的自适应P2P流媒体数据调度算法

计算机应用与软件Computer Applications and Software基于贡献度的自适应P2P流媒体数据调度算法赵天昊郑烇王嵩杨坚(中国科学技术大学自动化系安徽 合肥 )(网络传播系统与控制安徽省重点实验室安徽 合肥 )摘要 在P2P流媒体系统中，数据调度算法是决定视频播放质量和系统性能的核心部分。针对当前P2P流媒体数据调度算法未能考虑节点带宽和服务能力的差异，从而造成对系统资源利用不充分的问题，提出了一种基于贡献度的自适应(CBA)流媒体数据调度算法。算法定义节点贡献度来衡量节点的数据上传和可用带宽情况，预先向部分节点传输准备数据。并根据数据块优先级、带宽估计情况和节点贡献度等信息进行自适应调整，确定数据块请求的提供方和次序。仿真实验表明，CBA算法能充分地利用节点可用带宽，降低流媒体的启动延时和服务器负载，改善系统的整体性能。关键词 数据调度对等网络流媒体启动延迟负载均衡中图分类号 TP393文献标识码 A DOI: CONTRIBUTION-BASED ADAPTIVE DATA SCHEDULING ALGORITHM FOR P2P MEDIA STREAMINGZhao Tianhao12 Zheng Quan12 Wang Song12 Yang Jian11(Department of Automation, University of Science and Technology of China, Hefei ,Anhui,China) 2(Key Laboratory of Network Communication System & Control of Anhui, Hefei ,Anhui,China)Abstract In peer-to-peer streaming system, data scheduling algorithm is the key to determine the playback quality and system performance. Existing algorithms make insufficient consideration of differences in bandwidth and service capacities, and are not able to make full use of system resources. In order to solve this problem, a contribution-based adaptive (CBA) data scheduling algorithm is proposed in this paper. In the algorithm, contribution is used to measure the capacity of transmission and bandwidth. Data is transmitted to some peers in advance for preparation. Peers decide the suppliers and scheduling orders according to priorities of segments, bandwidth estimations and contributions. Simulation results show that this algorithm can take full advantage of bandwidth resources to reduce start-up delays and server peers load, and improve the overall service capacity of the system as well. Keywords Data scheduling Peer-to-peer Streaming Start-up delay Load balance计算机应用与软件50 引言收稿日期: xxxx-xx-xx。国家自然科学基金项目()，国家发改委CNGI课题(CNGI-09-03-14)，安徽省教育厅高校自然科学研究项目(KJ2011A276)。赵天昊，硕士研究生，主研领域：网络媒体分发系统。郑烇，副教授。王嵩，讲师。杨坚，副教授。网络的发展为流媒体的大规模应用提供了基础，基于P2P技术的流媒体以其良好的可扩展性和低成本的优势，已成为当前网络环境下的主导级应用1。P2P流媒体系统中各节点与邻居组成底层覆盖网络，节点与邻居间进行数据交换，利用终端的上行带宽资源降低了服务器的负载，提高视频的流畅程度，解决了传统流媒体系统中服务器网络资源要求高、服务能力有限的问题。分布式的P2P流媒体系统中，媒体内容通常以块为单位进行划分2，节点通过与邻居交换所持有的数据块信息，根据调度算法独立地决定所需数据块的发送方和次序。良好的调度算法可以发掘节点的服务能力，提高异构网络中的带宽利用率。数据调度算法对视频播放质量和系统性能具有重要影响，是P2P流媒体系统中的研究热点3。文献4利用“最大流-最小耗费”来解决流媒体数据调度问题，文献5提出一种整数线性规划方案求解数据调度问题，这两种算法可得到较优的调度效果，但算法复杂度高，不适合分布式的实时P2P流媒体系统。以最大化流媒体服务质量为目的的数据块最优调度问题是NP难的，因此一些求解较快的启发式算法调度算法被提出，如文献6中提出的数据驱动覆盖网络（Data-driven Overlay Network，DONet）采用局部稀有优先（Local Rarest First， LRF）策略，选取邻居节点中最少的数据块进行调度，并优先请求剩余带宽最多的节点。但仅根据剩余带宽来选择发送节点会造成部分高带宽节点负载过大，对稀有数据块的请求过于集中。文献7中提出了随机选择的策略，但是对数据块特性和节点服务能力等多种因素考虑欠缺而存在性能不稳定的问题。文献8中采用了轮询调度的方法，适用于同构环境，在节点带宽存在差异时系统性能较差。针对上述问题，本文提出一种基于贡献度的自适应(CBA)流媒体调度算法。该算法考虑了网络中不同带宽节点的数据传输能力差异，提出了贡献度的定义。针对调度初期系统中存在的数据块稀有问题，提出了向部分贡献度较高节点传输缓存数据的策略。同时根据数据块优先级、动态变化的带宽情况和贡献度综合进行自适应调度，得到提高带宽资源效率和适应性更强的数据调度方案。1 系统模型1.1 调度过程与存在问题为满足数据时效和顺序的要求，节点维护一个媒体数据接收缓存，缓存将根据媒体播放消耗和节点接收数据的状态而向前移动。缓存中数据块的可用性信息用缓存映像Buffer Map6, 9来表示。每个调度周期中，节点和邻居节点间通过交换缓存映像获知对方持有的数据块，通过调度算法完成相互协同服务，达到媒体内容的分布式传输和播放的目的。在数据传输过程中，高下行带宽节点获取所需数据块较快。在当前周期内数据获取完毕，且利用上行带宽向邻居提供数据时，下行带宽将处于闲置状态。同时在每个调度周期中，邻居节点请求获取源节点中的新数据并在P2P网络中扩散传播。若这些直接邻居的带宽较小，对网络提供数据块的服务能力不高，将制约整体系统的流媒体分发效率。CBA数据调度算法将对以上问题提出解决方案。1.2 贡献度定义P2P流媒体系统中节点的上行带宽反映了可向邻居提供数据的服务能力。通常上下行带宽是正相关的，高带宽节点在调度中能更快地获取稀有数据块，低带宽节点将趋向从高带宽节点请求较多数据块，因此带宽较高的节点贡献的数据块数量多。为区分节点在调度周期向邻居传输的数据块与带宽的关系，定义了贡献度的概念。为计算贡献度所需的各节点上行带宽集合，为节点上传带宽，为节点在调度周期上传的数据量，节点的贡献度定义如下。 其中表示单位上行带宽上发送数据块的实际贡献量，表征了节点当前的数据共享程度。表示节点的上行带宽在所有节点带宽中所占比例，为潜在的贡献能力，即高带宽的节点其期望提供的数据应越多。1.3 数据调度模型P2P流媒体数据块调度策略可抽象为使总体调度成功的数据块优先级的和达到最大，同时不能超出各节点的带宽服务能力限制，可用数学模型表达如下，其中各符号的意义如Error! Reference source not found.所示。 式中的条件与分别限定了调度中本地节点下载和邻居节点上传的数据不能超过各自的下行与上行带宽能力。表1 参数定义符号量意义节点的下行带宽节点中数据块的缓存映像节点的上行带宽所有节点的集合节点的邻居集合块的优先级需要调度的数据块集合t调度周期节点从节点下载块的速度为1表示节点从节点调度数据块，否则为02 CBA数据调度算法本文设计的CBA算法分为预缓存传输和节点间数据调度两部分。预缓存传输根据贡献度预先将调度周期内需要的准备数据发送到部分节点，提高整体的数据调度效率。节点间数据调度综合考虑贡献度、数据块特性和网络情况等因素，各节点利用自适应的启发式算法确定所需数据块的提供节点和顺序。2.1 预缓存传输策略预缓存传输策略的思想是在高贡献度节点下行带宽负载低时，由源节点向其传输准备数据，以提高下行带宽的利用率，并加快源节点中新数据在系统中的传播速率。预缓存传输策略将节点的缓存结构组织为如Error! Reference source not found.所示。缓存中数据块按照对应播放时间增序排列，对应时刻早于当前播放时刻的数据块位于已播放区。紧急区为距当前播放时刻较近而急需的数据块，节点需要尽量在截止时间之前填充相应空位。预缓区用于存放节点从源节点得到的准备数据块。图1 节点缓存结构每个新节点在加入P2P网络时告知源节点其最大上行带宽大小，源节点按照上行带宽的降序更新P2P网络中的节点列表，其中前个节点组成集合。每个调度周期末期，源节点向中各节点发送查询报文，这些节点将上一周期内上传的数据块数量与上行带宽返回源节点。参照式可计算各节点的贡献度集合，其中最大值为。在调度周期末期，源节点预先准备好下一周期需要的新数据，并传输至部分节点。一个调度周期内播放流媒体需要数据块数量为，源节点从中随机选择块传输给节点，以保证分配的数据块均匀地存在于系统中。的选择满足下式。 随着预缓区边界数据转换到紧急区，其中的准备数据将立即用于节点间的数据调度，节点间邻接关系使准备数据在网络中进行扩散，减小了源节点向系统中提供新数据的压力。分配给中各节点的准备数据量与贡献度正相关，以平衡节点带宽和上一周期实际数据上传数量：对于高贡献度节点，分配较多的数据块匹配其数据上传能力；若节点上周期贡献较低而带宽较高，考虑到带宽资源可能未得到有效的利用，计算得到的贡献度并不会偏低，仍会分配稍多的数据块以期望提高带宽的利用率。这样使策略在动态调整中达到高带宽节点的实际贡献度与带宽平衡的目的上述的选取既不能过大，使传输数据块占用源节点带宽时间过长，而减小了对低带宽节点负载的服务能力；也不能过小而使算法的预缓存效果不高。可将n设置为P2P网络中节点的最大邻居数，相当于将带宽最高的n个节点设置为源节点的直接邻居。同时在每次进行源节点数据传输时，仅需要向固定个数的节点发送贡献度请求报文，也能够限制控制开销。2.2 节点间数据调度算法在节点间数据调度算法中，针对数据块的紧迫程度和稀有性定义了优先级，根据优先级确定数据块的调度顺序。通过估计邻居的可分配带宽得到数据块的传输时间，并结合贡献度完成发送方的选择。流媒体数据块截止时刻越接近当前播放时刻则紧迫程度越高，需要尽快得到调度。设数据块对应的播放时刻为，数据块大小，发送节点和接收节点的剩余带宽分别为和，则启动该数据块的最晚时限。在数据块调度时间不能满足最晚时限时将从源节点请求，保证流媒体播放的连续性。数据块的稀有性是指被较少邻居拥有的数据块在系统中交换更困难，容易成为节点无法满足播放截止时间要求的瓶颈，因此节点在调度中应优先请求具有较少拥有者的数据块，从而加速数据块在系统中的传播。根据上述紧迫程度和稀有性的分析，算法定义了数据块优先级。数据块对于节点的优先级如下所示。 对于邻居带宽的估计，考虑到带宽的动态变化和连续性，据当前时刻较近周期的带宽值的参考价值更大。因此不同于文献10中对最近若干周期内邻居节点的实际带宽取平均值的方法，CBA算法采用退化的思想来进行带宽估计，带宽估计公式如下。 其中为节点在当前周期的带宽估计值，为节点根据上一周期向本地节点传输量得到的实际带宽，为上周期为节点估计的带宽，为退化系数，满足。使用该方法同时考虑了最近周期和历史数据从而得到更合适的带宽估计值。不同邻居节点带宽条件具有差异，因数据上传能力不同对本地节点的贡献也不同。如果一个邻居相对本地节点的贡献度较高，那么选择该邻居传输数据块具有更好的可靠性，将数据块调度优先请求到该邻居能够更合理地分配系统中的带宽资源。因此贡献度是数据块的发送方选择中需要参考的因素。为上周期邻居节点向本地节点提供的数据块量，为上周期所有邻居可向本地节点分配的带宽集合，可由带宽估计得到，为节点向本地节点分配的带宽。节点对本地节点贡献度计算公式如下。 调度算法初始前已统计每个邻居可提供的本地节点缺少的数据块数量segment_count，对于当前优先级最高的数据块，算法将选择向预期传输到达时间较早且节点贡献度高的节点发起调度请求。算法的伪代码表示如下。Input:B 邻居节点的估计带宽expected_set 需要获取的数据块集合 p 数据块优先级 Con 各邻居的贡献度segmeng_count各邻居中本节点需要的数据块数Scheduling:while expected_set != null dok=argjPjPj|j, jexpected_setq=argr(time(r)+/Br)/Conr 1 segment_countq=segment_countq-1Bq=Bq-expected_set=expected_set-kend whileOutput:supplieri:supplier for unavailable segment iexpected_set 在选择数据块发送方时，算法根据time(r)评估预期的传输结束时间，如果存在低带宽节点能够更早地完成数据块的传输，选择该节点不仅能更快地获取数据块，而且降低了高带宽节点的负载。在贡献度的衡量上，每分配一个发送方后，将对该节点的贡献度进行退化，使其他贡献度稍低的节点能够被分配到数据调度，而不会全部负载到贡献度高的节点上。当节点所处的网络拓扑或带宽发送改变时，算法将根据变化的贡献度进行自适应调整。如邻居的带宽情况在近几个周期变好，那么调度时将适度地分配多一些数据请求至该邻居，以利用带宽资源。如果节点负载较差而导致向本地节点贡献变小，调度算法会将该节点的数据请求相应减少，直到节点负载恢复稳定时再考虑增加数据请求。P2P系统中节点间分布式地独立运行调度算法，每个节点都考虑到了各邻居的贡献和负载情况，在节点的博弈中达到系统的平衡，提高系统的性能和资源利用效率。3 仿真评估为分析与评估算法的性能，采用清华大学的p2pstrsim11作为仿真实验平台。仿真实验中设置媒体流速率为300kbps，数据块大小1KB，初始缓冲时间10s，调度周期为1s，源服务器带宽10Mbps，1000个节点按照的泊松分布加入系统，仿真时间500s。为了模拟节点带宽的异质性，根据实际因特网的测量结果12将节点接入带宽设置为三类并如Error! Reference source not found.所示的比例。表2 节点接入带宽及比例上行带宽kb/s下行带宽kb/s比例12851235%51251245%2048204820%仿真中将本算法与DONet中的稀有优先（LRF）调度算法和随机调度（Random）进行比较。3.1 服务器负载Error! Reference source not found.所示为服务器带宽负载随时间的变化情况，可见CBA调度算法优于传统调度算法。LRF算法中节点只简单地从剩余带宽最大的节点处获取邻居中最稀有的数据块，容易造成高带宽节点负载过大而传输较差，于是需要向服务器调度较多数据。CBA算法中考虑到了调度初期的数据稀有性，高贡献度节点缓冲区中的准备数据能够缓解服务器压力，同时调度算法根据带宽与贡献度等多种因素来平衡各节点的数据提供负载，在服务器带宽能力相同的情况下可为更多节点提供流媒体服务，提高系统的可扩展性。图2 服务器负载比较3.2 节点吞吐率三种算法中系统节点的平均吞吐量与节点数量变化关系如Error! Reference source not found.所示。LRF调度算法容易造成拥有稀少数据块的节点在请求拥塞时降低数据传输效率浪费带宽资源的情况，超出发送节点服务能力时数据接收节点的吞吐率将达不到较高的水平。Random调度策略中对数据块特性和网络情况欠缺考虑，对系统资源的利用率最低。CBA调度算法将数据块请求根据对本地节点的贡献度均衡地分配到各邻居节点，充分利用了优质贡献度节点中的缓存准备数据，同时也并没有忽略传输较慢的节点。因此针对各节点的特性较好地利用了系统资源，提高带宽利用率和吞吐量。吞吐率也反映了表示了单位时间内有效接收数据的程度，吞吐量越接近流媒体播放速率则视频的播放越流畅，于是可知CBA调度算法可以达到更好的视频流畅度。3.3 启动延迟三种算法启动延迟的累积分布如Error! Reference source not found.所示。流媒体系统中节点需要缓存一定量数据才能提供播放，较低的启动延迟有助于提高用户的体验度。CBA算法考虑了带宽情况、数据块和节点特性，对带宽资源利用更充分，数据块请求成功率高于LRF和Random算法，因此降低了启动延迟。LRF仅对稀有数据块进行请求，获取数据的成功率相对低；Random算法未能合理地利用节点资源进行调度，因此两种算法的启动延迟较大。图3 平均吞吐率比较图4 启动延迟比较4 结论本文对P2P流媒体系统中数据传输问题进行了研究，提出了CBA调度算法。算法通过定义贡献度考虑了节点的带宽与服务情况，并综合数据块优先级和带宽估计，合理地分配服务器与节点间和节点相互间的数据传输调度。仿真实验表明与LRF和Random算法相比，CBA算法在服务器负载均衡、节点吞吐率和启动延迟等方面具有提升，提高了资源利用效率和系统性能。实际P2P流媒体系统中同时存在多个节目的播放，而目前针对多节目协同调度的研究还很少，因此今后将围绕此方面展开进一步研究。参考文献1 CIULLO D, GARCIA M A, HORV A Th A, et al. Network awareness of p2p live streaming applications: a measurement studyJ. IEEE Transactions on Multimedia, 2010,12(1):54-63.2 LIU Z, SHEN Y, ROSS K W, et al. Layerp2p: using layered video chunks in p2p live streamingJ. IEEE Transactions on Multimedia, 2009,11(7):1340-1352.3 苏少炜, 王劲林, 尤佳莉. 一种带宽自适应 P2P 视频点播数据调度策略J. 计算机工程, 2011,37(1) :13-15.4 ZHANG M, XIONQ Y, ZHANG Q, et al. On the optimal scheduling for media streaming in data-driven overlay networksC/Proc. of IEEE Global Telecommunications Conference, San Francisco, USA, 2006. New York:IEEE, 2006:1-5.5 HSU C H, HEFEEDA M. Quality-aware segment transmission scheduling in peer-to-peer streaming systemsC/Proc. of the first annual ACM SIGMM conference on Multimedia Systems, Arizona, 2010. New York:ACM, 2010:169-180.6 ZHANG X, LIU J, LI B, et al. CoolStreaming/DONet: a data-driven overlay network for peer-to-peer live media streamingC/Proc. of IEEE INFOCOM05, Miami, USA, 2005. New York:IEEE, 2005: 2102- 2111.7 PAI V, KUMAR K, TAMILMANI K, et al. Chainsaw: eliminating trees from overlay multicastJ. Proc. of International Workshop on Peer-to-peer systems, New York, USA, 2005:127-140.8 AGARWAL V, REJAIE R. Adaptive multisource streaming in heter