对等网络流媒体组播策略中遗传寻优算法的应用

杨棉绒

（新乡学院计算机与信息工程学院，河南新乡453003）

对等网络流媒体组播策略中遗传寻优算法的应用

杨棉绒

（新乡学院计算机与信息工程学院，河南新乡453003）

提出一种针对网络环境中流媒体传播与数据调度策略的改进方案，充分利用对等节点网络中子节点的资源来减轻服务器负载压力。基于遗传算法建立一种资源寻优策略，对服务器和对等网络节点中的数据资源进行更加优化的分配与调度。通过实验验证了算法的有效性。

对等网络数据调度；P2P数据传输；遗传算法；调度策略

目前，网络中流媒体服务基本都采用C/S工作方式，即使是播放嵌入到网页中的媒体文件，也是通过调用安装在本地浏览器上的多媒体播放插件来实现的，从本质上来讲，仍然属于基于C/S工作模式。C/S模式下流媒体数据调度算法分为两大类：静态调度算法和动态调度算法。

静态调度算法采用服务器推模式，即视频服务器不考虑用户动态行为而调度媒体流［1］。采用这种形式的视频服务网站一般会在网页中嵌入flash插件，用该插件直接播放从服务器推送来的流媒体视频。动态调度算法采用客户端拉模式，即媒体流的调度由用户请求驱动。在这种模式下，服务器根据用户请求到达的情况做出响应，动态选择调度方案，尽可能使不同的用户共享同一数据流，从而降低服务器带宽资源的消耗［2］。为此，学者们提出了众多的解决方案，但随着对等网络（下文简称P2P）数据传输技术的发展，该领域又产生了许多新的问题，如如何选择同一网络组中的优势资源节点、如何保障P2P网络环境中媒体源的数据完整性及节点用户计算资源和网络资源的占用率等问题。解决好这些问题，将对P2P组播技术产生积极的影响。

1　基于遗传算法的调度策略

总体上讲，P2P流媒体组播要解决的是异步资源调度问题，这是因为当用户在网络环境中播放媒体资源时，他们总是根据自己的需要来调整媒体播放的方式和进度，如从媒体中间部分开始播放、快进播放或者回看某个媒体片段。这些需求带来了一系列的资源调度问题，包括：如何选择网络中的资源节点，如何保障某个网段资源节点中媒体数据的完整性，如何让请求资源的用户得到最快速的数据响应等。可见，流媒体异步资源调度问题其实是多约束并发优化问题，因此无法给出完全满足每一个约束条件的最优答案。

本文将建立基于遗传寻优算法的数据模型，用来完成流媒体服务器的资源调度、负载的减小和更加有效地响应用户操作等任务。

本文P2P流媒体组播模型几个重要的假设条件如下。

1）在某个时间点t，网络中的某个资源节点Ni（i= 1，2，3，…，n）只能为一个媒体块Mi提供数据调度支撑。

2）在一次播放请求中，媒体块Mi只能有一个支撑节点。

3）节点Ni一旦响应某个播放请求后，在一定时间内不会中断。

4）每个节点都具有初步的并发响应能力（至少能响应3个并发访问请求）。

遗传算法是以编码空间代替问题的参数空间，以适应度函数为评价依据，以编码群体为进化基础，用群体中个体位串的遗传操作实现选择和遗传机制，建立起的一个迭代过程［3］。在多次迭代过程中，每次都要对新一代的个体位串通过适应度函数进行优选鉴别，形成更接近最优目标的个体。要利用遗传算法来解决流媒体资源调度问题，首要任务是解决用来表示受到各种约束的流媒体资源基因个体编码的问题。

2　个体基因编码的生成

在本文中，一个流媒体文件被分为大小相等的若干个片段，每个片段代表一次调度任务，由网络中的某个资源节点负责为该任务提供媒体数据，并以此为前提建立流媒体调度DNA模型。模型分两部分：第一部分为流媒体文件的片段序号，第二部分为每个片段所分配到的资源节点序号。例如，一个有12个片段、4个资源节点的DNA模型可以表示为［1，2，3，4，5，6，7，8，9，10，11，12#4，3，4，3，1，1，2，3，2，3，1，2］，其含义是：片段序号为1的媒体，在4号资源节点上进行数据调度；片段序号为2的媒体，在3号资源节点上进行数据调度；依此类推。因为流媒体的播放顺序与资源调度的先后无关，所以模型可简化成［4，3，4，3，1，1，2，3，2，3，1，2］，这样可使结构更加简单直观，利于设计更加高效的适应度函数。

3　初始群体的建立

DNA模型是对一个网络调度资源个体情况的描述，要想实施遗传寻优策略就必须建立一个作为祖先的初始基因群体。初始群体的建立过程并不复杂，但其规模和群体中个体DNA模型对原始资源节点的采样是否充分会直接影响后续族群的优选进度。笔者根据P2P资源访问调度实验的实测数据得出结论，最合适的初始种群中个体DNA模型的数量约是网络中有效资源节点数的8.7倍，为了计算简便，规定为9倍。

设网络中有n个能为媒体资源提供数据支撑的节点，待播放媒体被平均分割为m份，则每一份都有可能被n个资源节点中的某一个给予数据支持。初始群体产生的类C语言描述代码如下：

初始种群依托一个二维数组，数组中每行数据都代表一个资源调度DNA模型。代码中，数组共有9n行数据，代表初始种群中有9n个DNA模型作为数据调度的假设方案参与后续优选步骤。

4　适应度函数与优选流程

适应度函数的建立是遗传优选算法应用的关键。该函数通常是用来判断一个DNA个体优秀与否的依据；而用来表示流媒体调度方案的DNA是否优秀的关键在于，该DNA所代表的调度方案能不能让用户以更快的速度通过网络获得整个媒体文件。客户端获取媒体文件速度的主要约束条件有：一次调度周期中资源节点的上行带宽、资源节点的并发响应能力、是否存在用户所申请的子媒体块、当前CPU运算能力的剩余量和资源节点的空闲内存量等。根据这些约束条件建立的适应度函数为f=p1da+p2db+…+pndm。其中：da，db，…，dm为某约束条件实际值和期望值之间的偏差；p1，p2，…，pn为某约束条件分量重要程度的权值，且p1+p2+…+pn=1（0≤pi≤1，i=1，2，…，n）。根据文献［4］中设计的遗传算法制定了如图1所示的评估过程。

图1　媒体资源调度DNA群体优选流程评估过程

5　实验数据讨论

实验采用图1所示算法流程，设有100个用户并发访问一台100 M带宽的资源调度服务器，优选迭代次数为100次。改变初始种群中DNA个体的数量，得到的实验数据如图2所示。

图2　初始种群中DNA个体数量与适应度函数关系

由图2可以看出，初始种群规模为资源节点数的9倍时结果最佳。据此，设计如下实验：假设100个用户并发访问一台100 M带宽的资源调度服务器，初始种群规模为900个DNA模型个体。进行不同次数的遗传优选迭代，种群中每代被选中的DNA模型适应度函数平均值如图3所示。

从图3可以看出，迭代50次以后，适应度函数的值不再随迭代次数的增加而快速递增。因此本文将优选迭代的次数设置为50次。

根据图2和图3，实验设计如下：100个用户并发访问一台100 M带宽的资源调度服务器，采用图1所示优选策略，迭代50次，优选出调度DNA个体，并据此进行网络流媒体数据访问。实验结果与静态调度算法的对比如表1所示。

图3　迭代次数与适应度函数关系图

表1　静态调度算法与遗传寻优算法调度方案数据对比表

从表1可看出，本文所设计的调度方案有效地提高了客户端流媒体数据的获取速度，降低了对服务器运算资源和网络带宽资源的消耗。虽然方案增加了用户运算资源的消耗量，但它大幅度提高了用户流媒体数据的获取速度，总的来说，运算资源的消耗还是可以接受的。

6　结束语

虽然人们对P2P在流媒体方面的应用已经做了一些研究，并予以实现，但其性能和效果还有待提高。本文基于遗传算法提出一种资源寻优策略，对服务器和对等网络节点中数据资源的分配与调度进行了优化，并通过实验验证了策略的有效性。

［1］张立芳.基于遗传算法的P2P流媒体数据调度策略研究［J］.计算机与数字工程，2008（7）：31-33.

［2］廖建新，杨戈，朱晓民，等.基于代理缓存的移动流媒体动态调度算法［J］.计算机学报，2009（4）：1217-1223.

［3］付红帜.集成检索系统的研究与开发［D］.西安：西安电子科技大学，2007.

［4］张鑫，杨棉绒.基于遗传算法组卷策略的研究［J］.新乡学院学报（自然科学版），2010（2）：56-58.

【责任编辑梅欣丽】

The Application of Genetic Optimization Algorithm in Multicast Strategy of P2P Streaming Media

YANG Mianrong
（Computer and Information Engineering College，Xinxiang University，Xinxiang 453003，China）

The paper put forward an improved program focusing on strategies for streaming media transmission and data scheduling in network environment.The program aimed to reduce server’s load pressure by using the resources of sub-nodes in P2P network.0n the basis of genetic algorithm，the paper proposed a resource optimization strategy which could better the matching and scheduling of data resources in the server and P2P network.Finally，the paper verified the validity of algorithm through the experimental data.

P2P data scheduling；P2P data transmission；genetic algorithm；scheduling strategy

TP391.7

A

2095-7726（2015）09-0040-03

2015-07-01

杨棉绒（1979-），女，陕西兴平人，讲师，硕士，研究方向：软件工程和计算机网络。